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

В теории справедливого разрезания торта множество Радона — Никодима (англ. 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).

Определения

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Первое разбиение (отдавая лимонную и шоколадную часть Алисе, а остаток Джорджу) принадлежит точке (0,4;0,6), как и другим точкам, таким как (0,3;0,7) (некоторые разбиения принадлежат более чем одной точке). Более того, разрезание является разрезанием торта согласно полезности, которое максимизирует сумму ${\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), получим распределение, которое также принадлежит ему, и так далее. Все эти разбиения максимизируют сумму ${\frac {V_{\text{Alice}}}{0,5}}+{\frac {V_{\text{George}}}{0,5}}$. Более того, эта сумма равна 78 во всех этих разбиениях. Они все эффективны по Парето.

История

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

См. также

• Множество индивидуальных частей

Литература

• 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.