Game-theoretic recommendations: some progress in an uphill battle

ABSTRACT

Game theory has become the central language for the analysis of multi-agent systems. Moreover, the central game-theoretic solution concept, the Nash equilibrium, has become a standard tool for that analysis. A game is a general way for representation of interactions among agents: each agent has strategies he can choose from, and each tuple of strategies, one for each agent, determines a payoff for each of the agents. A Nash equilibrium is a strategy profile, such that unilateral deviations from it are not beneficial. However, this concept does not provide a solution to what we believe to be the major challenges of game theory and the theory of multi-agent systems:

1. Given a game, how should the agent choose his action?

2. Given a game, how can a mediator/administrator, who can not enforce behavior, lead the agents to adopt a desired behavior?

REFERENCES

• 1: A. Altman, A. Boden-Bercovici, and M. Tennenholtz. Learning in one-shot strategic form games. In Proceedings of ECML-06, 2006.
• 2: A. Altman and M. Tennenholtz. On the axiomatic foundations of ranking systems. In Proc. 19th International Joint Conference on Artificial Intelligence, pages 917--922, 2005.
• 3: A. Altman and M. Tennenholtz. An axiomatic approach to personalized ranking systems. In Proc. 20th International Joint Conference on Artificial Intelligence, 2006.
• 4: Reid Andersen , Christian Borgs , Jennifer Chayes , Uriel Feige , Abraham Flaxman , Adam Kalai , Vahab Mirrokni , Moshe Tennenholtz, Trust-based recommendation systems: an axiomatic approach, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China [doi>10.1145/1367497.1367525]
• 5: R. Aumann. Acceptable points in general cooperative n-person games. In A. Tucker and R. Luce, editors, Contribution to the Theory of Games, Vol. IV, Annals of Mathematics Studies, 40, pages 287--324. 1959.
• 6: R. Aumann. On the non-transferable utility value: A comment on the Roth-Shaper examples. Econometrica, 53(3):667--677, 1985.
• 7: Y. Bakos and C. N. Dellarocas. Cooperation without enforcement? a comparative analysis of litigation and online reputation as quality assurance mechanisms. MIT Sloan School of Management Working Paper No. 4295-03, 2003.
• 8: C. Camerer, T. Ho, and J. Chong. A cognitive hierarchy model of games. The Quarterly Journal of Economics, 119(3):861--898, 2004.
• 9: David Carmel , Shaul Markovitch, Exploration Strategies for Model-based Learning in Multi-agent Systems: Exploration Strategies, Autonomous Agents and Multi-Agent Systems, v.2 n.2, p.141-172, June 1999 [doi>10.1023/A:1010007108196]
• 10: M. Costa-Gomes, V. P. Crawford, and B. Broseta. Cognition and behavior in normal-form games: An experimental study. Econometrica, 69(5):1193--1235, 2001.
• 11: Rajdeep K. Dash , Sarvapali D. Ramchurn , Nicholas R. Jennings, Trust-Based Mechanism Design, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.748-755, July 19-23, 2004, New York, New York [doi>10.1109/AAMAS.2004.287]
• 12: Y. Freund and R. E. Schapire. Adaptive game playing using multiplicative weights. Games and Economic Behavior, 29:79--103, 1999.
• 13: I. Gilboa and D. Schmeidler. Case-based decision theory. Quarterly Journal of Economics, 110:605--639, 1995.
• 14: R. S. John, C. Harsanyi. A general theory of equilibrium selection in games. Journal of Economic Literature, 27:1171--1173, 1989.
• 15: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Journal of the ACM (JACM), v.46 n.5, p.604-632, Sept. 1999 [doi>10.1145/324133.324140]
• 16: E. Koutsoupias and C. Papadimitriou. Worst-Case Equilibria. In STACS, 1999.
• 17: D. Kuminov, and M. Tennenholtz. Competitive Safety Analysis in Position Auctions. In Proceedings of WINE-07, 2007.
• 18: P. Massa and P. Avesani. Controversial users demand local trust metrics: An experimental study on epinions.com community. In Proc. of AAAI-05, pages 121--126, 2005.
• 19: D. Monderer and L. Shapley. Potential games. Games and Economic Behavior, 14:124--143, 1996.
• 20: D. Monderer and M. Tennenholtz. K-Implementation. Journal of Artificial Intelligence Research, 21:37--62, 2004.
• 21: D. Monderer and M. Tennenholtz. Strong Mediated Equilibrium. In Proceedings of AAAI-06, 2006.
• 22: L. Page, S. Brin, R. Motwani, and T. Winograd. The pagerank citation ranking: Bringing order to the web. Technical Report, Stanford University, 1998.
• 23: R. Powers and Y. Shoham. New criteria and a new algorithm for learning in multi-agent systems. Proceedings of NIPS 2004, 2004.
• 24: P. Resnick and R. Zeckhauser. Trust among strangers in internet transactions: Empirical analysis of ebay's reputation system. Working Paper for the NBER workshop on empirical studies of electronic commerce, 2001.
• 25: Paul Resnick , Ko Kuwabara , Richard Zeckhauser , Eric Friedman, Reputation systems, Communications of the ACM, v.43 n.12, p.45-48, Dec. 2000 [doi>10.1145/355112.355122]
• 26: R. Rosenthal. A class of games possessing pure-strategy nash equilibria. International Journal of Game Theory, 2:65--67, 1973.
• 27: 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]
• 28: 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]
• 29: O. Rozenfeld and M. Tennenholtz. Group Dominant Strategies. In Proceedings of WINE-07, 2007.
• 30: O. Rozenfeld and M. Tennenholtz. Routing Mediators. In Proc. 20th International Joint Conference on Artificial Intelligence, 2007.
• 31: D. Stahl. Evolution of smart players. Games and Economic Behavior, 5(4):604--617, October 1993.
• 32: D. I. Stahl and P. W. Wilson. Experimental evidence on players' models of other players. Journal of Economic Behavior & Organization, 25(3):309--327, December 1994.
• 33: D. O. Stahl. Population rule learning in symmetric normal-form games: theory and evidence. Journal of Economic Behavior and Organization, 1304:1--14, 2001.
• 34: M. Tennenholtz. Competitive Safety Analysis: robust decision-making in multi-agent systems. Journal of Artificial Intelligence Research, 17:363--378, 2002.
• 35: Moshe Tennenholtz, Reputation systems: an axiomatic approach, Proceedings of the 20th conference on Uncertainty in artificial intelligence, p.544-551, July 07-11, 2004, Banff, Canada
• 36: H. R. Varian. Position auctions. Technical Report, UC Berkeley. Available at http://www.sims.berkeley.edu/~hal/Papers/2006/, 2006.
• 37: J. von Neumann and O. Morgenstern. Theory of Games and Economic Behavior. Princeton University Press, Princeton, 1944.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Coherence and coordination

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Multiagent systems
      I.2.8 Problem Solving, Control Methods, and Search

General Terms:
Algorithms, Design, Management