UK 
EnglishТипова
Polski💍 Стабільний розподіл — Алгоритм Гейла-Шеплі
Інтерактивна симуляція стабільного розподілу Гейла-Шеплі. Спостерігайте, як алгоритм відкладеного прийняття поєднує Групу A і Групу B через анімовані раунди пропозицій до стабільного розподілу.
Про Стабільний розподіл — Алгоритм Гейла-Шеплі
Ця симуляція моделює задачу стабільного шлюбу, сформульовану 1962 року математиками Девідом Гейлом і Ллойдом Шеплі у статті «College Admissions and the Stability of Marriage». За наявності N учасників Групи A та N учасників Групи B, кожен з яких має впорядкований список переваг щодо іншої сторони, розподіл вважається «стабільним», якщо не існує пари, яка б воліла одне одного більше за призначених партнерів. Алгоритм відкладеного прийняття будує такий розподіл: пропонувальники послідовно пропонують свій найкращий ще не відхилений варіант, а отримувачі тимчасово утримують найкращу з отриманих пропозицій і відхиляють решту — доки кожен пропонувальник не буде поєднаний.
Понад свою елегантну математику, стабільний розподіл лежить в основі деяких із найбільш значущих алгоритмів сучасного життя: він розподіляє лікарів-резидентів по лікарнях через Національну програму розподілу резидентів, розподіляє учнів по державних школах у таких містах, як Нью-Йорк і Бостон, і живить програми обміну нирками, що знаходять ланцюжки сумісних донорів і пацієнтів. Ця робота принесла Ллойду Шеплі та економісту Елвіну Роту Нобелівську премію з економіки 2012 року «за теорію стабільних розподілів і практику проєктування ринків».
🔬 Що демонструє
Алгоритм відкладеного прийняття Гейла-Шеплі завжди завершується стабільним розподілом: жодна пара не воліла б одне одного більше за своїх поточних партнерів. Анімація показує тимчасові пари (фіолетовим), відмови (червоним, що згасає) та кінцевий стабільний результат (зеленим).
🎮 Як користуватися
Змініть кількість пар (N) і натисніть «Нові випадкові переваги», щоб згенерувати нові списки переваг. Натисніть «Крок», щоб пройти один раунд пропозицій за раз, або «Автозапуск», щоб побачити весь процес аж до стабільного розподілу з обраною швидкістю.
💡 Чи знали ви?
Саме цей алгоритм щороку розподіляє понад 40 000 лікарів-резидентів по лікарнях США через Національну програму розподілу резидентів, а його варіанти використовуються для розподілу учнів по школах у таких містах, як Нью-Йорк і Бостон.
Поширені запитання
Що таке стабільний розподіл?
Стабільний розподіл — це поєднання двох рівних за розміром груп, кожен учасник яких має впорядкований список переваг щодо іншої сторони, за якого жодні двоє непоєднаних учасників не воліли б бути в парі одне з одним більше, ніж зі своїми поточними партнерами. Така нестабільна пара називається «блокувальною парою». Теорема Гейла-Шеплі доводить, що стабільний розподіл завжди існує для будь-якого набору списків переваг і може бути знайдений алгоритмом відкладеного прийняття, незалежно від структури переваг.
Як покроково працює алгоритм відкладеного прийняття?
Кожен непоєднаний учасник групи, що пропонує (Групи A), пропонує найвищому за рейтингом учаснику Групи B, якому він ще не пропонував. Кожен учасник Групи B порівнює всі пропозиції, отримані за цей раунд (плюс партнера, якого він наразі утримує), і тимчасово приймає найкращу, відхиляючи решту. Відхилені пропонувальники переходять до наступного варіанту в наступному раунді. Це триває, доки кожен пропонувальник не буде поєднаний — ніхто не приймається остаточно до самого кінця, звідси й назва «відкладене» прийняття.
Як користуватися цією симуляцією?
Оберіть кількість пар повзунком «Пари (N)» і натисніть «Нові випадкові переваги», щоб згенерувати нові випадкові списки переваг для обох груп. Натисніть «Крок», щоб пройти рівно один раунд пропозицій, спостерігаючи, як фіолетові лінії утворюють тимчасові пари, а червоні пунктирні лінії блимають при відмовах, або натисніть «Автозапуск», щоб алгоритм працював автоматично з обраною швидкістю до досягнення стабільного розподілу (показаного зеленим).
Які реальні системи насправді використовують цей алгоритм?
Найвідоміше застосування — Національна програма розподілу резидентів, яка з 1950-х років розподілила понад мільйон нових лікарів по програмах ординатури в лікарнях США. Варіанти алгоритму також працюють у системах вибору шкіл у Нью-Йорку, Бостоні та інших округах, а програми обміну нирками використовують споріднену теорію розподілу для пошуку довгих ланцюжків сумісних донорів, що рятує тисячі життів.
Який зв'язок із Нобелівською премією 2012 року?
Ллойд Шеплі, який розробив алгоритм разом із Девідом Гейлом у 1962 році, та економіст Елвін Рот, який пізніше застосував його для проєктування реальних ринків, зокрема обміну нирками та вибору шкіл, спільно отримали Нобелівську премію з економіки 2012 року «за теорію стабільних розподілів і практику проєктування ринків».
Чому результат називають «оптимальним для пропонувальника»?
Коли пропонує Група A, отриманий стабільний розподіл є доведено найкращим можливим стабільним результатом для кожного учасника Групи A одночасно — жоден інший стабільний розподіл не міг би дати жодному пропонувальнику партнера, якого він волів би більше. Водночас це найгірший стабільний результат для кожного учасника Групи B. Те, яка сторона пропонує, тому має реальні розподільчі наслідки, хоча кожен стабільний розподіл є «справедливим» у сенсі відсутності блокувальних пар.
Чи є відкладене прийняття стратегічно стійким?
Так, для сторони, що пропонує: для кожного учасника Групи A подання правдивого списку переваг є домінантною стратегією, оскільки жодне стратегічне спотворення не може дати кращого результату, ніж чесність. Однак ця гарантія не поширюється на сторону, що приймає (Групу B) — у деяких випадках отримувач теоретично міг би отримати кращого партнера, стратегічно відхиливши пропозицію, яку прийняв би за правдивих переваг, хоча це вимагає детального знання переваг усіх інших, що рідко доступне на практиці.
Що відбувається за нерівних розмірів груп або переваг із зв'язками?
Коли Група A і Група B мають різний розмір, алгоритм усе одно дає стабільний розподіл, але у більшій групі неминуче залишаються непоєднані учасники. Коли учасники мають зв'язки у списках переваг (байдужість між двома чи більше варіантами), класична гарантія стабільності може послаблюватися, і дослідники розробили кілька варіантів розв'язання зв'язків — сильну, слабку та супер-стабільність — кожен із власними властивостями існування та складності, що є активною темою досліджень в алгоритмічній теорії ігор.