Repeated games for multiagent systems: a survey

At this point, let the word ‘rational’ simply stand for ‘the one whose goal is to maximize its own payoff’.

This is true for certain choices of the players’ long-term payoff criteria. Different criteria will be described further.

Another definition of a mixed strategy is also possible. If we denote by $$\[--><$>{{\rSigma }_i} <$><!--$$ the set of all pure strategies available to player $$\[--><$> i <$><!--$$, then player $$\[--><$> i <$><!--$$'s mixed strategy can be defined as a mapping $$\[--><$>{{\rho }_i}:H\, \mapsto \,{{{\rm{\rSigma }}}_i} <$><!--$$. It can be verified that these two definitions are equivalent (Mertens et al., 1994).

In the notation γ^t, t is the power of γ and not a superscript.

The support of a mixed action $$\[--><$>{{\alpha }_i} \in {\rm{\rDelta }}({{A}_i}) <$><!--$$ are those pure actions $$\[--><$>{{ a}_i} \in {{A}_i} <$><!--$$ that have a non-zero probability in $$\[--><$>{{\alpha }_i} <$><!--$$.

Recall that an outcome path is defined as $$\[--><$>{{{\bf a}}}\, \equiv \,({{a}^0} ,{{a}^1} ,\, \ldots ) <$><!--$$ with $$\[--><$>{{ a}^t} \in A <$><!--$$.

The assumption of the subsequent punishment on the part of Player 1 is a corollary of the one-shot deviation principle. We have already mentioned in the proof of Theorem 3 that we can assume that the deviator (say Player 1) deviates only once and then it follows the prescribed strategy. In practice, this means that it punishes Player 2 for not being punished by Player 2.

More precisely, the problem of computing a Nash equilibrium profile for an n-player repeated game with n >2 is at least as complex as the problem of computing a Nash equilibrium in an (n − 1)-player stage-game. The latter problem does not have efficient algorithms solving it. Furthermore, this problem has recently been shown to be PPAD-complete (see Papadimitriou & Yannakakis, 1988; Chen & Deng, 2006; Daskalakis et al., 2006 for more details on this subject).