1st International Conference on Game Theory for Networks

Research Article

Selection of efficient pure strategies in allocation games

  • @INPROCEEDINGS{10.1109/GAMENETS.2009.5137457,
        author={Pierre Coucheney and Corinne Touati and Bruno  Gaujal},
        title={Selection of efficient pure strategies in allocation games},
        proceedings={1st International Conference on Game Theory for Networks},
        publisher={IEEE},
        proceedings_a={GAMENETS},
        year={2009},
        month={6},
        keywords={allocation games; replicator dynamics; stochastic approximation; pure Nash equilibrium},
        doi={10.1109/GAMENETS.2009.5137457}
    }
    
  • Pierre Coucheney
    Corinne Touati
    Bruno Gaujal
    Year: 2009
    Selection of efficient pure strategies in allocation games
    GAMENETS
    IEEE
    DOI: 10.1109/GAMENETS.2009.5137457
Pierre Coucheney1,*, Corinne Touati1,*, Bruno Gaujal1,*
  • 1: INRIA Rhône-Alpes, Grenoble, France.
*Contact email: pierre.coucheney@inria.fr, corinne.touati@inria.fr, bruno.gaujal@inria.fr

Abstract

In this work we consider allocation games and we investigate the following question: under what conditions does the replicator dynamics select a pure strategy? By definition, an allocation game is a game such that the payoff of a player when she takes an action only depends on the set of players who also take the same action. Such a game can be seen as a set of users who share a set of resources, a choice being an allocation to a resource. A companion game (with modified utilities) is introduced. From the payoffs of an allocation game, we define the repercussion utilities: for each player, her repercussion utility is her payoff minus the decrease in marginal payoff that her presence causes to all other players. The corresponding allocation game with repercussion utilities is the game whose payoffs are the repercussion utilities. A simple characterization of those games is given. In such games, if the players select their strategy according to a stochastic approximation of the replicator dynamics, we show that it converges to a Nash equilibrium of the game that is a locally optimal for the initial game. The proof is based on the construction of a potential function for the game. Furthermore, a spectral study of the dynamics shows that no mixed equilibrium is stable, so that the strategies of all players converge to a set of Nash equilibria. Then, martingale argument prove the convergence of the stochastic approximation to a pure point. A discussion of the global/local optimality of the limit points is also included.