Комментарии 17
один человек ("режущий") разрезает торт на две части; другой человек
("выбирающий") выбирает одну из частей; режущий получает оставшийся
кусок.
Почему то не учтен вариант, в котором "выбирающий" дает леща "режущему", чтобы тот отрезал "выбирающему" кусок побольше. (Пример о том, что "правила игры" в реальности не есть что-то незыблимое, а всегда могут быть пересмотрены еще до начала). Впрочем, такая оторванность от реальности присуща теориям игр.
Тогда режущий останется недоволен, а тут надо, чтобы все были довольны
Почему вы мешаете понятия о справедливом делении и о том что все останутся довольны? Может выбирающий будет доволен, если 90% достанется ему, а 10 он готов отдать, только потому что он такой добрый и социальноориентированный.
PS как чисто математическая задачка, вопросов нет, интересно поломать голову и статья в этом плане интересная. Но с прикладной точки зрения совершенно не применимо.
Почему то не учтен вариант, в котором "выбирающий" дает леща "режущему", чтобы тот отрезал "выбирающему" кусок побольше
Тогда режущий останется недоволен, а тут надо, чтобы все были довольны
С тем же успехом выбирающий может просто забрать себе весь пирог и уйти.
Давать леща человеку с ножом - так себе идея...
самая бедная семья получала на год самый плодородный надел - в итоге не было бедных
Это работает, если бедность семьи - следствие объективных обстоятельств или непредсказуемых бед, а не лени/криворукости/упертости в неверных методах земледелия...
В противном случае бедная семья и урожай не вырастит, и плодородный участок испортит...
В своё время решил так (на примере 3 чуваков):
1) А делит пирог на 2 части.
2) В выбирает себе одну из двух частей.
3) С разрезает каждую из половин на 3 части. А и В отдают ему по одному кусочку.
С постарается резать ровно на 1/3, чтобы ему отдадали по 1/3 от каждой половины, итого 1/3 от всего пирога (независимо от правильности разреза А). А постарается разрезать ровно, и ему перепадет половина, от которой он отдаст не более 1/3. В общем, исключен сговор любых двух игроков.
И вроде как, это обобщается на N. Игрок D может поделить каждый из 6 кусков на 4, владельцы отдадут ему по 1/4 от своих кусков. И т.д. Минус в том, что надо порезать на N! кусков.
"Если все участники сделки считают, что их обманули, значит, сделка была справедливой".
"В случаях, когда количество людей, разделяющих пирог, превышает два, n > 2, сложность протокола значительно возрастает"
Зачем усложнять? Это можно решить так: сначала все голосуют за того, кого надо исключить из деления торта. Повторяем голосование до тех пор, пока не останется 2 человека. А для такого случая решение уже есть. )))
Важное дополнение: "выбирающий" не должен видеть, какой именно кусок он выбрал. "Режущий" нарезает куски, когда готово - "выбирающий" не глядя говорит кому какой кусок.
А почему нельзя решить задачу через функции полезности (ФП) игроков? Которые показывают, насколько привлекателен данный кусочек торта именно для этого игрока по сравнению с остальным тортом?
Итак, пусть у нас есть 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).
С другой стороны, какие-то ограничения на ФП нам придется накладывать в любом случае. Иначе оно может оказаться бесконечным уже на первом шаге первого варианта алгоритма... Одна надежда на число Авогадро. Что ФП не имеет права менять свое значение чаще, чем при смещении ножа на молекулу...
Прошу прощения, не уложился в лимит времени. Поэтому поправку пишу отдельно.
"В пределах любого полученного на шаге (1) отрезка S либо все ФП совпадают, либо есть есть ровно одна ФП, которая всюду идет выше, чем остальные"
Разумеется, строго выше остальных могут идти две или больше совпадающих ФП. Тогда отдаем этот кусок не одному участнику, а группе участников с совпадающими ФП (делим на всех). Это немного усложняет разбор особых случаев, но принципиальных проблем вроде быть не должно. Например, при обработке условия 2а у нас появится не одна новая "точка разделения", а по числу участников. Но вроде бы это решаемо , и принципиально ничего не меняет (выбираем из них того, чья точка самая первая, отдаем ему его долю и пусть выбывает).
Ну и еще уточню, что после выбытия любого участника разбиение торта на отрезки выполняется заново, хотя это вроде бы очевидно. При этом можно использовать те же самые (заданные изначально) ФП, просто перенормировав их по оставшейся части торта.
А вот чего я не сообразил - это что такая перенормировка наверно может привести к возникновению "зависти". Так как теперь возникает проблема с выполнением условия [ФП(T,z) / ФП(T, все кроме z) = max] для всех остальных участников, кроме выбывшего. Тут у меня явно косяк. Надеюсь, кто-нибудь сможет это подтвердить официально ;-)
Если кто-то получил свой кусок и уже не участвует в дальнейшем разделе, мы не сможем гарантировать, что у него не проявится зависть к одному или нескольким игрокам после завершения раздела. Ведь все оценивают свою и чужие доли субъективно и не имеют объективной линейки или весов.
Если кто-то получил свой кусок и уже не участвует в дальнейшем разделе, мы не сможем гарантировать, что у него не проявится зависть к одному или нескольким игрокам после завершения раздела. Ведь все оценивают свою и чужие доли субъективно и не имеют объективной линейки или весов.
Согласен, такая проблема есть. Только к субъективности оценки она отношения не имеет. Ведь эти оценки хотя и субъективны, но фиксированы во времени. Математически это означает, что любой участник заранее может сказать относительно любого фрагмента торта: это справедливая доля или нет (больше/меньше). Ну а из этого условия уже можно перейти к функциям полезности. Они задаются изначально, и далее не меняются (иначе задача вообще решения не имеет).
Но Вы правы, что при итеративном алгоритме гарантировать отсутствие зависти непросто. Ведь это зависит от вида ФП, который нам неизвестен. Я подозреваю, что при большом количестве игроков никакой итеративный алгоритм не сможет гарантировать отсутствие зависти. Даже если упорядочить игроков по какому-то критерию, всегда может оказаться, что у первых выбывающих игроков очень похожие ФП, а где-то в конце - очень непохожие. Если последние игроки будут делить торт согласно своим ФП, то зависть может появиться у первых игроков. А если делить последние кусочки не совсем в соответствии с ФП последних игроков, то, наоборот, последние будут завидовать первым.
Было бы интересно узнать, действительно ли у итеративных алгоритмов есть такое ограничение.
А неитеративные алгоритмы для большого количества участников будут достаточно сложными, как мне кажется. В статье приведены примеры для трех участников, и даже в этом случае для понимания приходится включать голову. А если нас будет девять? Я не уверен, что после шашлыка и прочего мы сможем такой алгоритм беспристрастно реализовать. Особенно если придется
быстро считать молекулы
медленно не поучится: торт либо испортится, либо потеряет свою актуальность
Было бы интересно узнать мнение автора публикации про эти вопросы. Надеюсь, он знает ответы ;-)
Оффтопик
А если без математики, то мы в лесу делим торт так. Кто-нибудь его разрезает (можно это делать вдвоем для большей объективности). Потом один из присутствующих отворачивается, а другой берет кусочек и спрашивает "Кому?" Отвернувшийся (он не видит куска) отвечает, называя всех (включая себя) в произвольном порядке.
И еще одна идея. Поскольку критерий истины - практика, то я бы предложил всем присутствующим собраться и сравнить разные алгоритмы в лесу у нашего традиционного новогоднего костра (можно с детьми). Мероприятие происходит ежегодно вечером 13 января (СНГ) примерно в 100км от Москвы. Пишите в личку ближе к НГ. Торты будут ;-)
Когда мы говорим о "торте", подразумеваем нечто объективно однородное и правильной формы. Лучше говорить о "земле" - тут понятно, что и делимый участок может быть самой причудливой формы, и плодородность неравномерная, и перепад высот, и где-то заросла кустарником...
Далее, мы рассматриваем одну человеческую "функцию" - зависть. Но есть ещё минимум две, которые могут преобладать в этой игре над завистью у одного или нескольких игроков:
"Чувство справедливости" (субъективное), когда человеку важнее, чтобы все кусочки были (на его взгляд) равными, независимо от того, насколько его кусочек будет субъективно лучше. В более сложном случае - справедливость будет требовать, чтобы тому, кто ранее получил больше, сейчас досталось меньше...
"Жадность", что может проявиться, например, в том, что момент с движущихся ножом будет отодвинут так, что первый менее жадный, крикнувший "стоп", получит лучший кусок.
А что насчет равновесия Нэша ?
Как поделить торт и не поссориться: математические протоколы справедливого деления