Ярмарка вырезания тортов, когда игроки присоединяются поздно

Question

Обычное заявление Справедливая проблема вырезания тортов Предполагается, что все игроки $ n $ получают свою долю одновременно. Однако во многих случаях игроки прибывают постепенно. Например, мы можем разделить торт на игроков за $ n $, но затем прибывает новый игрок и хочет доли.

Обычно подразделение Fair Cake требует больших усилий (например, требует от игроков отвечать на многие вопросы), особенно когда количество игроков большое.

Возможно ли использовать существующее подразделение торта более чем $ n $ players, чтобы создать новое подразделение торта для игроков $ n+1 $, с минимальными дополнительными усилиями (т.е. значительно меньше усилий, чем переосмысление торта с нуля)?

Answer 1

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

Фон. Анкет Позвольте мне четко указать модель для вырезания тортов. Мы хотим разделить интервал $ [0,1] $ между игроками $ n $. Каждый игрок $ i $ имеет функцию оценки $ v_i (s) $ над подмножествами $ s $ из торта. Мы предположим, что эта функция является мерой вероятности; Это неотрицательное и аддитивное (для непрерывного $ a, b subteq [0,1] $, $ v_i (a cup b) = v_i (a) + v_i (b) $) и $ v_i ([0,1] ) = 1 $. Решением этой проблемы является протокол или алгоритм, который запрашивает игроков и назначает части интервала. Обратите внимание, что игроки могут ошибочно сообщать/лгать в ответе на запросы.

Некоторые документы будут иметь более конкретные ограничения; например, Функции оценки непрерывны, или кусочно-линейные или кусочно-стойкие.

Пусть части, назначенные игрокам, будут $ {s_1, dots, s_n } $. Мы часто хотим следующих свойств протокола:

• пропорциональность: У каждого игрока $ i $ есть стратегия, которая гарантирует, что он/он получает стоимость не менее $ (1/n) v_i ([0,1]) $. (С точки зрения $ i $, он/он получает 1 доллар/н $ от общей стоимости торта.)
• зависть: У каждого игрока есть стратегия, которая гарантирует, что $ v_i (s_i) geq v_i (s_j) $ для любого другого игрока $ j $. (Каждый игрок предпочитает свою собственную пьесу любому другому игроку.)

Обратите внимание, что Freeby Freevess подразумевает пропорциональность.

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

---

Конкретные вопросы, которые нужно задать. Анкет Две заметки. Во -первых, любой ответ на ваш вопрос решит общую проблему: начните с того, что дайте весь торт игроку $ 1 $, а затем позвольте другим игрокам прибыть в Интернете и итеративно применить этот протокол. Таким образом, мы должны ожидать, что эта проблема будет сложнее, чем стандартная настройка вырезания торта, к которой мы ее применяем.

Во -вторых, мы всегда можем решить вашу проблему, забрав весь торт от всех и используя известный алгоритм, чтобы перераспределить его с нуля. Таким образом, вопрос в том, есть ли несколько более элегантный способ сделать это. Я думаю, что хороший способ определить это: «Когда перераспределение требует меньше времени или меньше сокращений, чем начинать с нуля; и/или когда игроки получают значительную часть своего текущего среза?»

1. Предположим, у нас есть бесплатное распределение для игроков $ n $. Как мы перераспределяем, чтобы произвести бесплатное распределение без зависти среди игроков $ n+1 $?

Я подозреваю, что это очень сложно. Причина в том, что поиск свободного от зависти, эффективное распределение уже является сложной проблемой. Насколько я знаю, известные протоколы могут потребовать неограниченного количества разрезов для торта и очень сложны. (См. Брэмс и Тейлор, Протокол деления тортов без зависти, 1995.) Таким образом, нет ничего лучше, чем забрать весь торт от всех и перераспределить его агентам $ n+1 $, используя Brams-Taylor.

1. Предположим, у нас есть пропорциональное распределение за $ n $; Как перераспределить, чтобы получить пропорциональное распределение за $ n+1 $?

Я думаю, что это все еще сложно (хотя более выполнимо). Рассмотрим случай, когда каждый игрок ценит торт равномерно, и у каждого игрока есть кусок $ 1/N $. Тогда все, что делает новый игрок, потребует перестановки среди всех. Вот еще один плохой случай: предположим, что игрок $ 1 $ имеет ровно $ 1/N $ за ее ломтик, но ценит Slice игрока $ 2 $ по цене $ (n-1)/n $. Предположим, игрок $ 2 $ ценит свой собственный кусочек ровно $ 1/N $, но ценит Slice Player $ 3 $ по цене $ (n-1)/n $, и т. Д., С игроком $ n $, оценивая свой собственный кусочек по 1 доллара// N $ и Player $ 1 $ Slice по цене $ (n-1)/n $. Теперь новый игрок прибывает. Независимо от того, чего хочет новый игрок, ваш протокол в конечном итоге придется перестановаться с игроком $ 2 $ до игрока $ 1 $, от игрока $ 3 $ до игрока $ 2 $ и т. Д.

---

Одна ссылка может быть Уолш, Онлайн -резка торта, в теории алгоритмических решений 2011 (PDF -ссылка). Но я думаю, что Paper предполагает, что мы заранее знаем количество прибывающих агентов, и предполагает, что игрокам следует выделить часть точно, когда они уходят (что до конца протокола), так что на самом деле это не так применимо к вашей проблеме.

---

Один из способов перераспределения пропорционального распределения, который поддерживает пропорциональность, заключается в следующем. Пусть каждый из нынешних игроков $ n $ сократит его выделенный кусок торта в кусочки $ n+1 $, которые он сам одинаково ценит. Игрок $ n+1 $ теперь выберет лучшую часть, по его словам, из каждого из сокращений игрока $ n $. Легко показать, что полученное распределение также пропорционально.

Answer 2

Предположим, что торт/область - это круг $ C $ с радиусом $ r $. Затем мы можем создать справедливые кусочки $ n $ с помощью канонической резки торта и, таким образом, назначить каждому игроку область $ frac { pi r^2} {n} $. Затем мы можем назначить $ (n+1) $ небольшой круг вокруг центра, и последующие новые игроки звонит вокруг этого (глотает часть внутреннего круга) и так далее. Таким образом, каждый игрок получает один смежный кусок/сюжет, который монотонно сжимается для первых игроков $ n+1 $, и движется к центру для тех, кто присоединяется позже.

Выполнить цифры просты; Для первого нового игрока просто решайте

$ qquad pi r_1^2 = frac { pi r^2} {n+1} $

получить радиус для его сюжета. На второй речь

$ qquad begin {align} pi r_1^2 & = frac { pi r^2} {n+2} pi r_2^2 - pi r_1^2 & = frac { pi r ^2} {n+2} end {align} $

Чтобы получить (внешние) радиусы для обоих новых игроков и так далее. Кажется, что игрок $ n + i $ получает внешний радиус $ r_i = frac {r sqrt {i}} { sqrt {n + k}} $ после того, как присоединились дополнительные игроки, но я не доказывал это Анкет

Это то, что вы получаете за $ n = 6 $ и $ k = 0,1,2,3 $:

^{[источник]}

Та же идея работает для регулярных многоугольников с $ n $ sides. Если вы предполагаете прямоугольник в качестве основной формы, вы можете сделать аналогичную вещь, назначив первые столбцы $ n $ одинаково размер и следующие строки игроков (начиная с одной стороны).