Семинар по алгоритмам и структурам данных «Алгоритмы справедливых дележей неделимых предметов»
Юрий Дементьев
ИТМО
10 июня 2025 в 18:10
Докладчик: Юрий Дементьев, ИТМО
Тема: Алгоритмы справедливых дележей неделимых предметов
Аннотация: Справедливое распределение ресурсов между людьми — одна из фундаментальных задач, волнующих человечество с древних времен. На протяжении долгого времени математические исследования этой темы концентрировались преимущественно на моделях с бесконечно делимыми ресурсами. Однако в последние десятилетия значительно возрос интерес к случаям, когда ресурсы являются неделимыми, что характерно для множества реальных сценариев.
Современные работы в этой области исследуют вычислительные аспекты различных формализаций справедливости, таких как максиминная справедливость долей (MMS), отсутствие зависти с точностью до одного предмета (EF1) и отсутствие зависти с точностью до любого предмета (EFX). В докладе будет представлен обзор ключевых результатов в области справедливого распределения неделимых благ с акцентом на случае аддитивных функций полезности и на прогрессе, достигнутом за последние десять лет. Особое внимание будет уделено алгоритмическим методам, существующим границам применимости известных подходов, а также открытым вопросам и перспективным направлениям для дальнейших исследований.
Место проведения: Покровский бульвар, 11, аудитория G114