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

Справедливое разделение между группами ^[1] (или семьи ^[2]) — это класс задач справедливого разделения , в которых ресурсы распределяются между группами агентов, а не между отдельными агентами. После разделения все члены каждой группы потребляют одинаковую долю, но у них могут быть разные предпочтения; следовательно, разные члены одной и той же группы могут расходиться во мнениях относительно того, является ли распределение справедливым или нет. Некоторые примеры настроек разделения групповых выставок:

Несколько братьев и сестер унаследовали несколько домов от своих родителей, и им пришлось их разделить. У каждого брата или сестры есть семья, члены которой могут иметь разные мнения относительно того, какой дом лучше.
Партнерство расторгается, а его активы должны быть разделены между партнерами. Партнерами являются фирмы; У каждой фирмы есть несколько акционеров, которые могут расходиться во мнениях относительно того, какой актив важнее.
Руководство университета хочет выделить несколько переговорных между своими кафедрами. На каждом факультете есть несколько преподавателей, которые имеют разные мнения о том, какие помещения лучше.
Две соседние страны хотят поделить между собой спорный регион. Граждане каждой страны расходятся во мнениях, какие части региона более важны. Это обычное препятствие для разрешения международных споров.
«Группа агентов» также может представлять различные конфликтующие предпочтения одного человека . Как замечено в поведенческой экономике , люди часто меняют свои предпочтения в зависимости от настроения или настроения. ^[3] Таких людей можно представить как группу агентов, каждый из которых имеет разные предпочтения.

Во всех приведенных выше примерах группы фиксированы заранее. В некоторых случаях группы могут определяться по мере необходимости, то есть людей можно группировать на основе их предпочтений. Пример такой настройки: ^[4]

Около 30 человек хотят воспользоваться местной баскетбольной площадкой. В каждой игре участвуют 10 игроков с разными предпочтениями относительно того, какое время лучше. Требуется разделить время суток на 3 части, а игроков разделить на 3 группы и назначить группу на каждый временной интервал.

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

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

Единогласная справедливость требует, чтобы распределение считалось справедливым в глазах всех агентов во всех группах. Например:

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

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

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

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

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

Единодушная справедливость подразумевает как совокупную справедливость, так и демократическую справедливость. Совокупная справедливость и демократическая справедливость независимы – ни одна из них не подразумевает другую. ^[2]

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

Результаты для делимых ресурсов

В контексте честного разрезания торта известны следующие результаты (где k — количество групп, а n — количество агентов во всех группах вместе взятых). ^[2]

Единогласная справедливость : всегда существуют единогласно-пропорциональные и единогласные распределения без зависти. Однако они могут быть отключены: как минимум n подключенных компонентов может потребоваться . В случае двух групп n компонентов всегда достаточно. При k >2 группах компонентов O( n log k ) всегда достаточно для единогласно-пропорционального распределения, а компонентов O( nk ) всегда достаточно для единогласного распределения без зависти. остается открытым . Вопрос о том, всегда ли n компонентов достаточно,
Агрегатная справедливость : всегда существуют распределения, пропорциональные средним и свободные от зависти, и требуют только k связанных компонентов (то есть каждая группа может получить связный кусок). Однако их невозможно найти с помощью конечного алгоритма в модели запроса Робертсона-Уэбба .
Демократическая справедливость : 1/2-демократическое пропорциональное распределение и 1/2-демократическое распределение без зависти всегда существует. При двух группах существуют такие распределения, которые также связаны , и их можно найти за полиномиальное время. При k >2 группах связанное 1/2-демократическое справедливое распределение может не существовать, но количество необходимых компонентов меньше, чем при единогласно-пропорциональном распределении.
Справедливость и эффективность . Все три варианта пропорциональности совместимы с эффективностью Парето для любого количества групп. Свобода от единодушной зависти совместима с эффективностью по Парето для 2 групп, но не для 3 и более групп. 1/2-демократическая свобода от зависти совместима с эффективностью по Парето для 2 групп, но не для 5 и более групп. Неизвестно, совместимы ли они для 3 или 4 групп. ^[3]

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

Единогласная пропорциональность и точное разделение

При точном разделении (также называемом консенсусным разделением ) имеется n агентов, и цель состоит в том, чтобы разделить пирог на k частей так, чтобы все агенты оценили все части ровно по 1/ k . Известно, что точное деление с n ( k -1) существует всегда. Однако даже для k = 2 поиск точного деления с n разрезами является FIXP-сложным, а поиск приблизительного точного деления с n разрезами является PPA-полным ( см. в разделе Точное деление дополнительную информацию ). Можно доказать, что единогласная пропорциональность эквивалентна консенсусному разделению в следующем смысле: ^[2]

Для каждых n и k решение единогласно-пропорционального разделения среди n ( k -1)+1 агентов, сгруппированных в k семейств, подразумевает решение консенсусного разделения между n агентами с k частями. В частности, это подразумевает, что для единогласно-пропорционального дележа требуется не менее n -1 сокращений ( n компонентов), нахождение единогласно-пропорционального дележа с n -1 сокращением является FIXP-трудным, а нахождение приблизительного единогласно-пропорционального дележа с n -1 сокращения являются PPA-жесткими.
Для каждых n и k решение точного разделения между n агентами и k частями подразумевает решение единогласно-пропорционального разделения между n+1 агентами, сгруппированными в k семейств. В частности, это означает, что точное единогласно-пропорциональное деление может быть произведено с помощью ( n -1)( k -1) сокращений и что нахождение приблизительного единогласно-пропорционального деления находится в PPA. Число разрезов ограничено для k семейств =2, но не для k >2. ^[5]

Результаты для неделимых предметов

В контексте справедливого распределения статей известны следующие результаты.

Единогласная приблизительная максимальная справедливость : ^[6]

При наличии двух групп положительное мультипликативное приближение к MMS-справедливости может быть гарантировано тогда и только тогда, когда число агентов в группах равно (1, n -1), (2,2) или (2,3). ). Положительные результаты достижимы с помощью алгоритмов с полиномиальным временем. Во всех остальных случаях бывают случаи, когда хотя бы один агент с положительным MMS получает нулевое значение во всех распределениях.
Когда существует три или более групп , положительное мультипликативное приближение к MMS-справедливости может быть достигнуто, если k -1 группы содержат одного агента; Напротив, если все группы содержат 2 агента, а одна группа содержит не менее 5 агентов, то положительное приближение невозможно.

Единогласное приблизительное отсутствие зависти : ^[7]

Когда существуют две группы агентов с бинарными аддитивными оценками , единогласное распределение EF1 существует, если размеры группы равны (1,5) или (2,3), но может не существовать, если размеры группы равны (1,6) или (2,4) или (3,3). В общем, распределение EF c может не существовать, если размеры групп $({2c+1 \choose c+1},{2c+1 \choose c+1})$ $({2c+1 \choose c+1}, {2c+1 \choose c+1})$ . Обратите внимание, что при двоичной оценке EF1 эквивалентен EFX, но слабее, чем EFX0. Единогласное распределение EFX0 может не существовать, если размеры группы равны (1,2); это контрастирует с ситуацией с отдельными агентами, то есть с размерами групп (1,1), где распределение EFX0 всегда существует даже для монотонных оценок. ^[8]
- NP -трудно решить, допускает ли данный экземпляр единогласное распределение EF1.
Когда существуют две группы агентов с отзывчивыми оценками (расширенный набор аддитивных оценок ), единогласно сбалансированное распределение EF1 существует, если размеры групп равны (1,2). Если некоторая гипотеза о графах Кнезера верна, то сбалансированное распределение единогласно-EF1 существует также для размеров группы (1,4), (2,3) и произвольных монотонных оценок. Единогласное распределение EFX может не существовать, если размеры групп равны (1,2).
Для двух специальных групп с любым количеством агентов с произвольными монотонными оценками существует единогласное распределение EF1. Также существует сбалансированное распределение агентов и единогласно сбалансированное распределение товаров по принципу EF1. EF1 не может быть усилен до EFX даже с помощью аддитивных оценок.
Для k специальных групп с любым количеством агентов с аддитивными оценками существует единогласное распределение PROP*1.
Для n агентов, произвольно разделенных на k групп, всегда существует свободное от зависти распределение до c элементов, где $O({\sqrt {n}})\geq c\geq \Omega ({\sqrt {n/k^{3}}})$ . То же самое справедливо и для пропорциональности до c пунктов. Для консенсусного разделения границы равны $O({\sqrt {n}})\geq c\geq \Omega ({\sqrt {n/k}})$ . Все границы асимптотически точны, когда число групп постоянно. В доказательствах используется теория расхождения . ^[9]

Единогласное отсутствие зависти с высокой вероятностью : ^[10]

Когда все k групп содержат одинаковое количество агентов и их оценки определяются случайным образом, распределение без зависти существует с высокой вероятностью, если количество товаров находится в пределах $\Omega (n\log n)$ $\Omega (n\log n)$ и может быть достигнуто с помощью жадного алгоритма, максимизирующего сумму полезностей.
- Результаты могут быть распространены на две группы разного размера.
- Существует также правдивый механизм , который с высокой вероятностью обеспечивает распределение практически без зависти.
Если количество товаров меньше n , то с высокой вероятностью распределения без зависти не существует.

Демократическая справедливость : ^[11]

Для двух групп с бинарными аддитивными оценками (с любым количеством агентов) всегда существует 1/2-демократическое распределение без зависти, кроме 1. Константа 1/2 является жесткой, даже если мы допускаем распределение «без зависти, кроме c» для любой константы c . То же самое справедливо и для пропорциональности, кроме- c . Другое понятие справедливости, которое может быть гарантировано более чем 1/2 агентов в каждой группе, — это приближение порядковой максимин-доли . Для каждого целого числа c существует $(1-1/2^{c-1})$ $(1-1/2^{c-1})$ «1 из c» - демократичное распределение MMS по принципу . Эти распределения можно эффективно найти, используя вариант кругового распределения элементов с взвешенным голосованием за одобрение внутри каждой группы. Верхняя граница доли агентов, которым может быть гарантирован 1 из их лучших c «1 из c» ), равна элементов (свойство слабее, чем MMS $(1-1/2^{c})$ $(1-1/2^{c})$ . Для $c=2$ $c=2$ , нижняя граница распределения «1 из лучших » может быть улучшена с 1/2 до 3/5; остается открытым вопрос, всегда ли можно достичь верхней границы 3/4.
- NP -трудно решить, допускает ли данный экземпляр распределение, которое дает каждому агенту положительную полезность.
Для двух групп с общими монотонными оценками всегда существует 1/2-демократическое распределение без зависти, кроме 1, и его можно найти с помощью эффективного алгоритма.
Для трех или более групп с бинарными аддитивными оценками всегда существует 1/ k -демократическое распределение без зависти, кроме-1; при общих монотонных оценках всегда существует 1/ k -демократическое распределение без зависти, кроме-2. Коэффициент 1/ k подходит для распределения без зависти, кроме c, для любой константы c . Если независимость от зависти смягчить до пропорциональности или максимин-доли, то аналогичных гарантий можно достичь, используя алгоритм с полиномиальным временем. Для групп с аддитивными оценками можно использовать вариант циклического распределения элементов, чтобы найти 1/3-демократическое распределение 1 из лучших k .

Групповое справедливое разделение вещей и денег

В контексте арендной гармонии (разделение комнат и арендная плата без зависти) известны следующие результаты. ^[12]

Единогласная свобода от зависти ( называемая сильной свободой от зависти в статье ) может не существовать, когда политика распределения затрат равна или пропорциональна, но всегда существует при свободной политике разделения затрат. Более того, единогласное распределение без зависти со свободным разделением затрат, которое максимизирует общую ренту, может быть найдено за полиномиальное время.
- В специальных группах существует единодушное отсутствие зависти даже при условии равного распределения затрат.
Средняя свобода от зависти ( называемая совокупной свободой от зависти ) всегда существует, когда политика распределения затрат равна, пропорциональна или свободна. в статье

Ярмарка разделения билетных лотерей

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

В случае, когда все члены группы идентифицируются заранее, механизм групповой лотереи упорядочивает группы в случайном порядке и обрабатывает их последовательно, пока имеется доступная емкость. Этот естественный механизм может быть несправедливым и неэффективным; есть несколько лучших альтернатив. ^[13]
Если агенты могут запросить несколько билетов без идентификации членов своей группы, механизм индивидуальной лотереи упорядочивает агентов равномерно в случайном порядке и выдает вознаграждение каждому их запросу до тех пор, пока есть доступная емкость. Этот общий механизм может привести к произвольно несправедливым и неэффективным результатам. Взвешенная индивидуальная лотерея — это альтернативный механизм, в котором порядок обработки смещен в пользу агентов с меньшими запросами. Это примерно справедливо и примерно эффективно. ^[13]
Алгоритм итеративной максимизации вероятности находит лотерею, которая максимизирует наименьшую полезность (на основе эгалитарного правила и порядка лексиминов ). Он устойчив к групповой стратегии и достигает 1/2-факторного приближения к максимальному использованию. Это также эффективно по Парето , не вызывает зависти и анонимно . Его свойства максимальны в том смысле, что невозможно улучшить одно свойство, не ухудшив при этом другое. ^[14]

Связанные понятия

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

Ссылки

^ Суксомпонг, Варут (2018). Распределение ресурсов и принятие решений в группах (Диссертация). OCLC 1050345365 .
^ Jump up to: ^а ^б ^с ^д Сегал-Халеви, Эрель; Ницан, Шмуэль (декабрь 2019 г.). «Семейное разрезание торта» (PDF) . Социальный выбор и благосостояние . 53 (4): 709–740. дои : 10.1007/s00355-019-01210-9 . S2CID 1602396 .
^ Jump up to: ^а ^б Баде, Софи; Сегал-Халеви, Эрель (1 сентября 2023 г.). «Справедливость для агентов с несколькими субъектами» . Игры и экономическое поведение . 141 : 321–336. arXiv : 1811.06684 . дои : 10.1016/j.geb.2023.06.004 . ISSN 0899-8256 .
^ Jump up to: ^а ^б Сегал-Халеви, Эрель; Суксомпонг, Варут (2 января 2021 г.). «Как честно разрезать торт: обобщение для групп». Американский математический ежемесячник . 128 (1): 79–83. arXiv : 2001.03327 . дои : 10.1080/00029890.2021.1835338 . S2CID 210157034 .
^ Сегал-Халеви, Эрель; Ницан, Шмуэль (декабрь 2019 г.). «Семейное разрезание торта» (PDF) . Социальный выбор и благосостояние . 53 (4): 709–740. дои : 10.1007/s00355-019-01210-9 . S2CID 1602396 .
^ Суксомпонг, Варут (1 марта 2018 г.). «Примерные доли максимина для групп агентов». Математические социальные науки . 92 : 40–47. arXiv : 1706.09869 . doi : 10.1016/j.mathsocsci.2017.09.004 . S2CID 3720438 .
^ Киропулу, Мария; Суксомпонг, Варут; Вудурис, Александрос А. (12 ноября 2020 г.). «Почти отсутствие зависти при распределении групповых ресурсов» (PDF) . Теоретическая информатика . 841 : 110–123. дои : 10.1016/j.tcs.2020.07.008 . S2CID 220546580 .
^ Плаут, Бенджамин; Рафгарден, Тим (январь 2020 г.). «Почти независть при общих оценках». SIAM Journal по дискретной математике . 34 (2): 1039–1068. arXiv : 1707.04769 . дои : 10.1137/19M124397X . S2CID 216283014 .
^ Мануранси, Пасин; Суксомпонг, Варут (2022 г.). «Почти отсутствие зависти для групп: улучшенные границы с помощью теории несоответствия». Теоретическая информатика . 930 : 179–195. arXiv : 2105.01609 . дои : 10.1016/j.tcs.2022.07.022 . S2CID 233714947 .
^ Мануранси, Пасин; Суксомпонг, Варут (1 сентября 2017 г.). «Асимптотическое существование справедливых делений групп». Математические социальные науки . 89 : 100–108. arXiv : 1706.08219 . doi : 10.1016/j.mathsocsci.2017.05.006 . S2CID 47514346 .
^ Сегал-Халеви, Эрель; Суксомпонг, Варут (декабрь 2019 г.). «Демократическое справедливое распределение неделимых благ». Искусственный интеллект . 277 : 103167. arXiv : 1709.02564 . дои : 10.1016/j.artint.2019.103167 . S2CID 203034477 .
^ Годси, Мохаммед; Латифиан, Мохамад; Мохаммади, Арман; Морадиан, Садра; Седдигин, Масуд (2018). «Распределение аренды между группами». Комбинаторная оптимизация и приложения . Конспекты лекций по информатике. Том. 11346. стр. 577–591. дои : 10.1007/978-3-030-04651-4_39 . ISBN 978-3-030-04650-7 .
^ Jump up to: ^а ^б Арности, Ник; Боне, Карлос (2022). «Лотереи для обмена опытом». Материалы 23-й конференции ACM по экономике и вычислениям . стр. 1179–1180. arXiv : 2205.10942 . дои : 10.1145/3490486.3538312 . ISBN 978-1-4503-9150-4 . S2CID 248986158 .
^ Арбив, Таль; Ауманн, Йонатан (28 июня 2022 г.). «Честные и правдивые лотереи» . Материалы конференции AAAI по искусственному интеллекту . 36 (5): 4785–4792. дои : 10.1609/aaai.v36i5.20405 . S2CID 250288879 .

[1] Суксомпонг, Варут (2018). Распределение ресурсов и принятие решений в группах (Диссертация). OCLC 1050345365 .

[:0-2] Jump up to: ^а ^б ^с ^д Сегал-Халеви, Эрель; Ницан, Шмуэль (декабрь 2019 г.). «Семейное разрезание торта» (PDF) . Социальный выбор и благосостояние . 53 (4): 709–740. дои : 10.1007/s00355-019-01210-9 . S2CID 1602396 .

[:3-3] Jump up to: ^а ^б Баде, Софи; Сегал-Халеви, Эрель (1 сентября 2023 г.). «Справедливость для агентов с несколькими субъектами» . Игры и экономическое поведение . 141 : 321–336. arXiv : 1811.06684 . дои : 10.1016/j.geb.2023.06.004 . ISSN 0899-8256 .

[:1-4] Jump up to: ^а ^б Сегал-Халеви, Эрель; Суксомпонг, Варут (2 января 2021 г.). «Как честно разрезать торт: обобщение для групп». Американский математический ежемесячник . 128 (1): 79–83. arXiv : 2001.03327 . дои : 10.1080/00029890.2021.1835338 . S2CID 210157034 .

[:02-5] Сегал-Халеви, Эрель; Ницан, Шмуэль (декабрь 2019 г.). «Семейное разрезание торта» (PDF) . Социальный выбор и благосостояние . 53 (4): 709–740. дои : 10.1007/s00355-019-01210-9 . S2CID 1602396 .

[6] Суксомпонг, Варут (1 марта 2018 г.). «Примерные доли максимина для групп агентов». Математические социальные науки . 92 : 40–47. arXiv : 1706.09869 . doi : 10.1016/j.mathsocsci.2017.09.004 . S2CID 3720438 .

[7] Киропулу, Мария; Суксомпонг, Варут; Вудурис, Александрос А. (12 ноября 2020 г.). «Почти отсутствие зависти при распределении групповых ресурсов» (PDF) . Теоретическая информатика . 841 : 110–123. дои : 10.1016/j.tcs.2020.07.008 . S2CID 220546580 .

[8] Плаут, Бенджамин; Рафгарден, Тим (январь 2020 г.). «Почти независть при общих оценках». SIAM Journal по дискретной математике . 34 (2): 1039–1068. arXiv : 1707.04769 . дои : 10.1137/19M124397X . S2CID 216283014 .

[9] Мануранси, Пасин; Суксомпонг, Варут (2022 г.). «Почти отсутствие зависти для групп: улучшенные границы с помощью теории несоответствия». Теоретическая информатика . 930 : 179–195. arXiv : 2105.01609 . дои : 10.1016/j.tcs.2022.07.022 . S2CID 233714947 .

[10] Мануранси, Пасин; Суксомпонг, Варут (1 сентября 2017 г.). «Асимптотическое существование справедливых делений групп». Математические социальные науки . 89 : 100–108. arXiv : 1706.08219 . doi : 10.1016/j.mathsocsci.2017.05.006 . S2CID 47514346 .

[11] Сегал-Халеви, Эрель; Суксомпонг, Варут (декабрь 2019 г.). «Демократическое справедливое распределение неделимых благ». Искусственный интеллект . 277 : 103167. arXiv : 1709.02564 . дои : 10.1016/j.artint.2019.103167 . S2CID 203034477 .

[12] Годси, Мохаммед; Латифиан, Мохамад; Мохаммади, Арман; Морадиан, Садра; Седдигин, Масуд (2018). «Распределение аренды между группами». Комбинаторная оптимизация и приложения . Конспекты лекций по информатике. Том. 11346. стр. 577–591. дои : 10.1007/978-3-030-04651-4_39 . ISBN 978-3-030-04650-7 .

[:2-13] Jump up to: ^а ^б Арности, Ник; Боне, Карлос (2022). «Лотереи для обмена опытом». Материалы 23-й конференции ACM по экономике и вычислениям . стр. 1179–1180. arXiv : 2205.10942 . дои : 10.1145/3490486.3538312 . ISBN 978-1-4503-9150-4 . S2CID 248986158 .

[14] Арбив, Таль; Ауманн, Йонатан (28 июня 2022 г.). «Честные и правдивые лотереи» . Материалы конференции AAAI по искусственному интеллекту . 36 (5): 4785–4792. дои : 10.1609/aaai.v36i5.20405 . S2CID 250288879 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]