Задача справедливого распределения объектов

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

• несколько наследников хотят поделить наследство, в которое входит, например, дом, автомобиль, рояль и несколько картин;
• несколько лекторов решают поделить курсы, которые даются на их факультете. Каждый лектор может читать один или несколько курсов, но только полный курс; один курс несколько лекторов читать не могут.

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

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

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

Эти составляющие объяснены в деталях ниже.

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

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

Естественный путь определения предпочтений — попросить каждого участника сопоставить число каждому возможному набору предметов, то есть указать его ценность в числовом выражении. Например, если объектами, которые следует распределить, будут автомобиль и мотоцикл, участники могут оценить автомобиль в 800, а мотоцикл в 200, а набор {автомобиль, мотоцикл} в 900 (см. статью Функции полезности на неделимых товарах для дополнительных примеров). Имеется две проблемы с этими подходами:

1. Участнику может быть сложно вычислить точную численную ценность набора предметов.
2. Число возможных наборов может быть огромным — если имеется $m$ предметов, то имеется $2^{m}$ возможных наборов. Например, если имеется 16 предметов, то каждый участник должен будет представить свои предпочтения, указав 65536 чисел.

Первая проблема побуждает использовать порядковую полезность, а не количественную. В порядковой модели каждый участник должен показать лишь ранжирование по $2^{m}$ различным наборам, то есть сказать, какой набор объектов лучший, какой стоит на втором месте и т. д. Это может быть проще вычисления точных чисел, но остаётся сложным делом, если число объектов велико.

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

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

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

Аддитивные предпочтения

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

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

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

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

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

• 2-аддитивные предпочтения — каждый участник сообщает ценность для каждого набора размером 1 или 2. Значение набора вычисляется как сумма значений индивидуальных объектов в наборе и добавления значений пар в наборе. Обычно, когда имеются заменяемые объекты, значения пар будут отрицательными, а когда имеются дополняющие объекты, значения пар будут положительными. Эта идея может быть обобщена до k-аддитивных предпочтений для любого положительного целого k.
• Графические модели — для каждого участника имеется граф, который представляет зависимости между различными объектами. При численном подходе обычным средством является GAI net (обобщённая аддитивная независимость, англ. Generalized Additive Independence). При порядковом подходе обычным средством является CP net (условные предпочтения, англ. Conditional Preferences) и его расширения TCP net, UCP net, CP theory, CI net (условная важность, англ. Conditional Importance) и SCI net (упрощение CI net англ. a simplification of CI net).
• Основанные на логике языки — каждый участник описывает некоторые наборы с помощью формул логики первого порядка и может назначить значение для каждой формулы. Например, участник может сказать: «Для (x или (y и z)) моё значение будет 5». Это означает, что агент назначает ценность 5 для любого набора из: x, xy, xz, yz, xyz.
• Языки торгов — изучались многие языки для представления комбинаторных предпочтений в контексте комбинаторных аукционов. Некоторые из этих языков могут быть приспособлены для условий распределения объектов.

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

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

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

1. Max-min справедливая доля (англ. Max-min fair-share, MFS): Max-min справедливая доля (называется также max-min гарантированной долей) агента является наиболее предпочтительным набором, который агент может гарантировать себе, если будет делящим лицом в протоколе Дели-и-выбирай. Распределение называется MFS-справедливым, если любой агент получает набор, который слегка предпочтительнее его MFS. MFS агента можно интерпретировать как максимальная полезность, которую агент может надеяться получить при распределении, когда все другие агенты имеют те же самые предпочтения, если агент всегда получает наихудшую долю. Это можно рассматривать как минимальное количество полезности, которое на которое агент может рассчитывать, основываясь на следующих доводах: если все другие агенты имеют те же предпочтения, что и я, имеется по меньшей мере одно распределение, которое даёт мне эту полезность и делает всех других агентов (слегка) богаче. Следовательно, нет никаких причин дать мне меньше. Это также максимальная полезность, которую агент может получить наверняка в игре распределения «Я режу, я выбираю последним» — агент предлагает лучшее распределение и оставляет остальным участникам выбрать свои доли, а сам получает оставшуюся долю. MFS-справедливость можно также описать как результат следующего процесса переговоров. Предлагается некоторое распределение. Каждый агент может возразить путём предложения другого разбиения предметов. Однако, делая это, он должен позволить всем другим агентам выбрать их доли перед тем как забрать свою. Следовательно, агент будет возражать на распределение только если он может предложить разбиение на наборы, которые все лучше текущего набора. Распределение MFS-справедливо тогда и только тогда, когда ни один из агентов не возражает, то есть для любого агент в любом разбиении существует набор, который слегка хуже, чем его текущая доля.

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

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

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

Имеется 3 агента и 3 предмета:

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

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

• Любое распределение, которое даёт по предмету каждому участнику, является MFS-справедливость.
• Любое распределение, которое даёт первый и второй предметы Бобу и Карлу, а третий предмет — Алисе, является пропорциональным.
• Никакое распределение не будет mFS-справедливым.

Приведённые выше выводы не верны, если оценки агентов не под/супераддитивны.

4. Отсутствие зависти (англ. Envy-freeness, EF): любой агент предпочитает свой собственный набор любому другому набору. Любое свободное от зависти распределение всех предметов является mFS-справедливым. Это следует прямо из порядковых определений и не зависит от аддитивности. Если оценки аддитивны, то EF распределение также пропорционально и MFS-справедливо. В противном случае EF распределение может быть не пропорциональным и даже не MFS. См. Завистливое распределение предметов для детального рассмотрения.

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

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

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

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

Глобальный критерий оптимальности

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

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

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

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

Справедливость Max-min-доли

Задача вычисления MFS для агента NP-полна — это можно показать сведением задачи из задачи разбиения множества чисел .

MFS распределения существуют в большинстве случаев, но не всегда. Существуют очень редкие случаи, когда такого распределения не существует.

Задача определения, существует ли MFS распределение, является $NP^{NP}$, то есть она может быть решена за недетерминировано полиномиальное время с помощью предсказателя для NP-трудной задачи (предсказатель нужен для вычисления max-min-доли агента). Однако точная вычислительная сложность этой задачи остаётся неизвестной.

Распределения, которые гарантируют каждому участнику 2/3 приведённого выше значения всегда существуют. Процедура распределения была имплементирована в веб-сервисе spliddit.

Пропорциональность

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

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

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

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

Справедливость Min-max-доли

Задача вычисления mFS агента coNP-полна.

Задача, существует ли mFS распределение является $NP^{NP}$, но её точная вычислительная сложность остаётся неизвестной.

Отсутствие зависти (без денег)

Основная статья: Завистливое распределение объектов

Отсутствие зависти (с деньгами)

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

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

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

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

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

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

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

В статье Нгуена, Рууса и Роте и статье Н.-T. Нгуена, T. T. Нгуена, Рууса и Роте представлены некоторые более сильные результаты.

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

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

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

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

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

Последовательность выборки

Основная статья: Последовательность выборки

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

Различные паевые доли

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