Алгоритм одновременного приема пищи

Алгоритм одновременного потребления пищи (SE) — это алгоритм распределения делимых объектов среди агентов с порядковыми предпочтениями . [1]

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

SE параметризуется "скоростью еды" каждого агента. Если всем агентам дана одинаковая скорость еды, то распределение SE удовлетворяет SD-envy-freeness - сильному порядковому варианту envy-freeness (это означает, что распределение является свободным от зависти для всех векторов аддитивных функций полезности, соответствующих рейтингам элементов агентов). Этот конкретный вариант SE называется вероятностным последовательным правилом (PS). [1]

SE был разработан Эрве Муленом и Анной Богомольной как решение для задачи справедливого случайного назначения , где доля, которую каждый агент получает от каждого предмета, интерпретируется как вероятность. Если интеграл скорости еды всех агентов равен 1, то сумма долей, назначенных каждому агенту, равна 1, поэтому матрицу долей можно разложить в лотерею по назначениям, в которой каждый агент получает ровно один предмет. При равных скоростях еды лотерея свободна от зависти в ожидании ( ex-ante ) для всех векторов функций полезности, соответствующих рейтингам предметов агентов.

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

Описание

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

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

Для каждого предмета записывается доля этого предмета, съеденная каждым агентом. В контексте случайных назначений эти доли рассматриваются как вероятности. На основе этих вероятностей проводится лотерея. Тип лотереи зависит от проблемы:

  • Если каждому агенту разрешено получать любое количество предметов, то для каждого предмета можно провести отдельную лотерею. Каждый предмет отдается одному из агентов, съевших его часть, выбранную случайным образом в соответствии с распределением вероятностей для этого предмета.
  • Если каждый агент должен получить ровно один предмет, то должна быть одна лотерея, которая выбирает назначение по некоторому распределению вероятностей на множестве детерминированных назначений. Для этого матрица вероятностей n -на- n должна быть разложена в выпуклую комбинацию матриц перестановок . Это можно сделать с помощью алгоритма Биркгофа . Гарантированно найдется комбинация, в которой количество матриц перестановок не превышает n 2 -2 n +2.

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

Примеры

Есть четыре агента и четыре элемента (обозначаемые w, x, y, z). Предпочтения агентов следующие:

  • Алиса и Боб предпочитают w вместо x, y вместо z.
  • Чана и Дана предпочитают x вместо w, а не z вместо y.

Агенты имеют равные права, поэтому мы применяем СЭ с одинаковой и равномерной скоростью потребления 1 единица в минуту.

Изначально Алиса и Боб идут к w, а Чана и Дана идут к x. Каждая пара съедает свой предмет одновременно. Через 1/2 минуты у Алисы и Боба есть по 1/2 w, а у Чаны и Даны — по 1/2 x.

Затем Алиса и Боб идут к y (их любимому оставшемуся предмету), а Чана и Дана идут к z (их любимому оставшемуся предмету). Через 1/2 минуты у Алисы и Боба по 1/2 y, а у Чаны и Даны по 1/2 z.

Матрица дробей теперь имеет вид:

Алиса: 1/2 0 1/2 0

Боб: 1/2 0 1/2 0

Хана: 0 1/2 0 1/2

Дана: 0 1/2 0 1/2

На основе съеденных фракций, элемент w с равной вероятностью отдается Алисе или Бобу, и то же самое делается с элементом y; элемент x с равной вероятностью отдается Чане или Дане, и то же самое делается с элементом z. Если требуется отдать ровно 1 элемент на агента, то матрица вероятностей разлагается на следующие две матрицы назначений:

1 0 0 0 ||| 0 0 1 0

0 0 1 0 ||| 1 0 0 0

0 1 0 0 ||| 0 0 0 1

0 0 0 1 ||| 0 1 0 0

Одно из этих заданий выбирается случайным образом с вероятностью 1/2.

Другие примеры можно найти на сайте MatchU.ai.

Характеристики

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

Эффективность

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

В контексте случайных назначений SD-эффективность подразумевает эффективность ex-post: каждое детерминированное назначение, выбранное лотереей, является Парето-эффективным .

Дробное назначение является SD-эффективным тогда и только тогда, когда оно является результатом SE для некоторого вектора функций скорости поедания. [1] : Теор.1 

Справедливость

SE с равными скоростями поедания (называемые PS) удовлетворяет свойству справедливости, называемому ex-ante стохастическим доминированием беззавистности (sd-envy-free). Неформально это означает, что каждый агент, рассматривая полученную матрицу вероятностей, слабо предпочитает свой собственный ряд вероятностей ряду любого другого агента. Формально, для каждых двух агентов i и j :

  • У агента i вероятность получить лучший предмет в строке i немного выше, чем в строке j ;
  • У агента i вероятность получить один из двух лучших предметов в строке i немного выше, чем в строке j ;
  • ...
  • Для любого k ≥ 1 агент i имеет немного более высокую вероятность получить один из своих k лучших предметов в строке i, чем в строке j .

Обратите внимание, что sd-envy-freeness гарантирована ex-ante : она справедлива только до проведения лотереи. Алгоритм, конечно, не является ex-post справедливым: после проведения лотереи неудачливые агенты могут позавидовать счастливчикам. Это неизбежно при распределении неделимых объектов.

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

Стратегия

SE не является правдивым механизмом : агент, который знает, что его наиболее предпочтительный предмет не нужен никакому другому агенту, может манипулировать алгоритмом, съедая свой второй по предпочтению предмет, зная, что его лучший предмет останется нетронутым. О стратегическом манипулировании PS известно следующее:

  • PS является истинным, когда агенты сравнивают пакеты, используя нисходящее лексикографическое отношение. [3]
  • Агент может вычислить за полиномиальное время наилучший ответ относительно нисходящего лексикографического отношения. Когда есть два агента, каждый агент может вычислить за полиномиальное время наилучший ответ относительно ожидаемой полезности. Когда число агентов может меняться, вычисление наилучшего ответа относительно EU является NP-трудным. [4]
  • Наилучшие ответы относительно ожидаемой полезности могут циклически меняться. Однако чистое равновесие Нэша существует для любого количества агентов и предметов. Когда есть два агента, существуют линейные алгоритмы для вычисления профиля предпочтений, который находится в равновесии Нэша относительно исходных предпочтений. В некоторых эмпирических условиях PS менее склонен к манипуляциям. Когда агент не склонен к риску и не имеет информации о стратегиях других агентов, его максиминная стратегия — быть правдивым. [4]
  • Манипулирующий агент может увеличить свою полезность максимум в 3/2 раза. Это было впервые обнаружено эмпирически на случайных примерах, [5] а затем доказано формально. [6]

Обратите внимание, что правило случайного приоритета , которое решает ту же проблему, что и PS, является истинным.

Расширения

Алгоритм SE был расширен во многих отношениях.

  • Катта и Сетураман [7] представляют расширенный PS (EPS), который допускает слабые порядковые предпочтения (ранжирования с безразличием). Алгоритм основан на многократном решении экземпляров параметрического сетевого потока .
  • Богомольная [3] представила более простое определение правила PS для слабых предпочтений, основанное на лексиминном порядке .
  • Йылмаз [8] допускает как безразличие, так и дарование.
  • Атанасоглут и Сетураман [9] представляют правило контролируемого потребления (CC) , которое допускает безразличие и дробные наделения любой величины.
  • Будиш, Че, Кодзима и Милгром [10] представляют обобщенную модель PS , которая допускает несколько единиц на единицу товара, больше товаров, чем агентов, каждый агент может получить несколько единиц, верхние квоты и бииерархические ограничения на возможные распределения.
  • Ашлаги, Сабери и Шамели [11] представляют еще одну обобщенную модель распределения , которая допускает нижние и верхние квоты, а также ограничения распределения (ограничения на распределение вероятностей, а не только на окончательное распределение).
  • Азиз и Стурсберг [12] представляют эгалитарное одновременное резервирование (ESR) , которое допускает не только справедливое распределение предметов, но и общие проблемы социального выбора с возможными безразличиями.
  • Азиз и Брандл [13] представляют метод бдительного питания (БП) , который допускает еще более общие ограничения.

Гарантия приблизительной справедливости ex post

Как объяснялось выше, распределение, определяемое PS, справедливо только ex-ante, но не ex-post. Более того, когда каждый агент может получить любое количество предметов, ex-post несправедливость может быть произвольно плохой: теоретически возможно, что один агент получит все предметы, а другие агенты не получат ни одного. Недавно было предложено несколько алгоритмов, которые гарантируют как ex-ante справедливость, так и ex-post приблизительную справедливость.

Фримен, Шах и Вайш [14] показывают:

  • Алгоритм Recursive Probabilistic Serial (RecPS), который возвращает распределение вероятностей по распределениям, которые все свободны от зависти, кроме одного элемента (EF1). Распределение — это ex-ante EF, а распределение — ex-post EF1. Наивная версия этого алгоритма дает распределение по возможно экспоненциальному числу детерминированных распределений, полином размера поддержки по числу агентов и товаров достаточен, и, таким образом, алгоритм работает за полиномиальное время. Алгоритм использует оракулы разделения .
  • Другой алгоритм, основанный на распределении ex-ante max-product, который достигает ex-ante групповой свободы от зависти (GEF; подразумевает как EF, так и PO), и ex-post PROP1+EF 1 1 . Это единственное правило распределения, которое достигает всех этих свойств. Его нельзя разложить на распределения EF1.
  • Эти комбинации свойств являются наилучшими из возможных: невозможно гарантировать одновременно ex-ante EF (четный PROP) и ex-ante PO вместе с ex-post EF1; или ex-ante EF (четный PROP) вместе с ex-post EF1 и дробным PO.
  • RecPS можно модифицировать для достижения аналогичных гарантий (ex-ante EF и ex-post EF1) для плохих результатов.

Азиз [15] показывает:

  • Алгоритм PS-lottery , в котором распределение ex-ante sd-EF, и лотерея проводится только среди детерминированных распределений, которые являются sd-EF1, т. е. гарантии EF и EF1 сохраняются для любых кардинальных полезностей, соответствующих порядковому ранжированию. Более того, результат sd-PO как ex-ante, так и ex-post. Алгоритм использует в качестве подпрограмм как алгоритм PS, так и алгоритм Биркгофа . Распределение ex-ante эквивалентно тому, которое возвращает PS; это показывает, что результат PS можно разложить на распределения EF1.
  • С бинарными утилитами алгоритм лотереи PS устойчив к групповым стратегиям , ex-ante PO, ex-ante EF и ex-post EF1.
  • Эти комбинации свойств являются наилучшими из возможных: невозможно гарантировать одновременно ex-ante sd-EF, ex-post EF1 и ex-post PO; или ex-ante PO и ex-ante sd-EF.
  • Проверка того, может ли заданное случайное распределение быть реализовано с помощью лотереи по распределениям EF1 и PO, является NP-трудной задачей.

Бабаиофф, Эзра и Файги [16] показывают:

  • Полиномиальный алгоритм для вычисления распределений, которые являются ex-ante пропорциональными, а ex-post как PROP1, так и 1/2-дробьной максиминной долей (а также 1/2-дробьной усеченно-пропорциональной долей ).
  • Эти свойства близки к оптимальным — невозможно гарантировать больше, чем PROP ex-ante, и больше, чем n /(2 n -1) усеченно-пропорциональной доли ex-post.

Хоефер, Шмальхофер и Варриккио [17] распространяют понятие лотереи «лучшее из обоих миров» на агентов с различными правами .

Смотрите также

На странице, посвященной справедливому случайному распределению, PS сравнивается с другими процедурами решения той же проблемы, такими как правило случайного приоритета .

Ссылки

  1. ^ abc Богомольная, Анна ; Мулен, Эрве (2001). «Новое решение проблемы случайного назначения». Журнал экономической теории . 100 (2): 295. doi :10.1006/jeth.2000.2710.
  2. ^ Азиз, Харис; Йе, Чун (2014). «Алгоритмы разрезания торта для кусочно-постоянных и кусочно-равномерных оценок». В Лю, Те-Янь; Ци, Ци; Йе, Инью (ред.). Веб и интернет-экономика . Конспект лекций по информатике. Том 8877. Чам: Springer International Publishing. стр.  1– 14. doi : 10.1007/978-3-319-13129-0_1. ISBN 978-3-319-13129-0. S2CID  18365892.
  3. ^ abc Богомольная, Анна (2015-07-01). «Случайное назначение: переосмысление последовательного правила». Журнал экономической теории . 158 : 308–318 . doi :10.1016/j.jet.2015.04.008. ISSN  0022-0531.
  4. ^ ab Азиз, Харис; Гасперс, Серж; Маккензи, Саймон; Маттей, Николас; Народицкая, Нина; Уолш, Тоби (2015-05-04). Труды Международной конференции 2015 года по автономным агентам и многоагентным системам. Стамбул, Турция: Международный фонд автономных агентов и многоагентных систем. стр.  1451–1459 . ISBN 978-1-4503-3413-6.. Более старый технический отчет: https://arxiv.org/abs/1401.6523.
  5. ^ Хоссейни, Хади; Ларсон, Кейт; Коэн, Робин (2018-07-01). «Исследование характеристик односторонних механизмов сопоставления при различных предпочтениях и отношении к риску». Автономные агенты и многоагентные системы . 32 (4): 534–567 . arXiv : 1703.00320 . doi :10.1007/s10458-018-9387-y. ISSN  1573-7454. S2CID  14041902.
  6. ^ Ван, Цзыхэ; Вэй, Чжидэ; Чжан, Цзе (2020-04-03). «Ограниченные стимулы в манипулировании вероятностным последовательным правилом». Труды конференции AAAI по искусственному интеллекту . 34 (2): 2276–2283 . arXiv : 2001.10640 . doi : 10.1609/aaai.v34i02.5605 . ISSN  2374-3468. S2CID  210943079.
  7. ^ Катта, Акшай-Кумар; Сетхураман, Джей (2006). «Решение проблемы случайного назначения в полной области предпочтений». Журнал экономической теории . 131 : 231–250 . doi :10.1016/j.jet.2005.05.001.
  8. ^ Йылмаз, Озгюр (2009). «Случайное назначение при слабых предпочтениях». Игры и экономическое поведение . 66 : 546–558 . doi :10.1016/j.geb.2008.04.017.
  9. ^ Атанасоглоу, Стергиос; Сетураман, Джей (2011-08-01). «Распределение домов с дробными вкладами». Международный журнал теории игр . 40 (3): 481– 513. doi :10.1007/s00182-010-0251-9. ISSN  1432-1270. S2CID  15909570.
  10. ^ Будиш, Эрик; Че, Ён-Ку; Кодзима, Фухито; Милгром, Пол (2013-04-01). «Проектирование механизмов случайного распределения: теория и применение». American Economic Review . 103 (2): 585– 623. doi :10.1257/aer.103.2.585. ISSN  0002-8282.
  11. ^ Ашлаги, Итай; Сабери, Амин; Шамели, Али (2020-03-01). «Механизмы назначения при распределительных ограничениях». Исследование операций . 68 (2): 467– 479. arXiv : 1810.04331 . doi : 10.1287/opre.2019.1887. ISSN  0030-364X.
  12. ^ Азиз, Харис; Стурсберг, Пол (2014-06-20). «Обобщение вероятностного последовательного рандомизированного социального выбора». Труды конференции AAAI по искусственному интеллекту . 28 (1). doi : 10.1609/aaai.v28i1.8796 . ISSN  2374-3468. S2CID  16265016.
  13. ^ Азиз, Харис; Брандл, Флориан (01.09.2022). «Правило бдительного питания: общий подход к вероятностному экономическому проектированию с ограничениями». Игры и экономическое поведение . 135 : 168–187 . arXiv : 2008.08991 . doi : 10.1016/j.geb.2022.06.002. ISSN  0899-8256. S2CID  221186811.
  14. ^ Freeman, Rupert; Shah, Nisarg; Vaish, Rohit (2020-07-13). «Лучшее из двух миров: ожидаемая и ожидаемая справедливость в распределении ресурсов». Труды 21-й конференции ACM по экономике и вычислениям . EC '20. Виртуальное мероприятие, Венгрия: Ассоциация вычислительной техники. стр.  21–22 . arXiv : 2005.14122 . doi : 10.1145/3391403.3399537. ISBN 978-1-4503-7975-5. S2CID  211141200.
  15. ^ Азиз, Харис (2020-12-07). «Одновременное достижение ex-ante и ex-post справедливости». Экономика Интернета и сети . Конспект лекций по информатике. Том 12495. Берлин, Гейдельберг: Springer-Verlag. С.  341–355 . arXiv : 2004.02554 . doi : 10.1007/978-3-030-64946-3_24. ISBN 978-3-030-64945-6. S2CID  214802174.
  16. ^ Бабаиофф, Моше; Эзра, Томер; Файге, Уриэль (2021-02-09). «Лучшее из обоих миров справедливое распределение». arXiv : 2102.04909 [cs.GT].
  17. ^ Хоефер, Мартин; Шмальхофер, Марко; Варриккьо, Джованна (08.09.2022). «Лучшее из обоих миров: агенты с правами». arXiv : 2209.03908 [cs.GT].
Взято с "https://en.wikipedia.org/w/index.php?title=Алгоритм_одновременного_приема_пищи&oldid=1270621558"