A Combinatorial Topology Approach to Arrow's Impossibility Theorem

Rajsbaum, Sergio and Raventós-Pujol, Armajac (2022): A Combinatorial Topology Approach to Arrow's Impossibility Theorem.

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.

• Item Type: MPRA Paper
• 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 Decision-Making > D71 - Social Choice ; Clubs ; Committees ; Associations

References

Applications of combinatorial topology to computer science. In Lisbeth Fajstrup, Dmitry Feichtner-Kozlov, Robert Ghrist, and Maurice Herlihy, editors, Dagstuhl Report 12121, Issue 3, volume 2 of Seminar, Germany, March 2012. Dagstuhl, Leibniz-Zentrum 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 wait-free 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 decision-making. 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.

Armando Castañeda, Sergio Rajsbaum, and Michel Raynal. The renaming problem in shared memory systems: An introduction. Computer Science Review, 5(3):229–251, 2011.

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 twenty-seven - 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.

Ky Fan. Simplicial maps from an orientable n-pseudomanifold 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 single-profile versions. Working Paper 2008-8, 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.

Roy Friedman, Achour Mostefaoui, Sergio Rajsbaum, and Michel Raynal. Asynchronous agreement and its relation with error-correcting 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. Wait-Free 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–Leibniz-Zentrum 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.

Jan-Philipp Litza. Weak symmetry breaking and simplex path demonochromatizing. Master’s thesis, Bremen University, Germany, March 2015. Supervisor Dmitry Feichtner-Kozlov 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.

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.

Saba Ramazani, Jinko Kanno, Rastko R. Selmic, and Matthias R. Brust. Topological and combinatorial coverage hole detection in coordinate-free wireless sensor networks. Int. J. Sen. Netw., 21(1):40–52, jan 2016.

Michel Raynal. Fault-Tolerant Message-Passing Distributed Systems - An Algorithmic Approach. Springer, 2018.

John Stillwell. Classical topology and combinatorial group theory. Graduate Texts in Mathematics. Springer-Verlag 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. Computer-aided 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.

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 26-January-2022].

Ning Neil Yu. A one-shot 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.