# Game Theory-Based Load-Balancing Algorithms for Small Cells Wireless Backhaul Connections +
## 2 Materials and Methods
### Modeling the Load Balancing on a Set of Tunnels as a Multiplayer Game
#### 2.2.1 Selfish Routing Load Balancing  
In this game, each flow agent chooses the route (tunnel) which minimizes the transit time of the flows' packets (private objective of the game). The social goal of the game is to find an arrangement which minimizes the average delay. Following [37], the notion of \"selfishly defined traffic flow\" is formalized in the next theorem. In this case, it is expected that each packet of a flow is transmitted along the path inserting the minimum latency, the latency being measured with respect to the rest of the flow's packets. If this condition can't be fulfilled for some packets, those packets will be routed on the path with the smallest possible delay. The latency \(\ell_{T_{j}}(f_{i})\) introduced by the tunnel \(T_{j}\) on the packets of flow \(f_{i}\), i.e., \(f_{i}\in\mathbf{K}_{j}\), is defined by the sojourn time. **Theorem 1**. : _A flow \(f_{i}\) in a graph \(G\) representing the network is at Nash equilibrium if and only if for every \(i\in\{1,\ldots,K\}\)\(f_{i}\in\mathbf{K}_{j}\)\(\ell_{T_{j}}(f_{i})\leq\ell_{T_{z}}(f_{i})\); \(\forall z\in\{1,\ldots,N\},z\
eq j\)._  
Briefly, Theorem 1 state that, in a flow at Nash equilibrium, all packets travel on the minimum latency paths. If \(f_{i}\) is at Nash equilibrium, then all flows mapped to that tunnel have equal latency let say \(L_{j}(\mathbf{K}_{j})\). Therefore, the social cost \(\mathcal{C}(\mathbf{s})\) of an arrangement can be expressed as [36]:  
\[\mathcal{C}(\mathbf{s})=\sum_{j=1}^{N}L_{j}\big{(}\mathbf{K}_{j}\big{)}\cdot \lambda_{j} \tag{18}\]  
where \(\lambda_{j}\) denotes the average packet rate through tunnel \(j\). If the stability condition is fulfilled (i.e., the global input rate is less than or equal to the total capacity of the tunnels) the Nash equilibrium always exists and is inherently unique. Definition of the game:  
* the \(f_{i},\ i\in\{1,\ldots K\}\) flow-agents, i.e., the players;
* \(A_{i}=\{T_{1},\ldots,T_{N}\}\) is the finite set of the actions of player \(i\), i.e., each player (flow) should choose one tunnel. It is defined an action profile \(\mathbf{a}=(a_{1},a_{2},\ldots,a_{K})\), where each element \(a_{i}\) of the vector represents one action for each player of the game, and this profile corresponds to an arrangement \(\mathbf{s}\);
* the payoff or the utility function \(u_{i}\) of a player (flow) in this case is \(u_{i}=\ell_{T_{j}}(f_{i})\), i.e., the expected latency if the agent \(i\) chooses tunnel \(j\). Algorithm 1 presented below gives the operations involved by the Selfish Routing LB algorithm. In the previous sections it was mentioned that the mixture of flows applied to each tunnel is supposed to be Poisson distributed, and in consequence the packets interarrival times are exponentially distributed with parameter \(\lambda_{Aj}\). This parameter is necessary to estimate the expected latency \(\ell_{T_{j}}(f_{i})\) on each tunnel. The \(\lambda_{Aj}\) parameter can be obtained by fitting the measured distribution of the interpackel delays with the pdf curve of the exponential distribution. By using the method of moments results \(1/\lambda_{Aj}=mean(\Delta p_{j})\), where \(\Delta p_{j}\) are the packets interarrival times of the flow mix applied to tunnel \(j\). In this simple case, we have only one parameter of the distribution which should be computed.