Jump to content

Proportional-fair rule

From Wikipedia, the free encyclopedia

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

[edit]

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

[edit]

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

[edit]

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

[edit]

Proportional fairness has been studied in various settings.

References

[edit]
  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. ^ a b c 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.