City: Санкт-Петербург Новосибирск Казань Language: Русский English

Fair division protocols
Санкт-Петербург / spring 2018, посмотреть все семестры

Enroll in the course to get notifications and to be able to submit home assignments.
Register to enroll now Login

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

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

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

Date and time Class|Name Venue|short Materials
17 February
17:15–18:45
Лекция 1, lecture ПОМИ РАН No
17 February
19:00–20:30
Лекция 2, lecture ПОМИ РАН No
18 February
11:15–12:45
Лекция 3, lecture ПОМИ РАН No
18 February
13:00–14:30
Лекция 4, lecture ПОМИ РАН No