Стабільне Зіставлення: Алгоритм Гале-Шаплі

Задача: не дозволяємо блукати очима

Розділіть на дві рівні групи — скажімо, n кандидатів і n лікарень, кожна з яких має ранжований список уподобань щодо іншої сторони. Зіставлення пари кожного члена однієї групи з одним членом іншої групи. Це стабільне, якщо не існує блокуючої пари: дві людини, які не зіставлені одна з одною, але обидві б із переваги бути зіставленими один з одним, а не з їх поточними партнерами. Якщо існує блокуюча пара, зіставлення крихке — ці двоє мають усі стимули для дезертирства разом, незалежно від офіційного призначення. Девід Гейл і Ллойд Шэплі довели в 1962 році, що стабільне зіставлення завжди існує для будь-якого набору уподобань, і дали конструктивний алгоритм для його знаходження — роботу, розширену Альвіном Ротом для реального дизайну ринку, яка принесла Шэплі та Рота Нобелівську премію пам'яті 2012 року з економіки.

Відтерміноване прийняття, крок за кроком

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

while some proposer p is free and has not proposed to everyone: r = p's most-preferred receiver not yet proposed to p proposes to r if r is free: r tentatively accepts p elif r prefers p to its current tentative match p': r rejects p', tentatively accepts p // p becomes free again else: r rejects p // p tries its next choice return the tentative matches — now final and stable The word deferred is the key idea: a receiver's acceptance is always provisional until the very end, so a proposer can be "bumped" by a better offer at any point, but a receiver never permanently commits until no better proposal can possibly arrive. This is exactly why the process cannot cycle forever — every rejection permanently removes one proposer-receiver pair from consideration, and there are only n² such pairs, so the algorithm terminates in at most n² proposals.

while some proposer p is free and has not proposed to everyone:
    r = p's most-preferred receiver not yet proposed to
    p proposes to r
    if r is free:
        r tentatively accepts p
    elif r prefers p to its current tentative match p':
        r rejects p', tentatively accepts p     // p' becomes free again
    else:
        r rejects p                              // p tries its next choice
return the tentative matches — now final and stable

Чому результат не має блокуючих пар

Припустимо, кандидат A з'єднується з лікарнею H, але A насправді віддає перевагу іншій лікарні H′ більше. Алгоритм гарантує, що A запропоновано до H′ в якийсь момент до того, як він дійде до H (запропонування завжди відбувається вниз списку в порядку), і H′ відхиляє A — це трапляється лише тоді, коли H′ вже (тимчасово або остаточно) тримає когось, хто йому більше подобається, ніж A. Оскільки приймач може покращувати свою фінальну відповідність з часом, H′ все ще віддає перевагу своїй фінальній відповіді над A в кінці. Таким чином, A і H′ не можуть сформувати блокуючу пару: будь-хто з двох незадоволено оцінює потенційну перестановку блокує її. Застосування цього аргументу до кожного кандидата доводить, що остаточне зіставлення є стабільним.

Пропонент-оптимальний, приймач-песимімальний

Алгоритм не є симетричним, і ця асиметрія має реальні наслідки. Сторона, яка пропонує, закінчує з найкращим партнером, який вона могла б отримати в будь-якому стабільному відповіді, тоді як сторона, яка приймає, закінчує з найгіршим стабільним партнером. Змініть, хто пропонує, і ви зазвичай отримаєте іншу — також стабільну — відповідність, кращу для нових пропозиціонерів і гірше для нових отримувачів. Це не примітка: коли програма національного відповідного призначення США переробила свій алгоритм у 1990-х роках завдяки допомозі Рота, прийняття медичними студентами (а не лікарнями) як пропонуючою стороною було свідомим вибором для покращення результатів для заявників.

Часті запитання

Спробуйте наживо

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