Нові правила прийому до ВНЗ, які діють з 2018 року, не дуже просто написані (сарказм).
Не занурюючись в деталі, схема така:
- Кандидати готують всі документи для вступу (складають ЗНО, додаткові іспити і т.д.). Вступники можуть подати до семи заяв на місця державного та регіонального замовлення в фіксованих (закритих) та відкритих конкурсних пропозиціях не більше, ніж з чотирьох спеціальностей. У кожній заяві зазначають її пріоритетність; при цьому показник пріоритетності 1 (один) означає найвищу пріоритетність. Зазначену вступником пріоритетність заяв не може бути змінено.
- ВНЗ формують квоти і визначають кількість місць, які вони цього року мають заповнити та формують рейтинговий список вступників, який впорядковується:
- за конкурсним балом — від більшого до меншого;
- за пріоритетністю заяви від 1 до останньої;
- за середнім балом додатка до документа про здобутий освітній (освітньо-кваліфікаційний) рівень — від більшого до меншого.
- Списки вступників, рекомендованих до зарахування … перевіряються на предмет достовірності поданих вступниками відомостей та дотримання передбачених цими Умовами вимог ... оприлюднюються шляхом розміщення на інформаційних стендах приймальних комісій та веб-сайті закладу вищої освіти
- Магічний алгоритм розподілу (додаток 6) визначає. хто куди потрапляє.
Можливо, несподівано, але цей алгоритм теж відноситься до теорії ігор, тому в цій статті спробую пояснити, чому саме такий алгоритм обраний і як він працює. Я намагався зробити пояснення максимально простим, тому воно буде довгим і поступовим з прикладами.
Проблема парування
В 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 |
d отримує відмову від D, оскільки прийшов кращий кандидат b.
Третій крок.
Кожен кандидат, який отримав відмову, звертається до наступного ВНЗ у своєму списку. І так продовжується, поки є кандидати з відмовами.
| 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 |
| відмова |
Теорема. Алгоритм Гейла-Шеплі зупиняється за скінченну кількість кроків, його результатом є стабільне парування.
Девід Гейл
Загальна ситуація
В реальній ситуації є не так багато ВНЗ і багато бажаючих кандидатів, кожен з яких хоче поступити в один з декількох ВНЗ. Алгоритм Гейла-Шеплі масштабується і на цей випадок. Власне, його основна частина незмінна:
- Усі кандидати подаються в ВНЗ, яка є їх першим номером. ВНЗ вибирає кількість абітурієнтів, яка відповідає квоті, та відмовляє решті. Поточні кандидати потрапляють у список очікування.
- Кандидати, що отримали відмову, подаються до наступного ВНЗ в їх списку пріоритетів. Вони потрапляють у список з попереднього кроку та сортуються за балами.
- Ситуація повторюється, поки в системі не припиняються відмови. Тобто алгоритм завершується, коли кожен абітурієнт або потрапив у список очікування, або отримав відмову від кожного ВНЗ. у який подавався.
Дві очевидні думки з цього приводу:
- Є сенс заповнювати всі 7 можливих ВНЗ, але відноситись до цього вибору серйозно, бо потрапити можна в кожен з них (особливо, якщо бали середні).
- Пріоритет слід писати реальний, це дасть найкращі шанси. Маніпуляції не дадуть ніякого виграшу.
Приклад.
ВНЗ:
А — квота 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 році Алвіну Роту і Ллойду Шеплі.
Алвін Рот