Набор Радона–Никодима

В теории справедливого разрезания торта множество Радона –Никодима (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 С}$${\displaystyle \mathbb {C} }$${\displaystyle С}$

Есть партнеры. У каждого партнера есть личная мера ценности . Эта мера определяет, насколько каждая подгруппа ценна для этого партнера.${\displaystyle n}$${\displaystyle я}$ ${\displaystyle V_{i}:\mathbb {C} \to \mathbb {R} }$${\displaystyle С}$

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

${\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}$

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

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

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

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

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

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

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

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

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

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

Вот два примера разбиения для примера с двумя партнерами, где — сегмент между (1,0) и (0,1)${\displaystyle \Дельта}$

• Разрежьте в точке (0.4,0.6). Отдайте отрезок (1,0)-(0.4,0.6) Алисе, а отрезок (0.4,0.6)-(0,1) Джорджу. Это соответствует тому, что Лимон и Шоколад отдаются Алисе (общая стоимость 27), а остальное — Джорджу (общая стоимость 12).${\displaystyle \Дельта}$
• Разрежьте в той же точке (0,4,0,6), но отдайте отрезок (1,0)-(0,4,0,6) Джорджу (общее значение 18), а отрезок (0,4,0,6)-(0,1) — Алисе (общее значение 3).

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

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

• Говорят, что раздел принадлежит , если:${\displaystyle \Дельта =\Дельта _{1}\cup \cdots \cup \Дельта _{n}}$ ${\displaystyle w}$

Для всех и для всех :${\displaystyle я,j}$${\displaystyle (v_{1},\dots ,v_{n})\in \Delta _{i}}$${\displaystyle {\frac {v_{i}}{v_{j}}}\geq {\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)}}\geq {\frac {w_{i}}{w_{j}}}}$

Можно доказать, что: ^{[1] : 241–244}

Раздел принадлежит положительной точке ,${\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}$

Поскольку каждое эффективное по Парето деление является взвешенно-утилитарно-максимальным для некоторого набора весов, ^[3] следующая теорема также верна: ^{[1] : 246}

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

если и только если оно является Парето-эффективным .

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

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

• Первое разбиение (отдача Лимона и Шоколада Алисе, а остальных Джорджу) принадлежит точке , а также другим точкам, таким как (некоторые разбиения принадлежат более чем одной точке). Действительно, это утилитарное разрезание торта , которое максимизирует сумму , и оно также является Парето-эффективным.${\displaystyle (0.4,0.6)}$${\displaystyle (0.3,0.7)}$${\displaystyle {\frac {V_{\text{Alice}}}{0.4}}+{\frac {V_{\text{George}}}{0.6}}}$
• Напротив, второе разбиение не принадлежит ни одной точке и, действительно, не является Парето-эффективным.
• Есть некоторые точки, которым принадлежат многие различные разбиения. Например, точка . Это точка СРК, и с ней связана положительная масса торта, поэтому любое разбиение этой массы приводит к разбиению, которое принадлежит . Например, передача Лимона и Шоколада Алисе (значение 27), а остального Джорджу (значение 12) принадлежит ; передача только Лимона Алисе (значение 9), а остального Джорджу (значение 30) также принадлежит ему; передача Лимона и половины шоколада Алисе (значение 18), а остального Джорджу (значение 21) также принадлежит ему; и т. д. Все эти разбиения максимизируют сумму ; действительно, эта сумма равна 78 во всех этих разбиениях. Все они являются Парето-эффективными.${\displaystyle (0.5,0.5)}$${\displaystyle (0.5,0.5)}$${\displaystyle (0.5,0.5)}$${\displaystyle {\frac {V_{\text{Alice}}}{0.5}}+{\frac {V_{\text{George}}}{0.5}}}$

СОК был введен как часть теорем Дубинса–Спаньера и использовался в доказательстве теоремы Веллера и более поздних результатов Этаном Эйкиным. ^[2] Термин «множество Радона–Никодима» был придуман Юлиусом Барбанелем. ^[1]

• Отдельные части набора