# 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.2 Auction-Based Load Balancing  
To describe the LB process as a _first price sealed-bid auction_[39], the LB module could be considered a contractor who has \(K=\left|\mathbf{K}\right|\) goods (the \(K\) flows) to deliver and let the \(N\) tunnel agents represent the \(N\) available deliverers. Each tunnel agent \(j\) submits simultaneous \"sealed bids\" \(b_{j}(f_{i})\) which represent the price for transferring the packets of flow \(f_{i}\), the bidder with the lowest offer wins the contract for transferring flow \(f_{i}\), and the LB module pays the price for the transfer of the flow \(f_{i}\). The goal of the tunnel agents is to maximize their payoff represented by the difference between the price paid by the LB module, \(b_{j}(f_{i})\), and the true cost of transferring the flow \(f_{i}\) through the tunnel \(j\), denoted by \(v_{j}(f_{i})\). If \(b_{j}(f_{i})\)is not the winning bid, then the payoff to tunnel agent \(j\) is 0. If \(b_{j}(f_{i})\) is the winning bid, then the payoff to tunnel agent \(j\) is \(b_{j}(f_{i})-v_{j}(f_{i})\). It can be noticed that the true-value bidding in this game cannot be the dominant strategy. By bidding for the true value, a bidder receives a payoff of 0 if it loses and it will also receive a payoff of 0 if it wins, since he receives the same value as its costs. As a result, the optimal way to bid in the first price auction is to \"shade\" the bid slightly upward, so that if a bidder wins, it receives a positive payoff. Finding out how much to increase the bid involves a trade-off between two opposite forces. If the bid is close to the true value, then the payoff will be small if the bidder wins. However, if the asked price is too large compared to the true costs, this increases the potential payoff of the bidder in the event of winning, but it reduces the chance of being the lowest bid and in consequence the chance of winning. Finding the optimal value of the bid is a complex problem that depends on the knowledge of the other bidders and their way of acting. In the case of our optimization problem, we consider that the real cost of carrying the flow \(f_{i}\) through the tunnel \(j\) would be:  
\[v_{j}(f_{i})=L_{j}\big{(}\mathbf{K}_{j}\cup\{f_{i}\}\big{)}\cdot\big{(}\lambda _{j}+\lambda_{i}\big{)} \tag{21}\]  
which represents the expected latency (relative to the interpacket delay) inserted by tunnel \(j\) if it wins the delivery contract of flow \(i\). The submitted bid is proportional to the communication resources, i.e., the bandwidth used to ensure the requested delays when the packet rates have some values, and the used bandwidth can be considered the cost necessary to carry the packets. For simplicity it can be considered that the submitted bid by the tunnel is:  
\[b_{j}(f_{i})=\big{\{}L_{j}\big{(}\mathbf{K}_{j}\cup\{f_{i}\}\big{)}\cdot\big{(} \lambda_{j}+\lambda_{i}\big{)}+n_{j}\big{\}}+\Delta_{i,j}=\big{\{}v_{j}(f_{i} )+n_{j}\big{\}}+\Delta_{i,j} \tag{22}\]  
It can be noticed that the bid submitted by the agent \(j\), is shaded by the number of packets waiting in the queue \(n_{j}\), while \(\Delta_{i,jj}\) represents the amount of penalty which the contractor (the LB module) must pay if it changes the beneficiary of a contract:  
\[\Delta_{i,j}=\left\{ \begin{array}{ll}n_{i}&;f_{i}\
otin\mathbf{K}_{j}\\ z-j&\\ 0&;f_{i}\in\mathbf{K}_{j}\end{array} \right. \tag{23}\]  
where \( \begin{array}{ll}n_{i}\\ z-j\end{array} \) represents the amount of signaling traffic (number of signaling packets) required to move the flow \(i\) from the tunnel \(z\) to tunnel \(j\). The number of packets waiting in the queue \(n_{j}\) will influence the evolution of the delay in the next time periods, and to keep the desired value of the delay it is possible to be needed more bandwidth if \(n_{j}\) increases, i.e., the cost for carrying the packets is influenced by \(n_{j}\). Algorithm 2 presented below gives the operations involved by the Auction-Based LB mechanism.