Минимизация зависти

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

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

Определение степени зависти

Существует несколько способов определения целевой функции (величины зависти) для минимизации. Некоторые из них:

Количество завистников ;
Количество отношений зависти (- ребер в графе зависти );
Максимальный коэффициент зависти , где коэффициент зависти i в j в распределении X определяется как: ${\text{EnvyRatio}}(X,i,j):=\max \left(1,{u_{i}(X_{j}) \over u_{i}(X_{i})}\right)$ ${\text{EnvyRatio}}(X,i,j):=\max \left(1,{u_{i}(X_{j}) \over u_{i}(X_{i})} \верно)$ ; поэтому соотношение равно 1, если я не завидую j , и больше, когда я завидую j .
- Аналогично можно рассмотреть сумму коэффициентов зависти или их произведение.
Максимум, сумма или произведение зависти-разности .

Минимизация коэффициента зависти

При общих оценках любой детерминированный алгоритм, минимизирующий максимальный коэффициент зависти, требует количества запросов, число которых в худшем случае экспоненциально пропорционально количеству товаров. ^{[ 1 ]}^: 3

При аддитивных и одинаковых оценках : ^{[ 1 ]}^: 4–6

Следующий жадный алгоритм находит распределение, максимальный коэффициент зависти которого не более чем в 1,4 раза превышает оптимальный: ^{[ 2 ]}
1. Упорядочить элементы по убыванию стоимости;
2. Пока предметов больше, отдайте следующий предмет агенту с наименьшей общей стоимостью.
Существует PTAS для минимизации максимального коэффициента зависти. Более того, когда количество игроков постоянно, существует FPTAS .

С аддитивными и разными оценками : ^{[ 3 ]}

Когда количество агентов является частью входных данных, невозможно получить за полиномиальное время коэффициент аппроксимации лучше 1,5, если только P = NP.
Когда количество агентов постоянно (не является частью входных данных), существует FPTAS для минимизации максимального коэффициента зависти и произведения коэффициентов зависти.
Когда количество агентов равно количеству элементов, существует алгоритм с полиномиальным временем.

Минимизация распределенной зависти

В некоторых случаях требуется вычислить распределение, минимизирующее зависть, распределенным способом, т. е. каждый агент должен вычислить свое собственное распределение таким образом, чтобы гарантировать, что полученное распределение будет согласованным. Эту проблему можно решить, представив ее как задачу оптимизации асимметричных распределенных ограничений (ADCOP) следующим образом. ^{[ 4 ]}

Добавьте двоичную переменную v _ij для каждого агента i и элемента j . Значение переменной равно «1», если агент получает элемент, и «0» в противном случае. Переменная принадлежит агенту i .
Чтобы выразить ограничение, согласно которому каждый элемент передается не более чем одному агенту, добавьте двоичные ограничения для каждых двух разных переменных, связанных с одним и тем же элементом, с бесконечной стоимостью, если две переменные одновременно равны «1», и нулевой стоимостью в противном случае.
Чтобы выразить ограничение, согласно которому все элементы должны быть распределены, добавьте n -арное ограничение для каждого элемента (где n — количество агентов) с бесконечной стоимостью, если ни одна переменная, связанная с этим элементом, не равна «1».

Проблему можно решить, используя следующий алгоритм локального поиска . ^{[ 4 ]}

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

Онлайн минимизация разницы из зависти

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

Benade, Kazachkov, Procaccia and Psomas ^{[ 5 ]} рассмотрим задачу минимизации максимальной разницы зависти , где оценки нормализованы так, что значение каждого элемента находится в [0,1]. Обратите внимание, что в автономном варианте этой настройки легко найти распределение, в котором максимальная разница зависти равна 1 (такое распределение называется EF1; в разделе «Распределение элементов без зависти» дополнительные сведения см. ). Однако в онлайн-варианте разница в виде зависти увеличивается с увеличением количества предметов. Они показывают алгоритм, в котором зависть после T предметов находится в $O({\sqrt {T/n}})$ . Цзян, Кулкарни и Сингла ^{[ 6 ]} улучшить свою границу зависти, используя алгоритм двумерных несоответствий онлайн- минимизации .

Другие настройки

Другие условия, в которых изучалась минимизация зависти:

Оптимальный налог . ^{[ 7 ]}
Выбор школы . ^{[ 8 ]}

Ссылки

^ Перейти обратно: ^а ^б Липтон, Р.Дж.; Маркакис, Э.; Моссель, Э.; Сабери, А. (2004). «О примерно справедливом распределении неделимых благ». Материалы 5-й конференции ACM по электронной коммерции - EC '04 . п. 125. дои : 10.1145/988772.988792 . ISBN 1-58113-771-0 .
^ Грэм, Р.Л. (1969). «Границы аномалий синхронизации многопроцессорной обработки». SIAM Journal по прикладной математике . 17 (2): 416–429. CiteSeerX 10.1.1.90.8131 . дои : 10.1137/0117039 .
^ Нгуен, Чунг Тхань; Роте, Йорг (2014). «Минимизация зависти и максимизация среднего социального благосостояния Нэша при распределении неделимых благ» . Дискретная прикладная математика . 179 : 54–68. дои : 10.1016/j.dam.2014.09.010 .
^ Перейти обратно: ^а ^б Нетцер, Арнон; Мейзельс, Амнон; Живан, Рой (01 марта 2016 г.). «Минимизация распределенной зависти к распределению ресурсов» . Автономные агенты и мультиагентные системы . 30 (2): 364–402. дои : 10.1007/s10458-015-9291-7 . ISSN 1387-2532 . S2CID 13834856 .
^ Бенаде, Гердус; Казачков Александр М.; Прокачча, Ариэль Д.; Псомас, Христос-Александрос (11 июня 2018 г.). «Как заставить зависть исчезнуть со временем» . Материалы конференции ACM по экономике и вычислениям 2018 года . ЕС '18. Итака, Нью-Йорк, США: Ассоциация вычислительной техники. стр. 593–610. дои : 10.1145/3219166.3219179 . ISBN 978-1-4503-5829-3 . S2CID 3340196 .
^ Цзян, Хаотянь; Кулкарни, Джанардхан; Сингла, Сахил (2 октября 2019 г.). «Онлайн-геометрическое несоответствие для стохастических поступлений с применением к минимизации зависти». arXiv : 1910.01073 [ cs.DS ].
^ Юкихиро, Нисимура (2008). «Минимизация зависти в оптимальном налоговом контексте» . AgEcon Поиск . Рабочий документ № 1178. doi : 10.22004/ag.econ.273655 .
^ Абдулкадироглу, Атила; Че, Ён Ку; Патхак, Параг А.; Рот, Элвин Э.; Терсье, Оливье (27 марта 2017 г.). «Минимизация оправданной зависти при выборе школы: дизайн OneApp в Новом Орлеане» . Серия рабочих документов. дои : 10.3386/w23265 . S2CID 9497845 . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )

[lmms04-1] Перейти обратно: ^а ^б Липтон, Р.Дж.; Маркакис, Э.; Моссель, Э.; Сабери, А. (2004). «О примерно справедливом распределении неделимых благ». Материалы 5-й конференции ACM по электронной коммерции - EC '04 . п. 125. дои : 10.1145/988772.988792 . ISBN 1-58113-771-0 .

[g69-2] Грэм, Р.Л. (1969). «Границы аномалий синхронизации многопроцессорной обработки». SIAM Journal по прикладной математике . 17 (2): 416–429. CiteSeerX 10.1.1.90.8131 . дои : 10.1137/0117039 .

[nr15-3] Нгуен, Чунг Тхань; Роте, Йорг (2014). «Минимизация зависти и максимизация среднего социального благосостояния Нэша при распределении неделимых благ» . Дискретная прикладная математика . 179 : 54–68. дои : 10.1016/j.dam.2014.09.010 .

[:2-4] Перейти обратно: ^а ^б Нетцер, Арнон; Мейзельс, Амнон; Живан, Рой (01 марта 2016 г.). «Минимизация распределенной зависти к распределению ресурсов» . Автономные агенты и мультиагентные системы . 30 (2): 364–402. дои : 10.1007/s10458-015-9291-7 . ISSN 1387-2532 . S2CID 13834856 .

[:0-5] Бенаде, Гердус; Казачков Александр М.; Прокачча, Ариэль Д.; Псомас, Христос-Александрос (11 июня 2018 г.). «Как заставить зависть исчезнуть со временем» . Материалы конференции ACM по экономике и вычислениям 2018 года . ЕС '18. Итака, Нью-Йорк, США: Ассоциация вычислительной техники. стр. 593–610. дои : 10.1145/3219166.3219179 . ISBN 978-1-4503-5829-3 . S2CID 3340196 .

[6] Цзян, Хаотянь; Кулкарни, Джанардхан; Сингла, Сахил (2 октября 2019 г.). «Онлайн-геометрическое несоответствие для стохастических поступлений с применением к минимизации зависти». arXiv : 1910.01073 [ cs.DS ].

[7] Юкихиро, Нисимура (2008). «Минимизация зависти в оптимальном налоговом контексте» . AgEcon Поиск . Рабочий документ № 1178. doi : 10.22004/ag.econ.273655 .

[8] Абдулкадироглу, Атила; Че, Ён Ку; Патхак, Параг А.; Рот, Элвин Э.; Терсье, Оливье (27 марта 2017 г.). «Минимизация оправданной зависти при выборе школы: дизайн OneApp в Новом Орлеане» . Серия рабочих документов. дои : 10.3386/w23265 . S2CID 9497845 . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]