ВИКОРИСТАННЯ АЛГОРИТМУ ГЕЙЛА-ШЕПЛІ ДЛЯ ВИРІШЕННЯ ЕКОНОМІЧНИХ ЗАДАЧ - Scientific conference
Main page
UA RU EN

Congratulation from Internet Conference!

Hello

Рік заснування видання - 2014

ВИКОРИСТАННЯ АЛГОРИТМУ ГЕЙЛА-ШЕПЛІ ДЛЯ ВИРІШЕННЯ ЕКОНОМІЧНИХ ЗАДАЧ

24.06.2023 12:39

[1. Economic sciences]

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



Annotation. This paper is devoted to matching theory applications in economics and especially in banking. The stable marriage problem and the Gale-Shapley algorithm are reviewed as well as their applications. The Gale-Shapley algorithm with quotas is considered as an effective method to solve variety of problems in banking. We demonstrate this with the problem of banking products distribution among the bank's clients, that is presented as a stable marriage problem with quotas. The set of banking products and services, on the one hand, and the set of their potential consumers (clients), on the other hand, are considered as elements for matching problem. Clients have individual preferences of banking products and services. For each product from the set the bank, in turn, ranks clients as potential consumers.  Products can have quotas (number of clients, credit resource, etc.).  The developed software allows to solve problems of different dimensions.




Вступ. В 2012 році Нобелівську премію в області економіки отримали двоє американських вчених Елвін Рот (Гарвардський університет) і Ллойд Шеплі (університет Каліфорнії) за результати в теорії коаліційних ігор. На їх основі були створені практичні алгоритми, котрі замінювали ринкову взаємодію в багатьох галузях діяльності, де вона була неможливою або неефективно [3]. «Поєднання основ теорії Ллойда Шеплі з емпіричними дослідженнями і практичними моделями Елвіна Рота створили поле для дослідження і підвищення потужностей багатьох ринків» [5].

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

В даному дослідженні розглядається застосування алгоритму Гейла-Шеплі у банківській діяльності на основі завдання 2-х стороннього матчингу з квотами. 

Дослідження має структуру: вступ, базова модель мар'яжу, основні напрямки використання теорії матчингу; проблема оптимального розподілу банківських послуг як завдання матчингу з квотами.

Базова модель мар’яжу. У 1962 році в журналі American Mathematical Monthly з’явилася робота «College admission and the stability of marriage» (Вступ до коледжу і стабільність шлюбу) математиків Девіда Гейла (університет Брауна) і Ллойда Шеплі (Принстонський університет) [1]. У цій роботі, яка відносилася до теорії коаліційних ігор, вчені розглядали формальну задачу, яка пізніше отримала назву «задача (модель) мар’яжу».

Розглянемо дві множини економічних агентів (індивідів): M={m1,…,mn } - агенти, і W={w1,…,wm } - контрагенти. Кожен агент має свій набір уподобань (переваг) серед контрагентів, і кожен контрагент має свої уподобання (переваги) серед агентів. Уподобання представлені у вигляді упорядкованого списку елементів множини, тобто кожен агент має упорядкований список уподобань серед контрагентів і навпаки. Матчинг являє собою множину агентів/контрагентів, складених за деяким правилом. Співставлення може бути випадковим: матчинг елементів у пару відбувається випадково, незалежно від їх переваг. Такий матчинг може бути покращений з урахуванням переваг, якщо можна скласти пари, в яких партнери будуть мати вищий рівень уподобань один одному. Якщо матчинг неможливо покращити в цьому сенсі, то він є стабільним: жоден з учасників матчингу не зможе створити пару з більш вигідним контрагентом. Розглянемо простий приклад: потрібно скласти пару з 3-х агентів і 3-х контрагентів із заданими перевагами в порядку зменшення (табл.1).

Табл.1

Вихідні дані матчингу (приклад)




Припустимо, випадковим чином створені пари (А, а), (В, с), (С, в). Очевидно, що вони можуть бути покращені, так як стійким матчингом в цьому випадку є набір пар {(А, а); (В, в); (С, с)}, в якому пари створені за найвищим рівнем уподобань серед партнерів. 

У теоремі Гейла-Шеплі показано, що в будь-якій моделі мар’яжу існує хоча б один стійкий матчинг, і запропоновано алгоритм його побудови (побудови матчингу) (алгоритм відкладеного прийняття запропонованих агентів). Суть його полягає у наступному.

Крок 1. a) кожен агент робить пропозицію номеру 1 в своєму списку (якщо у нього є прийнятні кандидатури).

b) кожен контрагент відхиляє відразу всі неприйнятні варіанти, і, якщо він отримав більш ніж одну прийнятну пропозицію, «відкладає» найбільш прийнятну, а інші – відхиляє.

Шаг k. a) будь-який агент, відхилений на k-1 кроці, робить нову пропозицію наступній прийнятній кандидатурі-контрагенту із варіантів, котрі йому ще не відмовили. Якщо прийнятних варіантів у нього не залишилося, то він не робить більше пропозицій. 

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

У випадку відсутності будь-яких пропозицій – алгоритм зупиняється і створюється матчинг із пар: агент та контрагент, чию пропозицію він залишив. Результатом роботи алгоритму завжди є стійкий матчинг [3]. Крім того, якщо всі уподобання у двосторонньому профілі строгі, то множина стійкого матчингу має M-оптимальний стійкий матчинг, і, аналогічно, W-оптимальний стійкий матчинг [2, с. 63].

Класичний варіант алгоритму Гейла-Шеплі детально розглянутий в роботах [1, 4, 7, 8, 9; 10; 11]. В задачі мар’яжу існує декілька узагальнень: нерівна кількість партнерів (агентів та контрагентів), квоти (декілька варіантів вибору) та інші, які використовуються для вирішення задач матчингу в різноманітних сферах. 

Основні напрямки використання теорії матчингу. Розповсюдженими прикладами застосування моделі мар’яжу в економічній сфері є завдання про вибір коледжу (вона фігурувала в назві оригінальної роботи [1]), про працевлаштування (підбір кадрів, [12, с.45]), про розподіл випускників (завдання про підбір пар в агентствах знайомств також має певний економічний аспект). У задачі про вибір коледжу (в широкому розумінні - це задача про розподіл абітурієнтів) агентами виступають студенти, а контрагентами - навчальні заклади. Особливістю цього завдання є те, що навчальні заклади можуть приймати більш ніж одного студента. Така модель застосовується при розподілі абітурієнтів на бюджетні місця у вищих навчальних закладах України, і це завдання вирішується за допомогою алгоритму Гейла-Шеплі.

Модель мар’яжу «фірми-працівники», де існує безліч фірм та працівників. Кожен працівник має свої уподобання щодо фірм працевлаштування, а кожна фірма – щодо працівників. Прикладом такої моделі є завдання розподілу молодих лікарів, яке було запропоновано Е. Ротом [12, с.32]. Алгоритм Гейла-Шеплі застосовується у різних сферах, зокрема, у трансплантології при підборі органів для трансплантації та пацієнтів [5]. Одним із останніх напрямків досліджень застосування даного алгоритму стали різноманітні ринки [5]. Так було встановлено, що механізм ціни-оплати цілком можна вбудувати в алгоритм, що виявилося корисним для вивчення функціонування інтернет-аукціонів, які відрізняються від звичайних [6].

Використання алгоритму Гейла-Шеплі у банківській сфері. Ефективність функціонування банку залежить від успішного вирішення проблеми забезпечення якісними послугами клієнтів із мінімальними ризиками для самої банківської організації. Для цього пропонується використовувати модель мар’яжу та розв’язання задачі матчингу за допомогою алгоритму Шеплі з квотами.

Розглянемо банк, який характеризується переліком послуг, що надаються. Припустимо, що є група споживачів цих послуг (клієнти банку), кожен із яких має переваги щодо цих послуг (перелік пріоритетів). Умови надання тієї чи іншої банківської послуги зафіксовані у рамках системи ризик-менеджменту банку. Таким способом ця система визначає пріоритет кожного споживача (клієнта) щоб одержати ту чи іншу послугу, тобто. переваги банку у наданні послуги тим чи іншим клієнтам. Тут можуть враховуватись різні характеристики клієнта (платоспроможність, надійність, вік тощо, це залежить від змісту послуги та політики банку). Отже, у цій моделі агентами є послуги банку, контрагентами – клієнти (споживачі послуг).

Завдання матчингу тут полягає в тому, щоб розподілити банківські послуги по споживачам таким чином, щоб переваги обох сторін були найкраще враховані. У цьому випадку клієнт отримає найкращі для себе послуги, які можливі з урахуванням його оцінки з боку банку, який надасть свої послуги з мінімальним ризиком. Надання банківських послуг обмежено квотою q_i, в якості якої можуть бути використані кількість наданих послуг або обсяг ресурсів, що розподіляються за цією послугою (наприклад, обсяг кредитних ресурсів). Для вирішення цього завдання використано алгоритм Гейла-Шеплі з урахуванням квот, і його реалізація виконана за допомогою мови Python.

Розглянемо приклад: розподіл кредитів серед потенційних позичальників. Банк може надати 2 види кредитів: N={n1,n2 } – множина послуг банку в сфері кредитування. База складається із 10 позичальників M={m1,m2,m3,m4,m5,m6,m7,m8,m9,m10 } – множина позичальників. Варто відзначити, що деякі позичальники мають строгі уподобання щодо певних видів кредитних послуг. 

Уподобання клієнтів мають наступний вигляд: m1: n1>n2; m2:n1>n2; m3:n1>n2; m4:n2>n1; m5:n2>n1; m6:n2; m7:n1; m8:n1>n2; m9:n2>n1; m10 n2>n1.

На основі системи оцінювання клієнтів було отримано такий профіль уподобань банку по кожному кредиту: 

n1:m1>m3>m5>m2>m10>m4>m9>m8>m6>m7

n2:m2>m1>m4>m3>m5>m6>m8>m10>m7>m9 

Банк може надати перших тип кредиту трьом позичальникам, другий – семи, тобто квоти послуг q={q1,q2 }={3;7}.

В результаті розв’язання задачі матчингу отримаємо наступний розподіл кредитів серед клієнтів: 

n1:{m1,m3,m2,}

n2:{m4,m5,m6,m10,m8,m9 } 

Відзначимо, що клієнт m7 позаматчинговий: він не отримав 1-й тип кредиту через низький рейтинг при малій квоті даної послуги, а друга послуга в його уподобаннях не була заявлена. Даний матчинг є стійким, тобто він не може бути покращений індивідуально або за допомогою пари. 

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

Список літератури: 

1. Gale D.; Shapley L.S.. College Admissions and the Stability of Marriage. The American Mathematical Monthly, Vol. 69, No. 1 (Jan., 1962), 9-15.

2. Balinski M. and Sonmez T.. A tale of two mechanism: Student placement. J. Econom. Theory, 84 (1): 73-94, 1999.

3. Gale D. and Sotomayor M. Some remarks on the stable matching problem. Discrete Applied Mathematics, Vol. 11, pp.223-232, 1985.

4. Serrano R. Cooperative games: core and Shapley value. In Encyclopedia of Complexity and Systems Science. Edited by R. Meyers. New York: Springer, 2009.  

5. Stable matching: Theory, evidence and practical design. Material of the Royal Sweden Academy of sciences. The prize in economic sciences 2012. 

6. Roberto-Medina A., Implementation of stable solution in a restricted matching market. Review of Economic Design, 3(2): 137-147, 1998.

7. Halldorsson M.M., Iwana K., Miyazaki S. and Yanagisawa H. Randomized approximation of the stable marriage problem. Theoretical Computer Science, Vol. 325, No. 3, pp. 439-465, 2004

8. Dubins L.E., Freedman D.A. Machiavelli and the Gale-Shapley Algorithm. The American Mathematical Monthly, Vol. 88, No. 7. (Aug-Sep., 1981), pp. 485-494.

9. Biro Peter. Student Admissions in Hungary  as Gale and Shapley Envisaged. Technical Report. Department of Computing Science. University of Glasgow, UK. Glasgow G12 8QQ, TR-2008-291. October 2008.

10. Braun S., Dwenger N., and Kubler D.. Telling the truth may not pay off: An empirical study of centralized university admission in Germany. 2007. SFB 649 Discussion Paper 2007-070.

11. Roth A.E. and Sotomayor M. Two-sided matching, volume 18 of Econometric  Society Monographs. Cambridge University Press, Cambridge, 1990. A study in game-theoretic modeling and analysis, With a foreword by Robert Aumann.

12. Roth, A.E. (2008) “Deferred Acceptance Algorithms: History, Theory, Practice and Open questions”, Internat. J. Game Theory, vol. 36.



Creative Commons Attribution Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License
допомога Знайшли помилку? Виділіть помилковий текст мишкою і натисніть Ctrl + Enter

Another articles in this section

Сonferences

Conference 2024

Conference 2023

Conference 2022

Conference 2021

Conference 2020

Conference 2019

Conference 2018

Conference 2017

Conference 2016

Conference 2015

Conference 2014

:: LEX-LINE :: Юридична лінія

Міжнародна інтернет-конференція з економіки, інформаційних систем і технологій, психології та педагогіки

Наукові конференції

Економіко-правові дискусії. Спільнота