"Learning Equilibria in Repeated Congestion Games"

Speaker: Aviv Zohar, The Hebrew University
Date: Wednesday, 21 January 2009
Time: 12noon
Place: Ross 201

Abstract:

While the class of congestion games has been thoroughly studied in the
multi-agent systems literature, settings with incomplete information
have received relatively little attention. In this paper we consider a
setting in which the cost functions of resources in the congestion
game are initially unknown. The agents gather information about these
cost functions through repeated interaction, and observations of costs
they incur. In this context we consider the following requirement: the
agents' algorithms should {\em themselves} be in equilibrium, {\em
regardless} of the actual cost functions and should lead to an
efficient outcome. We prove that this requirement is achievable for a
broad class of games: repeated symmetric congestion games. Our results
are applicable even when agents are somewhat limited in their capacity
to monitor the actions of their counterparts, or when they are unable
to determine the exact cost they incur from every resource. On the
other hand, we show that there exist asymmetric congestion games for
which no such equilibrium can be found, not even an inefficient
one. Finally we consider equilibria with resistance to the deviation
of more than one player and show that these do not exist even in
repeated resource selection games.

Joint work with Moshe Tennenholtz.