Справедливое разделение

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

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

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

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

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

Набор может быть разных типов: $С$

$С$ может быть конечным набором неделимых предметов, например: , таким образом, что каждый предмет должен быть передан целиком одному человеку. $C=\{{\text{пианино}},{\text{машина}},{\text{квартира}}\}$
$С$ может быть бесконечным множеством, представляющим делимый ресурс, например: деньги или торт. Математически делимый ресурс часто моделируется как подмножество реального пространства, например, сечение [0,1] может представлять длинный узкий торт, который нужно разрезать на параллельные части. Единичный диск может представлять яблочный пирог.

Кроме того, разделяемый набор может быть:

однородный – например, деньги, где важна только сумма, или
неоднородный – например, торт, который может иметь разные ингредиенты, разную глазурь и т. д.

Наконец, принято делать некоторые предположения о том, являются ли предметы, подлежащие разделению:

товары – например, автомобиль или торт, или
плохие – например, домашние дела.

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

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

Распространены также комбинации и особые случаи:

Гармония аренды (также известная как проблема соседей по квартире) – разделение множества неделимых разнородных благ (например, комнат в квартире) и одновременно однородного делимого зла (арендной платы за квартиру).
Справедливое распределение рек — разделение вод международной реки между странами вдоль ее течения.
Справедливое случайное распределение — разделение лотерей по подразделениям — особенно распространено при распределении неделимых благ.

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

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

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

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

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

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

Пропорциональное деление означает, что каждый игрок получает по крайней мере свою долю в соответствии с его собственной функцией ценности . Например, если три человека делят торт, каждый получает по крайней мере треть по своей собственной оценке, т.е. каждый из n человек получает подмножество, которое он оценивает как по крайней мере 1/ n от общей ценности: $С$
- $V_{i}(X_{i})\geq V_{i}(C)/n$ для всех я.
Суперпропорциональный раздел – это раздел, при котором каждый игрок получает строго больше, чем 1/ n. (Такой раздел существует только в том случае, если у игроков разные оценки.):
- $V_{i}(X_{i})>V_{i}(C)/n$ для всех я .
Раздел без зависти гарантирует, что никто не захочет получить чужую долю больше, чем свою собственную, т.е. каждый человек ценит свою долю по крайней мере так же, как и все остальные доли:
- $V_{i}(X_{i})\geq 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.

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

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

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

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

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

Процедуры

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

Игроки делают следующее:

Согласовать свои критерии справедливого разделения
Выберите действительную процедуру и следуйте ее правилам.

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

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

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

Ни один конечный протокол (даже если он неограничен) не может гарантировать раздел торта без зависти между тремя или более игроками, если каждый игрок должен получить один связанный кусок. ^[3] Однако этот результат применим только к модели, представленной в этой работе, а не к случаям, когда, например, посредник имеет полную информацию о функциях оценки игроков и предлагает раздел на основе этой информации. ^[4]

Расширения

Недавно модель справедливого деления была расширена с отдельных агентов на семьи (заранее определенные группы) агентов. См. справедливое деление среди групп .

История

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

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

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

Историю разрезания торта без зависти см. на странице разрезание торта без зависти .

В популярной культуре

Головоломка о наследовании 17 животных включает в себя справедливое деление 17 верблюдов (или слонов, или лошадей) в пропорциях 1/2, 1/3 и 1/9. Это популярная математическая головоломка , часто утверждающая, что она имеет древнее происхождение, но ее первая задокументированная публикация была в Иране 18-го века. ^[6]
В эпизоде «Один час» третьего сезона сериала «Числа » Чарли рассуждает о проблеме разрезания торта применительно к сумме денег, которую требовал похититель.
Гуго Штейнхаус писал о ряде вариантов справедливого деления в своей книге «Математические снимки» . В своей книге он говорит, что специальная версия справедливого деления для трех человек была разработана Г. Крохмайни в Бердехове в 1944 году, а другая — г-жой Л. Котт. ^[7]
Мартин Гарднер и Ян Стюарт опубликовали книги с разделами об этой проблеме. ^[8]^[9] Мартин Гарднер представил форму задачи о разделении обязанностей. Ян Стюарт популяризировал задачу о справедливом разделении в своих статьях в Scientific American и New Scientist .
В основе комикса «Dinosaur Comics» лежит задача разрезания торта. ^[10]
В израильском фильме « Святая Клара » русский иммигрант спрашивает израильского учителя математики, как можно справедливо разделить круглый торт на 7 человек? Его ответ — сделать 3 прямых разреза посередине, получив 8 равных частей. Поскольку людей всего 7, один кусок следует выбросить, в духе коммунизма.

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

Ссылки

^ Ауманн, Роберт Дж.; Машлер, Майкл (1985). «Теоретико-игровой анализ проблемы банкротства из Талмуда» (PDF) . Журнал экономической теории . 36 (2): 195–213. doi :10.1016/0022-0531(85)90102-4. Архивировано из оригинала (PDF) 2006-02-20.
^ Яари, М. Э.; Бар-Хиллел, М. (1984). «О справедливом разделении». Социальный выбор и благосостояние . 1 : 1. doi :10.1007/BF00297056. S2CID 153443060.
^ Stromquist , Walter (2008). «Беззавистные деления торта не могут быть найдены конечными протоколами». Электронный журнал комбинаторики . 15. doi : 10.37236/735 . Получено 26 октября 2022 г.
^ Ауманн, Йонатан; Домбб, Яир (2010). «Эффективность справедливого деления со связанными частями». Экономика Интернета и сетей . Международный семинар по экономике Интернета и сетей. Springer. стр. 26–37. doi :10.1007/978-3-642-17572-5_3.
^ Сол Гарфанкель. Равнее других: взвешенное голосование. Для всех практических целей. COMAP. 1988
^ Агерон, Пьер (2013). «Le partage des dix-sept chameaux et autres arithmétiques Attributes à l'immam 'Ali: Mouvance et communication de Récits de la Tradition musulmane chiite» (PDF) . Revue d'histoire des mathématiques (на французском языке). 19 (1): 1–41.; см. в частности стр. 13–14.
^ Математические снимки. Х.Штайнхаус. 1950, 1969 ISBN 0-19-503267-5
^ ага! Проницательность. Мартин. Гарднер, 1978. ISBN 978-0-7167-1017-2
^ Как разрезать торт и другие математические головоломки. Ян Стюарт. 2006. ISBN 978-0-19-920590-5
^ «Комиксы о динозаврах!».

Учебники

Янг, Пейтон Х. (1995). Капитал: в теории и на практике . Princeton University Press.
Брамс, Стивен Дж.; Тейлор, Алан Д. (1996). Справедливое разделение: от разрезания торта до разрешения споров . Cambridge University Press. ISBN 0-521-55644-9.
Робертсон, Джек; Уэбб, Уильям (1998). Алгоритмы разрезания торта: будьте честны, если можете . Натик, Массачусетс: AK Peters. ISBN 978-1-56881-076-8. LCCN 97041258. OL 2730675W.
Эрве Мулен (2004). Справедливое разделение и коллективное благосостояние . Кембридж, Массачусетс: MIT Press. ISBN 9780262134231.
Барбанель, Джулиус Б. (2005). Геометрия эффективного справедливого дележа. Введение Алана Д. Тейлора. Кембридж: Cambridge University Press. doi : 10.1017/CBO9780511546679. ISBN 0-521-84248-4. МР 2132232. Краткое изложение доступно по адресу: Barbanel, J. (2010). "Геометрический подход к справедливому делению". The College Mathematics Journal . 41 (4): 268. doi :10.4169/074683410x510263.
Стивен Дж. Брамс (2008). Математика и демократия: разработка лучших процедур голосования и справедливого разделения . Принстон, Нью-Джерси: Princeton University Press. ISBN 9780691133218.

Обзорные статьи

Винсент П. Кроуфорд (1987). «справедливое разделение», The New Palgrave: A Dictionary of Economics , т. 2, стр. 274–75.
Хэл Вариан (1987). «справедливость», Новый Палгрейв: Экономический словарь , т. 2, стр. 275–76.
Брайан Скирмс (1996). Эволюция общественного договора Издательство Кембриджского университета. ISBN 978-0-521-55583-8
Хилл, TP (2000). «Математические приемы для получения справедливой доли». American Scientist . 88 (4): 325–331. Bibcode : 2000AmSci..88..325H. doi : 10.1511/2000.4.325. S2CID 221539202.
Брандт, Феликс; Конитцер, Винсент; Эндрисс, Улле; Ланг, Жером; Прокачча, Ариэль Д. (2016). Справочник по вычислительному социальному выбору. Cambridge University Press. ISBN 9781107060432.(бесплатная онлайн-версия), главы 11–13.
Справедливое разделение Кристиана Кламлера – в Справочнике по групповым решениям и переговорам, стр. 183–202.
Разрезание торта: справедливое разделение делимых благ, автор Клаудия Линднер и Йорг Роте – в журнале «Экономика и вычисления», стр. 395–491.
Справедливое разделение неделимых благ Жерома Ланга и Йорга Роте – в «Экономике и вычислениях», стр. 493–550.

Внешние ссылки

Справедливое деление из проекта «Дискретная математика» в Университете Колорадо в Боулдере.
Справедливое деление: метод маркеров
Справедливое разделение: Метод закрытых торгов