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.

In many computational and economic models of multi-agent interaction, each participant repeatedly "best-responds" to the others' actions. Game theory research on the prominent "best-response dynamics" model typically relies on the premise that the interaction between agents is somehow synchronized. However, in many real-life settings, e.g., internet protocols and large-scale markets, the interaction between participants is asynchronous. We tackle the following important questions: (1) When are best-response dynamics guaranteed to converge to an equilibrium even under asynchrony? (2) What is the (computational and communication) complexity of verifying guaranteed convergence? We show that, in general, verifying guaranteed convergence is intractable. In fact, our main negative result establishes that this task is undecidable. We exhibit, in contrast, positive results for several environments of interest, including complete, computationally-tractable, characterizations of convergent systems. We discuss the algorithmic implications of our results, which extend beyond best-response dynamics to applications such as asynchronous Boolean circuits.