Протоколы Симмонса–Су

Протоколы Симмонса–Су — это несколько протоколов для дележа без зависти . Они основаны на лемме Шпернера . Достоинства этих протоколов в том, что они накладывают мало ограничений на предпочтения партнеров и задают партнерам только простые вопросы, такие как «какую часть вы предпочитаете?».

Были разработаны протоколы для решения нескольких взаимосвязанных проблем:

Разрезание торта

В задаче разрезания торта без зависти «торт» (неоднородный делимый ресурс) должен быть разделен между n партнерами с различными предпочтениями относительно частей торта. Торт должен быть разделен на n частей таким образом, чтобы: (a) каждый партнер получил один связанный кусок, и (b) каждый партнер считал, что его кусок (слабо) лучше, чем все остальные части. Протокол для решения этой задачи был разработан Форестом Симмонсом в 1980 году в переписке с Майклом Старбердом . Он был впервые опубликован Фрэнсисом Су в 1999 году. ^[1]

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

Протокол делает следующие предположения относительно предпочтений партнеров:

1. Независимость от других партнеров : Предпочтение зависит от партнера и всего набора признаков, но не от выбора, сделанного другими партнерами.
2. Голодные партнеры : Партнеры никогда не предпочитают пустой кусок.
3. Топологически замкнутые наборы предпочтений : Любой кусок, который предпочтителен для сходящейся последовательности наборов разрезов, предпочтителен в предельном наборе разрезов. Так, например, если партнер предпочитает первый кусок во всех наборах разрезов, где первый разрез сделан при x  > 0,2, и предпочитает второй кусок во всех наборах разрезов, где первый разрез сделан при x  < 0,2, то в наборе разрезов, где первый разрез сделан при x  = 0,2, этот партнер предпочитает оба куска в равной степени.

Условие замкнутости исключает существование отдельных точек торта с положительной желательностью. ^{[ почему? ]}

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

Протокол рассматривает 1-мерные разрезы. Например, торт может быть 1-мерным интервалом [0,1], а каждый кусок является интервалом; или торт может быть прямоугольником, разрезанным вдоль его длинной стороны так, что каждый кусок является прямоугольником. Каждый разрез может быть представлен n числами x _i , i  = 1, ...,  n , где x _i — длина i -го куска. Мы предполагаем, что общая длина торта равна 1, поэтому x ₁  + ... +  x _n  = 1. Таким образом, пространство возможных разделов является ( n  − 1)-мерным симплексом с n вершинами в R ⁿ . Протокол работает с этим симплексом следующим образом:

1. Триангулируйте симплекс разбиений на меньшие симплексы любого желаемого размера.
2. Назначим каждую вершину триангуляции одному партнеру так, чтобы каждый подсимплекс имел n различных меток.
3. Для каждой вершины триангуляции спросите ее владельца: «Какой кусок вы бы выбрали, если бы торт был разрезан с помощью разреза, представленного этой точкой?». Обозначьте эту вершину номером желаемого куска.

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

• Каждая вершина исходного симплекса соответствует разрезу, в котором один кусок содержит весь торт, а все остальные куски пусты. По предположению "голодных партнеров" владелец этой вершины должен предпочесть этот кусок. Следовательно, метки вершин большого симплекса все различны.
• Каждая сторона/грань исходного симплекса соответствует множествам разрезов, в которых некоторые части пусты, а непустые части соответствуют вершинам этой стороны. Согласно предположению «голодных партнеров», владельцы должны предпочитать только непустые части, поэтому вершины триангуляции на этих сторонах могут иметь только одну из меток, которые появляются в соответствующих вершинах.

Следовательно, по лемме Шпернера должен быть хотя бы один подсимплекс, в котором все метки различны. На шаге № 2 мы назначили каждую вершину этого подсимплекса разным партнерам. Следовательно, мы нашли n очень похожих множеств разрезов, в которых разные партнеры предпочитают разные куски торта.

Теперь мы можем триангулировать подсимплекс в более мелкую сетку под-подсимплексов и повторить процесс. Мы получаем последовательность все меньших и меньших симплексов, которые сходятся в одной точке. Эта точка соответствует одному набору разрезов. Согласно предположению «Наборы предпочтений закрыты», в этом наборе разрезов каждый партнер предпочитает другую часть. Это разбиение без зависти!

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

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

Через несколько лет после публикации этого алгоритма было доказано, что разбиения без зависти со связанными частями не могут быть найдены конечными протоколами. ^[3] Следовательно, аппроксимационный алгоритм — это лучшее, на что мы можем надеяться за конечное время. В настоящее время алгоритм Симмонса является единственным аппроксимационным алгоритмом для разрезания торта без зависти со связанными частями.

Алгоритм Симмонса — один из немногих алгоритмов справедливого дележа, которые были реализованы и размещены в сети. ^[4]

Одной из приятных особенностей алгоритма является то, что запросы, которые он задает партнерам, очень просты: им просто нужно решить, в каждом разделе, какую часть они предпочитают. Это отличается от других алгоритмов, которые задают числовые запросы, такие как «отрезать часть со значением 1/3» и т. д.

Сложность выполнения

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

• Когда функции полезности доступны только через оракулы, количество запросов для достижения зависти, меньшей ϵ, равно . ${\displaystyle \Theta ({\frac {1}{\epsilon ^{n}}})}$
• Когда функции полезности задаются явно с помощью алгоритмов с полиномиальным временем, задача разрезания торта без зависти имеет ту же сложность, что и нахождение фиксированной точки Брауэра , т.е. PPAD -полная.

Аренда Гармония

В этой задаче n соседей по дому решили снять дом с n спальнями по арендной плате, установленной домовладельцем. У каждого соседа по дому могут быть разные предпочтения — один может предпочесть большую комнату, другой может предпочесть комнату с видом и т. д. Следующие две задачи должны быть решены одновременно: (a) Назначить комнату каждому партнеру, (b) Определить арендную плату, которую должен платить каждый партнер, так, чтобы сумма платежей равнялась общей арендной плате. Назначение должно быть свободным от зависти , так как каждый партнер слабо предпочитает свою часть комнаты + арендная плата другим частям, т. е. ни один партнер не хотел бы снимать другую комнату по арендной плате, назначенной для этой комнаты. Протокол для решения этой задачи был разработан Фрэнсисом Су в 1999 году. ^[1]

Идея заключается в следующем. Нормализуем общую арендную плату до 1. Тогда каждая схема ценообразования является точкой в ​​-мерном симплексе с вершинами в . Протокол Су работает с дуализированной версией этого симплекса аналогично протоколам Симмонса–Су для разрезания торта: для каждой вершины триангуляции двойственного симплекса, которая соответствует определенной схеме ценообразования, он спрашивает у партнера-владельца «какую комнату вы предпочитаете в этой схеме ценообразования?». Это приводит к раскраске Шпернера двойственного симплекса, и, таким образом, существует небольшой подсимплекс, который соответствует приблизительному свободному от зависти назначению комнат и арендной платы. ${\displaystyle (n-1)}$ ${\displaystyle n}$ ${\displaystyle \mathbb {R} ^{n}}$

^[6] и ^[7] предоставляют популярные объяснения протокола Rental Harmony. ^[8] и ^[9] предоставляют онлайн-реализации.

Дополнительные решения этой проблемы см. в разделе «Гармония аренды» .

Разделение обязанностей

В этой задаче есть работа, которую необходимо разделить между n партнерами, например, стрижка газона на большой площади.

Протокол Rental Harmony можно использовать для приблизительного распределения обязанностей без зависти, просто думая об арендных платежах как о обязанностях и игнорируя комнаты. Делимость обязанностей может быть достигнута путем деления времени, затрачиваемого на них. ^[1]

Многослойная нарезка торта

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

Решение этой проблемы для случая 2 партнеров и 2 или 3 тортов было опубликовано в 2009 году. ^[10] Если количество тортов равно m , и каждый торт разделен на k частей, то пространство разделов может быть представлено n -вершинным d -мерным многогранником , где d = m ( k  − 1) и n  =  k ^m . Обобщение леммы Шпернера на многогранники ^[11] гарантирует, что если этот многогранник триангулирован и помечен соответствующим образом, то существует по крайней мере n  −  d подсимплексов с полной маркировкой; каждый из этих симплексов соответствует (приблизительному) распределению без зависти, в котором каждый партнер получает различную комбинацию частей. Однако комбинации могут перекрываться: один партнер может получить «утреннюю» и «вечернюю» смены, в то время как другой партнер может получить «вечернюю» и «вечернюю». Хотя это разные выборы, они несовместимы. Раздел 4 ^[10] доказывает, что раздел без зависти между двумя партнерами с непересекающимися кусками может быть невозможен, если m  =  k  = 2, но всегда возможен, если m  = 2 и k  = 3 (т. е. по крайней мере один торт делится на три куска, каждый партнер получает по одному куску от каждого торта, и по крайней мере один кусок отбрасывается). Аналогичные результаты доказаны для трех тортов.

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

• Топологическая комбинаторика
• Калькулятор справедливого деления (Java-апплет алгоритмов Симмонса-Су) в колледже Харви Мадда

Ссылки

1. Su, FE (1999). «Rental Harmony: лемма Спернера в справедливом дележе». The American Mathematical Monthly . 106 (10): 930–942. doi :10.2307/2589747. JSTOR  2589747.
2. Стромквист, Уолтер (1980). «Как честно разрезать торт». The American Mathematical Monthly . 87 (8): 640–644. doi :10.2307/2320951. JSTOR  2320951.
3. Stromquist, Walter (2008). "Envy-free cake delegates cannot be found by final protocols" (PDF) . Электронный журнал комбинаторики . 15 . doi : 10.37236/735 . Получено 26 августа 2014 г. .
4. Реализация Фрэнсиса Су, Элиши Петерсон и Патрика Винограда доступна по адресу: https://www.math.hmc.edu/~su/fairdivision/
5. Дэн, X.; Ци, Q.; Сабери, A. (2012). «Алгоритмические решения для разрезания торта без зависти». Исследование операций . 60 (6): 1461. doi :10.1287/opre.1120.1116. S2CID  4430655.
6. Sun, Albert (28 апреля 2014 г.). «Чтобы разделить ренту, начните с треугольника». The New York Times . Получено 26 августа 2014 г.
7. Прокачча, Ариэль (15 августа 2012 г.). «Справедливое деление и проблема нытиков-философов». Невидимая рука Тьюринга . Получено 26 августа 2014 г.
8. «Калькулятор справедливого деления – Фрэнсис Су».
9. «Распределите арендную плату справедливо». The New York Times . 28 апреля 2014 г.
10. Cloutier, J.; Nyman, KL; Su, FE (2010). «Двухпользовательский многотортовый раздел без зависти». Математические общественные науки . 59 : 26–37. arXiv : 0909.0301 . doi : 10.1016/j.mathsocsci.2009.09.002. S2CID  15381541.
11. Де Лоэра, JA ; Петерсон, Э.; Эдвард Су, Ф. (2002). «Политопическое обобщение леммы Спернера». Журнал комбинаторной теории, серия А. 100 : 1–26. дои : 10.1006/jcta.2002.3274 .