## 5 Computation of Stationary Markov Equilibrium: An Algorithm  
The result of Theorem 2 suggests a method for computing a stationary Markov equilibrium in asynchronous stochastic games when the game has a fixed number of cycles. Assume that \(n\) players choose in a fixed-cycle every \(K\) period, where \(K\geq n\), then, the following method can be used to compute a stationary Markov equilibrium of the game. **The Algorithm** STEP 1: Assume some value function \(v^{K}:S\rightarrow\mathbb{R}^{n}\) for period \(K+1\). Then, find the optimal action of player \(p(K)\) for the payoff function in period \(K\),  
\[u_{p(K)}(s_{K},a_{K})+\delta\sum_{s_{w}\in S_{K+1}}v^{K}_{p(K)}(s_{w})q(s_{w}: s_{K},a_{K}), \tag{9}\]  
given that the expected future payoff is given by \(v^{K}_{p(K)}:S\rightarrow\mathbb{R}\). STEP 2: Denote \(v^{K}_{p(K-1),K}:S_{K-1}\to\mathbb{R}\) to be the value function of player \(p(K-1)\), from the optimal choice of player \(p(K)\) in Step 1. Find the optimal choice of player \(p(K-1)\) for the payoff function  
\[u_{p(K-1)}(s_{K-1},a_{K-1})+\delta\sum_{s_{w}\in S_{K}}v^{K}_{p(K-1),K}(s_{w})q( s_{w}:s_{K-1},a_{K-1}). \tag{10}\]  
This will generate the value function \(v^{K}_{p(K-2),K-1}:S_{K-1}\to\mathbb{R}\) for player \(p(K-2)\). This is the expected payoff of player \(p(K-2)\) in period \(K-1\), given that players \(p(K)\) and \(p(K-1)\) have chosen optimally in periods \(K\) and \(K-1\). The optimal choice of player \(p(K-2)\) in period \(K-2\) then gives the expected payoff of player \(p(K-3)\) in period \(K-3\). One proceeds in this manner until one gets to period 1, and the optimal choice of player \(p(1)\). The value function that one now has is the expected payoff of the players \(1\cdots n\) in the \(K\)-period asynchronous game, given that the value function for period \(K+1\) is \(v^{K}:S_{K+1}\to\mathbb{R}^{n}\). Denote this by \(v^{K}_{1}:S_{1}\to\mathbb{R}^{n}\). This is the Markov equilibrium payoff of the truncated \(K\)-period asynchronous game in period 1. STEP 3: One now computes the equilibrium payoff of the truncated \(2K\)-period asynchronous game as follows. The last \(K\) periods of the \(2K\) period game is a replica of the \(K\)-period game analyzed in Steps 1 and 2. In period \(K\), the expected payoff of player \(p(K)\) is now given by \(v^{K,1}:S_{K}\to\mathbb{R}\). Using this as the expected payoff function for period \(K+1\), one computes the value functions, and the Markov equilibrium payoff of the asynchronous game, as in Steps 1 and 2. The value function that one now has is the expected payoff of players \(1\cdots n\) in the \(2K\)-period asynchronous game, given that the value function for period \(K+1\) is \(v^{K,1}:S_{1}\to\mathbb{R}^{n}\). Denote this by \(v^{K,2}:S_{1}\to\mathbb{R}^{n}\). This is the Markov equilibrium payoff of the truncated \(2K\)-period asynchronous game. STEP 4: One now computes the Markov equilibrium payoffs of the truncated \(3K\)-period game as in Steps 1 and 2 using the expected payoff function \(v^{K,2}:S_{1}\to\mathbb{R}^{n}\). This will generate the payoff functions \(\{v^{K,2}_{\ell}\}_{\ell=1}^{K}\), where \(v^{K,2}_{\ell}:S_{\ell}\to\mathbb{R}^{n}\) is the payoff function of the players in period \(\ell:1\leq\ell\leq K\), in the \(3K\)-period truncated game. Iterations of Steps 1 through 4 are carried through until the process starts to converge. Theorem 3: _The algorithm generates a stationary equilibrium in the asynchronous game with the fixed \(K\)-period cycle._  
Proof: We first note that for each set of \(K\)-periods \(sK+1,\cdots,(s+1)K\), for \(s=0,1,2,\cdots\), the algorithm generates a sequence \(\{f^{\ell}_{p(sK+1)},\cdots,f^{\ell}_{p((s+1)K)}\}_{\ell}\) of strategies and a sequence \(\{v^{\ell}_{p(sK+1)},\cdots,v^{\ell}_{p((s+1)K)}\}_{\ell}\) of value functions that give the optimal choices, and the optimal value functions for these periods, for the truncation of the asynchronous game after \(\ell K\)-periods, \(\ell=1,2,\cdots\).