• 5 років тому
  • Наука
  • 5 695
  • 426
  • 187
  • 7

Нові правила прийому до ВНЗ, які діють з 2018 року, не дуже просто написані (сарказм).

Не занурюючись в деталі, схема така:

  1. Кандидати готують всі документи для вступу (складають ЗНО, додаткові іспити і т.д.). Вступники можуть подати до семи заяв на місця державного та регіонального замовлення в фіксованих (закритих) та відкритих конкурсних пропозиціях не більше, ніж з чотирьох спеціальностей. У кожній заяві зазначають її пріоритетність; при цьому показник пріоритетності 1 (один) означає найвищу пріоритетність. Зазначену вступником пріоритетність заяв не може бути змінено.
  2. ВНЗ формують квоти і визначають кількість місць, які вони цього року мають заповнити та формують рейтинговий список вступників, який впорядковується:
    • за конкурсним балом - від більшого до меншого;
    • за пріоритетністю заяви від 1 до останньої;
    • за середнім балом додатка до документа про здобутий освітній (освітньо-кваліфікаційний) рівень - від більшого до меншого.
  3. Списки вступників, рекомендованих до зарахування … перевіряються на предмет достовірності поданих вступниками відомостей та дотримання передбачених цими Умовами вимог ... оприлюднюються шляхом розміщення на інформаційних стендах приймальних комісій та веб-сайті закладу вищої освіти
  4. Магічний алгоритм розподілу (додаток 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

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


ABCD
списокa bcd
відмоваb

b має нижчий пріоритет для ВНЗ А ніж а, тому b відхиляється. Всі інші потрапляють у списки очікування.

Другий крок.

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

ABCD
списокacb d
відмоваd
d отримує відмову від D, оскільки прийшов кращий кандидат b.


Третій крок.

Кожен кандидат, який отримав відмову, звертається до наступного ВНЗ у своєму списку. І так продовжується, поки є кандидати з відмовами.

ABCD
списокac db
відмова
c

Четвертий крок.

ABCD
списокa cdb
відмоваa

П'ятий крок.

ABCD
списоксd ab
відмова
a

Шостий крок.

ABCD
списокcdab
відмова

Теорема. Алгоритм Гейла-Шеплі зупиняється за скінченну кількість кроків, його результатом є стабільне парування.


Девід Гейл

Загальна ситуація

В реальній ситуації є не так багато ВНЗ і багато бажаючих кандидатів, кожен з яких хоче поступити в один з декількох ВНЗ. Алгоритм Гейла-Шеплі масштабується і на цей випадок. Власне, його основна частина незмінна:

  1. Усі кандидати подаються в ВНЗ, яка є їх першим номером. ВНЗ вибирає кількість абітурієнтів, яка відповідає квоті, та відмовляє решті. Поточні кандидати потрапляють у список очікування.
  2. Кандидати, що отримали відмову, подаються до наступного ВНЗ в їх списку пріоритетів. Вони потрапляють у список з попереднього кроку та сортуються за балами.
  3. Ситуація повторюється, поки в системі не припиняються відмови. Тобто алгоритм завершується, коли кожен абітурієнт або потрапив у список очікування, або отримав відмову від кожного ВНЗ. у який подавався.

Дві очевидні думки з цього приводу:

  1. Є сенс заповнювати всі 7 можливих ВНЗ, але відноситись до цього вибору серйозно, бо потрапити можна в кожен з них (особливо, якщо бали середні).
  2. Пріоритет слід писати реальний, це дасть найкращі шанси. Маніпуляції не дадуть ніякого виграшу.

Приклад.

ВНЗ:

А - квота 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 році Алвіну Роту і Ллойду Шеплі.


Алвін Рот

olexii.ignatenko
Олексій Ігнатенко

Коментарі доступні тільки зареєстрованим користувачам

вхід / реєстрація

Рекомендації