Цена справедливости

Описанные выше экстремальные случаи уже дают тривиальную верхнюю границу: ${\displaystyle UPOP\leqslant 10000/100=100}$. Однако мы можем дать более точную верхнюю границу.

Предположим, что мы имеем эффективное деление земельной собственности на 100 участников с утилитарным благом U. Мы хотим превратить его в пропорциональный делёж. Чтобы это сделать, группируем участников согласно их текущим значениям:

• Участников, у которых текущее значение не меньше 10, назовём счастливчиками.
• Остальных участников назовём неудачниками.

Имеется два случая:

• Если имеется менее 10 счастливчиков, просто отбрасываем имеющийся делёж и осуществляем новый пропорциональный делёж (например, с помощью протокола «последний уменьшивший»). При пропорциональном дележе каждый участник получает значение, не меньшее 1, так что общее значение будет не меньше 100. Значение исходного дележа было менее (10*100+90*10)=1900, так что UPOP не превосходит 19.
• Если имеется по меньшей мере 10 счастливчиков, то создаём пропорциональный делёж согласно следующему варианту протокола «последний уменьшивший»:
  • Каждый счастливчик выделяет 0,1 своей доли и позволяет одному из неудачников забрать эту выделенную часть.
  • Это продолжается, пока каждый из (но не более) 90 неудачников получат свои доли. Теперь каждый (по меньшей мере) из 10 счастливчиков имеет по меньшей мере 0,1 от своего начального значения, а каждый из неудачников имеет по меньшей мере своё предыдущее значение, так что UPOP не превосходит 10.

Суммируя, UPOP всегда меньше 20 независимо от оценочных мер участников.

UPOP может быть равна 1. Например, если все участники имеют одинаковые оценочные меры, то для любого дележа, независимо от понятия справедливости, утилитарное благо будет равно 100, а следовательно, UPOP=100/100=1.

Нам, однако, интересен наихудший случай UPOP, например, комбинация мер оценок, в которой UPOP велико. Ниже пример такого случая.

Представим, что имеется два типа партнёров:

• 90 безразличных партнёров, для которых значение всей земли однородно (например, когда значение куска земли пропорционально его размеру).
• 10 нацеленных партнёров, каждый из которых ценит только одну часть земли, которая составляет 0,1 всего участка.

Рассмотрим два следующих разбиения:

• Справедливый делёж: Разделим землю однородно, передав каждому участнику 0,01 земли и нацеленные партнёры получают их 0,01 от желаемого участка. Делёж справедливый, значение для каждого безразличного участника равно 1, в то время как значение каждого нацеленного участника равно 10, так что утилитарное благо равно 190.
• Эффективный делёж: Разделим всю землю среди нацеленных участников, отдав каждому из них весь желаемый участок. Утилитарное благо равно 100*10=1000.

В этом примере UPOP равно ${\displaystyle {\tfrac {1000}{190}}\cong 5,26}$. Таким образом, 5,26 является нижней границей в худшем случае UPOP (где «худший случай» выбирается среди всех возможных комбинаций оценочных мер).

Комбинируя все эти результаты, мы получим, что в худшем случае UPOP находится между 5 и 20.

Этот пример типичен для доводов о границах POF. Для доказательства нижней границы достаточно привести единственный пример, а для доказательства верхней границы необходимо предложить алгоритм или другой изощрённый аргумент.

Описанный выше числовой пример можно обобщить со 100 до n участников, что даёт следующие границы в худшем случае UPOP:

${\displaystyle {\tfrac {\sqrt {n}}{2}}\leqslant UPOP\leqslant 2{\sqrt {n}}-1}$

${\displaystyle UPOP=\Theta ({\sqrt {n}})}$

Для двух участников более детальные вычисления дают границу ${\displaystyle 8-4{\sqrt {3}}\cong 1,07}$[1].

Когда весь торт поделён, свободное от зависти разрезание всегда пропорционально. Следовательно, нижняя граница в худшем случае ${\displaystyle UPOP({\tfrac {\sqrt {n}}{2}})}$ здесь также применима. С другой стороны, сверху мы имеем лишь слабую границу ${\displaystyle n-{\tfrac {1}{2}}}$[1]. Следовательно,

${\displaystyle {\tfrac {\sqrt {n}}{2}}\leqslant UPOV\leqslant n-{\tfrac {1}{2}}}$

${\displaystyle \Omega ({\sqrt {n}})\leqslant UPOV\leqslant O(n)}$

Здесь UPOV означает англ. Utilitarian Price Of enVy, то есть утилитарную цену зависти.

Для двух участников более тщательные вычисления дают границу ${\displaystyle 8-4{\sqrt {3}}\cong 1,07}$[1].

${\displaystyle {\tfrac {(n+1)^{2}}{4n}}\leqslant UPOQ\leqslant n}$

${\displaystyle UPOQ=\Theta (n)}$

Здесь UPOQ означает англ. Utilitarian Price Of eQuitability, то есть Утилитарную цену беспристрастности.

Для двух участников более тщательные вычисления дают границу 9/8=1,125[1].

Имеются следующие результаты относитльно утилитарного блага[2]:

${\displaystyle UPOP=\Theta ({\sqrt {n}})}$

${\displaystyle UPOV=\Theta ({\sqrt {n}})}$

${\displaystyle n-1+{\tfrac {1}{n}}\leqslant EPOQ\leqslant n}$

${\displaystyle EPOQ=\Theta (''n'')}$

При пропорциональном дележе значение для каждого участника не меньше 1/n общей оценки ресурса. В частности, значение для наименее счастливого агента (которое называется эгалитарным благом дележа) не менее 1/n. Это означает, что в эгалитарно оптимальном дележе эгалитарное благо составляет величину, не меньшую 1/n, а потому эгалитарно оптимальный делёж всегда пропорционален. Следовательно, эгалитарная цена пропорциональности (англ. egalitarian price of proportionality, EPOP) равна 1:

${\displaystyle EPOP=1}$

Аналогичные доводы применимы к эгалитарной цене беспристрастности (англ. egalitarian price of equitability, EPOQ):

${\displaystyle EPOQ=1}$

Эгалитарная цена отсутствия зависти много больше[2]:

${\displaystyle EPOV={\tfrac {n}{2}}}$

Это интересный результат, поскольку из него следует, что обязательность критерия отсутствия зависти увеличивает социальные пропасти и вредит большинству жителей-неудачников. Критерий пропорциональности куда менее вреден.

Вместо вычисления потери блага для обеспечении справедливости мы можем вычислить потерю справедливости при оптимизации блага. Мы получаем следующие результаты[2]:

цена пропорциональности по эгалитаризму = 1

цена отсутствия зависти по эгалитаризму = n-1

цена пропорциональности по утилитарности ${\displaystyle =\infty }$

цена отсутствия зависти по утилитарности ${\displaystyle =\infty }$