# Stochastic Game Analysis of Cooperation and Selfishness in a Random Access Mechanism
## 4 Problem Formulation
### Analytical Model  
In this section, we provide the theoretical model of the proposed mechanism. Let \(\{(X_{k},Y_{k}),\ k\in\mathbb{N}\}\) be the stochastic process representing the number of backlogged users in each group at the beginning of the time slot \(k\). The reason behind using a bi-dimensional stochastic process comes from the subdivision of the users into two groups. Theorem 4.1: _For any choice of values \(q_{c}\in(0,1]\) and \(q_{nc}\in(0,1]\), \((X_{k},Y_{k})_{k\in\mathbb{N}}\) is Markovian with a unique stationary distribution._  
Proof: Consider the process \(\{(X_{k},Y_{k}),\ k\in\mathbb{N}\}\), representing the number of backlogged nodes among cooperative and selfish users in a given slot time \(k\). The state space is then  
\[S=\{0,1,\ldots,M\}\times\{0,1,\ldots,N\}, \tag{5}\]  
where \(M\) and \(N\) denote, respectively, the total number of cooperative and selfish users. Let \(A_{k}\) and \(B_{k}\) denote the number of newly arrived packets, respectively, for cooperative and selfish users during slot \(k-1\) and are scheduled for the first transmission attempt in slot \(k\). Furthermore, let \(C_{k}\) and \(D_{k}\), respectively, be the number of cooperative and selfish backlogged users that attempt to transmit in slot \(k\). Thus, we have  
\[P(A_{k}=i|X_{k}=m) =Q_{c}(i,m), i=0,\ldots,M, \tag{6}\] \[P(B_{k}=i|Y_{k}=n) =Q_{nc}(i,n), i=0,\ldots,N,\] (7) \[P(C_{k}=i|X_{k}=m) =Q_{c}^{r}(i,m), i=0,\ldots,M,\] (8) \[P(D_{k}=i|Y_{k}=n) =Q_{nc}^{r}(i,n), i=0,\ldots,N. \tag{9}\]  
Figure 1: A scenario of a wireless network where \(M\) cooperative users share the same medium with \(N\) selfish users. Therefore, the number of transmissions occurring in a given slot \(k\) among cooperative and selfish users denoted, respectively, by \(E_{k}\) and \(F_{k}\), can be expressed as follows:  
\[E_{k} =A_{k}+C_{k}, \tag{10}\] \[F_{k} =B_{k}+D_{k}. \tag{11}\]  
The evolution of the number of backlogged nodes found in the system at the beginning of slot \(k+1\) can now be expressed by the following equations:  
\[X_{k+1} =X_{k}+A_{k}-\mathds{1}_{\{E_{k}=1\}}-2\cdot\mathds{1}_{\{E_{k}= 2\}}, \tag{12}\] \[Y_{k+1} =Y_{k}+B_{k}-\mathds{1}_{\{F_{k}=1\}}-2\cdot\mathds{1}_{\{F_{k}= 2\}}, \tag{13}\]  
where \(\mathds{1}\) is the indicator function. Thus, the number of backlogged nodes at the beginning of a given time slot \(k+1\) depends not only on the number of arrivals and departures in previous slot \(k\) but also on the system state \((X_{k},Y_{k})\) (i.e., the number of backlogged users). Therefore, the following Markov property holds since the future states of the process are independent of the past states. For all \((x_{0},y_{0}),\ldots,(x_{k+1},y_{k+1})\in S\) and \(k\in\mathbb{N}\), we have:  
\[ \begin{split} P\{(X_{k+1},Y_{k+1})=(x_{k+1},y_{k+1})|(X_{k},Y_{k}) =(x_{k},y_{k}),\ldots,(X_{0},Y_{0})=(x_{0},y_{0})\}\\ =P((X_{k+1},Y_{k+1})=(x_{k+1},y_{k+1})|(X_{k},Y_{k})=(x_{k},y_{k}) ),\end{split}  \tag{14}\]  
where \((x_{0},y_{0})\) denotes the initial state of the Markov chain. Now, let us assume that \(q_{c}=0\) and \(q_{nc}=0\). Then, the Markov chain has six absorbing states, namely, \((M,N)\), \((M-1,N)\), \((M,N-1)\), \((M-2,N)\), \((M,N-2)\) and \((M-1,N-1)\). For \(p_{c}>0\) and \(p_{nc}>0\), all other states are transient. The absorbing states can be reached with positive probabilities \(p_{c}>0\) and \(p_{nc}>0\) from any initial state, except from another absorbing state. Therefore, we shall exclude the case of \(q_{c}=0\) and \(q_{nc}=0\). The stochastic process \(\{(X_{k},Y_{k}),\ n\in\mathbb{N}\}\) can now be described as a homogeneous finite Markov process with \((M+1)\times(N+1)\) possible states, where the transition probabilities are given in the appendix. The transition diagram is given in Figure 2.  
Since all states communicate with each other and the state space is finite, the Markov chain is ergodic [30]. Therefore, the steady-state probability exists, and it is unique.