Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

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

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

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

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

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

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

Для каждого агента с субаддитивной утилитой mFS стоит как минимум . Следовательно, каждое справедливое распределение mFS пропорционально. Для каждого агента с сверхаддитивными полезностями , ценности опознавателей MMSI самыми большим . Следовательно, каждое пропорциональное распределение является справедливым для 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 социальное обеспечение является продуктом полезностей агентов. Назначение, называемое оптимальным по Нэшу или максимальным благосостоянием по Нэшу, если оно максимизирует продукт полезности. Оптимальные по Нэшу распределения обладают некоторыми хорошими свойствами справедливости. [9]

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

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

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

  • Распределение предметов с максимальной долей ;
  • Пропорциональное распределение позиций ;
  • Распределение элементов с минимальной долей: задача вычисления mFS агента является полной для coNP . Проблема определения того, существует ли распределение mFS, существует , но его точная вычислительная сложность все еще неизвестна. [6]
  • Распределение предметов без зависти ;
  • Распределение эгалитарных предметов ;
  • Оптимальное по Нэшу распределение: [10] и [11] доказывают трудность вычисления утилитарно-оптимального и оптимального по Нэшу распределения. В [12] представлена ​​процедура аппроксимации оптимальных по Нэшу распределений.
  • Последовательность выбора: простой протокол, в котором агенты по очереди выбирают предметы на основе некоторой заранее заданной последовательности ходов. Цель состоит в том, чтобы разработать последовательность выбора таким образом, чтобы максимизировать ожидаемую ценность функции общественного благосостояния (например, эгалитарной или утилитарной) при некоторых вероятностных допущениях относительно оценок агентов.
  • Конкурентное равновесие: различные алгоритмы нахождения распределения CE описаны в статье о рынке Фишера .

Варианты и расширения [ править ]

Различные права [ править ]

В этом варианте разные агенты имеют право на разные доли ресурса. Распространенный вариант использования - разделение министерств между партиями коалиции. Принято считать, что каждая партия должна получать министерства в соответствии с количеством мест в парламенте. Соответственно необходимо адаптировать различные понятия справедливости. См [13] и [14] и [15] для обсуждения этой проблемы и некоторых решений.

Распределение по группам [ править ]

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

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

Принятие публичных решений [ править ]

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

См. Также [ править ]

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

Ссылки [ править ]

  1. ^ a b c Сильвен Бувере, Ян Шевалейр и Николя Моде, «Справедливое распределение неделимых благ». Глава 12 в: Брандт, Феликс; Конитцер, Винсент; Эндрисс, Улле; Ланг, Жером; Прокачча, Ариэль Д. (2016). Справочник по вычислительному социальному выбору . Издательство Кембриджского университета. ISBN 9781107060432.( бесплатная онлайн-версия )
  2. ^ Barberà, S .; Боссерт, В .; Паттанаик, П.К. (2004). «Ранжирование наборов предметов». (PDF) . Справочник по теории полезности . Springer США.
  3. ^ Сильвен Bouveret; Улле Эндрисс; Жером Ланг (2010). Справедливое разделение при порядковых предпочтениях: вычисление распределения неделимых товаров без зависти . Материалы конференции 2010 г. по ECAI 2010: 19-я Европейская конференция по искусственному интеллекту . Проверено 26 августа +2016 .
  4. ^ Брамс, Стивен Дж .; Эдельман, Пол Х .; Фишберн, Питер С. (2003). «Справедливое разделение неделимых предметов». Теория и решение . 55 (2): 147. DOI : 10,1023 / Б: THEO.0000024421.85722.0a .
  5. ^ Брамс, SJ (2005). «Эффективное справедливое разделение: помочь худшему или избежать зависти?». Рациональность и общество . 17 (4): 387–421. CiteSeerX 10.1.1.118.9114 . DOI : 10.1177 / 1043463105058317 . 
  6. ^ a b c d e Бувере, Сильвен; Лемэтр, Мишель (2015). «Характеристика конфликтов при справедливом разделении неделимых товаров по шкале критериев». Автономные агенты и мультиагентные системы . 30 (2): 259. DOI : 10.1007 / s10458-015-9287-3 .
  7. ^ Будит, E. (2011). «Комбинаторная проблема распределения: приблизительное конкурентное равновесие от равных доходов». Журнал политической экономии . 119 (6): 1061–1103. CiteSeerX 10.1.1.357.9766 . DOI : 10.1086 / 664613 . 
  8. ^ а б Хайнен, Тобиас; Нгуен, Нхан-Там; Роте, Йорг (2015). «Справедливость и взвешенный по рангам утилитаризм в распределении ресурсов». Теория алгоритмических решений . Конспект лекций по информатике. 9346 . п. 521. DOI : 10.1007 / 978-3-319-23114-3_31 . ISBN 978-3-319-23113-6.
  9. ^ a b Карагианнис, Иоаннис; Курокава, Дэвид; Мулен, Эрве; Procaccia, Ariel D .; Шах, Нисарг; Ван, Цзюньсин (2016). Необоснованная справедливость максимального благосостояния Нэша (PDF) . Труды конференции ACM по экономике и вычислениям 2016 года - EC '16. п. 305. DOI : 10,1145 / 2940716,2940726 . ISBN  9781450339360.
  10. ^ Нгуен, Чунг Тхань; Роос, Магнус; Роте, Йорг (2013). «Обзор приближаемости и неприемлемости результатов для оптимизации социального обеспечения при многоагентном распределении ресурсов». Анналы математики и искусственного интеллекта . 68 (1–3): 65–90. CiteSeerX 10.1.1.671.3497 . DOI : 10.1007 / s10472-012-9328-4 . 
  11. ^ Нгуен, Нхан-Там; Нгуен, Трунг Тхань; Роос, Магнус; Роте, Йорг (2013). «Вычислительная сложность и аппроксимируемость оптимизации социального обеспечения при многоагентном распределении ресурсов». Автономные агенты и мультиагентные системы . 28 (2): 256. DOI : 10.1007 / s10458-013-9224-2 .
  12. ↑ Trung Thanh Nguyen и Jörg Rothe (2013). Оптимизация социального благосостояния на основе зависти и среднего уровня при многоагентном распределении ресурсов . AAMAS 13.CS1 maint: использует параметр авторов ( ссылка )
  13. ^ Брамс, Стивен Дж .; Каплан, Тодд Р. (2004). «Разделение неделимого». Журнал теоретической политики . 16 (2): 143. DOI : 10,1177 / 0951629804041118 . S2CID 154854134 . 
  14. ^ Бабайофф, Моше; Нисан, Ноам; Талгам-Коэн, Инбал (23.03.2017). «Конкурентное равновесие с неделимыми товарами и общими бюджетами». arXiv : 1703.08150 [ cs.GT ].
  15. ^ Segal-Галеви, Эрэл (2018-07-09). «Конкурентное равновесие почти для всех доходов» . Материалы AAMAS 2018 . Aamas '18. Международный фонд автономных агентов и многоагентных систем. С. 1267–1275.
  16. ^ Сегал-Халеви, Эрель; Суксомпонг, Варут (01.12.2019). «Демократическое справедливое размещение неделимых товаров». Искусственный интеллект . 277 : 103167. arXiv : 1709.02564 . DOI : 10.1016 / j.artint.2019.103167 . ISSN 0004-3702 . S2CID 203034477 .  
  17. ^ Конитцер, Винсент; Фриман, Руперт; Шах, Нисарг (2016). "Принятие справедливых общественных решений | Материалы конференции ACM по экономике и вычислениям 2017 г.". arXiv : 1611.04034 . DOI : 10.1145 / 3033274.3085125 . S2CID 30188911 .  Цитировать журнал требует |journal=( помощь )