Обзор: Нетрудно поделить торт на двоих,
Нетрудно поделить торт на двоих, никого не обидев: я режу, ты выбираешь; но на троих, на четверых или на всех — уже сложнее.Процедура Брамса — Тейлора — это процедура завистливого разрезания торта. Процедура предлагает процедуру завистливого дележа торта на любое положительное число игроков.
Процедура Брамса — Тейлора — Цвикера — это протокол завистливого разрезания торта на 4 участников.
Завистливое разрезание торта — вид справедливого разрезания торта. Это разрезание неоднородного ресурса («торта») с удовлетворением критерия отсутствия зависти, а именно, что любой участник обладает чувством, что выделенная ему часть не меньше кусков, отданных другим участникам.
Процедура Селфриджа — Конвея — это дискретная процедура, дающая разрезание торта без зависти для трёх участников. Процедура названа именем Джона Селфриджа и Джона Конвея. Селфридж обнаружил процедуру в 1960 году и сообщил о ней Ричарду Гаю, который рассказал о ней многим людям, но сам Селфридж не опубликовал свое открытие официально. Джон Конвей позднее открыл процедуру независимо и также не публиковал. Это было первой дискретной процедурой деления торта без зависти для трёх участников и открыла путь для более продвинутых процедур для n участников.
Дели и выбирай — это процедура разрезания торта между двумя участниками, в результате которой отсутствует зависть. В задаче предполагаются неоднородные блага или ресурсы («торт») и два участника с различными предпочтениями на отдельные части торта. Протокол работает следующим образом: один из участников («разрезающий») режет торт на два куска, второй участник («выбирающий») выбирает один из кусков, а разрезающему достаётся оставшийся кусок.
Теги: Завистливое разрезание торта Протокол Дели-и-выбирай Процедура Селфриджа — Конвея Процедура Брамса — Тейлора — Цвикера Процедура Брамса — Тейлора поделить торт двоих никого троих четверых всех сложнее