Нобелівська премія з економіки за 2012 рік була присуджена Ллойду Шеплі і Алвіну Роту за розробку теорії стійких парувань та її застосування до створення ринків. Традиційний економічний аналіз розглядає ринки, в яких ціна балансується попитом-пропозицією. І часто ринок є таким, наприклад, ринок нафти. Але іноді виникають ситуації, коли гроші “не працюють”. Наприклад, навчання у ВНЗ безкоштовне (принаймні бюджетні місця), але потрібно вирішити, хто потрапить у який університет чи інститут. Такі ринки отримали назву matching markets (ринки з паруванням). Будь-який алгоритм розподілу має бути справедливим і стійким до маніпуляцій, бо люди - це агенти з власними інересами. Ці й інші проблеми розв’язуються за допомогою алгоритму Гейла-Шеплі - алгоритму, що виник у 50х роках минулого століття як результат рішення кооперативної гри.

Одним з розвитком цих ідей є задача SPA (students - project assignment). В цій задачі є група студентів, лекторів і набір проектів, які вони можуть менторити. При цьому кожен студент має уподобання на підмножині проектів, кожен лектор - уподобання на підмножині студентів, а проекти та лектори мають обмеження на максимальну (а іноді і мінімальну) кількість студентів. Щоб розв’язати цю задачу використовується проста, але красива модифікація алгоритму Гейла-Шеплі.  Ми познайомимось з цим алгоритмом та доведемо його стабільнсть.

Матеріали та відеозапис будуть доступні на сторінці семінару 16 лютого.