# Stochastic Game Analysis of Cooperation and Selfishness in a Random Access Mechanism
## 5 Stochastic Game Formulation
### Characterization of the Game Equilibrium  
The game equilibrium is a situation where all users are satisfied with their action choices, and no one is interested in deviating. In game theory, an equilibrium is usually characterized by a strategy profile where different users (players) choose different actions [31]. However, for simplicity purposes, we focus on the symmetric strategy profile \((\Psi^{*}_{c},\Psi^{*}_{nc})\), where \(\Psi^{*}_{c}\) is the strategy chosen by all cooperative users, and \(\Psi^{*}_{nc}\) is the strategy chosen by all non-cooperative users. Furthermore, we consider Markovian strategies that do not depend on past actions but only on the system state. The equilibrium of the game can be obtained as a pair \((\Psi^{*}_{c},\Psi^{*}_{nc})\), where \(\Psi^{*}_{c}\) is the social optimal for cooperative users and \(\Psi^{*}_{nc}\) is the Nash equilibrium for non-cooperative game. The following theorem provides the conditions for the existence of the equilibrium. **Theorem 2**. : _The pair \((\Psi^{*}_{c},\Psi^{*}_{nc})\) is an equilibrium of the game if it satisfies:_  
\[(i)\Psi^{*}_{c}\text{ maximizes the global utility }U_{g}(\Psi). \tag{48}\] \[(ii)\Psi^{*}_{nc}\in\underset{\Psi^{i}\in[\epsilon,1]^{2}}{ \operatorname{argmax}}\{u_{i}([\Psi^{*}_{nc}]^{-i},\Psi^{i})\},\quad\forall i \in S_{N},\quad\forall\epsilon>0. \tag{49}\]  
Proof. : To prove the existence of an equilibrium profile, we should investigate the two games. First, let us consider the cooperative game where users of the set \(S_{M}\) attempt to maximize the overall system performance \(U_{g}\). We emphasize that cooperative users are aware of the total number of users \(M+N\). Additionally, they assume that all users cooperate. Thus, the game from the point of view of users in \(S_{M}\) is a cooperative game of \(M+N\) users. Therefore, the equilibrium is given by the social optimality concept, which is defined by the following optimization problem:  
\[\max_{\Psi\in[\epsilon,1]^{2}}U_{g}(\Psi)\text{ subject to: } \tag{50}\] \[\left\{ \begin{array}{l}\Pi(\Psi)=\Pi(\Psi)\cdot P(\Psi),\\ \Pi_{m,n}(\Psi)\geq 0,\quad m=0,\ldots,M,\quad n=0,\ldots,N\\ \sum\limits_{m=0}^{M}\sum\limits_{n=0}^{N}\Pi_{m,n}(\Psi)=1,\end{array} \right.\]  
where \(\Psi=[\psi,\ldots,\psi]\) and \(\psi=(q_{r},1-q_{r})\). For any value \(q_{r}\in(0,1]\), the steady-state probabilities are continuous functions. Therefore, a solution to the optimization problem (50) might not exist if we consider thenon-closed interval \((0,1]\). However, since we optimize on the closed interval \([e,1]\), an optimal solution exists. Let us now consider the game from the point of view of a selfish user. Each user in the set \(S_{N}\) plays a non-cooperative game with all other users on the system, including users that choose to cooperate. Thus, selfish users assume that everyone is rational and attempt to optimize their own utility functions. Therefore, the game from the point of view of the set \(S_{N}\) is a non-cooperative game of \(M+N\) users. As a result, the equilibrium is obtained using the Nash concept, which satisfies for every user \(i\) in \(S_{N}\) the following condition:  
\[u_{i}(\Psi^{*})\geq u_{i}([\Psi^{*}]^{-i},\Psi^{i})\qquad\forall\psi^{i}\
eq \psi^{*}, \tag{51}\]  
where \(\Psi_{nc}=\{\psi^{*}_{nc},\ldots,\psi_{i},\ldots,\psi^{*}_{nc}\}\), \(\psi_{i}=(q^{i}_{r},1-q^{i}_{r})\) and \(\psi^{*}_{nc}=(q^{*}_{nc},1-q^{*}_{nc})\). According to [PERSON] theorem, a mixed-strategy Nash equilibrium exists since the game includes a finite number of users and actions. Let us now consider the set \(\mathcal{R}_{i}\) of the best response strategies of a user \(i\) in \(S_{N}\). \[\mathcal{R}_{i} =\operatorname*{argmax}_{\Psi^{i}\in[\epsilon,1]^{2}}\{u_{i}( \Psi^{-i},\Psi^{i})\}, \tag{52}\] \[=\{\Psi^{i}\in[\epsilon,1]^{2}\quad/\quad u_{i}(\Psi)\leq u_{i}( \Psi^{i}),\quad\forall\Psi\in[\epsilon,1]^{2}\}. \tag{53}\]  
We are interested in a symmetric equilibrium where all selfish users use the same strategy.