Справедливый делёж

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

Задача справедливого дележа возникает в различных ситуациях, например, таких как раздел наследства. Это активная область исследований в математике, экономике (особенно в теории социального выбора^[англ.]), теории игр, решении спорных вопросов^[англ.] и многих других.

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

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

Вещи, которые можно делить

Формально задача справедливого дележа определяется множеством $X$ и группой из $n$ игроков. Делёж — это разбиение множества $X$ на $n$ непересекающихся подмножеств: $X=X_{1}\sqcup X_{2}\sqcup \cdots \sqcup X_{n}$ , по одному подмножеству на игрока.

Множество $X$ может быть различных видов:

X может быть конечным множеством неделимых объектов, например: X = {пианино, автомобиль, квартира}, так что каждый объект должен быть передан отдельному участнику.
X может быть бесконечным множеством, представленным делимыми ресурсами, например: деньги или торт. Математически, делимый ресурс часто моделируется как подмножество вещественного пространства, например, отрезок [0,1] может представлять длинный узкий торт, который может быть разрезан параллельными сечениями на куски. Единичный круг может представлять собой яблочный пирог.

Кроме того, множество, которое следует разделить, может быть:

однородным — таким, как деньги, где имеет значение только величина или количество;
неоднородным — таким, как торт, который может содержать различные ингредиенты, различную глазировку, кремы, фрукты и т. д.

Наконец, обычно необходимо сделать некоторые предположения о желательности делимых объектов — к какой из групп они относятся:

блага — такие, как автомобили или торт;
неприятные вещи — такие, как домашние обязанности.

Основываясь на этих различиях, изучались несколько общих типов задач справедливого дележа:

справедливое распределение предметов — делёж множества неделимых и неоднородных объектов;
справедливое распределение ресурсов — делёж множества делимых и однородных благ. Специальным случаем является справедливый делёж одного однородного ресурса^[англ.];
справедливый делёж торта — делёж делимого неоднородного блага. Специальным случаем является круглая форма торта, в этом случае задача называется справедливым дележом пирога;
справедливый делёж обязанностей — делёж делимых неоднородных неприятных вещей.

Обычно рассматриваются также комбинации и специальные случаи:

задача о совместном найме квартиры — делёж множества неделимых неоднородных благ (например, комнаты в квартире) и одновременно однородных делимых неприятных вещей (оплаты квартиры);
справедливое использование реки — делёж воды, текущей в реках по границам стран;
справедливое случайное назначение^[англ.] — алгоритм дележа с использованием случайности, дающий в среднем справедливый результат, особенно пригодный для распределения неделимых благ.

Определения справедливости

Большинство того, что обычно называется справедливым дележом, теорией не рассматривается, поскольку используется арбитраж. Эти ситуации часто встречаются с математическими теориями, которые имеют названия задач реальной жизни. Решения в талмуде о долях^[англ.], когда собственность банкротится, отражают некоторые сложные идеи о справедливости^[1] и большинство людей считают эти решения справедливыми. Однако они являются результатом обсуждений раввинов, а не дележом согласно оценкам участников имущественного спора.

Согласно субъективной теории ценности не может быть объективной меры ценности каждого объекта. Тогда объективная справедливость невозможна, поскольку различные лица назначают различные цены для каждого объекта. Эмпирические эксперименты о том, как люди определяют концепцию справедливости^[2] привели к малосостоятельным результатам.

Таким образом, большинство современных исследований по справедливости фокусируются на концепции субъективной справедливости. Предполагается, что каждый из $n$ людей имеет персональную субъективную функцию полезности или функцию значимости $V_{i}$ , которая назначает численное значение каждому подмножеству $X$ . Часто функции предполагаются нормализованными, так что значения для каждого человека равны 0 для пустого множества ( $V_{i}(\emptyset )=0$ для всех i), и 1 для множества всех элементов ( $V_{i}(X)=1$ для всех i), если элементы желательны, и −1, если элементы нежелательны. Примеры:

Если $X$ является множеством неделимых предметов {пианино, автомобиль, квартира}, то Алиса может назначить значение 1/3 для каждого предмета, что означает, что каждый предмет одинаково ценен для неё. Боб может назначить значение 1 множеству {автомобиль, квартира} и значение 0 для всех других множеств, за исключением X. Это означает, что он хочет получить автомобиль и квартиру вместе. Один автомобиль или квартира, а также эти объекты вместе с пианино Боба не интересуют.
Если $X$ является длинным узким тортом, что можно моделировать как интервал [0; 1], то Алиса может назначить каждому подмножеству значение, пропорциональное его длине, что означает, что она хочет получить торта как можно больше, независимо от украшений глазурью и кремами. Боб может назначить значения только для подмножества [0,4; 0,6], например, поскольку эта часть торта может содержать вишенки, а Боб заботится только о получении вишенок.

Основываясь на этих субъективных функциях существуют широко используемые критерии справедливого дележа. Некоторые из них конфликтуют с другими, но часто их можно и комбинировать. Критерии, описанные здесь, относятся только к случаям, когда игрок может иметь то же количество:

Пропорциональный делёж означает, что каждый участник получает не меньше его должной доли согласно его собственной функции ценности. Например, если три человека делят торт, то каждый из трёх получает по меньшей мере треть по его собственной оценке, то есть, каждый из n участников получает подмножество X, которое он оценивает не меньше, чем в 1/n:
- $V_{i}(X_{i})\geqslant 1/n$ для всех i.
Суперпропорциональный делёж — это делёж, при котором каждый игрок получает строго больше 1/n (так что делёж возможен только если игроки имеют различные оценки):
- $V_{i}(X_{i})>1/n$ для всех i.
Делёж без зависти^[3] гарантирует, что никто не хочет, чтобы другой получил больше, чем он, то есть каждое лицо получает долю, ценность которой не меньше ценности кусков для других участников:
- $V_{i}(X_{i})\geqslant V_{i}(X_{j})$ для всех i и j.
Делёж без групповой зависти гарантирует, что нет подмножества агентов, завидующих другому подмножеству такого же размера, это существенно более сильное условие чем отсутствие зависти.
Равенство в долях^[англ.] дележа означает, что каждое лицо чувствует ту же самую удовлетворённость, то есть порция торта, полученная игроком, по его собственной оценке та же самая, что и для других игроков. Это трудная цель, поскольку игрок может и не быть правдивым, если спросить о его оценке:
- $V_{i}(X_{i})=V_{j}(X_{j})$ для всех i и j.
Точный делёж (или согласованный делёж) — это делёж, в котором все игроки согласны со значением каждого куска:
- $V_{i}(X_{i})=V_{j}(X_{i})$ для всех i и j.

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

Дополнительные требования

Вдобавок к справедливости иногда желают, чтобы делёж был оптимальным по Парето, то есть, никакое другое деление не может быть лучше для кого-либо без потерь для другого. Термин «эффективность» приходит из экономической идеи эффективного рынка. Делёж, при котором один игрок получает всё, оптимален по этому определению, так что сам по себе он не гарантирует справедливого дележа. См. также статьи «Эффективное разрезание торта» и «Цена справедливости».

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

Дополнительным требованием является, чтобы эта процедура справедливого дележа была правдивым механизмом^[англ.], то есть она должна быть доминантной стратегией для участников, чтобы показывать их действительные оценки. Это требование обычно очень трудно удовлетворить в комбинации со справедливостью и эффективностью по Парето.

Обобщением задачи является разрешение каждой заинтересованной стороне состоять из нескольких игроков, разделяющих то же множество ресурсов, но имеющих различные предпочтения^[4]^[5].

Процедуры

Алгоритмы, или процедуры^[6] справедливого дележа перечисляют действия игроков в терминах видимых данных и их оценок. Правильная процедура — это та, которая гарантирует справедливый делёж для любого игрока, который действует рационально согласно его собственной оценке. В то время как действие игрока зависит от его оценок, процедура описывает стратегию рационального игрока, которой он следует. Игрок может действовать как если бы кусок имел другую оценку, но должен быть последовательным (предсказуемым). Например, если процедура говорит, что первый игрок режет торт на две равные части, а второй выбирает кусок, то первый игрок не может жаловаться, что второй игрок получил бо́льшую часть.

Что игрок делает:

соглашается на критерий справедливого дележа;
выбирает правильную процедуру и следует её правилам.

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

Процедуры можно разделить на дискретные и непрерывные. Дискретная процедура могла бы, например, вовлекать только одно лицо для разрезания пирога в каждый момент времени. Непрерывные процедуры вовлекают вещи, например, когда один игрок передвигает нож^[англ.], а другой игрок говорит «стоп». Другой вид непрерывной процедуры вовлекает лицо в присвоение значения для каждой части торта.

Для списка процедур справедливого дележа см. Категория:Протоколы справедливого дележа.

История

Согласно Солу Гарфункелю^[англ.], задача разрезания торта была одной из наиболее важных открытых проблем в математике XX века^[7], и наиболее важный вариант задачи был окончательно разрешён процедурой Брамса — Тейлора, разработанной Стивеном Брамсом и Аланом Тейлором в 1995 году.

Источники протокола «Дели и выбирай» неизвестны. Связанные действия, такие как торговля и бартер известны издревле. Переговоры, вовлекающие более двух участников, также являются вполне общим явлением, Потсдамская конференция служит выдающимся примером.

Теория справедливого дележа отсчитывается только с конца второй мировой войны. Её разрабатывала группа польских математиков (Гуго Штейнгауз, Бронислав Кнастер и Стефан Банах), которые обычно встречались в Шотландском кафе во Львове (затем в Польше). Пропорциональный делёж для любого числа участников с названием «последний уменьшающий» разработан в 1944 году. Его Штейнгауз приписывал Банаху и Кнастеру, когда представил задачу публично первый раз на собрании Эконометрического общества в Вашингтоне в сентябре 1947 года. На этом собрании он также предложил задачу поиска наименьшего числа разрезов, необходимых для такого дележа.

Об истории завистливого разрезания см. статью Завистливое разрезание торта.

Приложения

Задачи справедливого дележа возникают в таких ситуациях, как раздел наследства, прекращение партнёрства, бракоразводные процессы^[англ.], при выделении радиочастот^[англ.], управлении движением в аэропорту и эксплуатации спутников дистанционного зондирования Земли^[англ.].