skip to main content
10.5555/1402383.1402389acmconferencesArticle/Chapter ViewAbstractPublication PagesaamasConference Proceedingsconference-collections
research-article

Game-theoretic recommendations: some progress in an uphill battle

Published: 12 May 2008 Publication History

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]
R. Andersen, C. Borgs, J. Chayes, U. Feige, A. Flaxman, A. Kalai, V. Mirrokni, and M. Tennenholtz. Trust-Based Recommendation Systems: an Axiomatic Approach. In Proceedings of WWW-08, 2008.
[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]
D. Carmel and S. Markovitch. Exploration strategies for model-based learning in multiagent systems. Autonomous Agents and Multi-agent Systems, 2(2):141--172, 1999.
[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]
R. Dash, S. Ramchurn, and N. Jennings. Trust-based mechanism design. In Proceedings of the Third International Joint Conference on Autonomous Agents and MultiAgent Systems, pages 748--755, 2004.
[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]
J. M. Kleinberg. Authoritative sources in a hyperlinked environment. Journal of the ACM (JACM), 46(5):604--632, 1999.
[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]
P. Resnick, R. Zeckhauser, R. Friedman, and E. Kuwabara. Reputation systems. Communications of the ACM, 43(12):45--48, 2000.
[26]
R. Rosenthal. A class of games possessing pure-strategy nash equilibria. International Journal of Game Theory, 2:65--67, 1973.
[27]
T. Roughgarden. The price of anarchy is independent of the network topology. In Proceedings of the 34th Annual ACM Symposium on the Theory of Computing, pages 428--437, 2001.
[28]
T. Roughgarden and E. Tardos. How bad is selfish routing? Journal of the ACM, 49(2):236--259, April 2002.
[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]
M. Tennenholtz. Reputation systems: An axiomatic approach. Proceedings of UAI-04, 2004.
[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.

Cited By

View all
  • (2012)Deployment of trust management system in environment of e-commerceProceedings of the 6th KES international conference on Agent and Multi-Agent Systems: technologies and applications10.1007/978-3-642-30947-2_53(484-493)Online publication date: 25-Jun-2012
  • (2011)Trust management methodologies for the webProceedings of the 7th international conference on Reasoning web: semantic technologies for the web of data10.5555/2033313.2033322(445-459)Online publication date: 23-Aug-2011
  • (2009)A prescriptive approach for playing gamesACM SIGecom Exchanges10.1145/1980522.19805268:2(1-4)Online publication date: 1-Dec-2009
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
AAMAS '08: Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems - Volume 1
May 2008
565 pages
ISBN:9780981738109

Sponsors

Publisher

International Foundation for Autonomous Agents and Multiagent Systems

Richland, SC

Publication History

Published: 12 May 2008

Check for updates

Qualifiers

  • Research-article

Conference

AAMAS08
Sponsor:

Acceptance Rates

Overall Acceptance Rate 1,155 of 5,036 submissions, 23%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)1
  • Downloads (Last 6 weeks)0
Reflects downloads up to 13 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2012)Deployment of trust management system in environment of e-commerceProceedings of the 6th KES international conference on Agent and Multi-Agent Systems: technologies and applications10.1007/978-3-642-30947-2_53(484-493)Online publication date: 25-Jun-2012
  • (2011)Trust management methodologies for the webProceedings of the 7th international conference on Reasoning web: semantic technologies for the web of data10.5555/2033313.2033322(445-459)Online publication date: 23-Aug-2011
  • (2009)A prescriptive approach for playing gamesACM SIGecom Exchanges10.1145/1980522.19805268:2(1-4)Online publication date: 1-Dec-2009
  • (2009)Mediated Equilibria in Load-Balancing GamesProceedings of the 5th International Workshop on Internet and Network Economics10.1007/978-3-642-10841-9_60(591-599)Online publication date: 9-Dec-2009

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media