IDEAS home Printed from https://ideas.repec.org/p/pra/mprapa/112004.html
   My bibliography  Save this paper

A Combinatorial Topology Approach to Arrow's Impossibility Theorem

Author

Listed:
  • Rajsbaum, Sergio
  • Raventós-Pujol, Armajac

Abstract

Baryshnikov presented a remarkable algebraic topology proof of Arrow's impossibility theorem trying to understand the underlying reason behind the numerous proofs of this fundamental result of social choice theory. We present here a novel combinatorial topology approach that does not use advance mathematics, while giving a geometric intuition of the impossibility. This exposes a remarkable connection with distributed computing techniques. We show that Arrow's impossibility is closely related to the index lemma, and expose the geometry behind prior pivotal arguments to Arrow's impossibility. We explain why the case of two voters, n=2, and three alternatives, |X|=3, is where this interesting geometry happens, by giving a simple proof that this case implies Arrow's impossibility for any finite n>= 2,|X|>= 3. Finally, we show how to reason about domain restrictions using combinatorial topology.

Suggested Citation

  • Rajsbaum, Sergio & Raventós-Pujol, Armajac, 2022. "A Combinatorial Topology Approach to Arrow's Impossibility Theorem," MPRA Paper 112004, University Library of Munich, Germany.
  • Handle: RePEc:pra:mprapa:112004
    as

    Download full text from publisher

    File URL: https://mpra.ub.uni-muenchen.de/112004/1/MPRA_paper_112004.pdf
    File Function: original version
    Download Restriction: no

    File URL: https://mpra.ub.uni-muenchen.de/113858/1/MPRA_paper_112004.pdf
    File Function: revised version
    Download Restriction: no

    File URL: https://mpra.ub.uni-muenchen.de/113858/8/MPRA_paper_113858.pdf
    File Function: revised version
    Download Restriction: no

    File URL: https://mpra.ub.uni-muenchen.de/120023/1/MPRA_paper_120023.pdf
    File Function: revised version
    Download Restriction: no

    File URL: https://mpra.ub.uni-muenchen.de/113861/8/MPRA_paper_113858.pdf
    File Function: revised version
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Chichilnisky, Graciela & Heal, Geoffrey, 1983. "Necessary and sufficient conditions for a resolution of the social choice paradox," Journal of Economic Theory, Elsevier, vol. 31(1), pages 68-87, October.
    2. Le Breton, Michel & Weymark, John A., 2011. "Chapter Seventeen - Arrovian Social Choice Theory on Economic Domains," Handbook of Social Choice and Welfare, in: K. J. Arrow & A. K. Sen & K. Suzumura (ed.), Handbook of Social Choice and Welfare, edition 1, volume 2, chapter 17, pages 191-299, Elsevier.
    3. Allan M. Feldman & Roberto Serrano, 2006. "Welfare Economics and Social Choice Theory, 2nd Edition," Springer Books, Springer, edition 2, number 978-0-387-29368-4, January.
    4. Kenneth J. Arrow, 1950. "A Difficulty in the Concept of Social Welfare," Journal of Political Economy, University of Chicago Press, vol. 58(4), pages 328-328.
    5. Lauwers, Luc, 2000. "Topological social choice," Mathematical Social Sciences, Elsevier, vol. 40(1), pages 1-39, July.
    6. Mock, Andrea & Volić, Ismar, 2021. "Political structures and the topology of simplicial complexes," Mathematical Social Sciences, Elsevier, vol. 114(C), pages 39-57.
    7. Tanaka, Yasuhito, 2009. "On the equivalence of the Arrow impossibility theorem and the Brouwer fixed point theorem when individual preferences are weak orders," Journal of Mathematical Economics, Elsevier, vol. 45(3-4), pages 241-249, March.
    8. Luc Lauwers, 2009. "The topological approach to the aggregation of preferences," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 33(3), pages 449-476, September.
    9. Salvador Barberà & Dolors Berga & Bernardo Moreno, 2020. "Arrow on domain conditions: a fruitful road to travel," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 54(2), pages 237-258, March.
    10. Fishburn, Peter C., 1970. "Arrow's impossibility theorem: Concise proof and infinite voters," Journal of Economic Theory, Elsevier, vol. 2(1), pages 103-106, March.
    11. Yuliy M. Baryshnikov, 1997. "Topological and discrete social choice: in a search of a theory," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 14(2), pages 199-209.
    12. Baigent, Nicholas, 2011. "Chapter Eighteen - Topological Theories of Social Choice," Handbook of Social Choice and Welfare, in: K. J. Arrow & A. K. Sen & K. Suzumura (ed.), Handbook of Social Choice and Welfare, edition 1, volume 2, chapter 18, pages 301-334, Elsevier.
    13. K. J. Arrow & A. K. Sen & K. Suzumura (ed.), 2011. "Handbook of Social Choice and Welfare," Handbook of Social Choice and Welfare, Elsevier, edition 1, volume 2, number 2.
    14. Gaertner, Wulf, 2009. "A Primer in Social Choice Theory: Revised Edition," OUP Catalogue, Oxford University Press, number 9780199565306, Decembrie.
    15. Ning Yu, 2015. "A quest for fundamental theorems of social choice," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 44(3), pages 533-548, March.
    16. Saari, Donald G., 2011. "Chapter Twenty-Seven - Geometry of Voting," Handbook of Social Choice and Welfare, in: K. J. Arrow & A. K. Sen & K. Suzumura (ed.), Handbook of Social Choice and Welfare, edition 1, volume 2, chapter 27, pages 897-945, Elsevier.
    17. Andrea Mock & Ismar Volic, 2021. "Political structures and the topology of simplicial complexes," Papers 2104.02131, arXiv.org, revised Dec 2021.
    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. Guillaume Chèze, 2017. "Topological aggregation, the twin paradox and the No Show paradox," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 48(4), pages 707-715, April.
    2. Andrea Attar & Thomas Mariotti & François Salanié, 2019. "On a class of smooth preferences," Economic Theory Bulletin, Springer;Society for the Advancement of Economic Theory (SAET), vol. 7(1), pages 37-57, May.
    3. Greenfield, Mark & Zhang, Jun, 2018. "Null preference and the resolution of the topological social choice paradox," Mathematical Social Sciences, Elsevier, vol. 93(C), pages 47-51.
    4. Susumu Cato, 2018. "Collective rationality and decisiveness coherence," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 50(2), pages 305-328, February.
    5. Crespo, Juan A. & Sanchez-Gabites, J.J, 2016. "Solving the Social Choice problem under equality constraints," MPRA Paper 72757, University Library of Munich, Germany.
    6. Leo Katz & Alvaro Sandroni, 2020. "Limits on power and rationality," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 54(2), pages 507-521, March.
    7. Nicola Acocella-super-, 2017. "The Rise And Decline Of Economic Policy As An Autonomous Discipline: A Critical Survey," Journal of Economic Surveys, Wiley Blackwell, vol. 31(3), pages 661-677, July.
    8. Lauwers, Luc, 2000. "Topological social choice," Mathematical Social Sciences, Elsevier, vol. 40(1), pages 1-39, July.
    9. Marek Pycia & M. Utku Ünver, 2021. "Arrovian Efficiency and Auditability in Discrete Mechanism Design," Boston College Working Papers in Economics 1044, Boston College Department of Economics.
    10. Yasuhito Tanaka, 2005. "A topological approach to the Arrow impossibility theorem when individual preferences are weak orders (forcoming in ``Applied Mathematics and Compuation''(Elsevier))," Public Economics 0506013, University Library of Munich, Germany, revised 17 Jun 2005.
    11. Bossert, Walter & Peters, Hans, 2014. "Single-basined choice," Journal of Mathematical Economics, Elsevier, vol. 52(C), pages 162-168.
    12. Mongin, Philippe, 2019. "Interview of Peter J. Hammond," CRETA Online Discussion Paper Series 50, Centre for Research in Economic Theory and its Applications CRETA.
    13. Kari Saukkonen, 2007. "Continuity of social choice functions with restricted coalition algebras," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 28(4), pages 637-647, June.
    14. Susumu Cato, 2010. "Brief proofs of Arrovian impossibility theorems," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 35(2), pages 267-284, July.
    15. Armajac Raventós-Pujol & María J. Campión & Esteban Induráin, 2020. "Decomposition and Arrow-Like Aggregation of Fuzzy Preferences," Mathematics, MDPI, vol. 8(3), pages 1-18, March.
    16. Duddy, Conal & Piggins, Ashley, 2020. "A foundation for Pareto optimality," Journal of Mathematical Economics, Elsevier, vol. 88(C), pages 25-30.
    17. David Canning, 2007. "Valuing Lives Equally and Welfare Economics," PGDA Working Papers 2707, Program on the Global Demography of Aging.
    18. Alberto Vesperoni, 2016. "A contest success function for rankings," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 47(4), pages 905-937, December.
    19. Muto, Nozomu & Sato, Shin, 2016. "Bounded response of aggregated preferences," Journal of Mathematical Economics, Elsevier, vol. 65(C), pages 1-15.
    20. Muto, Nozomu & Sato, Shin, 2017. "An impossibility under bounded response of social choice functions," Games and Economic Behavior, Elsevier, vol. 106(C), pages 1-15.

    More about this item

    Keywords

    Social choice; Arrow impossibility theorem; Combinatorial topology; Distributed computing; Topological social choice; Simplicial complexes; Domain restriction; Index lemma;
    All these keywords.

    JEL classification:

    • D71 - Microeconomics - - Analysis of Collective Decision-Making - - - Social Choice; Clubs; Committees; Associations

    NEP fields

    This paper has been announced in the following NEP Reports:

    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:pra:mprapa:112004. 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: Joachim Winter (email available below). General contact details of provider: https://edirc.repec.org/data/vfmunde.html .

    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.