Probabilistic view of voting, paradoxes, and manipulation

Mossel, Elchanan

doi:10.1090/bull/1751

Probabilistic view of voting, paradoxes, and manipulation
HTML articles powered by AMS MathViewer

by Elchanan Mossel HTML | PDF

Bull. Amer. Math. Soc. 59 (2022), 297-330

Abstract:

The Marquis de Condorcet, a French philosopher, mathematician, and political scientist, studied mathematical aspects of voting in the eighteenth century. Condorcet was interested in studying voting rules as procedures for aggregating noisy signals and in the paradoxical nature of ranking three or more alternatives. We survey some of the main mathematical models, tools, and results in a theory that studies probabilistic aspects of social choice. Our journey will take us through major results in mathematical economics from the second half of the twentieth century, through the theory of Boolean functions and their influences and through recent results in Gaussian geometry and functional inequalities.

References

K. Arrow, A difficulty in the theory of social welfare, J. of Political Economy 58 (1950), 328–346., DOI 10.1086/256963
Kenneth J. Arrow, Social Choice and Individual Values, Cowles Commission Monograph No. 12, John Wiley & Sons, Inc., New York, N. Y.; Chapman & Hall, Ltd., London, 1951. MR 0039976
Salvador Barberá, Pivotal voters: a new proof of Arrow’s theorem, Econom. Lett. 6 (1980), no. 1, 13–16. MR 614478, DOI 10.1016/0165-1765(80)90050-6
William Beckner, Inequalities in Fourier analysis, Ann. of Math. (2) 102 (1975), no. 1, 159–182. MR 385456, DOI 10.2307/1970980
Colin E. Bell, A random voting graph almost surely has a Hamiltonian cycle when the number of alternatives is large, Econometrica 49 (1981), no. 6, 1597–1603. MR 636170, DOI 10.2307/1911423
M. Ben-Or and N. Linial, Collective coin flipping, Randomness and computation, 1990.
Itai Benjamini, Gil Kalai, and Oded Schramm, Noise sensitivity of Boolean functions and applications to percolation, Inst. Hautes Études Sci. Publ. Math. 90 (1999), 5–43 (2001). MR 1813223, DOI 10.1007/BF02698830
S. G. Bobkov, An isoperimetric inequality on the discrete cube, and an elementary proof of the isoperimetric inequality in Gauss space, Ann. Probab. 25 (1997), no. 1, 206–214. MR 1428506, DOI 10.1214/aop/1024404285
Aline Bonami, Ensembles $\Lambda (p)$ dans le dual de $D^{\infty }$, Ann. Inst. Fourier (Grenoble) 18 (1968), no. fasc. 2, 193–204 (1969) (French). MR 249940, DOI 10.5802/aif.297
Aline Bonami, Étude des coefficients de Fourier des fonctions de $L^{p}(G)$, Ann. Inst. Fourier (Grenoble) 20 (1970), no. fasc. 2, 335–402 (1971) (French, with English summary). MR 283496, DOI 10.5802/aif.357
Christer Borell, Positivity improving operators and hypercontractivity, Math. Z. 180 (1982), no. 2, 225–234. MR 661699, DOI 10.1007/BF01318906
Christer Borell, Geometric bounds on the Ornstein-Uhlenbeck velocity process, Z. Wahrsch. Verw. Gebiete 70 (1985), no. 1, 1–13. MR 795785, DOI 10.1007/BF00532234
Jean Bourgain, Jeff Kahn, Gil Kalai, Yitzhak Katznelson, and Nathan Linial, The influence of variables in product spaces, Israel J. Math. 77 (1992), no. 1-2, 55–64. MR 1194785, DOI 10.1007/BF02808010
Colin D Campbell and Gordon Tullock, The paradox of voting—a possible method of calculation, American Political Science Review 60 (1966), no. 3, 684–685., DOI 10.1017/S0003055400130539
Benny Chor, Oded Goldreich, Johan Håsted, Joel Freidmann, Steven Rudich, and Roman Smolensky, The bit extraction problem or t-resilient functions, 26th Annual Symposium on Foundations of Computer Science, 1985, pp. 396–407.
Jean-Antoine-Nicolas Condorcet, Essai sur l’application de l’analyse à la probabilité des décisions rendues à la pluralité des voix, De l’Imprimerie Royale, 1785.
J. Corneli, I. Corwin, S. Hurder, V. Sesum, Y. Xu, E. Adams, D. Davis, M. Lee, R. Visocchi, and N. Hoffman, Double bubbles in Gauss space and spheres, Houston J. Math. 34 (2008), no. 1, 181–204. MR 2383703
Anindya De, Elchanan Mossel, and Joe Neeman, Majority is stablest: discrete and SoS, STOC’13—Proceedings of the 2013 ACM Symposium on Theory of Computing, ACM, New York, 2013, pp. 477–486. MR 3210809, DOI 10.1145/2488608.2488668
Anindya De, Elchanan Mossel, and Joe Neeman, Majority is stablest: Discrete and sos, Theory of Computing 12 (2016), no. 4, 1–50.
Pradeep Dubey and Lloyd S. Shapley, Mathematical properties of the Banzhaf power index, Math. Oper. Res. 4 (1979), no. 2, 99–131. MR 543924, DOI 10.1287/moor.4.2.99
Ronen Eldan, A two-sided estimate for the Gaussian noise stability deficit, Invent. Math. 201 (2015), no. 2, 561–624. MR 3370621, DOI 10.1007/s00222-014-0556-6
Dvir Falik and Ehud Friedgut, Between Arrow and Gibbard-Satterthwaite; a representation theoretic approach, Israel J. Math. 201 (2014), no. 1, 247–297. MR 3265286, DOI 10.1007/s11856-014-1064-5
Yuval Filmus, Noam Lifshitz, Dor Minzer, and Elchanan Mossel, AND testing and robust judgement aggregation, Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020, pp. 222–233.
Ehud Friedgut, Gil Kalai, Nathan Keller, and Noam Nisan, A quantitative version of the Gibbard-Satterthwaite theorem for three alternatives, SIAM J. Comput. 40 (2011), no. 3, 934–952. MR 2823513, DOI 10.1137/090756740
Ehud Friedgut, Gil Kalai, and Assaf Naor, Boolean functions whose Fourier transform is concentrated on the first two levels, Adv. in Appl. Math. 29 (2002), no. 3, 427–437. MR 1942632, DOI 10.1016/S0196-8858(02)00024-6
E. Friedgut, G. Kalai, and N. Nisan, Elections can be manipulated often, Proceedings of the 49th annual ieee symposium on foundations of computer science (focs), 2009, pp. 243–249.
William V Gehrlein, Condorcet’s paradox, Theory and Decision Library C, vol. 40, Springer-Verlag Berlin Heidelberg, 2006., DOI 10.1007/3-540-33799-7
Allan Gibbard, Manipulation of voting schemes: a general result, Econometrica 41 (1973), 587–601. MR 441407, DOI 10.2307/1914083
Leonard Gross, Logarithmic Sobolev inequalities, Amer. J. Math. 97 (1975), no. 4, 1061–1083. MR 420249, DOI 10.2307/2373688
Steven Heilman, Elchanan Mossel, and Joe Neeman, Standard simplices and pluralities are not the most noise stable (abstract), Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, 2015, pp. 255–255.
Steven Heilman and Alex Tarter, Three candidate plurality is stablest for small correlations, arXiv:2011.05583 (2020).
Marcus Isaksson, Guy Kindler, and Elchanan Mossel, The geometry of manipulation—a quantitative proof of the Gibbard-Satterthwaite theorem, Combinatorica 32 (2012), no. 2, 221–250. MR 2927640, DOI 10.1007/s00493-012-2704-1
Marcus Isaksson and Elchanan Mossel, Maximally stable Gaussian partitions with discrete applications, Israel J. Math. 189 (2012), 347–396. MR 2931402, DOI 10.1007/s11856-011-0181-7
Jacek Jendrej, Krzysztof Oleszkiewicz, and Jakub O. Wojtaszczyk, On some extensions of the FKN theorem, Theory Comput. 11 (2015), 445–469. MR 3446023, DOI 10.4086/toc.2015.v011a018
Chris Jones, A noisy-influence regularity lemma for Boolean functions, arXiv:1610.06950 (2016).
J. Kahn, G. Kalai, and N. Linial, The influence of variables on Boolean functions, Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988, pp. 68–80.
Gil Kalai, A Fourier-theoretic perspective on the Condorcet paradox and Arrow’s theorem, Adv. in Appl. Math. 29 (2002), no. 3, 412–426. MR 1942631, DOI 10.1016/S0196-8858(02)00023-4
Gil Kalai, Social indeterminacy, Econometrica 72 (2004), no. 5, 1565–1581. MR 2078213, DOI 10.1111/j.1468-0262.2004.00543.x
Nathan Keller, A tight quantitative version of Arrow’s impossibility theorem, J. Eur. Math. Soc. (JEMS) 14 (2012), no. 5, 1331–1355. MR 2966653, DOI 10.4171/JEMS/334
N. Keller, E. Mossel, and A. Sen, Geometric influences, Annals of Probability 40 (2012), no. 3, 1135–1166., DOI 10.1214/11-AOP643
Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell, Optimal inapproximability results for MAX-CUT and other 2-variable CSPs?, SIAM J. Comput. 37 (2007), no. 1, 319–357. MR 2306295, DOI 10.1137/S0097539705447372
Guy Kindler, Naomi Kirshner, and Ryan O’Donnell, Gaussian noise sensitivity and Fourier tails, Israel J. Math. 225 (2018), no. 1, 71–109. MR 3805643, DOI 10.1007/s11856-018-1646-8
Lewis A Kornhauser and Lawrence G Sager, Unpacking the court, Yale Law Jour. 96 (1986), 82., DOI 10.2307/796436
Michel Ledoux, Remarks on Gaussian noise stability, Brascamp-Lieb and Slepian inequalities, Geometric aspects of functional analysis, Lecture Notes in Math., vol. 2116, Springer, Cham, 2014, pp. 309–333. MR 3364694, DOI 10.1007/978-3-319-09477-9_{2}0
Christian List and Philip Pettit, Aggregating sets of judgments: An impossibility result, Economics and Philosophy 18 (2002), no. 1, 89–110., DOI 10.1017/S0266267102001098
Christian List and Philip Pettit, Aggregating sets of judgments: two impossibility results compared, Synthese 140 (2004), no. 1-2, 207–235. With a comment by Isaac Levi. MR 2077375, DOI 10.1023/B:SYNT.0000029950.50517.59
Emanuel Milman and Joe Neeman, The Gaussian double-bubble conjecture, arXiv:1801.09296 (2018).
Emanuel Milman and Joe Neeman, The Gaussian multi-bubble conjecture, arXiv:1805.10961 (2018).
E. Mossel, Gaussian bounds for noise correlation of functions and tight analysis of long codes, Foundations of Computer Science, 2008 (FOCS 08), 2008, pp. 156–165.
E. Mossel, Arrow’s impossibility theorem without unanimity, arXiv:0901.4727 (2009).
Elchanan Mossel, Gaussian bounds for noise correlation of functions, Geom. Funct. Anal. 19 (2010), no. 6, 1713–1756. MR 2594620, DOI 10.1007/s00039-010-0047-x
Elchanan Mossel, A quantitative Arrow theorem, Probab. Theory Related Fields 154 (2012), no. 1-2, 49–88. MR 2981417, DOI 10.1007/s00440-011-0362-7
Elchanan Mossel, Gaussian bounds for noise correlation of resilient functions, Israel J. Math. 235 (2020), no. 1, 111–137. MR 4068779, DOI 10.1007/s11856-019-1951-x
Elchanan Mossel, Probabilistic aspects of voting, intransitivity and manipulation, arXiv:2012.10352 (2020).
Elchanan Mossel and Joe Neeman, Robust optimality of Gaussian noise stability, J. Eur. Math. Soc. (JEMS) 17 (2015), no. 2, 433–482. MR 3317748, DOI 10.4171/JEMS/507
Elchanan Mossel and Ryan O’Donnell, On the noise sensitivity of monotone functions, Random Structures Algorithms 23 (2003), no. 3, 333–350. MR 1999039, DOI 10.1002/rsa.10097
E. Mossel, R. O’Donnell, and K. Oleszkiewicz, Noise stability of functions with low influences: invariance and optimality (extended abstract), 46th annual ieee symposium on foundations of computer science (focs 2005), 23-25 october 2005, pittsburgh, pa, usa, proceedings, 2005, pp. 21–30.
E. Mossel, R. O’Donnell, and K. Oleszkiewicz, Noise stability of functions with low influences: invariance and optimality, Annals of Mathematics 171 (2010), no. 1, 295–341., DOI 10.4007/annals.2010.171.295
E. Mossel, R. O’Donnell, O. Regev, J. E. Steif, and B. Sudakov, Non-interactive correlation distillation, inhomogeneous Markov chains, and the reverse Bonami-Beckner inequality, Israel J. Math. 154 (2006), 299–336. MR 2254545, DOI 10.1007/BF02773611
Elchanan Mossel, Krzysztof Oleszkiewicz, and Arnab Sen, On reverse hypercontractivity, Geom. Funct. Anal. 23 (2013), no. 3, 1062–1097. MR 3061780, DOI 10.1007/s00039-013-0229-4
Elchanan Mossel and Miklós Z. Rácz, A quantitative Gibbard-Satterthwaite theorem without neutrality [extended abstract], STOC’12—Proceedings of the 2012 ACM Symposium on Theory of Computing, ACM, New York, 2012, pp. 1041–1060. MR 2961564, DOI 10.1145/2213977.2214071
Elchanan Mossel and Miklós Z. Rácz, A quantitative Gibbard-Satterthwaite theorem without neutrality, Combinatorica 35 (2015), no. 3, 317–387. MR 3367129, DOI 10.1007/s00493-014-2979-5
Joe Neeman, A multidimensional version of noise stability, Electron. Commun. Probab. 19 (2014), no. 72, 10. MR 3274518, DOI 10.1214/ECP.v19-3005
Ilan Nehama, Approximately classic judgement aggregation, Ann. Math. Artif. Intell. 68 (2013), no. 1-3, 91–134. MR 3145873, DOI 10.1007/s10472-013-9358-6
Edward Nelson, A quartic interaction in two dimensions, Mathematical Theory of Elementary Particles (Proc. Conf., Dedham, Mass., 1965) M.I.T. Press, Cambridge, Mass., 1966, pp. 69–73. MR 0210416
Edward Nelson, The free Markoff field, J. Functional Analysis 12 (1973), 211–227. MR 0343816, DOI 10.1016/0022-1236(73)90025-6
R. G. Niemi and H. F. Weisberg, A mathematical solution for the probability of paradox of voting, Behavioral Science 13 (1968), 317–323., DOI 10.1002/bs.3830130406
Ryan O’Donnell, Analysis of Boolean functions, Cambridge University Press, New York, 2014. MR 3443800, DOI 10.1017/CBO9781139814782
Ryan O’Donnell, Rocco Servedio, Li-Yang Tan, and Andrew Wan, A regularity lemma for low noisy-influences, 2010. Unpublished manuscript.
Mark Allen Satterthwaite, Strategy-proofness and Arrow’s conditions: Existence and correspondence theorems for voting procedures and social welfare functions, J. Econom. Theory 10 (1975), no. 2, 187–217. MR 414051, DOI 10.1016/0022-0531(75)90050-2
W. Sheppard, On the application of the theory of error to cases of normal distribution and normal correlation, Phil. Trans. Royal Soc. London 192 (1899), 101–168.
Wikipedia contributors, Marquis de Condorcet—Wikipedia, the free encyclopedia, 2019. [Online; accessed 2019].
Robert Wilson, Social choice theory without the Pareto principle, J. Econom. Theory 5 (1972), no. 3, 478–486. MR 449494, DOI 10.1016/0022-0531(72)90051-8
Lei Yu and Vincent YF Tan, On non-interactive simulation of binary random variables, IEEE Transactions on Information Theory 67 (2021), no. 4, 2528–2538., DOI 10.1109/TIT.2021.3054659