WikiDer > Утилитарная резка торта

Utilitarian cake-cutting

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

Пример

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

Партнер	Шоколад	Ваниль
Алиса	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}}$ .

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

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

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

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

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

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

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

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

Характеристика правила максимальной суммы

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

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

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

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

Нахождение максимальной суммы делений

Отсоединенные части

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

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

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

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

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

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

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

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

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

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

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

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

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

Поиск максимальной суммы-справедливого распределения

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

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

Свойства максимальных и справедливых распределений

^[7] изучать как без зависти (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. Этот результат распространяется на общие оценки с точностью до аддитивного приближения (т. Е. ${ displaystyle epsilon}$ -EF распределения имеют полезную сумму не менее EQ распределения минус ${ displaystyle epsilon}$ ).

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

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

Navigation