В контексте экономики и теории игр отсутствие зависти является критерием справедливого раздела, при котором каждый человек считает, что при разделе какого-либо ресурса его доля по крайней мере так же хороша, как доля любого другого человека — таким образом, он не испытывает зависти. Для n = 2 человек протокол состоит из так называемой процедуры "разделяй и выбирай":
Процедура разрезания торта без зависти гласит, что если два человека должны разделить торт таким образом, чтобы каждый считал, что его доля ничуть не хуже, чем у любого другого человека, один человек ("режущий") разрезает торт на две части; другой человек ("выбирающий") выбирает одну из частей; режущий получает оставшийся кусок.
В случаях, когда количество людей, разделяющих пирог, превышает два, n > 2, сложность протокола значительно возрастает. Эта процедура имеет множество применений, в том числе (совершенно очевидно) в распределении ресурсов, а также в разрешении конфликтов и искусственном интеллекте, среди других областей. К настоящему времени были изучены два типа процесса нарезки торта без зависти, для:
Торты из соединенных кусочков, где каждый участник получает один субинтервал одномерного интервала; и
Торты с обычными кусочками, где каждый человек получает объединение непересекающихся подинтервалов одномерного интервала
В этой статье вы познакомитесь с примерами различных случаев (n = 2, 3, ...) того, как справедливо разделить торт на соединенные и обычные куски, с дополнительным свойством отсутствия зависти или без него. Приятного чтения!
История
"Интересные математические задачи возникают, если мы хотим определить минимальное количество "надрезов", необходимых для справедливого деления." — Хьюго Штайнхаус
Самое раннее упоминание о протоколе разрезания торта без зависти взято из Книги Бытия, где персонаж Авраама делит землю Ханаанскую, а персонаж Лот выбирает, какую из двух земель он хочет. В наше время проблема была впервые изучена в 1940-х годах польскими математиками Стефаном Банахом, Брониславом Кнастером и, в частности, их научным руководителем Хьюго Штайнхаусом. Первым критерием справедливости, изученным Штайнхаусом, было пропорциональное деление, которое просто предполагает разделение ресурса между агентами с субъективной оценкой каждой доли ресурса. Штайнхаус также был первым, кто обобщил определение задачи для трех или более человек, предложив использовать критерий пропорционального деления. Впервые он представил проблемы разрезания торта в 1947 году на собрании Эконометрического общества в Вашингтоне, Округ Колумбия.
![Хьюго Штайнхаус (1887–1972) Хьюго Штайнхаус (1887–1972)](https://habrastorage.org/getpro/habr/upload_files/3b6/d27/18c/3b6d2718c8dc99f566ce95daab9d5d62.png)
Более строгий критерий отсутствия зависти был введен в 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.
В целом, мы различаем два типа нарезки торта:
Пропорциональное деление, при котором ресурс делится между n людьми с субъективными оценками, при этом каждый человек получает не менее 1/n ресурса по своей субъективной оценке.
Разделение без зависти, пропорциональное разделение с дополнительным свойством, заключающимся в том, что каждый человек считает, что его доля, по крайней мере, не хуже доли любого другого агента.
Концепция "справедливости" может быть дополнительно формализована как удовлетворяющая следующим условиям (Pacuit, 2007):
Пропорциональность: Каждый игрок получает по крайней мере 1/n ресурса в соответствии со своей собственной оценкой его полезности
Отсутствие зависти: Ни один игрок не готов отказаться от своего распределения в обмен на распределение других игроков
Справедливость: Каждый игрок оценивает свое распределение так же, как и другие распределения, в соответствии со своей собственной функцией полезности
Эффективность: Не существует другого разделения, которое лучше максимизировало бы коллективную полезность каждого или кого-либо еще.
Процедуры перемещения ножа
Несколько методов разделения называются "процедурами перемещения ножа", описанными Остином (1982) следующим образом:
Процедура разрезания торта с помощью движущегося ножа Для двоих, Алисы и Боба:
Один игрок проводит ножом по торту, традиционно слева направо
Торт разрезается, когда любой из участников говорит "стоп"
Если каждый игрок объявляет "стоп", когда он или она видит, что нож находится на грани 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/n кусочков, не убавляя ни кусочка, все, кроме двух последних игроков, могут позавидовать тем, кто получит кусочки позже — т.е., хотя игроки в игре довольны своим кусочком, они не могут гарантировать, что не предпочли бы кусочек, позже полученный кем-то другим (Brams & Taylor, 1996).
Метод "Движущегося ножа" Дюбинса-Спаньера
Версией метода "Последнего уменьшения" в непрерывном режиме является метод "движущегося ножа" Дубинса-Спаньера, предложенный Лестером Э. Дубинсом и Эдвином Х. Спаньером (1961). Это первая процедура с использованием движущегося ножа, описанная в литературе (хотя, как отмечают Brams & Taylor, более ранняя "процедура заливки" была опубликована в Davis, 1955).
Метод движущегося ножа Дюбинса-Спаньера:
Судья держит нож на левой стороне торта, а затем непрерывно перемещает нож к правой стороне
В любой момент любой из трех игроков может крикнуть "режь" и получить кусочек слева от ножа, начиная игру
Процедура повторяется с оставшейся частью торта. Если два оставшихся игрока одновременно кричат "режь!", отрезанный кусок отдается одному из игроков случайным образом
Процедура Дубинса-Спаньера справедлива (каждый игрок оценивает свое распределение так, чтобы оно было таким же, как у других, в соответствии со своей собственной функцией полезности), но не без зависти. Ключевое различие между этой процедурой и последним уменьшителем заключается в том, что каждый игрок, все еще находящийся в игре, должен делать непрерывный выбор, а не по очереди.
Процедура "Одинокого разделителя" Штайнхауса-Куна
Так называемая "процедура одинокого разделителя" - это процедура справедливого раздела, которая, подобно последнему уменьшителю и методу перемещения ножа, описанному выше, также приводит к пропорциональному разделению ресурса между произвольным количеством людей. Она была предложена теоретиком игр Гарольдом Куном в 1967 году и работает следующим образом (Brams & Taylor, 1996), в случае n = 3 для простоты:
Процедура Штайнхауса-Куна "Одинокий разделитель" для трех человек - Алисы, Боба и Кэрол:
Пусть Алиса разделит торт на три части равной ценности, исходя из ее функции полезности
Теперь пусть Боб и Кэрол укажут, какие кусочки для них приемлемы (по крайней мере, 1/3 стоимости на основе их собственных функций полезности) Это приводит к двум взаимоисключающим случаям:
Либо Боб, либо Кэрол сочтут приемлемыми два или более кусочка. Если Боб сочтет приемлемым более одного кусочка, то выбор в порядке: Кэрол, Боб и Алиса приведет к пропорциональному распределению
Или и Боб, и Кэрол указывают, что приемлемо не более одного кусочка. Затем мы отдаем Алисе кусочек, который Боб и Кэрол считают неприемлемым, затем выполняем процедуру "раздели и выбери" между Бобом и Кэрол. Это также приведет к пропорциональному распределению Поскольку ни Кэрол, ни Боб не могут подумать, что все три кусочка, нарезанные Алисой, неприемлемы (размером меньше 1/3), вариант два должен иметь преимущественную силу, если вариант один этого не делает, поскольку это единственно две возможные ситуации.
Процедура "одинокого разделителя" также не лишена зависти, потому что в первом случае, хотя Алиса и Боб никому не будут завидовать, Кэрол позавидует Бобу, если он возьмет больший из двух кусков, которые она сочла приемлемыми. Во втором случае, если, по мнению Боба, раздел между Бобом и Кэрол не будет точно 50/50, то он будет завидовать кому-то из двух других (Brams & Taylor, 1996).
Кун опубликовал результат в главе, озаглавленной "Об играх справедливого разделения", в книге 1967 года "Очерки математической экономики в честь Оскара Моргенштерна" под редакцией Мартина Шубика издательства Принстонского университета. В книге Кун представляет случай произвольного числа игроков и доказывает справедливое пропорциональное деление, используя теорему Фробениуса-Кенига.
Разделение без зависти
Дополнительный критерий отсутствия зависти требует, чтобы в дополнение к пропорциональному разделению (справедливости) распределение ресурса обладало свойством отсутствия зависти, а именно:
Ни один игрок не готов отказаться от своего распределения в обмен на распределение других игроков
Дискретная процедура Селфриджа-Конвея
Первая процедура нарезки торта без зависти для трех игроков была открыта Джоном Селфриджем в 1960 году, без публикации доказательства. Позже она была заново открыта Джоном Хортоном Конвеем независимо, хотя он также решил не публиковать ее (Brams & Taylor, 1996). Для игроков Алисы, Боба и Кэрол процедура может быть описана следующим образом:
Процедура разрезания торта без зависти от Селфриджа-Конвея для игроков Алисы, Боба и Кэрол:
Алиса делит торт на три части A, B, C, которые, по ее мнению, одинакового размера.
Боб считает, что кусок A самый большой
Теперь Боб отрезает кусочек от куска А, чтобы он был того же размера, что и второй по величине кусок. Теперь кусочек А делится на: 1. Обрезанный кусочек А₁ и обрезки А₂
Затем Кэрол выбирает кусочек из A₁ и двух других кусочков B, C
Затем Боб выбирает кусочек с ограничением, что если Кэрол не выбрала A₁, он должен сделать это
Алиса, наконец, выбирает последний кусочек, оставляя только обрезки A₂, которые нужно разделить между тремя Обрезанный кусочек A₁ выбирал либо Кэрол, либо Боб. Назовите игрока, который выбрал его, игроком A, а другого игрока B. Чтобы разделить между ними обрезки A₂:
Игрок B сначала разрезает обрезки A₂ на три равные части A₂₁, A₂₂ и A₂₃
Затем игрок А выбирает кусочек A₂, назовем его A₂₁
Затем Алиса выбирает кусочек A₂, назовем его A₂₂
-
Игрок B, наконец, выбирает последний оставшийся кусочек A₂, называет его A₂₃
Результат процедуры:
Игрок А получил A₁ + A₂₁ Игрок B получил B + A₂₃ Алиса получила кусочек C + A₂₂ Процедура Селфриджа-Конвея гарантирует отсутствие зависти, потому что, если Кэрол выбирает первой, она делает это, зная, из чего ей выбирать, и поэтому не будет завидовать никому, кто выберет любой из двух других кусочков. Поскольку Боб создает двустороннюю завязку для самого большого куска, обрезая кусочек А, и по крайней мере один из этих двух остается доступным после выбора Кэрол, он также никому не будет завидовать. Наконец, поскольку, если Кэрол не выбрала A₁, это должен сделать Боб, обрезанный кусочек не может быть тем, что осталось. Таким образом, Алиса выбирает один из двух необрезанных кусочков, которые она нарезала сама, и поэтому никому не будет завидовать.
Отсюда ключевое наблюдение: Алиса не будет завидовать игроку, получившему отрезанный кусочек. Алиса разделила кусочки на три равные части и получила кусочек без обрезки, в то время как обрезанный кусочек, даже с добавлением обрезков, даст Кэрол только кусочек, который, по мнению Алисы, будет точно такого же размера, как тот, который она получила (Brams & Taylor, 1996).
Процедура "Движущихся ножей" Стромквиста
Для связных кусков так называемая процедура перемещения ножей Стромквиста, впервые представленная Уолтером Стромквистом в 1980 году, обеспечивает как пропорциональность, так и отсутствие зависти. Аналогично процедуре перемещения ножа Дюбина-Спаньера, она требует, чтобы игроки постоянно выбирали, обеспечит ли им пропорциональный кусок часть слева от ножа.
Процедура разрезания торта без зависти с помощью "Движущихся ножей" Стромквиста:
Судья проводит ножом слева направо по одномерному торту, гипотетически разделяя его на маленький левый кусочек и большой правый
У каждого игрока есть свой нож, который держат параллельно и справа от ножа судьи, всегда располагая его так, чтобы он разделял оставшуюся часть торта пополам
В любой момент любой игрок может крикнуть "режь", получив кусок слева от ножа судьи. Одновременно разрез производится тем из ножей трех игроков, который находится посередине ножей трех игроков
-
Игрок, который сделал выбор в пользу разрезания, получает кусочек слева от ножа судьи. Игрок, чей нож был ближе всего к ножу судьи, получает средний кусочек. Последний игрок получает правый кусочек. Процедура перемещения ножей Стромквиста гарантирует отсутствие зависти, потому что тот, кому достанется средний кусок (из двух игроков, которые не кричали "режь", его нож был ближе всего к ножу судьи), держал либо второй, либо третий нож слева. Следовательно, игрок, получивший средний кусок, считает, что средний кусок либо больше нужного (если его / ее нож находится ближе всего к ножу судьи), либо равен по величине нужному куску (если его / ее нож является тем ножом, которым делится оставшаяся часть торта). Аналогично, другой игрок, который не кричал "режь", держал либо нож, которым разрезал оставшуюся часть торта, либо нож в крайнем правом положении.
Ножи игроков и судьи в процедуре разрезания торта
Эпилог
Первая публикация Хуго Штайнхауса "Проблема справедливого разделения" положила начало столетию все более сложных и завершенных процедур разрезания торта. Раздел справедливого дележа, который сам по себе является подразделом теории игр, разрезание торта сегодня выступает как архетипическая игра, представляющая стимулы и ограничения определенных видов социально-научных конфликтов конкуренции и сотрудничества в некооперативных играх.
Всё это и много другое — ТГ "Математика не для всех"
Комментарии (16)
Alexandroppolus
16.08.2024 11:20+1В своё время решил так (на примере 3 чуваков):
1) А делит пирог на 2 части.
2) В выбирает себе одну из двух частей.
3) С разрезает каждую из половин на 3 части. А и В отдают ему по одному кусочку.
С постарается резать ровно на 1/3, чтобы ему отдадали по 1/3 от каждой половины, итого 1/3 от всего пирога (независимо от правильности разреза А). А постарается разрезать ровно, и ему перепадет половина, от которой он отдаст не более 1/3. В общем, исключен сговор любых двух игроков.
И вроде как, это обобщается на N. Игрок D может поделить каждый из 6 кусков на 4, владельцы отдадут ему по 1/4 от своих кусков. И т.д. Минус в том, что надо порезать на N! кусков.
CitizenOfDreams
16.08.2024 11:20+2"Если все участники сделки считают, что их обманули, значит, сделка была справедливой".
Shpakov
16.08.2024 11:20"В случаях, когда количество людей, разделяющих пирог, превышает два, n > 2, сложность протокола значительно возрастает"
Зачем усложнять? Это можно решить так: сначала все голосуют за того, кого надо исключить из деления торта. Повторяем голосование до тех пор, пока не останется 2 человека. А для такого случая решение уже есть. )))
Важное дополнение: "выбирающий" не должен видеть, какой именно кусок он выбрал. "Режущий" нарезает куски, когда готово - "выбирающий" не глядя говорит кому какой кусок.
adeshere
16.08.2024 11:20А почему нельзя решить задачу через функции полезности (ФП) игроков? Которые показывают, насколько привлекателен данный кусочек торта именно для этого игрока по сравнению с остальным тортом?
Итак, пусть у нас есть N игроков и торт длиной N. Для простоты нормировки, потребуем также, чтобы интеграл от каждой ФП равнялся бы N. Очевидно, что каждый участник будет доволен, если получит такую часть торта, что интеграл от его ФП по ней будет больше 1. Для краткости будем обозначать интеграл от ФП для участника номер i по участку R как ФП(R,i).
Дальше собственно алгоритм. Он итеративный и включает два шага.
1) Для начала мысленно развернем торт в одну линию и нарисуем графики всех ФП. Теперь разобьем весь торт на отрезки, границы которых задаются точками пересечения ФП друг с другом. Если где-то некоторые ФП совпадают, то границы такого участка (где они расходятся) тоже будут "точками разбиения". Тем самым мы не только свели непрерывную задачу к дискретной, но и гарантировали, что в пределах любого фрагмента любые ФП либо совпадают, либо одна из них лежит строго выше другой (кроме концов отрезка).
2) Дискретная задача решается итеративно. В пределах любого полученного на шаге (1) отрезка S либо все ФП совпадают, либо есть есть ровно одна ФП, которая всюду идет выше, чем остальные. Пусть это будет участник z. Отдав кусок торта S (его длину обозначим как L) или любую его часть (это важно!) участнику с этой ФП, мы улучшаем ситуацию для всех. Это следует из того, что ФП(S,z) больше, чем сумма ФП(S, все кроме z), Но тогда в силу условия нормировки ФП(торт-S,z) будет меньше, чем ФП(торт-S,все-z). Попросту говоря, участник z получит на этом шаге непропорционально много, со своей точки зрения, но все остальные участники будут считать, что он получил непропорционально мало (а им, соответственно, останется непропорционально много).
2а) Дополнительное условие к шагу (2): важно, чтобы в результате (2) суммарная (по всем доставшимся z кусочкам) ФП(z) не превысила 1. Если отдача целого куска S приводит к такой ситуации, то ставим дополнительную точку разбиения (или несколько точек) и отдаем участнику z ровно столько торта, чтобы его ФП достигла 1. После этого он выбывает из дальнейшей дележки.
3) Теперь докажем, что процесс остановится.
Шаг 1 всегда уменьшает количество точек разбиения. Если оно изначально было конечным (в реальном мире вспоминаем число Авогадро), то при неизменном количестве участников процесс обязательно завершится.
На шаге 2 число точек разбиения может вырасти, но зато уменьшается число участников. Которое тоже конечно (вспоминаем про минимальный размер участника в атомах,число атомов на Земле и т.д..
Если в поедании торта участвуют инопланетяне, включая ненаблюдаемые части Вселенной, то алгоритм, по всей видимости, не подходит
4) Ну и еще одно замечание. Если ФП участников не совпали, и если в ходе итераций применялось условие (2а), (а оно будет применяться с вероятностью 1, если только точки пересечения ФП не расставились особым образом), то в конце процедуры: а) значение ФП у каждого участника будет равно 1, и при этом б) часть торта останется неподеленной. Разделив ее на всех каким-либо образом, мы получим ФП(i) > 1 для всех участников сделки.
5) Тут, конечно, может еще возникнуть вопрос об остановке процедуры (4). Например, если применять в цикле "деления остатков" шаги (1-2), то гарантий никаких нет. Я бы поэтому предложил в какой-то момент снова вспомнить про число Авогадро, и прекратить итерации, как только число молекул в неподеленной части торта станет соизмеримо с числом участников N. Тогда просто делим этот остаток всем поровну.
6) По построению очевидно, что описанная процедура гарантирует "пропорциональное деление". А вот с "разделением без зависти" немного сложнее. Без наложения доп.условий оно явно не гарантируется.
UPD. Сейчас еще вот какая идея пришла. А если давать участнику z не один фрагмент из первого разделения, а выбирать такие куски T (возможно, неодносвязные), в пределах которых отношение ФП(T,z) к ФП(T, все кроме z) максимально? Не гарантирует ли это тем самым "без зависти"?
Правда, такое требование может повлечь бесконечный рост числа "точек разделения", если не наложить какие-то ограничения на ФП. Ведь если не разрешить фрагментарность, то оно в любой момент может стать бесконечным. А если фрагментарность запрещена, то не получится с завистью. Ведь тогда мы не сможем выбирать часть торта с максимальным отношением ФП(T,z) / ФП(T, все кроме z).
С другой стороны, какие-то ограничения на ФП нам придется накладывать в любом случае. Иначе оно может оказаться бесконечным уже на первом шаге первого варианта алгоритма... Одна надежда на число Авогадро. Что ФП не имеет права менять свое значение чаще, чем при смещении ножа на молекулу...
adeshere
16.08.2024 11:20Прошу прощения, не уложился в лимит времени. Поэтому поправку пишу отдельно.
"В пределах любого полученного на шаге (1) отрезка S либо все ФП совпадают, либо есть есть ровно одна ФП, которая всюду идет выше, чем остальные"
Разумеется, строго выше остальных могут идти две или больше совпадающих ФП. Тогда отдаем этот кусок не одному участнику, а группе участников с совпадающими ФП (делим на всех). Это немного усложняет разбор особых случаев, но принципиальных проблем вроде быть не должно. Например, при обработке условия 2а у нас появится не одна новая "точка разделения", а по числу участников. Но вроде бы это решаемо , и принципиально ничего не меняет (выбираем из них того, чья точка самая первая, отдаем ему его долю и пусть выбывает).
Ну и еще уточню, что после выбытия любого участника разбиение торта на отрезки выполняется заново, хотя это вроде бы очевидно. При этом можно использовать те же самые (заданные изначально) ФП, просто перенормировав их по оставшейся части торта.
А вот чего я не сообразил - это что такая перенормировка наверно может привести к возникновению "зависти". Так как теперь возникает проблема с выполнением условия [ФП(T,z) / ФП(T, все кроме z) = max] для всех остальных участников, кроме выбывшего. Тут у меня явно косяк. Надеюсь, кто-нибудь сможет это подтвердить официально ;-)
avshkol
16.08.2024 11:20Если кто-то получил свой кусок и уже не участвует в дальнейшем разделе, мы не сможем гарантировать, что у него не проявится зависть к одному или нескольким игрокам после завершения раздела. Ведь все оценивают свою и чужие доли субъективно и не имеют объективной линейки или весов.
adeshere
16.08.2024 11:20Если кто-то получил свой кусок и уже не участвует в дальнейшем разделе, мы не сможем гарантировать, что у него не проявится зависть к одному или нескольким игрокам после завершения раздела. Ведь все оценивают свою и чужие доли субъективно и не имеют объективной линейки или весов.
Согласен, такая проблема есть. Только к субъективности оценки она отношения не имеет. Ведь эти оценки хотя и субъективны, но фиксированы во времени. Математически это означает, что любой участник заранее может сказать относительно любого фрагмента торта: это справедливая доля или нет (больше/меньше). Ну а из этого условия уже можно перейти к функциям полезности. Они задаются изначально, и далее не меняются (иначе задача вообще решения не имеет).
Но Вы правы, что при итеративном алгоритме гарантировать отсутствие зависти непросто. Ведь это зависит от вида ФП, который нам неизвестен. Я подозреваю, что при большом количестве игроков никакой итеративный алгоритм не сможет гарантировать отсутствие зависти. Даже если упорядочить игроков по какому-то критерию, всегда может оказаться, что у первых выбывающих игроков очень похожие ФП, а где-то в конце - очень непохожие. Если последние игроки будут делить торт согласно своим ФП, то зависть может появиться у первых игроков. А если делить последние кусочки не совсем в соответствии с ФП последних игроков, то, наоборот, последние будут завидовать первым.
Было бы интересно узнать, действительно ли у итеративных алгоритмов есть такое ограничение.
А неитеративные алгоритмы для большого количества участников будут достаточно сложными, как мне кажется. В статье приведены примеры для трех участников, и даже в этом случае для понимания приходится включать голову. А если нас будет девять? Я не уверен, что после шашлыка и прочего мы сможем такой алгоритм беспристрастно реализовать. Особенно если придется
быстро считать молекулы
медленно не поучится: торт либо испортится, либо потеряет свою актуальность
Было бы интересно узнать мнение автора публикации про эти вопросы. Надеюсь, он знает ответы ;-)
Оффтопик
А если без математики, то мы в лесу делим торт так. Кто-нибудь его разрезает (можно это делать вдвоем для большей объективности). Потом один из присутствующих отворачивается, а другой берет кусочек и спрашивает "Кому?" Отвернувшийся (он не видит куска) отвечает, называя всех (включая себя) в произвольном порядке.
И еще одна идея. Поскольку критерий истины - практика, то я бы предложил всем присутствующим собраться и сравнить разные алгоритмы в лесу у нашего традиционного новогоднего костра (можно с детьми). Мероприятие происходит ежегодно вечером 13 января (СНГ) примерно в 100км от Москвы. Пишите в личку ближе к НГ. Торты будут ;-)
avshkol
16.08.2024 11:20Когда мы говорим о "торте", подразумеваем нечто объективно однородное и правильной формы. Лучше говорить о "земле" - тут понятно, что и делимый участок может быть самой причудливой формы, и плодородность неравномерная, и перепад высот, и где-то заросла кустарником...
Далее, мы рассматриваем одну человеческую "функцию" - зависть. Но есть ещё минимум две, которые могут преобладать в этой игре над завистью у одного или нескольких игроков:
"Чувство справедливости" (субъективное), когда человеку важнее, чтобы все кусочки были (на его взгляд) равными, независимо от того, насколько его кусочек будет субъективно лучше. В более сложном случае - справедливость будет требовать, чтобы тому, кто ранее получил больше, сейчас досталось меньше...
"Жадность", что может проявиться, например, в том, что момент с движущихся ножом будет отодвинут так, что первый менее жадный, крикнувший "стоп", получит лучший кусок.
Glen5
Почему то не учтен вариант, в котором "выбирающий" дает леща "режущему", чтобы тот отрезал "выбирающему" кусок побольше. (Пример о том, что "правила игры" в реальности не есть что-то незыблимое, а всегда могут быть пересмотрены еще до начала). Впрочем, такая оторванность от реальности присуща теориям игр.
Почему вы мешаете понятия о справедливом делении и о том что все останутся довольны? Может выбирающий будет доволен, если 90% достанется ему, а 10 он готов отдать, только потому что он такой добрый и социальноориентированный.
PS как чисто математическая задачка, вопросов нет, интересно поломать голову и статья в этом плане интересная. Но с прикладной точки зрения совершенно не применимо.
Alexandroppolus
Тогда режущий останется недоволен, а тут надо, чтобы все были довольны
С тем же успехом выбирающий может просто забрать себе весь пирог и уйти.
Shpakov
Давать леща человеку с ножом - так себе идея...
anonymous
НЛО прилетело и опубликовало эту надпись здесь
avshkol
Это работает, если бедность семьи - следствие объективных обстоятельств или непредсказуемых бед, а не лени/криворукости/упертости в неверных методах земледелия...
В противном случае бедная семья и урожай не вырастит, и плодородный участок испортит...
anonymous
НЛО прилетело и опубликовало эту надпись здесь