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

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

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

Особый случай, в котором ценность каждого предмета j для каждого агента равна либо 0, либо некоторой константе v _j, называется проблемой Санта-Клауса : у Санта-Клауса есть фиксированный набор подарков, и он хочет распределить их между детьми таким образом, чтобы наименее счастливый ребенок был максимально счастлив.

Вот некоторые связанные с этим проблемы:

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

Нормализация

Существует два варианта эгалитарного правила: ^[1]

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

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

Точные алгоритмы

Хотя общая задача является NP-трудной, небольшие примеры можно решить точно с помощью методов программирования в ограничениях .

• Бувере и Леметр представляют пять различных алгоритмов для поиска лексимин -оптимальных решений для дискретных задач удовлетворения ограничений. ^[2] Они представляют распределение элементов по максимуму и минимуму как особый случай.
• Далл'Альо и Моска ^[3] предложили точный алгоритм ветвей и границ для двух агентов, основанный на адаптации процедуры скорректированного победителя .

Рандомизированные алгоритмы

Демко и Хилл ^[4] представляют рандомизированный алгоритм, который обеспечивает равноправное распределение предметов в ожидании.

Алгоритмы аппроксимации

Ниже n — количество агентов, m — количество элементов.

Для частного случая задачи о Санта-Клаусе:

• Бансал и Свириденко ^[5] предложили алгоритм аппроксимации, основанный на округлении линейной программы . ${\displaystyle O(\log {\log {n}}/\log {\log {\log {n}}})}$
• Фейге ^[6] доказал, что существует алгоритм аппроксимации с постоянным множителем и полиномиальным временем, но доказательство использовало локальную лемму Ловаса и было неконструктивным.
• Асадпур, Фейге и Сабери ^[7] дали фактический алгоритм аппроксимации с постоянным множителем, используя сопоставление гиперграфов . Они не смогли доказать, что он сходится за конечное число шагов.
• Аннамалай, Калаитзис и Свенссон ^[8] предложили 13-аппроксимационный алгоритм с полиномиальным временем выполнения.
• Дэвис, Ротвосс и Чжан ^[9] улучшили коэффициент аппроксимации до 4, введя ограничения матроида в базовую линейную программу .

В общем случае для агентов с аддитивными оценками :

• Безакова и Дани ^[10] представили два алгоритма. Первый дает -факторное приближение к оптимальному эгалитарному значению. Второй находит распределение, которое является эгалитарным с точностью до одного блага, то есть каждый агент получает свою ценность в оптимальном эгалитарном распределении за вычетом максимум одного элемента. Их алгоритм основан на предыдущем алгоритме Ленстры, Шмойса и Тардоса ^[11] , который по сути находит распределение, которое является эгалитарным с точностью до одной работы . Оба алгоритма основаны на схожей идее. Они находят базовое допустимое решение линейной программы для нахождения дробного эгалитарного распределения и округляют его таким образом, что каждый агент теряет максимум одно благо или получает максимум одну работу. ${\displaystyle (m-n+1)}$
• Асадпур и Сабери ^[12] дали алгоритм -аппроксимации. Их алгоритм использует итеративный метод округления дробного соответствия на дереве . Они также обеспечивают лучшие границы, когда разрешено исключить небольшую часть людей из задачи. ${\displaystyle O({\sqrt {n}}\cdot \log ^{3}n)}$

• Чакрабарти, Чузой и Кханна ^[13] дали алгоритм аппроксимации с временем выполнения , для любого . Для особого случая, в котором каждый элемент имеет ненулевую полезность для максимум двух агентов, они дали алгоритм аппроксимации с 2 факторами и доказали, что его трудно аппроксимировать к какому-либо лучшему фактору. ${\displaystyle O(m^{\varepsilon })}$ ${\displaystyle O(m^{1/\varepsilon })}$ ${\displaystyle \varepsilon \in \Omega \left({\frac {\log \log m}{\log m}}\right)}$
• Головин ^[14] дал алгоритм, по которому для каждого целого числа часть агентов получает полезность не менее . Этот результат получен округлением подходящей релаксации линейного программирования задачи и является наилучшим возможным результатом для этой линейной программы. Он также дал алгоритм -аппроксимации для особого случая с двумя классами товаров. ${\displaystyle k}$ ${\displaystyle (1-1/k)}$ ${\displaystyle OPT/k}$ ${\displaystyle O({\sqrt {n}})}$
• Когда число агентов постоянно, существует FPTAS с использованием техники Вёгингера . ^[15]

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

• Головин ^[14] дал алгоритм аппроксимации и некоторые результаты о неприближенности для общих функций полезности. ${\displaystyle (m-n+1)}$
• Гоэманс, Харви, Ивата и Мирркони ^[16] предлагают алгоритм аппроксимации ${\displaystyle O({\sqrt {m}}\cdot n^{1/4}\cdot \log n\cdot \log ^{3/2}m)}$
• Нгуен, Рус и Роте ^{[17] [18]} представили некоторые более высокие результаты по твердости.

Обычно эгалитарные распределения

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

1. Предположим, что агенты имеют порядковый рейтинг по набору наборов . Для любого дискретного распределения для любого агента i определим r ( i ) как ранг набора агента i, так что r(i)=1, если я получил его лучший набор, r(i)=2, если я получил его второй лучший набор и т. д. Этот r является вектором размера n (число агентов). Порядково-эгалитарное распределение — это распределение, которое минимизирует наибольший элемент в r. Процедура снижения спроса находит порядково-эгалитарное распределение для любого числа агентов с любым порядком наборов.

2. Предположим, что агенты имеют порядковый рейтинг по набору элементов . При любом дискретном или дробном распределении для любого агента i и положительного целого числа k определите t ( i , k ) как общую долю, которую агент i получает от своих k самых верхних классов безразличия. Это t является вектором размером не более n * m , где n — количество агентов, а m — количество элементов. Порядково-эгалитарное распределение — это распределение, которое максимизирует вектор t в лексиминном порядке. Алгоритм одновременного приема пищи с равными скоростями приема пищи — это уникальное правило, которое возвращает порядково-эгалитарное распределение. ^[19]

Сравнение с другими критериями справедливости

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

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

Отсутствие зависти

1. Когда все агенты имеют одинаковые оценки с ненулевой предельной полезностью, любое распределение относительного лексимина равно PO и EFX .

• Улучшение лексимина, называемое лексимин++, гарантирует EFX (но не PO) с общими идентичными оценками. ^[20]

2. Для двух агентов с аддитивными оценками любое распределение относительного лексимина равно EF1. ^{[20] : Теор.5.5} Однако:

• Распределение абсолютного лексимина может не быть EF1 даже для двух агентов с аддитивными оценками. Например, предположим, что есть четыре товара и два агента, которые оценивают их в {0,1,1,1} и {3,3,3,3}. Уникальное распределение абсолютного лексимина дает {1,1,1} первому агенту и {3} второму агенту, но тогда второй агент завидует. ^{[21] : 32}
• Относительное распределение лексимина может не быть EF1 для трех или более агентов. Например, предположим, что есть четыре товара и три агента, которые оценивают их в {30,0,0,0} {20,5,5,0} и {0,12,12,6}. Обратите внимание, что оценки нормализованы (общая стоимость равна 30). При распределении лексимина первый товар должен быть распределен агенту 1. Затем второй и третий товары должны быть распределены агенту 2, а товар остается для агента 3. Но затем агент 3 завидует агенту 2 даже после удаления элемента. ^{[22] : 22}

3. Когда все агенты имеют оценки, которые являются функциями ранга матроида (т.е. субмодулярными с бинарными маргиналами), набор распределений абсолютного лексимина эквивалентен набору распределений максимального продукта; все такие распределения являются максимальными суммами и EF1. ^[21]

4. В контексте неделимого распределения домашних дел (элементов с отрицательной полезностью) с 3 или 4 агентами с аддитивными оценками любое лексимин-оптимальное распределение — это PROP1 и PO; с n агентами с общими идентичными оценками любое лексимин-оптимальное распределение — это EFX. ^[23]

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

Когда все агенты имеют одинаковые оценки, эгалитарное распределение, по определению, дает каждому агенту по крайней мере его/ее максиминную долю.

Однако, когда у агентов разные оценки, проблемы различны. Распределение максиминной доли — это проблема удовлетворения: цель — гарантировать, что каждый агент получит ценность выше порога идентичных оценок. Напротив, эгалитарное распределение — это проблема оптимизации: цель — дать каждому агенту как можно большую ценность. В некоторых случаях результирующие распределения могут сильно отличаться. Например, предположим, что есть четыре товара и три агента, которые оценивают их в {3,0,0,0}, {3-2 ε,ε,ε ,0} и {1-2 ε ,1,1,2 ε } (где ε — небольшая положительная константа). Обратите внимание, что оценки нормализованы (общее значение равно 3), поэтому абсолютный лексимин и относительный лексимин эквивалентны.

• Распределение лексимина дает профиль полезности (3, 2ε, 2ε ): первый элемент должен достаться агенту 1, в противном случае наименьшая полезность равна 0. Затем второй и третий элементы должны достаться агенту 2, в противном случае следующая наименьшая полезность равна ε или меньше; поэтому агент 3 получает только последний элемент.
• Максиминные значения долей агентов равны 0, ε , 1. Следовательно, распределение максиминной доли должно предоставить агенту 3 один из первых трех пунктов; некоторые возможные профили полезности в этом случае равны (0, 2ε , 1) или (3, ε , 1+ 2ε ).

Пример можно расширить до 1-из- k MMS для любого k >3. Есть k +1 товар и три агента, которые оценивают их в { k , 0, ..., 0}, { k- ( k -1) ε , ε, ..., ε , 0} и {1- kε , 1, 1, ..., kε } . Профиль полезности лексимина должен быть ( k , kε, kε ), в то время как 1-из- k MMS агента 3 равен 1.

Реальное применение

Правило лексимина использовалось для справедливого распределения неиспользуемых классных комнат в государственных школах среди чартерных школ. ^[24]

Ссылки

1. Сегал-Халеви, Эрель; Шиклай, Балаж Р. (01 сентября 2019 г.). «Монотонность и конкурентное равновесие в разрезании тортов». Экономическая теория . 68 (2): 363–401. arXiv : 1510.05229 . дои : 10.1007/s00199-018-1128-6. ISSN  1432-0479. S2CID  179618.
2. Бувере, Сильвен; Леметр, Мишель (01 февраля 2009 г.). «Вычисление лексимин-оптимальных решений в сетях ограничений». Искусственный интеллект . 173 (2): 343–364. дои : 10.1016/j.artint.2008.10.010 . ISSN  0004-3702.
3. Далл'Альо, Марко; Моска, Рафаэле (2007). «Как справедливо распределить леденцы». Математические социальные науки . 54 (3): 218. CiteSeerX 10.1.1.330.2617 . doi :10.1016/j.mathsocsci.2007.04.008. 
4. Демко, Стивен; Хилл, Теодор П. (1988-10-01). «Справедливое распределение неделимых объектов». Математические социальные науки . 16 (2): 145–158. doi :10.1016/0165-4896(88)90047-9. ISSN  0165-4896.
5. Бансал, Нихил; Свириденко, Максим (2006). "Проблема Санта-Клауса". Труды тридцать восьмого ежегодного симпозиума ACM по теории вычислений - STOC '06 . стр. 31. doi :10.1145/1132516.1132522. ISBN 1595931341.
6. Фейге, Уриэль (2008-01-20). «О распределениях, которые максимизируют справедливость». Труды девятнадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . SODA '08. Сан-Франциско, Калифорния: Общество промышленной и прикладной математики: 287–293.
7. Asadpour, Arash; Feige, Uriel; Saberi, Amin (2008). "Santa Claus Meets Hypergraph Matchings". В Goel, Ashish; Jansen, Klaus; Rolim, José DP; Rubinfeld, Ronitt (ред.). Approximation, Randomization and Combinatory Optimization. Algorithms and Techniques . Lecture Notes in Computer Science. Vol. 5171. Berlin, Heidelberg: Springer. pp. 10–20. doi :10.1007/978-3-540-85363-3_2. ISBN 978-3-540-85363-3.
8. Аннамалай, Чидамбарам; Калаитзис, Христос; Свенссон, Ола (2017-05-26). «Комбинаторный алгоритм для ограниченного справедливого распределения Max-Min». ACM Transactions on Algorithms . 13 (3): 37:1–37:28. arXiv : 1409.0607 . doi : 10.1145/3070694. ISSN  1549-6325. S2CID  14749011.
9. Дэвис, Сами; Ротвосс, Томас; Чжан, Ихао (18 июля 2018 г.). Сказка о Санта-Клаусе, гиперграфах и матроидах . Труды четырнадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам. Общество промышленной и прикладной математики, 2020. стр. 2748–2757. doi :10.1137/1.9781611975994.
10. Bezáková, Ivona; Dani, Varsha (2005). «Распределение неделимых товаров». ACM SIGecom Exchanges . 5 (3): 11. CiteSeerX 10.1.1.436.18 . doi :10.1145/1120680.1120683. S2CID  1176760. 
11. Lenstra, Jan Karel; Shmoys, David B.; Tardos, Éva (1990-01-01). «Аппроксимационные алгоритмы для планирования не связанных параллельных машин». Математическое программирование . 46 (1): 259–271. doi :10.1007/BF01585745. ISSN  1436-4646. S2CID  52867171.
12. Асадпур, Араш; Сабери, Амин (2010-01-01). «Алгоритм приближения для справедливого распределения неделимых благ по максимуму и минимуму». Журнал SIAM по вычислениям . 39 (7): 2970–2989. doi :10.1137/080723491. ISSN  0097-5397.
13. Чакрабарти, Д.; Чужой, Дж.; Кханна, С. (2009-10-01). «О распределении благ для максимизации справедливости». 50-й ежегодный симпозиум IEEE по основам компьютерной науки 2009 г. С. 107–116. arXiv : 0901.0205 . doi :10.1109/FOCS.2009.51. ISBN 978-1-4244-5116-6. S2CID  165160.
14. Головин, Дэниел (2005). "Макс-мин справедливое распределение неделимых благ". CMU . Получено 27 августа 2016 .
15. Вёгингер, Герхард Дж. (2000-02-01). «Когда динамическая программная формулировка гарантирует существование полностью полиномиальной схемы аппроксимации времени (FPTAS)?». INFORMS Journal on Computing . 12 (1): 57–74. doi :10.1287/ijoc.12.1.57.11901. ISSN  1091-9856.
16. Goemans, Michel X.; Harvey, Nicholas JA; Iwata, Satoru; Mirrokni, Vahab (2009-01-04), "Approximating Submodular Functions Everywhere", Труды ежегодного симпозиума ACM-SIAM по дискретным алгоритмам 2009 года , Труды, Общество промышленной и прикладной математики, стр. 535–544, doi : 10.1137/1.9781611973068.59, hdl : 1721.1/60671 , ISBN 978-0-89871-680-1, S2CID  14308006 , получено 2020-11-22
17. Нгуен, Трунг Тхань; Роос, Магнус; Роте, Йорг (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. 
18. Нгуен, Нян-Там; Нгуен, Трунг Тхань; Роос, Магнус; Роте, Йорг (2013). «Вычислительная сложность и аппроксимируемость оптимизации общественного благосостояния при распределении ресурсов с несколькими агентами». Автономные агенты и многоагентные системы . 28 (2): 256. doi :10.1007/s10458-013-9224-2. S2CID  442666.
19. Богомольная, Анна (2015-07-01). «Случайное назначение: переосмысление последовательного правила». Журнал экономической теории . 158 : 308–318. doi :10.1016/j.jet.2015.04.008. ISSN  0022-0531.
20. Plaut, Benjamin; Roughgarden, Tim (2020-01-01). «Почти свободная от зависти с общими оценками». SIAM Journal on Discrete Mathematics . 34 (2): 1039–1068. arXiv : 1707.04769 . doi : 10.1137/19M124397X. ISSN  0895-4801. S2CID  216283014.
21. Benabbou, Nawal; Chakraborty, Mithun; Igarashi, Ayumi; Zick, Yair (2020). «Finding Fair and Efficient Allocations when Valuations Don't Add up». Алгоритмическая теория игр . Конспект лекций по информатике. Том 12283. С. 32–46. arXiv : 2003.07060 . doi :10.1007/978-3-030-57980-7_3. ISBN 978-3-030-57979-1. S2CID  208328700.
22. Caragiannis, Ioannis; Kurokawa, David; Moulin, Hervé; Procaccia, Ariel D.; Shah, Nisarg; Wang, Junxing (2019-09-24). «Необоснованная справедливость максимального благосостояния Нэша». ACM Transactions on Economics and Computation . 7 (3): 12:1–12:32. doi : 10.1145/3355902 . ISSN  2167-8375. S2CID  202729326.
23. Чэнь, Синюй; Лю, Цзыцзе (2020-05-11). «Справедливость лексимина при распределении неделимых дел». arXiv : 2005.04864 [cs.GT].
24. Курокава, Дэвид; Прокачча, Ариэль Д.; Шах, Нисарг (2015-06-15). «Распределение лексиминов в реальном мире». Труды шестнадцатой конференции ACM по экономике и вычислениям . EC '15. Портленд, Орегон, США: Ассоциация вычислительной техники. стр. 345–362. doi :10.1145/2764468.2764490. ISBN 978-1-4503-3410-5. S2CID  1060279.