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

Radon–Nikodym set

В теории ярмарка разрезания торта, то Набор Радон – Никодим (РНС) - геометрический объект, представляющий торт, в зависимости от того, как разные люди оценивают разные части торта.

Пример

Допустим, у нас есть торт из четырех частей. Есть два человека, Алиса и Джордж, с разными вкусами: каждый по-разному оценивает разные части торта. В таблице ниже описаны детали и их значения; последняя строка, «RNS Point», объясняется позже.

	Шоколад	Лимон	Ваниль	Вишня
Ценность Алисы	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)	(.9,.1)	(.8,.2)	(.7,.3)	(.6,.4)	(.5,.5)	(.4,.6)	(.3,.7)	(.2,.8)	(.1,.9)	(.0,1.0)
Лимон	-	-	-	-	Шоколад	-	-	Ваниль, Вишня	-	-

По сути, торт раскладывается и строится заново на отрезке (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 = сумма _ {я = 1} ^ {п} V_ {я}}

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

{ Displaystyle V_ {я} (Х) = int _ {X} v_ {я} , dV}

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

${ Displaystyle сумма _ {я = 1} ^ {п} v_ {я} (х) = 1}$
${ displaystyle forall i: 0 leq v_ {i} (x) leq 1}$

За каждую точку ${ displaystyle x in C}$ , точка RNS ${ displaystyle x}$ определяется:

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

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

В RNS торта - это совокупность всех его точек РНС:

{ Displaystyle RNS (C) = {v (x) mid x in C }}

Торт раскладывается, а затем заново строится внутри. ${ displaystyle Delta}$ . Каждая вершина ${ displaystyle Delta}$ связан с одним из п партнеры. Каждая фракция торта сопоставлена с точкой в ${ 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 на противоположной стороне.

Эффективные перегородки RNS

Устройство симплекс ${ 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 шоколада; это улучшит полезность Алисы на 2 и полезности Джорджа на 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 { гидроразрыва {v_ {i}} {v_ {j}}} geq { frac {w_ {i}} {w_ {j}}}}

Скажите, что раздел ${ Displaystyle C = X_ {1} чашка cdots чашка X_ {n}}$ принадлежит ${ displaystyle w}$ , если он индуцирован разбиением ${ displaystyle Delta}$ это принадлежит ${ displaystyle w}$ . То есть:

Для всех

{ displaystyle i, j}

и для всех

{ Displaystyle х в X_ {я}}

:

{ displaystyle { frac {v_ {i} (x)} {v_ {j} (x)}} geq { frac {w_ {i}} {w_ {j}}}}

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

Раздел

{ Displaystyle C = X_ {1} чашка cdots чашка 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} чашка cdots чашка 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}}}$ , и он также эффективен по Парето.
Напротив, второе разделение не принадлежит какой-либо точке и действительно не эффективно по Парето.
Есть некоторые точки, к которым принадлежит много разных разделов. Например, точка ${ Displaystyle (.5, .5)}$ . Это точка RNS, и с ней связана положительная масса торта, поэтому любое разделение этой массы приводит к разделу, принадлежащему ${ displaystyle (0,5,0,5)}$ . Например, отдать Лимон и Шоколад Алисе (значение 27), а остальное Джорджу (значение 12) принадлежит ${ displaystyle (0,5,0,5)}$ ; отдать только Лимон Алисе (значение 9), а остальное Джорджу (значение 30) также принадлежит ему; отдать Лимон и половину шоколада Алисе (значение 18), а остальное Джорджу (значение 21) также принадлежит ему; и т.д. Все эти перегородки увеличивают сумму ${ displaystyle { frac {V _ { text {Alice}}} {0.5}} + { frac {V _ { text {George}}} {0.5}}}$ ; действительно, во всех этих разделах эта сумма равна 78. Все они эффективны по Парето.

История

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

Смотрите также

Набор отдельных предметов

Navigation