Price of fairness

In the theory of fair division, the price of fairness (POF) is the ratio of the largest economic welfare attainable by a division to the economic welfare attained by a fair division. The POF is a quantitative measure of the loss of welfare that society has to take in order to guarantee fairness.

In general, the POF is defined by the following formula:

The exact price varies greatly based on the kind of division, the kind of fairness and the kind of social welfare we are interested in.

The most well-studied type of social welfare is utilitarian social welfare, defined as the sum of the (normalized) utilities of all agents. Another type is egalitarian social welfare, defined as the minimum (normalized) utility per agent.

Numeric example

In this example we focus on the utilitarian price of proportionality, or UPOP.

Consider a heterogeneous land-estate that has to be divided among 100 partners, all of whom value it as 100 (or the value is normalized to 100). First, let's look at some extreme cases.

  • The maximum possible utilitarian welfare is 10000. This welfare is attainable only in the very rare case where each partner wants a different part of the land.
  • In a proportional division, each partner receives a value of at least 1, so the utilitarian welfare is at least 100.

Upper bound

The extreme cases described above already give us a trivial upper bound: UPOP ≤ 10000/100 = 100. But we can get a tighter upper bound.

Assume that we have an efficient division of a land-estate to 100 partners, with a utilitarian welfare U. We want to convert it to a proportional division. To do this, we group the partners according to their current value:

  • Partners whose current value is at least 10 are called fortunate .
  • The other partners are called unfortunate.

There are two cases:

  • If there are less than 10 fortunate partners, then just discard the current division and make a new proportional division (e.g. using the last diminisher protocol). In a proportional division, every partner receives a value of at least 1, so the total value is at least 100. The value of the original division is less than (10*100+90*10)=1900, so the UPOP is at most 19.
  • If there are at least 10 fortunate partners, then create a proportional division using the following variant of the last diminisher protocol:
    • Each fortunate partner in turn cuts 0.1 of his share and lets the other unfortunate partners diminish it. Either he or one of the unfortunate partners receives this share.
    • This goes on until each of the (at most) 90 unfortunate partner has a share. Now each of the (at least) 10 fortunate partners has at least 0.1 of his previous value, and each of the unfortunate partners has at least his previous value, so the UPOP is at most 10.

To summarize: the UPOP is always less than 20, regardless of the value measures of the partners.

Lower bound

The UPOP can be as low as 1. For example, if all partners have the same value measure, then in any division, regardless of fairness, the utilitarian welfare is 100. Hence, UPOP=100/100=1.

However, we are interested on a worst-case UPOP, i.e., a combination of value measures in which the UPOP is large. Here is such an example.

Assume there are two types of partners:

  • 90 uniform partners who value the entire land uniformly (i.e. the value of a piece is proportional to its size).
  • 10 focused partners, each of whom values only a single district that covers 0.1 of the land.

Consider the two following partitions:

  • Fair division: Divide the land uniformly, giving each partner 0.01 of the land, where the focused partners each receive their 0.01 in their desired district. This division is fair. The value of each uniform partner is 1, while the value of each focused partner is 10, so the utilitarian welfare is 190.
  • Efficient division: Divide the entire land to the focused partners, giving each partner his entire desired district. The utilitarian welfare is 100*10=1000.

In this example, the UPOP is 1000/190=5.26. Thus 5.26 is a lower bound on the worst-case UPOP (where the "worst-case" is taken over all possible combinations of value measures).

Combined

Combining all the results, we get that the worst-case UPOP is bounded between 5 and 20.

This example is typical of the arguments used to bound the POF. To prove a lower bound, it is sufficient to describe a single example; to prove an upper bound, an algorithm or another sophisticated argument should be presented.

Cake-cutting with general pieces

Utilitarian price of proportionality

The numeric example described above can be generalized from 100 to n partners, giving the following bounds for the worst-case UPOP:

√n/2 ≤ UPOP ≤ 2√n-1
UPOP = Θ(√n)

For two partners, a more detailed calculation gives a bound of: 8-4*√3 ≅ 1.07.[1]

Utilitarian price of envy

When the entire cake is divided, an envy-free division is always proportional. Hence the lower bound on the worst-case UPOP (√n/2) applies here too. On the other hand, as an upper bound we only have a weak bound of n-1/2.[1] Hence:

√n/2 ≤ UPOV ≤ n-1/2
Ω(√n) ≤ UPOV ≤ O(n)

For two partners, a more detailed calculation gives a bound of: 8-4*√3 ≅ 1.07.[1]

Utilitarian price of equitability

For two partners, a more detailed calculation gives a bound of: 9/8=1.125.[1]

Indivisible goods allocation

For indivisible items, an assignment satisfying proportionality, envy-freeness, or equitability does not always exist (for a simple example, imagine two partners trying to divide a single valuable item). See also fair item allocation. Consequently, in the price of fairness calculations, the instances in which no assignment satisfies the relevant fairness notion are not considered. A brief summary of the results:[1]

UPOP = n - 1 + 1/n; for two people: 3/2.
(3n+7)/9-O(1/n) ≤ UPOV ≤ n-1/2; for two people: 3/2
UPOQ=Infinity; for two people: 2

Chore-cutting with general pieces

For the problem of cake-cutting when the "cake" is undesirable (e.g. lawn-mowing), we have the following results:[1]

(n+1)^2/4n ≤ UPOP ≤ n; for two people: 9/8
(n+1)^2/4n ≤ UPOV ≤ infinity; for two people: 9/8
UPOQ=n

Indivisible bads allocation
UPOP = n
UPOV = infinity
UPOQ = infinity

Cake-cutting with connected pieces

The problem of fair cake-cutting has a variation in which the pieces must be connected. In this variation, both the nominator and the denominator in the POF formula are smaller (since the maximum is taken over a smaller set), so a priori it is not clear whether the POF should be smaller or larger than in the disconnected case.

Utilitarian price of fairness

We have the following results for utilitarian welfare:[2]

UPOP = Θ(√n)
UPOV = Θ(√n)
n-1+1/n ≤ EPOQ ≤ n
EPOQ = Θ(n)

Egalitarian price of fairness

In a proportional division, the value of each partner is at least 1/n of the total. In particular, the value of the least fortunate agent (which is called the egalitarian welfare of the division) is at least 1/n. This means that in an egalitarian-optimal division, the egalitarian welfare is at least 1/n, and so an egalitarian-optimal division is always proportional. Hence, the egalitarian price of proportionality (EPOP) is 1:

EPOP = 1

Similar considerations apply to the egalitarian price of equitability (EPOQ):

EPOQ = 1

The egalitarian price of envy-freeness is much larger:[2]

EPOV = n/2

This is an interesting result, as it implies that insistence on the criterion of envy-freeness increases the social gaps and harms the most unfortunate citizens. The criterion of proportionality is much less harmful.

Price of welfare-maximization

Instead of calculating the loss of welfare due to fairness, we can calculate the loss of fairness due to welfare optimization. We get the following results:[2]

proportional-price-of-egalitarianism = 1
envy-price-of-egalitarianism = n-1
proportional-price-of-utilitarianism = infinity
envy-price-of-egalitarianism = infinity

Indivisible goods allocation with connected blocks

As in cake-cutting, for indivisible item assignment there is a variation where the items lie on a line and each assigned piece must form a block on the line. A brief summary of the results:[3]

UPOP = n - 1 + 1/n
UPOV = Θ(√n)
UPOQ = infinity; for two people: 3/2
EPOP = 1
EPOV = n/2
EPOQ = infinity; for two people: 1

Chore-cutting with connected pieces

A brief summary of the results:[4]

n/2 ≤ UPOP ≤ n
UPOV = infinity
UPOQ = n
EPOP = 1
EPOV = infinity
EPOQ = 1

Homogeneous resource allocation

The price of fairness has also been studied in the contest of the allocation of homogeneous divisible resources, such as oil or woods. Known results are:[5][6]

UPOV = UPOP = Θ(√n)

This is because the rule of competitive equilibrium from equal incomes yields an envy-free allocation, and its utilitarian price is O(√n).

Other contexts

The price-of-fairness has been studied in the context of the fair subset sum problem.

The price of justified representation is the loss in the average satisfaction due to the requirement to have a justified representation in an approval voting setting.[7]

See also

References
  1. Caragiannis, I.; Kaklamanis, C.; Kanellopoulos, P.; Kyropoulou, M. (2011). "The Efficiency of Fair Division". Theory of Computing Systems. 50 (4): 589. CiteSeerX 10.1.1.475.9976. doi:10.1007/s00224-011-9359-y. S2CID 8755258.
  2. Aumann, Y.; Dombb, Y. (2010). "The Efficiency of Fair Division with Connected Pieces". Internet and Network Economics. Lecture Notes in Computer Science. Vol. 6484. pp. 26. CiteSeerX 10.1.1.391.9546. doi:10.1007/978-3-642-17572-5_3. ISBN 978-3-642-17571-8.
  3. Suksompong, W. (2019). "Fairly Allocating Contiguous Blocks of Indivisible Items". Discrete Applied Mathematics. 260: 227–236. arXiv:1707.00345. doi:10.1016/j.dam.2019.01.036. S2CID 126658778.
  4. Heydrich, S.; van Stee, R. (2015). "Dividing Connected Chores Fairly". Theoretical Computer Science. 593: 51–61. doi:10.1016/j.tcs.2015.05.041.
  5. Bertsimas, D.; Farias, V. F.; Trichakis, N. (2011). "The Price of Fairness". Operations Research. 59: 17–31. doi:10.1287/opre.1100.0865. hdl:1721.1/69093.
  6. Bertsimas, D.; Farias, V. F.; Trichakis, N. (2012). "On the Efficiency-Fairness Trade-off". Management Science. 58 (12): 2234. CiteSeerX 10.1.1.380.1461. doi:10.1287/mnsc.1120.1549.
  7. Elkind, Edith; Faliszewski, Piotr; Igarashi, Ayumi; Manurangsi, Pasin; Schmidt-Kraepelin, Ulrike; Suksompong, Warut (2021-12-13). "The Price of Justified Representation". arXiv:2112.05994 [cs.GT].
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.