Date: Wednesday 01 March 2017
Time: 12:45 - 13:30 (Lunch available from 12:35)
Room: RA 1501 (Ravelijn)
Title: Approximate Pure Nash Equilibria In Budget Games
This talk gives an introduction into the concept of budget games, a variation of the classic congestion games in which the players compete over resources with a finite budget. If the budget of a resource is not sufficient to satisfy the demands of all players, then it has to be split between them in a way that every player receives less than he actually demands. As a strategy, a player can choose among a finite number of subsets of the resources. Each subset features distinct demands on its resources, meaning that the impact a player has on a resource can change with his strategy. These games generally do not have pure Nash equilibria, so we shift our attention to so-called approximate pure Nash equilibria, in which no player can increase his utility by more than some game-wide constant factor (for regular Nash equilibria, this factor is 1). We give an upper bound for the existence of such equilibria by using a potential function. Also, we upper-bound the number of steps the best-response dynamic requires to reach such an approximate equilibrium.