research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Inproceedings
Entered by:chita
TitleEquilibrium Points in Fear of Correlated Threats
Bibtex cite IDRACTI-RU1-2008-68
Booktitle 4th International Workshop on Internet and Network Economics (WINE 2008)
Year published 2008
Number 5385
Pages 210-221
Organization WINE 2008
The presentwork considers the following computational problem: Given any finite game in normal form G and the corresponding infinitely repeated game G∞, determine in polynomial time (wrt1 the representation ofG) a profile of strategies for the players inG∞ that is an equilibrium point wrt the limit-of-means payoff. The problem has been solved for two players [10], based mainly on the implementability of the threats for this case. Nevertheless, [4] demonstrated that the traditional notion of threats is a computationally hard problem for games with at least 3 players (see also [8]). Our results are the following: (i) We propose an alternative notion of correlated threats, which is polynomial time computable (and therefore credible). Our correlated threats are also more severe than the traditional notion of threats, but not overwhelming for any individual player. (ii) When for the underlying game G there is a correlated strategy with payoff vector strictly larger than the correlated threats vector, we efficiently compute a polynomial–size (wrt the description of G) equilibrium point for G∞, for any constant number of players. (iii) Otherwise, we demonstrate the construction of an equilibrium point for an arbitrary number of players and up to 2 concurrently positive payoff coordinates in any payoff vector of G. This completely resolves the cases of 3 players, and provides a direction towards handling the cases of more than 3 players. It is mentioned that our construction is not a Nash equilibrium point, because the correlated threats we use are implemented via, not only full synchrony (as in [10]), but also coordination of the other players˘ actions. But this seems to be a fair trade-off between efficiency of the construction and players˘ coordination, in particular because it only affects the punishments (which are anticipated never to be used).
Kontogiannis, Spyros
Spirakis, Paul
KS08_EquilibriumPointsInFearOfCorrelatedThreats_WINE2008version.pdf (main file)
Publication ID529