Approximate mechanism design without money

ABSTRACT

The literature on algorithmic mechanism design is mostly concerned with game-theoretic versions of optimization problems to which standard economic money-based mechanisms cannot be applied efficiently. Recent years have seen the design of various truthful approximation mechanisms that rely on enforcing payments. In this paper, we advocate the reconsideration of highly structured optimization problems in the context of mechanism design. We argue that, in such domains, approximation can be leveraged to obtain truthfulness without resorting to payments. This stands in contrast to previous work where payments are ubiquitous, and (more often than not) approximation is a necessary evil that is required to circumvent computational complexity.

We present a case study in approximate mechanism design without money. In our basic setting agents are located on the real line and the mechanism must select the location of a public facility; the cost of an agent is its distance to the facility. We establish tight upper and lower bounds for the approximation ratio given by strategyproof mechanisms without payments, with respect to both deterministic and randomized mechanisms, under two objective functions: the social cost, and the maximum cost. We then extend our results in two natural directions: a domain where two facilities must be located, and a domain where each agent controls multiple locations.

REFERENCES

• 1: N. Andelman, Y. Azar, and M. Sorani. Truthful approximation mechanisms for scheduling selfish related machines. In Proc. of 22nd STACS, pages 69--82, 2005.
• 2: A. Archer , É. Tardos, Truthful Mechanisms for One-Parameter Agents, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.482, October 14-17, 2001
• 3: A. Archer and E. Tardos. Frugal path mechanisms. ACM Transactions on Algorithms, 3(1), article 3, 2007.
• 4: Sanjeev Arora , Prabhakar Raghavan , Satish Rao, Approximation schemes for Euclidean k-medians and related problems, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.106-113, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276718]
• 5: S. Barbera. An introduction to strategy-proof social choice functions. Social Choice and Welfare, 18:619--653, 2001.
• 6: S. Barbera and B. Peleg. Strategy-proof voting schemes with continuous preferences. Social Choice and Welfare, 7:31--38, 1990.
• 7: Marshall Bern , David Eppstein, Approximation algorithms for geometric problems, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 8: George Christodoulou , Elias Koutsoupias , Angelina Vidali, A lower bound for scheduling mechanisms, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.1163-1170, January 07-09, 2007, New Orleans, Louisiana
• 9: Ofer Dekel , Felix Fischer , Ariel D. Procaccia, Incentive compatible regression learning, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.884-893, January 20-22, 2008, San Francisco, California
• 10: Peerapong Dhangwatnotai , Shahar Dobzinski , Shaddin Dughmi , Tim Roughgarden, Truthful Approximation Schemes for Single-Parameter Agents, Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science, p.15-24, October 25-28, 2008 [doi>10.1109/FOCS.2008.71]
• 11: Shahar Dobzinski , Noam Nisan , Michael Schapira, Truthful randomized mechanisms for combinatorial auctions, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132607]
• 12: Edith Elkind , Amit Sahai , Ken Steiglitz, Frugality in path auctions, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 13: D. Gale and L.S. Shapley. College admissions and the stability of marriage. Americal Mathematical Monthly, 69(1):9--15, 1962.
• 14: A. Gibbard. Manipulation of voting schemes. Econometrica, 41:587--602, 1973.
• 15: Ron Lavi , Chaitanya Swamy, Truthful and Near-Optimal Mechanism Design via Linear Programming, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.595-604, October 23-25, 2005 [doi>10.1109/SFCS.2005.76]
• 16: Ron Lavi , Chaitanya Swamy, Truthful mechanism design for multi-dimensional scheduling via cycle monotonicity, Proceedings of the 8th ACM conference on Electronic commerce, June 11-15, 2007, San Diego, California, USA [doi>10.1145/1250910.1250947]
• 17: Daniel Lehmann , Liadan Ita Oćallaghan , Yoav Shoham, Truth revelation in approximately efficient combinatorial auctions, Journal of the ACM (JACM), v.49 n.5, p.577-602, September 2002 [doi>10.1145/585265.585266]
• 18: Stefano Leonardi , Guido Schaefer, Cross-monotonic cost-sharing methods for connected facility location games, Proceedings of the 5th ACM conference on Electronic commerce, May 17-20, 2004, New York, NY, USA [doi>10.1145/988772.988814]
• 19: Hagay Levin , Michael Schapira , Aviv Zohar, Interdomain routing and games, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374388]
• 20: R. Meir, A.D. Procaccia, and J.S. Rosenschein. Strategyproof classification under constant hypotheses: A tale of two functions. In Proc. of 23rd AAAI, pages 126--131, 2008.
• 21: R. Meir, A.D. Procaccia, and J.S. Rosenschein. Strategyproof classification with shared inputs. In Proc. of 21st IJCAI, 2009. To appear.
• 22: E. Miyagawa. Locating libraries on a street. Social Choice and Welfare, 18(3):527--541, 2001.
• 23: H. Moulin. On strategy-proofness and single-peakedness. Public Choice, 35:437--455, 1980.
• 24: N. Nisan. Introduction to mechanism design (for computer scientists). In N. Nisan, T. Roughgarden, É. Tardos, and V. Vazirani, editors, Algorithmic Game Theory, chapter 9. Cambridge University Press, 2007.
• 25: N. Nisan and A. Ronen. Algorithmic mechanism design. Games and Economic Behavior, 35(1-2):166--196, 2001.
• 26: Martin Pál , Éva Tardo, Group Strategyproof Mechanisms via Primal-Dual Algorithms, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.584, October 11-14, 2003
• 27: A.D. Procaccia and M. Tennenholtz. Approximate mechanism design without money. Manuscript, 2009. Available from: http://www.cs.huji.ac.il/~arielpro/papers/facility.pdf.
• 28: A.E. Roth and M. Sotomayor. Two-Sided Mathing: A Study in Game-Theoretic Modelling and Analysis. Cambridge University Press, 1991.
• 29: M. Satterthwaite. Strategy-proofness and Arrow's conditions: Existence and correspondence theorems for voting procedures and social welfare functions. Journal of Economic Theory, 10:187--217, 1975.
• 30: J. Schummer and R.V. Vohra. Strategy-proof location on a network. Journal of Economic Theory, 104(2):405--428, 2004.
• 31: J. Schummer and R.V. Vohra. Mechanism design without money. In N. Nisan, T. Roughgarden, É. Tardos, and V. Vazirani, editors, Algorithmic Game Theory, chapter 10. Cambridge University Press, 2007.
• 32: Y. Sprumont. Strategyproof collective choice in economic and political environments. The Canadian Journal of Economics, 28(1):68--107, 1995.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

Additional Classification:
  J. Computer Applications
  J.4 SOCIAL AND BEHAVIORAL SCIENCES
      Subjects: Economics

General Terms:
Algorithms, Economics, Theory

Keywords:
algorithmic mechanism design, game theory, social choice