3
$\begingroup$

Consider a game with the following payoff matrix:

3,5   0,0   0,0
0,0   5,3   0,0
0,0   0,0   0,0

Suppose the game is played infinitely many times, and both players have discount factor $\delta$.

The players want to create the outcome $4,4$ using only pure strategies. Intuitively, they should alternate between the (3,5) and the (5,3). This will give the row player:

$$(1-\delta)\sum_{t=0}^\infty \delta^{2t}*3 + \delta^{2t+1}*5 = \frac{3+5\delta}{1+\delta} $$

and the column player: $$(1-\delta)\sum_{t=0}^\infty \delta^{2t}*5 + \delta^{2t+1}*3 = \frac{5+3\delta}{1+\delta} $$

The payoff vector goes to $(4,4)$ when $\delta \to 1$, but otherwise it is not exactly $(4,4)$.

I am looking for references about the following questions: in what conditions is it possible to attain exactly a desired payoff vector with only pure strategies (for an arbitrary game and arbitrary number of players)? And how this payoff vector can be constructed?

I looked at some papers about folk theorems for discounted infinitely-repeated games. The problem is that they usually assume that $\delta\to 1$, which is not always true in practice.

$\endgroup$
  • $\begingroup$ Would mixed strategies help you do it? $\endgroup$ – cc7768 Nov 14 '15 at 21:53
  • $\begingroup$ @cc7768 with mixed strategies it is easy; my question is about pure strategies (added an explanation). $\endgroup$ – Erel Segal-Halevi Nov 14 '15 at 22:06
  • $\begingroup$ I am not sure how you derive your payoffs. In repeated games people usually look at 1. average payoffs or 2. sum of discounted payoffs. You seem to be looking at weighted average payoffs. Is this intentional? $\endgroup$ – Giskard Nov 15 '15 at 10:09
  • $\begingroup$ @denesp I look at (2) sum of discounted payoffs. The multiplication by $(1-\delta)$ is standard in the literature; it comes to normalize the discounted sum such that, if the outcome in all periods is the same, then the payoff in the infinite game is equal to the payoff in each period. $\endgroup$ – Erel Segal-Halevi Nov 15 '15 at 13:33
1
$\begingroup$

Disclaimer: I only have a slight clue about repeated games and I have virtually no clue about coding (except the compulsory stuff I had to do in grad school). That being said, consider this stream of consciousness as how I would approach this problem (if I knew how to code). I am not sure this actually works, maybe someone could support this answer with a diagram (that may suggest, it does not work, see comment in the end). As you see, I cannot provide a reference. Take it for what it's worth and please tell me if my idea fails. I am interested. I am mainly replying such that this question gets attention again.

You are interested in a strategy that yields a ($\delta$-weighted) average payoff of 4 for both players in the infinitely repeated game. I construct a finite sequence of strategy profiles for the stage game that yields a payoff arbitrarily close to 4 for both players by alternating between the (3,5) and the (5,3). This sequence can then be repeated infinitely often.

Let $\Pi^i_t$ be player $i$'s ($\delta$-weighted) average payoff of the (to be constructed) sequence at step $t$. Let $NPV_t$ be the net present value of the sequence's payoff of player $i$ at iteration $t$ such that: $$ \Pi_t^i = NPV_t^i \frac{1-\delta}{1-\delta^{t+1}}$$

Start with $\Pi^1_0 = NPV^1_0 =5$ and $\Pi^2_0=NPV^2_0 =3$ (so start with (5,3) outcome). At each point in the iteration, we have $\Delta_t = |\Pi^1_t - 4| = |\Pi^2_t -4|$. Then there is some vector $s$ that tracks whether the (3,5) or the (5,3) outcome is played. It is a sequence of $i$s and $j$s indicating who got the 5 payoff. So start with $s_0 = 1$ (so by the later construction $s_1 = (1, 2)$)

Take some $\delta$ as given and take some $\varepsilon >0$.

Now comes the coding part that intuitively should work:

Start with $t=0$.

If $\Delta_t > \varepsilon$, continue.

If $\Pi^i_t > 4$: Set $NPV^i_{t+1} = NPV^i_{t} +3 \delta^t$ and $NPV^j_{t+1} = NPV^j_{t} +5 \delta^t$. $s_{t+1} = s_t$ with an additional entry $i$.

Once $\Delta_t \leq \varepsilon$, stop and set $T$ equal to the current $t$. Infinite repetition of this sequence yields of course average payoff $\Pi^i_T$ for all players, because the the (weighted) average is $$\Pi^i = (1-\delta) NPV^i = (1-\delta) NPV_T \frac{1}{1-\delta^{T+1}}=\Pi^i_T.$$

Note that the payoffs $\Pi_t$ may NOT converge to 4. Since I do not program I did this manually for some iterations for $\delta =0.9$. $\Delta$ jumps around. But the jumps seem to become smaller. Here I list the payoffs $\Delta$ following this procedure for $t\in \{1,\dots,12\}$. Every time $\Delta$ jumps up is boldface, see that the boldface sequence seems to decrease.

1: 0.05263

2: 0.26199

3: 0.00552

4: 0.15558

5: 0.00995

6: 0.09293

7: 0.00115

8: 0.0692

9: 0.00561

10: 0.04549

11: 0.00023

12: 0.03765

13: 0.00345

$\endgroup$
1
$\begingroup$

I am going to construct pure strategies, taking average payoffs so far as a state variable, that achieve the payoffs $(4,4)$ in the infinitely repeated game.

Call the row player's actions $T$, $M$, and $B$ for Top, Middle and Bottom respectively. Similarly, call the column player's actions $L$, $C$, and $R$.

Define

$$v_i^t = \frac{1 - \delta}{1 - \delta^t} \sum_{k = 0}^{t-1} \delta^k u_i (a^k)$$

for $t \geq 1$, where $a^t$ is the realised action profile in stage $t$. Clearly, $v_i^t$ is the average realised payoff for player $i$ from all periods preceding $t$.

Now, define the strategies inductively:

$$ a^0 = (T,L) $$ $$ a^1 = (M,C) $$ $$ \vdots $$ $$ a^t = \begin{cases} (T,L) & \text{if }v_1^t \ge v_2^t \\ (M,C) & \text{if }v_1^t < v_2^t \end{cases} $$

It is straightforward to show that $v_i^t$ converges (bounded monotonic sequences converge), and that $v_i^t \to 4$. (Suppose not, and then consider the resulting actions for large $t$.)

It is also easy to see that these strategies form a subgame perfect equilibrium.

As for your more general question, as to what conditions guarantee that a given payoff vector can be supported by some equilibrium in pure strategies:

I want to say that all equilibrium payoffs can be supported with pure strategies by a construction similar to the one given above -- at least, in repeated games of complete information with perfect monitoring(*). However, I will admit to not having thought about this very carefully, nor have I seen this result formally stated anywhere, so caveat emptor, I suppose? At the very least, you should be able to support any payoff that lies in the convex hull of the stage game pure strategy NE.

(*) Abreu, Pearce and Stachetti's bang-bang result should extend this, under some conditions, to the case of imperfect public monitoring.

$\endgroup$

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.