Proportional-fair rule

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.

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).

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]

Proportional fairness has been studied in various settings.

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