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

В теории справедливого дележа цена справедливости (POF) — это отношение наибольшего экономического благосостояния, достижимого при разделе, к экономическому благосостоянию, достигнутому при справедливом разделе. POF – это количественная мера потери благосостояния, которую общество должно принять, чтобы гарантировать справедливость.

В общем случае POF определяется по следующей формуле: $$POF={\frac {\max _{D\in {\text{Divisions}}}{(\mathrm {welfare} (D))}}{\max _{D\in {\text{Fair Divisions}}}{(\mathrm {welfare} (D))}}}$$

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

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

Числовой пример

В этом примере мы фокусируемся на утилитарной цене пропорциональности , или УПОП.

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

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

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

Описанные выше крайние случаи уже дают нам тривиальную верхнюю оценку: UPOP ≤ 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.

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

Комбинированный

Объединив все результаты, мы получаем, что UPOP в худшем случае ограничен диапазоном от 5 до 20.

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

Разрезание торта общими кусочками

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

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

√ n /2 ≤ УПОП ≤ 2√ n -1

УПОП = Θ(√ n )

Для двух партнеров более детальный расчет дает оценку: 8-4*√3 ≅ 1,07.

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

Когда весь торт разделен, деление без зависти всегда пропорционально. Следовательно, и здесь применима нижняя граница UPOP для наихудшего случая (√ n /2). С другой стороны, в качестве верхней границы у нас есть только слабая граница n -1/2. Следовательно:

√ n /2 ≤ УПОВ ≤ n -1/2

Ω(√ n ) ≤ UPOV ≤ O( n )

Для двух партнеров более детальный расчет дает оценку: 8-4*√3 ≅ 1,07.

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

${(n+1)^{2} \over 4n}\leq UPOQ\leq n$

$UPOQ=\Theta (n)$

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

Распределение неделимых товаров

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

УПОП = n - 1 + 1/ n ; на двоих: 3/2.

(3 n +7)/9-О(1/ n ) ≤ УПОВ ≤ n -1/2; на двоих: 3/2

UPOQ=Бесконечность; на двоих: 2

Разделение рутинных дел с помощью общих частей

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

( n +1)^2/4 n ≤ UPOP ≤ n ; на двоих: 9/8

(n+1)^2/4n ≤ УПОВ ≤ бесконечность; на двоих: 9/8

УПОК= н

Неделимое распределение бэдов

УПОП = н

UPOV = infinity

UPOQ = бесконечность

Вырезка торта соединенными кусочками

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

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

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

УПОП = Θ(√ n )

UPOV = Θ(√ n )

n -1+1/ n ≤ EPOQ ≤ n

EPOQ = Θ( п )

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

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

ЕПОП = 1

Аналогичные соображения применимы и к эгалитарной цене справедливости (EPOQ):

ЭПОК = 1

Эгалитарная цена свободы от зависти гораздо выше:

ЭПОВ = n /2

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

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

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

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

зависть-цена-эгалитаризма = n -1

пропорциональная цена утилитаризма = бесконечность

зависть-цена-эгалитаризма = бесконечность

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

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

УПОП = n - 1 + 1/ n

UPOV = Θ(√ n )

UPOQ = бесконечность; на двоих: 3/2

ЕПОП = 1

ЭПОВ = n /2

EPOQ = бесконечность; на двоих: 1

Выкройка с соединенными деталями

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

n /2 ≤ УПОП ≤ n

UPOV = infinity

УПОК = п

ЕПОП = 1

ЭПОВ = бесконечность

ЭПОК = 1

Равномерное распределение ресурсов

Цена справедливости также изучалась в борьбе за распределение однородных и делимых ресурсов, таких как нефть или лес. Известные результаты:

УПОВ = УПОП = Θ(√ n )

Это происходит потому, что правило конкурентного равновесия, основанное на равных доходах, приводит к распределению без зависти, а его утилитарная цена равна O(√ n ).

Другие контексты

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

Цена обоснованного представительства — это потеря среднего удовлетворения из-за требования иметь обоснованное представительство при голосовании за одобрение .

См. также

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