Модель запроса Робертсона-Уэбба

Модель вычислений, используемая алгоритмами

В информатике модель запросов Робертсона -Уэбба (RW) — это модель вычислений, используемая алгоритмами для задачи справедливого разрезания торта . В этой задаче есть ресурс, называемый «тортом», и несколько агентов с различными мерами ценности на торте. Цель состоит в том, чтобы разделить торт между агентами таким образом, чтобы каждый агент считал свой кусок «справедливым» по своей личной мере ценности. Поскольку оценки агентов могут быть очень сложными, они не могут — в общем случае — быть заданы в качестве входных данных для алгоритма справедливого деления. Модель RW определяет два вида запросов , которые алгоритм справедливого деления может задавать агентам: Eval и Cut . Неформально, запрос Eval просит агента указать его/ее ценность для данного куска торта, а запрос Cut (также называемый запросом Mark ) просит агента указать кусок торта с заданной ценностью.

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

Запросы Eval и Cut были впервые описаны в книге Джека М. Робертсона и Уильяма А. Уэбба. ^[1] Название «модель Робертсона–Уэбба» было придумано и формализовано Воегингером и Сгаллом. ^[2]

Определения

Стандартная модель RW предполагает, что торт представляет собой интервал, обычно интервал [0,1]. Есть n агентов, и у каждого агента i есть мера значения v _i на торте. Алгоритм не знает v _i , но может получить к нему доступ с помощью двух видов запросов:

• Запрос eval : для двух действительных чисел x и y функция Eval _i ( x , y ) просит агента i сообщить значение интервала [ x , y ], т. е. v _i ([ x , y ]).
• Запрос на отметку (также называемый запросом на отсечение ): при наличии двух действительных чисел x и r, Mark _i ( x , r ) просит агента i сообщить некоторое значение y такое, что v _i ([ x , y ]) = r .

Пример

Классический алгоритм «Раздели и выбери» для разрезания торта между двумя детьми можно реализовать с помощью четырех запросов.

• Задайте Алисе запрос Eval(0,1); пусть V ₁ будет ответом (это ценность всего торта для Алисы).
• Задайте Алисе запрос Mark(0, V ₁ / 2); пусть x ₁ будет ответом (это оценка Алисы, которая дает две равные по ее мнению части).
• Задайте Джорджу запросы Eval(0, x ₁ ) и Eval( x ₁ , 1).
• Если первое значение больше, дать (0, x ₁ ) Джорджу и ( x ₁ ,1) Алисе; в противном случае дать (0, x ₁ ) Алисе и ( x ₁ ,1) Джорджу.

Результаты

Помимо «разделяй и выбирай», многие алгоритмы разрезания торта могут быть выполнены с использованием запросов RW, число которых полиномиально от n (число агентов). Например: Last Reducer может быть выполнен с помощью O( n ² ) запросов RW, а протокол Even–Paz может быть выполнен с помощью O( n log n ) запросов RW. Параллельно с этим, есть много результатов по сложности, доказывающих, что некоторые проблемы справедливого деления требуют для завершения многих запросов RW. Некоторые такие результаты по сложности показаны ниже.

Пропорциональное разрезание торта требует Ω( n log n ) RW-запросов, когда либо

• части должны быть соединены, ^[2] или
• протокол является детерминированным, ^[3] или
• точность разрезания торта конечна. ^[3]
• Единственный протокол, который использует O( n ) RW-запросов, — это рандомизированный протокол, который может возвращать несвязанные части, а распределение может быть только дробно-пропорциональным.

Пропорциональное разрезание торта с различными правами требует как минимум Ω( n log( D )) RW-запросов, где D — общий знаменатель прав (в частности, его нельзя найти с помощью ограниченного числа запросов, если права иррациональны). Существует алгоритм, который использует O( n log( D )) RW-запросов для рациональных прав и конечный алгоритм для иррациональных прав. ^[4]

Для разрезания торта без зависти требуется

• Ω( n ² ) RW запрашивает, когда части могут быть отсоединены, ^[5]
• Бесконечное множество запросов, когда части должны быть связаны и есть по крайней мере 3 агента. ^[6] Другими словами, не существует алгоритма, который всегда находит распределение без зависти среди 3 или более агентов, используя конечное множество запросов RW.
• Для любого ε > 0, для ε-свободного от зависти разрезания торта требуется не менее Ω(log ε ⁻¹ ) запросов. ^[7] Для 3 агентов существует протокол O(log ε ⁻¹ ). Для 4 агентов существует протокол O(poly(log ε ⁻¹ )). ^[8] Для 5 или более агентов наиболее известный протокол требует O( n ε ⁻¹ ), что показывает экспоненциальный разрыв в сложности запросов.

Равноправное разделение торта не может быть выполнено с использованием конечного числа запросов RW даже для 2 агентов. ^[9] Более того, для любого ε > 0:

• Связанный ε-справедливый разрез торта требует по крайней мере Ω(log ε ⁻¹ ) запросов. ^[7] Для 2 агентов существует протокол O(log ε ^{−1 ) . [10]} Для 3 или более агентов наиболее известный протокол требует O( n (log n + log ε ⁻¹ )) запросов. ^[11]
• Даже без связности ε-справедливое разрезание торта требует по крайней мере Ω(log ε ⁻¹ / log log ε ⁻¹ ) RW-запросов. ^[9]

Точное разрезание торта (также известное как идеальное разрезание торта ) не может быть выполнено с использованием конечного числа запросов RW даже для 2 агентов. Более того, для любого ε > 0:

• ε-идеальное разрезание торта с минимально возможным числом разрезов требует по крайней мере Ω(log ε ⁻¹ ) запросов. Для 2 агентов существует протокол O(log ε ^{−1 ). [7]} Для 3 или более агентов наиболее известный протокол требует O( n ³ ε ⁻¹ ) запросов. ^[12]

Максиминная доля разрезания торта , когда куски должны быть разделены положительным расстоянием, не может быть выполнена с использованием конечного числа запросов RW. Более того, даже для одного агента не существует алгоритма, который вычисляет максиминную долю агента с использованием конечного числа запросов RW. Однако: ^[13]

• Для любого ε > 0 можно вычислить значение между MMS и MMS-ε, используя O( n log ε ⁻¹ ) RW-запросов.
• Когда пирог круглый (т.е. при честном разрезании пирога ), можно вычислить значение между MMS и MMS-ε, используя O( n ε ^{−1 ) RW-запросов. Вопрос о том, достаточно ли O(} n log ε ⁻¹ ) RW-запросов , остается открытым .

Средне-пропорциональное разрезание торта (т.е. распределение между n семьями , такое, что для каждой семьи среднее значение составляет не менее 1/ n от общего числа) не может быть вычислено с использованием конечного числа запросов RW, даже когда есть 2 семьи с 2 членами в каждой семье. Доказательство заключается в сокращении из справедливого разрезания торта. ^[14]

Варианты

Левый и правый следы

Когда мера значения агента не строго положительна (т. е. есть части, которые агент оценивает как 0), запрос отметки может, в принципе, возвращать бесконечно много значений. Например, если агент оценивает [0,0.9] как 1 и [0.9,1] как 0, то запрос Mark(0,1) может возвращать любое значение между 0.9 и 1. Некоторые алгоритмы требуют более конкретного значения:

• Запрос левой отметки LeftMark( x , r ) возвращает самый левый (наименьший) y такой, что v _i ([ x , y ]) = r ;
• Запрос правой отметки RightMark( x , r ) возвращает самый правый (наибольший) y такой, что v _i ([ x , y ]) = r ;

Если задан только один из этих двух вариантов (в дополнение к запросу Eval), другой вариант не может быть вычислен за конечное время. ^[11]

Двухмерные торты

Модель запроса RW была обобщена на двумерные торты ^[15] и многомерные торты ^{[16] .}

Альтернативные модели

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

Модель прямого откровения

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

Модель с подвижным ножом

В этой модели ножи непрерывно движутся вдоль торта (см. процедуры движущихся ножей ). Эта модель связана с моделью RW следующим образом: любая процедура движущихся ножей с фиксированным числом агентов и фиксированным числом ножей может быть смоделирована с использованием O(log ε ⁻¹ ) RW-запросов. ^[7]

Модель одновременных запросов

В этой модели агенты одновременно отправляют дискретизации своих предпочтений. Дискретизация — это последовательность точек отсечения и значений частей между этими точками отсечения (например: протокол для двух агентов может потребовать, чтобы каждый агент сообщал последовательность из трех точек отсечения (0, x ,1), где значения (0, x ) и ( x ,1) равны 1/2). Эти отчеты используются для вычисления справедливого распределения. Сложность алгоритма в этой модели определяется как максимальное количество интервалов в требуемой дискретизации (поэтому сложность приведенного выше протокола равна 2).

Одним из преимуществ этой модели по сравнению с моделью RW является то, что она позволяет выявлять предпочтения параллельно. Это позволяет вычислять пропорциональный разрез торта за время O( n ), одновременно спрашивая каждого агента о дискретизации с n интервалами (равной ценности). Напротив, в модели RW существует нижняя граница O( n log n ). С другой стороны, в одновременной модели невозможно вычислить разрезание торта без зависти , используя конечную дискретизацию для 3 или более агентов; но для каждого e >0 существует одновременный протокол со сложностью O( n / e ² ), который достигает e -приблизительного разделения без зависти. ^[17]

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

• Оракул спроса (и оракул значения ) — похожая модель запроса в обстановке с неделимыми объектами.

Ссылки

1. Робертсон, Джек; Уэбб, Уильям (1998). Алгоритмы разрезания торта: будьте честны, если можете . Натик, Массачусетс: AK Peters. ISBN 978-1-56881-076-8. LCCN  97041258. OL  2730675W.
2. Gerhard J. Woeginger и Jiri Sgall (2007). «О сложности разрезания торта». Дискретная оптимизация . 4 (2): 213–220. doi : 10.1016/j.disopt.2006.07.003 .
3. Эдмондс, Джефф (2006). «Разрезание торта на самом деле не кусок торта». Труды семнадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам — SODA '06 . С. 271–278. CiteSeerX 10.1.1.412.7166 . doi :10.1145/1109557.1109588. ISBN  978-0898716054., Эдмондс, Джефф (2011). «Разрезание торта на самом деле не является кусочком торта». ACM Transactions on Algorithms . 7 (4): 1–12. CiteSeerX 10.1.1.146.1536 . doi :10.1145/2000807.2000819. S2CID  2440968. 
4. Cseh, Ágnes; Fleiner, Tamás (2020-06-01). «Сложность разрезания торта с неравными долями». ACM Transactions on Algorithms . 16 (3): 29:1–29:21. arXiv : 1709.03152 . doi : 10.1145/3380742. ISSN  1549-6325. S2CID  218517351.
5. Прокачча, Ариэль (2009). «Возжелай пирога ближнего твоего». Труды IJCAI'09 21-й Международной объединенной конференции по искусственному интеллекту : 239–244.
6. Стромквист, Уолтер (2008). "Беззавистные дележи торта не могут быть найдены конечными протоколами" (PDF) . Электронный журнал комбинаторики . 15 . doi : 10.37236/735 .
7. Brânzei, Simina; Nisan, Noam (2018-07-13). "Сложность запросов при разрезании торта". arXiv : 1705.02946 [cs.GT].
8. Холлендер, Александрос; Рубинштейн, Авиад (2023). Разрезание торта без зависти для четырех агентов. С. 113–122. arXiv : 2311.02075 . doi :10.1109/FOCS57990.2023.00015. ISBN 979-8-3503-1894-4. Получено 2024-01-04 .
9. Procaccia, Ariel D.; Wang, Junxing (2017-06-20). "Нижняя граница для справедливого разрезания торта". Труды конференции ACM 2017 года по экономике и вычислениям . EC '17. Кембридж, Массачусетс, США: Ассоциация вычислительной техники. стр. 479–495. doi :10.1145/3033274.3085107. ISBN 978-1-4503-4527-9. S2CID  9834718.
10. Чехларова, Катарина; Пилларова, Ева (2012). «Почти равноправный алгоритм разрезания торта для двух человек». Оптимизация . 61 (11): 1321. doi : 10.1080/02331934.2011.563306. S2CID  120300612.
11. Чехларова, Катарина; Пилларова, Ева (01 ноября 2012 г.). «О вычислимости справедливых делений». Дискретная оптимизация . 9 (4): 249–257. дои : 10.1016/j.disopt.2012.08.001 . ISSN  1572-5286.{{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )
12. Brânzei, Simina; Miltersen, Peter Bro (2015-07-25). "Теорема диктатуры для разрезания торта". Труды 24-й Международной конференции по искусственному интеллекту . IJCAI'15. Буэнос-Айрес, Аргентина: AAAI Press: 482–488. ISBN 978-1-57735-738-4.
13. Элкинд, Эдит; Сегал-Халеви, Эрель; Суксомпонг, Варут (2022). «Остерегайтесь разрыва: разрезание торта с разделением». Искусственный интеллект . 313 : 103783. arXiv : 2012.06682 . doi : 10.1016/j.artint.2022.103783. S2CID  229153490.
14. Сегал-Халеви, Эрель; Ницан, Шмуэль (2019-12-01). «Справедливое разрезание торта среди семей». Социальный выбор и благосостояние . 53 (4): 709–740. arXiv : 1510.03903 . doi : 10.1007/s00355-019-01210-9. ISSN  1432-217X. S2CID  1602396.
15. Сегал-Халеви, Эрель; Ницан, Шмуэль; хасидим, Авинатан; Ауманн, Йонатан (2017). «Честно и справедливо: разрезание торта в двух измерениях». Журнал математической экономики . 70 : 1–28. arXiv : 1409.4511 . doi : 10.1016/j.jmateco.2017.01.007. S2CID  1278209.
16. Чех, Агнес; Флейнер, Тамаш (2018), «Сложность разрезания торта с неравными долями», Алгоритмическая теория игр , Springer International Publishing, стр. 19–30, arXiv : 1709.03152 , doi : 10.1007/978-3-319-99660-8_3, ISBN 9783319996592, S2CID  19245769
17. Балкански, Эрик; Бранзеи, Симина; Курокава, Дэвид; Прокачча, Ариэль (2014-06-21). «Одновременное разрезание торта». Труды конференции AAAI по искусственному интеллекту . 28 (1). doi : 10.1609/aaai.v28i1.8802 . ISSN  2374-3468. S2CID  1867115.