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

Есть торт ${\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}}$.

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

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

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

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

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

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