Arrow’s theorem through a fixpoint argument. (English) Zbl 07450028
Moss, Lawrence S. (ed.), Proceedings of the seventeenth conference on theoretical aspects of rationality and knowledge, TARK 2019, Toulouse, France, July 17–19, 2019. Waterloo: Open Publishing Association (OPA). Electron. Proc. Theor. Comput. Sci. (EPTCS) 297, 175-188 (2019).
Summary: We present a proof of Arrow’s theorem from social choice theory that uses a fixpoint argument. Specifically, we use Banach’s result on the existence of a fixpoint of a contractive map defined on a complete metric space. Conceptually, our approach shows that dictatorships can be seen as “stable points” (fixpoints) of a certain process.
For the entire collection see [Zbl 1446.68018].
For the entire collection see [Zbl 1446.68018].
MSC:
| 68T27 | Logic in artificial intelligence |
Keywords:
social choice theory; voting; Arrow’s impossibility theorem; Banach’s fixpoint theorem; dictatorship; force; fixpoint; metricReferences:
| [1] | Aleksandr V. Arhangel’skij & Lev S. Pontryagin (1990): General Topology: Basic Concepts and Constructions. Dimension Theory. I. Springer-Verlag. · Zbl 0778.00007 |
| [2] | Kenneth J. Arrow (1951): Social Choice and Individual Values. New York. · Zbl 0984.91513 |
| [3] | Stefan Banach (1922): Sur les opérations dans les ensembles abstraits et leur application auxéquations intégrales. Fundamenta Mathematicae 3(1), pp. 133-181, doi:10.4064/fm-3-1-133-181. · JFM 48.0201.01 · doi:10.4064/fm-3-1-133-181 |
| [4] | John F. Banzhaf III (1964): Weighted Voting Doesn’t Work: A Mathematical Analysis. Rutgers L. Rev. 19, p. 317. |
| [5] | Salvador Barbera (1980): Pivotal Voters: A New Proof of Arrow’s Theorem. Economics Letters 6(1), pp. 13-16, doi:10.1016/0165-1765(80)90050-6. · doi:10.1016/0165-1765(80)90050-6 |
| [6] | Julian H. Blau (1972): A Direct Proof of Arrow’s Theorem. Econometrica: Journal of the Econometric Society, pp. 61-67, doi:10.2307/1909721. · Zbl 0239.90001 · doi:10.2307/1909721 |
| [7] | Francesca Cagliari, Barbara Di Fabio & Claudia Landi (2015): The Natural Pseudo-distance as a Quotient Pseudo-metric, and Applications. In: Forum Mathematicum, 27, De Gruyter, pp. 1729-1742. · Zbl 1320.54014 |
| [8] | Frank M. V. Feys (2015): Fourier Analysis for Social Choice. Master’s thesis, Universiteit van Amsterdam, the Netherlands. |
| [9] | Ehud Friedgut, Gil Kalai & Assaf Naor (2002): Boolean Functions Whose Fourier Transform is Concen-trated on the First Two Levels. Advances in Applied Mathematics 29(3), pp. 427-437, doi:10.1016/S0196-8858(02)00024-6. · Zbl 1039.91014 · doi:10.1016/S0196-8858(02)00024-6 |
| [10] | Mark B. Garman & Morton I. Kamien (1968): The Paradox of Voting: Probability Calculations. Behavioral Science 13(4), pp. 306-316, doi:10.1002/bs.3830130405. · doi:10.1002/bs.3830130405 |
| [11] | John Geanakoplos (2005): Three Brief Proofs of Arrow’s Impossibility Theorem. Economic Theory 26(1), pp. 211-215, doi:10.1007/s00199-004-0556-7. · Zbl 1097.91031 · doi:10.1007/s00199-004-0556-7 |
| [12] | Allan Gibbard (1973): Manipulation of Voting Schemes: A General Result. Econometrica 41(4), pp. 587-601, doi:10.2307/1914083. · Zbl 0325.90081 · doi:10.2307/1914083 |
| [13] | Gil Kalai (2002): A Fourier-theoretic Perspective on the Condorcet Paradox and Arrow’s Theorem. Advances in Applied Mathematics 29(3), pp. 412-426, doi:10.1016/S0196-8858(02)00023-4. · Zbl 1038.91027 · doi:10.1016/S0196-8858(02)00023-4 |
| [14] | Alan P. Kirman & Dieter Sondermann (1972): Arrow’s Theorem, Many Agents, and Invisible Dictators. Journal of Economic Theory 5(2), pp. 267-277, doi:10.1016/0022-0531(72)90106-8. · doi:10.1016/0022-0531(72)90106-8 |
| [15] | Elchanan Mossel (2012): A Quantitative Arrow Theorem. Probability Theory and Related Fields 154(1-2), pp. 49-88, doi:10.1007/s00440-011-0362-7. · Zbl 1269.60010 · doi:10.1007/s00440-011-0362-7 |
| [16] | John F. Nash (1950): Equilibrium Points in n-Person Games. Proceedings of the National Academy of Sciences 36(1), pp. 48-49, doi:10.1073/pnas.36.1.48. · Zbl 0036.01104 · doi:10.1073/pnas.36.1.48 |
| [17] | Ryan O’Donnell (2014): Analysis of Boolean Functions. Cambridge University Press, doi:10.1017/CBO9781139814782. · Zbl 1336.94096 · doi:10.1017/CBO9781139814782 |
| [18] | Vittorino Pata (2014): Fixed Point Theorems and Applications. Politecnico di Milano. · Zbl 1448.47001 |
| [19] | Philip J. Reny (2001): Arrow’s Theorem and the Gibbard-Satterthwaite Theorem: A Unified Approach. Economics Letters 70(1), pp. 99-105, doi:10.1016/S0165-1765(00)00332-3. · Zbl 0963.91019 · doi:10.1016/S0165-1765(00)00332-3 |
| [20] | Joseph J. Rotman (2012): An Introduction to the Theory of Groups. 148, Springer Science & Business Media. · Zbl 0810.20001 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
