# 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.3 Combinatorial Auction-Based Load Balancing  
It is considered that the contractor from the previous algorithm could receive quotes for one single flow at a time. However, this may not be very effective because the auction should be repeated with each arriving packet. The combinatorial auction allows players to bid on a subset \(\mathbf{K}_{z}\subseteq\mathbf{K}\). These are most useful if there are _compliments_, i.e., a set of items might be worth more than the sum of the parts [37]. In this case, the bidders submit bids \(b_{j}(\mathbf{K}_{z})\) on each \(\mathbf{K}_{z}\subseteq\mathbf{K}\). The auctioneer chooses an allocation \(\mathbf{s}=(\mathbf{K}_{1}^{*},\mathbf{K}_{2}^{*},\ldots,\mathbf{K}_{N}^{*})\) that minimizes \(\sum\limits_{j=1}^{N}b_{j}(\mathbf{K}_{j})\) over all feasible allocations. Considering all possible arrangements each player submits an exponential number of bids, and the allocation problem becomes NP-hard [36]. To reduce the dimension of the optimization space, the flow agents are endorsed with a potential function \(\phi_{i}\). These potential functions describe the time evolution of the beneficiary's satisfaction with the deliverer [40], i.e., the variation in time of the key performance indicators (bit rate and latency) of the flows. If the potential functions of the flows mapped on a tunnel decrease, the contractor decides to revise the contracts for that tunnel. It generates a set of allocations redistributing a subset of the flows mapped on that tunnel. Considering that the tunnel agents are single-minded bidders, i.e., player \(j\) only cares about one subset \(\mathbf{K}_{j}\), the computation complexity is reduced to polynomial time. In the case of delay-sensitive flows, the time spent by a packet in the transmission chain is the primary parameter that influences the QoS of the transmission. In this case, the _potential function_ should express the delays experienced by the packets of the flow and the degree of user satisfaction in the condition of the experienced delays, which decreases rapidly as the delay is increasing. Denoting by \(\tau_{i}\) the maximum value of the expected delay, we define the utility function for the delay-sensitive data streams as:  
\[\phi_{i}=10^{-\frac{\tau_{i}}{\tau_{i}}} \tag{24}\]  
where \(c_{i}\) is a constant value associated with each flow which allows differentiating the same type of real-time service flows. The maximum value of the proposed utility function is one. Figure 5a presents the variation of the utility function given in (24) with the delay inserted by the tunnel when the coefficient \(c_{i}\) has different values. The used potential function allows a good separation between real-time flows with different maximum delay constraints. For non-real-time traffic the main parameter of interest is the average throughput. The experienced delay, and the possible variations of this delay, have significantly lower importance, even if the delay inserted by the transmission chain cannot be neglected. The proposed potential function expresses the satisfaction of the user according to the Average Call Throughput associated with the flow and the target is, of course, the maximization of the user's satisfaction. The Average Call Throughput \(R_{i}\) can be defined as the total number of transmitted bits divided by the duration of the transmission process. Let \(R_{i}^{call}\) denote the number of bits sent by the user generating flow \(i\) during the current call and \(t_{i}^{call}\) the time elapsed from the beginning of the current call. If the number of bits that can be transferred through the tunnel \(j\) in a single time unit (for ex. one millisecond) is \(L_{j}\), the instantaneous value of the average call throughput, computed on a finite length window, will be:  
\[R_{i}=\frac{R_{i}^{call}+L_{j}}{t_{i}^{call}} \tag{25}\]  
The \(L_{j}\) parameter results from the instantaneous capacity of the wireless link \(C_{j}(t)\).