Learning Equilibrium in Resource Selection Games

摘要

We consider a resource selection game with incomplete information about the resource-cost functions. All the players know is the set of players, an upper bound on the possible costs, and that the cost functions are positive and nondecreas-ing. The game is played repeatedly and after every stage each player observes her cost, and the actions of all players. For every ε > 0 we prove the existence of a learning e-equilibrium, which is a profile of algorithms, one for each player such that a unilateral deviation of a player is, up to ε not beneficial for her regardless of the actual cost functions. Furthermore, the learning equilibrium yields an optimal social cost.