Множество Радона — Никодима (Buk'yvmfk Jg;kug — Untk;nbg)

Перейти к навигации Перейти к поиску

В теории справедливого разрезания торта множество Радона — Никодима (англ. Radon–Nikodym set, RNS) — это геометрический объект, представляющий торт на основе оценок различными людьми различных частей этого торта.

Предположим, что мы имеем торт, состоящий из четырёх частей. Имеется два человека, Алиса и Джордж, с различными вкусами, каждое лицо оценивает различные части торта различно. Таблица ниже описывает части и их оценки. Последняя строка, «Точка RNS», объяснена позже.

Шоколад Лимон Ваниль Вишни
оценка Алисы 18 9 1 2
оценка Джорджа 18 0 4 8
точка RNS (0,5;0,5) (1;0) (0,2;0,8) (0,2;0,8)

«Точка RNS» куска торта описывает относительные значения участников этих кусков. Она имеет две координаты — одна для Алисы и одна для Джорджа. Например:

  • Участники согласны о значениях шоколадной части, так что координаты точки RNS также равны (они нормализованы так, что их сумма равна 1).
  • Лимонная часть имеет значение только для Алисы, так что точка RNS имеет координату 1 для Алисы, в то время как для Джорджа координата равна 0.
  • Для ванильной части и части с вишенками отношение между значениями Алисы и Джорджа равно 1:4. Следовательно, такое же отношение выполняется для координат их точек RNS. Заметим, что как ванильная часть, так и часть с вишнями отображаются в ту же самую точку RNS.

RNS торта — это множество всех его точек RNS. В описанном выше торте это множество состоит из трёх точек: {(0,5;0,5), (1;0), (0,2;0,8)}. Оно может быть представлено отрезком (1;0)-(0;1):

(1,0;0,0) (0,9;0,1) (0,8;0,2) (0,7;0,3) (0,6;0,4) (0,5;0,5) (0,4;0,6) (0,3;0,7) (0,2;0,8) (0,1;0,9) (0,0;1,0)
Лимон - - - - Шоколад - - Ваниль, Вишни - -

В результате торт разложен и реконструирован на отрезке (1;0)-(0;1).

Определения

[править | править код]

Имеется множество («торт»), и множество , которое является сигма-алгеброй подмножеств множества .

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

Определим следующую меру:

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

Функции называются функциями плотности оценок. Они имеют следующие свойства для почти всех точек торта [1]:

Для любой точки RNS точка точки определяется как:

Заметим, что является всегда точкой в -мерном единичном симплексе в , обозначаемом (или просто , если подразумевается в контексте).

RNS торта — это множество всех его RNS точек:

Торт разбивается и затем собирается заново внутри . Каждая вершина ассоциируется с одним из n участников. Каждая доля торта отображается в точку в согласно оценкам — чем более ценен кусок для участника, тем он ближе к вершине участника. Это показано в вышеприведённом примере для участников (где просто отрезок между (1,0) и (0,1)). Акин[2] описывает значение RNS для участников:

Представим таблицу в форме равностороннего треугольника с потребителями в вершинах… желаемость потребителя в фрагменте торта в точке задаётся барицентрическими координатами , отражающими близость к вершине . Тогда равно 1 в вершине и уменьшается линейно до 0 к противоположной стороне.

Эффективное RNS разбиение

[править | править код]

Единичный симплекс может быть разделён среди участников, если передать каждому участнику подмножество . Каждый делёж порождает разбиение торта , в котором участник получает кусок торта , RNS-точки которого попадают в .

Здесь два примера разбиений для двух участников, где является отрезком (1;0) — (0;1)

  • Разрезаем в точке (0,4;0,6). Отдаём отрезок (1;0)-(0,4;0,6) Алисе, а отрезок (0,4;0,6)-(0;1) Джорджу. Это соответствует передаче лимонной и шоколадной частей Алисе (полное значение 27) и передаче остатка Джорджу (полное значение 12).
  • Разрезаем ту же точку (0,4;0,6), но отдаём отрезок (1;0)-(0,4;0,6) Джорджу (полное значение 18) и отрезок (0,4;0,6)-(0;1) Алисе (полное значение 3).

Первое разбиение выглядит более эффективным, чем второе — в первом разбиении каждому участнику отдаётся кусок, который более ценен для него/её (ближе к его/её вершине симплекса), в то время как для второго разбиения верно противоположное. Фактически, первое разбиение эффективно по Парето, в то время как второе не эффективно. Например, во втором разбиении Алиса может дать вишни Джорджу в обмен на 2/9 шоколадной части. Это может улучшить полезность разбиения для Алисы на два, а полезность Джорджа на 4. Этот пример иллюстрирует общий факт, который мы покажем ниже.

Для любой точки :

  • Скажем, что разбиение принадлежит , если:
Для всех и всех :
  • Скажем, что разбиение принадлежит , если оно порождено разбиением , которое принадлежит . То есть:
Для любых и для всех :

Можно доказать, что[3]:

Разбиение принадлежит к положительной точке ,
тогда и только тогда, когда оно максимизирует сумму:
то есть тогда и только тогда, когда оно является взвешенным разбиением с максимальной полезностью с вектором весов.

Поскольку любой эффективный по Парето делёж максимален по полезности для некоторых выбранных весов[4], следующая теорема также верна[5]:

Положительное разбиение принадлежит некоторой положительной точке в тогда и только тогда, когда оно эффективно по Парето.

Таким образом имеется отображение между множеством эффективных по Парето разбиений и точками в .

Возвращаясь к вышеприведённому примеру

  • Первое разбиение (отдавая лимонную и шоколадную часть Алисе, а остаток Джорджу) принадлежит точке (0,4;0,6), как и другим точкам, таким как (0,3;0,7) (некоторые разбиения принадлежат более чем одной точке). Более того, разрезание является разрезанием торта согласно полезности, которое максимизирует сумму , и оно также эффективно по Парето.
  • В то же время, второе разбиение не принадлежит какой-либо точке и не эффективно по Парето.
  • Существует несколько точек, которым принадлежат несколько различных разбиений. Например, точка (0,5;0,5). Это точка множества RNS и имеется положительная масса торта, ассоциированная с ними, так что любое разбиение этой массы приводит к разбиению, которое принадлежит (0,5;0,5). Например, отдавая лимонную и шоколадные части Алисе (значение 27) и остаток отдавая Джорджу (значение 12), получим разбиение, которое принадлежит (0,5;0,5). Отдав Алисе всю лимонную часть (значение 9) и остаток Джорджу (значение 30), получим распределение, которое также принадлежит этой точке. Отдав всю лимонную часть и половину шоколадной части Алисе (значение 18) и остаток Джорджу (значение 21), получим распределение, которое также принадлежит ему, и так далее. Все эти разбиения максимизируют сумму . Более того, эта сумма равна 78 во всех этих разбиениях. Они все эффективны по Парето.

RNS множества были представлены как часть теорем Дубинса — Спеньера и использовались для доказательства теоремы Веллера и более поздних результатов Итан Акин[6]. Термин «множество Радона — Никодима» введён Юлиусом Барбанелем[7].

Примечания

[править | править код]
  1. Barbanel, 2005, с. 222.
  2. Akin, 1995, с. 23.
  3. Barbanel, 2005, с. 241—244.
  4. Barbanel, Zwicker, 1997, с. 203.
  5. Barbanel, 2005, с. 246.
  6. Akin, 1995, с. 23Ethan.
  7. Barbanel, 2005.

Литература

[править | править код]
  • Julius B. Barbanel. The geometry of efficient fair division. — Cambridge: Cambridge University Press, 2005. — ISBN 0-521-84248-4. — doi:10.1017/CBO9780511546679. Краткое изложение можно найти в статье
  • Julius B. Barbanel, William S. Zwicker. Two applications of a theorem of Dvoretsky, Wald, and Wolfovitz to cake division // Theory and Decision. — 1997. — Т. 43, вып. 2. — doi:10.1023/a:1004966624893.
  • Ethan Akin. Vilfredo Pareto cuts the cake // Journal of Mathematical Economics. — 1995. — Т. 24. — doi:10.1016/0304-4068(94)00674-y.