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

Задача о справедливом дележе, в которой делимые предметы являются дискретными, а не непрерывными.

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

• Несколько наследников хотят разделить унаследованное имущество, включающее в себя, например, дом, машину, пианино и несколько картин.
• Несколько лекторов хотят разделить курсы, читаемые на их факультете. Каждый лектор может вести один или несколько полных курсов.
• Вечеринки по обмену подарками «Белый слон»

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

Задача о назначении предметов состоит из нескольких компонентов:

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

Эти ингредиенты подробно описаны ниже.

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

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

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

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

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

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

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

При соответствующих предположениях можно повысить предпочтения по элементам до предпочтений по наборам. ^{[3] : 44–48} Затем агенты сообщают свои оценки/рейтинги по отдельным элементам, а алгоритм вычисляет для них их оценки/рейтинги по наборам.

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

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

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

Аддитивность подразумевает, что каждый партнер всегда может выбрать «предпочтительный элемент» из набора элементов на столе, и этот выбор не зависит от других элементов, которые могут быть у партнера. Это свойство используется некоторыми алгоритмами справедливого назначения, которые будут описаны далее. ^{[2] : 287–288}

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

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

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

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

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

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

Максимин доля

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

Пропорциональныйсправедливая доля (PFS)

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

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

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

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

Есть три агента и три предмета:

• Алиса оценивает элементы как 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.

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

Отсутствие зависти(ЭФ)

Каждый агент слабо предпочитает свой собственный набор любому другому набору. Каждое распределение всех элементов без зависти является mFS-справедливым; это следует непосредственно из ординальных определений и не зависит от аддитивности. Если оценки аддитивны, то распределение EF также является пропорциональным и MMS-справедливым. В противном случае распределение EF может быть непропорциональным и даже не MMS. ^[9]

Более слабые версии EF включают: ^[10]

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

Конкурентное равновесиеиз Равных Доходов (CEEI)

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

Глобальные критерии оптимизации

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

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

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

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

Различные алгоритмы справедливого распределения предметов рассматриваются на страницах, посвященных конкретным критериям справедливости:

• Распределение элементов по принципу максиминной доли ;
• Пропорциональное распределение предметов ;
• Распределение минимаксных долей: Задача вычисления mFS агента является coNP-полной . Задача определения того, существует ли распределение mFS, находится в , но ее точная вычислительная сложность до сих пор неизвестна. ^[7] ${\displaystyle NP^{NP}}$
• Распределение предметов без зависти ;
• Эффективное, приблизительно справедливое распределение предметов ;
• Равноправное распределение предметов ;
• Оптимальное по Нэшу распределение: ^[11] и ^[12] доказывают сложность вычисления утилитарно-оптимального и оптимального по Нэшу распределения. ^[13] представляют процедуру аппроксимации для оптимального по Нэшу распределения.
• Последовательность выбора : простой протокол, в котором агенты по очереди выбирают предметы, основываясь на некоторой заранее заданной последовательности ходов. Цель состоит в том, чтобы спроектировать последовательность выбора таким образом, чтобы максимизировать ожидаемое значение функции общественного благосостояния (например, эгалитарной или утилитарной) при некоторых вероятностных предположениях об оценках агентов.
• Конкурентное равновесие: различные алгоритмы поиска распределения CE описаны в статье о рынке Фишера .

Между делимым и неделимым

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

Ограничение объема обмена

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

• Для пропорционального , свободного от зависти , справедливого и эгалитарного распределения n −1 разделов/общих объектов всегда достаточно и может быть необходимо; ^[14]
• Для разделения консенсуса на k частей всегда достаточно n ( n −1) общих ресурсов/общих объектов, а может быть и необходимо. ^[15]

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

• Сандомирский и Сигал-Халеви ^[14] изучают минимизацию совместного использования в распределениях, которые являются как справедливыми, так и дробно эффективными по Парето (fPO). Они доказывают, что если оценки агентов невырождены, то количество распределений fPO полиномиально по количеству объектов (для фиксированного количества агентов). Поэтому можно перечислить их все за полиномиальное время и найти распределение, которое является справедливым и fPO с наименьшим количеством распределений. Напротив, если оценки вырождены, задача становится NP-трудной. Они представляют эмпирические доказательства того, что в реалистичных случаях часто существует распределение с существенно меньшим количеством распределений, чем наихудшая граница.
• Мисра и Сетия ^[16] дополняют свой результат, доказывая, что когда n не фиксировано, даже для невырожденных оценок, NP-трудно решить, существует ли распределение без зависти fPO с 0 делениями. Они также демонстрируют альтернативный подход к перечислению различных графов потребления для распределений с небольшим числом делений.
• Голдберг, Холлендер, Игараси, Манурангси и Суксомпонг ^[15] изучают минимизацию совместного использования при разделении консенсуса . Они доказывают, что для агентов с аддитивной полезностью существует полиномиальный алгоритм для вычисления консенсусного деления пополам с максимум n делениями и для вычисления консенсусного k -деления с максимум ( k −1) n разрезаниями. Но минимизация совместного использования является NP-трудной: для любого фиксированного n NP-трудно отличить экземпляр, требующий n делений, от экземпляра, требующего 0 делений. Вероятностно, n делений почти наверняка необходимы для консенсусного деления пополам, когда полезности агентов берутся из вероятностных распределений. Для агентов с неаддитивной монотонной полезностью консенсусное деление пополам является PPAD-трудным, но существуют полиномиальные алгоритмы для фиксированного числа агентов.
• Bismuth, Makarov, Shapira и Segal-Halevi ^[17] изучают справедливое распределение с идентичными оценками, что эквивалентно планированию на идентичных машинах , а также более общую настройку планирования на однородных машинах . Они изучают сложность времени выполнения принятия решения о существовании справедливого распределения с s разделениями или общими объектами, где s меньше наихудшей верхней границы n −1. Они доказывают, что для разделения задача является NP-трудной для любого s ≤ n −2; но для общих объектов и n ≥ 3 задача является полиномиальной для s = n −2 и NP-трудной для любого s ≤ n −3. Когда n не фиксировано, задача является сильно NP-трудной.

Смесь делимых и неделимых товаров

• Бэй, Ли, Лю, Лю и Лу ^[18] изучают смесь неделимых и делимых благ (объектов с положительной полезностью). Они определяют приближение к свободе от зависти, называемое EFM (свобода от зависти для смешанных предметов), которое обобщает как свободу от зависти для делимых предметов, так и EF1 для неделимых предметов. Они доказывают, что распределение EFM всегда существует для любого числа агентов с аддитивными оценками. Они представляют эффективные алгоритмы для вычисления распределений EFM для двух агентов с общими аддитивными оценками и для n агентов с кусочно-линейными оценками по делимым благам. Они также представляют эффективный алгоритм, который находит эпсилон -приближенное распределение EFM.
• Бэй, Лю, Лу и Ван ^[19] изучают ту же самую ситуацию, фокусируясь на справедливости максиминной доли . Они предлагают алгоритм, который вычисляет альфа-приближенное распределение MMS для любого числа агентов, где альфа является константой между 1/2 и 1, которая монотонно увеличивается со стоимостью делимых благ относительно значений MMS.
• Бхаскар, Шричаран и Вайш ^[20] изучают смесь неделимых дел (объектов с отрицательной полезностью) и делимого торта (с положительной полезностью). Они представляют алгоритм для поиска распределения EFM в двух особых случаях: когда каждый агент имеет одинаковый рейтинг предпочтений по набору дел, и когда количество элементов не превышает количества агентов плюс 1.
• Ли, Лю, Лу и Тао ^[21] изучают правдивые механизмы для EFM. Они показывают, что в общем случае не существует правдивого алгоритма EFM, даже если есть только одно неделимое благо и одно делимое благо и только два агента. Но когда агенты имеют бинарные оценки для неделимых благ и идентичные оценки для одного делимого блага, EFM и правдивый механизм существуют. Когда агенты имеют бинарные оценки как для делимых, так и для неделимых благ, EFM и правдивый механизм существуют, когда есть только два агента или когда есть одно делимое благо.
• Нисимура и Сумита ^[22] изучают свойства максимального распределения благосостояния Нэша (MNW) для смешанных товаров. Они доказывают, что когда оценки всех агентов являются бинарными и линейными для каждого товара, распределение MNW удовлетворяет свойству, более сильному, чем EFM, которое они называют «отсутствием зависти до любого товара для смешанных товаров». Их результаты справедливы не только для максимального благосостояния Нэша, но и для общего понятия справедливости, основанного на минимизации симметричной строго выпуклой функции. Для общих аддитивных оценок они доказывают, что распределение MNW удовлетворяет приближению EF, которое слабее, чем EFM.
• Кавасе, Нисимура и Сумита ^[23] изучают оптимальное распределение смешанных товаров, где вектор полезности должен минимизировать симметричную строго выпуклую функцию (это обобщение эгалитаристского распределения предметов и максимального благосостояния Нэша). Они предполагают, что все агенты имеют бинарные оценки. Известно, что если существуют только делимые товары или только неделимые товары, проблема разрешима за поливременной интервал. Они показывают, что со смешанными товарами проблема является NP-трудной, даже когда все неделимые товары идентичны. Напротив, если все делимые товары идентичны, существует алгоритм поливременной интервал.
• Бэй, Лю и Лу ^[24] изучают более общую ситуацию, в которой один и тот же объект может быть делимым для некоторых агентов и неделимым для других. Они показывают, что наилучшее возможное приближение для MMS — 2/3, даже для двух агентов; и представляют алгоритмы, достигающие этой границы для 2 или 3 агентов. Для любого числа агентов они представляют приближение 1/2-MMS. Они также показывают, что EFM несовместим с нерасточительностью.
• Ли, Ли, Лю и Ву ^[25] изучают ситуацию, в которой каждый агент может иметь разное «коэффициент неделимости» (= доля неделимых элементов). Каждому агенту гарантируется распределение, которое является EF/PROP с точностью до доли элемента, где доля зависит от коэффициента неделимости агента. Результаты точны до константы для EF и асимптотически точны для PROP.
• Ли, Лю, Лу, Тао и Тао ^[26] изучают цену справедливости как в неделимом, так и в смешанном распределении элементов. Они предоставляют границы для цены EF1, EFx, EFM и EFxM. Они предоставляют узкие границы для двух агентов и асимптотически узкие границы для n агентов, как для масштабируемых, так и для немасштабируемых полезностей.

Лю, Лу, Сузуки и Уолш ^[27] рассматривают некоторые недавние результаты по смешанным предметам и выявляют несколько открытых вопросов:

1. Совместим ли EFM с эффективностью по Парето ?
2. Существуют ли эффективные алгоритмы максимизации утилитарного общественного благосостояния среди распределений EFM?
3. Существуют ли ограниченные или даже конечные алгоритмы для вычисления распределений EFM в модели запросов Робертсона-Уэбба ?
4. Всегда ли существует распределение EFM, когда есть неделимые обязанности и торт?
5. В более общем плане: всегда ли существует распределение EFM, когда как делимые, так и неделимые элементы могут быть положительными для одних агентов и отрицательными для других?
6. Существует ли правдивый алгоритм EFM для агентов с бинарными аддитивными оценками?

Варианты и расширения

Различные права

В этом варианте разные агенты имеют право на разные доли ресурса. Обычный вариант использования — разделение министерств кабинета между партиями в коалиции. ^[28] Принято считать, что каждая партия должна получать министерства в соответствии с количеством мест, которые она имеет в парламенте. Различные понятия справедливости должны быть адаптированы соответствующим образом. Было рассмотрено несколько классов понятий справедливости:

• Понятия, основанные на взвешенном конкурентном равновесии; ^{[29] [30]}
• Понятия, основанные на взвешенной свободе от зависти; ^{[31] [32] [33]}
• Понятия, основанные на взвешенной справедливой доле; ^[34]

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

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

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

Распределение общественных благ

В этом варианте каждый элемент обеспечивает полезность не только одному агенту, но и всем агентам. Разные агенты могут приписывать разные полезности одному и тому же элементу. Группа должна выбрать подмножество элементов, удовлетворяющее некоторым ограничениям, например:

• Максимум k элементов может быть выбрано. Этот вариант тесно связан с голосованием с несколькими победителями , за исключением того, что при голосовании с несколькими победителями число избранных кандидатов обычно намного меньше числа избирателей, тогда как при распределении общественных благ число выбранных товаров обычно намного больше числа агентов. Примером может служить публичная библиотека, которая должна решить, какие книги покупать, учитывая предпочтения читателей; число книг обычно намного больше числа читателей. ^[36]
• Общая стоимость всех пунктов не должна превышать фиксированный бюджет. Этот вариант часто называют бюджетированием с участием .
• Число элементов должно быть как можно меньше, при условии, что все агенты должны согласиться, что выбранный набор лучше, чем невыбранный набор. Этот вариант известен как проблема приемлемого подмножества .
• На выбранном наборе могут быть общие ограничения матроида , ограничения соответствия или ограничения рюкзака . ^[37]

Распределение частных благ можно рассматривать как особый случай распределения общественных благ: учитывая проблему частных благ с n агентами и m предметами, где агент i оценивает предмет j в v _ij , постройте проблему общественных благ с n · m предметами, где агент i оценивает каждый предмет i,j в v _ij , а остальные предметы в 0. Предмет i,j по сути представляет собой решение отдать предмет j агенту i . Эту идею можно формализовать, чтобы показать общее сокращение от распределения частных благ до распределения общественных благ, которое сохраняет максимальное распределение благосостояния Нэша, а также аналогичное сокращение, которое сохраняет лексиминное оптимальное распределение. ^[36]

Распространенными концепциями решений для распределения общественных благ являются базовая стабильность (которая подразумевает как эффективность по Парето, так и пропорциональность), ^[37] максимальное благосостояние по Нэшу, лексиминовая оптимальность и пропорциональность вплоть до одного элемента. ^[36]

Принятие государственных решений

В этом варианте несколько агентов должны принять решения по нескольким вопросам. Обычный вариант использования — это семья, которая должна решить, какое действие выполнять каждый день (здесь каждый вопрос — это день). Каждый агент назначает различные полезности различным вариантам в каждом вопросе. Классическая настройка распределения предметов соответствует особому случаю, в котором каждый вопрос соответствует предмету, каждый вариант решения соответствует передаче этого предмета конкретному агенту, а полезности агентов равны нулю для всех вариантов, в которых предмет передается кому-то другому. В этом случае пропорциональность означает, что полезность каждого агента составляет по крайней мере 1/ n его «полезности диктатуры», т. е. полезности, которую он мог бы получить, выбрав лучший вариант в каждом вопросе. Пропорциональность может быть недостижима, но PROP1 достижима с помощью распределения предметов по круговой системе . ^[38]

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

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

Стохастическое распределение неделимых благ

Стохастическое распределение неделимых благ ^[40] — это тип справедливого распределения предметов, в котором решение описывает распределение вероятностей по набору детерминированных распределений.

Предположим, что m элементов должны быть распределены между n агентами. Формально, в детерминированной обстановке, решение описывает допустимое распределение элементов между агентами — разбиение набора элементов на n подмножеств (по одному для каждого агента). Набор всех детерминированных распределений можно описать следующим образом:

${\displaystyle {\mathcal {A}}=\{(A^{1},\dots ,A^{n})\mid \forall i\in [n]\colon A^{i}\subseteq [m],\quad \forall i\neq j\in [n]\colon A^{i}\cap A^{j}=\emptyset ,\quad \cup _{i=1}^{n}A^{i}=[m]\}}$

В стохастической постановке решение представляет собой распределение вероятностей по множеству . То есть множество всех стохастических распределений (т.е. всех возможных решений проблемы) можно описать следующим образом: ${\displaystyle {\mathcal {A}}}$

${\displaystyle {\mathcal {D}}=\{d\mid p_{d}\colon {\mathcal {A}}\to [0,1],\sum _{A\in {\mathcal {A}}}p_{d}(A)=1\}}$

С каждым агентом связаны две функции: функция полезности, связанная с детерминированным распределением , ${\displaystyle u_{i}\colon {\mathcal {A}}\to \mathbb {R} _{+}}$ и ожидаемая функция полезности, связанная со стохастическим распределением , которая определяется следующим образом : ${\displaystyle E_{i}\colon {\mathcal {D}}\to \mathbb {R} _{+}}$ ${\displaystyle u_{i}}$

${\displaystyle E_{i}(d)=\sum _{A\in {\mathcal {A}}}p_{d}(A)\cdot u_{i}(A)}$

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

Те же критерии, которые предлагаются для детерминированной ситуации, можно рассмотреть и в стохастической ситуации:

• Правило утилитаризма : это правило гласит, что общество должно выбирать решение, которое максимизирует сумму полезностей. То есть выбирать стохастическое распределение , которое максимизирует утилитарное благо : Кавасе и Сумита ^[40] показывают, что максимизация утилитаристского благосостояния в стохастической обстановке всегда может быть достигнута с помощью детерминированного распределения . Причина в том, что утилитарная ценность детерминированного распределения по крайней мере равна утилитаристской ценности : ${\displaystyle d^{*}\in {\mathcal {D}}}$ ${\displaystyle d^{*}={\underset {d\in {\mathcal {D}}}{\operatorname {argmax} }}\sum _{i=1}^{n}\sum _{A\in {\mathcal {A}}}\left(p_{d}(A)\cdot u_{i}(A)\right)}$ ${\displaystyle A^{*}={\underset {A\in {\mathcal {A}}\colon p_{d^{*}}(A)>0}{\operatorname {argmax} }}\sum _{i=1}^{n}u_{i}(A)}$ ${\displaystyle d^{*}}$ ${\displaystyle \sum _{i=1}^{n}\sum _{A\in {\mathcal {A}}}\left(p_{d^{*}}(A)\cdot u_{i}(A)\right)=\sum _{A\in {\mathcal {A}}}p_{d^{*}}(A)\sum _{i=1}^{n}u_{i}(A)\leq \max _{A\in {\mathcal {A}}\colon p_{d^{*}}(A)>0}\sum _{i=1}^{n}u_{i}(A)}$
• Правило эгалитаризма: это правило гласит, что общество должно выбирать решение, которое максимизирует полезность для беднейших. То есть, выбирать стохастическое распределение , которое максимизирует эгалитарное благо : В отличие от правила утилитаризма, здесь стохастическая установка позволяет обществу достичь более высокой ценности ^[40] — в качестве примера рассмотрим случай, когда есть два идентичных агента и только один предмет, который стоит ${\displaystyle d^{*}\in {\mathcal {D}}}$ ${\displaystyle d^{*}={\underset {d\in {\mathcal {D}}}{\operatorname {argmax} }}\min _{i=1,\ldots ,n}\sum _{A\in {\mathcal {A}}}\left(p_{d}(A)\cdot u_{i}(A)\right)}$100. Легко видеть, что в детерминированной обстановке эгалитарная ценность равна0 , тогда как в стохастической настройке это50 .
  • Сложность: Кавасэ и Сумита ^[40] доказывают, что найти стохастическое распределение, которое максимизирует эквалитарное благосостояние , NP-сложно, даже когда все полезности агентов являются бюджетно-аддитивными ; а также, что NP-сложно приблизить эквалитарное благосостояние к множителю, лучшему, чем когда все агенты имеют одинаковую субмодулярную функцию полезности . ${\displaystyle 1-{\tfrac {1}{e}}}$
  • Алгоритм: Кавасе и Сумита ^[40] представляют алгоритм, который, учитывая алгоритм для нахождения детерминированного распределения, которое приближает утилитаристское благосостояние к фактору α , находит стохастическое распределение, которое приближает эгалитаристское благосостояние к тому же фактору α .

Смотрите также

• Проблема покрытия контейнеров и проблема упаковки контейнеров — две хорошо изученные задачи оптимизации, которые можно рассматривать как частные случаи неделимого распределения товаров и неделимого распределения хлопот соответственно. Многие методы, используемые для этих задач, полезны и в случае справедливого распределения предметов.
• Эксперименты по справедливому дележу , включая некоторые тематические исследования и лабораторные эксперименты, связанные со справедливым распределением предметов.
• Гармония арендной платы — проблема справедливого раздела, при которой неделимые объекты и фиксированная общая стоимость должны быть разделены одновременно.
• Справедливое случайное распределение — задача справедливого дележа без денег, в которой справедливость достигается посредством рандомизации.
• Задача о распределении домов — задача о справедливом разделе, в которой каждый агент должен получить ровно один объект, без денежных переводов или рандомизации.
• Распределение курсов — проблема справедливого распределения, при которой места на университетских курсах должны быть разделены между студентами.
• Цена справедливости — общая мера компромисса между справедливостью и эффективностью, с некоторыми результатами относительно настройки назначения элементов.
• Проблема справедливой суммы подмножества
• 17-головоломка о наследовании животных

Ссылки

1. Демко, Стивен; Хилл, Теодор П. (1988-10-01). «Справедливое распределение неделимых объектов». Математические социальные науки . 16 (2): 145–158. doi :10.1016/0165-4896(88)90047-9. ISSN  0165-4896.
2. Сильвен Бувере и Ян Шевалейр и Николя Моде, «Справедливое распределение неделимых благ». Глава 12 в: Брандт, Феликс; Конитцер, Винсент; Эндрисс, Улле; Ланг, Жером; Прокачча, Ариэль Д. (2016). Справочник по вычислительному социальному выбору. Cambridge University Press. ISBN 9781107060432.(бесплатная онлайн-версия)
3. Barberà, S.; Bossert, W.; Pattanaik, PK (2004). "Ранжирование множеств объектов". (PDF) . Справочник по теории полезности . Springer US.
4. Сильвен Бувере; Улле Эндрисс; Жером Ланг (2010). Справедливое разделение при порядковых предпочтениях: вычисление свободного от зависти распределения неделимых благ. Труды конференции 2010 года по ECAI 2010: 19-я Европейская конференция по искусственному интеллекту . Получено 26 августа 2016 г.
5. Brams, Steven J.; Edelman, Paul H.; Fishburn, Peter C. (2003). «Справедливое разделение неделимых предметов». Теория и решение . 55 (2): 147. doi :10.1023/B:THEO.0000024421.85722.0a. S2CID  153943630.
6. Brams, SJ (2005). «Эффективное справедливое разделение: помочь наихудшим или избежать зависти?». Рациональность и общество . 17 (4): 387–421. CiteSeerX 10.1.1.118.9114 . doi :10.1177/1043463105058317. S2CID  154808734. 
7. Бувере, Сильвен; Лемэтр, Мишель (2015). «Характеристика конфликтов при справедливом разделе неделимых благ с использованием шкалы критериев». Автономные агенты и многоагентные системы . 30 (2): 259. doi :10.1007/s10458-015-9287-3. S2CID  16041218.
8. Будиш, Э. (2011). «Комбинаторная задача о назначениях: приближенное конкурентное равновесие из равных доходов». Журнал политической экономии . 119 (6): 1061–1103. CiteSeerX 10.1.1.357.9766 . doi :10.1086/664613. S2CID  154703357. 
9. Хейнен, Тобиас; Нгуен, Нхан-Там; Роте, Йорг (2015). «Справедливость и ранговый утилитаризм в распределении ресурсов». Алгоритмическая теория принятия решений . Конспекты лекций по информатике. Том. 9346. с. 521. дои : 10.1007/978-3-319-23114-3_31. ISBN 978-3-319-23113-6.
10. Caragiannis, Ioannis; Kurokawa, David; Moulin, Hervé; Procaccia, Ariel D.; Shah, Nisarg; Wang, Junxing (2016). Необоснованная справедливость максимального благосостояния Нэша (PDF) . Труды конференции ACM 2016 года по экономике и вычислениям - EC '16. стр. 305. doi :10.1145/2940716.2940726. ISBN 9781450339360.
11. Нгуен, Трунг Тхань; Роос, Магнус; Роте, Йорг (2013). «Обзор результатов аппроксимируемости и неаппроксимируемости для оптимизации общественного благосостояния при распределении ресурсов с несколькими агентами». Annals of Mathematics and Artificial Intelligence . 68 (1–3): 65–90. CiteSeerX 10.1.1.671.3497 . doi :10.1007/s10472-012-9328-4. S2CID  6864410. 
12. Нгуен, Нян-Там; Нгуен, Трунг Тхань; Роос, Магнус; Роте, Йорг (2013). «Вычислительная сложность и аппроксимируемость оптимизации общественного благосостояния при распределении ресурсов с несколькими агентами». Автономные агенты и многоагентные системы . 28 (2): 256. doi :10.1007/s10458-013-9224-2. S2CID  442666.
13. Trung Thanh Nguyen; Jörg Rothe (2013). Оптимизация социального благосостояния по коэффициенту зависти и среднему Нэшу при распределении ресурсов с несколькими агентами . AAMAS 13.
14. Сандомирский, Федор; Сегал-Халеви, Эрель (май 2022 г.). «Эффективное справедливое разделение с минимальным разделением». Исследование операций . 70 (3): 1762–1782. arXiv : 1908.01669 . doi : 10.1287/opre.2022.2279. ISSN  0030-364X.
15. Goldberg, Paul W.; Hollender, Alexandros; Igarashi, Ayumi; Manurangsi, Pasin; Suksompong, Warut (2022). «Консенсусное деление пополам для наборов элементов». Математика исследования операций . 47 (4): 3357–3379. arXiv : 2007.06754 . doi : 10.1287/moor.2021.1249. S2CID  246764981.
16. Misra, Neeldhara; Sethia, Aditi (2021). «Справедливое разделение трудно даже для дружественных агентов». В Bureš, Tomáš; Dondi, Riccardo; Gamper, Johann; Guerrini, Giovanna; Jurdziński, Tomasz; Pahl, Claus; Sikora, Florian; Wong, Prudence WH (ред.). SOFSEM 2021: Теория и практика компьютерных наук . Конспект лекций по компьютерным наукам. Том 12607. Cham: Springer International Publishing. стр. 421–430. doi : 10.1007/978-3-030-67731-2_31. ISBN 978-3-030-67731-2.
17. Висмут, Самуэль; Макаров, Владислав; Сегал-Халеви, Эрель; Шапира, Дана (2023-11-08), Разбиение чисел с помощью расщепления , arXiv : 2204.11753
18. Бэй, Сяохуэй; Ли, Цзыхао; Лю, Шэнсинь; Лу, Синьхан (5 января 2021 г.). «Справедливое разделение смешанных делимых и неделимых товаров». Искусственный интеллект . 293 103436. Elsevier. arXiv : 1911.07048 . doi :10.1016/j.artint.2020.103436.
19. Бэй, Сяохуэй; Лю, Шэнсинь; Лу, Синьхан; Ван, Хунгао (30.06.2021). «Максимин справедливости со смешанными делимыми и неделимыми товарами». Автономные агенты и многоагентные системы . 35 (2): 34. arXiv : 2002.05245 . doi : 10.1007/s10458-021-09517-7. ISSN  1573-7454.
20. Бхаскар, Уманг; Шричаран, АР; Вайш, Рохит (2021). «О приблизительной свободе от зависти для неделимых домашних дел и смешанных ресурсов». DROPS-IDN/V2/Document/10.4230/LIPIcs.APPROX/RANDOM.2021.1 . Замок Дагштуль – Центр информатики им. Лейбница. doi : 10.4230/LIPIcs.APPROX/RANDOM.2021.1 .
21. Ли, Цзыхао; Лю, Шэнсинь; Лу, Синьхан; Тао, Бяошуай (2023-08-19). «Истинные справедливые механизмы распределения смешанных делимых и неделимых товаров». Труды тридцать второй Международной совместной конференции по искусственному интеллекту . IJCAI '23. Макао, Китайская Народная Республика. С. 2808–2816. doi :10.24963/ijcai.2023/313. ​​ISBN 978-1-956792-03-4.{{cite book}}: CS1 maint: location missing publisher (link)
22. Нисимура, Коичи; Сумита, Ханна (2023-08-13), Свобода от зависти и максимальное благосостояние Нэша для смешанных делимых и неделимых благ , arXiv : 2302.13342
23. Кавасэ, Ясуси; Нисимура, Коичи; Сумита, Ханна (2023-11-08), Справедливое распределение с бинарными оценками для смешанных делимых и неделимых товаров , arXiv : 2306.05986
24. Бэй, Сяохуэй; Лю, Шэнсинь; Лу, Синьхан (2023-10-02), Справедливое деление с субъективной делимостью , arXiv : 2310.00976
25. Ли, Бо; Ли, Цзыхао; Лю, Шэнсинь; У, Зекай (2024-04-28), Распределение смешанных товаров с настраиваемым коэффициентом справедливости и неделимости , arXiv : 2404.18132
26. Ли, Цзыхао; Лю, Шэнсинь; Лу, Синьхан; Тао, Бяошуай; Тао, Ичен (2024-01-02), Полный ландшафт по цене отсутствия зависти , arXiv : 2401.01516
27. Лю, Шэнсинь; Лу, Синьхан; Сузуки, Машбат; Уолш, Тоби (2024-03-24). «Смешанное справедливое разделение: обзор». Труды конференции AAAI по искусственному интеллекту . 38 (20): 22641–22649. arXiv : 2306.09564 . doi : 10.1609/aaai.v38i20.30274. ISSN  2374-3468.
28. Брамс, Стивен Дж.; Каплан, Тодд Р. (2004). «Разделение неделимого». Журнал теоретической политики . 16 (2): 143. doi : 10.1177/0951629804041118. hdl : 10036/26974 . S2CID  154854134.
29. Бабаиофф, Моше; Нисан, Ноам; Талгам-Коэн, Инбал (2017-03-23). ​​«Конкурентное равновесие с неделимыми товарами и общими бюджетами». arXiv : 1703.08150 [cs.GT].
30. Сегал-Халеви, Эрель (2018-07-09). «Конкурентное равновесие почти для всех доходов». Труды AAMAS 2018. Aamas '18. Международный фонд автономных агентов и многоагентных систем. С. 1267–1275.
31. Чакраборти, Митхун; Игараси, Аюми; Суксомпонг, Варут; Зик, Яир (16.08.2021). «Взвешенная свобода от зависти при распределении неделимых предметов». ACM Transactions on Economics and Computation . 9 (3): 18:1–18:39. arXiv : 1909.10502 . doi : 10.1145/3457166. ISSN  2167-8375. S2CID  202719373.
32. Чакраборти, Митхун; Шмидт-Крепелин, Ульрике; Суксомпонг, Варут (2021-12-01). "Выбор последовательностей и монотонность при взвешенном справедливом делении". Искусственный интеллект . 301 : 103578. arXiv : 2104.14347 . doi :10.1016/j.artint.2021.103578. ISSN  0004-3702. S2CID  233443832.
33. Чакраборти, Митхун; Сегал-Халеви, Эрел; Суксомпонг, Варут (28.06.2022). «Повторный взгляд на понятия взвешенной справедливости для неделимых предметов». Труды конференции AAAI по искусственному интеллекту . 36 (5): 4949–4956. arXiv : 2112.04166 . doi : 10.1609/aaai.v36i5.20425 . ISSN  2374-3468. S2CID  244954009.
34. Бабаиофф, Моше; Эзра, Томер; Файге, Уриэль (15.11.2021). «Справедливое распределение для агентов с произвольными правами». arXiv : 2103.04304 [cs.GT].
35. Сегал-Халеви, Эрел; Суксомпонг, Варут (2019-12-01). «Демократическое справедливое распределение неделимых благ». Искусственный интеллект . 277 : 103167. arXiv : 1709.02564 . doi : 10.1016/j.artint.2019.103167. ISSN  0004-3702. S2CID  203034477.
36. Garg, Jugal; Kulkarni, Pooja; Murhekar, Aniket (2021). Bojańczy, Miko\laj; Chekuri, Chandra (ред.). «О справедливом и эффективном распределении неделимых общественных благ». 41-я ежегодная конференция IARCS по основам программных технологий и теоретической информатики (FSTTCS 2021) . Leibniz International Proceedings in Informatics (LIPIcs). 213. Дагштуль, Германия: Schloss Dagstuhl – Leibniz-Zentrum für Informatik: 22:1–22:19. doi : 10.4230/LIPIcs.FSTTCS.2021.22 . ISBN 978-3-95977-215-0. S2CID  236154847.
37. Fain, Brandon; Munagala, Kamesh; Shah, Nisarg (2018-06-11). «Справедливое распределение неделимых общественных благ». Труды конференции ACM 2018 года по экономике и вычислениям . EC '18. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 575–592. doi :10.1145/3219166.3219174. ISBN 978-1-4503-5829-3. S2CID  3331859.
38. Конитцер, Винсент; Фримен, Руперт; Шах, Нисарг (2017). «Справедливое принятие государственных решений». В Daskalakis, Constantinos; Babaioff, Moshe; Moulin, Hervé (ред.). Труды конференции ACM 2017 года по экономике и вычислениям, EC '17, Кембридж, Массачусетс, США, 26-30 июня 2017 г. {ACM}. стр. 629–646. arXiv : 1611.04034 . doi :10.1145/3033274.3085125. ISBN 978-1-4503-4527-9.
39. Игараси, Аюми; Лакнер, Мартин; Нарди, Оливьеро; Новаро, Арианна (2023-04-04). «Повторное справедливое распределение неделимых предметов». arXiv : 2304.01644 [cs.GT].
40. Кавасэ, Ясуси; Сумита, Ханна (2020). «О справедливом стохастическом распределении неделимых благ по максимуму и минимуму». Труды конференции AAAI по искусственному интеллекту . 34 (2): 2070–2078. doi : 10.1609/AAAI.V34I02.5580 . S2CID  214407880.