Rajsbaum, Sergio and RaventósPujol, Armajac (2022): A Combinatorial Topology Approach to Arrow's Impossibility Theorem.
This is the latest version of this item.
Preview 
PDF
MPRA_paper_113858.pdf Download (3MB)  Preview 
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 a combinatorial topology proof that does not use advance mathematics, and gives a very intuitive geometric reason for Arrow’s impossibility. The geometric proof for the basis case of two voters, n=2, and three alternatives, X=3, is based on the index lemma, that counts the absolute number of times that a closed curve in the plane travels around a point. This yields a characterization of the domain restrictions that allow nondictatorial aggregation functions. It also exposes the geometry behind prior pivotal arguments to Arrow’s impossibility. We explain why the basis case of two voters, is where this interesting geometry happens, by giving a simple proof that this case implies Arrow’s impossibility for any X≥ 3 and any finite n≥2.
Item Type:  MPRA Paper 

Original Title:  A Combinatorial Topology Approach to Arrow's Impossibility Theorem 
Language:  English 
Keywords:  Social choice; Arrow impossibility theorem; Combinatorial topology; Distributed computing; Topological social choice; Simplicial complexes; Domain restriction; Index lemma 
Subjects:  D  Microeconomics > D7  Analysis of Collective DecisionMaking > D71  Social Choice ; Clubs ; Committees ; Associations 
Item ID:  113861 
Depositing User:  Armajac Raventós Pujol 
Date Deposited:  27 Jul 2022 23:06 
Last Modified:  27 Jul 2022 23:06 
References:  Applications of combinatorial topology to computer science. In Lisbeth Fajstrup, Dmitry FeichtnerKozlov, Robert Ghrist, and Maurice Herlihy, editors, Dagstuhl Report 12121, Issue 3, volume 2 of Seminar, Germany, March 2012. Dagstuhl, LeibnizZentrum fur Informatik. Koichiro Akashi. A Simplified Derivation of Arrow’s Impossibility Theorem. Hitotsubashi Journal of Economics, 46(2):177–181, nov 2005. Kenneth J. Arrow. A difficulty in the concept of social welfare. Journal of Political Economy, 58(4):328–346, 1950. Kenneth Joseph Arrow. Social Choice and Individual Values. Cowles Commission Monograph No. 12. John Wiley & Sons, Inc., New York, N. Y.; Chapman & Hall, Ltd., London, 1951. Hagit Attiya and Sergio Rajsbaum. The combinatorial structure of waitfree solvable tasks. SIAM J. Comput., 31(4):1286–1313, 2002. Hagit Attiya and Jennifer Welch. Distributed Computing: Fundamentals, Simulations and Advanced Topics. John Wiley & Sons, Hoboken, NJ, USA, 2004. Vahid Babaei and Roger D. Hersch. $n$ ink printer characterization with barycentric subdivision. IEEE Transactions on Image Processing, 25:3023–3031, 2016. Salvador Barberá. Pivotal voters: A new proof of arrow’s theorem. Economics Letters, 6(1):13–16, 1980. Salvador Barberà, Dolors Berga, and Bernardo Moreno. Arrow on domain conditions: a fruitful road to travel. Social Choice and Welfare, 54(2):237–258, 2020. Yuliy M. Baryshnikov. Unifying impossibility theorems: A topological approach. Advances in Applied Mathematics, 14(4):404–415, 1993. Yuliy M. Baryshnikov. Topological and discrete social choice: in a search of a theory. Social Choice and Welfare, 14(2):199–209, 1997. Duncan Black. On the rationale of group decisionmaking. Journal of Political Economy, 56(1):23–34, 1948. Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel D. Procaccia. Handbook of Computational Social Choice. Cambridge University Press, USA, 1st edition, 2016. Armando Castañeda and Sergio Rajsbaum. New combinatorial topology bounds for renaming: the lower bound. Distributed Computing, 22:287–301, 2010. Wei Han Chia. The topological apprach to social choice. http://math.uchicago.edu/~may/REU2015/REUPapers/Chia.pdf, September 2015. G Chichilnisky and G Heal. Necessary and sufficient conditions for a resolution of the social choice paradox. Journal of Economic Theory, 31(1):68–87, 1983. Saari Donald G. Chapter twentyseven  geometry of voting. In Kenneth J. Arrow, Amartya Sen, and Kotaro Suzumura, editors, Handbook of Social Choice and Welfare, volume 2 of Handbook of Social Choice and Welfare, pages 897–945. Elsevier, 2011. Beno Eckmann. Social choice and topology a case of pure and applied mathematics. Expositiones Mathematicae, 22(4):385–393, 2004. Edith Elkind, Martin Lackner, and Dominik Peters. Preference restrictions in computational social choice: A survey, May 2022. arXiv:2205.09092, 116 pages. Ky Fan. Simplicial maps from an orientable npseudomanifold into sm with the octahedral triangulation. Journal of Combinatorial Theory, 2(4):588–602, 1967. Allan M. Feldman and Roberto Serrano. Welfare Economics and Social Choice Theory, 2nd Edition. Springer, 2006. Allan M. Feldman and Roberto Serrano. Arrow’s impossibility theorem: Two simple singleprofile versions. Working Paper 20088, Brown University, Department of Economics, Providence, RI, 2008. P C Fishburn. Arrow’s impossibility theorem: Concise proof and infinite voters. Journal of Economic Theory, 2(1):103–106, 1970. P C Fishburn. Dictators on blocks: Generalizations of social choice impossibility theorems. Journal of Combinatorial Theory, Series B, 20(2):153–170, 1976. Peter C Fishburn. Impossibility Theorems without the Social Completeness Axiom. Econometrica, 42(4):695–704, 1974. Roy Friedman, Achour Mostefaoui, Sergio Rajsbaum, and Michel Raynal. Asynchronous agreement and its relation with errorcorrecting codes. IEEE Transactions on Computers, 56(7):865–875, 2007. Wulf Gaertner. Chapter 3 domain restrictions. In Handbook of Social Choice and Welfare, volume 1 of Handbook of Social Choice and Welfare, pages 131–170. Elsevier, 2002. Wulf Gaertner. A Primer in Social Choice Theory: Revised Edition. Oxford University Press, 2009. J Geanakoplos. Three brief proofs of Arrow’s Impossibility Theorem. Economic Theory, 26(1):211–215, 2005. Éric Goubault, Marijana Lazic, Jérémy Ledent, and Sergio Rajsbaum. WaitFree Solvability of Equality Negation Tasks. In Jukka Suomela, editor, 33rd International Symposium on Distributed Computing (DISC 2019), volume 146 of Leibniz International Proceedings in Informatics (LIPIcs), pages 21:1–21:16, Dagstuhl, Germany, 2019. Schloss Dagstuhl–LeibnizZentrum fuer Informatik. Michael Henle. A Combinatorial Introduction To Topology. Dover, New York, 1994. Maurice Herlihy, Dmitry N. Kozlov, and Sergio Rajsbaum. Distributed Computing Through Combinatorial Topology. Morgan Kaufmann, 2013. Maurice Herlihy and Nir Shavit. The topological structure of asynchronous computability. J. ACM, 46(6):858–923, 1999. Ken ichi Inada. Elementary proofs of some theorems about the social welfare function. Annals of the Institute of Statistical Mathematics, 6:115–122, 1954. Harish Kannan, Emil Saucan, Indrava Roy, and Areejit Samal. Persistent homology of unweighted complex networks via discrete morse theory. Scientific Reports, 9(1):13817, 2019. Dmitry N. Kozlov. Combinatorial Algebraic Topology, volume 21 of Algorithms and computation in mathematics. Springer, 2008. Dmitry N. Kozlov. Structure theory of flip graphs with applications to weak symmetry breaking. J. Appl. Comput. Topol., 1(1):1–55, 2017. Luc Lauwers. Topological social choice. Mathematical Social Sciences, 40(1):1–39, 2000. Luc Lauwers. The topological approach to the aggregation of preferences. Social Choice and Welfare, 33(3):449–476, 2009. Michel Le Breton and John A Weymark. Chapter Seventeen  Arrovian Social Choice Theory on Economic Domains. In Kenneth J Arrow, Amartya Sen, and Kotaro Suzumura, editors, Handbook of Social Choice and Welfare, volume 2 of Handbook of Social Choice and Welfare, pages 191–299. Elsevier, 2011. JanPhilipp Litza. Weak symmetry breaking and simplex path demonochromatizing. Master’s thesis, Bremen University, Germany, March 2015. Supervisor Dmitry FeichtnerKozlov 2015. Andrea Mock and Ismar Volić. Political structures and the topology of simplicial complexes. Mathematical Social Sciences, 114:39–57, 2021. Achour Mostéfaoui, Sergio Rajsbaum, and Michel Raynal. Conditions on input vectors for consensus solvability in asynchronous distributed systems. J. ACM, 50(6):922–954, 2003. Armando Casta neda, Sergio Rajsbaum, and Michel Raynal. The renaming problem in shared memory systems: An introduction. Computer Science Review, 5(3):229–251, 2011. N.F. Neves, M. Correia, and P. Verissimo. Solving vector consensus with a wormhole. IEEE Transactions on Parallel and Distributed Systems, 16(12):1120–1131, 2005. Baigent Nicholas. Chapter eighteen  topological theories of social choice. In Kenneth J. Arrow, Amartya Sen, and Kotaro Suzumura, editors, Handbook of Social Choice and Welfare, volume 2 of Handbook of Social Choice and Welfare, pages 301–334. Elsevier, 2011. Sergio Rajsbaum and Armajac RaventósPujol. A distributed combinatorial topology approach to arrow’s impossibility theorem. In Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing, PODC’22, page 471–481, New York, NY, USA, 2022. Association for Computing Machinery. Saba Ramazani, Jinko Kanno, Rastko R. Selmic, and Matthias R. Brust. Topological and combinatorial coverage hole detection in coordinatefree wireless sensor networks. Int. J. Sen. Netw., 21(1):40–52, jan 2016. Michel Raynal. FaultTolerant MessagePassing Distributed Systems  An Algorithmic Approach. Springer, 2018. John Stillwell. Classical topology and combinatorial group theory. Graduate Texts in Mathematics. SpringerVerlag New York, 1980. Yasuhito Tanaka. On the equivalence of the arrow impossibility theorem and the brouwer fixed point theorem when individual preferences are weak orders. Journal of Mathematical Economics, 45(3):241–249, 2009. Pingzhong Tang and Fangzhen Lin. Computeraided proofs of arrow’s and other impossibility theorems. Artificial Intelligence, 173(11):1041–1053, 2009. J. C. Weldon. On the problem of social welfare functions. The Canadian Journal of Economics and Political Science / Revue canadienne d’Economique et de Science politique, 18(4):452–463, 1952. John A Weymark. Arrow’s theorem with social quasiorderings. Public Choice, 42(3):235–246, 1984. Wikipedia contributors. Arrow’s impossibility theorem — Wikipedia, the free encyclopedia. https://en.wikipedia.org/w/index.php?title=Arrow%27s_impossibility_theorem&oldid=1060161477, 2021. [Online; accessed 26January2022]. Ning Neil Yu. A oneshot proof of Arrow’s impossibility theorem. Economic Theory, 50(2):523–525, 2012. Ning Neil Yu. A quest for fundamental theorems of social choice. Social Choice and Welfare, 44(3):533–548, 2015. 
URI:  https://mpra.ub.unimuenchen.de/id/eprint/113861 
Available Versions of this Item

A Combinatorial Topology Approach to Arrow's Impossibility Theorem. (deposited 17 Feb 2022 07:56)

A Combinatorial Topology Approach to Arrow's Impossibility Theorem. (deposited 23 Jul 2022 12:47)
 A Combinatorial Topology Approach to Arrow's Impossibility Theorem. (deposited 12 Feb 2024 14:40)
 A Combinatorial Topology Approach to Arrow's Impossibility Theorem. (deposited 27 Jul 2022 23:06) [Currently Displayed]

A Combinatorial Topology Approach to Arrow's Impossibility Theorem. (deposited 23 Jul 2022 12:47)