Множество Радона — Никодима

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

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

«Точка 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;1).

Имеется множество ${\displaystyle C}$ («торт»), и множество ${\displaystyle \mathbb {C} }$, которое является сигма-алгеброй подмножеств множества ${\displaystyle C}$.

Имеется ${\displaystyle n}$ участников. Любой участник ${\displaystyle i}$ имеет персональное значение меры ${\displaystyle V_{i}:\mathbb {C} \to \mathbb {R} }$. Эта мера определяет, какова оценка каждого подмножества ${\displaystyle C}$ для этого участника.

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

${\displaystyle V=\sum _{i=1}^{n}V_{i}}$

Заметим, что каждая ${\displaystyle V_{i}}$ является абсолютно непрерывной мерой относительно ${\displaystyle V}$. Следовательно, по теореме Радона — Никодима она имеет производную Радона — Никодима, которая является функцией ${\displaystyle v_{i}:C\to [0,\infty )}$, такой что для любого измеримого подмножества ${\displaystyle X\in \mathbb {C} }$:

${\displaystyle V_{i}(X)=\int _{X}v_{i}\,dV}$

Функции ${\displaystyle v_{i}}$ называются функциями плотности оценок. Они имеют следующие свойства для почти всех точек торта ${\displaystyle x\in C}$^[1]:

• ${\displaystyle \sum _{i=1}^{n}v_{i}(x)=1}$
• ${\displaystyle \forall i:0\leqslant v_{i}(x)\leqslant 1}$

Для любой точки ${\displaystyle x\in C}$ RNS точка точки ${\displaystyle x}$ определяется как:

${\displaystyle v(x)=(v_{1}(x),\dots ,v_{n}(x))}$

Заметим, что ${\displaystyle v(x)}$ является всегда точкой в ${\displaystyle (n-1)}$-мерном единичном симплексе в ${\displaystyle \mathbb {R} ^{n}}$, обозначаемом ${\displaystyle \Delta ^{n-1}}$ (или просто ${\displaystyle \Delta }$, если ${\displaystyle n}$ подразумевается в контексте).

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

${\displaystyle RNS(C)=\{v(x)\mid x\in C\}}$

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

Представим таблицу в форме равностороннего треугольника с потребителями в вершинах… желаемость потребителя ${\displaystyle i}$ в фрагменте торта в точке ${\displaystyle v\in \Delta }$ задаётся барицентрическими координатами ${\displaystyle v_{i}}$, отражающими близость к вершине ${\displaystyle i}$. Тогда ${\displaystyle v_{i}}$ равно 1 в вершине и уменьшается линейно до 0 к противоположной стороне.

Единичный симплекс ${\displaystyle \Delta }$ может быть разделён среди участников, если передать каждому участнику ${\displaystyle i}$ подмножество ${\displaystyle \Delta _{i}}$. Каждый делёж порождает разбиение торта ${\displaystyle C}$, в котором участник ${\displaystyle i}$ получает кусок торта ${\displaystyle C}$, RNS-точки которого попадают в ${\displaystyle \Delta _{i}}$.

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

• Разрезаем ${\displaystyle \Delta }$ в точке (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. Этот пример иллюстрирует общий факт, который мы покажем ниже.

Для любой точки ${\displaystyle w=(w_{1},\dots ,w_{n})\in \Delta }$:

• Скажем, что разбиение ${\displaystyle \Delta =\Delta _{1}\cup \cdots \cup \Delta _{n}}$ принадлежит ${\displaystyle w}$, если:

Для всех ${\displaystyle i,j}$ и всех ${\displaystyle (v_{1},\dots ,v_{n})\in \Delta _{i}}$: ${\displaystyle {\frac {v_{i}}{v_{j}}}\geqslant {\frac {w_{i}}{w_{j}}}}$

• Скажем, что разбиение ${\displaystyle C=X_{1}\cup \cdots \cup X_{n}}$ принадлежит ${\displaystyle w}$, если оно порождено разбиением ${\displaystyle \Delta }$, которое принадлежит ${\displaystyle w}$. То есть:

Для любых ${\displaystyle i,j}$ и для всех ${\displaystyle x\in X_{i}}$: ${\displaystyle {\frac {v_{i}(x)}{v_{j}(x)}}\geqslant {\frac {w_{i}}{w_{j}}}}$

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

Разбиение ${\displaystyle C=X_{1}\cup \cdots \cup X_{n}}$ принадлежит к положительной точке ${\displaystyle w=(w_{1},\dots ,w_{n})\in \Delta ^{+}}$,

тогда и только тогда, когда оно максимизирует сумму: ${\displaystyle {\frac {V_{1}(X_{1})}{w_{1}}}+\cdots +{\frac {V_{1}(X_{n})}{w_{n}}}}$

то есть тогда и только тогда, когда оно является взвешенным разбиением с максимальной полезностью с вектором ${\displaystyle w}$ весов.

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

Положительное разбиение ${\displaystyle C=X_{1}\cup \cdots \cup X_{n}}$ принадлежит некоторой положительной точке в ${\displaystyle \Delta ^{+}}$ тогда и только тогда, когда оно эффективно по Парето.

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

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

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

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

• Множество индивидуальных частей^[англ.]

• Julius B. Barbanel. The geometry of efficient fair division. — Cambridge: Cambridge University Press, 2005. — ISBN 0-521-84248-4. — doi:10.1017/CBO9780511546679. Краткое изложение можно найти в статье
  • Barbanel J. A Geometric Approach to Fair Division // The College Mathematics Journal. — 2010. — Т. 41, вып. 4. — С. 268. — doi:10.4169/074683410x510263.
• 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.