Резюме. Развитието на количествените методи през последните години и прилагането им в икономическата и социалната сфера бе мотивирано от проблема за преразпределителните процеси в различните области на обществените дейности. Постигането на оптималното (балансирано) състояние на това разпределение бе поставено като основна цел в емпиричните и теоретичните изследвания на икономистите от края на миналия и началото на настоящия век. Естествено, понятието разпределение (преразпределение) в никакъв случай не трябва да бъде разбирано като контрапункт на класическите принципи на съвършената конкуренция, които не предполагат монопол или държавна намеса в стопанските процеси, но тези модерни прийоми бяха прилагани от социални и етични подбуди. В области като разпределянето на донорски органи между нуждаещите се реципиенти или разпределението на местата в учебните заведения не може да се борави с традиционните ценови системи и това поражда нуждата от институционална намеса, която да регулира тези процеси, защото подобни „тънки” (с ограничен брой контрагенти от двете страни) пазари изискват регулаторни режими поне на определени нива. Настоящата статия описва прилагането на подобни разпределителни алгоритми, техните предимства и слабости и съпоставката между тях. Разгледано е практическото прилагане на алгоритъма на Гейл-Шапли и т. нар. Унгарски алгоритъм (Кьониг-Егервари алгоритъм) с техните силни и слаби страни. Изложени са и основни моменти от кооперативната теория на игрите. Теоретично обосновани са двата практически използвани алгоритъма.

Ключови думи: Gale-Shapley algorithm, Hungarian algorithm, cooperative games, stable matching, mathematical model

През 1962 г. математиците Дейвид Гейл и Лойд Шапли в съвместната си статия „Постъпването в колеж и стабилността на брака“ представят решение на математическа задача от областта на кооперативните игри. Там двамата учени изработват алгоритъм, който винаги води до образуването на стабилни двойки. Този алгоритъм получава в научната литература названието „алгоритъм с отложено приемане“ или алгоритъм на Гейл-Шапли.

Алгоритъмът с отложено приемане е автономен процес, който се състои от етапите: изготвяне и представяне на предложение, кандидатстване, приемане или отхвърляне на кандидата. Всеки кандидат ранжира предпочитанията си по низходящ ред. Той подрежда желанията си по желан от него начин, като най-желаната от него позиция се поставя на първо място, а по-слабо интересуващите го позиции се поставят на по-ниски рангове в изготвяния от него списък. На тази основа институцията, която селектира кандидатите, създава един въображаем пазар, за който не важат принципите, действащи на класическите пазари, т. е. механизмът на функциониране е различен. Алгоритъмът на Гейл-Шапли провокира игра със синхронизирани ходове на играчите, в която всеки участник заявява реда на желаните от него позиции, като се приема, че всеки от играчите има информация за методиката, по която въпросният алгоритъм съчетава отправените оферти със заявените интереси на играчите спрямо конкретните предложения. По този начин се формират числови редове, подчинени на определен тип разпределение. Често пъти подобни числови модели се проиграват чрез компютърни симулации. Някои от параметрите на модела могат да бъдат променяни предварително или в хода на самата симулация и получените резултати се подлагат на по-нататъшен анализ. Целта е да се построи максимално правдоподобен модел, описващ конкретната ситуация, който модел да генерира оптимално решение, което да удовлетвори всички участници в играта, т. е. всеки да е доволен от отправеното му предложение, а отправилият предложението да е съвместим с респондента, който го приема.

Този алгоритъм може да бъде практически приложен при определяне на приема в училища, колежи и университети. Важно е да се отбележи, че подреждането на приоритетите на кандидатите (кандидат-гимназисти или кандидат-студенти) трябва да е подчинено на обективни критерии и възможности, а не на субективни такива. Обективността при избора и от двете страни изисква те да не се разглеждат като стратегически субекти (всеки да е с цел да надхитри или победи другия на базата на собствените си преимущества), а да се разглеждат като равноправни партньори, всеки от които има какво да предложи на другия и ползата да е съвместна и за двамата. Създадените по този алгоритъм стабилни съчетания предполагат устойчивост и жизненост на системите, които са формирани от единици, свързани по този начин – преодолява се вътрешната ентропия и балансът и осигурен.

Пример за нестабилно съчетание е т. нар. „Бостънски механизъм“. „Този алгоритъм най-напред се опитва да съчетае колкото се може повече кандидати с първия им избор, след това той съчетава останалите с втория им избор и т. н., ако за даден кандидат е много трудно да влезе в най-предпочитаното си училище, при този механизъм е по-добре като първи избор да се определи по-малко популярно училище. Това поставя кандидатите в неприятно стратегическо положение – да изиграят системата по оптимален начин, те трябва да знаят в кои училища приемът е реалистичен за тях. Онези, които просто съобщават истинските си предпочитания, имат необосновано ниски резултати1) .“ (2006) През 2005 г. се въвежда алгоритъм с отложено приемане с предложение от кандидата. Тъй като той е съвместим със стимулите на кандидата, отпада необходимостта от стратегическо по-ведение.

В САЩ например за стабилното съчетаване на кандидатите се използват специализирани инструменти – т. нар. клирингови къщи, които имат за цел да оптимизират процесите на съчетаване.

В България процесите на реформиране в образователната сфера протекоха с известно закъснение, което наложи по-друг подход в регулирането на процесите. Решение 454 от 02.07.2010 г. формулира децентрализацията (в случая в образователната сфера) като „процес на прехвърляне на правомощия и ресурси за тяхното упражняване от по-високо към по-ниски равнища на публичното управление“. 2)

В конкретния случай е удачно да се приложат две форми на децентрализация:

– функционална – признават се правомощия, които са специфични и ограничени в определен сектор или дейност. Най-често това се свързва с предоставяне на определена услуга на дадено изпълнително звено, което има свой юридически статут и собственост, например изпълнителна агенция, дружество или фирма;

– териториална – при нея правото за вземане на решение се предоставя на единици, чиято юрисдикция и сфера на действие е определена по териториален принцип, зона и местоположение и чиито правомощия са предначертани от централната власт. 3)

Теоретична обосновка на кооперативните игри и алгоритъма на Гейл-Шапли

Най-общата дефиниция за кооперативните игри е „кооперативните игри са игри, при които играчите могат да образуват коалиция и да се договарят при избора на стратегии. Те избират своите стратегии върху основата на съглашение, при което се отчитат интересите на страните, участващи в него. Играчите се договарят както за своите стратегии, така и за разпределението на печалбата“ (Стойков, 2005).

В нашата ситуация при формиралата се коалиция между играчите в групата те използват принципа на „смесена стратегия“, т. е. стратегия, при която „чистите стратегии се изпълняват в някакъв вероятностен порядък с елемент на случайност. Без да правим обстойно обяснение на теорията на игрите, могат да се изведат математически следните зависимости:

Всяка крайна игра има цена, а цената е ограничена от долната и горната цена на играта, т. е. δ ≤ М ≤ γ където δ – долна цена на играта, γ – горна цена на играта, Μ – цена на играта.

Ако имаме двама играчи X и Y, то налице е игра от типа zxh, в която играч Х има z стратегии, а играч Y има h стратегии. Съответно обозначаваме първия играч с X1 , X2 ,…, Xz, а втория играч – с Y1 , Y2 ,…, Yh.

В случая изразът SX = {F1 , F2 ,…, Fz} е смесената стратегия на играч Х, която той прилага с вероятност (честота) F. При което F1 + F2 +…+ Fz =1.

Съответно за играч Y получаваме SY = {F1 , F2 ,…, Fh} => F1 + F2 + …+ Fh = 1

Формулировка на алгоритъма на Гейл-Шапли, адаптирана към решаването на конкретната задача

Дадени са две съвкупности SC (school) и ST (student) и всеки елемент от множество SC има определено предпочитание към елемент от множеството ST. Тоест в случая можем да говорим какъв брой елементи от съвкупността SC за определен елемент от съвкупността ST се явяват по-предпочитани, а кои се ползват с по-слаби предпочитания. Аналогично заключение можем да изведем и за предпочитанията на дадени единици от множество SC към единиците от множество ST. Смисълът на задачата се свежда до фрагментирането (съчетаването) на единиците от двете множества по двойки, но не само като механично съчетаване, а и като съчетаване със стабилен характер. Стабилността – обобщено понятие от теорията на игрите, което в конкретния случай означава, че отсъстват двойки (ST’, SC’) и (ST’’, SC’’), притежаващи такива свойства: за ST’ елемент SC’’ се явява по-предпочитан пред SC’, а за SC’’ ST’’ е по-предпочитан пред ST’.

Алгоритъмът приема следното решение:

– учениците кандидатстват за най-предпочитаното училище;

– всяко училище избира измежду всеки кандидат най-добрия по определен критерий и му дава отговор „може би“, а на останалите дава категоричен отговор „не“;

– учениците, получили отказ, кандидатстват за поредното в предпочитанията си училище, учениците, получили отговор „може би“, не кандидатстват за поредното училище от списъка си;

– ако конкретно училище класира по-качествен кандидат от набраните до момента, то на последния, който е получил отговор „може би“, се дава категоричен отговор „не“, а на новокласирания кандидат се отговаря „може би“;

– итерациите се повтарят, докато у всички ученици не се изчерпи списъкът с ранжирани учебни заведения, в този момент училищата дават отговор „категорично да“ на последните класирани по техните изисквания кандидати, които до момента получават отговор „може би“.

Приема се, че е налице мрежа от 4 училища и 4 ученици, всеки със своите предпочитания.

Графично гореописаният алгоритъм може да се представи така:

Компютърен модел на математическата задача, в която е използван „алгоритъм с отложено приемане“

Компютърният модел4) на задачата, разработен в среда за математическо моделиране и програмиране, има вида: вж. фиг. 2

В първата матрица в задачата предпочитанията на учениците са зададени по редове, а на училищата – по колони. Във втората матрица по колони са предпочитанията на училищата, а на учениците са по редове.

След решаването на зададения модел получаваме следните данни: вж. фиг. 3

От решението е видно, че стабилно свързани са следните двойки ученик – училище: STUDENT1, SCHOOL3; STUDENT2, SCHOOL4; STUDENT3, SCHOOL1 и STUDENT4, SCHOOL2 и съответно техните стойности са 1. За нестабилно съчетаните двойки стойностите са 0.

Решението притежава и графично измерение: вж. фиг. 4 и фиг. 5

Критерии за подбор

Критериите за подбор от страна на кандидат-гимназистите (кандидат-студентите) или от страна на училищата (университетите) могат да бъдат от разнороден характер в зависимост от целите, които си поставят отделните субекти.

От страна на кандидат-гимназиста критериите могат да бъдат:

1. Престижносттана избраната професионална гимназия (СОУ) и перспективите за работа по специалността и стабилни доходи след дипломирането. Отговаря ли профилът на съответната професионална гимназия (СОУ) на отрасловата специализация на региона, в който живее кандидат-гимназистът.

2. Дали е налична приемственост между средното професионално образование и висшето. Продължаване на образованието по аналогична специалност във ВУЗ и надграждане върху получените вече знания.

3. Дали съответното училище се намира във или в близост до населеното място, където живее кандидат-гимназистът. Приема ли той за целесъобразно и рентабилно да учи в отдалечено селище, където се намира набелязаното от него училище.

От страна на кандидат-студента критериите могат да бъдат:

1. Престижът на избрания ВУЗ – дали той попада в челните места на националните и международните класации на университетите.

2. Дали учебните програми и предлаганите специалности са съобразени с нуждите на бизнес средата.

3. Размерът на таксите за обучение и оценката на обучаващите се дали са съобразени с качеството на предлаганото образование.

4. Материално-техническата база на учебните заведения и учебно-методическата (научната) подготовка на преподавателския състав.

От страна на университетите (средните училища) критерии могат да бъдат:

1. Средният успех от свидетелствата за основно образование (за кандидатгимназистите) или резултати от приемните изпити в елитните гимназии или максималния бал на кандидатите (за кандидат-студентите).

2. Демонстрирани резултати от страна на кандидатите на национални или световни олимпиади по съответните научни направления (за кандидат-студентите).

3. Ценовата готовност на кандидатите да заплатят изискуемите такси за обучение (за кандидат-студентите).

Естествено, критериите могат да имат по-широк диапазон от тук посочените.

Алтернативно решаване на модела чрез т. нар. Унгарски алгоритъм За целта използваме втората матрица на предпочитанията на училищата по колони спрямо тези на учениците по редове. Например в първата колона Училище 1 поставя на първо място в класацията си кандидат-гимназист (кандидат-студент) с номер 3. След това следват кандидатите с номера 4, 1 и 2 и т. н. (Вж. Таблица №1, където е зададена матрицата на предпочитанията).

Следващата стъпка е да определим минималния елемент във всеки ред и да го извадим от всички елементи на матрицата, които се намират в съответния ред. Вж. таблица №1.1

Таблица 1.1

Във втората итерация повтаряме същата процедура по колони, при условие че в колоната няма нула. Но тъй като във всяка колона имаме по едно нула, не е необходимо изваждане. Вж. таблица №1.2.

След това зачертаваме всички редове и колони, където присъства елементът 0 два пъти. Вж. таблица №1.3.

Но тъй като в нито един ред или колона няма по две нули, класическото изпълнение на алгоритъма5) се прекратява. Правилото е, че е необходимо да бъдат зачертани всички редове и колони с по две нули в тях. Липсата на този факт в задачата ни принуждава да спрем изпълнението на алгоритъма до тук и да анализираме получените до момента резултати. Сравнявайки редовете и колоните в таблицата в клетките със стойност 0, с които те се засичат, получаваме следното решение (Вж. таблица 1.4):

STUDENT1, SCHOOL3; STUDENT3, SCHOOL1 ; STUDENT4; SCHOOL2

Сравнени с резултатите, получени по Гейл-Шапли – STUDENT1, SCHOOL3; STUDENT2, SCHOOL4; STUDENT3, SCHOOL1 и STUDENT4, SCHOOL2 е ясно, че имаме следните съвпадения: Вж. таблица 1.5.

От анализа на данните разбираме, че двойката STUDENT2, SCHOOL4 не могат да бъдат стабилно съчетани, ако се приложи в задачата Унгарски (Кьониг-Егервари) алгоритъм, което съчетаване е възможно при алгоритъма с „отложено приемане“.

Графично решението чрез Унгарския алгоритъм приема вида, посочен във фиг. 6 (с пунктир е отбелязана нестабилно съчетана двойка).

Заключение

Алгоритъмът на Гейл-Шапли може да бъде прилаган на различни нива или от различни структури, били те частни, или обществени. Потребителите са улеснени в значителна степен от наличието на специализиран софтуери от различен характер (в настоящата статия е използван LINGO 14.0). Това подобрява ефективността на изследователския и приложно-практическия труд на ползващите алгоритъма. LINGO 14.0 или друга по ранна версия предоставя предимство в това отношение, защото дава достъп до библиотеки със скриптове от най-различни области на икономиката, инженерните науки, логистиката, приложната математика и др., които могат да бъдат модифицирани и преработвани в зависимост от потребностите на ползвателя. По-напредналите в областта на програмирането могат сами да си създават свои скриптове, които да ползват за целите на работата си.

БЕЛЕЖКИ

1. Нобелова награда за постижения в областта на икономическите науки за 2012 г.// Икономическа мисъл, 2012, № 6, с.110 – 111.

2. Паскалев, Ат. Децентрализацията в системата на средното професионално образование // Икономическа мисъл, 2013, №1, с.134.

3. Паскалев, Ат. Децентрализацията в системата на средното професионално образование // Икономическа мисъл, 2013, №1, с.135.

4. http://www.lindo.com/cgi-bin/modelf.cgi?STABLE_MARRIAGE4.txt;LINGO (към 02.08.2013).

5. http://article.sapub.org/pdf/10.5923.j.algorithms.20120104.02.pdf (към 02.08.2013).

ЛИТЕРАТУРА

Стойков, И. (2005) Количествени методи в управлението. Свищов