Как поделить торт и не поссориться: математические протоколы справедливого деления

[mathnotforyou]

В контексте экономики и теории игр отсутствие зависти является критерием справедливого раздела, при котором каждый человек считает, что при разделе какого-либо ресурса его доля по крайней мере так же хороша, как доля любого другого человека - таким образом, он не испытывает зависти. Для n = 2 человек протокол состоит из так называемой процедуры "разделяй и выбирай":

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

В случаях, когда количество людей, разделяющих пирог, превышает два, n > 2, сложность протокола значительно возрастает. Эта процедура имеет множество применений, в том числе (совершенно очевидно) в распределении ресурсов, а также в разрешении конфликтов и искусственном интеллекте, среди других областей. К настоящему времени были изучены два типа процесса нарезки торта без зависти, для:

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

В этой статье вы познакомитесь с примерами различных случаев (n = 2, 3, ...) того, как справедливо разделить торт на соединенные и обычные куски, с дополнительным свойством отсутствия зависти или без него. Приятного чтения!

История

"Интересные математические задачи возникают, если мы хотим определить минимальное количество "надрезов", необходимых для справедливого деления." - Хьюго Штайнхаус

Самое раннее упоминание о протоколе разрезания торта без зависти взято из Книги Бытия, где персонаж Авраама делит землю Ханаанскую, а персонаж Лот выбирает, какую из двух земель он хочет. В наше время проблема была впервые изучена в 1940-х годах польскими математиками Стефаном Банахом, Брониславом Кнастером и, в частности, их научным руководителем Хьюго Штайнхаусом. Первым критерием справедливости, изученным Штайнхаусом, было пропорциональное деление, которое просто предполагает разделение ресурса между агентами с субъективной оценкой каждой доли ресурса. Штайнхаус также был первым, кто обобщил определение задачи для трех или более человек, предложив использовать критерий пропорционального деления. Впервые он представил проблемы разрезания торта в 1947 году на собрании Эконометрического общества в Вашингтоне, Округ Колумбия.



Более строгий критерий отсутствия зависти был введен в 1958 году Джорджем Гамовым и Марвином Стерном. Их критерий гласит, что каждый агент считает, что его доля по крайней мере так же велика, как и любая другая доля, подразумевая, что ни один агент не захочет обменять свою долю с каким-либо другим агентом. Дункан Фоули в 1967 году ввел концепцию отсутствия зависти в экономику, где позже она стала так называемым "доминирующим критерием справедливости", используемым среди прочего в теоремах существования главного экономиста Google Хэла Вариана об эффективном по Парето подразделении без зависти (Varian, 1974). В 1960-х годах Джон Селфридж и Джон Хортон Конвей предложили первую процедуру разрезания торта без зависти для трех партнеров и общих кусков.

Математика разрезания торта

Торт - это метафора разделяемого разнородного ресурса. Формально мы можем определить "торт", который нужно разделить следующим образом, со следующими свойствами:

Торт представлен интервалом [0,1], где кусок торта является объединением подинтервалов [0,1]. Каждый агент в N = {1, ..., n} имеет свою собственную оценку подмножеств [0,1]. Их оценка:

• неотрицательная: Vi(X) ≥ 0
• аддитивная: для всех непересекающихся X, X' ⊆ [0,1], Vi(X ∪ X') = Vi(X) + Vi(X')
• делимая: для любого X ⊆ [0,1] и 0 ≤ λ ≤ 1, существует такой элемент X' ⊂ X с Vi(X') = λVi(X) , где Xi является выделением агенту i.

Отсутствие зависти в данной модели может быть определено просто как: Vi(Xi) ≥ Vi(Xj) ∀ i и j ∈ N.

В целом, мы различаем два типа нарезки торта:

1. Пропорциональное деление, при котором ресурс делится между n людьми с субъективными оценками, при этом каждый человек получает не менее 1/n ресурса по своей субъективной оценке.
2. Разделение без зависти, пропорциональное разделение с дополнительным свойством, заключающимся в том, что каждый человек считает, что его доля, по крайней мере, не хуже доли любого другого агента.

Концепция "справедливости" может быть дополнительно формализована как удовлетворяющая следующим условиям (Pacuit, 2007):

• Пропорциональность: Каждый игрок получает по крайней мере 1/n ресурса в соответствии со своей собственной оценкой его полезности
• Отсутствие зависти: Ни один игрок не готов отказаться от своего распределения в обмен на распределение других игроков
• Справедливость: Каждый игрок оценивает свое распределение так же, как и другие распределения, в соответствии со своей собственной функцией полезности
• Эффективность: Не существует другого разделения, которое лучше максимизировало бы коллективную полезность каждого или кого-либо еще.

Процедуры перемещения ножа

Несколько методов разделения называются "процедурами перемещения ножа", описанными Остином (1982) следующим образом:

Процедура разрезания торта с помощью движущегося ножа Для двоих, Алисы и Боба:

1. Один игрок проводит ножом по торту, традиционно слева направо
2. Торт разрезается, когда любой из участников говорит "стоп"
3. Если каждый игрок объявляет "стоп", когда он или она видит, что нож находится на грани 50 на 50, то первый игрок, который объявит "стоп", произведет дележ без зависти, если вызывающий получит левую часть, а другой игрок - правую

Пропорциональное деление

Для пропорционального распределения (proportionality) ресурс делится между n людьми с субъективными оценками, при этом каждый человек получает не менее 1/n ресурса по своей субъективной оценке. Было показано, что для n человек с аддитивной оценкой всегда существует пропорциональное распределение, и существует несколько известных протоколов для достижения такого распределения, в том числе:

Процедура Банаха-Кнастера "Последний уменьшающий" (Steinhaus, 1948)

Вдохновленный протоколом разделения торта между двумя партнерами, Хьюго Штайнхаус в 1947 году поставил перед двумя своими докторантами, Стефаном Банахом и Брониславом Кнастером, задачу найти процедуру, которая могла бы работать для любого количества людей. Их решение было опубликовано в статье "Проблема справедливого разделения" в журнале Econometrica 16 (1) в 1948 году. По словам авторов, протокол работает следующим образом (Steinhaus, 1948, стр. 102):

"Партнеры, находящиеся в ранжировании A, B, C, .. N, A отрезает от торта произвольную часть. Теперь B имеет право, но не обязан, уменьшить отрезанный кусок. Что бы он ни делал, C имеет право (без обязательств) еще уменьшить уже уменьшенный (или не уменьшенный) кусочек, и так далее до N. Правило обязывает "последнего уменьшающего" взять тот кусочек, к которому он прикасался последним. После того, как этот партнер устранен, оставшиеся n−1 человек начинают ту же игру с остатками торта. После того, как количество участников сократилось до двух, они применяют классическое правило сокращения оставшегося вдвое."

Вот еще одно, более аккуратное объяснение для трех человек - Алисы, Боба, Кэрол:

1. Алиса начинает с того, что отрезает от торта часть произвольного размера в соответствии со своей индивидуальной функцией полезности
2. Боб далее имеет право, но не обязан, отрезать часть от ломтика Алисы. Кэрол затем также имеет право, но не обязана, отрезать еще одну часть от ломтика Алисы
3. Каждый участник должен взять тот кусок, от которого отрезал последним, и таким образом выйти из игры
4. Процедура повторяется с оставшимся тортом для тех, кто еще не получил ни кусочка

Процедура справедлива, но не лишена зависти, потому что, хотя все игроки могут обеспечить себе по крайней мере 1/n кусочков, не убавляя ни кусочка, все, кроме двух последних игроков, могут позавидовать тем, кто получит кусочки позже - т.е., хотя игроки в игре довольны своим кусочком, они не могут гарантировать, что не предпочли бы кусочек, позже полученный кем-то другим (Brams & Taylor, 1996).

Метод "Движущегося ножа" Дюбинса-Спаньера

Версией метода "Последнего уменьшения" в непрерывном режиме является метод "движущегося ножа" Дубинса-Спаньера, предложенный Лестером Э. Дубинсом и Эдвином Х. Спаньером (1961). Это первая процедура с использованием движущегося ножа, описанная в литературе (хотя, как отмечают Brams & Taylor, более ранняя "процедура заливки" была опубликована в Davis, 1955).

Метод движущегося ножа Дюбинса-Спаньера:

1. Судья держит нож на левой стороне торта, а затем непрерывно перемещает нож к правой стороне
2. В любой момент любой из трех игроков может крикнуть "режь" и получить кусочек слева от ножа, начиная игру
3. Процедура повторяется с оставшейся частью торта. Если два оставшихся игрока одновременно кричат "режь!", отрезанный кусок отдается одному из игроков случайным образом

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

Процедура "Одинокого разделителя" Штайнхауса-Куна

Так называемая "процедура одинокого разделителя" - это процедура справедливого раздела, которая, подобно последнему уменьшителю и методу перемещения ножа, описанному выше, также приводит к пропорциональному разделению ресурса между произвольным количеством людей. Она была предложена теоретиком игр Гарольдом Куном в 1967 году и работает следующим образом (Brams & Taylor, 1996), в случае n = 3 для простоты:

Процедура Штайнхауса-Куна "Одинокий разделитель" для трех человек - Алисы, Боба и Кэрол:

1. Пусть Алиса разделит торт на три части равной ценности, исходя из ее функции полезности
2. Теперь пусть Боб и Кэрол укажут, какие кусочки для них приемлемы (по крайней мере, 1/3 стоимости на основе их собственных функций полезности) Это приводит к двум взаимоисключающим случаям:
3. Либо Боб, либо Кэрол сочтут приемлемыми два или более кусочка. Если Боб сочтет приемлемым более одного кусочка, то выбор в порядке: Кэрол, Боб и Алиса приведет к пропорциональному распределению
4. Или и Боб, и Кэрол указывают, что приемлемо не более одного кусочка. Затем мы отдаем Алисе кусочек, который Боб и Кэрол считают неприемлемым, затем выполняем процедуру "раздели и выбери" между Бобом и Кэрол. Это также приведет к пропорциональному распределению Поскольку ни Кэрол, ни Боб не могут подумать, что все три кусочка, нарезанные Алисой, неприемлемы (размером меньше 1/3), вариант два должен иметь преимущественную силу, если вариант один этого не делает, поскольку это единственно две возможные ситуации.

Процедура "одинокого разделителя" также не лишена зависти, потому что в первом случае, хотя Алиса и Боб никому не будут завидовать, Кэрол позавидует Бобу, если он возьмет больший из двух кусков, которые она сочла приемлемыми. Во втором случае, если, по мнению Боба, раздел между Бобом и Кэрол не будет точно 50/50, то он будет завидовать кому-то из двух других (Brams & Taylor, 1996).

Кун опубликовал результат в главе, озаглавленной "Об играх справедливого разделения", в книге 1967 года "Очерки математической экономики в честь Оскара Моргенштерна" под редакцией Мартина Шубика издательства Принстонского университета. В книге Кун представляет случай произвольного числа игроков и доказывает справедливое пропорциональное деление, используя теорему Фробениуса-Кенига.

Разделение без зависти

Дополнительный критерий отсутствия зависти требует, чтобы в дополнение к пропорциональному разделению (справедливости) распределение ресурса обладало свойством отсутствия зависти, а именно:

Ни один игрок не готов отказаться от своего распределения в обмен на распределение других игроков

Дискретная процедура Селфриджа-Конвея

Первая процедура нарезки торта без зависти для трех игроков была открыта Джоном Селфриджем в 1960 году, без публикации доказательства. Позже она была заново открыта Джоном Хортоном Конвеем независимо, хотя он также решил не публиковать ее (Brams & Taylor, 1996). Для игроков Алисы, Боба и Кэрол процедура может быть описана следующим образом:

Процедура разрезания торта без зависти от Селфриджа-Конвея для игроков Алисы, Боба и Кэрол:

1. Алиса делит торт на три части A, B, C, которые, по ее мнению, одинакового размера.
2. Боб считает, что кусок A самый большой
3. Теперь Боб отрезает кусочек от куска А, чтобы он был того же размера, что и второй по величине кусок. Теперь кусочек А делится на: 1. Обрезанный кусочек А₁ и обрезки А₂
4. Затем Кэрол выбирает кусочек из A₁ и двух других кусочков B, C
5. Затем Боб выбирает кусочек с ограничением, что если Кэрол не выбрала A₁, он должен сделать это
6. Алиса, наконец, выбирает последний кусочек, оставляя только обрезки A₂, которые нужно разделить между тремя Обрезанный кусочек A₁ выбирал либо Кэрол, либо Боб. Назовите игрока, который выбрал его, игроком A, а другого игрока B. Чтобы разделить между ними обрезки A₂:
7. Игрок B сначала разрезает обрезки A₂ на три равные части A₂₁, A₂₂ и A₂₃
8. Затем игрок А выбирает кусочек A₂, назовем его A₂₁
9. Затем Алиса выбирает кусочек A₂, назовем его A₂₂
10. Игрок B, наконец, выбирает последний оставшийся кусочек A₂, называет его A₂₃Результат процедуры:

Игрок А получил A₁ + A₂₁ Игрок B получил B + A₂₃ Алиса получила кусочек C + A₂₂ Процедура Селфриджа-Конвея гарантирует отсутствие зависти, потому что, если Кэрол выбирает первой, она делает это, зная, из чего ей выбирать, и поэтому не будет завидовать никому, кто выберет любой из двух других кусочков. Поскольку Боб создает двустороннюю завязку для самого большого куска, обрезая кусочек А, и по крайней мере один из этих двух остается доступным после выбора Кэрол, он также никому не будет завидовать. Наконец, поскольку, если Кэрол не выбрала A₁, это должен сделать Боб, обрезанный кусочек не может быть тем, что осталось. Таким образом, Алиса выбирает один из двух необрезанных кусочков, которые она нарезала сама, и поэтому никому не будет завидовать.

Отсюда ключевое наблюдение: Алиса не будет завидовать игроку, получившему отрезанный кусочек. Алиса разделила кусочки на три равные части и получила кусочек без обрезки, в то время как обрезанный кусочек, даже с добавлением обрезков, даст Кэрол только кусочек, который, по мнению Алисы, будет точно такого же размера, как тот, который она получила (Brams & Taylor, 1996).

Процедура "Движущихся ножей" Стромквиста

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

Процедура разрезания торта без зависти с помощью "Движущихся ножей" Стромквиста:

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

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



Эпилог

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

Всё это и много другое - ТГ "Математика не для всех".