# How to find the equilibrium of the following stochastic game (numerically)

I build up a stochastic game with two groups of players (Group A and Group B) and within each group, the players can have two labels as H and L (label of each player may change from period to period). Each player (regardless of her group) can take two actions (1 or 0) at any time. The time $T=0,1,2,...$, discrete time horizon. Each group contains $N$ people (one can think $N$ being large).

The game is played as the following: at $t=0$, the fraction of people within each group with label H is given as initial condition. At the beginning of each period, people from group A and B are randomly re-matching to form $N$ pairs. Within each pair, both parties observe the label vector $r=(r^A,r^B)$, then both parties have to simultaneously take action (either 1 or 0).

If both parties take action 1, then the people in group A within this pair gets reward $R=f(r^B)$ and the people in group B within this pair gets reward $R=f(r^A)$ and $f(H)>f(L)$. Then the label of the two people in this pair will change according to a given transition matrix

\begin{align*} \mathbf{P}\triangleq\begin{array}{ccccc} ~&(H,H)&(H,L)&(L,H)&(L,L)\\ (H,H)&p_{11}&p_{12}&p_{13}&p_{14}\\ (H,L)&p_{21}&p_{22}&p_{23}&p_{24}\\ (L,H)&p_{31}&p_{32}&p_{33}&p_{34}\\ (L,L)&p_{41}&p_{42}&p_{43}&p_{44}\\ \end{array} \end{align*}

If either party take action 0, then neither parties will get any reward and their label remains unchanged and carry over to the next period.

The objective of each player (in either group) is to maximize her total expected discounted reward over infinite time horizon. The discount factor is $\delta\in(0,1)$.

The key of this game is that: it is just like two players solving a Markov Decision Process (MDP), but the two MDPs are linked since the decision of each pair will affect the distribution of the H label players within each group in the next period and this will in turn affects the probability that each player encountering an H player in the next period.

Though this game looks simple, I couldn't even figure out how to compute the equilibrium strategy numerically needless to say solving this game analytically. What I could do is to fix the strategy of group A people and group B people, then I run a simulation. A strategy that I used in the simulation has the form: "if my label is H, what should I do when facing H or L; if my label is L, what should I do when facing H or L". The equilibrium strategy may or may not have this form.

Any suggestion about numerically (or analytically?) solving this game is appreciated.

• Since the players are small (atomistic), isn't it simply the solution of a static game (played over and over)? Moreover, they never meet again, which makes it looks even more as a static game. I am probably missing something. – Pcw. Sep 8 '16 at 18:07
• @Pcw. The idea is the following: think about in period 0, there are 50% of group A player with label H and 30% of group B player with label H. Then let's say group A player always choose 1 and group B player only choose 1 when his label is H and the counterpart's label is H in his pair and if his label is L, he always choose 0. Then you know that only gonna be less than 100% of pairs reach a "deal", then according to the transition matrix, the distribution of group A (and B) player with label H will change in period 1 – FTXX Sep 8 '16 at 18:33
• @Pcw. which means any focal player will have different probability of encountering the other group of player with label H from period to period. Hence, when he compute the expected total discounted reward before the game starts so as to figure out the best strategy, the expectation is very complicated, since it changes over time and depends on the strategy of both group of people. So how the change of the focal player's label only depends on the transition matrix, but the probability of the other party he will meet in the future depends on the collective action – FTXX Sep 8 '16 at 18:35
• What do players observe? And shouldn't strategies depend also at leat on the distribution of Hs and Ls? – Michael Greinecker Sep 9 '16 at 4:44
• @Michael The player only observe the label pair in his/her matching pair. I think the distribution of H within each group evolves in a deterministic way when N goes to infinity. So with the initial condition, the player should be able to derive the evolution of the distribution of H within each group at any time for any fixed strategy – FTXX Sep 9 '16 at 12:35