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

Цена справедливости (англ. Price of fairness, POF) в задачах справедливого дележа — это отношение максимального экономического блага, полученного после дележа, к максимальному экономическому благу, полученному при условии справедливости дележа. POF является количественной мерой потери блага, которую общество должно заплатить, чтобы гарантировать справедливость.

В общем случае POF определяется следующей формулой:

$POF={\frac {\max _{D\in Divisions}{(welfare(D))}}{\max _{D\in FairDivisions}{(welfare(D))}}}$

Здесь welfare(D) = благо при дележе D, Divisons = множество всех дележей, FairDivisions = множество справедливых дележей.

Точная цена варьируются сильно в зависимости от вида дележа, вида справедливости и вида общественного блага, которые мы рассматриваем.

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

Численный пример

В этом примере мы фокусируемся на утилитарной цене пропорциональности (англ. utilitarian price of proportionality, UPOP).

Рассмотрим неоднородную земельную собственность, которую следует разделить среди 100 участников, каждый из которых оценивает всю землю в 100 единиц (или в значение, нормализованное к 100). Рассмотрим сначала некоторые экстремальные случаи.

• Максимально возможное утилитарное благо равно 10000. Это значение достижимо лишь в крайне редких случаях, когда все участники хотят получить различные участки земли.
• При пропорциональном дележе каждый участник получает значение по меньшей мере 1, так что утилитарное благо не будет меньше 100.

Верхняя граница

Описанные выше экстремальные случаи уже дают тривиальную верхнюю границу: $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 равно ${\tfrac {1000}{190}}\cong 5,26$. Таким образом, 5,26 является нижней границей в худшем случае UPOP (где «худший случай» выбирается среди всех возможных комбинаций оценочных мер).

Комбинируя

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

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

Справедливое разрезание с кусками общего вида

Утилитарная цена пропорциональности

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

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

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

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

Утилитарная цена зависти

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

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

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

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

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

Утилитарная цена беспристрастности

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

$UPOQ=\Theta (n)$

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

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

Назначение неделимых объектов

Для неделимых объектов распределение, удовлетворяющее пропорциональности, отсутствию зависти или беспристрастности, не всегда существует (в качестве простого примера представим двух участников дележа, пытающихся разделить один неделимый ценный объект). Следовательно, при вычислении цены справедливости не рассматриваются случаи, в которых никакой делёж не удовлетворяет выбранному понятию справедливости. Краткое суммирование результатов:

$UPOP=n-1+{\tfrac {1}{n}}$, для двух человек: 3/2.

$(3n+7)/9-O({\tfrac {1}{/}}{n})\leqslant UPOV\leqslant n-{\tfrac {1}{2}}$, для двух человек: 3/2

$UPOQ=\infty$, для двух человек: 2

Делёж делимых рутинных работ

Для задачи дележа торта, когда «торт» нежелателен (например, выкашивание лужайки), мы имеем следующие результаты:

$(n+1)^{\tfrac {2}{4n}}\leqslant UPOP\leqslant n$, для двух человек: 9/8

$(n+1)^{\tfrac {2}{4n}}\leqslant UPOV\leqslant \infty$, для двух человек: 9/8

$UPOQ=n$

Назначение неделимых рутинных работ

$UPOP=n$

$UPOV=\infty$

$UPOQ=\infty$

Разрезание торта на связные куски

Задача справедливого разрезания торта имеет вариации, когда выделяемые куски должны быть связными (едиными, не состоять из разделённых частей). В этом случае и числитель, и знаменатель в формуле POF меньше (ввиду взятия максимума на меньшем множестве), так что априори не ясно, будет POF меньше или больше, чем в случае несвязности.

Утилитарная цена справедливости

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

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

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

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

$EPOQ=\Theta (''n'')$

Эгалитарная цена справедливости

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

$EPOP=1$

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

$EPOQ=1$

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

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

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

Цена максимизации блага

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

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

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

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

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

Назначение неделимых объектов связными частями

Как и в случае разрезания торта для назначения неделимых объектов есть вариации, в которых объекты лежат на линии и каждый выделяемый кусок должен представлять собой отрезок. Краткое суммирование результатов:

$UPOP=n-1+{\tfrac {1}{n}}$

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

$UPOQ=\infty$; для двух человек: 3/2

$EPOP=1$

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

$EPOQ=\infty$; для двух человек: 1

Распределения обязанностей со связными кусками

Краткое суммирование результатов:

${\tfrac {n}{2}}\leqslant UPOP\leqslant n$

$UPOV=\infty$

$UPOQ=n$

$EPOP=1$

$EPOV=\infty$

$EPOQ=1$

Другие результаты

Цена справедливости изучалась также в контексте распределения ресурсов.

См. также

• Экономическая эффективность
• Цена анархии