Русская Википедия:Эффективное разрезание торта
Эффекти́вное разреза́ние то́рта — задача в экономике и информатике: имеется неоднородный ресурс, такой как торт с различными видами украшений или участок земли с различной растительностью. Предполагается, что ресурс разделяем — его можно разрезать на сколь угодно малые части без потери ценности. Ресурс следует разделить между несколькими участниками, учитывая их запросы: некоторые люди предпочитают шоколадные украшения, другие — вишенки, а кто-то желает получить как можно больший кусок и так далее. Итоговое разбиение должно получиться эффективным по Парето.
Наиболее часто эффективность изучалась в связи со справедливостью, когда целью ставился поиск разбиения, удовлетворяющего обоим критериям — как эффективности, так и справедливости.
Формализация задачи
Есть торт <math>C</math>. Обычно предполагается модель в виде конечного одномерного отрезка, либо двумерного многоугольника, либо конечного подмножества многомерного евклидова пространства <math>\mathbb{R}^d</math>.
Пусть имеется <math>n</math> участников. Каждый участник <math>i</math> имеет функцию субъективной оценки <math>V_i</math> рассматриваемого ресурса, которая отображает подмножества <math>C</math> в числа.
Требуется разбить <math>C</math> на <math>n</math> непересекающихся подмножеств, таких что каждый участник получает отдельный кусок. Кусок, передаваемый участнику <math>i</math> обозначим как <math>X_i</math>; таким образом <math>C = X_1 \sqcup ... \sqcup X_n</math>.
Пример торта
Ниже мы рассмотрим торт, состоящий из двух частей, шоколадной и ванильной, который делят двое: Алиса и Джордж. Пусть значения функций оценки у них имеют значения:
| Шоколадная часть | Ванильная часть | |
|---|---|---|
| Алиса | 9 | 1 |
| Джордж | 6 | 4 |
Эффективность
Разбиение <math>Y</math> доминирует по Парето <math>X</math> (считается более оптимальным), если по меньшей мере одно лицо чувствует, что <math>Y</math> лучше, чем <math>X</math>, и никто не чувствует, что <math>Y</math> хуже, чем <math>X</math>. Символически:
- <math>\forall{i}:\ V_i(Y_i)\geqslant V_i(X_i)</math> и <math>\exists{i}: V_i(Y_i)>V_i(X_i)</math>
Эффективное по Парето (ЭП, Шаблон:Lang-en, PE) распределение — это распределение, которое не доминируется по Парето каким-либо другим распределением, то есть его нельзя улучшить. В примере торта возможно несколько ЭП распределений, при этом . Например, любое разбиение, которое даёт весь торт одному лицу, является ЭП, поскольку любое изменение в распределении приведёт к возражению этого одного лица. Естественно, ЭП распределение не обязательно справедливо.
Комбинация эффективности и справедливости
Разбиение, которое и эффективно по Парето, и пропорционально, называется ЭППР (Шаблон:Lang-en, PEPR), а разбиение, которое и ЭП, и свободно от зависти, называется ЭПСЗ (Шаблон:Lang-en, PEEF) для краткости.
Делёж ЭППР
ЭП делёж можно получить тривиально путём передачи всего торта одному участнику. Но ЭП распределение, которое также и пропорционально, нельзя найти конечным алгоритмом. Доказательство аналогично использованному для проблемы разрезания торта согласно полезности.
Делёж ЭПСЗ
Для n участников с аддитивными функциями оценок, когда куски могут быть несвязными, ЭПСЗ разбиение всегда существует. Это теорема Веллера.
Если торт является одномерным отрезком и каждое лицо должно получить связный отрезок, выполняются следующие общие результаты: если функции оценок строго монотонны (то есть каждое лицо строго предпочитает кусок всем его собственным подмножествам), то любое СЗ распределение является также ЭП (заметим, что это не верно, если агенты могут получать разрезанные куски). Следовательно, в этом случае протоколы Симмонса — Су создают ЭПСЗ разбиение.
Если торт является одномерной окружностью (то есть отрезком, два конца которого топологически отождествлены), а каждый участник должен получить связные дуги, то вышеприведённые результаты не выполняются — СЗ распределения не обязательно ЭП. Кроме того, существуют пары (неаддитивных) функций оценок, для которых никакого ЭПСЗ распределения не существует. Однако, если есть 2 агента и по меньшей мере один из них имеет аддитивную функцию оценок, то ЭПСЗ существуетШаблон:Sfn.
См. также
Примечания
Литература
- Шаблон:Статья. Заголовок: «Дети плачут на вечеринках по поводу дня рождения. Почему?»
Шаблон:Refend Шаблон:Нет ссылок
