---
tags: HSNL, NCKU
---

# Fairness
contributed by <`RusselCK` >

###### tags: `RusselCK`
- [ ] [Fairness in Wireless Networks:Issues, Measures and Challenges](https://ieeexplore.ieee.org/document/6517050)
- [ ] [Fair end-to-end window-based congestion control](https://ieeexplore.ieee.org/document/879343)
- [ ] [Cross-layer optimization for OFDM wireless networks-part I: Theoretical framework](https://ieeexplore.ieee.org/document/1413227)
- [ ] [Multi-resource allocation is measured by proportional fairness](http://www.statslab.cam.ac.uk/~frank/elastic.pdf)
- [ ] [Rate control for communication networks: shadow prices, proportional fairness and stability](http://www.statslab.cam.ac.uk/~frank/rate.pdf) [18]
- [ ] [Charging and rate control for elastic traffic](http://www.statslab.cam.ac.uk/~frank/elastic.pdf) [17]
## Introduction
發生 unfairness ，該如何解決?
1. 在本輪補償 上一輪的弱勢
2. 重新分配資源，不進行補償

假設:
* 只有一種 Resource 要分配，且總量為 $C$
* 分給 $n$ 個人(individual)，每個人拿 $x_i$

$X = (x_1, x_2,...,x_n)$ : 資源分配

:::info
* $X$ is **feasible**
$\Leftrightarrow$ 每個人一次只能分配一定數量的資源
>A feasible allocation indicates that every individual can only be allocated a certain amount of resource once

$\Leftrightarrow$ $x_i \geq 0$ and $\sum_{i=1}^nx_i \leq C$
:::

範例用圖: ( Resource : network capacity )

## Qualitative Fairness Measures
* 無法以 實數 來表示 measurement of fairness
* 可以評斷 allocation 是否達到 fairness
* 可以 give guidance for resource allocation
>Qualitative fairness measures are not able to provide a measurement of fairness with a real number representation
however, they can judge whether the allocations achieve fairness and give guidance for resource allocation

### Max-min Fairness
:::info
* A feasible $X$ is **max-min fair**
$\Leftrightarrow$ $\forall i,$ $x_i$ cannot be increased (while maintaining the feasibility) without decreasing $x_j$, where $x_j⩽x_i,(i≠j)$
:::
在 feasible $X$ 中，對所有 $i$ 來說
若 無法在 **不減少 $x_j$** 的情況下來 **增加 $x_i$**，$x_j⩽x_i,(i≠j)$，則 $X$ 為 max-min fair
>A system reaches max-min fairness, if it cannot increase any individual's resource without decreasing another individual's resource allocation which is already less than the previous ones

:::warning
* 不論 $x_i$ 多大，都不會增加
* 不論 $x_j$ 多小，都能得到補償
:::

對所有 $x_i$ 來說，都只能透過 減少比自己大的人 來 增加自己
也就是說，==大家分配到的會一樣多==

#### 舉例
* 若 $X$ = (A,B,C,D,E) = (10%,20%,30%,30%,10%)，則 $X$ 不為 max-min fair
* A 可以透過減少 B 來 增加自己，且 B > A
* 若 $X$ = (A,B,C,D,E) = (20%,20%,20%,20%,20%)，則 $X$ 為 max-min fair
* 沒有一個人可以增加其容量而不降低其他比自己多的節點的容量
> none of the nodes can increase its capacity without decreasing the capacity of other nodes which is no more than its own capacity.

### Proportional Fairness
Multi-resource allocation is measured by proportional fairness
( 這裡只寫 1 resource 的 定義 )
:::info
* A feasible $X$ is **proportionally-fair**
$\Leftrightarrow$ For any other allocation $x^∗_i$ , the sum of differences between $x^∗_i$ and $x_i$ (proportional changes) is zero or negative .
That is, $X^* = (x_1^*, x_2^*,...,x_n^*)$: any other allocation,
$$
\sum_{i=1}^{n} \frac{x^∗_i - x_i}{x_i} \leq 0
$$
:::
:::warning
* $\sum_{i=1}^{n} \frac{x^∗_i - x_i}{x_i} \leq 0$ is equivalent to $max (\sum_{i=1}^{n}logx_i)$


> A convex increasing function
> $f(x)=log(x) \rightarrow −∞ \space as \space x \rightarrow 0$
> $f'(x)=log(x) \rightarrow ∞ \space as \space x \rightarrow 0$


- [ ] [Time scale analysis and scalability issues for explicit rate allocation in ATM networks](https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=532866)
- [ ] [Integration of pricing and flow control for available bit rate services in ATM networks](https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=594441)
:::
* An equal allocation (i.e., $x_i=x_k,∀i,k$, where $i≠k$) achieves proportional fairness

> Proportional fairness is robust and can achieve a better trade-off between utilities than maxmin fairness when particular utility-metrics are used in rate allocation in ad hoc networks

- [ ] [Rate control for communication networks: shadow prices, proportional fairness and stability](http://www.statslab.cam.ac.uk/~frank/rate.pdf)
- [ ] [Nash bargaining solution](https://en.wikipedia.org/wiki/Bargaining_problem#Nash_bargaining_solution)
### (p,α)-proportional Fairness
A generalized form of proportional fairness
:::info
* $p$ : weight of indivisual
* $\alpha$ : a positive number
* A feasible $X$ is **(p,α)-proportionally-fair**
$\Leftrightarrow$ For any other allocation ,$X^* = (x_1^*, x_2^*,...,x_n^*)$,
$$
\sum_{i=1}^{n} p \frac{x^∗_i - x_i}{(x_i)^α} \leq 0
$$
:::
* $p$ provides flexibility and controllability during allocation
* $p$ helps in tuning the allocation based on other parameters such as cost

### An optimization problem
:::warning
* $X$ is **(p,α)-proportionally-fair**
$\Leftrightarrow$ $X$ reaches maximal utility $\sum_{i=1}^{n}p \cdot u_α(x_i)$,where
$$
u_α(x) =
\begin{cases}
logx & \text{ if } α= 1 \\
\frac{x^{(1-α)}}{(1-α)} & \text{ if } α \neq 1
\end{cases}
$$
:::
* when $α = 1$ ，(p,α)-proportional fairness reduces to **proportional fairness**
* when $α \rightarrow \infty$ ，(p,α)-proportional fairness converges to **max-min fairness**

#### 證明

- [ ] [拉格朗日乘數](https://zh.wikipedia.org/wiki/%E6%8B%89%E6%A0%BC%E6%9C%97%E6%97%A5%E4%B9%98%E6%95%B0)

The [**compactness**](https://en.wikipedia.org/wiki/Compact_space) and [**convexity**](https://en.wikipedia.org/wiki/Concave_function) of the feasible region for $X$ imply that such a vector exists, and is unique.

<iframe src="https://www.geogebra.org/calculator/j7rjxfeg?embed" width="800" height="600" allowfullscreen style="border: 1px solid #e4e4e4;border-radius: 4px;" frameborder="0"></iframe>


:::warning
【Lemma 3】
* If $h(x)$ is a **differentiable increasing concave negative function** when $x \geq 0$, the solution of $max \sum_{i}p_if_\alpha(x_i)$ with $f_\alpha = -(-h)^\alpha$ approaches the **max–min fair rate vector** as $\alpha \rightarrow \infty$.
:::

$\because$ $f_\alpha(x) = \frac{x^{(1-α)}}{(1-α)} = -(\frac{1}{α-1})(\frac{1}{x})^{α-1}$ satisfies the conditions of Lemma 3 with $h(x) = -(\frac{1}{x})$

$\therefore$ when $α \rightarrow \infty$ ，(p,α)-proportional fairness converges to **max-min fairness**