Proportional-fair rule

For the resource allocation problem, see Proportional division.

In operations research and social choice, the proportional-fair (PF) rule is a rule saying that, among all possible alternatives, one should pick an alternative that cannot be improved, where "improvement" is measured by the sum of relative improvements possible for each individual agent. It aims to provide a compromise between the utilitarian rule - which emphasizes overall system efficiency, and the egalitarian rule - which emphasizes individual fairness.

The rule was first presented in the context of rate control in communication networks. ^[1] However, it is a general social choice rule and can also be used, for example, in resource allocation. ^[2]

Definition

Let ${\displaystyle X}$ be a set of possible `states of the world' or `alternatives'. Society wishes to choose a single state from ${\displaystyle X}$. For example, in a single-winner election, ${\displaystyle X}$ may represent the set of candidates; in a resource allocation setting, ${\displaystyle X}$ may represent all possible allocations of the resource.

Let ${\displaystyle I}$ be a finite set, representing a collection of individuals. For each ${\displaystyle i\in I}$, let ${\displaystyle u_{i}:X\longrightarrow \mathbb {R} }$ be a utility function , describing the amount of happiness an individual i derives from each possible state.

A social choice rule is a mechanism which uses the data ${\displaystyle (u_{i})_{i\in I}}$ to select some element(s) from ${\displaystyle X}$ which are `best' for society. The question of what 'best' means is the basic question of social choice theory. The proportional-fair rule selects an element ${\displaystyle x\in X}$ such that, for every other state ${\displaystyle y\in X}$:

${\displaystyle 0\geq \sum _{i\in I}{\frac {u_{i}(y)-u_{i}(x)}{u_{i}(x)}}.}$

Note that the term inside the sum, ${\displaystyle {\frac {u_{i}(y)-u_{i}(x)}{u_{i}(x)}}}$, represents the relative gain of agent i when switching from x to y. The PF rule prefers a state x over a state y, if and only if If the sum of relative gains when switching from x to y is not positive.

Comparison to other rules

The utilitarian rule selects an element ${\displaystyle x\in X}$ that maximizes the sum of individual utilities, that is, for every other state ${\displaystyle y\in X}$:

${\displaystyle 0\geq \sum _{i\in I}\left(u_{i}(y)-u_{i}(x)\right).}$

That rule ignores the current utility of the individuals. In particular, it might select a state in which the utilities of some individuals is zero, if the utilities of some other individuals is sufficiently large. The egalitarian rule selects an element ${\displaystyle x\in X}$ that maximizes the smallest individual utilities, that is, for every other state ${\displaystyle y\in X}$:

${\displaystyle 0\geq \min _{i\in I}u_{i}(y)-\min _{i\in I}u_{i}(x).}$

This rule ignores the total efficiency of the system. In particular, it might select a state in which the utilities of most individuals are very low, just to make the smallest utility slightly larger.

The proportional-fair rule aims to balance between these two extremes. On one hand, it considers a sum of utilities rather than just the smaller utility; on the other hand, inside the sum, it gives more weight to agents whose current utility is smaller. In particular, if the utility of some individual in x is 0, and there is another state y in which his utility is larger than 0, then the PF rule would prefer state y, as the relative improvement of individual y is infinite (it is divided by 0).

Properties

When the utility sets are convex, a proportional-fair solution always exists. Moreover, it maximizes the product of utilities (also known as the Nash welfare). ^[3]

When the utility sets are not convex, a proportional-fair solution is not guaranteed to exist. However, when it exists, it still maximizes the product of utilities. ^[2]

The PF rule in specific settings

Proportional fairness has been studied in various settings.

• Network scheduling; see proportional-fair scheduling. ^[4]
• The fair subset sum problem. ^[2]
• Queueing. ^[5]

References

1. Kelly, F P; Maulloo, A K; Tan, D K H (1998-03-01). "Rate control for communication networks: shadow prices, proportional fairness and stability". Journal of the Operational Research Society. 49 (3): 237–252. doi:10.1057/palgrave.jors.2600523. ISSN   0160-5682. S2CID   2876114.
2. Nicosia, Gaia; Pacifici, Andrea; Pferschy, Ulrich (2017-03-16). "Price of Fairness for allocating a bounded resource". European Journal of Operational Research. 257 (3): 933–943. arXiv: 1508.05253 . doi:10.1016/j.ejor.2016.08.013. ISSN   0377-2217. S2CID   14229329.
3. Bertsimas, Dimitris; Farias, Vivek F.; Trichakis, Nikolaos (2011-02-01). "The Price of Fairness". Operations Research. 59 (1): 17–31. doi:10.1287/opre.1100.0865. hdl: 1721.1/69093 . ISSN   0030-364X.
4. Kushner, H. J.; Whiting, P.A. (July 2004), "Convergence of proportional-fair sharing algorithms under general conditions", IEEE Transactions on Wireless Communications, 3 (4): 1250–1259, CiteSeerX   10.1.1.8.6408 , doi:10.1109/TWC.2004.830826, S2CID   6780351.
5. Bonald, T.; Massoulié, L.; Proutière, A.; Virtamo, J. (2006-06-01). "A queueing analysis of max-min fairness, proportional fairness and balanced fairness". Queueing Systems. 53 (1): 65–84. doi:10.1007/s11134-006-7587-7. ISSN   1572-9443. S2CID   1207054.