# Wireless Networks under a Backoff Attack: A Game Theoretical Perspective
## 5 Game Theory Analysis of the CSMA/CA Problem When \(N_{p}=2\)
### Learning Algorithms: Regret Matching  
There are algorithms for learning static equilibria. One of the simplest and best known is Regret Matching (RM) algorithm, proposed by [PERSON] and [PERSON] [18; 33]. It is a simple, adaptive strategy that guarantees that the joint distribution of play converges to the set of correlated equilibria of the underlying game if each player plays a regret matching strategy [33]. The main idea of RM is to play a static game repeatedly and update a regret measure for each player depending on the outcome the players obtain each time they play the game. This algorithm requires that each player knows only her payoff and the actions of the other players (i.e., a player does not need to know the payoff functions of the other players). Each time the game is played, the regret \(W_{i}(a^{\prime}_{i})\) is obtained as:  
\[W_{i}(a^{\prime}_{i})=u_{i}(a^{\prime}_{i},a_{-i})-u_{i}(a_{i},a_{-i}),\quad \forall a^{\prime}_{i}\in A_{i} \tag{28}\]  
where \(a_{i}\) is the pure action played by player \(i\), \(a_{-i}\) denotes the pure actions played by all the other players, \(a^{\prime}_{i}\) is used to denote all pure actions available to player \(i\) and \(A_{i}\) is the set of pure actions for player \(i\). If \(W_{i}(a^{\prime}_{i})>0\), RM will assign positive probability to play \(a^{\prime}_{i}\) in the future, because the player would have gained in the past if she had played \(a^{\prime}_{i}\). On the other hand, if \(W_{i}(a^{\prime}_{i})\leq 0\), the player will assign probability 0 to play \(a^{\prime}_{i}\). At the beginning of the game, all regrets are initialized to 0, and they are updated with each repetition of the static game following:  
\[W^{t+1}_{i}(a^{\prime}_{i})=W^{t}_{i}(a^{\prime}_{i})+W_{i}(a^{\prime}_{i}), \quad\forall a^{\prime}_{i}\in A_{i} \tag{29}\]  
where \(W^{t}_{i}(a^{\prime}_{i})\) is the regret at the beginning of the previous iteration \(t\) and \(W_{i}(a^{\prime}_{i})\) is obtained using (28). Observe that subscripts denote players, and superscripts denote time. At the beginning of the static game \(t\), each player chooses a pure action randomly following a distribution \(p_{i}(a_{i})\), where \(p_{i}(a_{i})\) is the probability that player \(i\) uses pure action \(a_{i}\). \(p_{i}(a_{i})\) is obtained at the beginning of each static game as follows:  
* If \(W_{i}(a_{i})\leq 0,\quad\forall a_{i}\in A_{i}\), then choose a pure action randomly following the uniform distribution \(p_{i}(a_{i})\): \[p_{i}(a_{i})=\frac{1}{|A_{i}|}\] (30) where \(|A_{i}|\) stands for the number of pure actions available to player \(i\). * If there are regrets strictly higher than zero, then choose a pure action randomly following this distribution \(p_{i}(a_{i})\): \[p_{i}(a_{i})=\left\{ \begin{array}{ccc}\frac{W_{i}^{t}(a_{i})}{W}&\text{if}&W_{i }^{k}(a_{i})>0\\ 0&\text{if}&W_{i}^{t}(a_{i})\leq 0\end{array} \right.\] (31) where \[W=\sum_{a_{i}\in A_{i}|W_{i}^{t}(a_{i})>0}W_{i}^{t}(a_{i})\] (32) that is, \(W\) is the sum of all positive regrets in game \(t\). Observe that \(W\) is computed in each iteration, as the vector \(W_{i}^{t}\) is updated in each iteration. This definition of \(W\) guarantees that \(p_{i}(a_{i})\) in (31) is an actual distribution: it sums 1 and has nonnegative components. ```
1:Initialize \(W_{i}=(0,0,...,0)\), the dimension of \(W_{i}\) is \(|A_{i}|\)
2:Fix \(T\), the number of iterations
3:for\(t\in\{1,2,...,T\}\)do
4:if\(\max\{W_{i}^{t}\}\leq 0\)then
5: Assign \(a_{i}^{t}\) following (30)
6:else
7: Assign \(a_{i}^{t}\) following (31) and (32)
8:endif
9: Obtain payoff \(u_{i}^{t}(a_{1}^{t},a_{2}^{t})\) for \(i\in\{1,2\}\)
10: Update regrets using (29) and (28)
11:endfor
12:return Strategies using (33)
```  
**Algorithm 1** Regret matching for each player. We use RM to obtain the solution for the CSMA/CA game. A possible implementation for each player is found in Algorithm 1.