Справедливое распределение предметов - Fair item allocation

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Чтобы упростить задачу назначения элементов, принято считать, что все элементы независимые товары (так что они не товары-заменители ни дополнительные товары ). [3]Потом:

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

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

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

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

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

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

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

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

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

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

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

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

Всего 3 агента и 3 предмета:
  • Алиса оценивает элементы как 2,2,2. Для нее MMS = PFS = mFS = 2.
  • Боб оценивает элементы как 3,2,1. Для него MMS = 1, PFS = 2 и mFS = 3.
  • Карл оценивает предметы как 3,2,1. Для него MMS = 1, PFS = 2 и mFS = 3.
Возможные распределения следующие:
  • Каждое распределение, которое дает товар каждому агенту, является MMS-ярмаркой.
  • Каждое распределение, которое дает первый и второй элементы Бобу и Карлу, а третье - Алисе, пропорционально.
  • Распределение не является справедливым для mFS.

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

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

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

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

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

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

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

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

  • В эгалитарный социальное благосостояние - это минимальная полезность одного агента. Назначение элемента называется эгалитарно-оптимальный если он достигает максимально возможного эгалитарного благополучия, т.е. максимизирует полезность самого бедного агента. Поскольку может быть несколько разных распределений, максимизирующих наименьшую полезность, эгалитарная оптимальность часто уточняется до лексимин-оптимальность: из подмножества распределений, максимизирующих наименьшую полезность, он выбирает те распределения, которые максимизируют вторую по величине полезность, затем третью по величине полезность и т. д.
  • В Нэш социальное благосостояние - это продукт полезности агентов. Задание под названием Оптимальный по Нэшу или же Максимум-Nash-Welfare если он максимизирует продукт коммунальных услуг. Оптимальные по Нэшу распределения обладают некоторыми хорошими свойствами справедливости.[9]

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

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

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

Основная статья: Максимин-доля

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

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

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

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

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

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

Задача расчета mFS агента заключается в следующем: coNP-Complete.

Проблема определения того, существует ли распределение mFS, заключается в , но его точная вычислительная сложность пока неизвестна.[6]

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

Основная статья: распределение предметов без зависти

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

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

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

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

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

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

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

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

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

[17] и [18] доказать трудность расчета утилитарно-оптимальных и оптимальных по Нэшу распределений.

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

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

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

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

Разные права

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

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

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

Рекомендации

  1. ^ а б c Сильвен Бувере, Ян Шевалейр и Николя Моде, «Справедливое распределение неделимых благ». Глава 12 в: Брандт, Феликс; Конитцер, Винсент; Эндрисс, Улле; Ланг, Жером; Прокачча, Ариэль Д. (2016). Справочник по вычислительному социальному выбору. Издательство Кембриджского университета. ISBN  9781107060432. (бесплатная онлайн-версия )
  2. ^ Barberà, S .; Боссерт, В .; Паттанаик, П. К. (2004). «Ранжирование наборов предметов». (PDF). Справочник по теории полезности. Springer США.
  3. ^ Сильвен Бувере; Улле Эндрисс; Жером Ланг (2010). Справедливое разделение при порядковых предпочтениях: расчет распределения неделимых товаров без зависти. Материалы конференции 2010 г. по ECAI 2010: 19-я Европейская конференция по искусственному интеллекту. Получено 26 августа 2016.
  4. ^ Брамс, Стивен Дж .; Эдельман, Пол Х .; Фишберн, Питер С. (2003). «Справедливое разделение неделимых предметов». Теория и решение. 55 (2): 147. Дои:10.1023 / B: THEO.0000024421.85722.0a.
  5. ^ Брамс, С. Дж. (2005). «Эффективное справедливое разделение: помочь худшему или избежать зависти?». Рациональность и общество. 17 (4): 387–421. CiteSeerX  10.1.1.118.9114. Дои:10.1177/1043463105058317.
  6. ^ а б c d е ж Бувере, Сильвен; Лемэтр, Мишель (2015). «Характеризация конфликтов при справедливом разделении неделимых товаров по шкале критериев». Автономные агенты и мультиагентные системы. 30 (2): 259. Дои:10.1007 / s10458-015-9287-3.
  7. ^ Будиш, Э. (2011). "Комбинаторная проблема распределения: приблизительное конкурентное равновесие от равных доходов". Журнал политической экономии. 119 (6): 1061–1103. CiteSeerX  10.1.1.357.9766. Дои:10.1086/664613.
  8. ^ а б Хайнен, Тобиас; Нгуен, Нхан-Там; Роте, Йорг (2015). «Справедливость и взвешенный по рангам утилитаризм в распределении ресурсов». Теория алгоритмических решений. Конспект лекций по информатике. 9346. п. 521. Дои:10.1007/978-3-319-23114-3_31. ISBN  978-3-319-23113-6.
  9. ^ а б Карагианнис, Иоаннис; Курокава, Дэвид; Мулен, Эрве; Procaccia, Ariel D .; Шах, Нисарг; Ван, Цзюньсин (2016). Необоснованная справедливость максимального благосостояния Нэша (PDF). Труды конференции ACM по экономике и вычислениям 2016 г. - EC '16. п. 305. Дои:10.1145/2940716.2940726. ISBN  9781450339360.
  10. ^ а б Азиз, Харис; Гасперс, Серж; Маккензи, Саймон; Уолш, Тоби (2015). «Справедливое присвоение неделимых объектов по порядковым предпочтениям». Искусственный интеллект. 227: 71–92. arXiv:1312.6546. Дои:10.1016 / j.artint.2015.06.002.
  11. ^ Прухс, Кирк; Woeginger, Герхард Дж. (2012). «Легкий развод». Развлечение с алгоритмами. Конспект лекций по информатике. 7288. п. 305. Дои:10.1007/978-3-642-30347-0_30. ISBN  978-3-642-30346-3.
  12. ^ Деманж Г., Гейл Д., Сотомайор М. (1986). «Многопозиционные аукционы». Журнал политической экономии. 94 (4): 863–872. Дои:10.1086/261411. JSTOR  1833206.
  13. ^ Муалем А (2014). «Ярмарка по замыслу: многомерные механизмы без зависти». Игры и экономическое поведение. 88: 29–46. Дои:10.1016 / j.geb.2014.08.001.
  14. ^ Руджеро Кавалло (2012). Справедливость и благосостояние через перераспределение при передаче полезности (PDF). AAAI-12.
  15. ^ Бейли, Мартин Дж. (1997). «Процесс выявления спроса: распределить излишки». Общественный выбор. 91 (2): 107–126. Дои:10.1023 / А: 1017949922773.
  16. ^ Кавалло, Руджеро (2006). «Принятие оптимальных решений с минимальными отходами». Материалы пятой международной совместной конференции по автономным агентам и мультиагентным системам - AAMAS '06. п. 882. Дои:10.1145/1160633.1160790. ISBN  1595933034.
  17. ^ Нгуен, Трунг Тхань; Роос, Магнус; Роте, Йорг (2013). «Обзор приближаемости и несовместимости результатов для оптимизации социального обеспечения при многоагентном распределении ресурсов». Анналы математики и искусственного интеллекта. 68 (1–3): 65–90. CiteSeerX  10.1.1.671.3497. Дои:10.1007 / s10472-012-9328-4.
  18. ^ Нгуен, Нхан-Там; Нгуен, Чунг Тхань; Роос, Магнус; Роте, Йорг (2013). «Вычислительная сложность и аппроксимируемость оптимизации социального обеспечения при многоагентном распределении ресурсов». Автономные агенты и мультиагентные системы. 28 (2): 256. Дои:10.1007 / s10458-013-9224-2.
  19. ^ Трунг Тхань Нгуен и Йорг Роте (2013). Оптимизация социального обеспечения на основе зависти и среднего уровня при многоагентном распределении ресурсов. AAMAS 13.CS1 maint: использует параметр авторов (связь)
  20. ^ Брамс, Стивен Дж .; Каплан, Тодд Р. (2004). «Разделение неделимого». Журнал теоретической политики. 16 (2): 143. Дои:10.1177/0951629804041118. S2CID  154854134.
  21. ^ Бабайофф, Моше; Нисан, Ноам; Талгам-Коэн, Инбал (23.03.2017). «Конкурентное равновесие с неделимыми товарами и общими бюджетами». arXiv:1703.08150 [cs.GT ].
  22. ^ Сегал-Халеви, Эрель (9.07.2018). «Конкурентное равновесие почти для всех доходов». Труды AAMAS 2018. Aamas '18. Международный фонд автономных агентов и многоагентных систем. С. 1267–1275.