# Game theory-based Routing for Wireless Sensor Networks: A Comparative Survey
## 2 Preliminaries
### Basics of Game Theory  
In game theory, a game consists of \(n\) players, each player selects a strategy \(s_{i}\) from a set \(S\). The objective is in maximizing the utility. A game in game theory can be modeled as:  
1. \(P=\{p_{1},p_{2},p_{3},\ldots,p_{n}\}\), which is a set of \(n\) players;
2. \(A=\{a_{1},a_{2},a_{3},\ldots,a_{m}\}\), which is a set of \(m\) actions;
3. \(S=\{s_{1},s_{2},s_{3},\ldots,s_{k}\}\), which is a set of \(k\) strategies;
4. \(U=\) pay-off function to calculate the pay-off.  
_Player_: A player is an agent who makes rational decisions in a game.  
_Game_: A game is a formal description of a strategic situation.  
_Rationality_: We call a player rational if they play such that their own pay-off is maximized. It is often assumed that the rationality of all the players is common knowledge.  
_Strategy_: A strategy is one of the possible actions among the given actions.  
_Pay-off_: A pay-off is a number that is also called the utility. It presents the desirability of an outcome for a player. Given that the outcome is random, pay-offs are weighted with probabilities. The expected pay-off is highly related to the player's intention of taking risks.  
_Action profile_: An action profile is a list of actions, one for each player in the game.  
_Nash equilibrium_: A Nash equilibrium is an action profile \(a^{*}=\{a_{1}{}^{*},a_{2}{}^{*},a_{3}{}^{*},\ldots,a_{n}{}^{*}\}\), where any player \(p_{i}\) cannot perform better by choosing an action different from \(a^{*}\)[48]. It is to be noted that \(a_{i}{}^{*}\) is the set of possible actions that player \(p_{i}\) can choose to lead the Nash equilibrium.  
A game-theoretic modeling of a routing algorithm for a WSN [42] will be briefly discussed here. A cluster-based routing protocol is assumed, where sensor nodes decide whether to be the cluster head (CH) or not on the basis of their residual energy. As discussed above, a game in game theory can be represented as \(G=(P,A,S,u_{i})\), where \(P=\{N\!H,N\!L\}\) is a set of players, where \(N\!H\) represents nodes with high energy, \(N\!L\) represents nodes with low energy; \(S=\{Decision of being a cluster head, Remaining as a normal cluster member\}\), is a set of strategies;;, \(A=\{To\) _be a cluster head, Not to be a cluster head,_\(\}\) is a set of actions; and \(i=0,1,2,\ldots,n\).  
If the residual energy (i.e., amount of energy left in the node) of a node is higher, it is logical to assume that it will become a CH. Players in this game should have this rationality. In set \(A\), two actions have been listed. This list is called the action profile for a game. The pay-off function \(u_{i}\) for node \(i\) with higher energy is given by,  
\[u_{i}=r_{i}-c_{i}, \tag{1}\]  
where \(r_{i}\) and \(c_{i}\) are the reward and penalty for the action that node \(i\) chooses, respectively. If node \(i\) chooses to be a CH despite having low residual energy, it will get a higher penalty than reward. Conversely, if it chooses to be a CH when it has more residual energy than the surrounding nodes, it will receive a higher reward than penalty. For example, if node \(i\) receives a reward of 20 and a penalty of 10 for being a CH, the pay-off is 10. In this example, nodes must compare with each other in terms of residual energy and decide collectively who must be the CH. They use two actions together in the action set, which we can call joint actions, and the pay-offs they generate are collective pay-offs as they are achieved through cooperative coalition. If two players choose two different strategies and there is no other strategy that can maximize the pay-off if one chooses another given that the other player retains the strategy chosen before, a Nash equilibrium is achieved.