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

В теории справедливого разрезания торта множество Радона — Никодима (Шаблон:Lang-en, 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$ («торт»), и множество $ℂ$, которое является сигма-алгеброй подмножеств множества $C$.

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

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

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

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

$V_i(X)=\underset{X}{\int }{v}_{i}dV$

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

• $\sum _{i=1}^n{v}_i(x)=1$
• $\mathrm{\forall }i:0⩽v_i(x)⩽1$

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

$v(x)=(v_1(x),\dots ,v_n(x))$

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

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

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

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

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

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

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

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

• Разрезаем $\mathrm{\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 \mathrm{\Delta }$:

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

Для всех $i,j$ и всех $(v_1,\dots ,v_n)\in {\mathrm{\Delta }}_i$: $\frac{v_i}{v_j}⩾\frac{w_i}{w_j}$

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

Для любых $i,j$ и для всех $x\in X_i$: $\frac{v_i(x)}{v_j(x)}⩾\frac{w_i}{w_j}$

Можно доказать, чтоШаблон:Sfn:

Разбиение $C=X_1\cup \cdots \cup X_n$ принадлежит к положительной точке $w=(w_1,\dots ,w_n)\in {\mathrm{\Delta }}^{+}$,

тогда и только тогда, когда оно максимизирует сумму: $\frac{V_1(X_1)}{w_1}+\cdots +\frac{V_1(X_n)}{w_n}$

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

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

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

Таким образом имеется отображение между множеством эффективных по Парето разбиений и точками в $\mathrm{\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 множества были представлены как часть теорем Дубинса — Спеньера и использовались для доказательства теоремы Веллера и более поздних результатов Итан АкинШаблон:Sfn. Термин «множество Радона — Никодима» введён Юлиусом БарбанелемШаблон:Sfn.

См. также

• Шаблон:Не переведено 5

Литература

• Шаблон:Книга Краткое изложение можно найти в статье
  • Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья