Proceedings

Proving the Incompatibility of Efficiency and Strategyproofness via SMT Solving

Download BibTeX Cite

Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. Pages 116-121.

© 2016 International Joint Conferences on Artificial Intelligence

Abstract

Two important requirements when aggregating the preferences of multiple agents are that the outcome should be economically efficient and the aggregation mechanism should not be manipulable. In this paper, we provide a computer-aided proof of a sweeping impossibility using these two conditions for randomized aggregation mechanisms. More precisely, we show that every efficient aggregation mechanism can be manipulated for all expected utility representations of the agents' preferences. This settles a conjecture by Aziz et al. [2013b] and strengthens a number of existing theorems, including statements that were shown within the special domain of assignment. Our proof is obtained by formulating the claim as a satisfiability problem over predicates from real-valued arithmetic, which is then checked using an SMT (satisfiability modulo theories) solver. To the best of our knowledge, this is the first application of SMT solvers in computational social choice.

  1. [Aziz et al., 2013a] H. Aziz, F. Brandt, and M. Brill. The computational complexity of random serial dictatorship. Economics Letters, 121(3):341-345, 2013.
  2. [Aziz et al., 2013b] H. Aziz, F. Brandt, and M. Brill. On the tradeoff between economic efficiency and strategyproof- ness in randomized social choice. In Proc. of 12th AAMAS Conference, pages 455-462.
  3. IFAAMAS, 2013.
  4. [Aziz et al., 2014] H. Aziz, F. Brandl, and F. Brandt. On the incompatibility of efficiency and strategyproofness in ran- domized social choice. In Proc. of 28th AAAI Conference, pages 545-551. AAAI Press, 2014.
  5. [Aziz et al., 2015] H. Aziz, F. Brandl, and F. Brandt. Uni- versal Pareto dominance and welfare for plausible utility functions. Journal of Mathematical Economics, 60:123- 133, 2015.
  6. [Barrett et al., 2010] C. Barrett, A. Stump, and C. Tinelli. The SMT-LIB Standard: Version 2.0. In Proc. of 8th In- ternational Workshop on Satisfiability Modulo Theories, 2010.
  7. [Barrett et al., 2013] C. Barrett, M. Deters, L. de Moura, A. Oliveras, and A. Stump. 6 years of SMT-COMP. Jour- nal of Automated Reasoning, 50(3):243-277, 2013.
  8. [Bogomolnaia and Moulin, 2001] A. Bogomolnaia and H. Moulin. A new solution to the random assignment problem. Journal of Economic Theory, 100(2):295-328, 2001.
  9. [Brandl et al., 2015] F. Brandl, F. Brandt, C. Geist, and J. Hofbauer. Strategic abstention based on preference ex- tensions: Positive results and computer-generated impos- sibilities. In Proc. of 24th IJCAI, pages 18-24. AAAI Press, 2015. IJCAI
  10. [Brandl et al., 2016a] F. Brandl, F. Brandt, and C. Geist. Proving the incompatibility of efficiency and strat- egyproofness via SMT solving. Technical report, http://arxiv.org/abs/1604.05692, 2016. Link
  11. [Brandl et al., 2016b] F. Brandl, F. Brandt, and W. Suksom- pong. The impossibility of extending random dictatorship to weak preferences. Economics Letters, 141:44-47, 2016.
  12. [Brandt and Geist, 2016] F. Brandt and C. Geist. Finding strategyproof social choice functions via SAT solving. Journal of Artificial Intelligence Research, 55:565-602, 2016.
  13. [Brandt et al., 2016] F. Brandt, C. Geist, and D. Peters. Op- timal bounds for the no-show paradox via SAT solving. In Proc. of 15th AAMAS Conference, pages 314-322.
  14. [Cimatti et al., 2013] A. Cimatti, A. Griggio, B. Schaafsma, and R. Sebastiani. The MathSAT5 SMT Solver. In Pro- ceedings of TACAS, volume 7795 of LNCS, pages 93-107.
  15. [de Moura and Bjørner, 2008] L. de Moura and N. Bjørner. Z3: An efficient SMT solver. In Proceedings of TACAS, volume 7795 of LNCS, pages 337-340. Springer, 2008.
  16. [Dutta et al., 2007] B. Dutta, H. Peters, and A. Sen. Strategy-proof cardinal decision schemes. Social Choice and Welfare, 28(1):163-179, 2007.
  17. [Gale, 1987] D. Gale. College course assignments and opti- mal lotteries, 1987. Mimeo.
  18. [Geist and Endriss, 2011] C. Geist and U. Endriss. Auto- mated search for impossibility theorems in social choice theory: Ranking sets of objects. Journal of Artificial Intel- ligence Research, 40:143-174, 2011.
  19. [Gibbard, 1973] A. Gibbard. Manipulation of voting schemes: A general result. Econometrica, 41(4):587-601, 1973.
  20. [Gibbard, 1977] A. Gibbard. Manipulation of schemes that mix voting with chance. Econometrica, 45(3):665-681, 1977.
  21. [Katta and Sethuraman, 2006] A.-K. Katta and J. Sethura- man. A solution to the random assignment problem on the full preference domain. Journal of Economic Theory, 131(1):231-250, 2006.
  22. [McLennan, 2002] A. McLennan. Ordinal efficiency and the polyhedral separating hyperplane theorem. Journal of Economic Theory, 105(2):435-449, 2002.
  23. [Postlewaite and Schmeidler, 1986] A. Postlewaite and D. Schmeidler. Strategic behaviour and a notion of ex ante efficiency in a voting model. Social Choice and Welfare, 3(1):37-49, 1986.
  24. [Sato, 2013] S. Sato. Strategy-proofness and the reluctance to make large lies: the case of weak orders. Social Choice and Welfare, 40(2):479-494, 2013.
  25. [Satterthwaite, 1975] M. A. Satterthwaite. Strategy- proofness and Arrow's conditions: Existence and corre- spondence theorems for voting procedures and social wel- fare functions. Journal of Economic Theory, 10(2):187- 217, 1975.
  26. [Tang and Lin, 2009] P. Tang and F. Lin. Computer-aided proofs of Arrow's and other impossibility theorems. Ar- tificial Intelligence, 173(11):1041-1053, 2009.
  27. [Zhou, 1990] L. Zhou. On a conjecture by Gale about one- sided matching problems. Journal of Economic Theory, 52(1):123-135, 1990.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards