IDEAS home Printed from https://ideas.repec.org/a/the/publsh/5380.html
   My bibliography  Save this article

A natural adaptive process for collective decision-making

Author

Listed:
  • Brandl, Florian

    (Department of Economics, University of Bonn)

  • Brandt, Felix

    (Department of Computer Science, Technische Universität München)

Abstract

Consider an urn filled with balls, each labeled with one of several possible collective decisions. Now, let a random voter draw two balls from the urn and pick her more preferred as the collective decision. Relabel the losing ball with the collective decision, put both balls back into the urn, and repeat. Once in a while, relabel a randomly drawn ball with a random collective decision. We prove that the empirical distribution of collective decisions produced by this process approximates a maximal lottery, a celebrated probabilistic voting rule proposed by Peter C. Fishburn (Rev. Econ. Stud., 51(4), 1984). In fact, the probability that the collective decision in round n is made according to a maximal lottery increases exponentially in n. The proposed procedure is more flexible than traditional voting rules and bears strong similarities to natural processes studied in biology, physics, and chemistry as well as algorithms proposed in machine learning.

Suggested Citation

  • Brandl, Florian & Brandt, Felix, 0. "A natural adaptive process for collective decision-making," Theoretical Economics, Econometric Society.
    • Handle: RePEc:the:publsh:5380
    as

    Download full text from publisher

    File URL: http://econtheory.org/ojs/index.php/te/article/viewForthcomingFile/5380/36377/1
    File Function: Working paper version. Paper will be copyedited and typeset before publication.
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Myerson, Roger B., 1993. "Incentives to Cultivate Favored Minorities Under Alternative Electoral Systems," American Political Science Review, Cambridge University Press, vol. 87(4), pages 856-869, December.
    2. Jacopo Grilli & György Barabás & Matthew J. Michalska-Smith & Stefano Allesina, 2017. "Higher-order interactions stabilize dynamics in competitive network models," Nature, Nature, vol. 548(7666), pages 210-213, August.
    3. Foster, Dean P. & Vohra, Rakesh, 1999. "Regret in the On-Line Decision Problem," Games and Economic Behavior, Elsevier, vol. 29(1-2), pages 7-35, October.
    4. Benoit Laslier & Jean-François Laslier, 2017. "Reinforcement learning from comparisons: Three alternatives are enough, two are not," PSE-Ecole d'économie de Paris (Postprint) halshs-01630231, HAL.
    5. Sergiu Hart & Andreu Mas-Colell, 2013. "A Simple Adaptive Procedure Leading To Correlated Equilibrium," World Scientific Book Chapters, in: Simple Adaptive Strategies From Regret-Matching to Uncoupled Dynamics, chapter 2, pages 17-46, World Scientific Publishing Co. Pte. Ltd..
    6. Laffond, Gilbert & Laslier, Jean-Francois & Le Breton, Michel, 1997. "A Theorem on Symmetric Two-Player Zero-Sum Games," Journal of Economic Theory, Elsevier, vol. 72(2), pages 426-431, February.
    7. Michel BenaÔm & J–rgen W. Weibull, 2003. "Deterministic Approximation of Stochastic Evolution in Games," Econometrica, Econometric Society, vol. 71(3), pages 873-903, May.
    8. Florian Brandl & Felix Brandt, 2020. "Arrovian Aggregation of Convex Preferences," Econometrica, Econometric Society, vol. 88(2), pages 799-844, March.
    9. William V. Gehrlein & Dominique Lepelley, 2011. "Voting paradoxes and group coherence: the condorcet efficiency of voting rules," Post-Print hal-01243452, HAL.
    10. William V. Gehrlein & Dominique Lepelley, 2011. "Voting Paradoxes and Group Coherence," Studies in Choice and Welfare, Springer, number 978-3-642-03107-6, December.
    11. Carbonell-Nicolau, Oriol & Ok, Efe A., 2007. "Voting over income taxation," Journal of Economic Theory, Elsevier, vol. 134(1), pages 249-286, May.
    12. P. C. Fishburn, 1984. "Probabilistic Social Choice Based on Simple Voting Comparisons," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 51(4), pages 683-692.
    13. Josef Hofbauer & William H. Sandholm, 2002. "On the Global Convergence of Stochastic Fictitious Play," Econometrica, Econometric Society, vol. 70(6), pages 2265-2294, November.
    14. Gibbard, Allan, 1977. "Manipulation of Schemes That Mix Voting with Chance," Econometrica, Econometric Society, vol. 45(3), pages 665-681, April.
    15. Satterthwaite, Mark Allen, 1975. "Strategy-proofness and Arrow's conditions: Existence and correspondence theorems for voting procedures and social welfare functions," Journal of Economic Theory, Elsevier, vol. 10(2), pages 187-217, April.
    16. Johannes Knebel & Markus F. Weber & Torben Krüger & Erwin Frey, 2015. "Evolutionary games of condensates in coupled birth–death processes," Nature Communications, Nature, vol. 6(1), pages 1-9, November.
    17. Florian Brandl & Felix Brandt & Christian Stricker, 2022. "An analytical and experimental comparison of maximal lottery schemes," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 58(1), pages 5-38, January.
    18. Jean-François Laslier, 2011. "And the loser is... Plurality Voting," Working Papers hal-00609810, HAL.
    19. Jac C. Heckelman, 2003. "Probabilistic Borda rule voting," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 21(3), pages 455-468, December.
    20. Florian Brandl & Felix Brandt & Hans Georg Seedig, 2016. "Consistent Probabilistic Social Choice," Econometrica, Econometric Society, vol. 84, pages 1839-1880, September.
    21. Gibbard, Allan, 1973. "Manipulation of Voting Schemes: A General Result," Econometrica, Econometric Society, vol. 41(4), pages 587-601, July.
    22. Brandt, Felix & Fischer, Felix, 2008. "Computing the minimal covering set," Mathematical Social Sciences, Elsevier, vol. 56(2), pages 254-268, September.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Florian Brandl & Felix Brandt, 2021. "A Natural Adaptive Process for Collective Decision-Making," Papers 2103.14351, arXiv.org, revised Mar 2024.
    2. Florian Brandl & Felix Brandt & Christian Stricker, 2022. "An analytical and experimental comparison of maximal lottery schemes," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 58(1), pages 5-38, January.
    3. Aziz, Haris & Brandl, Florian & Brandt, Felix & Brill, Markus, 2018. "On the tradeoff between efficiency and strategyproofness," Games and Economic Behavior, Elsevier, vol. 110(C), pages 1-18.
    4. Brandt, Felix & Saile, Christian & Stricker, Christian, 2022. "Strategyproof social choice when preferences and outcomes may contain ties," Journal of Economic Theory, Elsevier, vol. 202(C).
    5. Chatterji, Shurojit & Zeng, Huaxia, 2018. "On random social choice functions with the tops-only property," Games and Economic Behavior, Elsevier, vol. 109(C), pages 413-435.
    6. Pycia, Marek & Ünver, M. Utku, 2015. "Decomposing random mechanisms," Journal of Mathematical Economics, Elsevier, vol. 61(C), pages 21-33.
    7. Peter Fishburn & Steven Brams, 1984. "Manipulability of voting by sincere truncation of preferences," Public Choice, Springer, vol. 44(3), pages 397-410, January.
    8. Felix Brandt & Patrick Lederer & Ren'e Romen, 2022. "Relaxed Notions of Condorcet-Consistency and Efficiency for Strategyproof Social Decision Schemes," Papers 2201.10418, arXiv.org.
    9. Felix Brand & Patrick Lederer & Sascha Tausch, 2023. "Strategyproof Social Decision Schemes on Super Condorcet Domains," Papers 2302.12140, arXiv.org.
    10. Chatterji, Shurojit & Roy, Souvik & Sadhukhan, Soumyarup & Sen, Arunava & Zeng, Huaxia, 2022. "Probabilistic fixed ballot rules and hybrid domains," Journal of Mathematical Economics, Elsevier, vol. 100(C).
    11. Andriy Zapechelnyuk, 2009. "Limit Behavior of No-regret Dynamics," Discussion Papers 21, Kyiv School of Economics.
    12. Maurice Salles, 2014. "‘Social choice and welfare’ at 30: its role in the development of social choice theory and welfare economics," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 42(1), pages 1-16, January.
    13. Lirong Xia, 2021. "The Smoothed Satisfaction of Voting Axioms," Papers 2106.01947, arXiv.org.
    14. Lê Nguyên Hoang, 2017. "Strategy-proofness of the randomized Condorcet voting system," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 48(3), pages 679-701, March.
    15. Federico Echenique & Joseph Root & Fedor Sandomirskiy, 2022. "Efficiency in Random Resource Allocation and Social Choice," Papers 2203.06353, arXiv.org, revised Aug 2022.
    16. Benaïm, Michel & Hofbauer, Josef & Hopkins, Ed, 2009. "Learning in games with unstable equilibria," Journal of Economic Theory, Elsevier, vol. 144(4), pages 1694-1709, July.
    17. Souvik Roy & Soumyarup Sadhukhan, 2019. "A characterization of random min–max domains and its applications," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 68(4), pages 887-906, November.
    18. Gehrlein, William V. & Moyouwou, Issofa & Lepelley, Dominique, 2013. "The impact of voters’ preference diversity on the probability of some electoral outcomes," Mathematical Social Sciences, Elsevier, vol. 66(3), pages 352-365.
    19. Berghammer, Rudolf & Schnoor, Henning, 2015. "Control of Condorcet voting: Complexity and a Relation-Algebraic approach," European Journal of Operational Research, Elsevier, vol. 246(2), pages 505-516.
    20. Emerson Melo, 2021. "Learning in Random Utility Models Via Online Decision Problems," Papers 2112.10993, arXiv.org, revised Aug 2022.

    More about this item

    Keywords

    Probabilistic social choice; maximal lotteries; Markov processes;
    All these keywords.

    JEL classification:

    • D70 - Microeconomics - - Analysis of Collective Decision-Making - - - General
    • C73 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Stochastic and Dynamic Games; Evolutionary Games

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:the:publsh:5380. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Martin J. Osborne (email available below). General contact details of provider: http://econtheory.org .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.