Алгоритм Гейла-Шеплі: від сінгапурського додатку до українських реєстрів

Уряд Сінгапуру запустив застосунок для знайомств, який зводить пари не за лайками, а за алгоритмом, що в 2012 році приніс Нобелівську премію з економіки. Називається він алгоритмом стабільних шлюбів Гейла-Шеплі, і логіка в нього така, що зраджувати правилам стає невигідно обом сторонам.

Що саме придумали Гейл і Шеплі

Уявіть кімнату, де сто людей шукають пару. У кожного є свій список переваг: кого хотілося б найбільше, кого — якщо більше нікого. Проблема очевидна: якщо просто роздати людей за першими бажаннями, хтось залишиться з тим, кого не хотів, і при першій нагоді втече до кращого варіанта.

Алгоритм працює раундами. На першому кожен робить пропозицію тому, хто стоїть у нього на вершині списку. Той, хто отримує пропозиції, залишає найкращу з них і відмовляє решті — але нікому не каже "так" остаточно. На наступному раунді відхилені йдуть до другого за списком, і так далі. Коли ніхто вже не хоче нікуди переходити, процес зупиняється.

Ключове слово тут — стабільний. Результат влаштований так, що не існує двох людей, які обидва воліли б бути разом, а не з тими, кого їм призначили. Немає пари, яка захотіла б розвалити систему заради себе. Саме це робить рішення довговічним, а не просто формально виконаним.

Чому це не про знайомства

Застосунок у Сінгапурі — лише ефектна вітрина. Насправді алгоритм десятиліттями тихо працює там, де треба зіставити дві множини з протилежними бажаннями. У США за цим принципом розподіляють випускників медичних шкіл по лікарнях-резидентурах. У Нью-Йорку і Бостоні ним розводять школярів по школах.

Логіка завжди однакова: є ті, хто обирає, і є ті, кого обирають, причому в обох є свої ранжовані переваги. І є вимога, щоб результат ніхто не хотів обійти в обхід правил.

Де це болить в Україні

Тепер подивіться на знайомі черги. Запис до садочка і першого класу — класична задача на розподіл, де в батьків є переваги за школами, а в шкіл — обмежена кількість місць і свої критерії пріоритету. Зараз це часто вирішується швидкістю натискання кнопки о восьмій ранку та неформальними домовленостями. Стабільний алгоритм прибирає обидва важелі: місце дістається тому, хто за правилами має на нього більше прав, а не тому, хто першим прорвався.

На Дія.Робота той самий механізм зводив би здобувачів і вакансії так, щоб не лишалося пар "роботодавець хотів би саме цього кандидата, а кандидат — саме цю вакансію, але система розвела їх по гірших варіантах". Для волонтерської логістики — зіставлення тих, хто пропонує допомогу, з конкретними запитами: за навичками, локацією, терміновістю. В IT-командах це розподіл завдань між розробниками з урахуванням того, хто за що хоче братися, а не лише хто вільний.

Вигода не в тому, що алгоритм "справедливіший" в абстрактному сенсі. Вона в тому, що результат неможливо оскаржити аргументом "мене обійшли": за визначенням стабільного розподілу не існує двох учасників, яким разом було б вигідніше домовитися повз систему. Там, де сьогодні працюють знайомства і реакція, працювала б перевірювана процедура.

Є одне обмеження, і його варто назвати прямо. Алгоритм дає перевагу тій стороні, яка робить пропозиції: якщо пропонують садочки, виграють садочки; якщо батьки — батьки. Тому головне політичне рішення — не технічне. Воно в тому, чиї переваги реєстр ставить на перше місце.