×

zbMATH — the first resource for mathematics

Optimal bounds for the no-show paradox via SAT solving. (English) Zbl 1415.91110
Summary: One of the most important desirable properties in social choice theory is Condorcet-consistency, which requires that a voting rule should return an alternative that is preferred to any other alternative by some majority of voters. Another desirable property is participation, which requires that no voter should be worse off by joining an electorate. A seminal result by H. Moulin [J. Econ. Theory 45, No. 1, 53–64 (1988; Zbl 0649.90010)] has shown that Condorcet-consistency and participation are incompatible whenever there are at least 4 alternatives and 25 voters. We leverage SAT solving to obtain an elegant human-readable proof of Moulin’s result that requires only 12 voters. Moreover, the SAT solver is able to construct a Condorcet-consistent voting rule that satisfies participation as well as a number of other desirable properties for up to 11 voters, proving the optimality of the above bound. We also obtain tight results for set-valued and probabilistic voting rules, which complement and significantly improve existing theorems.

MSC:
91B12 Voting theory
91B14 Social choice
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Belov, A.; Marques-Silva, J., Muser2: an efficient MUS extractor, J. Satisf. Boolean Model. Comput., 8, 123-128, (2012) · Zbl 1322.68178
[2] Biere, A., Lingeling, plingeling and treengeling entering the SAT competition 2013, (Proceedings of the SAT Competition 2013, (2013)), 51-52
[3] Brandl, F.; Brandt, F.; Geist, C.; Hofbauer, J., Strategic abstention based on preference extensions: positive results and computer-generated impossibilities, (Proceedings of the 24th International Joint Conference on Artificial intelligence, IJCAI, (2015), AAAI Press), 18-24
[4] Brandl, F.; Brandt, F.; Hofbauer, J., Incentives for participation and abstention in probabilistic social choice, (Proceedings of the 14th International Conference on Autonomous Agents and Multi-Agent Systems, AAMAS, (2015), IFAAMAS), 1411-1419
[5] Brandl, F., Brandt, F., Hofbauer, J., Welfare maximization entices participation, 2016. Working paper. · Zbl 1419.91293
[6] Brandt, F., Set-monotonicity implies kelly-strategyproofness, Soc. Choice Welf., 45, 4, 793-804, (2015) · Zbl 1341.91061
[7] Brandt, F.; Geist, C., Finding strategyproof social choice functions via SAT solving, J. Artificial Intelligence Res., 55, 565-602, (2016) · Zbl 1352.91022
[8] (Brandt, F.; Conitzer, V.; Endriss, U.; Lang, J.; Procaccia, A., Handbook of Computational Social Choice, (2016), Cambridge University Press) · Zbl 1436.91001
[9] Brandt, F., Geist, C., Peters, D., 2016b. Replication data for: Optimal bounds for the no-show paradox via SAT solving. Harvard Dataverse. http://dx.doi.org/10.7910/DVN/TGIQB7. · Zbl 1415.91110
[10] Campbell, D. E.; Kelly, J. S., Strategy-proofness and weighted voting, Math. Social Sci., 60, 1, 15-23, (2010) · Zbl 1232.91171
[11] Campbell, D. E.; Graver, J.; Kelly, J. S., There are more strategy-proof procedures than you think, Math. Social Sci., 64, 3, 263-265, (2012) · Zbl 1260.91074
[12] Chatterjee, S.; Sen, A., Automated reasoning in social choice theory — some remarks, Math. Comput. Sci., 8, 1, 5-10, (2014) · Zbl 1302.91077
[13] Conitzer, V., Sandholm, T., 2002. Complexity of mechanism design. In: Proceedings of the 18th Annual Conference on Uncertainty in Artificial Intelligence, UAI, pp. 103-110.
[14] de Condorcet, M., Essai sur l’application de l’analyse à la probabilité des décisions rendues à la pluralité des voix. Imprimerie Royale, 1785. Facsimile published in 1972 by Chelsea Publishing Company, New York.
[15] Duddy, C., Condorcet’s principle and the strong no-show paradoxes, Theory Decision, 77, 2, 275-285, (2014) · Zbl 1304.91076
[16] Duggan, J.; Schwartz, T., Strategic manipulability without resoluteness or shared beliefs: Gibbard-Satterthwaite generalized, Soc. Choice Welf., 17, 1, 85-93, (2000) · Zbl 1069.91548
[17] Fishburn, P. C., Condorcet social choice functions, SIAM J. Appl. Math., 33, 3, 469-489, (1977) · Zbl 0369.90002
[18] Fishburn, P. C.; Brams, S. J., Paradoxes of preferential voting, Math. Mag., 56, 4, 207-214, (1983) · Zbl 0521.90006
[19] Fréchette, A.; Newman, N.; Leyton-Brown, K., Solving the station repacking problem, (Proceedings of the 30th AAAI Conference on Artificial intelligence (AAAI), (2016), AAAI Press)
[20] Geist, C.; Endriss, U., Automated search for impossibility theorems in social choice theory: ranking sets of objects, J. Artificial Intelligence Res., 40, 143-174, (2011) · Zbl 1214.68382
[21] Heule, M. J.H.; Kullmann, O.; Marek, V. W., Solving and verifying the Boolean Pythagorean triples problem via cube-and-conquer, (Proceedings of the 19th International Conference on Theory and Applications of Satisfiability Testing, Lecture Notes in Computer Science (LNCS), vol. 9710, (2016), Springer-Verlag), 228-245 · Zbl 1403.68226
[22] Holzman, R., To vote or not to vote: what is the quota?, Discrete Appl. Math., 22, 2, 133-141, (1988) · Zbl 0662.90006
[23] Jimeno, J. L.; Pérez, J.; García, E., An extension of the moulin no show paradox for voting correspondences, Soc. Choice Welf., 33, 3, 343-459, (2009) · Zbl 1190.91047
[24] Kardel, K., Participation and group-participation in social choice theory, (2014), Technische Universität München, (Master’s thesis)
[25] Konev, B.; Lisitsa, A., A SAT attack on the Erdős discrepancy conjecture, (Theory and Applications of Satisfiability Testing-SAT 2014, (2014), Springer), 219-226 · Zbl 1343.68217
[26] Laslier, J.-F., Tournament solutions and majority voting, (1997), Springer-Verlag · Zbl 0948.91504
[27] Lepelley, D.; Merlin, V., Scoring run-off paradoxes for variable electorates, Econom. Theory, 17, 1, 53-80, (2000) · Zbl 0984.91030
[28] Liffiton, M. H.; Previti, A.; Malik, A.; Marques-Silva, J., Fast, flexible MUS enumeration, Constraints, 1-28, (2015)
[29] Moulin, H., Condorcet’s principle implies the no show paradox, J. Econom. Theory, 45, 53-64, (1988) · Zbl 0649.90010
[30] Pérez, J., The strong no show paradoxes are a common flaw in Condorcet voting correspondences, Soc. Choice Welf., 18, 3, 601-616, (2001) · Zbl 1069.91534
[31] Ray, D., On the practical possibility of a ’no show paradox’ under the single transferable vote, Math. Social Sci., 11, 2, 183-189, (1986) · Zbl 0584.90007
[32] Sanver, M. R.; Zwicker, W. S., One-way monotonicity as a form of strategy-proofness, Internat. J. Game Theory, 38, 4, 553-574, (2009) · Zbl 1211.91111
[33] Schulze, M., 2003. Condorcet and participation. Election-methods mailing list. http://lists.electorama.com/pipermail/election-methods-electorama.com/2003-October/011042.html (accessed 7 November 2015).
[34] Smith, W.D., 2007. Participation failure is forced in Condorcet methods with at least 4 candidates. The Center for Range Voting. http://rangevoting.org/CondPF.html (accessed 7 November 2015).
[35] Tang, P.; Lin, F., Computer-aided proofs of arrow’s and other impossibility theorems, Artificial Intelligence, 173, 11, 1041-1053, (2009) · Zbl 1187.91061
[36] Woodall, D. R., Monotonicity of single-seat preferential election rules, Discrete Appl. Math., 77, 1, 81-98, (1997) · Zbl 0879.90060
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.