Ярмарочный отдел

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

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

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

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

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

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

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

Кроме того, набор, подлежащий разделению, может быть:

• однородные – например, деньги, где имеет значение только количество, или
• неоднородный – например, торт, в котором могут быть разные ингредиенты, разная глазурь и т. д.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Процедуры

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

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

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

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

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

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

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

Расширения

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

История

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

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

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

Об истории разрезания тортов без зависти см. разрезание торта без зависти .

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

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

См. также

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

Учебники

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

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

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

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

• Ярмарочный отдел Проекта дискретной математики Университета Колорадо в Боулдере.
• Ярмарка: метод маркеров
• Справедливое разделение: метод закрытых заявок