Город: Санкт-Петербург Казань Язык: Русский English

Протоколы справедливого дележа
Санкт-Петербург / весна 2018, посмотреть все семестры

Запишитесь на курс, чтобы получать уведомления и иметь возможность сдавать домашние задания. Для записи требуется регистрация на сайте.
Перейти к регистрации Войти

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

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

Дата и время Название Место Материалы
17 февраля
17:15–18:45
Лекция 1, лекция ПОМИ РАН Нет
17 февраля
19:00–20:30
Лекция 2, лекция ПОМИ РАН Нет
18 февраля
11:15–12:45
Лекция 3, лекция ПОМИ РАН Нет
18 февраля
13:00–14:30
Лекция 4, лекция ПОМИ РАН Нет