TIME: 1:30-2:20 pm,  October 31, 2006

PLACE: EEB 003

TITLE:  Equilibria in Online Games

SPEAKER: Roee Engelberg
         Technion   (visiting graduate student at UW)
 

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.

Joint work with Joseph (Seffi) Naor.