4 papers
Undecided State Dynamics with Many Opinions
Colin Cooper, Frederik Mallmann-Trenn, Tomasz Radzik +2
We study the Undecided-State Dynamics (USD), a fundamental consensus process in which each vertex holds one of decided opinions or the undecided state. We consider both the gos…
3-Majority and 2-Choices with Many Opinions
Nobutaka Shimizu, Takeharu Shiraga
We present the first nearly-optimal bounds on the consensus time for the well-known synchronous consensus dynamics, specifically 3-Majority and 2-Choices, for an arbitrary number o…
Asynchronous 3-Majority Dynamics with Many Opinions
Colin Cooper, Frederik Mallmann-Trenn, Tomasz Radzik +2
We consider 3-Majority, a probabilistic consensus dynamics on a complete graph with vertices, each vertex starting with one of initial opinions. At each discrete time step,…
Discrete Incremental Voting on Expanders
Colin Cooper, Tomasz Radzik, Takeharu Shiraga
Pull voting is a random process in which vertices of a connected graph have initial opinions chosen from a set of distinct opinions, and at each step a random vertex alters its…