Jump to content

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

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

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

Шоколад Лимон Ваниль Вишня
Ценность Алисы 18 9 1 2
Ценность Джорджа 18 0 4 8
точка РНС (0.5,0.5) (1,0) (0.2,0.8) (0.2,0.8)

«Точка RNS» куска торта описывает относительную ценность партнеров по этому куску. У него две координаты — одна для Алисы и одна для Джорджа. Например:

  • Партнеры согласовывают значения шоколадной части, поэтому координаты ее точки СНО также равны (они нормализованы так, что их сумма равна 1).
  • Лимонная часть имеет ценность только для Алисы, поэтому в ее точке RNS только координата Алисы равна 1, а координата Джорджа равна 0.
  • In both the vanilla and the cherries part, the ratio between Alice's value to George's value is 1:4. Hence, this is also the ratio between the coordinates of their RNS points. Note that both the vanilla and the cherries are mapped to the same RNS point.

The RNS of a cake is just the set of all its RNS points; in the above cake this set contains three points: {(0.5,0.5), (1,0), (0.2,0.8)}. It can be represented by the segment (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)
Lemon Chocolate Vanilla, Cherries

In effect, the cake is decomposed and re-constructed on the segment (1,0)-(0,1).

Definitions

[edit]

There is a set ("the cake"), and a set which is a sigma-algebra of subsets of .

There are partners. Every partner has a personal value measure . This measure determines how much each subset of is worth to that partner.

Define the following measure:

Note that each is an absolutely continuous measure with respect to . Therefore, by the Radon–Nikodym theorem, it has a Radon–Nikodym derivative, which is a function such that for every measurable subset :

The are called value-density functions. They have the following properties, for almost all points of the cake :[1]: 222 

For every point , the RNS point of is defined by:

Note that is always a point in the -dimensional unit simplex in , denoted by (or just when is clear from the context).

The RNS of a cake is the set of all its RNS points:

The cake is decomposed and then re-constructed inside . Each vertex of is associated with one of the n partners. Each fraction of the cake is mapped to a point in according to the valuations: the more valuable a piece is to a partner, the closer it is to that partner's vertex. This is shown in the above example for partners (where is just the segment between (1,0) and (0,1)). Akin[2] describes the meaning of the RNS for partners:

We imagine a table shaped like an equilateral triangle with each consumer seated at a vertex... the desirability to consumer of a fragment of cake at a point is given by the barycentric coordinate measuring its closeness to vertex . Thus, is 1 at the vertex and declines linearly to value 0 at the opposite face.

Efficient RNS partitions

[edit]

The unit simplex can be partitioned among the partners, giving each partner a subset . Each such partition induces a partition of the cake , in which partner receives the bits of whose RNS-points fall within .

Here are two example partitions for the two-partner example, where is the segment between (1,0) and (0,1)

  • Cut in the point (0.4,0.6). Give the segment (1,0)-(0.4,0.6) to Alice and the segment (0.4,0.6)-(0,1) to George. This corresponds to giving the Lemon and Chocolate to Alice (total value 27) and the rest to George (total value 12).
  • Cut in the same point (0.4,0.6), but give the segment (1,0)-(0.4,0.6) to George (total value 18) and the segment (0.4,0.6)-(0,1) to Alice (total value 3).

The first partition looks much more efficient than the second one: in the first partition, each partner is given the pieces that are more valuable to him/her (closer to his/her vertex of the simplex), while in the second partition the opposite is true. In fact, the first partition is Pareto efficient while the second partition is not. For example, in the second partition, Alice can give the cherries to George in exchange for 2/9 of the chocolate; this will improve Alice's utility by 2 and George's utility by 4. This example illustrates a general fact that we define below.

For every point :

  • Say that a partition of belongs to , if:
For all and for all :
  • Say that a partition of belongs to , if it is induced by a partition of that belongs to . I.e:
For all and for all :

It is possible to prove that:[1]: 241–244 

A partition belongs to a positive point ,
if-and-only-if it maximizes the sum:
I.e, iff it is a weighted-utilitarian-maximal division with weight vector .

Since every Pareto-efficient division is weighetd-utilitarian-maximal for some selection of weights,[3] the following theorem is also true:[1]: 246 

A positive partition belongs to some positive point in ,
if-and-only-if it is Pareto-efficient.

So there is a mapping between the set of Pareto-efficient partitions and the points in .

Returning to the above example:

  • The first partition (giving the Lemon and Chocolate to Alice and the rest to George) belongs to the point , as well as to other points such as (some partitions belong to more than one point). Indeed, it is a utilitarian cake-cutting that maximizes the sum , and it is also Pareto-efficient.
  • In contrast, the second partition does not belong to any point, and indeed it is not Pareto-efficient.
  • There are some points to which many different partitions belong. For example, the point . This is a point of the RNS and there is a positive mass of cake associated with it, so any partition of that mass leads to a partition that belongs to . For example, giving the Lemon and Chocolate to Alice (value 27) and the rest to George (value 12) belongs to ; giving only the Lemon to Alice (value 9) and the rest to George (value 30) also belongs to it; giving the Lemon and half the chocolate to Alice (value 18) and the rest to George (value 21) also belongs to it; etc. All these partitions maximize the sum ; indeed, this sum is 78 in all these partitions. They are all Pareto-efficient.

History

[edit]

RNS была введена как часть теорем Дубинса-Спанье и использовалась в доказательстве теоремы Веллера и более поздних результатов Итана Эйкина . [2] The term "Radon–Nikodym set" was coined by Julius Barbanel.[1]

См. также

[ редактировать ]
  1. ^ Перейти обратно: а б с д Барбанель, Юлиус Б. (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-y .
  3. ^ Барбанель, Юлиус Б.; Цвикер, Уильям С. (1997). «Два применения теоремы Дворецкого, Вальда и Вольфовица к делению торта». Теория и решение . 43 (2): 203. doi : 10.1023/a:1004966624893 .
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: a3d9b9578d52443c483154a9e8d0ad9b__1702863000
URL1:https://arc.ask3.ru/arc/aa/a3/9b/a3d9b9578d52443c483154a9e8d0ad9b.html
Заголовок, (Title) документа по адресу, URL1:
Radon–Nikodym set - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)