Эффективная нарезка торта - Efficient cake-cutting

Эффективная нарезка торта проблема в экономика и Информатика. Это включает неоднородный ресурс, такой как торт с разными начинками или земля с разными покрытиями, который предполагается делимый - из нее можно вырезать сколь угодно мелкие кусочки, не разрушая их ценности. Ресурс должен быть разделен между несколькими партнерами, которые имеют разные предпочтения в отношении разных частей торта, то есть кто-то предпочитает шоколадную начинку, кто-то предпочитает вишню, кто-то просто хочет получить как можно больший кусок и т. Д. экономически эффективный. Были изучены несколько понятий эффективности:

• Наиболее распространенное понятие - Парето-эффективность. Это означает, что никакое другое распределение не может быть лучше хотя бы для одного участника и хотя бы так хорошо для всех.
• Более слабое понятие безотходность. Распределение не является расточительным, если ни один агент не получает кусок торта, который стоит 0 для него / нее и более 0 для другого агента.

Чаще всего эффективность изучается в связи с справедливость, и цель - найти подразделение, удовлетворяющее критериям эффективности и справедливости.

Определения

Есть торт ${\displaystyle C}$. Обычно предполагается, что это либо конечный одномерный отрезок, либо двумерный многоугольник, либо конечное подмножество многомерной евклидовой плоскости. ${\displaystyle \mathbb {R} ^{d}}$.

Есть ${\displaystyle n}$ партнеры. Каждый партнер ${\displaystyle i}$ имеет субъективную функцию ценности ${\displaystyle V_{i}}$ который отображает подмножества ${\displaystyle C}$ к числам.

${\displaystyle C}$ должен быть разделен на ${\displaystyle n}$ непересекающиеся подмножества, так что каждый человек получает непересекающееся подмножество. Кусок, выделенный человеку ${\displaystyle i}$ называется ${\displaystyle X_{i}}$, так что ${\displaystyle C=X_{1}\sqcup ...\sqcup X_{n}}$.

В следующих строках мы рассматриваем торт из четырех частей: шоколада, ванили, лимона и сахара и двух агентов: Алисы и Джорджа, со следующими оценками:

	Шоколад	Ваниль	Лимон	Сахар
Ценность Алисы	7	1	2	0
Ценность Георгия	6	4	0	0

Распределение ${\displaystyle X}$называется расточительный если он выделяет какому-то агенту кусок, который равен 0 для этого агента, но стоит больше 0 для другого агента. В символах:

${\displaystyle \exists {i,j}:\exists Z\subseteq X_{i}:V_{i}(Z)=0~~{\text{and}}~~V_{j}(Z)>0}$ и ${\displaystyle \exists {i}:V_{i}(Y_{i})>V_{i}(X_{i})}$.

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

Распределение ${\displaystyle Y}$ Парето-доминирует распределение ${\displaystyle X}$, если хотя бы один человек считает, что ${\displaystyle Y}$ лучше, чем ${\displaystyle X}$, и никто не чувствует, что ${\displaystyle Y}$ хуже чем ${\displaystyle X}$. В символах:

${\displaystyle \forall {i}:\ V_{i}(Y_{i})\geq V_{i}(X_{i})}$ и ${\displaystyle \exists {i}:V_{i}(Y_{i})>V_{i}(X_{i})}$

Распределение ${\displaystyle X}$называется Оптимальный по Парето (PO), если в нем не преобладает Парето в каком-либо другом подразделении, т. Е. Его нельзя улучшить без возражений. В примере с тортом передача всего торта Алисе является PO, но передача всего торта Бобу определяется распределением по Парето, когда часть лимона передается Алисе. В целом (когда нет требований к подключению к частям), каждое нерациональное выделение является преобладающим по Парето, поэтому каждое выделение PO является NW. Однако обратное неверно. Например, выделение шоколада Джорджу и оставшегося торта Алисе - это NW, но не PO - в нем преобладает распределение по Парето за счет распределения Джорджу ванили и половины шоколада. Это связано с тем, что в исходном распределении утилиты (Алиса, Джордж) равны (3, 6), а в альтернативном распределении утилиты - (5.5, 7).

Существование и расчет

Всегда существует эффективное распределение. Например, каждый утилитарно-оптимальная резка торта есть PO, следовательно, и NW.

Однако найти такое распределение может быть сложно. Может оказаться невозможным найти NW-распределение, используя конечное число запросов «mark» и «eval», даже если есть только два агента с кусочно-однородными оценками.^{[1]:9, кл.3} Это связано с тем, что после любого конечного числа таких запросов алгоритм имеет информацию только относительно конечного числа интервалов, и, следовательно, он не может предотвратить потери внутри интервалов: для любого выделения интервала агенту возможно, что этот агент оценивает часть этого интервала равным 0, в то время как другой агент оценивает ту же часть равным 1. Следовательно, PO также не может быть достигнут конечным протоколом.^{[2]:560, Thm.5}

Проблема становится легкой в ​​предположении строгая позитивность (каждый агент оценивает каждую точку пирога строго больше 0): каждое выделение тривиально NW, и каждое выделение, которое дает весь торт одному агенту, тривиально PO (поскольку каждое другое распределение дает этому агенту строго меньшую полезность).

Проблема также проста для алгоритма, который использует прямое откровение вместо запросов. В алгоритме прямого раскрытия каждый агент раскрывает алгоритму всю свою функцию оценки; это возможно, например, когда оценки кусочно-постоянны. С прямым раскрытием легко найти утилитарно-оптимальное распределение (отдавая каждую часть агенту, который ее больше всего ценит), и такое распределение также является PO и NW.

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

Часто требуется найти не только эффективное, но и справедливый согласно различным представлениям о справедливости. Существование по-прежнему сохраняется:

• Распределение на поставку, которое также пропорциональный всегда существует. Например, распределение, максимизирующее сумму значений, подлежащих пропорциональности, всегда существует (поскольку множество всех пропорциональных распределений компактно), и это PO (поскольку пропорциональность сохраняется за счет улучшений Парето).
• Кроме того, распределение PO, которое также без зависти всегда существует. Это не следует прямо из приведенного выше аргумента, поскольку зависть нет сохранены улучшения Парето. Однако это явно доказывается как Теорема Веллера.

В зависимости от вычислительной модели найти такое распределение может быть сложно даже при строго положительных оценках:

• В модели запроса нет конечного алгоритма, который дает каждому агенту положительный часть торта может быть PO даже с двумя агентами со строго положительными оценками. Это связано с тем, что конечный алгоритм всегда знает значения конечного числа интервалов, поэтому он не может избежать неэффективности внутри интервалов: для любого распределения интервалов может быть выгодный обмен подинтервалом, который алгоритм не может обнаружить.
• В модели прямого раскрытия (с кусочно-постоянными оценками) алгоритм рыночного равновесия^[3] дает PO и свободное от зависти (следовательно, пропорциональное) распределение за полиномиальное время для любого числа агентов.

Сочетание эффективности со справедливостью и возможностью подключения

Часто, помимо эффективности и справедливости, фигуры имеют геометрические ограничения. Например, если торт представляет собой интервал, то каждому агенту может потребоваться кусок, являющийся непрерывным интервалом. С этим дополнительным требованием:

• Распределение заказа на поставку, которое также является пропорциональным, всегда существует. Это связано с тем, что набор всех пропорциональных смежных распределений по-прежнему является компактным, и пропорциональность все еще сохраняется за счет улучшений Парето.
• Распределение PO, которое также не требует зависти, может нет существуют, когда есть по крайней мере три агента, даже если они имеют кусочно-постоянные оценки.^{[4]:Пример 5.1}

С вычислительной точки зрения:

• При общих оценках, когда плотности стоимости строго положительны, разделяй и выбирай является PO и пропорционален для двух агентов. Предположим, что w.l.o.g. которую отрезает Алиса, Джордж выбирает крайний левый кусок, а Алиса получает крайний правый кусок. Любое альтернативное распределение, при котором Джордж получает левую сторону, а Алиса получает право, не может быть улучшением по Парето, так как (исходя из предположения о строгой положительности) любое перемещение места разреза влево причиняет Джорджу боль, а любое движение вправо причиняет вред Алисе. Любое альтернативное распределение, при котором Джордж получает право, а Алиса - левое, не может быть улучшением Парето, поскольку при любом таком распределении по крайней мере одно из них должно получить менее 1/2 от общего значения, тогда как в исходном распределении оба получают минимум 1/2.
• При кусочно-постоянных оценках алгоритм рыночного равновесия не обязательно производит связанные части, поэтому он не работает. Однако алгоритм, похожий на ^{[5]:317, Thm.5} может использоваться для нахождения пропорционального распределения, которое максимизирует сумму полезности для любого количества агентов, путем решения ${\displaystyle O(m^{n})}$ линейные программы (где м количество штук).

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

Неаддитивные оценки

Если торт одномерный интервал и каждый человек должен получить связанный интервал, имеет место следующий общий результат: если функции ценности строго монотонны (т. е. каждый человек строго предпочитает кусок всем своим собственным подмножествам), то каждое подразделение EF также является PO (обратите внимание, что это неверно если агенты могут получить отключенные части). Следовательно, в этом случае Протоколы Симмонса – Су создать подразделение PO + EF.

Если торт одномерный круг (т.е. интервал, две конечные точки которого топологически идентифицированы) и каждый человек должен получить соединенную дугу, тогда предыдущий результат не выполняется: разделение EF не обязательно является PE. Кроме того, существуют пары (неаддитивных) функций значений, для которых не существует деления PO + EF. Однако, если есть 2 агента и хотя бы один из них имеет функцию аддитивной ценности, тогда существует подразделение PO + EF.^[6]

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

• Утилитарная резка торта
• Ярмарка нарезки торта
• Цена справедливости

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

1. Яновский, Егор (2012-03-01). «Механизмы нарезки торта». arXiv:1203.0100 [cs.GT ].
2. Курокава, Дэвид; Лай, Джон К .; Прокачча, Ариэль Д. (30.06.2013). «Как разрезать торт до окончания вечеринки». Двадцать седьмая конференция AAAI по искусственному интеллекту.
3. Азиз, Харис; Е, Чун (2014). Лю, Те-Янь; Ци, Ци; Е Инью (ред.). «Алгоритмы вырезания торта для кусочно-постоянных и кусочно-однородных оценок». Интернет и Интернет-экономика. Конспект лекций по информатике. Издательство Springer International. 8877: 1–14. Дои:10.1007/978-3-319-13129-0_1. ISBN  978-3-319-13129-0.
4. Сегал-Халеви, Эрель; Шиклай, Балаж Р. (01.09.2018). «Ресурсо-монотонность и популяционно-монотонность в связном разрезании торта». Математические социальные науки. 95: 19–30. arXiv:1703.08928. Дои:10.1016 / j.mathsocsci.2018.07.001. ISSN  0165-4896.
5. Алиджани, Реза; Фархади, Маджид; Годси, Мохаммад; Седдигин, Масуд; Таджик, Ахмад С. (2017-02-10). «Механизмы без зависти с минимальным количеством разрезов». Тридцать первая конференция AAAI по искусственному интеллекту.
6. Томсон, В. (2006). «Дети плачут на днях рождения. Почему?». Экономическая теория. 31 (3): 501–521. Дои:10.1007 / s00199-006-0109-3.