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

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

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

Формализация задачи

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

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

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

Пример торта

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

	Шоколадная часть	Ванильная часть
Алиса	9	1
Джордж	6	4

Эффективность

Разбиение $Y$ доминирует по Парето $X$ (считается более оптимальным), если по меньшей мере одно лицо чувствует, что $Y$ лучше, чем $X$, и никто не чувствует, что $Y$ хуже, чем $X$. Символически:

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

Эффективное по Парето (ЭП, англ. Pareto-efficient, PE) распределение — это распределение, которое не доминируется по Парето каким-либо другим распределением, то есть его нельзя улучшить. В примере торта возможно несколько ЭП распределений, при этом . Например, любое разбиение, которое даёт весь торт одному лицу, является ЭП, поскольку любое изменение в распределении приведёт к возражению этого одного лица. Естественно, ЭП распределение не обязательно справедливо.

Комбинация эффективности и справедливости

Разбиение, которое и эффективно по Парето, и пропорционально, называется ЭППР (англ. Pareto-efficient and proportional, PEPR), а разбиение, которое и ЭП, и свободно от зависти, называется ЭПСЗ (англ. Pareto-efficient and envy-free , PEEF) для краткости.

Делёж ЭППР

ЭП делёж можно получить тривиально путём передачи всего торта одному участнику. Но ЭП распределение, которое также и пропорционально, нельзя найти конечным алгоритмом. Доказательство аналогично использованному для проблемы разрезания торта согласно полезности.

Делёж ЭПСЗ

Для n участников с аддитивными функциями оценок, когда куски могут быть несвязными, ЭПСЗ разбиение всегда существует. Это теорема Веллера.

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

Если торт является одномерной окружностью (то есть отрезком, два конца которого топологически отождествлены), а каждый участник должен получить связные дуги, то вышеприведённые результаты не выполняются — СЗ распределения не обязательно ЭП. Кроме того, существуют пары (неаддитивных) функций оценок, для которых никакого ЭПСЗ распределения не существует. Однако, если есть 2 агента и по меньшей мере один из них имеет аддитивную функцию оценок, то ЭПСЗ существует.

См. также

• Разрезание торта согласно полезности
• Задача справедливого разрезания торта
• Цена справедливости