3-Majority and 2-Choices with Many Opinions
Nobutaka Shimizu, Takeharu Shiraga · 2025
Read 3-Majority and 2-Choices with Many Opinions by Nobutaka Shimizu, Takeharu Shiraga (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-02426.txt.
Description
Nobutaka Shimizu and Takeharu Shiraga settle how fast two classic voting rules reach agreement when many opinions compete, in a 2025 paper. In these rules, every node in a network polls a few random neighbors each round and may switch to their opinion. One rule samples three neighbors and follows the majority, and the other samples two and follows them only when they agree. Earlier bounds on the time to full consensus were loose, especially with many opinions.
The pair prove nearly exact bounds for both rules across every number of opinions up to the network size. The three-sample rule settles in a time governed by the smaller of the opinion count and the square root of the network size. The two-sample rule's time simply tracks the opinion count. Their results close a line of work stretching back a decade. Such rules model gossip, load balancing, and distributed agreement.
Catalog record
| CREATOR | Nobutaka Shimizu, Takeharu Shiraga |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 174 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-02426