Equilibria in online games

ABSTRACT

We initiate the study of scenarios that combine online decision making with interaction between non-cooperative agents. To this end we introduce online games that model such scenarios as non-cooperative games, and lay the foundations for studying this model. Roughly speaking, an online game captures systems in which independent agents serve requests in a common environment. The requests arrive in an online fashion and each is designated to be served by a different agent. The cost incurred by serving a request is paid for by the serving agent, and naturally, the agents seek to minimize the total cost they pay. Since the agents are independent, it is unlikely that some central authority can enforce a policy or an algorithm (centralized or distributed) on them, and thus, the agents can be viewed as selfish players in a non-cooperative game. In this game, the players have to choose as a strategy an online algorithm according to which requests are served. To further facilitate the game theoretic approach, we suggest the measure of competitive analysis as the players' decision criterion. As the expected result of non-cooperative games is an equilibrium, the question of finding the equilibria of a game is of central importance, and thus, it is the central issue we concentrate on in this paper.

We study some natural examples for online games; in order to obtain general insights and develop generic techniques, we present an abstract model for the study of online games generalizing metrical task systems. We suggest a method for constructing equilibria in this model and further devise techniques for implementing it.

REFERENCES

• 1: Aditya Akella , Srinivasan Seshan , Richard Karp , Scott Shenker , Christos Papadimitriou, Selfish behavior and stability of the internet:: a game-theoretic analysis of TCP, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 2: Itai Ashlagi , Dov Monderer , Moshe Tennenholtz, Resource selection games with unknown number of players, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan [doi>10.1145/1160633.1160782]
• 3: Baruch Awerbuch , Yossi Azar , Yair Bartal, On-line generalized Steiner problem, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.68-74, January 28-30, 1996, Atlanta, Georgia, United States
• 4: Yair Bartal , Amos Fiat , Yuval Rabani, Competitive algorithms for distributed data management (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.39-50, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129717]
• 5: Piotr Berman , Chris Coulston, On-line algorithms for Steiner tree problems (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.344-353, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258618]
• 6: Avrim Blum , Jason D. Hartline, Near-optimal online auctions, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 7: Allan Borodin , Ran El-Yaniv, Online computation and competitive analysis, Cambridge University Press, New York, NY, 1998
• 8: Byung-Gon Chun , Kamalika Chaudhuri , Hoeteck Wee , Marco Barreno , Christos H. Papadimitriou , John Kubiatowicz, Selfish caching in distributed systems: a game-theoretic analysis, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada [doi>10.1145/1011767.1011771]
• 9: Debojyoti Dutta , Ashish Goel , John Heidemann, Oblivious AQM and nash equilibria, ACM SIGCOMM Computer Communication Review, v.32 n.3, p.20-20, July 2002 [doi>10.1145/571697.571709]
• 10: Mohammad T. Hajiaghayi, Online auctions with re-usable goods, Proceedings of the 6th ACM conference on Electronic commerce, p.165-174, June 05-08, 2005, Vancouver, BC, Canada [doi>10.1145/1064009.1064027]
• 11: Mohammad Taghi Hajiaghayi , Robert Kleinberg , David C. Parkes, Adaptive limited-supply online auctions, Proceedings of the 5th ACM conference on Electronic commerce, May 17-20, 2004, New York, NY, USA [doi>10.1145/988772.988784]
• 12: Nathanael Hyafil , Craig Boutilier, Regret minimizing equilibria and mechanisms for games with strict type uncertainty, Proceedings of the 20th conference on Uncertainty in artificial intelligence, p.268-277, July 07-11, 2004, Banff, Canada
• 13: M. Imase and B. Waxman. Dynamic steiner tree problem. SIAM J. on Disc. Math., 4(3):369--384, 1991.
• 14: Robert Kleinberg , Tom Leighton, The Value of Knowing a Demand Curve: Bounds on Regret for Online Posted-Price Auctions, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.594, October 11-14, 2003
• 15: Ron Lavi , Noam Nisan, Competitive analysis of incentive compatible on-line auctions, Theoretical Computer Science, v.310 n.1-3, p.159-180, 01 January 2004 [doi>10.1016/S0304-3975(03)00391-8]
• 16: Ron Lavi , Noam Nisan, Online ascending auctions for gradually expiring items, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 17: Lavy Libman , Ariel Orda, Optimal sliding-window strategies in networks with long round-trip delays, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.46 n.2, p.219-235, 7 October 2004 [doi>10.1016/j.comnet.2004.03.032]