# Stochastic Game Analysis of Cooperation and Selfishness in a Random Access Mechanism
## 4 Problem Formulation
### Performance Evaluation  
**Proposition 1**. : _The average throughput of cooperative and non-cooperative users is given, respectively, as follows_  
\[TH_{c}=\frac{p_{c}}{T_{s}}\sum_{m=0}^{M}\left[(M-m)\,\sum_{n=0}^{N}\Pi_{m,n} \right], \tag{16}\]  
\[TH_{nc}=\frac{p_{nc}}{T_{s}}\sum_{n=0}^{N}\left[(N-n)\,\sum_{m=0}^{M}\Pi_{m,n} \right]. \tag{17}\]  
Proof. : To derive the throughput expression, we need to define the packet's transmission time \(T_{s}\). The slots' lengths in SA are of the same size. However, in SAZD, the slot duration depends on the stations' transmission activities. In the case of ZigZag, the transmission duration takes two slots. Otherwise, the transmission takes one slot duration. Therefore, \(T_{s}\) can be defined as follows  
\[T_{s}= 1\cdot(1-P_{zigzag})+2\cdot P_{zigzag}, \tag{18}\] \[= 1+P_{zigzag}, \tag{19}\]  
where \(P_{zigzag}\) is the probability that two packets are sent using ZD, and it is given by  
\[ \begin{split} P_{zigzag}&=\sum_{m=0}^{M}\sum_{n=0} ^{N}\sum_{i,j,k,l\in\mathbb{N}}\left[Q_{c}(i,m)\cdot Q_{nc}(j,m)\cdot Q_{c}^{r}( k,m)\cdot Q_{nc}^{r}(l,m)\right]\\ &\quad\cdot\Pi_{m,n}\cdot\mathbf{I}_{\{i+j+k+l=2\}}.\end{split}  \tag{20}\]  
Figure 2: Transition diagram of the Markov chain. The straight line corresponds to either a successful transmission or an increase in backlogged packets, whereas the dashed line represents a successful transmission with ZigZag. \(\mathds{1}\) is the indicator function, such that  
\[\mathds{1}_{\{i+j+k+l=2\}}:=\left\{ \begin{array}{ll}1&\text{if}\quad i+j+k+l=2, \\ 0&\text{otherwise}.\end{array} \right. \tag{21}\]  
Now, we can find the average throughput of cooperative users. In the steady state, the average number of transmitted packets equals the average number of arrivals. Therefore, for a fixed value of \(m\), the cooperative arrival rate in each state \((m,n)\), where \(n=0,\ldots,N\), is \(p_{c}(M-m)/T_{s}\). Then, by taking all possible cases for \(m\), we can derive the throughput of cooperative users as Equation (16) of the previous proposition. Similarly, the average number of arrival packets of non-cooperative users is \(p_{nc}(N-n)/T_{s}\), which yields Equation (17) by considering all the possible cases for \(n\). **Remark 1**. : _Equations (16) and (17) represent the average throughput entering the system. In the stationary regime, the expected number of arrivals derived from Equations (16) and (17) equals the expected number of departures. Therefore, the throughput can be expressed as follows_  
\[TH_{c} =\frac{1}{T_{s}}\sum_{m=0}^{M}\sum_{n=0}^{N}P_{c}^{s}(m,n)\cdot \Pi_{m,n}, \tag{22}\] \[TH_{nc} =\frac{1}{T_{s}}\sum_{m=0}^{M}\sum_{n=0}^{N}P_{nc}^{s}(m,n)\cdot \Pi_{m,n}, \tag{23}\]  
where \(P_{c}^{s}(m,n)\) and \(P_{nc}^{s}(m,n)\) are the average number of successfully delivered packets among cooperative and non-cooperative users, respectively. They are given as follows  
\[ \begin{split} P_{c}^{s}(m,n)&=\sum_{i,j\in\mathbb{ N}}(i+j)\big{[}Q_{c}(i,m)\cdot Q_{nc}(j,m)\cdot Q_{c}^{r}(0,m)\cdot Q_{nc}^{r}(0,m )\big{]}\cdot\mathds{1}_{\{1\leq i+j\leq 2\}}\\ &\quad+\sum_{i,j,k,l\in\mathbb{N}}\big{[}Q_{c}(i,m)\cdot Q_{nc}( j,m)\cdot Q_{c}^{r}(k,m)\cdot Q_{nc}^{r}(l,m)\big{]}\cdot\mathds{1}_{\{(i+j)(k+l)=1\}}, \\ P_{nc}^{s}(m,n)&=\sum_{k,l\in\mathbb{N}}(k+l)\big{[} Q_{c}(0,m)\cdot Q_{nc}(0,m)\cdot Q_{c}^{r}(k,m)\cdot Q_{nc}^{r}(l,m)\big{]} \cdot\mathds{1}_{\{1\leq k+l\leq 2\}}\\ &\quad+\sum_{i,j,k,l\in\mathbb{N}}\big{[}Q_{c}(i,m)\cdot Q_{nc}( j,m)\cdot Q_{c}^{r}(k,m)\cdot Q_{nc}^{r}(l,m)\big{]}\cdot\mathds{1}_{\{(i+j)(k+l)=1\}}. \end{split}  \tag{25}\]  
**Proposition 2**. : _The average number of backlogged users is given by_  
\[S_{c} =\sum_{m=0}^{M}m\cdot\left[\sum_{n=0}^{N}\Pi_{m,n}\right], \tag{26}\] \[S_{nc} =\sum_{n=0}^{N}n\cdot\left[\sum_{m=0}^{M}\Pi_{m,n}\right]. \tag{27}\]  
Proof. : The backlogged users are the ones that have a packet on hold due to a previous collision.