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.

8more comments