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

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

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

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

Проблема назначения элементов состоит из нескольких компонентов:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Свобода от зависти (EF)

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

К более слабым версиям EF относятся:

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

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

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

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

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

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

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

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

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

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

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

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

Ограничение количества обмена

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

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

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

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

Смешение делимых и неделимых благ

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

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

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

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

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

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

• Представления, основанные на взвешенном конкурентном равновесии;
• Представления, основанные на взвешенной свободе от зависти;
• Понятия, основанные на взвешенной справедливой доле;

См. Также: Пропорциональное разрезание торта с различными льготами.

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

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

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

См. Также: Справедливое разделение между группами.

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

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

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

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

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

Принятие публичных решений

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

См. Также: голосование по нескольким вопросам.

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

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

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

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

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

${\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]\}$

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

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

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

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

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

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

• Утилитарное правило : это правило гласит, что общество должно выбирать решение, максимизирующее сумму полезностей. То есть, чтобы выбрать стохастическое распределение $d^{*}\in {\mathcal {D}}$ это максимизирует утилитарную выгоду : $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)$Кавасе и Сумита показать, что максимизация утилитарного благосостояния в стохастической ситуации всегда может быть достигнута с помощью детерминистического распределения . Причина в том, что утилитарная ценность детерминированного распределения $A^{*}={\underset {A\in {\mathcal {A}}\colon p_{d^{*}}(A)>0}{\operatorname {argmax} }}\sum _{i=1}^{n}u_{i}(A)$ это, по крайней мере, утилитарная ценность $d^{*}$: $\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)$
• Эгалитарное правило: это правило гласит, что общество должно выбирать решение, которое максимизирует полезность беднейших слоев населения. То есть, чтобы выбрать стохастическое распределение $d^{*}\in {\mathcal {D}}$ это максимизирует эгалитарную войну : $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 .
  • Твердость: Кавасе и Сумита. доказать, что найти стохастическое распределение, которое максимизирует эгалитарное благосостояние , NP-трудно, даже если все полезности агентов являются аддитивными к бюджету ; а также, что NP-трудно приблизить эгалитарное благосостояние к фактору лучше, чем $1-{\tfrac {1}{e}}$ даже если все агенты имеют одну и ту же субмодульную функцию полезности .
  • Алгоритм: Кавасе и Сумита представить алгоритм, который, учитывая алгоритм поиска детерминистического распределения, которое приближает утилитарное благосостояние к фактору α , находит стохастическое распределение, которое приближает эгалитарное благосостояние к тому же фактору α .

См. также

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