Алгоритми пошуку паросполучень для задачі вступу до навчальних закладів

Представлені алгоритми пошуку стабільних паросполучень для двох класів учасників, кожний з яких має рейтинг іншого класу.

Saved in:

Bibliographic Details
Date:	2015
Main Authors:	Горбачук, В.М., Шулинок, Г.О.
Format:	Article
Language:	Ukrainian
Published:	Інститут кібернетики ім. В.М. Глушкова НАН України 2015
Series:	Теорія оптимальних рішень
Online Access:	https://nasplib.isofts.kiev.ua/handle/123456789/112409
Tags:	Add Tag No Tags, Be the first to tag this record!
Journal Title:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Cite this:	Алгоритми пошуку паросполучень для задачі вступу до навчальних закладів / В.М. Горбачук, Г.О. Шулинок // Теорія оптимальних рішень: Зб. наук. пр. — 2015. — № 2015. — № 2015. — № 2015. — С. 126-133. — Бібліогр.: 21 назв. — укр.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-112409
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-1124092025-02-23T20:20:59Z Алгоритми пошуку паросполучень для задачі вступу до навчальних закладів Алгоритмы поиска паросочетаний для задачи поступления в учебные заведения The search algorithms of matching for a college admission problem Горбачук, В.М. Шулинок, Г.О. Представлені алгоритми пошуку стабільних паросполучень для двох класів учасників, кожний з яких має рейтинг іншого класу. Представлены алгоритмы поиска стабильных паросочетаний для двух классов участников, каждый из которых имеет рейтинг другого класса. The algorithms of search stable matching for two classes of agents where every agent has ranking for another class. 2015 Article Алгоритми пошуку паросполучень для задачі вступу до навчальних закладів / В.М. Горбачук, Г.О. Шулинок // Теорія оптимальних рішень: Зб. наук. пр. — 2015. — № 2015. — № 2015. — № 2015. — С. 126-133. — Бібліогр.: 21 назв. — укр. XXXX-0013 https://nasplib.isofts.kiev.ua/handle/123456789/112409 519.8 uk Теорія оптимальних рішень application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Ukrainian
description	Представлені алгоритми пошуку стабільних паросполучень для двох класів учасників, кожний з яких має рейтинг іншого класу.
format	Article
author	Горбачук, В.М. Шулинок, Г.О.
spellingShingle	Горбачук, В.М. Шулинок, Г.О. Алгоритми пошуку паросполучень для задачі вступу до навчальних закладів Теорія оптимальних рішень
author_facet	Горбачук, В.М. Шулинок, Г.О.
author_sort	Горбачук, В.М.
title	Алгоритми пошуку паросполучень для задачі вступу до навчальних закладів
title_short	Алгоритми пошуку паросполучень для задачі вступу до навчальних закладів
title_full	Алгоритми пошуку паросполучень для задачі вступу до навчальних закладів
title_fullStr	Алгоритми пошуку паросполучень для задачі вступу до навчальних закладів
title_full_unstemmed	Алгоритми пошуку паросполучень для задачі вступу до навчальних закладів
title_sort	алгоритми пошуку паросполучень для задачі вступу до навчальних закладів
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2015
url	https://nasplib.isofts.kiev.ua/handle/123456789/112409
citation_txt	Алгоритми пошуку паросполучень для задачі вступу до навчальних закладів / В.М. Горбачук, Г.О. Шулинок // Теорія оптимальних рішень: Зб. наук. пр. — 2015. — № 2015. — № 2015. — № 2015. — С. 126-133. — Бібліогр.: 21 назв. — укр.
series	Теорія оптимальних рішень
work_keys_str_mv	AT gorbačukvm algoritmipošukuparospolučenʹdlâzadačívstupudonavčalʹnihzakladív AT šulinokgo algoritmipošukuparospolučenʹdlâzadačívstupudonavčalʹnihzakladív AT gorbačukvm algoritmypoiskaparosočetanijdlâzadačipostupleniâvučebnyezavedeniâ AT šulinokgo algoritmypoiskaparosočetanijdlâzadačipostupleniâvučebnyezavedeniâ AT gorbačukvm thesearchalgorithmsofmatchingforacollegeadmissionproblem AT šulinokgo thesearchalgorithmsofmatchingforacollegeadmissionproblem
first_indexed	2025-11-25T01:13:27Z
last_indexed	2025-11-25T01:13:27Z
_version_	1849722885069864960
fulltext	126 Теорія оптимальних рішень. 2015 ТЕОРІЯ ОПТИМАЛЬНИХ РІШЕНЬ Представлені алгоритми пошуку стабільних паросполучень для двох класів учасників, кожний з яких має рейтинг іншого класу.  В.М. Горбачук, Г.О. Шулінок, 2015 УДК 519.8 В.М. ГОРБАЧУК, Г.О. ШУЛІНОК АЛГОРИТМИ ПОШУКУ ПАРОСПОЛУЧЕНЬ ДЛЯ ЗАДАЧІ ВСТУПУ ДО НАВЧАЛЬНИХ ЗАКЛАДІВ Вступ. Виходячи з епохальної статті [1] (один з її авторів – Нобелівський лауреат 2012 р.), теоретичні моделі надають важливе і практично цінне розуміння стратегічної структури ринків паросполучень і розкрива- ють істотні зв’язки між різними економічни- ми задачами. Хоча література просунулася далеко за межі відомої моделі [1] ринку мо- ногамних шлюбів, ідеї тієї моделі залиша- ються центральними в літературі. Головним елементом теоретичних моделей паросполу- чень є поняття кооперативного рішення по- парної стабільності: паросполучення аген-тів може зберігатися на ринку корисливих агентів тоді й тільки тоді, коли не існує двох несполучених агентів, кожний з яких бажав би сформувати їхнє партнерство. Експериме- нтальні свідчення [2] (автор роботи [2] – Но- белівський лауреат 2012 р.) говорять, що стабільність може бути ключовим визначни- ком довговічності й успіху ринкових механі- змів. Важливим практичним питанням є те, як слід проектувати ринкові правила для то- го, щоб досягати стабільних результатів [3]. Для одного класу моделей паросполучень проста й зрозуміла процедура, яку називають алгоритмом відтермінованого прийняття (deferred acceptance algorithm, DAA) [4], завжди знаходить стабільні паросполучення. При вступі в університети України у 2015 р. кожний абітурієнт вперше викори- стає пріоритетність – показник, виражений цифрами від 1 до 15, який вступник осо- бисто присвоює своїм заявам, де 1 є показ- ником найбільшої пріоритетності заяви [5]. АЛГОРИТМИ ПОШУКУ ПАРОСПОЛУЧЕНЬ ДЛЯ ЗАДАЧІ ВСТУПУ ... Теорія оптимальних рішень. 2015 127 Пріоритетність, визначена вступником у заяві про участь у конкурсі, не може бути змінена протягом вступної кампанії. Аналіз можна розпочати з класу ринків двостороннього паросполучення, в яких лише одна сторона ринку (університети чи школи) може сполучатися з двома і більше партнерами [6]. Однак теорія таких ринків виключає практичне застосування з погляду добробуту: наприклад, на ринках праці пошук працівни- ками кількох робіт не є незвичайним. На багатьох ринках паросполучень посе- редники сприяють обміну думками чи формуванню партнерства між агентами, тобто ці ринки перестають бути двосторонніми. Була запропонована модель ланцюга постачання [7], що враховує вищезазначені особливості [8]. У цій моделі агенти розташовані на екзогенно заданій вертикально впорядкова- ній мережі (направленому графі зв’язків між агентами без направлених циклів), не виявляючи переваг щодо множин комерційних взаємозв’язків або контрактів з їхніми сусідами. Було показано, що узагальнена попарна стабільність (ланцюгова стабільність) існує для природного кола переваг і може відігравати важливу роль у поширенні теорії паросполучень на двосторонні ринки пароспо- лучень. На відміну від попарних стабільних паросполучень у двосторонніх ви- щерозглянутих моделях, ланцюгові стабільні розподіли можуть залежати від координованих відхилень і не бути ефективними, що ставить під питання коопе- ративні засади поняття ланцюгової стабільності і заважає поширенню теорії двосторонніх паросполучень. Можна охарактеризувати найбільший клас моде- лей ланцюгів постачання, в яких ланцюгові стабільні розподіли не залежать від будь-яких коаліційних відхилень і є ефективними. Характеризація основана на властивостях екзогенно заданої структури мережі, в якій агенти взаємодіють, за умови виключення певних видів комерційних циклів. Використання ланцюгової стабільності без обмежень на переваги є зручним: якщо мінімальні вимоги стабільності можна узгодити з ефективністю, то ланцюгові стабільні розподіли є ефективними; якщо ланцюгові стабільні розподіли залежать від деяких ко- аліційних відхилень, то не існує розподілу, що не залежить від усіх коаліційних відхилень. Можна дослідити взаємозв’язок між поняттям ланцюгової стабіль- ності та класичним поняттям (кооперативного) рішення – ядром, а також оха- рактеризувати найбільший клас моделей ланцюгів постачання, для яких ці по- няття дають однакові наслідки. Приклади показують, що цей клас строго мен- ший, ніж клас, в якому ланцюгові стабільні розподіли є ефективними і незалеж- ними від будь-яких коаліційних відхилень. Таке кооперативне поняття допов- нюватиме подальші дослідження некооперативної реалізації ланцюгових стабільних розподілів. Для ознайомлення з базовою формальною мовою і термінологією теорії (двостороннього) паросполучення розглянемо класичну задачу вступу до коледжів з чутливими перевагами [1], де дві скінченні множини студентів I В.М. ГОРБАЧУК, Г.О. ШУЛІНОК Теорія оптимальних рішень. 2015 128 та коледжів (colleges) C мають сполучатися одна з одною. Кожний абітурієнт (потенційний студент) бажає отримати місце в одному з коледжів, а кожний ко- ледж Cc має фіксовану верхню межу cq на максимальне число студентів, яке він може прийняти. Студенти мають переваги щодо наявних коледжів, а також можливість не відвідувати коледж. Позначимо IiiI RR  )( профіль строгих переваг студентів. Нехай для кожного студента Ii бінарне відношення (relation) iR є повним, рефлексивним, транзитивним, антисиметричним на }{iC . Коледжі мають переваги щодо вступу класів студентів. Позначимо CccC RR  )( профіль строгих переваг коледжів. Нехай для кожного коледжу Cc бінарне відношення cR є повним, рефлексивним, транзитивним, антиси- метричним на }{cI  . Припустимо, що переваги коледжів щодо груп студентів є чутливими до рейтингів окремих студентів [9]. Позначимо Cccq )( вектор місткості коледжів. Те, що студент i надає слабку перевагу коледжу c щодо коледжу ,c позначимо як ;iс R c якщо при цьому ,c c то студент i надає строгу перевагу (preference) коледжу c щодо коледжу ,c що позначимо як .iс P c Те, що студент i надає строгу перевагу коледжу c щодо неотримання місця в якомусь коледжі взагалі (коледж c є прийнятним для студента i ), позначимо як .iс P i Запис ki ccP ,,: 1  означає, що n i mc Pc при ,n m k  а коледжі kcc ,,1  є прийнятними для студента i . Позначення переваг коледжів аналогічні позначенням переваг студентів. Коледж c має відношення строгої переваги cP щодо окремих студентів (і можливості незаповнення місця), а також строгий рейтинг # cP на підмножинах ,I чутливий до рейтингу cP окремих студентів [9]: ( IJ  ; JIji \,  )  (( }{(}{ # jJPiJ c   jPi c )  ( JPiJ c #}{   ).ci P c Оскільки може бути кілька переваг щодо груп студентів, чутливих до того само- го рейтингу окремих студентів, то беремо до уваги останній. Паросполучення – це призначення студентів до коледжів, яке задовольняє обмеженням на місткості коледжів. Формально паросполучення є таким відоб- раженням  множини CI  в саму себе, що: ( ) { }i C i   ;i I  ( ) ,c I  \| ( ) \| cc q  ;c C  ( )i c  ( ) .i c  Якщо ( ) ,i i  то студент i є не- призначеним за паросполученням . У моделях паросполучень з екстерналіями [10, 11] припускають, що агенти дбають лише про своїх власних партнерів у паросполученні, а тому їхні переваги щодо паросполучень кон- АЛГОРИТМИ ПОШУКУ ПАРОСПОЛУЧЕНЬ ДЛЯ ЗАДАЧІ ВСТУПУ ... Теорія оптимальних рішень. 2015 129 груентні їхнім перевагам щодо потенційних партнерів. При фіксованих ,I C , Cccq )( задачу вступу до коледжів з чутливими перевагами задає профіль ),( CI RRR  . Головна мета теорії паросполучень – передбачити, які відбуватимуться па- росполучення, коли егоїстичні агенти формують партнерства. Для задачі R вступу до коледжів паросполучення є (попарно) стабільним [1], якщо: ( ) ii R i Ii (немає студента, який сполучається з неприйнятним коледжем); cPi c ( ),i c  Cc (немає коледжу, що відхиляє призначеного студента); не існує такої пари ( , ),i c що ( )ic P i  (( jPi c для деякого ( )j c )   ( cPi c  \| ( ) \| cc q  )) (немає пари ( , ),i c яка блокує паросполучення  ). Коли паросполучення не є стабільним, то агенти, переслідуючи свої мотиви, блокують його, формуючи нові партнерства. Зазначимо, що стабільність є поняттям кооперативного рішення, якого певним чином досягає ринок. Для об- ласті чутливих переваг стабільне паросполучення завжди існує, а попарна стабільність рівносильна стабільності ядра [2], тобто немає групи агентів, які блокують попарно стабільне паросполучення. Точніше, множина попарно стабільних паросполучень – це ядро, визначене слабким домінуванням. Парос- получення є ядром, коли немає групи агентів, які можуть отримати паросполу- чення, всі учасники якого надають йому слабку перевагу, причому принаймні один агент надає йому строгу перевагу, формуючи партнерства лише в межах групи. Стабільне паросполучення є ефективним відносно переваг студентів і ко- леджів. Два стабільних паросполучення в основі теорії паросполучень можна зайти двома варіантами DAA [1], на які спирається теорія двосторонніх пароcполучень [4]. Варіант DAA з пропозиціями студентів (student proposing deferred acceptance algorithm, SDA) для даного R складається з таких кроків: 1) на кроці 1 кожний студент подає документи до прийнятного для себе коледжу зі своєю найвищою перевагою; кожний коледж c ставить cq прийнят- них для себе студентів зі своєю найвищою перевагою у свій список очікування, а решту студентів відхиляє; t) на кроці t абітурієнти, які були відхилені на кроці ( 1t ), подають документи до прийнятного для себе коледжу зі своєю наступ- ною найвищою перевагою; кожний коледж c ставить cq прийнятних для себе студентів, з нових абітурієнтів і списку очікування, зі своєю найвищою перева- гою у свій новий список очікування, а решту студентів відхиляє. SDA завершує роботу, коли всі несполучені студенти запропонували всі прийнятні коледжі. Оскільки призначення визначаються за кілька кроків, то процедуру називать відтермінованим прийняттям. Для даної задачі R позна- чимо )(Rf I паросполучення, вибране SDA. Паросполучення )(Rf I є стабіль- ним паросполученням, якому одностайно надають найбільшу перевагу студенти, В.М. ГОРБАЧУК, Г.О. ШУЛІНОК Теорія оптимальних рішень. 2015 130 але водночас є стабільним паросполученням, якому одностайно надають най- меншу перевагу коледжі [1]: якщо ~ – будь-яке стабільне паросполучення для задачі R , то )(~)( iRRf i I i  Ii та )()(~ # RfRc I cc Cc . При цьому будь- яке чутливе розширення CR дає однаковий рейтинг стабільних паросполучень [12]. Для даного R варіант DAA з пропозиціями коледжів (college proposing de- ferred acceptance algorithm, CDA) міняє ролі студентів і коледжів: 1) на кроці 1 кожний коледж c пропонує вступ для cq прийнятних для себе студентів зі своєю найвищою перевагою; кожний студент тимчасово тримається своєї пропозиції зі своєю найвищою перевагою і відхиляє всі інші пропозиції; t) на кроці t кожний коледж c , який мав k своїх відхилених пропозицій на кроці )1( t , пропонує вступ для )( kqc  прийнятних для себе студентів зі своєю найвищою перевагою у свій список очікування, які не відхилили при- наймні одну зі своїх пропозицій на попередніх кроках; кожний студент i тимча- сово тримається своєї пропозиції зі своєю найвищою перевагою серед тих, яких він тримався наприкінці кроку )1( t , і тих, які він отримує на кроці t . CDA завершує роботу, коли всі коледжі з незаповненими місцями запропо- нували вступ усім прийнятним студентам. Отже, призначення визначаються за декілька кроків. Позначимо )(Rf C паросполучення, вибране CDA для задачі R . Це паросполучення має діаметрально протилежні властивості до )(Rf I у тому сенсі, що )(Rf C є стабільним паросполученням для R , найкращим для коледжів і найгіршим для студентів. Важлива гілка літератури паросполучень стосується проектування цен- тралізованої розрахункової палати для ринків паросполучень. Інституцію цен- тралізованого паросполучення можна вважати (детерміністським) механізмом паросполучення, який збирає переваги від агентів для визначення паросполу- чень. Механізм паросполучення – це відображення ,f яке пов’язує паросполу- чення з кожною задачею .R Зазначимо, що обмежуємося механіз-мами, які ви- являють лише рейтинг окремих студентів від коледжів. Оскільки множина стабільних паросполучень залежить тільки від цього рейтингу, то таке обмежен- ня не впливає на стабільні механізми з чутливими перевагами. Для даної задачі R позначимо )(Rfi коледж, призначений студенту i відображен-ням f (якщо такий коледж є). Аналогічно позначимо )(Rfc множину студентів, призначених коледжу .c Механізм паросполучення є стабільним, якщо він відбирає стабільне паросполучення для кожної задачі :R If – опти- мальний для студентів стабільний механізм паросполучення (student optimal sta- ble matching mechanism, SOSM), а Cf – оптимальний для коледжів стабільний механізм паросполучення (college optimal stable matching mechanism, COSM). АЛГОРИТМИ ПОШУКУ ПАРОСПОЛУЧЕНЬ ДЛЯ ЗАДАЧІ ВСТУПУ ... Теорія оптимальних рішень. 2015 131 Оскільки переваги щодо потенційних партнерів типово є приватною інфор- мацією, то механізм паросполучення має забезпечувати учасників правильними стимулами до розкриття їхньої приватної інформації. В ідеалі в найкращих інте- ресах учасника має бути правдиве подання його переваг, незалежно від його очікувань стосовно поведінки інших учасників. Механізм є стратегічно стійким, якщо немає задачі ,R де якийсь студент або коледж може виграти від неправдивого подання своїх переваг. Формально це означає, що R ),()( iiiii RRfRRf   Ii , iR , а також ),()( # ccccc RRfRRf   ,c C  .cR Проте стабільний механізм не може завжди забезпечувати всіх учасників стиму- лами домінантної стратегії для правдивого розкриття їхніх переваг [13]. Для за- гального класу задач паросполучень, що включають модель шлюбу як окремий випадок, стратегічно стійкий і стабільний механізм паросполучення існує тоді й тільки тоді, коли множина стабільних паросполучень є синглтоном [14]. До- сліджено слабші поняття сумісності стимулів, а також втілюваність рівноваг Неша у під-розв’язках стабільного правила [15 – 17]. Розроблено два простих послідовних механізми, що втілюють множину стабільних паросполучень у дос- коналій рівновазі підігор [18]. Однак у деяких застосуваннях здатності неправ- дивого подання своїх переваг не є симетричними між двома ринковими сторо- нами. Наприклад, коледжі часто спираються у своїх рішеннях вступу на пе- ревірювані характеристики студентів, скажімо, результати у стандартизованих тестах, а тому мають незначні можливості для стратегічної маніпуляції після оголошення критеріїв вступу. SOSM If є стратегічно стійким для студентів [13, 19], тобто R ),()( ii I i I i RRfRRf   ,i I  iR . Показано, що SOSM – єдиний стабільний механізм, який є стратегічно стійким для студентів [20]. Аналогічного результату немає для коледжів [9]: іноді для коледжів буває вигідним подавати до COSM неправильні рейтинги окремих студентів, коли ко- леджі мають право вказувати лише свої рейтинги окремих студентів або повніс- тю свої переваги на підмножинах студентів. Контрприклад [9] показує, що коле- джі можуть маніпулювати рейтингами, коли механізм паросполучення виявляє лише рейтинги окремих студентів. Задача вибору школи при строгих пріоритетах [21] концептуально майже тотожна задачі вступу до коледжів. Єдина й основна відмінність полягає у тому, що замість переваг щодо вступу класів студентів коледжі (школи) мають екзо- генно визначене пріоритетне впорядкування студентів. Останнє може бути наслідком, наприклад, тестових балів або таких соціальних критеріїв, як відстань до школи. Формально задачу вибору школи задають скінченні множини I та S учнів та шкіл відповідно, вектор Cccqq  )( місткості шкіл (припу- щення про те, що остання перевищує число учнів [21], є несуттєвим), профіль строгих пріоритетних упорядкувань Sss  )( шкіл, профіль строгих упоряд- кувань IiiRR  )( учнів при виборі школи. В.М. ГОРБАЧУК, Г.О. ШУЛІНОК Теорія оптимальних рішень. 2015 132 Задача вибору школи має таку ж інтерпретацію, як задача вступу до коле- джів, за винятком пріоритетного упорядкування s шкіл ,s яке строго впоряд- ковує множину I учнів: для учнів Iii , запис ii s  означає, що школа s має вищий пріоритет для учня ,i ніж для учня .i Наприклад, коли школи визначають пріоритети за відстанню до школи, то ii s  означає, що i прожи- ває до школи s ближче, ніж .i Для фіксованих множин I та ,S вектора ,q пріоритетної структури Sss  )( задача вибору школи задається профілем R переваг учнів. Паросполучення визначається так само, як у задачі вступу до ко- леджів, а механізм паросполучення є відображенням, яке визначає паросполу- чення для кожної задачі вибору школи (кожного профілю R ). Часто під парос- полученням розуміють відображення з множини I на множину ,S щоб наголо- сити на тому, що в задачі вибору школи останні є об’єктами. Оскільки учні во- лодіють приватною інформацією, то згаданий механізм є стратегічно стійким, якщо він стратегічно стійкий для учнів. Як і в задачі вступу до коледжів, головна мета публікацій стосовно задач вибору школи – проектувати механізми паросполучення, які задовольняють певним бажаним властивостям. Задача вступу до коледжів відрізняється тим, що в ній стабільність пов’язувалася з обмеженням, якому має задовольняти меха- нізм паросполучення для того, щоб гарантувати впорядковану участь студентів. У задачі вибору школи є декілька конкуруючих бажаних властивостей, запропо- нованих у відповідних публікаціях. Насамперед, для даної задачі вибору школи R паросполучення  є ефек- тивним, коли не існує іншого паросполучення  такого, що ( ) ( )ii R i  ,i I  ( ) ( )ii P i  для деякого .i I Оскільки школи є об’єктами, то ефективність сто- сується лише переваг учнів. Механізм паросполучення ефективний, якщо відби- рає ефективне паросполучення для кожної задачі вибору школи. Найчастіше для задач вибору школи використовується так званий Бостонський ефективний ме- ханізм паросполучення з особливою пріоритетною структурою для громадських шкіл м. Бостон (США) [21]. Цей механізм не залежить від конкретної пріоритет- ної структури. В М. Горбачук, Г.О. Шулинок АЛГОРИТМЫ ПОИСКА ПАРОСОЧЕТАНИЙ ДЛЯ ЗАДАЧИ ПОСТУПЛЕНИЯ В УЧЕБНЫЕ ЗАВЕДЕНИЯ Представлены алгоритмы поиска стабильных паросочетаний для двух классов участников, каждый из которых имеет рейтинг другого класса. АЛГОРИТМИ ПОШУКУ ПАРОСПОЛУЧЕНЬ ДЛЯ ЗАДАЧІ ВСТУПУ ... Теорія оптимальних рішень. 2015 133 V.M. Gorbachuk THE SEARCH ALGORITHMS OF MATCHING FOR A COLLEGE ADMISSION PROBLEM The algorithms of search stable matching for two classes of agents where every agent has ranking for another class. 1. Gale D., Shapley L. College admissions and the stability of marriage // American mathematical monthly. – 1962. – 69. – P. 9–15. 2. Roth A., Sotomayor M. Two sided markets – a study in game theoretic modeling. – Cambridge University Press, 1991. 3. Горбачук В.М. Моделювання вступу до університетів України 2015 р. // Сучасні пробле- ми управління підприємством: теорія і практика. – Харків: ХНЕУ, 2015. 4. Roth A. Deferred acceptance algorithms: history, theory, practice, and open questions // Interna- tional journal of game theory. – 2008. – 36. – P. 537 – 569. 5. Наказ Міністерства освіти і науки України № 1172 «Умови прийому на навчання до вищих навчальних закладів України в 2015 році» від 15 жовтня 2014 року. 6. Доценко С.И. Математические модели стабильных размещений // Журнал обчислюваль- ної та прикладної математики. – 2013. – 2 (112). – С. 3 – 13. 7. Шарифов Ф. Задача нахождения непересекающихся и несовпадающих циклов на сети // Теорія оптимальних рішень. – 2003. – 1. – С. 155 – 161. 8. Ostrovsky M. Stability in supply chain networks // American economic review. – 2008. – P. 897 – 923. 9. Roth A. The college admissions problem is not equivalent to the marriage problem // Journal of economic theory. – 1985. – 36. – P. 277 – 288. 10. Dutta B., Masso J. Stability of matchings when individuals have preferences over colleagues // Journal of economic theory. – 1997. – 75. – P. 464 – 475. 11. Echenique F., Yenmez B. A solution to matching with preferences over colleagues // Games and economic behavior. – 2007. – 59. – P. 46 – 71. 12. Roth A., Sotomayor M. The college admissions problem revisited // Econometrica. – 1989. – P. 559 – 570. 13. Roth A. The economics of matching: stability and incentives // Mathematics of operations re- search. – 1982. – 7. – P. 617–628. 14. Sonmez T. Strategy-proofness and essentially single-valued cores // Econometrica. – 1999. – 67. – P. 677 – 689. 15. Kara T., Sonmez T. Nash implementation of matching rules // Journal of economic theory. – 1996. – 68. – P. 425 – 439. 16. Kara T., Sonmez T. Implementation of college admission rules // Economic theory. – 1997. – 9. – P. 197 – 218. 17. Sonmez T. Games of manipulation in marriage problems // Games and economic behavior. – 1997. – 20. – P. 169 – 176. 18. Alcalde J., Romero-Medina A. Simple mechanisms to implement the core of college admissions problems // Games and economic behavior. – 2000. – P. 294 – 302. 19. Dubins L., Freedman D. Machiavelli and the Gale-Shapley algorithm // American mathematical monthly. – 1981. – 88. – P. 485 – 494. 20. Alcalde J., Barbera S. Top dominance and the possibility of strategy-proof stable solutions to matching problems // Economic theory. – 1994. – 4. – P. 417 – 435. 21. Abdulkadiroglu A., Sonmez T. School choice – a mechanism design approach // American eco- nomic review. – 2003. – 93 (3). – P. 729 – 747. Одержано 26.02.2015

Алгоритми пошуку паросполучень для задачі вступу до навчальних закладів

Institution

Similar Items