Consider an $n$-player nonzero sum finite game $G$. I have a vague recollection of a wonderful paper proving an equivalence between (1) steady state Nash equilibria of $G$ played countably many times in sequence and (2) a modified form of Nash equilibria that essentially allows enforceable contracts.

For example, the Nash equilibria of the single shot or finitely iterated Prisoner's Dilemma is always defect, but the iterated and cooperative Nash equilibria is always cooperative.

Does anyone remember which paper this might be, or have any hints as to how to find it? I searched for a while but didn't find sufficient keywords.

  • $\begingroup$ Any idea about the (before) date of publishing? What made it "wonderful"? Are you sure it was about $n$ rather then only $2$ players? $\endgroup$ – Řídící Mar 4 '13 at 12:39
  • $\begingroup$ I recall it being a least a couple decades old, and thought it was wonderful because (1) it reduced a infinite game to a finite dimensional computation and (2) was a simple theory that captured cooperation. I am fairly sure that it was for arbitrary numbers of players, since it allowed sets of players to form enforced coalitions. $\endgroup$ – Geoffrey Irving Mar 4 '13 at 17:03

It is not the case that players cooperate in the iterated prisoners dilemma in every Nash equilibrium. Always defect remains an equilibrium. There are results to the effect that if players are sufficiently patient, almost every payoff can be archived in a repeated game as a Nash equilibrium or a subgame-perfect Nash equilibrium. Besides from some technical details, the requirement is eesentially that everyone must get a payoff such that every player can guarantee no more in case the other players gang up on her or him. Such results are commonly known as "folk theorems" in the game theory literature. The seminal paper is due to Aumann and Shapley, wo work with undiscounted preferences. Nowadays, patient players are usually taken to be players that exponentially discount and have a sufficiently low discount rate. The seminal paper using this formalization is due to Fudenberg and Maskin.

There are papers that show that one can archive similar results using some form of (unilateral) contracting in one-shot games. Such papers have been written by Tennenholtz (working paper version here) and Kalai, Kalai, Lehrer, Samet (paper here). These paper restrict themselves to two players though.

  • 1
    $\begingroup$ Thanks! The paper I was thinking of was exactly Aumann's "Acceptable Points in General Cooperative $n$-Person Games", which is the first citation of the linked Shapley paper. You're correct that I misstated the result: I believe a correct summary is that any cooperative coalition-based equilibrium appears as a strong equilibrium of a competitive nondiscounted infinitely iterated game. As you say, the other way does not hold. $\endgroup$ – Geoffrey Irving Mar 5 '13 at 3:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.