Equilibria in Online Games

We initiate the study of scenarios that combine online decision making with interaction between noncooperative agents. To this end we introduce online games that model such scenarios as noncooperative 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 by the serving agent, and naturally the agents seek to minimize the total cost to themselves. 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 noncooperative 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 noncooperative games is an equilibrium, the question of finding the equilibria of a game is of central importance, and thus it is the central issue on which we concentrate 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.