Утилитарная резка торта - Utilitarian cake-cutting

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

Пример

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

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

Утилитарное правило дает партнеру максимальную пользу от каждой части. В этом случае утилитарное правило дает Алисе весь шоколад, а Джорджу - всю Ваниль. Максимальная сумма - 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}}$

Деление называется утилитарным или утилитарно-максимальным или maxsum , если он максимизирует следующее выражение: ${\ displaystyle X}$

{\ Displaystyle \ сумма _ {я = 1} ^ {п} {V_ {я} (X_ {я})}}

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

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

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

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

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

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

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

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

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

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

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

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

Отсоединенные кусочки

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

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

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

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

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

Связанные части

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

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

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

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

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

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

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

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

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

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

Монотонность свойств утилитарной нарезки торта

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

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

Смотрите также

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

Languages

In other projects