Arrow Research search

Author name cluster

Colin Cooper

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

19 papers
2 author rows

Possible papers

19

SODA Conference 2025 Conference Paper

Asynchronous 3-Majority Dynamics with Many Opinions

  • Colin Cooper
  • Frederik Mallmann-Trenn
  • Tomasz Radzik
  • Nobutaka Shimizu
  • Takeharu Shiraga

We consider 3-Majority, a probabilistic consensus dynamics on a complete graph with n vertices, each vertex starting with one of k initial opinions. At each discrete time step, a vertex u is chosen uniformly at random. The selected vertex u chooses three neighbors v 1, v 2, v 3 uniformly at random with replacement and takes the majority opinion held by the three, where ties are broken in favor of the opinion of v 3. The main quantity of interest is the consensus time, the number of steps required for all vertices to hold the same opinion. This asynchronous version turns out to be considerably harder to analyze than the synchronous version and so far results have only been obtained for k = 2. Even in the synchronous version the results for large k are far from tight. In this paper we prove that the consensus time is for all k. These are the first bounds for all k that are tight up to a polylogarithmic factor.

Details

UAI Conference 2022 Conference Paper

On early extinction and the effect of travelling in the SIR model

  • Petra Berenbrink
  • Colin Cooper
  • Cristina Gava
  • David Kohan Marzagão
  • Frederik Mallmann-Trenn
  • Tomasz Radzik

We consider a population protocol version of the SIR model. In every round, an individual is chosen uniformly at random. If the individual is susceptible, then it becomes infected w. p. $\beta I_t/N$, where $I_t$ is the number of infections at time $t$ and $N$ is the total number of individuals. If the individual is infected, then it recovers w. p. $\gamma$, whereas, if the individual is already recovered, nothing happens. We prove sharp bounds on the probability of the disease becoming pandemic vs extinguishing early (dying out quickly). The probability of extinguishing early, $\Pr{\mathcal{E}_{ext}}$, is typically neglected in prior work since most use (deterministic) differential equations. Leveraging on this, using $\Pr{\mathcal{E}_{ext}}$, we proceed by bounding the expected size of the population that contracts the disease $\mathbf{E}\left[R_\infty\right]$. Prior work only calculated $\mathbf{E}\left[R_\infty | \overline{\mathcal{E}_{ext}}\right]$, or obtained non-closed form solutions. We then study the two-country model also accounting for the role of $\Pr{\mathcal{E}_{ext}}$. We assume that both countries have different infection rates $\beta^{(i)}$, but share the same recovery rate $\gamma$. In this model, each round has two steps: First, an individual is chosen u. a. r. and travels w. p. $p_{travel}$ to the other country. Afterwards, the process continues as before with the respective infection rates. Finally, using simulations, we characterise the influence of $p_{travel}$ on the total number of infections. Our simulations show that, depending on the $\beta^{(i)}$, increasing $p_{travel}$ can decrease or increase the expected total number of infections $\mathbf{E}\left[R_\infty\right]$.

Details

SODA Conference 2019 Conference Paper

On the rank of a random binary matrix

  • Colin Cooper
  • Alan M. Frieze
  • Wesley Pegden

We study the rank of a random n × m matrix A n, m; k with entries from GF (2), and exactly k unit entries in each column, the other entries being zero. The columns are chosen independently and uniformly at random from the set of all ( n k ) such columns. We obtain an asymptotically correct estimate for the rank as a function of the number of columns m in terms of c, n, k, and where m = cn/k. The matrix A n, m; k forms the vertex-edge incidence matrix of a k -uniform random hypergraph H. The rank of A n, m; k can be expressed as follows. Let | C 2 | be the number of vertices of the 2-core of H, and | E ( C 2 )| the number of edges. Let m* be the value of m for which | C 2 | = | E ( C 2 )|. Then w. h. p. for m < m * the rank of A n, m; k is asymptotic to m, and for m ≥ m * the rank is asymptotic to m – | E ( C 2 )| + | C 2 |. In addition, assign i. i. d. U [0, 1] weights X i, i ∊ 1, 2, … m to the columns, and define the weight of a set of columns S as X ( S ) = ∑ j ∊ S X j. Define a basis as a set of n – 1 ( k even) linearly independent columns. We obtain an asymptotically correct estimate for the minimum weight basis. This generalises the well-known result of Frieze [On the value of a random minimum spanning tree problem, Discrete Applied Mathematics, (1985)] that, for k = 2, the expected length of a minimum weight spanning tree tends to ζ(3) ∼ 1. 202.

Details

AAMAS Conference 2017 Conference Paper

Multi-Agent Flag Coordination Games

  • David Kohan Marzag&atilde; o
  • Nicol&aacute; s Rivera
  • Colin Cooper
  • Peter McBurney
  • Kathleen Steinh&ouml; fel

Many multi-agent coordination problems can be understood as autonomous local choices between a finite set of options, with each local choice undertaken simultaneously without explicit coordination between decision-makers, and with a shared goal of achieving a desired global state or states. Examples of such problems include classic consensus problems between nodes in a distributed computer network and the adoption of competing technology standards. We model such problems as a multi-round game between agents having flags of different colours to represent the finite choice options, and all agents seeking to achieve global patterns of colours through a succession of local colour-selection choices. We generalise and formalise the problem, proving results for the probabilities of achievement of common desired global states when these games are undertaken on bipartite graphs, extending known results for non-bipartite graphs. We also calculate probabilities for the game entering infinite cycles of non-convergence. In addition, we present a game-theoretic approach to the problem that has a mixed-strategy Nash equilibrium where two players can simultaneously flip the colour of one of the opponent’s nodes in the bipartite graph before or during a flag-coordination game.

PDF