Пропорциональная резка торта - Proportional cake-cutting

А пропорциональная резка торта это своего рода ярмарка разрезания торта. Это разделение разнородного ресурса («пирога»), удовлетворяющего соразмерность критерий, а именно, чтобы каждый партнер чувствовал, что его выделенная доля стоит не менее 1 /п от общей суммы.

Когда обсуждается соразмерность, обычно делаются два предположения:

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

Формальные определения

Торт обозначается ${ displaystyle C}$ . Есть ${ displaystyle n}$ люди. Каждый человек ${ displaystyle i}$ имеет функцию ценности ${ displaystyle V_ {i}}$ . Перегородка торта, ${ Displaystyle X_ {1} sqcup cdots sqcup X_ {n} = C}$ , называется пропорциональный если:

${ Displaystyle V_ {я} (X_ {я}) geq V_ {я} (С) / п}$ для каждого человека ${ Displaystyle я в {1, ldots, п }}$ .

Процедуры

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

Есть много способов продлить эту процедуру более чем на 2 человека. У каждого способа есть свои преимущества и недостатки.

Простые процедуры

Последний уменьшитель это самая ранняя процедура пропорционального деления, разработанная для п люди:

Одного из партнеров просят нарисовать фигуру, которую он оценивает как минимум как 1 /п.
Другие партнеры, в свою очередь, имеют возможность заявить, что текущая часть действительно стоит более 1 /п; в этом случае их просят уменьшить его так, чтобы оставшееся значение было 1 /п по их собственной оценке.
Последний партнер, уменьшивший текущую фигуру, получает ее.
Затем оставшийся торт делится таким же образом между оставшимися п - 1 человек.

По индукции можно доказать, что каждый партнер, соблюдающий правила, гарантированно получит значение 1 /п, независимо от того, что делают другие партнеры. Это дискретная процедура, в которую можно играть по очереди. В худшем случае ${ Displaystyle п раз (п-1) / 2 = О (п ^ {2})}$ действия необходимы: одно действие на игрока за ход. Однако большинство этих действий можно выполнить на бумаге; Только п - Фактически требуется 1 кусок торта. Следовательно, если торт является смежным, можно гарантировать, что каждый кусок является смежным.

Dubins – Spanier процедура с подвижным ножом - это версия Last Diminisher, работающая в непрерывном режиме.^[1]

Нож проводят по пирогу параллельно самому себе от одного конца до другого.
Партнер говорит "стоп", когда думает ${ displaystyle 1 / n}$ торта находится слева от ножа. Затем торт разрезают, и они получают этот кусок.
Так повторяется с оставшимся тортом и партнерами. последний партнер получает остаток торта.

Протокол Fink - это алгоритм, который продолжает деление на последовательно меньшие «равные» части.

Первый партнер делит ресурс на части, которые, по их мнению, равны.
Затем второй выбирает половину, оставляя остальное первому партнеру.
Затем каждый из этих двух партнеров делит свои доли на трети.
Третий партнер выбирает две из полученных частей: одну у первого партнера и одну у второго партнера.
Если партнеров четыре, каждый из первых трех партнеров делит свои доли на четверти, и процесс продолжается.

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

Одинокий разделитель - это процедура, основанная на равном разделении, выполняемом одним агентом. Его преимущество состоит в том, что его можно обобщить, чтобы получить симметричная резка торта.

Смотрите также: ^[2]

Рекурсивное сокращение вдвое

Используя стратегию разделяй и властвуй, можно добиться пропорционального деления за время O (п бревноп).^[3] Для простоты процедура описана здесь для четного числа партнеров, но ее можно легко адаптировать к любому количеству партнеров:

Каждого партнера просят провести линию, разделяющую торт на две части, которые, по его мнению, имеют одинаковую ценность. Разрезы не должны пересекаться; простой способ гарантировать это - разрешить только горизонтальные линии или только вертикальные линии.
Алгоритм сортирует п линии в порядке возрастания и разрезает торт посередине линий. Например, если есть 4 партнера, которые проводят линии на Икс = 1, Икс = 3, Икс = 5 и Икс = 9, то алгоритм разрезает торт вертикально на Икс = 4.
Алгоритм назначает каждой из двух половин п/ 2 партнера - партнеры, линия которых находится внутри этой половины. Например, партнеры, проводившие линию в Икс = 1 и Икс = 3 назначаются западной половине, а два других партнера - восточной половине. Каждая половина рекурсивно делится между п/ 2 партнера закреплены за ней.

По индукции можно доказать, что каждому партнеру, играющему по правилам, гарантирована фигура стоимостью не менее 1 /.п, независимо от того, что делают другие партнеры.

Благодаря стратегии «разделяй и властвуй» количество итераций составляет всего O (log п), в отличие от O (п) в процедуре Last Diminisher. На каждой итерации каждый партнер должен сделать одну отметку. Следовательно, общее количество требуемых оценок составляет O (п бревно п).

Этот алгоритм имеет рандомизированную версию, которую можно использовать для уменьшения количества отметок; видеть Алгоритм Even-Paz.

Процедуры отбора

Другой подход к нарезке торта - позволить каждому партнеру нарисовать определенное количество кусочков в зависимости от количества партнеров. п(п) и дайте каждому партнеру по одной из выбранных им фигур, чтобы они не перекрывались.

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

Каждый партнер в частном порядке разделяет торт на п интервалы, которые он считает равноценными; они называются кандидаты.
Протокол предписывает п^ 2 кандидатов, увеличивая их восточный (с запада на восток) и выбирая интервал с наиболее западным восточным концом. Этот интервал называется последняя часть.
Протокол передает последний кусок своему владельцу и удаляет всех кандидатов, пересеченных им. Шаг № 2 затем повторяется с оставшимися интервалами оставшихся п - 1 партнер.

Правило выбора на шаге № 2 гарантирует, что на каждой итерации удаляется не более одного интервала каждого партнера. Следовательно, после каждой итерации количество интервалов для каждого партнера по-прежнему равно количеству партнеров, и процесс может продолжаться до тех пор, пока каждый партнер не получит интервал.^[4]

Этот протокол требует от каждого партнера ответа п запросов, поэтому сложность запроса O (п²), аналогично Last Diminisher.

Рандомизированные версии

Можно использовать рандомизацию, чтобы уменьшить количество запросов. Идея состоит в том, что отчитывается каждый партнер, а не вся совокупность п кандидаты, но только постоянное количество d кандидатов, выбранных случайным образом. Сложность запроса O (п), что, очевидно, является наилучшим из возможных. Во многих случаях все еще можно будет предоставить каждому партнеру одного кандидата, чтобы кандидаты не пересекались. Однако есть сценарии, в которых такое распределение невозможно.

Мы все еще можем разрезать торт, используя O (п) вопросы, если мы пойдем на несколько компромиссов:

Вместо того, чтобы гарантировать полную пропорциональность, мы гарантируем частичная пропорциональность, т.е. каждый партнер получает определенную постоянную долю ж(п) от общей стоимости, где ж(п)<1/п.
Вместо того, чтобы давать каждому партнеру одну смежную фигуру, мы даем каждому партнеру объединение одной или нескольких непересекающихся частей.

Общая схема выглядит следующим образом:^[5]

Каждый партнер в частном порядке разделяет торт на ан штуки равной субъективной ценности. Эти нан части называются кандидаты.
Каждый партнер выбирает 2d кандидатуры частей равномерно в случайном порядке, с заменой. Кандидаты сгруппированы в d пары, которые партнер сообщает алгоритму. Эти nd пары называются четвертьфинальные сетки.
Из каждой четвертьфинальной сетки алгоритм выбирает один кусок - кусок, который пересекает меньшее количество других фигур-кандидатов. Эти nd части называются полуфинальные пьесы.
Для каждого партнера алгоритм выбирает одну деталь; они называются финальные части. Последние части выбираются так, чтобы каждая точка торта была покрыта не более чем двумя финальными кусочками (см. Ниже). В случае успеха переходите к шагу №5. Если это не удается, начните заново с шага №1.
Каждая часть торта, принадлежащая только одному финальному куску, передается владельцу этого куска. Каждая часть торта, принадлежащая двум последним кускам, делится пропорционально любым детерминированным алгоритмом пропорционального деления.

Алгоритм гарантирует, что с вероятностью O (1а²), каждый партнер получает как минимум половину одной из своих фигур-кандидатов, что подразумевает (если значения складываются) ценность как минимум 1/2ан. Есть O (п) кандидаты и O (п) дополнительные деления на шаге 5, каждое из которых занимает O (1) раз. Следовательно, общее время выполнения алгоритма составляет O (п).

Основная проблема в этой схеме - выбор последних частей на шаге №4. Подробнее см. Протокол Эдмондса – Пруха.

Результаты твердости

Результаты твердости сформулированы в терминах «стандартной модели Робертсона – Уэбба», т.е. они относятся к процедурам, использующим два типа действий: «Оценить» и «Вырезать».

Каждая детерминированная процедура пропорционального деления для п≥3 партнера должны использовать не менее п действия, даже если все оценки идентичны.^[3]

Более того, каждая детерминированная или рандомизированная процедура пропорционального деления, назначающая каждому человеку смежную часть, должна использовать Ω (п бревно п) действия.^[6]

Более того, каждая детерминированная процедура пропорционального деления должна использовать Ω (п бревно п) действия, даже если процедуре разрешено назначать каждому партнеру кусок, который является объединением интервалов, и даже если процедуре разрешено только гарантировать приблизительная справедливость. Доказательство основано на оценке снизу сложности поиска для одного игрока кусочка пирога, который одновременно является богатым по стоимости и тонким по ширине.^[7]

Эти результаты твердости подразумевают, что рекурсивное уменьшение вдвое это самый быстрый из возможных алгоритмов для достижения полной пропорциональности с непрерывными частями, и это самый быстрый возможный детерминированный алгоритм для достижения даже частичной пропорциональности и даже с разъединенными частями. Единственный случай, когда он может быть улучшен, - это рандомизированные алгоритмы, гарантирующие частичную пропорциональность с отключенными частями.

Если игроки могут разрезать только с конечной точностью, то нижняя граница Ω (n log n) также включает рандомизированные протоколы.^[7]

В следующей таблице приведены известные результаты:^[5]

Пропорциональность (полный / частичный)	Шт (смежные / непересекающиеся)	Тип протокола (детерминированный / рандомизированный)	Запросы (точное / приблизительное)	# запросы
полный	смежный	дет.	точный	O (п бревно п)^[3] Ω (п бревно п)^[6]
полный	смежный	дет.	приблизительный	Ω (п бревно п)^[6]
полный	смежный	ранд.	точный	O (п бревно п)^[3] Ω (п бревно п)^[6]
полный	смежный	ранд.	приблизительный	Ω (п бревно п)^[6]
полный	отключен	дет.	точный	O (п бревно п)^[3] Ω (п бревно п)^[7]
полный	отключен	дет.	приблизительный	Ω (п бревно п)^[7]
полный	отключен	ранд.	точный	O (п бревно п)^[3]
полный	отключен	ранд.	приблизительный	Ω (п бревно п)^[7]
частичный	смежный	дет.	точный	O (п бревно п)^[3] Ω (п бревно п)^[7]
частичный	смежный	дет.	приблизительный	Ω (п бревно п)^[7]
частичный	смежный	ранд.	точный	O (п бревно п)^[3]
частичный	смежный	ранд.	приблизительный	Ω (п бревно п)^[7]
частичный	отключен	дет.	точный	O (п бревно п)^[3] Ω (п бревно п)^[7]
частичный	отключен	дет.	приблизительный	Ω (п бревно п)^[7]
частичный	отключен	ранд.	точный	O (п)^[5]
частичный	отключен	ранд.	слабо ок. (независимый от ошибок ценности)	O (п)^[5]
частичный	отключен	ранд.	приблизительный	Ω (п бревно п)^[7]

Варианты

Разные права

Критерий пропорциональности может быть обобщен на ситуации, в которых права партнеров не равны. Например, ресурс может принадлежать двум акционерам, таким образом, Алиса владеет 8/13, а Джордж - 5/13. Это приводит к критерию взвешенная пропорциональность (WPR): есть несколько весов ш_я в сумме до 1, и каждый партнер я должен получить хотя бы дробь ш_я ресурса по собственной оценке. Чтобы найти разделение WPR, можно использовать несколько алгоритмов. Основная проблема заключается в том, что количество сокращений может быть большим, даже если партнеров всего два. Видеть пропорциональная нарезка торта с разными правами.

Сверхпропорциональное деление

А сверхпропорциональное деление это разделение, в котором каждый партнер получает строго больше 1 /п ресурса по собственной субъективной оценке.

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

Удивительный факт заключается в том, что, когда оценки являются аддитивными и неатомарными, этого условия также достаточно. Т.е., когда есть хотя бы два партнеров, функция ценности которых даже немного отличается, то существует сверхпропорциональное деление, в котором все партнеры получают более 1 /п. Видеть сверхпропорциональное деление для подробностей.

Ограничение смежности

В дополнение к обычному ограничению, заключающемуся в том, что все части должны быть соединены, в некоторых случаях существуют дополнительные ограничения. В частности, когда торт для разделения - это спорная территория, лежащая между несколькими странами, может потребоваться, чтобы участок, выделенный каждой стране, находился рядом с ее текущим местоположением. Пропорциональное деление с этим свойством всегда существует, и его можно найти, объединив протокол Last Diminisher с геометрическими трюками, включающими конформные отображения. Видеть Проблема раздела земель Хилла – Бека.

Двумерные геометрические ограничения

Когда разделяемый «торт» является двумерным, например земельный участок или рекламное место в печатных или электронных средствах массовой информации, часто требуется, чтобы части удовлетворяли некоторым геометрическим ограничениям в дополнение к возможности соединения. Например, может потребоваться, чтобы каждый кусок был квадратом, толстый прямоугольник, или обычно толстый объект. При таких ограничениях по полноте пропорционального деления обычно не существует, но обычно существует частично пропорциональное деление, которое можно найти с помощью эффективных алгоритмов.^[8]

Экономически эффективное подразделение

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

Например, рассмотрим торт, который содержит 500 граммов шоколада и 500 граммов ванили, разделенных между двумя партнерами, один из которых хочет только шоколад, а другой - только ваниль. Многие протоколы нарезки торта дают каждому агенту 250 г шоколада и 250 г ванили. Это деление пропорционально, потому что каждый партнер получает 0,5 своей общей ценности, поэтому нормализованное социальное благосостояние равно 1. Однако это разделение очень неэффективно, потому что мы могли бы отдать весь шоколад одному партнеру и всю ваниль другому партнеру, получив нормализованное значение. социальное обеспечение 2.

В оптимальное пропорциональное деление Проблема заключается в нахождении пропорционального распределения, которое максимизирует общественное благосостояние среди всех возможных пропорциональных распределений. В настоящее время эта проблема имеет решение только для очень особого случая, когда торт представляет собой одномерный интервал, а функции плотности полезности являются линейными (т. Е. ты(Икс) = Топор + B). В целом проблема NP-сложная. Когда функции полезности не нормализованы (т. Е. Мы позволяем каждому партнеру иметь разное значение для всего торта), проблему даже NP-трудно аппроксимировать в пределах коэффициента 1 /√п.^[9]

Правдивое разделение

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

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

Есть правдивые механизмы для достижения идеального разделения; поскольку идеальное деление пропорционально, это также правдивые механизмы пропорционального деления.

Эти механизмы могут быть расширены для обеспечения сверхпропорциональное деление когда он существует:^[11]

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

Когда существует сверхпропорциональное деление, есть положительная вероятность, что оно будет выбрано на шаге 2. Следовательно, ожидаемая ценность каждого правдивого партнера строго больше 1 /п. Чтобы убедиться в правдивости механизма, рассмотрим три случая: (а) если выбранный раздел действительно сверхпропорционален, то единственный возможный результат лжи - это заставить механизм думать, что это не так; это заставит механизм реализовать идеальное разделение, что будет хуже для всех партнеров, включая лжеца. (b) Если выбранный раздел не является суперпропорциональным, потому что он дает только лжецу значение 1 /п или меньше, то единственный эффект лжи - заставить механизм думать, что перегородка является сверхпропорционально и реализовывать его, что только вредит самому лжецу. (c) Если выбранный раздел действительно не суперпропорциональный, потому что он дает другому партнеру значение 1 /п или меньше, то ложь не имеет никакого эффекта, так как разделение не будет реализовано ни в коем случае.

Пропорциональное разделение обязанностей

Когда ресурс делить нежелательно (как в деление по дому ) пропорциональное деление определяется как деление, дающее каждому человеку в большинстве 1/п ресурса (т.е. знак неравенства инвертирован).

Большинство алгоритмов пропорционального деления можно без труда адаптировать к рутинному делению.