Семинары

Как по-честному поделить шоколадку на N человек? Если шоколадка однородная, то вопрос только в точности измерений, но вот если шоколадка неоднородная, то становятся важны личные вкусы: для одного может быть ценнее одна часть, для другого — другая. Придумано немало протоколов дележа, в результате которых каждый участник получает субъективно хотя бы 1/N всей шоколадки. Но это условие не гарантирует отсутствия зависти: например, один из троих делящих может считать, что ему досталось 35%, а другому 40%, т.е. ещё больше.

Зависти не будет только в том случае, когда каждый участник считает, что его кусок не хуже любого другого. Теоремы о неподвижных точках гарантируют, что делёж без зависти всегда существует, однако вплоть до недавнего времени конечная процедура его получения была известна только для N=3. В 2015 году Азиз и Маккензи построили такую процедуру для N=4, а в 2016 году обобщили её для произвольного N. Но их алгоритм весьма сложен. В докладе будут рассказаны формальная постановка задачи, существовавшие ранее подходы к её решению и основные идеи нового алгоритма.