Понедельник 06.02. Федор Сандомирский (НИУ ВШЭ, лаб. Теории Игр): "Задачи распределения ресурсов и их алгоритмические свойства"

Понедельник 06.02. Федор Сандомирский (НИУ ВШЭ, лаб. Теории Игр): "Задачи распределения ресурсов и их алгоритмические свойства"

Speaker:

Федор Сандомирский

Date:

Monday, February 6, 2017 - 14:00

Abstract:

Задачи справедливого распределения (fair division) набора благ между агентами, имеющими различные предпочтения, представляют собой классическое направление на стыке математики и экономики. В последнее десятилетие оно переживает революцию в связи с приходом исследователей из Computer Science. Теперь многие механизмы распределения получают свое практическое воплощение в виде онлайн-сервисов таких как SPLIDDIT.ORG, а на первое место выходят вопросы об эффективности реализации. Учет этих вопросов может кардинально изменить понимание того, какие механизмы хороши, а какие нет. Так реализация некоторых механизмов ведет к NP-трудным задачам комбинаторной оптимизации, что делает их малопригодными на практике.

В этом обзорном докладе мы коснемся результатов последних лет и обсудим ряд открытых вопросов: для некоторых постановок неизвестна алгоритмическая сложность построения "хороших" дележей; для других --- даже их существование является лишь гипотезой.