Утилитарное разрезание торта

Утилитарное разрезание торта (также называемое разрезанием максимального торта ) — это правило разделения гетерогенного ресурса, такого как торт или земельное поместье, между несколькими партнерами с разными кардинальными функциями полезности, так что сумма полезностей партнеров максимально велик. Это частный случай утилитарного правила социального выбора . Утилитарное разрезание торта часто бывает несправедливым; следовательно, утилитаризм часто находится в противоречии со справедливым разрезанием торта .

Пример

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

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

Утилитарное правило отдает каждую часть партнеру с наибольшей полезностью. В этом случае утилитарное правило отдает весь шоколад Алисе и всю ваниль Джорджу. Максимальная сумма — 13.

Утилитарное разделение несправедливо: оно непропорционально, поскольку Джордж получает менее половины общей стоимости торта, и не лишено зависти, поскольку Джордж завидует Алисе.

Обозначения

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

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

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

Подразделение $X$ называется утилитарным , или утилитарно-максимальным , или максимальной суммой , если она максимизирует следующее выражение:

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

Эту концепцию часто обобщают, присваивая каждому партнеру разный вес. Подразделение $X$ называется взвешенно-утилитарно-максимальным (WUM), если оно максимизирует следующее выражение:

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

где $w_{i}$ даны положительные константы.

Максум и Парето-эффективность

Каждое деление WUM с положительными весами, очевидно, эффективно по Парето . Это связано с тем, что если подразделение $Y$ Парето-доминирует над делением $X$, то взвешенная сумма полезностей в $Y$ строго больше, чем в $X$, так $X$ не может быть подразделением WUM.

Что еще более удивительно, так это то, что каждое эффективное по Парето деление является WUM для некоторого выбора весов.

Характеристика утилитарного правила

Кристофер П. Чемберс предлагает характеристику правилу WUM. Характеристика основана на следующих свойствах правила деления R :

• Парето-эффективность (PE) : правило R возвращает только те подразделения, которые являются Парето-эффективными.
• Независимость деления (DI) : всякий раз, когда торт делится на несколько частей и каждый торт делится в соответствии с правилом R , результат такой же, как если бы исходный торт был разделен в соответствии R. с
• Независимость неосуществимой земли (IIL) : всякий раз, когда суб-пирог делится в соответствии с R , результат не зависит от полезностей партнеров в других суб-пирогах.
• Позитивное отношение к равным (PTE) : всякий раз, когда все партнеры имеют одинаковую функцию полезности, R рекомендует хотя бы одно деление, которое дает положительную полезность каждому партнеру.
• Масштабная инвариантность (SI) : всякий раз, когда функции полезности партнеров умножаются на константы (возможно, разные константы для каждого партнера), рекомендации, данные R, не меняются.
• Непрерывность (CO) : для фиксированного куска пирога набор профилей полезности, которые сопоставляются с конкретным распределением, является замкнутым набором в условиях поточечной сходимости .

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

• Если R — это PE DI и IIL, то существует последовательность весов $w_{1},\dots ,w_{n}$ так что все подразделения, рекомендованные R, являются WUM с этими весами (известно, что каждое разделение PE является WUM с некоторыми весами; новость заключается в том, что все подразделения, рекомендованные R, являются WUM с одинаковыми весами. Это следует из свойства DI).
• Если R — это PE DI IIL и PTE, то все рекомендуемые R деления являются утилитарно-максимальными (иными словами, все деления должны быть WUM и все агенты должны иметь равные веса. Это следует из свойства PTE).
• Если R — это PE DI IIL и SI, то R — диктаторское правило — оно отдает весь торт одному партнеру.
• Если R — это PE DI IIL и CO, то существует последовательность весов $w_{1},\dots ,w_{n}$ так, что R является правилом WUM с этими весами (т. е. R рекомендует все и только подразделения WUM с этими весами).

Нахождение утилитарных подразделений

Отключенные части

Когда функции стоимости аддитивны, всегда существуют деления на максимальную сумму. Интуитивно мы можем отдать каждую часть торта тому партнеру, который ценит ее больше всего, как в примере выше . Аналогичным образом можно найти подразделения WUM, отдав каждую долю пирога тому партнеру, для которого соотношение $V_{i}/w_{i}$ является крупнейшим.

Этот процесс легко осуществить, когда торт кусочно-однороден , т. е. торт можно разделить на конечное число кусков так, что плотность значений каждого куска постоянна для всех партнеров.

Когда торт не является кусочно-однородным, приведенный выше алгоритм не работает, поскольку необходимо учитывать бесконечное количество различных «кусков».

Подразделения Maxsum все еще существуют. Это следствие теоремы о компактности Дубинса–Спанье , и его также можно доказать с использованием множества Радона–Никодима .

Однако ни один конечный алгоритм не может найти деление максимальной суммы. Доказательство : Конечный алгоритм имеет данные-значения только о конечном числе частей. Т.е. существует только конечное число подмножеств торта, для которых алгоритм знает оценки партнеров. Предположим, что алгоритм остановился после получения данных о значениях $k$ подмножества. Теперь может случиться так, что все партнеры ответили на все вопросы так, как будто у них один и тот же показатель ценности. В этом случае максимально возможное утилитарное значение, которого может достичь алгоритм, равно 1. Однако возможно, что глубоко внутри одного из $k$ частей, существует подмножество, которое два партнера ценят по-разному. В этом случае существует сверхпропорциональное разделение , при котором каждый партнер получает стоимость, превышающую $1/n$, поэтому сумма полезностей строго больше 1. Следовательно, деление, возвращаемое конечным алгоритмом, не является максимальной суммой.

Соединённые части

Когда торт одномерный и его части должны быть связаны, простой алгоритм назначения каждого куска агенту, который ценит его больше всего, больше не работает, даже при кусочно-постоянных оценках . В этом случае проблема нахождения подразделения UM является NP-сложной , и, кроме того, FPTAS невозможен, если P = NP.

Существует 8-факторный алгоритм аппроксимации и управляемый алгоритм с фиксированными параметрами , экспоненциальный по количеству игроков.

Для каждого набора положительных весов существует подразделение WUM, которое можно найти аналогичным способом.

Максум и справедливость

Деление максимальной суммы не всегда справедливо; см. пример выше . Точно так же справедливое разделение не всегда является максимальной суммой.

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

Другой подход к объединению эффективности и справедливости состоит в том, чтобы найти среди всех возможных справедливых разделов справедливый раздел с наибольшей суммой полезностей:

Поиск утилитарно-справедливого распределения

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

1. Для $n$ партнеры с кусочно-постоянными оценками : разделите пирог на m совершенно постоянных областей. Решите линейную программу с переменными nm : каждая пара (агент, регион) имеет переменную, которая определяет долю региона, отданную агенту. Для каждого региона существует ограничение, согласно которому сумма всех дробей из этого региона равна 1; для каждой пары (агент, агент) существует ограничение, заключающееся в том, что первый агент не завидует второму. Обратите внимание, что распределение, полученное с помощью этой процедуры, может быть сильно дробным.
2. Для $2$ партнеры с кусочно-линейными оценками : для каждой точки торта вычислите соотношение между полезностями: $r=u_{1}/u_{2}$. Дайте партнеру 1 баллы с $r\geq r^{*}$ и партнер 2 точки с $r<r^{*}$, где $r^{*}$ — это порог, рассчитанный таким образом, чтобы разделение было свободным от зависти. В общем $r^{*}$ невозможно вычислить, поскольку это может быть иррационально, но на практике, когда оценки кусочно-линейны, $r^{*}$ может быть аппроксимирован алгоритмом аппроксимации «иррационального поиска». Для любого $\epsilon >0$, Алгоритм находит распределение, которое $\epsilon$-EF (ценность каждого агента равна как минимум стоимости каждого другого агента минус $\epsilon$), и достигает суммы, которая является, по крайней мере, максимальной суммой распределения EF. Время его выполнения является полиномиальным по входным и $\log(1/\epsilon )$.
3. Для $n$ партнеры с общими оценками: аддитивная аппроксимация зависти и эффективности, основанная на алгоритме кусочно-постоянных оценок.

Свойства утилитарно-справедливого распределения

Брамс, Фельдман, Лай, Моргенштерн и Прокачча изучите как разделение торта без зависти (EF), так и справедливое (EQ) и свяжите их с максимальной суммой и оптимальностью по Парето (PO). Как объяснялось выше, распределение максимальной суммы всегда является PO. Однако если максимальная сумма ограничена соображениями справедливости, это не обязательно так. Они доказывают следующее:

• При наличии двух агентов распределения maxsum-EF, Maximum-EQ и Maximum-EF-EQ всегда являются PO.
• Когда имеется три или более агентов с кусочно-равномерными оценками , распределения maxsum-EF всегда являются PO (поскольку EF эквивалентен пропорциональности , которая сохраняется при улучшениях Парето). Однако могут отсутствовать . распределения maxsum-EQ и maxsum-EQ-EF, которые являются PO,
• Когда есть три или более агентов с кусочно-постоянными оценками , может не быть даже распределений maxsum-EF, которые были бы PO. Например, рассмотрим торт с тремя регионами и тремя агентами со значениями:

Алиса	51/101	50/101	0
Боб	50/101	51/101	0
Карл	51/111	10/111	50/111

Правило максимальной суммы дает агенту i регион i, но это не EF, поскольку Карл завидует Алисе. Используя линейную программу, можно найти уникальное распределение maxsum-EF и показать, что оно должно совместно использовать как область 1, так и область 2 между Алисой и Бобом. Однако такое распределение не может быть PO, поскольку Алиса и Боб могли бы оба получить выгоду, поменяв свои доли в этих регионах.

• Когда все агенты имеют кусочно-линейные оценки , сумма полезности при распределении maxsum-EF не меньше, чем при распределении maxsum-EQ. Этот результат распространяется на общие оценки вплоть до аддитивной аппроксимации (т. е. распределения ε -EF имеют сумму полезности, равную, по крайней мере, распределениям EQ − ε ).

Свойства монотонности утилитарной резки торта

Когда части могут быть разъединены , абсолютно-утилитарное правило (максимизирующее сумму ненормализованных полезностей) является монотонным по ресурсам и монотонным по численности населения . Относительно-утилитарное правило (максимизация суммы нормированных полезностей) является монотонным для населения, но не монотонным для ресурсов.

Это больше не действует, когда части соединены.

См. также

• Эффективная нарезка торта
• Ярмарка разрезания торта
• Теорема Веллера
• Парето-эффективное деление без зависти
• Ранг-максимальное распределение
• Утилитарное голосование – утилитарный принцип в другом контексте.