Wireless Networks (WNs) are characterized for sharing a medium with limited resources (i.e., the air), which may lead to coexistence issues that harm the overall performance of the overlapping devices. Due to the possibility of choosing different configurations (e.g., range of channels, carrier sense threshold, transmit power), we often find an unbalanced share of the resources between WNs. Such imbalance may be solved by the application of fairness policies. However, a fair solution does not always entail a maximization of the aggregate performance. In general, fairness is achieved by a central unit that decides the configuration of the wireless devices. However, we aim to extend this concept to collaborative approaches that share the same fairness goal that boosts the overall performance.

In this document, we aim to shed some light on the fairness problem in WNs, as well as on the main considerations to be done for a proper resource allocation. We also aim to bound the meaning of \emph{the cost of fairness}. Note, as well, that we focus on configurations in which the utilities of players are known. However, there are many other situations in which players show a selfish behavior and do not truthfully reveal their utilities. Such situations lead to what is commonly known as \emph{the price of anarchy}.

Disclaimer: most of the material in this document has been retrieved from Bertsimas, D., Farias, V. F., & Trichakis, N. (2011). The price of fairness. Operations research, 59(1), 17-31.

Fairness definition and measures

We can consider that a solution is fair if none of the parties considers that such a solution is achieved at the expense of some individuals. Henceforth, the concept of fairness is strictly related to the Nash Equilibrium (NE), which is reached if none of the players has reasons to play a different action. Note, as well, that multiple definitions of fairness can be found due to the several interpretations it may have.

Formally, the resource allocation problem can be defined as follows:

• Let $n$ be the number of involved players that compete for scarce resources,
• Let $X \in \mathcal{R}^m$ be the set of feasible resource allocations among players

• Let $U$ be the set of utilities achieved by each allocation: $U = {u \in \mathcal{R}^n

  \exists x \in X: f_i(x) = u_j, \forall j = 1, …, n} $

The utilitarian solution, $\hat{U}$, is the one that maximizes the sum of the individual utilities of the players, i.e., the solution that maximizes the aggregate performance. The utilitarian solution entails a complete system efficiency, but may not be fair for some of the players.

Regarding fairness, we can formally define $\mathcal{F}(U)$ as the resulting utility set that considers any fairness scheme to the resource allocation problem (instead of the pure measurement). The sum of fair utilities is bounded to the utilitarian function, so that fairness may generate an efficiency loss. Henceforth, the price of fairness, $\text{POF}(U; \mathcal{F})$, can be defined as the relative decrease in the fair utility with respect to the utilitarian solution: \begin{equation} \text{POF}(U; \mathcal{F}) = \frac{\hat{U} - \mathcal{F}(U)}{\hat{U}} \nonumber \end{equation}

Since the sum of fair utilities is bounded to the utilitarian function, the price of fairness is a number between 0 and 1. As one can imagine, a POF close to 0 is preferable because allows maximizing the system efficiency while being fair.

Fairness Measures

Throughout history, many fairness principles have been defined; from Aristotle’s principle of equity (which considers some pre-existing claims, or rights) to Rawlsian justice (give priority to the players with the least well-off to guarantee a minimum utility level). We also find the Nash standard of comparison, which is the percentage change in a player’s utility when he receives a small additional amount of the resources.

In addition to the aforementioned theories, there are a set axioms in the literature that a fairness scheme should ideally satisfy:

• AXIOM 1 (Pareto Optimality): a solution is Pareto optimal if there does not exist an allocation $u \in U$, such that $u \geq \mathcal{F}(U)$, with $u \neq \mathcal{F}(U)$.
• AXIOM 2 (Symmetry): a solution is symmetric if any permutation of the fair allocation grants the same result.
• AXIOM 3 (Affine Invariance): given an affine operator defined as $A(u_1, …, u_n) = (A_1(u_1), …, A_n(u_n))$, with $A_i(u) = c_i u + d_i$ and $c_i > 0$, a fair allocation under the affinely transformed system is equal to the affine transformation of the fair allocation under the original system.
• AXIOM 4 (Independence of Irrelevant Alternatives): if $U$ and $W$ are two utility sets such that $U \subset W$, and $\mathcal{F}(W) \in U$, then $\mathcal{F}(U) = \mathcal{F}(W)$.
• AXIOM 5 (Monotonicity): let $U$ and $W$ be two utility sets under which the maximum utility of player 1 is equal ($u_1^* = w_i^*$). If other players can obtain bigger or equal utilities in $W$ when player 1 demands more utility levels, then the fair allocation of consecutive players is given by $W$: $\mathcal{F}(U)_i \leq \mathcal{F}(W)_i$.

Pareto optimality ensures that there is no wastage. By symmetry, the central decision maker does not differentiate the players by their names. The affine invariance requirement means that the scheme is invariant to a choice of numeraire. According to the independence of irrelevant alternatives, preferring option A over option B is independent of other available options. Finally, by monotonicity, if for every utility level that player 1 may demand, the maximum utility level that player 2 can simultaneously derive is increased, then the utility level assigned to player 2 under the fair scheme should also be increased.

Jain’s Fairness Index

The Jain’s Fairness Index (JFI) was proposed in \cite{jain1984quantitative} to solve fairness issues in bandwidth allocation problems. The JFI is an scale independent measurement that grants a value between 0 and 1 \begin{equation} JFI = \frac{(\sum x_i)^2}{n \sum x_i^2} \nonumber \end{equation}

Proportional Fairness

The proportional fairness (PF) considers allocations that allow increasing the system efficiency while preserving fairness. This means that the PF ensures that the percentage increase of the utility of a given player is not higher than the percentage increase of other players. The PF is given by: \begin{equation} PF = \sum_{j=1}^n \log u_j \nonumber \end{equation} Proportional fairness has been very important in the networks field, especially after the paper of Kelly et al. (1997).

Max-Min Fairness

Max-Min Fairness (MMF) aims to maximize the minimum utility of all the players, which is based in the concept of Rawlsian justice. Henceforth, in order to accomplish the MMF requisite, it is required that the players enjoy the maximum possible utility level, which may be scaled (or normalized) for each player. An MMF solution accomplishes Axioms 1-3 and 5 (refer to Section “Fairness Measures”).

To apply MMF, the system must first maximize the lowest utility level among all the players. Then, once it is ensured that all the players enjoy that minimum, it must be attempted to maximize the utility in a second iteration, and so on. An MMF solution guarantees that any other allocation can only benefit the rich at the expense of the poor (in terms of utility). With that, suboptimal behaviors in which there is a substantial efficiency loss (e.g., situations in which utility maximization of a given player does not affect the others), are avoided.

An allocation $u^{\text{MMF}}$ is said to fulfill the MMF condition if it lexicographically maximizes $T(u)$ over $U$: \begin{equation} T(u^{\text{MMF}}) \succeq_{lex} T(u), \forall u \in U \nonumber \end{equation}

Given $a \in \boldsymbol{R}^n$ and $b \in \boldsymbol{R}^n$, $a$ is lexicographically larger than $b$, i.e., $a \succeq_{lex} b$ , if there exists an index $k \leq n$, such that $a_i = b_i, \forall i < k$, and $a_k > b_k$ or $a = b$. Several algorithms for efficiently computing an MMF can be found in the literature \cite{ogryczak2005telecommunications}, which involve a sequential optimization procedure for utility levels identification. Since the MMF scheme deals with scaled utilities, the following property is hold: \begin{equation} \mathcal{F}^{\text{MMF}} (\sum U) = \sum \mathcal{F}^{\text{MMF}} (U) \nonumber \end{equation}

MMF has been previously applied to routing, load balancing and other resource allocation problems \cite{bertsekas1987data, bonald2001impact, luss1999equitable}. However, in \cite{radunovic2004rate} it is shown that MMF results in severe inefficiency for wireless networks in a limiting regime.

The Cost of Fairness

The cost of fairness can be defined as the performance loss incurred on the utilitarian function that maximizes the sum of utilities of individual players. By applying fairness under PF or MMF, the upper bounds of the price of fairness may vary according to the utilities distribution. Thus, in the following subsections we provide such upper bounds for equal and unequal maximum achievable utilities.

Equal Maximum Achievable Utilities

In case that the maximum achievable utilities of players are equal, the upper bound for the price of fairness is given by the following theorem. \begin{theorem} Let $n$ be the number of players, with $n \geq 2$, and let the utility set $U$ be compact and convex (follow a continuous and bounded function). Then, if all players have equal maximum achievable utilities, which are greater than 0, \begin{itemize} \item The price of PF is bounded by [POF(U, \mathcal{F}^{\text{PF}}) \leq 1 - \frac{2 \sqrt{n}-1}{n}] \item The price of MMF is bounded by [POF(U, \mathcal{F}^{\text{MMF}}) \leq 1 - \frac{4n}{(n+1)^2}] \end{itemize} \end{theorem}

With that, we see that the price of PF is smaller than the price of MMF, especially when the number of players is large.

Unequal Maximum Achievable Utilities

Now, we focus on scenarios in which the maximum achievable utilities of players are not equal.

Let $n$ be the number of players, with $n \geq 2$, and let the utility set $U$ be compact and convex. Then, if all players have equal maximum achievable utilities, which are greater than 0, \begin{itemize} \item The price of PF is bounded by [POF(U, \mathcal{F}^{\text{PF}}) \leq 1 - \frac{2 \sqrt{n}-1}{n} \frac{\min_{j \in {1,…,n} u_j^}}{\max_{j \in {1,…,n} u_j^}} - \frac{1}{n} + \frac{\min_{j \in {1,…,n} u_j^}}{\sum_{j=1}^n u_j^}] \item The price of MMF is bounded by [POF(U, \mathcal{F}^{\text{MMF}}) \leq 1 - \frac{4n}{(n+1)^2} \frac{1/n \sum_{j=1}^n u_j^}{\max_{j \in {1,…,n} u_j^}}] \end{itemize}

Fairness and Wireless Networks

In WNs, the fact of sharing the channel entails an adversarial setting in which devices compete for the available resources. One can equally distribute both frequency and time resources among the overlapping devices to achieve fairness, but several other factors must be taken into consideration. Traffic load and Quality of Service (QoS) are the most obvious examples.

To be completed…