Справедливое распределение элементов

редактировать

Справедливое распределение элементов - это своего рода проблема справедливого разделения, при которой элементы для разделения являются дискретными, а не непрерывными. Предметы должны быть разделены между несколькими партнерами, которые по-разному оценивают их, и каждый предмет должен быть отдан целиком одному человеку. Эта ситуация возникает в различных сценариях реальной жизни:

Несколько наследников хотят разделить унаследованное имущество, которое, например, содержит дом, машина, пианино и несколько картин.
Некоторые преподаватели хотят разделить курсы, проводимые на их факультете. Каждый лектор может вести один или несколько целых курсов.

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

Проблема распределения предметов имеет несколько составляющих:

Партнеры должны выразить свои предпочтения в отношении различных наборов предметов.
Группа должна выбрать критерий справедливости.
На основе предпочтений и критерия справедливости должен быть выполнен алгоритм справедливого назначения для вычисления справедливого разделения.

Эти компоненты подробно объясняются ниже.

Содержание

1 Предпочтения
- 1.1 Комбинаторные предпочтения
- 1.2 Аддитивные предпочтения
- 1.3 Компактные языки представления предпочтений
2 Критерии справедливости
- 2.1 Индивидуальные критерии гарантии
- 2.2 Глобальные критерии оптимизации
3 Алгоритмы присвоения
- 3.1 Справедливость по максимуму и минимуму
- 3.2 Пропорциональность
- 3.3 Честность минимум по максимуму
- 3.4 Свобода от зависти (без денег)
- 3.5 Свобода от зависти (с деньги)
- 3.6 Эгалитарно-оптимальные распределения
- 3.7 Оптимальные по Нэшу распределения
- 3.8 Последовательности выбора
4 Различные права
5 См. также
6 Ссылки

Предпочтения

Комбинаторные предпочтения

Наивный способ определить предпочтения - это попросить каждого партнера предоставить числовое значение для каждого возможного набора. Например, если разделяемые элементы - это автомобиль и велосипед, партнер может оценить автомобиль как 800, велосипед как 200, а связку {автомобиль, велосипед} как 900 (см. Вспомогательные функции для неделимых товаров для получения дополнительных примеров). У этого подхода есть две проблемы:

человеку может быть трудно вычислить точные числовые значения для пакетов.
Количество возможных пакетов может быть огромным: если есть $m { \ displaystyle m}$ $m$ элементов, тогда существует $2 m {\ displaystyle 2 ^ {m}}$ $2 ^ {m}$ возможных связок. Например, если имеется 16 элементов, каждый партнер должен будет представить свои предпочтения, используя 65536 чисел.

Первая проблема мотивирует использование порядковой полезности, а не кардинальной полезности. В порядковой модели каждый партнер должен выражать рейтинг только по $2 m {\ displaystyle 2 ^ {m}}$ $2 ^ {m}$ различных пакетах, т. Е. Сказать, какой набор лучший, а какой второй. -лучший и так далее. Это может быть проще, чем подсчет точных чисел, но все же сложно, если количество элементов велико.

Вторая проблема часто решается путем работы с отдельными предметами, а не с пакетами:

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

При подходящих предположениях можно поднять предпочтения по элементам до предпочтений по пакетам. Затем агенты сообщают свои оценки / рейтинги по отдельным элементам, и алгоритм вычисляет для них их оценки / рейтинги по пакетам.

Дополнительные предпочтения

Чтобы упростить задачу назначения позиций, принято считать, что все позиции являются независимыми товарами (поэтому они не являются заменяющими товарами ни дополнительные товары ). Затем:

В кардинальном подходе каждый агент имеет аддитивную функцию полезности (также называемую модульной функцией полезности). Как только агент сообщает значение для каждого отдельного элемента, легко вычислить значение каждого пакета, суммируя значения его элементов.
В порядковом подходе аддитивность позволяет нам вывести некоторые ранжирования между пакетами. Например, если человек предпочитает w вместо x, а не y, а не z, то он обязательно предпочитает {w, x} вместо {w, y} или {x, y} и {w, y} вместо {x}. Этот вывод является лишь частичным, например, мы не можем знать, предпочитает ли агент {w} вместо {x, y} или даже {w, z} вместо {x, y}.

Аддитивность подразумевает, что каждый партнер всегда может выбрать «предпочтительный предмет» из набора предметов на столе, и этот выбор не зависит от других предметов, которые может иметь партнер. Это свойство используется некоторыми алгоритмами справедливого присваивания, которые будут описаны ниже.

Компактные языки представления предпочтений

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

2-аддитивные предпочтения: каждый партнер сообщает значение для каждого пакета размером не более 2. Стоимость пакета рассчитывается путем суммирования значений для отдельных элементов в пакете и добавления значений пар. в комплекте. Обычно при наличии заменяющих элементов значения пар будут отрицательными, а при наличии дополнительных элементов значения пар будут положительными. Эту идею можно обобщить на k-аддитивные предпочтения для каждого положительного целого числа k.
Графические модели: для каждого партнера существует график, представляющий зависимости между различными элементами. В кардинальном подходе общим инструментом является сеть GAI (обобщенная аддитивная независимость). В порядковом подходе общим инструментом является сеть CP (условные предпочтения) и ее расширения: сеть TCP, сеть UCP, теория CP, сеть CI (условная важность) и сеть SCI (упрощение сети CI).
Языки на основе логики: каждый партнер описывает некоторые пакеты с помощью формулы логики первого порядка и может назначать значение для каждой формулы. Например, партнер может сказать: «Для (x или (y и z)) мое значение равно 5». Это означает, что агент имеет значение 5 для любого из наборов: x, xy, xz, yz, xyz.
Языки торгов: многие языки для представления комбинаторных предпочтений были изучены в контексте комбинаторные аукционы. Некоторые из этих языков могут быть адаптированы к настройке назначения элементов.

Критерии справедливости

Индивидуальные критерии гарантии

Индивидуальный критерий гарантии - это критерий, который должен соблюдаться для каждого отдельного партнера, пока поскольку партнер правдиво сообщает о своих предпочтениях. Ниже представлены пять таких критериев. Они упорядочены от самого слабого к самому сильному (при условии, что оценки аддитивны):

1. Максимальная доля : максимальная доля (также называемая: гарантия максимальной-минимальной-справедливой доли) агента является наиболее предпочтительным пакетом, который он может гарантировать себе как разделитель в разделяй и выбирай против враждебных противников. Распределение называется справедливым для MMS, если каждый агент получает пакет, который он слабо предпочитает своему MMS.

2. Пропорциональная справедливая доля (PFS) : пропорциональная справедливая доля агента составляет 1 / n его полезности от всего набора элементов. Распределение называется пропорциональным, если каждый агент получает пакет стоимостью не менее его пропорционально справедливой доли.

3. Минимальная-максимальная справедливая доля (mFS) : Минимальная-максимальная-справедливая-доля агента - это минимальная полезность, которую он может надеяться получить от распределения, если все другие агенты имеют те же предпочтения, что и ее, когда она всегда получает лучшую долю. Это также минимальная полезность, которую агент может точно получить в игре распределения «Кто-то режет, я выбираю первым». Распределение справедливо для mFS, если все агенты получают пакет, который они слабо предпочитают своей mFS. Справедливость mFS можно описать как результат следующего переговорного процесса. Предлагается определенное распределение. Каждый агент может возразить против этого, требуя, чтобы другой агент сделал другое распределение, позволяя ему выбирать первым. Следовательно, агент будет возражать против распределения, только если во всех разделах есть пакет, который он решительно предпочитает своему текущему пакету. Распределение является справедливым для mFS, если ни один агент не возражает против него, т.е.для каждого агента существует раздел, в котором все пакеты слабо хуже, чем его текущая доля.

Для каждого агента с субаддитивной утилитой mFS стоит не менее $1 / n {\ displaystyle 1 / n}$ $1 / n$ . Следовательно, каждое справедливое распределение mFS пропорционально. Для каждого агента с супераддитивной утилитой значение MMS составляет не более $1 / n {\ displaystyle 1 / n}$ $1 / n$ . Следовательно, каждое пропорциональное распределение является справедливым для MMS. Оба включения являются строгими, даже когда каждый агент имеет дополнительную полезность. Это проиллюстрировано в следующем примере:

Есть 3 агента и 3 элемента:

Алиса оценивает элементы как 2,2,2. Для нее MMS = PFS = mFS = 2.
Боб оценивает элементы как 3,2,1. Для него MMS = 1, PFS = 2 и mFS = 3.
Карл оценивает элементы как 3,2,1. Для него MMS = 1, PFS = 2 и mFS = 3.

Возможные распределения следующие:

Каждое распределение, которое дает элемент каждому агенту, является приемлемым для MMS.
Каждое распределение, которое дает первый и второй элементы Бобу и Карлу, а третий элемент Алисе, является пропорциональным.
Никакое распределение не является справедливым для mFS.

Вышеупомянутые последствия не выполняются, когда оценки агентов не являются суб / супераддитивными.

4. Свобода от зависти (EF) : каждый агент слабо предпочитает свой собственный комплект любому другому комплекту. Любое распределение всех предметов без зависти является справедливым для mFS; это следует непосредственно из порядковых определений и не зависит от аддитивности. Если оценки являются аддитивными, то распределение EF также пропорционально и справедливо для MMS. В противном случае распределение EF может быть непропорциональным и даже не MMS. Подробнее см. назначение предметов без зависти.

5. Конкурентное равновесие из равных доходов (CEEI) : этот критерий основан на следующем аргументе: процесс распределения следует рассматривать как поиск равновесия между поставками (набором объектов, каждый из которых имеет публичную цену) и спроса (желания агентов, каждый агент имеет одинаковый бюджет на покупку объектов). Конкурентное равновесие достигается, когда предложение соответствует спросу. Аргумент справедливости прост: цены и бюджет одинаковы для всех. CEEI подразумевает EF независимо от аддитивности. Когда предпочтения агентов являются аддитивными и строгими (каждый набор имеет свое значение), CEEI подразумевает эффективность по Парето.

Несколько недавно предложенных критериев справедливости:

6. Свобода-зависть-except-1 (EF1) : для каждых двух агентов A и B, если мы удалим из набора B предмет, наиболее ценный для A, то A не завидует B (другими словами, «уровень зависти» A в B - это не более чем ценность одного элемента). При монотонности всегда существует выделение EF1.

7. Без зависти-за исключением-дешевого (EFx) : для каждых двух агентов A и B, если мы удалим из набора B предмет, наименее ценный для A, то A не завидует B. EFx строго сильнее, чем EF1. Неизвестно, всегда ли существуют распределения EFx.

Критерии глобальной оптимизации

Критерий глобальной оптимизации оценивает разделение на основе заданной функции общественного благосостояния :

Эгалитарное социальное благосостояние - это минимальная полезность одного агента. Распределение элементов называется эгалитарно-оптимальным, если оно обеспечивает максимально возможное эгалитарное благополучие, то есть максимизирует полезность самого бедного агента. Поскольку может быть несколько разных распределений, максимизирующих наименьшую полезность, эгалитарная оптимальность часто уточняется до лексимин-оптимальности: из подмножества распределений, максимизирующих наименьшую полезность, выбираются те распределения, которые максимизируют вторую по величине полезность, а затем третью по величине полезность. и т. д.
Социальное благосостояние Нэша является продуктом полезности агентов. Назначение называется оптимальным по Нэшу или максимумом-благосостоянием по Нэшу, если оно максимизирует продукт полезности. Оптимальные по Нэшу распределения обладают некоторыми хорошими свойствами справедливости.

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

Алгоритмы присвоения

Макс-мин-доля справедливость

Соразмерность

1. Предположим, что у агентов есть кардинальные функции полезности предметов. Тогда проблема определения того, существует ли пропорциональное распределение, является NP-Complete : она может быть сокращена от проблемы разделения.

2. Предположим, агенты имеют порядковые ранжирования по пунктам с безразличием или без него. Тогда проблема определения существования обязательно-пропорционального распределения может быть решена за полиномиальное время: ее можно свести к проблеме проверки того, допускает ли двудольный граф допустимое b-сопоставление (a соответствие, когда края имеют емкости).

Для двух агентов существует более простой алгоритм.

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

Справедливость минимального и максимального распределения

Проблема вычисления mFS агента: coNP -complete.

Проблема определения наличия выделения mFS находится в $NPNP {\ displaystyle NP ^ {NP}}$ ${\ displaystyle NP ^ {NP}}$ , но ее точная вычислительная сложность все еще неизвестна.

Свобода от зависти (без денег)

Свобода от зависти (с деньгами)

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

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

Справедливо. by Design - это общая структура для задач оптимизации с гарантией свободы от зависти, которая естественным образом расширяет справедливое назначение предметов с помощью денежных выплат.

Кавалло обобщает традиционные бинарные критерии свободы от зависти, соразмерности и эффективности (благосостояния) на меры степени, которая находится в диапазоне от 0 до 1. В условиях канонического справедливого деления при любом эффективном с точки зрения распределения механизме уровень благосостояния наихудшего случая равен 0, а коэффициент диспропорциональности равен 1; Другими словами, результаты наихудшего случая как можно хуже. Это сильно мотивирует анализ среднего случая. Он ищет механизм, который обеспечивает высокий уровень благосостояния, низкий уровень зависти и низкий уровень диспропорциональности в ожиданиях во всем спектре условий справедливого разделения. Он показывает, что механизм VCG не является удовлетворительным кандидатом, но механизм перераспределения и является.

См. Также: гармония аренды.

Эгалитарно-оптимальное распределение

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

С аддитивными утилитами для каждого целого $k {\ displaystyle k}$ $k$ , a $(1 - 1 / k) { \ displaystyle (1-1 / k)}$ ${\ displaystyle (1-1 / k)}$ доля агентов, получающих полезность не менее $OPT / k {\ displaystyle OPT / k}$ ${ \ displaystyle OPT / k}$ . Этот результат получается путем округления подходящего решения задачи линейного программирования и является наилучшим возможным результатом для этой линейной программы.
С двумя классами товаров $O (n) {\ displaystyle O ({\ sqrt {n}})}$ $O ({\ sqrt {n}})$ существует приближение.
С субмодульными функциями полезности, $(m - n + 1) {\ displaystyle (m-n + 1)}$ ${\ displaystyle (m-n + 1)}$ существует приближение.

и дает более сильные результаты по твердости.

Особый случай оптимизации эгалитарного благосостояния с дополнительными полезностями называется «проблемой Санта-Клауса». Проблема по-прежнему является NP-сложной и не может быть аппроксимирована с точностью до множителя>1/2, но есть приближение $O (n) {\ displaystyle O (n)}$ $О (п)$ и более сложное $O (n ⋅ log 3 ⁡ n) {\ displaystyle O ({\ sqrt {n}} \ cdot \ log ^ {3} {n})}$ ${\ displaystyle O ({\ sqrt {n}} \ cdot \ log ^ {3} {n})}$ приближение. См. Также алгоритм ветвей и границ для двух партнеров.

Процедура Уменьшение спроса возвращает эгалитарно-оптимальное деление в порядковом порядке: она максимизирует ранг в линейном ранжировании пакетов агента с самым низким рангом. Работает для любого количества агентов с любым порядком пакетов.

Оптимальные по Нэшу распределения

и доказывают трудность вычисления утилитарно-оптимальных и оптимальных по Нэшу распределений.

представляют процедуру аппроксимации для оптимальных по Нэшу распределений.

Последовательности комплектации

Последовательность комплектации - это простой протокол, в котором агенты по очереди выбирают предметы на основе некоторой заранее заданной последовательности ходов. Цель состоит в том, чтобы разработать последовательность выбора таким образом, чтобы максимизировать ожидаемую ценность функции общественного благосостояния (например, эгалитарной или утилитарной) при некоторых вероятностных допущениях об оценках агентов.

Разные права

Большинство исследований о назначении элементов предполагает, что все агенты имеют равные права. Но во многих случаях есть агенты с разными правами. Один из таких случаев - разделение министерств между партиями коалиции. Принято считать, что каждая партия должна получать министерства в соответствии с количеством мест в парламенте. Смотрите и и для обсуждения этой проблемы и некоторых решений.

См. Также

Эксперименты по справедливому разделению - включая некоторые тематические исследования и лабораторные эксперименты, связанные с справедливым распределением предметов.
Гармония аренды - проблема справедливого разделения, когда неделимые предметы и Фиксированная общая стоимость должна быть разделена одновременно.
Цена справедливости - общая мера компромисса между справедливостью и эффективностью, с некоторыми результатами в отношении настройки назначения элементов.

Ссылки