Selection of Efficient Pure Strategies in Allocation Games

Pierre Coucheney 1 Corinne Touati 1 Bruno Gaujal 1, *
* Auteur correspondant
1 MESCAL - Middleware efficiently scalable
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
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.
Type de document :
Communication dans un congrès
Proc. of the International Conference on Game Theory for Networks (GameNets), 2009, Istambul, Turkey. IEEE, pp.658-666, 2009, 〈10.1109/GAMENETS.2009.5137457〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00788918
Contributeur : Arnaud Legrand <>
Soumis le : vendredi 15 février 2013 - 13:46:24
Dernière modification le : mercredi 11 avril 2018 - 01:53:02

Lien texte intégral

Identifiants

Collections

Citation

Pierre Coucheney, Corinne Touati, Bruno Gaujal. Selection of Efficient Pure Strategies in Allocation Games. Proc. of the International Conference on Game Theory for Networks (GameNets), 2009, Istambul, Turkey. IEEE, pp.658-666, 2009, 〈10.1109/GAMENETS.2009.5137457〉. 〈hal-00788918〉

Partager

Métriques

Consultations de la notice

129