Справедливое деление - Fair division

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

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

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

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

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

Набор ${ displaystyle C}$ могут быть разных типов:

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

Дополнительно разделяемый набор может быть:

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

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

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

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

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

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

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

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

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

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

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

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

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

• А пропорциональное деление означает, что каждый получает как минимум свою долю в соответствии с его собственной функцией ценности. Например, если три человека делят торт, каждый получает как минимум треть по своей собственной оценке, то есть каждый из п люди получают подмножество ${ displaystyle C}$ который он оценивает как минимум как 1 /п от общей стоимости:
  • ${ Displaystyle V_ {я} (X_ {я}) geq V_ {я} (С) / п}$ для всех я.
• А сверхпропорциональное деление это тот, где каждый игрок получает строго больше, чем 1 /п (такое разделение существует, только если у игроков разные оценки):
  • ${ displaystyle V_ {i} (X_ {i})> V_ {i} (C) / n}$ для всех я.
• An без зависти разделение гарантирует, что никто не захочет получить чужую долю больше, чем свою собственную, то есть каждый человек получает долю, которую он ценит не меньше, чем все остальные акции:
  • ${ displaystyle V_ {i} (X_ {i}) geq V_ {i} (X_ {j})}$ для всех i и j.
• А групповой без зависти деление гарантирует, что ни одно подмножество агентов не завидует другому подмножеству того же размера; это гораздо сильнее зависти.
• An справедливый деление означает, что каждый человек испытывает одинаковое счастье, то есть пропорция торта, которую игрок получает по своей собственной оценке, одинакова для каждого игрока. Это сложная задача, поскольку игрокам не нужно быть правдивыми, если их спросить о своей оценке:
  • ${ Displaystyle V_ {i} (X_ {i}) = V_ {j} (X_ {j})}$ для всех i и j.
• An точное деление (также известное как разделение консенсуса), когда все игроки соглашаются относительно стоимости каждой акции:
  • ${ Displaystyle V_ {i} (X_ {i}) = V_ {j} (X_ {i})}$ для всех i и j.

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

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

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

Берлин разделен Потсдамская конференция

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

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

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

Процедуры

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

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

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

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

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

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

История

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

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

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

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

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

• В Numb3rs В эпизоде ​​3 сезона «Один час» Чарли рассказывает о проблеме разрезания торта применительно к сумме денег, которую требовал похититель.
• Хьюго Штайнхаус о ряде вариантов справедливого деления писал в своей книге Математические снимки. В своей книге он говорит, что специальная версия справедливого разделения для трех человек была изобретена Г. Крохмайным в Бердехове в 1944 году, а другая - миссис Л. Котт.^[6]
• Мартин Гарднер и Ян Стюарт обе опубликовали книги с разделами о проблеме.^[7][8] Мартин Гарднер представил задачу о разделении обязанностей по дому. Ян Стюарт популяризировал проблему справедливого разделения своими статьями в Scientific American и Новый ученый.
• А Комиксы про динозавров полоса основана на задаче нарезки торта.^[9]
• В израильском фильме Saint Clara, русский иммигрант спрашивает израильского учителя математики, как круглый торт можно справедливо разделить на 7 человек? Его ответ - сделать 3 прямых разреза через его середину, получив 8 равных частей. Так как здесь всего 7 человек, от одной штуки нужно отказаться, в духе коммунизма.

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

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

использованная литература

Учебники

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

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

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

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

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