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

Radon–Nikodym set

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

Пример

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

ШоколадЛимонВанильВишня
Ценность Алисы18912
Значение Георгия18048
Точка 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).

Определения

Есть набор («торт»), и набор который является сигма-алгебра подмножеств .

Есть партнеры. Каждый партнер имеет личную ценность мера . Этот показатель определяет, насколько каждое подмножество стоит для этого партнера.

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

Обратите внимание, что каждый является абсолютно непрерывная мера относительно . Поэтому по Теорема Радона – Никодима, у нее есть производная Радона – Никодима, которая является функцией такое, что для каждого измеримого подмножества :

В называются функции плотности стоимости. Они обладают следующими свойствами почти для всех точек торта :[1]:222

За каждую точку , точка RNS определяется:

Обратите внимание, что всегда точка в -размерный блок симплекс в , обозначаемый (или просто когда понятно из контекста).

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

Торт раскладывается, а затем заново строится внутри. . Каждая вершина связан с одним из п партнеры. Каждая фракция торта сопоставлена ​​с точкой в в соответствии с оценками: чем ценнее кусок для партнера, тем ближе он к его вершине. Это показано в приведенном выше примере для партнеры (где это просто отрезок между (1,0) и (0,1)). Похожий[2] описывает значение RNS для партнеры:

Мы представляем себе стол в форме равностороннего треугольника, в котором каждый потребитель сидит в вершине ... желательность для потребителя фрагмента торта в точке задается барицентрической координатой измерение его близости к вершине . Таким образом, равен 1 в вершине и линейно уменьшается до значения 0 на противоположной стороне.

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

Устройство симплекс можно разделить между партнерами, давая каждому партнеру подмножество . Каждое такое разбиение порождает разбиение торта , в котором партнер получает кусочки чьи RNS-точки попадают в .

Вот два примера разделов для пример двух партнеров, куда это отрезок между (1,0) и (0,1)

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

За каждую точку :

  • Скажите, что раздел принадлежит , если:
Для всех и для всех :
  • Скажите, что раздел принадлежит , если он индуцирован разбиением это принадлежит . То есть:
Для всех и для всех :

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

Раздел принадлежит положительной точке ,
если и только если он максимизирует сумму:
То есть, если это взвешенно-утилитарный-максимальный деление с вектором веса .

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

Положительный раздел принадлежит некоторой положительной точке в ,
если и только если это Парето-эффективный.

Таким образом, существует соответствие между набором парето-эффективных разделов и точками в .

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

  • Первый раздел (отдача лимона и шоколада Алисе, а остальные Джорджа) принадлежит точке , а также к другим точкам, таким как (некоторые разделы принадлежат более чем одной точке). Действительно, это утилитарная резка торта что максимизирует сумму , и он также эффективен по Парето.
  • Напротив, второе разделение не принадлежит какой-либо точке и действительно не эффективно по Парето.
  • Есть некоторые точки, к которым принадлежит много разных разделов. Например, точка . Это точка RNS, и с ней связана положительная масса торта, поэтому любое разделение этой массы приводит к разделу, принадлежащему . Например, отдать Лимон и Шоколад Алисе (значение 27), а остальное Джорджу (значение 12) принадлежит ; отдать только Лимон Алисе (значение 9), а остальное Джорджу (значение 30) также принадлежит ему; отдать Лимон и половину шоколада Алисе (значение 18), а остальное Джорджу (значение 21) также принадлежит ему; и т.д. Все эти перегородки увеличивают сумму ; действительно, во всех этих разделах эта сумма равна 78. Все они эффективны по Парето.

История

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

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

Рекомендации

  1. ^ а б c d Barbanel, Julius B .; с введением Алана Д. Тейлора (2005). Геометрия эффективного выставочного деления. Кембридж: Издательство Кембриджского университета. Дои:10.1017 / CBO9780511546679. ISBN 0-521-84248-4. МИСТЕР 2132232. Краткое резюме доступно по адресу: Барбанель, Дж. (2010). «Геометрический подход к справедливому разделению». Математический журнал колледжа. 41 (4): 268. Дои:10.4169 / 074683410x510263.
  2. ^ а б Акин, Итан (1995). «Вильфредо Парето режет торт». Журнал математической экономики. 24: 23. Дои:10.1016 / 0304-4068 (94) 00674-у.
  3. ^ Barbanel, Julius B .; Цвикер, Уильям С. (1997). «Два приложения теоремы Дворецкого, Вальда и Вольфовица к делению торта». Теория и решение. 43 (2): 203. Дои:10.1023 / а: 1004966624893.