k-Implementation

ABSTRACT

This paper discusses an interested party who wishes to influence the behavior of agents in a game, which is not under his control. The interested party cannot design a new game, cannot enforce agents' behavior, cannot enforce payments by the agents, and cannot prohibit strategies available to the agents. However, he can influence the outcome of the game by committing to non-negative monetary transfers for the different strategy profiles that may be selected by the agents. The interested party assumes that agents are rational in the commonly agreed sense that they do not use dominated strategies. Hence, a certain subset of outcomes is implemented in a given game if by adding non-negative payments, rational players will necessarily produce an outcome in this subset. Obviously, by making sufficiently big payments one can implement any desirable outcome. The question is what is the cost of implementation? In this paper we introduce the notion of k-implementation of a desired set of strategy profiles, where k stands for the amount of payment that need to be actually made in order to implement desirable outcomes. A major point in k-implementation is that monetary offers need not necessarily materialize when following desired behaviors. We define and study k-implementation in the contexts of games with complete and incomplete information. In the later case we mainly focus on the VCG games. Our setting is later extended to deal with mixed strategies using correlation devices. Together, the paper introduces and studies the implementation of desirable outcomes by a reliable party who can not modify game rules (i.e. provide protocols), complementing previous work in mechanism design, while making it more applicable to many realistic CS settings.

REFERENCES

• 1: R.J. Aumann. Subjectivity and correlation in randomized strategies. Journal of Mathematical Economics, 1:67--96, 1974.
• 2: E. Clarke. Multipart pricing of public goods. Public Choice, 18:19--33, 1971.
• 3: V. Conitzer and T. Sandholm. Complexity of mechanism design. In Proceedings of the 18th conference on uncertainity in Artificial Intelligence (UAI-02), pages 103--110, 2002.
• 4: P. Dybvig and C.S. Spatt. Adoption externalities as public goods. Journal of Public Economics, 20:231--247, 1983.
• 5: Joan Feigenbaum , Scott Shenker, Distributed algorithmic mechanism design: recent results and future directions, Proceedings of the 6th international workshop on Discrete algorithms and methods for mobile computing and communications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570810.570812]
• 6: D. Fudenberg and J. Tirole. Game Theory. MIT Press, 1991.
• 7: T. Groves. Incentives in teams. Econometrica, 41:617--631, 1973.
• 8: S. Hart. games in extensive and strategic forms. In R.J. Aumann and S. Hart, editors, Handbook of Game Theory, chapter 2, pages 19--40. North Holland, Amsterdam, 1992.
• 9: R. Holzman, N. Kfir-Dahav, D. Monderer, and M. Tennenholtz. Bundling Equilibrium in Combinatorial Auctions. Working paper Technion http://ie.technion.ac.il/dov.phtml, 2001.
• 10: R. Holzman and D. Monderer. Characterization of ex post equilibrium in the VCG combinatorial auctions. Working Paper, Technion, http://ie.technion.ac.il/dov.phtml, 2002.
• 11: E. Koutsoupias and C. Papadimitriou. Worst-Case Equilibria. In STACS, 1999.
• 12: H.W. Kuhn. Extensive games and the problem of information. Annals of Mathematics Studies, 48, 1953.
• 13: A. Mas-Colell, M.D. Whinston, and J.R. Green. Microeconomic Theory. Oxford University Press, 1995.
• 14: E. Maskin. Nash equilibrium and welfare optimality. Review of Economic Studies, 66:23--38, 1999.
• 15: E. Maskin and T. Sjostrom. Implementation theory. In K. J. Arrow, A. K. Sen, and Kotaro Suzumura, editors, Handbook of Social Choice Theory and Welfare Volume 1. North-Holland, Amsterdam, 2002.
• 16: D. Monderer and L.S. Shapley. Potential games. Games and Economic Behavior, 14:124--143, 1996.
• 17: Moni Naor , Benny Pinkas , Reuban Sumner, Privacy preserving auctions and mechanism design, Proceedings of the 1st ACM conference on Electronic commerce, p.129-139, November 03-05, 1999, Denver, Colorado, United States [doi>10.1145/336992.337028]
• 18: J.F. Nash. Equilibrium points in n-person games. Proceedings of the National Academy of Sciences of the United States of America, 36:48--49, 1950.
• 19: Noam Nisan, Bidding and allocation in combinatorial auctions, Proceedings of the 2nd ACM conference on Electronic commerce, p.1-12, October 17-20, 2000, Minneapolis, Minnesota, United States [doi>10.1145/352871.352872]
• 20: Noam Nisan , Amir Ronen, Algorithmic mechanism design (extended abstract), Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.129-140, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301287]
• 21: Christos Papadimitriou, Algorithms, games, and the internet, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.749-753, July 2001, Hersonissos, Greece [doi>10.1145/380752.380883]
• 22: David C. Parkes, iBundle: an efficient ascending price bundle auction, Proceedings of the 1st ACM conference on Electronic commerce, p.148-157, November 03-05, 1999, Denver, Colorado, United States [doi>10.1145/336992.337032]
• 23: Jeffrey S. Rosenschein and Gilad Zlotkin. Rules of Encounter. MIT Press, 1994.
• 24: R.W. Rosenthal. A class of games possessing pure-strategy nash equilibria. International Journal of Game Theory, 2:65--67, 1973.
• 25: Tim Roughgarden, The price of anarchy is independent of the network topology, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509971]
• 26: Tim Roughgarden , Éva Tardos, How bad is selfish routing?, Journal of the ACM (JACM), v.49 n.2, p.236-259, March 2002 [doi>10.1145/506147.506153]
• 27: T. Sandholm, S. Suri, A. Gilpin, and D. Levine. Cabob: A fast optimal algorithm for combinatorial auctions. In 17th International Joint Conference on Artificial Intelligence, pages 1102--1108, 2001.
• 28: I. Segal. Contracting with externalities. The Quarterly Journal of Economics, CXIV(2):337--388, May 1999.
• 29: Y. Shoham and M. Tennenholtz. On rational computability and communication complexity. Games and Economic Behavior, 35:197--211, 2001.
• 30: R. Spiegler. Extracting intercation-created surplus. Games and Economic Behavior, 30:142--162, 2000.
• 31: Moshe Tennenholtz, Electronic Commerce: From Economic and Game-Theoretic Models to Working Protocols, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.1420-1428, July 31-August 06, 1999
• 32: W. Vickrey. Counterspeculations, auctions, and competitive sealed tenders. Journal of Finance, 16:15--27, 1961.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.m Miscellaneous

General Terms:
Algorithms, Economics, Theory

Keywords:
implementation by an interested party, implementation cost, implementation theory