Протоколы Симмонса – Су - это несколько протоколов для разделения без зависти . Они основаны на лемме Спернера . Достоинства этих протоколов в том, что они накладывают несколько ограничений на предпочтения партнеров и задают партнерам только простые вопросы, такие как «какую часть вы предпочитаете?».
Протоколы были разработаны для решения нескольких связанных проблем:
Нарезка торта
В задаче разрезания торта без зависти «пирог» (неоднородный делимый ресурс) нужно разделить между n партнерами с разными предпочтениями в отношении частей торта. Торт должен быть разделен на n частей таким образом, чтобы: (а) каждый партнер получил один связанный кусок, и (б) каждый партнер считал, что его кусок (слабо) лучше, чем все остальные части. Протокол для решения этой проблемы был разработан Форестом Симмонсом в 1980 году в переписке с Майклом Старбердом . Впервые об этом сообщил Фрэнсис Су в 1999 году. [1]
Учитывая набор нарезки (то есть определенное разделение торта на n кусочков), мы говорим, что партнер предпочитает данный кусок, если он считает, что этот кусок немного лучше, чем все остальные части. «Слабо» означает, что партнер может быть безразличен между фигурой и одной или несколькими другими фигурами, поэтому он может (в случае завязки) «предпочесть» более одной фигуры.
Протокол делает следующие предположения о предпочтениях партнеров:
- Независимость от других партнеров : предпочтение зависит от партнера и всего набора, но не от выбора, сделанного другими партнерами.
- Голодные партнеры : партнеры никогда не предпочитают пустой кусок.
- Топологически замкнутые наборы предпочтений : Любая часть, которая предпочтительна для сходящейся последовательности наборов вырезок, предпочтительна в ограничивающем наборе наборов вырезок. Так, например, если партнер предпочитает первую деталь во всех наборах разрезов, где первый разрез выполняется с x > 0,2, и предпочитает вторую часть во всех наборах разрезов, где первый разрез выполняется с x <0,2, то в разрезе -множество, в котором первый разрез равен x = 0,2, этот партнер одинаково предпочитает обе части.
Условие замкнутости исключает существование отдельных точек пирога с положительной желательностью. [ почему? ]
Эти предположения очень мягкие: в отличие от других протоколов для честной резки торта , служебные функции не должны быть аддитивными или монотонными.
Протокол рассматривает одномерные разрезы. Например, торт может быть одномерным интервалом [0,1], а каждый кусок - интервалом; или торт может быть прямоугольником, разрезанным вдоль его длинной стороны, так что каждый кусок представляет собой прямоугольник. Каждый вырезанный набор может быть представлен n числами x i , i = 1, ..., n , где x i - длина i- го отрезка. Мы предполагаем, что общая длина торта равна 1, поэтому x 1 + ... + x n = 1. Пространство возможных разбиений, таким образом, является ( n - 1) -мерным симплексом с n вершинами в R n . Протокол работает на этом симплексе следующим образом:
- Триангулируйте симплекс разбиений на более мелкие симплексы любого желаемого размера.
- Назначьте каждую вершину триангуляции одному партнеру так, чтобы каждый суб-симплекс имел n разных меток.
- Для каждой вершины триангуляции спросите ее владельца: «Какой кусок вы бы выбрали, если бы торт был разрезан с набором вырезок, представленным этой точкой?». Обозначьте эту вершину номером желаемой детали.
Сгенерированная разметка удовлетворяет требованиям раскраски леммы Спернера :
- Каждая вершина исходного симплекса соответствует набору вырезок, в котором один кусок содержит весь торт, а все остальные кусочки пусты. Исходя из предположения о «голодных партнерах», владелец вершины должен предпочесть эту фигуру. Следовательно, все метки вершин большого симплекса различны.
- Каждая сторона / грань исходного симплекса соответствует наборам разрезов, в которых некоторые части пусты, а непустые части соответствуют вершинам этой стороны. По предположению «голодных партнеров» владельцы должны отдавать предпочтение только непустым частям, поэтому вершины триангуляции на этих сторонах могут иметь только одну из меток, которые появляются в соответствующих вершинах.
Следовательно, по лемме Спернера должен существовать хотя бы один суб-симплекс, в котором все метки различны. На шаге № 2 мы назначили каждую вершину этого суб-симплекса другому партнеру. Таким образом, мы нашли n очень похожих наборов, в которых разные партнеры предпочитают разные кусочки торта.
Теперь мы можем триангулировать суб-симплекс до более тонкой сетки суб-суб-симплексов и повторить процесс. Мы получаем последовательность все меньших и меньших симплексов, которые сходятся в одну точку. Эта точка соответствует единственному набору разрезов. Исходя из предположения, что «наборы предпочтений закрыты», в этом наборе каждый партнер предпочитает отдельную фигуру. Это раздел без зависти!
Существование свободного от зависти разбиения было доказано ранее [2], но доказательство Симмонса также дает конструктивный алгоритм аппроксимации. Например, предположим, что необходимо разделить определенный земельный участок, и партнеры согласны с тем, что разница в плюс-минус 1 сантиметр для них не важна. Затем исходный симплекс можно триангулировать до симплексов с длиной стороны менее 1 см. Тогда каждая точка в под-симплексе, в которой все метки различны, соответствует (приблизительному) разделу без зависти.
В отличие от других протоколов без зависти, которые могут назначать каждому партнеру большое количество крошек, протокол Симмонса дает каждому партнеру единственную подключенную деталь. Более того, если исходный торт прямоугольный, то каждый кусок будет прямоугольником.
Спустя несколько лет после публикации этого алгоритма было доказано, что свободные от зависти разделы со связанными частями не могут быть найдены с помощью конечных протоколов. [3] Следовательно, алгоритм аппроксимации - лучшее, на что мы можем надеяться за конечное время. В настоящее время алгоритм Симмонса является единственным приближенным алгоритмом для вырезания торта без зависти со связанными кусочками.
Алгоритм Симмонса - один из немногих алгоритмов справедливого деления, которые были реализованы и размещены в сети. [4]
Одна из приятных особенностей алгоритма заключается в том, что запросы, которые он задает партнерам, очень просты: им просто нужно решить в каждом разделе, какую часть они предпочитают. Это отличается от других алгоритмов, которые задают числовые запросы, такие как «отрезать кусок со значением 1/3» и т. Д.
Сложность выполнения
Хотя разделение без зависти на соединенные части можно приблизить с любой точностью, используя вышеупомянутый протокол, приближение может занять много времени. В частности: [5]
- Когда служебные функции доступны только через оракулы, количество запросов для достижения зависти меньше равно .
- Когда функции полезности задаются явно с помощью алгоритмов с полиномиальным временем, задача разрезания торта без зависти имеет ту же сложность, что и поиск фиксированной точки Брауэра , то есть PPAD-завершенный .
Арендная Гармония
В этой задаче n соседей по дому решили снять дом с n спальнями в аренду, установленную домовладельцем. У каждого соседа по дому могут быть разные предпочтения - один может предпочесть большую комнату, другой - комнату с красивым видом и т. Д. Следующие две проблемы должны решаться одновременно: (а) назначить комнату каждому партнеру, (б) определить арендную плату что каждый партнер должен платить, так что сумма платежей равна общей арендной плате. Назначение должно быть свободным от зависти, поскольку каждый партнер слабо предпочитает свой участок комнаты + арендная плата другим участкам, т.е. ни один партнер не хотел бы снимать другую комнату по арендной плате, назначенной этой комнате. Протокол для решения этой проблемы был разработан Фрэнсисом Су в 1999 году [1].
Идея в следующем. Нормализовать общую арендную плату до 1. Тогда каждая схема ценообразования представляет собой точку в-мерный симплекс с вершины в . Протокол Су работает с дуализованной версией этого симплекса аналогично протоколам Симмонса – Су для разрезания торта: для каждой вершины триангуляции двойного симплекса, которая соответствует определенной ценовой схеме, он запрашивает партнера-владельца " какой номер вы предпочитаете в этой ценовой схеме? ». Это приводит к окраске двойного симплекса по Спернеру, и, таким образом, существует небольшой суб-симплекс, который соответствует приблизительному распределению комнат и арендной платы без зависти.
[6] и [7] предоставляют популярные объяснения протокола Rental Harmony. [8] и [9] предоставляют интерактивные реализации.
Дополнительные решения этой проблемы см. В разделе « Гармония аренды» .
Подразделение по хозяйству
В этой задаче есть рутинная работа, которую нужно разделить между n партнерами, например, стрижка газона на большой территории.
Протокол «Гармония аренды» можно использовать для приблизительного распределения обязанностей без зависти, просто думая об арендных платежах как о работе и игнорируя комнаты. Делимости хлопот можно добиться, разделив затрачиваемое на них время. [1]
Нарезка нескольких торта
В этой задаче два или более торта должны быть разделены одновременно между двумя или более партнерами, давая каждому партнеру по одному куску от каждого торта. Конечно, если предпочтения независимы (т. Е. Полезность от распределения - это сумма полезностей от выделенного куска в каждом торте), тогда проблема может быть решена методами деления одного торта - просто выполните разделение без зависти на каждый торт отдельно. Вопрос становится интересным, когда партнеры связывают свои предпочтения в отношении тортов, в которых на долю одного торта, которую предпочитает партнер, влияет выделенная ему порция другого торта. Например, если «торты» - это время смены работы в течение двух последовательных дней, типичный сотрудник может предпочесть иметь одну и ту же смену каждый день (например, утро-утро или вечер-вечер), а не разные смены.
Решение этой проблемы для случая 2 партнеров и 2 или 3 тортов было опубликовано в 2009 году. [10] Если количество тортов равно m , и каждый торт разделен на k частей, то пространство разделов можно представить следующим образом: п -vertex д - мерный многогранник , где d = т ( к - 1) и п = к м . Обобщение леммы Шпернера к многогранникам [11] гарантирует , что, если это многогранник триангулирован и маркирован соответствующим образом, существует по крайней мере п - г суб-симплекс с полной маркировкой; каждый из этих симплексов соответствует (приблизительному) распределению без зависти, при котором каждый партнер получает различную комбинацию фигур. Однако комбинации могут перекрываться: одному партнеру могут быть назначены «утренняя» и «вечерняя» смены, а у другого партнера - «вечерняя» и «вечерняя». Хотя это разные варианты, они несовместимы. раздел 4 [10] доказывает, что разделение без зависти на двух партнеров с непересекающимися частями может быть невозможно, если m = k = 2, но всегда возможно, если m = 2 и k = 3 (т.е. хотя бы один торт делится на три куска, каждый партнер получает по одному куску от каждого торта, и как минимум один кусок выбрасывается). Аналогичные результаты доказаны для трех тортов.
Смотрите также
- Топологическая комбинаторика
- Калькулятор справедливого деления (Java-приложение алгоритмов Симмонса-Су) в колледже Харви Мадда
Рекомендации
- ^ a b c Su, FE (1999). «Гармония аренды: лемма Спернера в справедливом делении» . Американский математический ежемесячник . 106 (10): 930–942. DOI : 10.2307 / 2589747 . JSTOR 2589747 .
- ^ Стромквист, Уолтер (1980). «Как правильно разрезать торт». Американский математический ежемесячник . 87 (8): 640–644. DOI : 10.2307 / 2320951 . JSTOR 2320951 .
- ^ Стромквист, Уолтер (2008). «Разделение торта без зависти невозможно найти с помощью конечных протоколов» (PDF) . Электронный журнал комбинаторики . 15 . DOI : 10.37236 / 735 . Проверено 26 августа 2014 .
- ^ Реализация Фрэнсиса Су, Элиши Петерсона и Патрика Винограда доступна по адресу: https://www.math.hmc.edu/~su/fairdivision/
- ^ Дэн, X .; Ци, Q .; Сабери, А. (2012). «Алгоритмические решения для вырезания торта без зависти». Исследование операций . 60 (6): 1461. DOI : 10,1287 / opre.1120.1116 . S2CID 4430655 .
- ^ Солнце, Альберт. «Чтобы разделить ренту, начните с треугольника» . Нью-Йорк Таймс . Проверено 26 августа 2014 .
- ^ Прокачча, Ариэль. «Честное разделение и проблема нытьщих философов» . Невидимая рука Тьюринга . Проверено 26 августа 2014 .
- ^ https://www.math.hmc.edu/~su/fairdivision/
- ^ https://www.nytimes.com/interactive/2014/science/rent-division-calculator.html
- ^ а б Cloutier, J .; Найман, KL; Су, ИП (2010). «Дивизион с двумя тортами без зависти». Математические социальные науки . 59 : 26–37. arXiv : 0909.0301 . DOI : 10.1016 / j.mathsocsci.2009.09.002 . S2CID 15381541 .
- ^ De Loera, JA ; Peterson, E .; Эдвард Су, Ф. (2002). "Политическое обобщение леммы Спернера" . Журнал комбинаторной теории, Серия А . 100 : 1-26. DOI : 10.1006 / jcta.2002.3274 .