Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Equilibria in Online Games
event speaker icon
Roee Engelberg (Ph.D. Thesis Seminar)
event date icon
Monday, 06.10.2008, 14:00
event location icon
Taub 601
event speaker icon
Advisor: Prof. Seffi Naor
We initiate the study of scenarios that combine both online decision making and interaction between non-cooperative agents. To this end we introduce the notion of online games that model such scenarios as non-cooperative games, and lay out 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 not likely 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 criteria. 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, finding equilibria in online games is the central issue we concentrate on.