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

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

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

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

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

Формально проблема справедливого деления определяется набором (часто называемым «пирогом») и группой игроков. Разделение - это разделение на непересекающиеся подмножества:, по одному подмножеству на игрока.${\ 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], приводят к неубедительным результатам.

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

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

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

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

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

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

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

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

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

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

Процедуры [ править ]

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

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

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

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

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

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

История [ править ]

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

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

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

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

В популярной культуре [ править ]

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

См. Также [ править ]

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

Ссылки [ править ]

Учебники [ править ]

• Янг, Пейтон Х. (1995). Справедливость: в теории и на практике . Издательство Принстонского университета.
• Брамс, Стивен Дж .; Тейлор, Алан Д. (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. Руководство по ремонту  2132232 . Краткое изложение доступно по адресу: Barbanel, J. (2010). «Геометрический подход к справедливому разделению». Журнал математики колледжа . 41 (4): 268. DOI : 10,4169 / 074683410x510263 .
• Стивен Дж. Брамс (2008). Математика и демократия: разработка более эффективных процедур голосования и справедливого разделения . Принстон, Нью-Джерси: Издательство Принстонского университета. ISBN 9780691133218.

Статьи обзора [ править ]

• Винсент П. Кроуфорд (1987). "справедливое разделение," Новый Palgrave: Словарь экономических , v 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.
• Справедливое разделение Кристиана Кламлера - в Справочнике по групповым решениям и переговорам, стр. 183-202.
• Вырезание торта: справедливое разделение делимых товаров Клаудиа Линднер и Йорг Роте - в области экономики и вычислений, стр. 395-491.
• Справедливое разделение неделимых товаров Жерома Ланга и Йорга Роте - в экономике и вычислениях, стр. 493-550.

Внешние ссылки [ править ]

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