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

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

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

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

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

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

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

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

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

Протокол рассматривает одномерные разрезы. Например, торт может быть одномерным отрезком [0; 1] и каждый кусок является интервалом. Торт может быть прямоугольным и разрезания осуществляются вдоль более длинной стороны (параллельно короткой), так что все куски будут прямоугольными. Каждое разрезание может быть представлено n числами $x_{i},i=1,\dots ,n$, где $x_{i}$ является длиной i-го куска. Мы предполагаем, что полная длина торта равна 1, так что $x_{1}+\dots +x_{n}=1$. Пространство возможных разрезаний тогда представляет собой $(n-1)$-мерный симплекс с n вершинами в пространстве $\mathbb {R} ^{n}$. Протокол работает на этом симплексе следующим образом:

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

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

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

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

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

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

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

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

Алгоритм Симмонса является одним из немногих алгоритмов справедливого дележа, которые реализованы и доступны онлайн.

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

Вычислительная сложность

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

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

Гармоничный съём жилья

Основная статья: Задача о совместном съёме квартиры § Су: по человеку на комнату

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

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

Статьи Сана и Прокачча дают популяризированное объяснение протокола Гармоничного съёма жилья, а на странице приведена онлайновая реализация протокола.

См. статью Задача о совместном съёме квартиры для других решений этой задачи.

Делёж рутинных работ

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

Протокол «Гармоничного съёма жилья» может быть использован для получения распределения рутинных работ без зависти, просто если рассматривать оплату жилья как рутинные обязанности, а помещения игнорируем. Делимость рутинных работ может быть достигнута путём деления времени, потраченного на работу.

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

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

Решение этой задачи для случая 2 участников дележа и 2 или 3 тортов было опубликовано в 2009 году. Если число тортов равно m и каждый торт делится на k кусков, то пространство разрезаний может быть представлено в виде d-размерного многогранника с n вершинами, где $d=m(k-1)$ и $n=k^{m}$. Обобщение леммы Шпернера на многогранники гарантирует, что если этот многогранник триангуляризован и размечен подходящим образом, есть по меньшей мере $n-d$ подсимплексов с полной разметкой. Каждый из этих симплексов соответствует (приблизительному) распределению без зависти, в котором каждый участник получает различную комбинацию кусков. Однако комбинации могут накладываться — один участник может получить «утреннюю» и «вечернюю» смены, в то время как другой получит «вечернюю» и «утреннюю». Хотя это различный выбор, он несовместим. Раздел 4 статьи Клотье, Наймана и Су доказывает, что делёж без зависти на двоих с непересекающимися кусками может быть невозможным, если $m=k=2$, но всегда возможен, если $m=2$ и $k=3$ (то есть по меньшей мере один торт делится на три части и каждый участник получает один кусок от каждого торта, а по меньшей мере один кусок торта выбрасывается). Аналогичные результаты доказаны для трёх тортов.

См. также

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