Показать меню

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

Разрезание торта согласно полезности (или разрезание торта по maxsum) — это правило дележа неоднородных ресурсов, таких как торт или земельная недвижимость, между несколькими участниками с различными функциями количественной полезности так, что сумма полезности для участников будет как можно больше. Такое разрезание было вдохновлено философией утилитаризма. Разрезание торта согласно полезности часто бывает «несправедливым». Следовательно, утилитаризм конфликтует со справедливым разрезанием торта.

Пример

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

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

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

Обозначения

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

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

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

Разбиение X {displaystyle X} называется разбиением по полезности, или максимально полезным (МП), или maxsum, если оно максимизирует следующее выражение:

∑ i = 1 n V i ( X i ) {displaystyle sum _{i=1}^{n}{V_{i}(X_{i})}}

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

∑ i = 1 n V i ( X i ) w i {displaystyle sum _{i=1}^{n}{frac {V_{i}(X_{i})}{w_{i}}}}

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

Maxsum и эффективность по Парето

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

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

Характерные признаки правила maxsum

Христофер П. Чамберс предложил характерные признаки правила МВП. Признаки основаны на следующем свойстве правила разбиения 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 обладает свойствами ПЭ, НД и ННС, то существует последовательность весов w 1 , … , w n {displaystyle w_{1},dots ,w_{n}} , такое что все разбиения, рекомендованные правилом R являются МВП с этими весами (было показано, что любое ПЭ разбиение является МВП с некоторыми весами. Новым является то, что все разбиения, рекомендованные правилом R являются МВП с теми же весами. Это следует из НД свойствами).
  • Если правило R обладает свойствами ПЭ, НД, ННС и ПОР, то все разбиения, рекомендованные правилом R являются максимально полезными (другими словами, все дележи должны быть МВП и все агенты должны иметь равные веса. Это следует из свойства ПОР).
  • Если правило R обладает свойствами ПЭ, НД, ННС и НШ, то правило R является диктаторским правилом — оно отдаёт весь торт одному участнику.
  • Если правило R обладает свойствами ПЭ, НД, ННС и НП, то существует последовательность весов w 1 , … , w n {displaystyle w_{1},dots ,w_{n}} , такая что правило R является МВП правилом с этими весами (то есть R рекомендует только МВП дележи с этими весами).

Нахождение maxsum разбиений

Несвязные куски

Если функции оценок аддитивны, maxsum дележи всегда существуют. Интуитивно мы можем дать каждую часть торта участнику, который оценивает его максимально, как в примере выше. Аналогично, МВП делёж может быть найден путём передачи каждой части торта партнёру, для которого значение отношения V i / w i {displaystyle V_{i}/w_{i}} самое большое.

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

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

Хорошей новостью является то, что maxsum разбиение всё же существует. Это следствие теоремы компактности Дубинса — Спеньера и это может быть доказано с помощью множества Радона — Никодима.

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

Связные куски

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

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

Для любого множества положительных весов существует МВП разбиение и оно может быть найдено аналогичным образом.

Maxsum и справедливость

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

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

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

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

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

  • Для n {displaystyle n} участников с кусочно-постоянными оценками: делим торт на m полностью константных областей (). Решаем задачу линейного программирования с nm переменными — каждая пара (агент,область) имеет переменную, которая определяет долю области, передаваемую агенту. Для каждой области имеется ограничение, утверждающее, что сумма всех частей области равна 1. Для каждой пары (агент,агент) имеется ограничение, утверждающее, что первый агент не завидует второму агенту. Заметим, что разбиение торта, получаемое такой процедурой, может оказаться крайне мелким.
  • Для 2 {displaystyle 2} участников с кусочно-линейными оценками: для каждой точки торта вычисляем отношение между полезностями: r = u 1 / u 2 {displaystyle r=u_{1}/u_{2}} . Отдаём участнику 1 точки с r ⩾ r ∗ {displaystyle rgeqslant r^{*}} , а участнику 2 точки с r < r ∗ {displaystyle r<r^{*}} , где r ∗ {displaystyle r^{*}} является порогом, вычисленным так, что делёж будет свободным от зависти. В общем случае r ∗ {displaystyle r^{*}} не может быть вычислен, поскольку может быть иррациональным, но на практике, когда оценки кусочно-линейны, r ∗ {displaystyle r^{*}} можно аппроксимировать аппроксимационным алгоритмом «иррационального поиска». Для любого ϵ > 0 {displaystyle epsilon >0} алгоритм находит распределение, которое является ϵ {displaystyle epsilon } -СЗ (значение для каждого агента не меньше значения для любого другого агента минус ϵ {displaystyle epsilon } ) и сумма достигает как минимум максимальной суммы СЗ распределений. Время работы алгоритма полиномиально зависит от входных данных и от log ⁡ ( 1 / ϵ ) {displaystyle log(1/epsilon )} .
  • Для n {displaystyle n} участников с оценками общего вида: аддитивная аппроксимация для получения свободного от зависти и эффективного распределения, основываясь на алгоритме кусочно-линейной оценки.
  • Свойства maxsum-справедливых распределений

    В статье Брамса с соавторами изучаются как свободный от зависти (СЗ,англ. envy-free, EF), так и беспристрастный (БД, англ. equitable, EQ) дележи торта и устанавливается связь их с maxsum и оптимальными по Парето (ОП, англ. Pareto-optimality, PO) дележам. Как было объяснено выше, maxsum распределения всегда ОП. Однако, когда maxsum ограничено условием справедливости, это не обязательно верно. Они доказали следующее

    • Когда имеется два агента, СЗ максимальное, БД максимальное и СЗ-БД максимальное распределение всегда будут ОП.
    • Когда имеется три и более агентов с кусочно-однородными оценками, СЗ максимальные распределения всегда ОП (поскольку СЗ эквивалентно пропорциональности, что сохраняется при улучшениях по Парето). Однако может не быть БД максимального и БД-СЗ максимального распределений, которые были бы ОП.
    • Если имеется три или более агентов с кусочно-константными функциями оценок (то есть имеющими кусочно-константные плотности), может не быть СЗ максимального распределения, являющегося ОП. Например, рассмотрим торт с тремя областями и тремя агентами со значениями: Алиса: 51/101, 50/101, 0 Боб: 50/101, 51/101, 0 Карл: 51/111, 10/111, 50/111. Правило maxsum даёт область i агенту i, но такой делёж не без зависти, поскольку Карл завидует Алисе. Используя линейное программирование можно найти единственное СЗ максимальное распределение и показать, что оно должно дать паи в регионе 1 и регионе 2 и Алисе и Бобу. Однако такое распределение не может быть ОП, поскольку Алиса и Боб могли бы выиграть от обмена паёв в этих регионах.
    • Если все агенты имеют кусочно-линейные функции оценок, сумма полезностей СЗ максимального распределения не меньше полезностей БД максимального распределения. Этот результат расширяется до общих оценок для аддитивных аппроксимаций (то есть, ϵ {displaystyle epsilon } -СЗ распределения имеют сумму полезностей не меньшую полезностей БД распределений минус ϵ {displaystyle epsilon } ).
    Еще по этой теме:
    Маршалловский спрос
    06:40, 08 декабрь
    Маршалловский спрос
    В теории потребителя маршалловский спрос — количество товара, который потребитель приобретет при заданных ценах и доходе, решая задачу максимизации полезности. Назван по имени английского математика
    Функции полезности на неделимых товарах
    17:57, 04 декабрь
    Функции полезности на неделимых товарах
    Некоторые ветви экономики и теории игр имеют дело с неделимыми товарами, дискретными объектами, которые можно передавать только как целое. Например, в комбинаторных аукционах имеется конечный набор
    Теорема Бондаревой — Шепли
    20:24, 03 декабрь
    Теорема Бондаревой — Шепли
    В теории игр теорема Бондаревой — Шепли описывает необходимые и достаточные условия для непустоты ядра в кооперативной игре. В частности, ядро игры непусто тогда и только тогда, когда игра
    Белохвостиков, Евгений Сергеевич
    11:27, 02 декабрь
    Белохвостиков, Евгений Сергеевич
    Евгений Сергеевич Белохвостиков (1 февраля 1992, Заволжье, Россия) — российский хоккеист, защитник. В настоящее время является свободным агентом. Воспитанник заволжского хоккея. Карьера
    Какими инструментами можно резать панели ламината
    12:17, 30 декабрь
    Какими инструментами можно резать панели ламината
    Процесс монтажа ламината, в принципе, довольно прост. Самым сложным действием в ходе этого мероприятия является, пожалуй, разрезание панелей.
    Какими инструментами разрезать ламинат и как это сделать
    10:55, 03 апрель
    Какими инструментами разрезать ламинат и как это сделать
    Ламинат – напольное покрытие, обращаться с которым сравнительно просто. По крайней мере, пока не понадобится его разрезать. А резать панели ламината приходится все-таки довольно часто
    Комментарии:
    Добавить комментарий
    Ваше Имя:
    Ваш E-Mail: