Задача о справедливом дележе возникает в самых разных ситуациях: при разделе наследства, имущества разводящихся супругов, активов обанкротившейся компании между кредиторами, в международных переговорах, при распределении машинного времени между пользователями или задачами и т.д. Трудность заключается в том, что разные стороны процесса по-разному ценят разные компоненты разделяемого блага. Математически задача ставится так: имеется некоторое измеримое пространство (пирог) и N различных мер на нём (вкусы делящих). Требуется разбить пирог на N частей и распределить их в некотором смысле справедливо. Есть два основных понятия справедливости: пропорциональность, когда каждый из участников считает, что ему досталось хотя бы 1/N от пирога, и отсутствие зависти, когда каждый считает, что его кусок самый лучший. Теоремы о неподвижных точках гарантируют существование дележа без зависти при любых вкусах, но возникает алгоритмический вопрос о способе выявления такого дележа.

На первых двух лекциях мы изучим классическую теорию: строго поставим задачу (как можно вообще говорить об алгоритмах, получающих на вход несколько произвольных мер?), проанализируем различные протоколы пропорционального дележа и познакомимся с протоколами дележа без зависти на 3 или 4 части. На вторых двух лекциях будет дан обзор недавнего прорыва - протокола Азиза-Маккензи дележа без зависти на N частей, для которого есть верхняя граница на число шагов. К сожалению, эта верхняя граница очень быстро растёт (асимптотика N^N^N^N^N^N, башня из 6 экспонент!), так что остаётся широкий простор для дальнейшей оптимизации.

Видео первых лекций: https://www.youtube.com/playlist?list=PLqb0YjgGLWliqb3WVGJAM3wVQ9O7gIzCm