Proportional-fair rule explained
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
be a set of possible `states of the world' or `alternatives'. Society wishes to choose a single state from
. For example, in a
single-winner election,
may represent the set of candidates; in a
resource allocation setting,
may represent all possible allocations of the resource.
Let
be a finite set, representing a collection of individuals. For each
, let
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
to select some element(s) from
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
such that, for every other state
:Note that the term inside the sum,
, 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
that maximizes the
sum of individual utilities, that is, for every other state
: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
that maximizes the
smallest individual utilities, that is, for every other state
: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.
The PF rule in specific settings
Proportional fairness has been studied in various settings.
Notes and References
- 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. 10.1057/palgrave.jors.2600523. 2876114 . 0160-5682.
- 2017-03-16. Price of Fairness for allocating a bounded resource. European Journal of Operational Research. en. 257. 3. 933–943. 10.1016/j.ejor.2016.08.013. 0377-2217. 1508.05253. Nicosia . Gaia . Pacifici . Andrea . Pferschy . Ulrich . 14229329 .
- Bertsimas. Dimitris. Farias. Vivek F.. Trichakis. Nikolaos. 2011-02-01. The Price of Fairness. Operations Research. 59. 1. 17–31. 10.1287/opre.1100.0865. 0030-364X. 1721.1/69093. free.
- 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. en. 53. 1. 65–84. 10.1007/s11134-006-7587-7. 1207054 . 1572-9443.
