Max Home IndustryЗадача, которую необходимо решить, звучит тривиально — разрезать торт так, чтобы каждый думал, что получил справедливую долю. Вы также должны добавить наблюдение, что люди жульничают и жадны, чтобы увидеть, что это может быть проблемой. Теперь у нас есть алгоритм, который работает, даже когда торт распространяется через Интернет.
Разрезание торта может показаться неважной проблемой, но если вы перефразируете это как совместное использование ресурсов или территории, то вы быстро увидите, что у этого есть много практических применений. Это может даже пригодиться, когда есть настоящий пирог, которым можно поделиться, но я подозреваю, только если на вечеринке участвует группа программистов.
Прежде чем вы решите, что разрезать торт — это просто, давайте рассмотрим простой случай — всего два человека делят один торт. Если каждый оценивает торт одинаково, то очевидно, что они оба хотят получить одинаковое количество торта. Чтобы сделать вещи интересными, давайте предположим, что у каждого человека есть функция полезности u1 и u2, которая измеряет, насколько они ценят разное количество торта.
Введение функций полезности делает проблему более интересной, потому что каждый участник имеет собственное представление о стоимости или «размере» порций торта. В этой задаче важно то, что все участники думают, что они получили по крайней мере свою справедливую долю или большую долю пирога, измеренную их функцией полезности.
Так как же разделить торт между двумя людьми?
Одно из решений — алгоритм «разделяй и выбирай».
Один из участников разрезает торт, а другой выбирает. Куттер разделит торт на две части, равные по их собственной функции полезности. Затем выборщик выберет более крупный срез в соответствии с их функцией полезности (или случайным образом, если они кажутся равными).
Вы должны увидеть, что этот алгоритм имеет ряд желаемых свойств.
Лучшее решение для резака — разделить торт поровну, потому что в этом случае, независимо от того, какой кусок берет выбор, оказывается, что торт был разделен поровну. Независимо от того, в чем разница между вспомогательными функциями селектора и резака, выборщик всегда будет доволен, потому что он может выбрать самый большой или, по крайней мере, равный кусок торта.
Таким образом, торт делится «справедливо» с точки зрения обоих игроков — каждый из них получает то, что считает половиной торта или лучше.
Обобщая до n человек: алгоритм просто справедлив, если каждый участник получает кусок, который они оценивают как 1 / n или более от целого.
Таким образом, для n = 2 алгоритм «разделяй и выбирай» хорош и доказуемо «просто справедлив».
Есть алгоритмы, которые просто справедливы при n> 2. Например, алгоритм движущегося ножа «Dubins-Spanier» использует TPP «доверенной третьей стороны». TPP плавно перемещает нож вдоль пирога, который для простоты мы теперь предполагаем, что это прямоугольный стержень.
По мере перемещения ножа выделяемый срез S увеличивается в размере. Каждый из участников отрабатывает ui (A) и первым замечает, что их вызовы ui (A) = ui (cake) / n прекращаются и получают кусок.
Затем они прекращают процедуру, и эта процедура повторяется с n-1 участниками и оставшейся частью торта.
Обратите внимание, что каждый участник получает кусок, который стоит не менее 1 / n от общего количества торта, и нет никакого стимула жульничать, потому что вы можете получить меньший, а не больший кусок.
Алгоритм движущегося ножа кажется простым, но может быть трудно понять, что он действительно справедлив, и доказать, что это требует некоторой работы.
У этого алгоритма есть две проблемы. Во-первых, это работает только в том случае, если разделение является непрерывным, и если все участники могут видеть, что происходит без каких-либо задержек, и могут кричать, остановитесь без каких-либо задержек.
Теперь у нас есть новый алгоритм, который работает асинхронно и поэтому подходит для использования, скажем, алгоритмов совместного использования, реализованных в Интернете. Детали немного сложны, потому что он включает в себя криптографически безопасный аукцион, где каждый участник делает ставку в зашифрованной форме, что позволяет узнать максимум и кто сделал ставку, не зная другую ставку — для этого требуется гомоморфное шифрование.
С этим криптографическим аукционом новый дискретный асинхронный алгоритм работает следующим образом:
Сначала предположим, что общая длина торта составляет от 0 до 2 м, где m — большое целое число, а каждая точка разреза — целое число.
Каждый игрок определяет свою предпочтительную целочисленную точку разрезания xi так, чтобы полученный кусок стоил 1 / n от общего торта — по их показателю полезности.
Эта точка отсечения зашифровывается и транслируется другим участникам в качестве ставки на безопасном аукционе.
Все игроки определяют максимальную ставку и сделавшего ее игрока, не раскрывая других ставок, и победитель получает кусок, за который они сделали ставку.
Опять же, как и алгоритм движущегося ножа, в результате участник получает кусок стоимостью не менее 1 / n всего торта по их меркам. Как и в алгоритме движущегося ножа, участник, получивший награду, выпадает, и процедура повторяется с оставшейся частью торта.
Есть некоторые тонкости, о которых нужно позаботиться, чтобы процедура была эффективной, но это общая идея. Алгоритм просто честный, и ни одно из событий не должно выполняться одновременно.
Так что в следующий раз, когда вы организуете интернет-вечеринку и вам нужно будет поделиться тортом, вы можете выполнить работу асинхронно.