Протоколы Симмонса – Су - Simmons–Su protocols

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

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

Нарезка торта

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Основная статья: Гармония аренды § Вс

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

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

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

Видеть Гармония аренды для дополнительных решений этой проблемы.

Подразделение по хозяйству

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

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

Нарезка нескольких торта

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

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

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

• Топологическая комбинаторика

Рекомендации

1. Су, Ф. Э. (1999). «Гармония аренды: лемма Спернера в справедливом разделении». Американский математический ежемесячник. 106 (10): 930–942. Дои:10.2307/2589747. JSTOR  2589747.
2. Стромквист, Уолтер (1980). «Как правильно разрезать торт». Американский математический ежемесячник. 87 (8): 640–644. Дои:10.2307/2320951. JSTOR  2320951.
3. Стромквист, Уолтер (2008). «Разделение торта без зависти невозможно найти с помощью конечных протоколов» (PDF). Электронный журнал комбинаторики. 15. Дои:10.37236/735. Получено 26 августа 2014.
4. Реализация Фрэнсиса Су, Элиша Петерсона и Патрика Винограда доступна по адресу: https://www.math.hmc.edu/~su/fairdivision/
5. Дэн, X .; Ци, Q .; Сабери, А. (2012). «Алгоритмические решения для резки торта без зависти». Исследование операций. 60 (6): 1461. Дои:10.1287 / opre.1120.1116. S2CID  4430655.
6. Солнце, Альберт. «Чтобы разделить ренту, начните с треугольника». Нью-Йорк Таймс. Получено 26 августа 2014.
7. Прокачча, Ариэль. «Честное разделение и проблема нытьщих философов». Невидимая рука Тьюринга. Получено 26 августа 2014.
8. https://www.math.hmc.edu/~su/fairdivision/
9. https://www.nytimes.com/interactive/2014/science/rent-division-calculator.html
10. Cloutier, J .; Nyman, K. L .; Су, Ф. Э. (2010). «Дивизион с двумя тортами без зависти». Математические социальные науки. 59: 26–37. arXiv:0909.0301. Дои:10.1016 / j.mathsocsci.2009.09.002. S2CID  15381541.
11. Де Лоэра, Дж. А.; Peterson, E .; Эдвард Су, Ф. (2002). "Политическое обобщение леммы Спернера". Журнал комбинаторной теории, серия А. 100: 1–26. Дои:10.1006 / jcta.2002.3274.