Learning Equilibrium in Resource Selection Games

Abstract

We consider a resource selection game with incomplete in-formation 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 play-ers. For every > 0 we prove the existence of a learning -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 so-cial cost. 1.