Нові правила прийому до ВНЗ, які діють з 2018 року, не дуже просто написані (сарказм).
Не занурюючись в деталі, схема така:
Можливо, несподівано, але цей алгоритм теж відноситься до теорії ігор, тому в цій статті спробую пояснити, чому саме такий алгоритм обраний і як він працює. Я намагався зробити пояснення максимально простим, тому воно буде довгим і поступовим з прикладами.
Проблема парування
В 1962 році була надрукована стаття з дещо дивною назвою: “Подача документів у коледж та стабільність шлюбу” за авторством Девіда Гейла і Ллойда Шеплі. Як пізніше згадував Гейл, основним мотиватором стала поява в 1960 році в журналі New Yorker публікації про проблеми вступу до Йельського Університету. Бажаючі вступити подавали документи в різні навчальні заклади, і вступна комісія проводила відбір. Проблема полягала в тому, що у приймальної комісії немає можливості зрозуміти, наскільки пріоритетний даний заклад для претендента, а у претендента - оцінити свої шанси у конкуренції з іншими. В результаті виникає базова дилема:
Університет може вибрати рівно стільки кандидатів, скільки він може навчити, але якщо вони пізніше відмовляться (бо пройдуть в більш пріоритетні для них заклади), то доведеться аврально набирати всіх бажаючих або мати недобір. Якщо університет вибере кандидатів з запасом, і всі вони принесуть документи, то буде переповнення.
Уточнення: звичайно, це стосується західних універів, які тримають репутацію, бо від неї залежить конкурс, фінансування від спонсорів та пожертви від майбутніх успішних випускників.
Кандидат має вибирати між потужними універами з конкурсом і ризиком з одного боку та слабкими універами з гарантованим вступом - з іншого. Таким чином, ситуація перетворюється на гру “вгадай, куди поступати”. Нагадаю, що гра виникає, коли визначені гравці, їх стратегії і виграші. Гравцями в даному випадку є абітурієнти і приймальні комісії ВНЗ. Стратегія - куди подавати документи. Виграш - це особиста оцінка якості ВНЗ, у який вдалось вступити відповідно до власного рейтингу.
У ситуації, коли є лише один шанс на вступ (наприклад, якщо законодавчо необхідно подавати оригінал документу про освіту) виникають можливості для:
Врешті-решт, ще є варіант, який я власними вухами почув колись давно в КПІ: “Підем на сварку [зварювання], там 0.33 людини на місце”.
Таким чином, хороша стратегія абітурієнтів: подача документів в декілька ВНЗ (далі він вибирає кращий з тих, у які його взяли). Будемо вважати, що кожен знає сам (або його/її мама), який ВНЗ кращий за інший, тобто визначене відношення кращий-гірший для всіх ВНЗ, у які абітурієнт подає документи.
ВНЗ знаходиться в ще більш складній ситуації - він вибирає зі списку тих, хто йому підходить, але не може гарантувати їх згоду.
Необхідно запропонувати алгоритм, який би гарантував “якісне” парування (далі буде пояснено,у якому розумінні якісне). Саме це й зробили Гейл і Шеплі, цей алгоритм носить їх імена.
Математична постановка задачі наступна:
є множина абітурієнтів a, b, c, …
є множина ВНЗ A, B, C, …
Кожен абітурієнт і ВНЗ розуміє, хто для нього краще або гірше.
Спочатку розглянемо більш просту задачу, яка називається задача про шлюб. Загалом парування, або matching, є важливим і вживаним алгоритмом, що використовується для аукціонів з багатьма лотами, у задачах призначення та інших. Тому шлюб тут використовується у якості ілюстрації складної проблеми. Це спрощення попередньої задачі - ситуація, коли є N ВНЗ і N студентів і кожному ВНЗ потрібен рівно один студент. Щоб уникнути плутанини, будемо і далі використовувати цю термінологію.
Наприклад, для трьох студентів і трьох ВНЗ наступні матриці описують відношення переваги. Одна матриця описує місця пріоритетності ВНЗ за спаданням для кожного абітурієнта.
Уподобання абітурієнтів (кожен стовпець - одна особа)
a | b | c | |
1- А | 1 - B | 1 - B | |
2 - B | 2 - A | 2 - C | |
3 - C | 3 - C | 3 - A |
Друга матриця описує, як ВНЗ оцінюють абітурієнтів.
Уподобання ВНЗ (кожен рядок - один ВНЗ)
A | 1 - b | 2 - a | 3 - c |
B | 1 - a | 2 - c | 3 - b |
C | 1 - c | 2 - b | 3 - a |
Вже тут виникають проблеми, дійсно давайте розглянемо якесь довільне парування:
А --- а (2 х 1)
B --- b (3 х 1)
C --- c (1 х 2)
(у дужках - місце студента для ВНЗ та місце ВНЗ для студента відповідно)
Чим поганий такий варіант? Майже всі отримали перше або друге місце. І що таке взагалі хороше парування?
Визначення. Парування є стабільним, якщо не існує двох учасників, які б могли покращити свої виграші, утворивши нову пару.
Проблема (з запропонованим вище паруванням) в тому, що B і с можуть утворити кращу пару. Дійсно пара B --- с має індекс 2 х 1, тобто В покращує свій показник з 3 до 2, а с з 2 до 1. Можливо, тоді таке парування підійде:
А --- а (2 х 1)
B --- с (2 х 1)
C --- b (2 х 3)
Тут b може запропонувати А утворити нову пару, дійсно пара А --- b має індекс 1 x 2. Обоє покращують свій виграш. Нове парування буде таким:
А --- b (1 х 2)
B --- с (2 х 1)
C --- а (3 х 3)
Тут а запропонує В утворити пару від якої вони виграють. Нарешті парування
А --- b (1 х 2)
B --- а (1 х 2)
C --- с (1 х 2)
є стабільним, оскільки всі ВНЗ отримали свої перші місця і навіть, якщо якийсь з студент захоче покращити свій вибір, він не зможе знайти пари для такого покращення.
Зазначимо, що тут якість парування визначається саме неможливістю “покращення” для будь-якої пари, а не, скажімо, більшістю задоволених або відсотком здійснених мрій абітурієнтів.
Це був надзвичайно простий приклад для шести учасників, що ж буде для сотень? Виникає три очевидних питання:
Ллойд Шеплі
Алгоритм пошуку стабільної системи на прикладі вступу (поки що для ситуації рівної кількості ВНЗ і кандидатів та коли кожен ВНЗ набирає одного). Розглянемо більш складний приклад 4 на 4.
Уподобання кандидатів а, b, c, d.
a | b | c | d | |
А | A | B | D | |
B | D | A | B | |
C | C | C | C | |
D | B | D | A |
Уподобання ВНЗ A, B, C, D.
A | d | c | a | b |
B | b | d | a | c |
C | d | a | b | c |
D | c | b | a | d |
Перший крок. Кожен абітурієнт подає документи у ВНЗ, який стоїть у нього під першим номером. Кожен ВНЗ, який отримав більше однієї пропозиції, вибирає одного найкращого кандидата і відмовляє всім іншим (хто подав заявку до нього у цьому раунді). Кандидати, які не отримали відмови зберігаються у “списку очікування” цього ВНЗ, інші видаляються і не можуть більше подаватись в цей ВНЗ.
A | B | C | D | |
список | a b | c | d | |
відмова | b |
b має нижчий пріоритет для ВНЗ А ніж а, тому b відхиляється. Всі інші потрапляють у списки очікування.
Другий крок.
Кожен кандидат, який отримав відмову, звертається до другого ВНЗ у своєму списку. Кожен ВНЗ, який отримав більше однієї пропозиції, порівнює нового кандидата з існуючим списком очікування та вибирає кращого. Кращий залишається у списку, гірший отримує відмову.
A | B | C | D | |
список | a | c | b d | |
відмова | d |
Третій крок.
Кожен кандидат, який отримав відмову, звертається до наступного ВНЗ у своєму списку. І так продовжується, поки є кандидати з відмовами.
A | B | C | D | |
список | a | c d | b | |
відмова | c |
Четвертий крок.
A | B | C | D | |
список | a c | d | b | |
відмова | a |
П'ятий крок.
A | B | C | D | |
список | с | d a | b | |
відмова | a |
Шостий крок.
A | B | C | D | |
список | c | d | a | b |
відмова |
Теорема. Алгоритм Гейла-Шеплі зупиняється за скінченну кількість кроків, його результатом є стабільне парування.
Девід Гейл
Загальна ситуація
В реальній ситуації є не так багато ВНЗ і багато бажаючих кандидатів, кожен з яких хоче поступити в один з декількох ВНЗ. Алгоритм Гейла-Шеплі масштабується і на цей випадок. Власне, його основна частина незмінна:
Дві очевидні думки з цього приводу:
Приклад.
ВНЗ:
А - квота 3
B - квота 4
C - квота 6
Є 15 абітурієнтів в ці ВНЗ. Уподобання кандидатів наступні (номер - це місце відповідного ВНЗ у списку пріорітетів):
a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | |
A | 1 | 3 | 1 | 1 | 2 | 2 | 3 | 2 | 2 | 3 | 1 | 1 | 2 | 2 | 1 |
B | 2 | 1 | 3 | 2 | 1 | 3 | 2 | 1 | 3 | 1 | 2 | 3 | 1 | 3 | 2 |
C | 3 | 2 | 2 | 3 | 3 | 1 | 1 | 3 | 1 | 2 | 3 | 2 | 3 | 1 | 3 |
Уподобання ВНЗ наступні (номер це місце студента у конкурсі ВНЗ ):
a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | |
A | 1 | 5 | 2 | 4 | 3 | 10 | 6 | 9 | 11 | 7 | 8 | 14 | 12 | 13 | 15 |
B | 1 | 4 | 2 | 3 | 6 | 14 | 5 | 13 | 12 | 11 | 7 | 8 | 9 | 15 | 10 |
C | 5 | 2 | 1 | 14 | 6 | 12 | 13 | 7 | 8 | 9 | 10 | 11 | 15 | 3 | 4 |
Далі будемо помічати зірочкою тих кандидатів, які отримують відмову.
Перший крок.
A --- a c d k l o ______ A --- a c d - k* l* o*
B --- b e h j m __→ ___B --- b e m j - h*
C --- f g i n __________C --- n i f g
ВНЗ відсортовують кандидатів, залишають квоту і решті відмовляють (зірочки).
Другий крок.
A --- a c d h __________A --- a c d - h*
B --- b e m j k o__→ ___ B --- b e k m - o* j*
C --- n i f g l __________C --- n i l f g
Третій крок.
A --- a c d _________A --- a c d
B --- b e k m__→ ___ B --- b e k m
C --- n i l f g h o j ____C --- n o h i j l - f* g*
Четвертий крок
A --- a c d f _________ A --- a c d - f*
B --- b e k m g__→ ___ B --- b g e k - m*
C --- n o h i j l ________ C --- n o h i j l
П’ятий крок.
A --- a c d m ________A --- a c d - m*
B --- b g e k f __→ ___ B --- b g e k - f*
C --- n o h i j l _______C --- n o h i j l
Шостий крок.
A --- a c d ________ A --- a c d
B --- b g e k __→ ___B --- b g e k
C --- n o h i j l m _____C --- n o h i j l - m*
В результаті m і f не потрапляють нікуди в цьому році. Інші отримують місця відповідно до останнього парування.
Оптимальність алгоритму
Виникає природне питання: якщо стабільних систем може бути декілька, то, можливо, вони не однакові. І можна вибрати краще.
Дійсно, стабільна система парування називається оптимальною для абітурієнтів, якщо за нею кожен з них отримує місце не гірше, ніж за будь-якої іншої стабільної системи.
Теорема. Для будь-якої системи уподобань алгоритм Гейла-Шеплі є оптимальним для абітурієнтів.
Виявляється, що це не єдине застосування алгоритму.
Донорство нирок
В 2005-2007 роках Алвін Рот застосував ідею алгоритму Гейла-Шеплі до створення ринку донорства нирок. Справа в тому, що є два типи донорства нирки: звичайне (від людини, яка загинула в катастрофі, наприклад) та живе, коли людина віддає одну свою нирку і живе з іншою. Звичайно, це не те, що люди охоче роблять, але це поширена практика, коли від цього залежить життя близької людини. Проблема полягає в тому, що є два теста: на сумісність крові та сумісність тканин, провал хоча б одного з них ставить хрест на донорстві.
Отже, є люди, які потребують нирку особливого типу і люди, які готові їм віддати свою, але їх тип не співпадає. Теоретично можна спробувати знайти іншу пару, що знаходиться в подібній ситуації, але якщо обидва типи не співпадуть (що дуже малоймовірно), домовитись вони не зможуть.
В 2003 році в усіх Сполучених Штатах було усього 19 операцій від живих американських донорів. Алгоритм Рота використовував складне парування, коли утворювалися ланцюжки донорів і кожен віддавав свою нирку і отримував нирку потрібного типу. Після запуску алгоритму кількість операцій стрімко зростала: 400 за 2012 рік, 5300 операцій за 2017 рік.
Успіх цих алгоритмів був однією з суттєвих причин присудження нобелівської премії з економіки в 2012 році Алвіну Роту і Ллойду Шеплі.
Алвін Рот
Коментарі доступні тільки зареєстрованим користувачам
вхід / реєстрація