Пропорциональный делёж

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

Пропорциональный делёж — это вид справедливого дележа, в котором ресурс делится среди n участников с субъективными оценками, дающий по меньшей мере 1/n ресурса по собственной субъективной оценке каждого участника.

Пропорциональность была первым критерием справедливости, изучаемым в литературе, поэтому она иногда называется «простым справедливым дележом». Критерий впервые предложил Штейнгауз в 1948 году[1].

Рассмотрим наследную землю, которая должна быть разделена между 3 наследниками — Алисой и Бобом, считающими, что земля стоит 3 000 000 $, и Джорджем, считающим, что она стоит 4 500 000 $. При пропорциональном дележе Алиса получает участок земли, который она оценивает по меньшей мере в 1 000 000 $, Боб получает участок, который, как он думает, стоит по меньшей мере 1 000 000 $ (даже если Алиса может считать, что он стоит меньше), а Джордж получает участок, который, по его мнению, стоит не менее 1 500 000 $.

Существование

[править | править код]

Пропорциональный делёж не всегда существует. Например, если ресурс содержит несколько индивидуальных объектов, а число людей превышает число объектов, то некоторые люди не получат ничего совсем, так что оценка приобретения для них будет нулевой. Тем не менее, делёж существует с высокой вероятностью для неделимых объектов при некоторых предположениях по оценке объектов участниками[2].

Более того, пропорциональный делёж гарантированно существует при выполнении следующих условий:

Следовательно, пропорциональный делёж обычно изучается в контексте справедливого разрезания торта (См. статью «Пропорциональное деление торта»).

Более гибким критерием справедливости является частичная пропорциональность, при которой участник получает определённую долю f(n) полной оценки, где . Частичные пропорциональные дележи существуют (при некоторых условиях) даже для неделимых объектов.

Суперпропорциональный делёж

[править | править код]

Суперпропорциональный делёж — это делёж, в котором каждый участник получает строго больше 1/n ресурса по его собственной субъективной оценке.

Конечно же, такой делёж не всегда существует — если все участники имеют в точности те же самые функции оценок, лучшее, что мы можем сделать, это дать каждому участнику в точности 1/n. Таким образом, необходимым условием существования суперпропорционального дележа является требование наличия у всех карт одинаковых мер значимости.

Удивительно также то, что это условие также является и достаточным, если оценки аддитивны и неатомарны. То есть, при наличии хотя бы двух участников, функции оценок которых хотя бы слегка отличаются, существует суперпропорциональный делёж, при котором все участники получают более 1/n (См. статью «Суперпропорциональный делёж»).

Связь с другими критериями справедливости

[править | править код]

Связь между пропорциональностью и свободой от зависти

[править код]

Пропорциональность (ПД) и отсутствие зависти (ОЗ) являются двумя независимыми свойствами, но, в некоторых случаях, из одного свойства вытекает другое.

Когда все оценки являются аддитивными функциями множеств[англ.] и весь торт разделён, выполняются следующие связи:

  • Для двух участников ПД и ОЗ эквивалентны
  • Для трёх и более участников из ОЗ вытекает ПД, но не наоборот. Например, возможен случай, когда каждый из трёх участников получает по 1/3 по его собственному субъективному мнению, но по мнению Алисы часть Боба оценивается в 2/3

Когда оценки являются лишь субаддитивными[англ.], из ОЗ всё ещё вытекает ПД, но из ПД больше не следует ОЗ, даже для двух участников — возможен случай, когда доля Алисы в её глазах сто́ит 1/2, но доля Боба сто́ит даже больше. Если же оценки супераддитивны[англ.], из ПД следует ОЗ для двух участников, но из ОЗ уже не следует ПД даже для двух участников — возможен случай, когда доля Алисы в её глазах сто́ит 1/4, но доля Боба сто́ит даже меньше. Аналогично, когда не весь торт разделён, из ОЗ не следует ПД. Импликации подытожены в следующей таблице:

Оценки 2 участника 3+ участника
Аддитивная
Субаддитивная
Супераддитивная -
Общего вида - -

Стабильность относительно добровольного обмена

[править | править код]

Одним из преимуществ пропорционального критерия над критерием отсутствия зависти и подобными критериями заключается в том, что он стабилен относительно добровольного обмена.

В качестве примера предположим, что некоторый участок земли делится среди 3 участников — Алисой, Бобом и Джорджем. При этом делёж одновременно пропорционален и свободен от зависти. Несколько месяцев позже, Алиса и Джордж решают объединить свои участки и переделить их так, чтобы новый делёж был выгоднее для них обоих. С точки зрения Боба деление остаётся пропорциональным, поскольку по его субъективной оценке он всё ещё имеет не менее 1/3 всего участка, и это не зависит от того, что делают Алиса и Джордж с их долями. С другой стороны, новое деление может оказаться несвободным от зависти. Например, возможно, что первоначально и Алиса, и Джордж по субъективной оценке Боба получили по 1/3, но после повторного дележа Джордж (в глазах Боба) получил всё значение, так что Боб начинает завидовать Джорджу.

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

Индивидуальная рациональность

[править | править код]

Дополнительное преимущество пропорциональности заключается в том, что оно совместимо с индивидуальной рациональностью в следующем смысле. Предположим, что n участников владеют общим ресурсом. Во многих практических сценариях (хотя и не во всех) партнёры имеют возможность продать ресурс на рынке и разделить выручку в количестве 1/n на каждого. Следовательно, рациональный партнёр будет согласен участвовать в процедуре дележа только если процедура гарантирует по меньшей мере 1/n его личной оценки общего ресурса.

Кроме того, должна быть по меньшей мере возможность (уж если не гарантия), что партнёры получат более 1/n. Это и доказывает важность существования теорем суперпропорционального делёжа.

Примечания

[править | править код]
  1. Steinhaus, 1948, с. 101–104.
  2. Suksompong, 2016, с. 62–65.

Литература

[править | править код]
  • Hugo Steinhaus. The problem of fair division // Econometrica. — 1948. — Т. 16, вып. 1. — JSTOR 1914289.
  • Warut Suksompong. Asymptotic existence of proportionally fair allocations // Mathematical Social Sciences. — 2016. — Т. 81. — doi:10.1016/j.mathsocsci.2016.03.007. — arXiv:1806.00218.
  • Austin A. K. Sharing a Cake // The Mathematical Gazette. — 1982. — Т. 66, вып. 437. — С. 212. — doi:10.2307/3616548. — JSTOR 3616548. Сводка пропорционального и других процедур дележа