Price of fairness

The POF is a quantitative measure of the loss of welfare that society has to take in order to guarantee fairness.

Another type is egalitarian social welfare, defined as the minimum (normalized) utility per agent.

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

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

Assume that we have an efficient division of a land-estate to 100 partners, with a utilitarian welfare U.

[1] 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).

A brief summary of the results:[1] For the problem of cake-cutting when the "cake" is undesirable (e.g. lawn-mowing), we have the following results:[1] The problem of fair cake-cutting has a variation in which the pieces must be connected.

We have the following results for utilitarian welfare:[2] In a proportional division, the value of each partner is at least 1/n of the total.

Hence, the egalitarian price of proportionality (EPOP) is 1: Similar considerations apply to the egalitarian price of equitability (EPOQ): The egalitarian price of envy-freeness is much larger:[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.

We get the following results:[2] 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.

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

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