@inproceedings{20052,
  abstract     = {This paper revisits a fundamental distributed computing problem in the population protocol model. Provided n agents each starting with an input color in [k], the relative majority problem asks to find the predominant color. In the population protocol model, at each time step, a scheduler selects two agents that first learn each other's states and then update their states based on what they learned.
We present the Circles protocol that solves the relative majority problem with k3 states. It is always-correct under weakly fair scheduling. Not only does it improve upon the best known upper bound of O(k7), but it also shows a strikingly simpler design inspired by energy minimization in chemical settings.},
  author       = {Breitkopf, Tom-Lukas and Dallot, Julien and El-Hayek, Antoine and Schmid, Stefan},
  booktitle    = {Proceedings of the ACM Symposium on Principles of Distributed Computing},
  isbn         = {9798400718854},
  location     = {Huatulco, Mexico},
  pages        = {549--552},
  publisher    = {Association for Computing Machinery},
  title        = {{Brief announcement: Minimizing energy solves relative majority with a cubic number of states in population protocols}},
  doi          = {10.1145/3732772.3733512},
  year         = {2025},
}

@inproceedings{20053,
  abstract     = {Liquid democracy is a transitive vote delegation mechanism over voting graphs. It enables each voter to delegate their vote(s) to another better-informed voter, with the goal of collectively making a better decision. The question of whether liquid democracy outperforms direct voting has been previously studied in the context of local delegation mechanisms (where voters can only delegate to someone in their neighbourhood) and binary decision problems. It has previously been shown that it is impossible for local delegation mechanisms to outperform direct voting in general graphs. This raises the question: for which classes of graphs do local delegation mechanisms yield good results?
In this work, we analyse (1) properties of specific graphs and (2) properties of local delegation mechanisms on these graphs, determining where local delegation actually outperforms direct voting. We show that a critical graph property enabling liquid democracy is that the voting outcome of local delegation mechanisms preserves a sufficient amount of variance, thereby avoiding situations where delegation falls behind direct voting1. These insights allow us to prove our main results, namely that there exist local delegation mechanisms that perform no worse and in fact quantitatively better than direct voting in natural graph topologies like complete, random d-regular, and bounded degree graphs, lending a more nuanced perspective to previous impossibility results.},
  author       = {Chatterjee, Krishnendu and Gilbert, Seth and Schmid, Stefan and Svoboda, Jakub and Yeo, Michelle X},
  booktitle    = {Proceedings of the ACM Symposium on Principles of Distributed Computing},
  isbn         = {9798400718854},
  location     = {Huatulco, Mexico},
  pages        = {241--251},
  publisher    = {Association for Computing Machinery},
  title        = {{When is liquid democracy possible?: On the manipulation of variance}},
  doi          = {10.1145/3732772.3733544},
  year         = {2025},
}