Проблема распределения домов

В экономике и информатике проблема распределения домов — это проблема распределения объектов между людьми с разными предпочтениями , так что каждый человек получает ровно один объект. Название «распределение домов» происходит от основного мотивирующего приложения, которое заключается в распределении общежитий среди студентов. ^[1] Другими часто используемыми терминами являются проблема распределения и одностороннее сопоставление . Когда агенты уже владеют домами (и могут обмениваться ими с другими агентами), проблему часто называют рынком жилья . ^[2] В задачах распределения домов предполагается, что денежные переводы не допускаются; вариант, в котором денежные переводы допускаются, известен как гармония аренды .

Определения

Есть n людей (также называемых: агентами ) и m объектов (также называемых: домами ). Агенты могут иметь различные предпочтения относительно домов. Они могут выражать свои предпочтения различными способами:

• Бинарные оценки : каждый агент оценивает каждый дом либо как 1 (что означает, что агенту нравится дом), либо как 0 (что означает, что агенту не нравится дом).
• Рейтинг предпочтений : каждый агент ранжирует дома от лучшего к худшему. Рейтинг может быть строгим (без безразличия) или слабым (безразличие допускается).
• Кардинальная полезность : каждый агент присваивает каждому дому неотрицательное числовое значение.

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

• Эффективность по Парето (PE) — никакое другое распределение не является лучшим для некоторых агентов и не хуже для всех агентов.
• Справедливость — может быть определена по-разному, например, как отсутствие зависти (EF) — ни один агент не должен завидовать другому агенту.
• Стратегическая защищенность (SP) — у каждого агента есть стимул сообщать алгоритму о своих истинных предпочтениях.
• Индивидуальная рациональность (ИР) — ни один агент не должен проиграть от участия в алгоритме.

Эффективное распределение

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

Вероятно, самым простым алгоритмом распределения домов является последовательная диктатура : агенты упорядочиваются в некотором произвольном порядке (например, по старшинству), и каждый агент по очереди выбирает лучший оставшийся дом по своим предпочтениям. Этот алгоритм, очевидно, SP. Если предпочтения агентов строгие, то он находит распределение PE. Однако это может быть очень несправедливо по отношению к агентам, которые выбирают последними. Его можно сделать более справедливым (в ожидании), выбрав порядок равномерно случайным образом; это приводит к механизму, называемому случайной последовательной диктатурой . Механизм является PE ex-ante, но это не PE ex-ante; см. справедливое случайное назначение для других рандомизированных механизмов, которые являются ex-ante PE.

Когда каждый агент уже владеет домом, соображения справедливости менее важны, более важно гарантировать агентам, что они не потеряют от участия (IR). Алгоритм верхнего торгового цикла — это уникальный алгоритм, который гарантирует IR, PE и SP. При строгих предпочтениях TTC находит уникальное распределение core-stable . ^[3]

Абдулкадироглу и Сёнмез ^[1] рассматривают расширенную установку, в которой некоторые агенты уже владеют домом, а некоторые другие не имеют дома. Их механизм — IR, PE и SP. Они представляют два алгоритма, реализующих этот механизм.

Эргин ^[4] рассматривает правила, которые также являются последовательными , то есть их предсказания не зависят от порядка, в котором выполняются назначения.

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

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

Алгоритмические проблемы, связанные с честностью сопоставления, изучались в нескольких контекстах.

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

• Определение того, существует ли полное распределение EF . Это выполняется, если и только если существует соответствие, которое насыщает всех агентов; это можно решить за полиномиальное время, просто найдя максимальное кардинальность соответствия в двудольном графе.
• Нахождение частичного распределения EF максимальной мощности. Айгнер-Хорев и Сигал-Халеви ^{[5] : Теория 1.6(a)} представляют поливременной алгоритм.
• Поиск частичного распределения EF с максимальной мощностью и минимальной стоимостью (где каждое ребро имеет заранее определенную стоимость для общества). Айгнер-Хорев и Сигал-Халеви ^{[5] : Теория 1.6(b)} представляют поливременной алгоритм.
• Поиск полного распределения EF , в котором число завистливых агентов сведено к минимуму. Камияма, Манурангси и Суксомпонг ^{[6] : Теория 3.5} доказывает, что это NP-трудно. Доказательство основано на сокращении из задачи минимального покрытия (также известной как двудольное расширение ). Мадатил, Мисра и Сетия ^[7] доказывают, что это NP-трудно, даже если каждый агент оценивает не более 2 домов, и W[1]-трудно, если параметризовано числом завистливых агентов. Доказательство основано на сокращении из задачи максимальной клики . Однако эта задача является разрешимой с фиксированными параметрами , если параметризована общим числом типов домов и типов агентов , и может быть решена эффективно, если у агентов есть предпочтения «экстремальных интервалов».
• Поиск полного распределения EF , в котором максимальное количество агентов, которым завидует один агент, минимизировано. Мадатил, Мисра и Сетия ^[7] доказывают, что это NP-трудно, даже когда каждый агент оценивает не более 2 домов, каждый дом одобрен постоянным числом агентов, а максимально допустимая зависть равна всего 1. Доказательство проводится путем редукции из максимального независимого множества на кубических графах. Однако проблема является разрешимой с фиксированными параметрами , когда параметризована общим числом типов домов и типов агентов , и может быть решена эффективно, когда у агентов есть предпочтения «экстремальных интервалов».

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

• Принятие решения о том, существует ли полное распределение EF .
  • Когда m = n , все дома должны быть назначены, поэтому распределение является EF, если и только если каждый агент получает дом с наивысшей стоимостью. Таким образом, можно свести исходный граф к невзвешенному графу, в котором каждый агент соседствует только со своими домами с наивысшей стоимостью, и искать идеальное соответствие в этом графе.
  • Когда m > n , приведенный выше алгоритм может не работать, поскольку не все дома должны быть назначены: даже если один дом является наиболее предпочтительным для всех агентов, может существовать полное распределение EF, в котором этот конкретный дом не назначен. Ган, Суксомпонг и Вудурис ^[8] представляют полиномиальный алгоритм, который за полиномиальное время решает, существует ли полное распределение EF для любого m ≥ n . Их алгоритм использует в качестве подпрограммы алгоритм для поиска минимального по включению нарушителя Холла .
• Определение того, существует ли полное локально-свободное от зависти распределение. Локальное отсутствие зависти означает, что агенты находятся в социальной сети и завидуют только своим соседям в этой сети. Бейнье, Шевалейр, Гурв, Арутюнян, Леска, Моде и Вильчинский ^[9] изучают проблему определения того, существует ли полное локально-свободное от зависти распределение при m = n для различных сетевых структур.
• Нахождение полного распределения EF , в котором число независтливых агентов максимизировано. Камияма, Манурангси и Суксомпонг. ^{[6] : Теория 3.1} доказывает, что при общем предположении теории сложности эту задачу трудно аппроксимировать. В частности, если NP не может быть решена за субэкспоненциальное время, то ее нельзя аппроксимировать с точностью до множителя для некоторого ; если гипотеза о малом расширении множества верна, то ее нельзя аппроксимировать с точностью до множителя для любого (поскольку аппроксимировать тривиально: просто дайте одному агенту его любимый дом и распределите других агентов произвольно). Доказательство заключается в редукции из задачи о максимально сбалансированной биклике . ${\displaystyle n^{\gamma }}$ ${\displaystyle \gamma >0}$ ${\displaystyle n^{\gamma }}$ ${\displaystyle \gamma <1}$ ${\displaystyle \gamma =1}$
• Определение того, существует ли полное пропорциональное распределение . Камияма, Манурангси и Суксомпонг ^{[6] : Теория 4.1} доказывает, что оно является NP-полным, путем редукции из точного покрытия из 3 множеств .
• Решение о том, существует ли полное справедливое распределение . Камияма, Манурангси и Суксомпонг ^{[6] : Теория 5.1} представляет поливременной алгоритм.
• Поиск частичного распределения EF максимальной мощности. Сложность выполнения этой проблемы открыта. ^{[5] : открытый вопрос 2}

Связанные проблемы

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

Ссылки

1. Abdulkadiroğlu, Atila; Sönmez, Tayfun (1999-10-01). «Распределение жилья с существующими арендаторами». Журнал экономической теории . 88 (2): 233–260. doi : 10.1006/jeth.1999.2553 . ISSN  0022-0531.
2. Азиз, Харис; Кейзер, Барт де (2012). «Рынки жилья с безразличием: история двух механизмов». Труды конференции AAAI по искусственному интеллекту . 26 (1): 1249–1255. doi : 10.1609/aaai.v26i1.8239 . ISSN  2374-3468. S2CID  15395473.
3. Рот, Элвин Э. (1982-01-01). «Совместимость стимулов на рынке с неделимыми товарами». Economics Letters . 9 (2): 127–132. doi :10.1016/0165-1765(82)90003-9. ISSN  0165-1765.
4. Эргин, Халук И. (2000-08-01). «Согласованность в задачах распределения домов». Журнал математической экономики . 34 (1): 77–97. doi :10.1016/S0304-4068(99)00038-5. hdl : 11693/18154 . ISSN  0304-4068.
5. Segal-Halevi, Erel; Aigner-Horev, Elad (2022). «Сочетания без зависти в двудольных графах и их применение к справедливому делению». Information Sciences . 587 : 164–187. arXiv : 1901.09527 . doi :10.1016/j.ins.2021.11.059. S2CID  170079201.
6. Камияма, Наоюки; Манурангси, Пасин; Суксомпонг, Варут (2021-07-01). «О сложности справедливого распределения домов». Operations Research Letters . 49 (4): 572–577. arXiv : 2106.06925 . doi : 10.1016/j.orl.2021.06.006. ISSN  0167-6377. S2CID  235422019.
7. Madathil, Jayakrishnan; Misra, Neeldhara; Sethia, Aditi (2023-05-30). «Сложность минимизации зависти при распределении жилья». Труды Международной конференции 2023 года по автономным агентам и многоагентным системам . AAMAS '23. Richland, SC: Международный фонд автономных агентов и многоагентных систем: 2673–2675. ISBN 978-1-4503-9432-1.
8. Ган, Цзяруй; Суксомпонг, Варут; Вудурис, Александрос А. (01 сентября 2019 г.). «Свобода от зависти в вопросах распределения жилья». Математические социальные науки . 101 : 104–106. arXiv : 1905.00468 . doi :10.1016/j.mathsocsci.2019.07.005. ISSN  0165-4896. S2CID  143421680.
9. Бенье, Орели; Шевалейр, Янн; Гурвес, Лоран; Арутюнян, Арарат; Леска, Жюльен; Моде, Николя; Вильчинский, Анаэль (01 сентября 2019 г.). «Местная свобода от зависти в вопросах распределения жилья». Автономные агенты и мультиагентные системы . 33 (5): 591–627. дои : 10.1007/s10458-019-09417-x. ISSN  1573-7454. S2CID  51869987.