Эффективная нарезка торта

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

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

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

Определения

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

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

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

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

	Шоколад	Ваниль	Лимон	Сахар
Ценность Алисы	7	1	2	0
Значение Джорджа	6	4	0	0

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

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

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

Распределение $Y$ Парето-доминирует распределение $X$ , если хоть один человек это чувствует $Y$ лучше, чем $X$ , и никто этого не чувствует $Y$ хуже, чем $X$ . В символах:

\forall {i}:\ V_{i}(Y_{i})\geq V_{i}(X_{i})

и

\exists {i}:V_{i}(Y_{i})>V_{i}(X_{i})

Распределение $X$ называется оптимальным по Парето (ПО), если в нем не доминирует по Парето какое-либо другое разделение, т. е. его нельзя улучшить без возражений. В примере с тортом передача всего торта Алисе является 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, которое также не вызывает зависти . Это не следует непосредственно из приведенного выше аргумента, поскольку свобода от зависти не сохраняется за счет улучшений по Парето. Однако она доказывается явно как теорема Веллера .

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

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

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

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

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

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

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

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

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

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

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

См. также

Ссылки

^ Яновский, Егор (01 марта 2012 г.). «Механизмы резки торта». arXiv : 1203.0100 [ cs.GT ].
^ Курокава, Дэвид; Лай, Джон К.; Прокачча, Ариэль Д. (30 июня 2013 г.). «Как разрезать торт до окончания вечеринки» . Двадцать седьмая конференция AAAI по искусственному интеллекту . 27 : 555–561. дои : 10.1609/aaai.v27i1.8629 . S2CID 12638556 .
^ Азиз, Харис; Йе, Чун (14–17 декабря 2014 г.). «Алгоритмы разрезания торта для кусочно-постоянных и кусочно-равномерных оценок». В Лю, Те-Янь; Ци, Ци; Йе, Иньюй (ред.). Экономика Интернета и Интернета . 10-я Международная конференция «Экономика Интернета и Интернета», Пекин, Китай. Конспекты лекций по информатике. Том. 8877. Международное издательство Springer. стр. 1–14. arXiv : 1307.2908 . дои : 10.1007/978-3-319-13129-0_1 . ISBN 978-3-319-13129-0 . S2CID 18365892 .
^ Сегал-Халеви, Эрель; Шиклай, Балаж Р. (01 сентября 2018 г.). «Ресурсная монотонность и популяционная монотонность в связанном разрезании торта». Математические социальные науки . 95 : 19–30. arXiv : 1703.08928 . doi : 10.1016/j.mathsocsci.2018.07.001 . ISSN 0165-4896 . S2CID 16282641 .
^ Алиджани, Реза; Фархади, Маджид; Годси, Мохаммед; Седдигин, Масуд; Таджик, Ахмад С. (10 февраля 2017 г.). «Механизмы без зависти с минимальным количеством сокращений» . Тридцать первая конференция AAAI по искусственному интеллекту . 31 . дои : 10.1609/aaai.v31i1.10584 . S2CID 789550 .
^ Томсон, В. (2006). «Дети плачут на днях рождения. Почему?». Экономическая теория . 31 (3): 501–521. дои : 10.1007/s00199-006-0109-3 . S2CID 154089829 .

[1] Яновский, Егор (01 марта 2012 г.). «Механизмы резки торта». arXiv : 1203.0100 [ cs.GT ].

[2] Курокава, Дэвид; Лай, Джон К.; Прокачча, Ариэль Д. (30 июня 2013 г.). «Как разрезать торт до окончания вечеринки» . Двадцать седьмая конференция AAAI по искусственному интеллекту . 27 : 555–561. дои : 10.1609/aaai.v27i1.8629 . S2CID 12638556 .

[3] Азиз, Харис; Йе, Чун (14–17 декабря 2014 г.). «Алгоритмы разрезания торта для кусочно-постоянных и кусочно-равномерных оценок». В Лю, Те-Янь; Ци, Ци; Йе, Иньюй (ред.). Экономика Интернета и Интернета . 10-я Международная конференция «Экономика Интернета и Интернета», Пекин, Китай. Конспекты лекций по информатике. Том. 8877. Международное издательство Springer. стр. 1–14. arXiv : 1307.2908 . дои : 10.1007/978-3-319-13129-0_1 . ISBN 978-3-319-13129-0 . S2CID 18365892 .

[4] Сегал-Халеви, Эрель; Шиклай, Балаж Р. (01 сентября 2018 г.). «Ресурсная монотонность и популяционная монотонность в связанном разрезании торта». Математические социальные науки . 95 : 19–30. arXiv : 1703.08928 . doi : 10.1016/j.mathsocsci.2018.07.001 . ISSN 0165-4896 . S2CID 16282641 .

[5] Алиджани, Реза; Фархади, Маджид; Годси, Мохаммед; Седдигин, Масуд; Таджик, Ахмад С. (10 февраля 2017 г.). «Механизмы без зависти с минимальным количеством сокращений» . Тридцать первая конференция AAAI по искусственному интеллекту . 31 . дои : 10.1609/aaai.v31i1.10584 . S2CID 789550 .

[t07-6] Томсон, В. (2006). «Дети плачут на днях рождения. Почему?». Экономическая теория . 31 (3): 501–521. дои : 10.1007/s00199-006-0109-3 . S2CID 154089829 .

[1]

[2]

[3]

[4]

[5]

[6]