Честное разделение

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

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

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

Содержание

• 1 Вещи, которые можно разделить
• 2 Определения справедливости
• 3 Дополнительные требования
• 4 Процедуры
• 5 История
• 6 В массовой культуре
• 7 См. Также
• 8 Ссылки
• 9 Учебники
• 10 Обзорные статьи
• 11 Внешние ссылки

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

Формально проблема справедливого разделения определяется набором $C\; \{\backslash \; displaystyle\; C\}$(часто называемый «торт») и группа из $n\; \{\backslash \; displaystyle\; n\}$игроков. Деление - это разделение $C\; \{\backslash \; displaystyle\; C\}$на $n\; \{\backslash \; displaystyle\; n\}$непересекающихся подмножеств: $C\; =\; X\; 1\; \bigsqcup \; X\; 2\; \bigsqcup \; \cdots \; \bigsqcup \; Икс\; n\; \{\backslash \; displaystyle\; C\; =\; X\_\; \{1\}\; \backslash \; sqcup\; X\_\; \{2\}\; \backslash \; sqcup\; \backslash \; cdots\; \backslash \; sqcup\; X\_\; \{n\}\}$, одно подмножество на игрока.

Набор $C\; \{\backslash \; displaystyle\; C\}$может быть различных типов:

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

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

• однородным - например, деньги, где имеет значение только сумма, или
• разнородные - например, торт, который может иметь разные ингредиенты, разные глазури и т. д.

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

• товарами - такими как автомобиль или торт, или
• плохие, такие как работа по дому.

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

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

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

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

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

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

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

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

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

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

• A пропорциональное деление означает, что каждый человек получает, по крайней мере, свою долю в соответствии с его собственной функцией ценности. Например, если три человека делят торт, каждый получает как минимум треть по своей оценке, т.е. каждый из n человек получает подмножество $C\; \{\backslash \; displaystyle\; C\}$, которое он оценивает как не менее 1 / n от общего значения:
  • $V\; i\; (X\; i)\; \ge \; V\; i\; (C)\; /\; n\; \{\backslash \; displaystyle\; V\_\; \{i\}\; (X\_\; \{i\})\; \backslash \; geq\; V\_\; \{i\}\; (C)\; /\; n\; \}$для всех i.
• A суперпропорциональное деление - это такое деление, в котором каждый игрок получает строго больше 1 / n (такое деление существует только в том случае, если игроки имеют разные оценки):
  • $V\; i\; (X\; i)>V\; i\; (C)\; /\; n\; \{\backslash \; displaystyle\; V\_\; \{i\}\; (X\_\; \{i\})>V\_\; \{i\}\; (C)\; /\; n\}$для всех i. 234>Разделение без зависти гарантирует, что никто не захочет получить чужую долю больше, чем свою собственную, т.е. каждый человек получает долю, которую он ценит не меньше, чем все остальные акции:
    • $V\; я\; (Икс\; я)\; \ge \; В\; я\; (Икс\; J)\; \{\backslash \; Displaystyle\; V\_\; \{я\}\; (X\_\; \{я\})\; \backslash \; GEQ\; V\_\; \{я\}\; (\; X\_\; \{j\})\}$для всех i и j.
  • A разделение без зависти группы гарантирует, что ни одно подмножество агентов не завидует другому подмножеству того же размера; это намного сильнее, чем свобода от зависти.
  • Справедливое разделение означает, что каждый человек испытывает одинаковое счастье, то есть пропорция торта, которую игрок получает по своей собственной оценке, одинакова для каждый игрок. Это трудная цель, поскольку игрокам не нужно быть правдивыми, если их спросить об их оценке:
    • $V\; i\; (X\; i)\; =\; V\; j\; (X\; j)\; \{\backslash \; displaystyle\; V\_\; \{i\}\; (X\_\; \{i\})\; =\; V\_\; \{j\}\; (X\_\; \{j\})\}$для всех i и j.
  • точное деление (также известное как согласованное деление) - это такое деление, при котором все игроки согласовывают стоимость каждой доли:
    • $V\; i\; (X\; i)\; =\; V\; j\; (X\; i)\; \{\backslash \; displaystyle\; V\_\; \{i\}\; (X\_\; \{i\})\; =\; V\_\; \{j\}\; (X\_\; \{i\})\}$для всех i и j.

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

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

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

  Берлин, разделенный на Потсдамскую конференцию

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

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

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

  Процедуры

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

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

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

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

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

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

  История

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

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

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

  Чтобы узнать об истории разрезания торта без зависти, см. разделение торта без зависти.

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

  • В Numb3rs эпизод 3 сезона «One Hour» «Чарли говорит о проблеме разрезания торта применительно к сумме денег, которую требовал похититель.
  • Хьюго Стейнхаус писал о нескольких вариантах справедливого деления в своей книге« Математические снимки ». В своей книге он говорит, что особая версия справедливого деления из трех человек была изобретена Г. Крохмайни в Бердехове в 1944 году, а другая - миссис Л. Котт.
  • Мартин Гарднер и Ян Стюарт имеют и то, и другое. изданы книги с разделами о проблеме. Мартин Гарднер представил задачу о разделении обязанностей по дому. Ян Стюарт популяризировал проблему справедливого разделения в своих статьях в Scientific American и New Scientist.
  • A Dinosaur Comics, в основе которой лежит задача разрезания торта.
  • В израильском фильме Святая Клара русский иммигрант спрашивает израильского учителя математики, как круглый торт можно справедливо разделить между 7 людьми? Его ответ - сделать 3 прямых разреза через его середину, получив 8 равных частей. Так как здесь всего 7 человек, от одного предмета следует отказаться в духе коммунизма.

  См. Также

  • Акционерный капитал (экономика)
  • Международная торговля
  • Правосудие (экономика)
  • Задача о ранце
  • Список нерешенных проблем в честном разделении
  • Торговая игра Нэша
  • Теорема о пицце
  • Цена справедливости
  • Злоба (теория игр)
  • Стратегическое справедливое разделение
  • Трагедия антикоммонов
  • Трагедия of the Commons

  Ссылки

  Учебники

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

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

  • Винсент П. Кроуфорд (1987). "справедливое разделение", Нью-Палгрейв: Экономический словарь, т. 2, стр. 274–75.
  • Хэл Вариан (1987). "справедливость", Нью-Палгрейв: Экономический словарь, т. 2, стр. 275–76.
  • Брайан Скирмс (1996). Эволюция общественного договора Cambridge University Press. ISBN 978-0-521-55583-8
  • Хилл, Т.П. (2000). «Математические устройства для получения справедливой доли». Американский ученый. 88 : 325–331. doi : 10.1511 / 2000.4.325.
  • Брандт, Феликс; Конитцер, Винсент; Эндрисс, Улле; Ланг, Жером; Прокачча, Ариэль Д. (2016). Справочник по вычислительному социальному выбору. Издательство Кембриджского университета. ISBN 9781107060432.(бесплатная онлайн-версия ), главы 11-13.
  • Справедливое разделение Кристиана Кламлера - в Handbook of Group Decision and Negotiation pp 183-202.
  • Разделка торта: справедливое разделение делимых товаров Клаудиа Линднер и Йорг Роте - in Economics and Computing, стр. 395-491.
  • Справедливое разделение неделимых товаров Жеромом Лангом и Йоргом Роте - in Economics and Computing, стр. 493-550.

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

  • Fair Division из проекта дискретной математики в Университете Колорадо в Боулдере.
  • The Fair Division Calculator (Java-приложение) на Колледж Харви Мадда
  • Справедливое деление: метод единственного делителя
  • Справедливое деление: метод маркеров
  • Справедливое деление: метод запечатанных предложений