Разрезание торта согласно полезности

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

Правило полезности отдаёт каждую часть участнику с наивысшей оценкой полезности. В данном случае по правилу полезности вся шоколадная часть достанется Алисе, а всю ванильная — Джорджу. Значение maxsum будет равно 13.

Разрезание согласно полезности несправедливо — оно не пропорционально, поскольку Джордж получает менее половины полной оценки. Оно также не свободно от зависти, поскольку Джордж завидует Алисе.

Обозначим торт буквой ${\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 X}$ называется разбиением по полезности, или максимально полезным (МП), или maxsum, если оно максимизирует следующее выражение:

${\displaystyle \sum _{i=1}^{n}{V_{i}(X_{i})}}$

Концепция часто обобщается путём назначения различных весов каждому участнику. Разбиение ${\displaystyle X}$ называется максимально взвешенно полезным (МВП, англ. weighted-utilitarian-maximal, WUM), если оно максимизирует следующее выражение:

${\displaystyle \sum _{i=1}^{n}{\frac {V_{i}(X_{i})}{w_{i}}}}$,

где ${\displaystyle w_{i}}$ являются заданными положительными константами.

Любое МВП разбиение с положительными весами очевидно эффективно по Парето. Если разбиение ${\displaystyle Y}$ доминирует по Парето разбиение ${\displaystyle X}$, то взвешенная сумма полезностей в ${\displaystyle Y}$ строго больше, чем в ${\displaystyle X}$, так что ${\displaystyle X}$ не может быть МВП разбиением.

Что более удивительно: любое эффективное по Парето разбиения является МВП при некотором выборе весов[1][2].

Христофер П. Чамберс предложил характерные признаки правила МВП[3]. Признаки основаны на следующем свойстве правила разбиения R:

• Эффективность по Парето (ПЭ, англ. Pareto-efficiency, PE): правило R возвращает только разбиения, которые эффективны по Парето.
• Независимость от деления (НД, англ. Division independence, DI): если торт разделён на несколько кусков и каждый из них разрезан согласно правилу R, результат будет тем же самым, как если бы исходный торт был разрезан по правилу R.
• Независимость недостижимой страны (ННС, англ. Independence of infeasible land, IIL): когда подторт разделён согласно правилу R, результат не зависит от пользы участников в других подтортах.
• Положительная обработка равных (ПОР, англ. Positive treatment of equals, PTE): если все участники имеют одинаковые функции полезности, правило R рекомендует по меньшей мере одно разбиение, которое даёт положительную полезность каждому участнику.
• Независимость от масштаба (НШ, англ. Scale-invariance, SI): когда функции оценки участников умножаются на постоянную величину (для разных участников допустимы различные константы), рекомендации, задаваемые правилом R, не меняются.
• Непрерывность (НП, рунди Continuity, CO): для фиксированного куска торта множество схем полезности, которые отображают в специфичное распределение, является замкнутым множеством по поточечной сходимости.

Следующие факты доказаны для участников, которые назначают положительную полезность любому куску торта с положительным размером:

• Если правило R обладает свойствами ПЭ, НД и ННС, то существует последовательность весов ${\displaystyle w_{1},\dots ,w_{n}}$, такая, что все разбиения, рекомендованные правилом R, являются МВП с этими весами (было показано, что любое ПЭ разбиение является МВП с некоторыми весами. Новым является то, что все разбиения, рекомендованные правилом R, являются МВП с теми же весами. Это следует из НД свойствами).
• Если правило R обладает свойствами ПЭ, НД, ННС и ПОР, то все разбиения, рекомендованные правилом R, являются максимально полезными (другими словами, все дележи должны быть МВП и все агенты должны иметь равные веса. Это следует из свойства ПОР).
• Если правило R обладает свойствами ПЭ, НД, ННС и НШ, то правило R является диктаторским правилом — оно отдаёт весь торт одному участнику.
• Если правило R обладает свойствами ПЭ, НД, ННС и НП, то существует последовательность весов ${\displaystyle w_{1},\dots ,w_{n}}$, такая, что правило R является МВП правилом с этими весами (то есть R рекомендует только МВП дележи с этими весами).

Делёж maxsum не всегда справедлив, см. пример выше. Аналогично, справедливый делёж не всегда maxsum.

Одним из подходов разрешения конфликта является ограничение «цены справедливости» — вычисляем верхнюю и нижнюю границы уменьшения суммы полезности, чтобы получить справедливое разбиение. Для деталей см. статью «Цена справедливости».

Другим подходом комбинации эффективности и справедливости является поиск среди всех возможных справедливых дележей дележа с максимальной суммой полезности:

• Подсчёт удовольствия — попытка определить полезности с помощью математических формул.
• Эффективное разрезание торта
• Задача справедливого разрезания торта
• Теорема Веллера
• Эффективное по Парето распределение без зависти
• Максимальное по рангу распределение