Payoffs in an infinitely-repeated game with discounting

Question

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.

Answer 1

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

Answer 2

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.