Proceedings

Analysis and Optimization of Multi-Dimensional Percentile Mechanisms

Download BibTeX Cite

Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. Pages 367-373.

© 2013 International Joint Conferences on Artificial Intelligence

Abstract

We consider the mechanism design problem for agents with single-peaked preferences over multi-dimensional domains when multiple alternatives can be chosen. Facility location and committee selection are classic embodiments of this problem. We propose a class of percentile mechanisms, a form of generalized median mechanisms, that are strategy-proof, and derive worst-case approximation ratios for social cost and maximum load for L1 and L2 cost models. More importantly, we propose a sample-based framework for optimizing the choice of percentiles relative to any prior distribution over preferences, while maintaining strategy-proofness. Our empirical investigations, using social cost and maximum load as objectives, demonstrate the viability of this approach and the value of such optimized mechanisms vis-a-vis mechanisms derived through worst-case analysis.

  1. [Barberà et al., 1993] Salvador Barberà, Faruk Gul, and En- nio Stacchetti. Generalized median voter schemes and committees. J. Economic Theory, 61(2):262-289, 1993.
  2. [Barberà, 2010] Salvador Barberà. Strategy-proof social choice. In K. J. Arrow, A. K. Sen, and K. Suzumura, ed- itors, Handbook of Social Choice and Welfare, volume 2, pp.731-832. North-Holland, Amsterdam, 2010.
  3. [Berthold, 2007] Vöcking Berthold. Selfish load balanc- ing. In Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V. Vazirani, editors, Algorithmic Game Theory, pp.517-542. Cambridge University Press, 2007.
  4. [Black, 1948] Duncan Black. On the rationale of group decision-making. J. Political Econ., 56(1):23-34, 1948.
  5. [Border and Jordan, 1983] Kim C. Border and J. S. Jordan. Straightforward elections, unanimity and phantom voters. The Review of Economic Studies, 50(1):153-170, 1983.
  6. [Clarke, 1971] Edward H. Clarke. Multipart pricing of pub- lic goods. Public Choice, 11(1):17-33, 1971.
  7. [Conitzer and Sandholm, 2002] Vincent Conitzer and Tuo- mas Sandholm. Complexity of mechanism design. In Proc. Eighteenth Conference on Uncertainty in Artificial Intelligence (UAI-02), pp.103-110, Edmonton, 2002.
  8. [Dokow et al., 2012] Elad Dokow, Michal Feldman, Reshef Meir, and Ilan Nehama. Mechanism design on discrete lines and cycles. In Proc. Thirteenth ACM Conference on Electronic Commerce (EC'12), pp.423-440, Valencia, Spain, 2012.
  9. [Escoffier et al., 2011] Bruno Escoffier, Laurent Gourvès, Thang Nguyen Kim, Fanny Pascual, and Olivier Span- jaard. Strategy-proof mechanisms for facility location games with many facilities. In Proc. Second Interna- tional Conference on Algorithmic Decision Theory (ADT- 11), pp.67-81, Piscataway, NJ, 2011.
  10. [Feigenbaum et al., 2010] Joan Feigenbaum, Aaron D. Jag- gard, and Michael Schapira. Approximate privacy: Foundations and quantification (extended abstract). In Proc. Eleventh ACM Conference on Electronic Commerce (EC'10), pp.167-178, Cambridge, MA, 2010.
  11. [Fotakis and Tzamos, 2010] Dimitris Fotakis and Christos Tzamos. Winner-imposing strategyproof mechanisms for multiple facility location games. In Proc. Sixth Inter- national Workshop on Internet and Network Economics (WINE-10), pp.234-245, Stanford, CA, 2010.
  12. [Fotakis and Tzamos, 2012] Dimitris Fotakis and Christos Tzamos. On the power of deterministic mechanisms for facility location games. arXiv: 1207.0935, 2012.
  13. [Groves, 1973] Theodore Groves. Incentives in teams. Econometrica, 41:617-631, 1973.
  14. [Koutsoupias and Papadimitriou, 1999] Elias Koutsoupias and Christos Papadimitriou. Worst-case equilibria. In Proc. 16th Symposium on Theoretical Aspects of Computer Science (STACS-99), pp.404-413, Trier, DE, 1999.
  15. [Likhodedov and Sandholm, 2004] Anton Likhodedov and Tuomas Sandholm. Methods for boosting revenue in com- binatorial auctions. In Proc. Nineteenth National Con- ference on Artificial Intelligence (AAAI-04), pp.232-237, Pittsburgh, PA, 2004.
  16. [Likhodedov and Sandholm, 2005] Anton Likhodedov and Tuomas Sandholm. Approximating revenue-maximizing combinatorial auctions. In Proc. Twentieth National Con- ference on Artificial Intelligence (AAAI-05), pp.267-274, Pittsburgh, PA, 2005.
  17. [Lu and Boutilier, 2011] Tyler Lu and Craig Boutilier. Bud- geted social choice: From consensus to personalized deci- sion making. In Proc. Twenty-second International Joint Conference on Artificial Intelligence (IJCAI-11), pp.280- 286, Barcelona, 2011. IJCAI
  18. [Lu et al., 2010] Pinyan Lu, Xiaorui Sun, Yajun Wang, and Zeyuan A. Zhu. Asymptotically optimal strategy-proof mechanisms for two-facility games. In Proc. Eleventh ACM Conference on Electronic Commerce (EC'10), pp.315-324, Cambridge, MA, 2010.
  19. [Massó and Moreno de Barreda, 2011] Jordi Massó and Inés Moreno de Barreda. On strategy-proofness and symmet- ric single-peakedness. Games and Economic Behavior, 72(2):467-484, 2011.
  20. [Moulin, 1980] Hervé Moulin. On strategy-proofness and single peakedness. Public Choice, 35(4):437-455, 1980.
  21. [Procaccia and Tennenholtz, 2009] Ariel D. Procaccia and Moshe Tennenholtz. Approximate mechanism design without money. In Proc. Tenth ACM Conf. on Electronic Commerce (EC'09), pp.177-186, Stanford, CA, 2009.
  22. [Sandholm et al., 2007] Tuomas Sandholm, Vincent Conitzer, and Craig Boutilier. Automated design of multistage mechanisms. In Proc. Twentieth International Joint Conference on Artificial Intelligence (IJCAI-07), pp.1500-1506, Hyderabad, India, 2007. IJCAI
  23. [Sandholm, 2003] Tuomas Sandholm. Automated mecha- nism design: A new application area for search algorithms. In Proc. Intl. Conference on Principles and Practice of Constraint Programming (CP-03), Kinsale, Ireland, 2003.
  24. [Schummer and Vohra, 2002] James Schummer and Rakesh V. Vohra. Strategy-proof location on a net- work. J. Economic Theory, 104(2):405-428, 2002.
  25. [Sui and Boutilier, 2011] Xin Sui and Craig Boutilier. Ef- ficiency and privacy tradeoffs in mechanism design. In Proc. Twenty-fifth AAAI Conference on Artificial Intelli- gence (AAAI-11), pp.738-744, San Francisco, CA, 2011.
  26. [Vickrey, 1961] William Vickrey. Counterspeculation, auc- tions, and competitive sealed tenders. Journal of Finance, 16(1):8-37, 1961.

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

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