 |
Markets with sectors: matching problems and assignment games
|
Help 
Print 
|
Here you can view and search the projects funded by NKFI since 2004
Back »
|
| |
Details of project |
|
|
| Identifier |
128348 |
| Type |
PD |
| Principal investigator |
Atay, Ata |
| Title in Hungarian |
Többszektoros piacok: párosítási problémák és hozzárendelési játékok |
| Title in English |
Markets with sectors: matching problems and assignment games |
| Keywords in Hungarian |
hozzárendelési játékok, kooperatív játékok, párosításelmélet, mechanizmustervezés, piactervezés |
| Keywords in English |
assignment games, cooperative games, matching theory, mechanism design, market design |
| Discipline |
| Economics (Council of Humanities and Social Sciences) | 100 % | | Ortelius classification: Economics |
|
| Panel |
Economics |
| Department or equivalent |
Institute of Economics, (Centre for Economic and Regional Studies) |
| Starting date |
2018-09-01 |
| Closing date |
2020-08-31 |
| Funding (in million HUF) |
5.269 |
| FTE (full time equivalent) |
0.70 |
| state |
closed project |
Summary in Hungarian A kutatás összefoglalója, célkitűzései szakemberek számára
Itt írja le a kutatás fő célkitűzéseit a témában jártas szakember számára.
A kutatás témája a hozzárendelési probléma kifizetéses és kifizetés nélküli párosítási piacokon. Ezen kérdéskört a párosításelmélet és a kooperatív játékelmélet szakirodalma tárgyalja. A projekt első részében a disztribúciós feltételek mellett történő párosítási problémákkal foglalkozunk. Az egyetemi felvételi és a rezidensek allokációja két piac, amely leírható ezen modellekkel. Mivel itt a Gale és Shapley által javasolt stabil párosítások létezése nem garantált, ezért alternatív stabilitási koncepciókat javasol a szakirodalom. Célunk, hogy egy gyengén stabil párosítást kiválasztó stratégiailag biztos mechanizmust adjunk. Ennek a létezése egy nyitott kérdés. Ha ilyen nem mindig létezik, akkor olyan feltételt igyekszünk találni, amely garantálja a létezését. A projekt második részében “igazságos” és “optimális” megoldás keresésével foglalkozunk többoldalú piacokon, ahol a pénzbeli kifizetés megengedett. E modell segítségével vizsgálhatók az ellátási láncok. Két kutatást tervezünk. Először megvizsgáljuk a többoldalú hozzárendelési feladatokon a stabil halmazokat, és karakterizáljuk a mag-stabilitást. Mivel a mag lehet üres, illetve amikor ez egy stabil halmaz, akkor ez az egyetlen stabil halmaz, ezért érdekesebb a stabil halmazok vizsgálata. A többoldalú piacokon ezt még nem vizsgálta a szakirodalom. Ezután a nukleoluszt vizsgáljuk, amely egy olyan egyértelmű megoldás, ahol a szereplők elégedetlenségét figyelembe véve kapunk egy igazságos megoldást. Az axiomatikus jellemzésünk új eredményt jelentene a többoldalú piacok esetében. Végül a karakterizáción keresztül célunk egy algoritmust adni a nukleolusz kiszámításához.
Mi a kutatás alapkérdése?
Ebben a részben írja le röviden, hogy mi a kutatás segítségével megválaszolni kívánt probléma, mi a kutatás kiinduló hipotézise, milyen kérdéseket válaszolnak meg a kísérletek.
A kutatás fő kérdése, miként tudunk „igazságosan” és „optimálisan” allokálni párosítási piacokon. Két fontos piaci modellt vizsgálunk: párosítási piacokat disztribúciós feltételek mellett, és többoldalú hozzárendelési piacokat. Először egy olyan párosítási mechanizmust szeretnénk tervezni disztribúciós feltételek mellett, amely stratégiailag biztos módon vezet gyengén stabil párosításra. Ennek létezése egy nyitott kérdés a szakirodalomban. Szeretnénk továbbá demonstrálni a módszer használatát valódi piacokon, hogy a döntéshozók felismerjék alkalmazhatóságát. Azt sejtjük, hogy ezen mechanizmus létezése a feltételrendszer struktúrájától függ. Ezért először ellenpéldákat keresünk az általános feltételrendszerekre nézve, majd igyekszünk meghatározni azon tulajdonságait a struktúrának, amely garantálja a kívánt mechanizmus létezését. Sejtésünk az is, hogy a kedvező struktúrák esetében az mechanizmus hatékony algoritmussal implementálható. A kutatás második részében kifizetéses piacokkal foglalkozunk. Itt azt sejtjünk, hogy a mag akkor és csakis akkor esik egybe a von Neumann-Morgenstern stabil halmazzal, ha az érték-mátrixnak domináns diagonálisa van. Célunk tehát a mag-stabilitás karakterizációja. Továbbá, azt állítjuk, hogy a von Neumann-Morgenstern stabil halmaz létezése bizonyos részjátékok segítségével igazolható. Ezután a nukleulusszal foglalkozunk, amelynek vizsgálatában a konzisztencia tulajdonság lehet meghatározó. Egy lehetséges irány egy igazságossági tulajdonság összehasonlítása a konzisztencia-tulajdonsággal. A karakterizáció segítségével a nukleolusz kiszámításához is használható algoritmust is kaphatunk.
Mi a kutatás jelentősége?
Röviden írja le, milyen új perspektívát nyitnak az alapkutatásban az elért eredmények, milyen társadalmi hasznosíthatóságnak teremtik meg a tudományos alapját. Mutassa be, hogy a megpályázott kutatási területen lévő hazai és a nemzetközi versenytársaihoz képest melyek az egyediségei és erősségei a pályázatának!
A javasolt kutatásban kettős a célunk. Először disztribúciós feltételekkel szabályozott piacokat vizsgálunk. A Gale és Shapley által definiált stabil megoldás itt nem mindig létezik. Emiatt a gyengén stabil megoldásokkal foglalkozunk, melyek létezése garantált. Viszont a feladat struktúrája miatt nem könnyű a mechanizmus további tulajdonságinak, így a stratégiailag biztosságnak a vizsgálata. Az első célunk egy olyan mechanizmus tervezése, amely stratégiailag biztos módon vezet gyengén stabil megoldásra. Mivel disztribúciós feltételek számos valós alkalmazásban is előfordulnak (pl. magyar egyetemi felvételi és japán rezidensek allokációja), ezért a javasolt mechanizmus viszonylag egyszerű és intuitív kell legyen, hogy piaci szereplők megértsék. Ez biztosítaná a gyakorlati alkalmazhatóságát a döntéshozók számára. Ez lenne az első ismert mechanizmus, amely a gyenge stabilitást és stratégiai biztonság tulajdonságait egyszerre tejesítené. A projekt második részében többoldalú hozzárendlési játékokkal foglalkozunk, amelyekben a szereplők pénzbeli kifizetést adhatnak egymásnak. Ilyen szituációkra példák azok a piacok, ahol a vevők és eladók közvetítőkön keresztül bonyolítják transzakcióikat, illetve az ellátási piacok. A stabil halmazok létezését fogjuk vizsgálni, és karakterizációt adni a mag-stabilitásra. Mivel a stabil halmazokat korábban nem vizsgálták, és a mag lehet üres az ilyen piacokon, ezért a kutatásunk a többoldalú piacok stabilitásának egyfajta vizsgálatát adja. Emellett a nukleouszt is vizsgáljuk, amely a szereplők elégedetlensége szerint definiált igazságos megoldási koncepció. Célunk egy axiomatikus karakterizációt adni a nukleoluszra, amley az elspilyen jellegű eredmény lehet többoldalú piacokra. Egy ilyen karakterizáció további eredményekre is vezethet a nukleolusz kiszámítására nézve hatékony algoritmussal.
A kutatás összefoglalója, célkitűzései laikusok számára
Ebben a fejezetben írja le a kutatás fő célkitűzéseit alapműveltséggel rendelkező laikusok számára. Ez az összefoglaló a döntéshozók, a média, illetve az érdeklődők tájékoztatása szempontjából különösen fontos az NKFI Hivatal számára.
Párosításoknak kiemelt szerepük van bizonyos gazdasági szituációkban, például diákok iskolákhoz, rezidensek kórházakhoz, és licitálók aukciós tárgyakhoz történő allokálásakor. Kérdés, hogy miként párosítsunk ilyen helyzetekben. A válasz nagyban múlhat a piac struktúráján és az elérni szándékozott célokon. Két fontos tulajdonság a stabilitás és a stratégiai biztosság. Egyszerűen fogalmazva a stabilitás azt jelenti, hogy nincs két szereplő, akik jobban szeretnének egymással párban lenni (esetlegesen elhagyva jelenlegi partnereiket). A stratégiai biztosság esetén senki sem tud jobb partnerhez jutni a mechanizmusban hamis preferenciák megadásával. Kutatásunkban párosítási mechanizmusokat vizsgálunk disztribúciós feltételek mellett. Ilyen piacra példa a japán rezidensek allokációja. Mivel a legtöbb rezidens városban szeretne dolgozni, ezért a vidéki kórházak nem tudnák feltölteni a helyeiket egy szabad piacon. Emiatt területi kvótákat vezettek be, de a döntéshozók számára nehézséget jelent egy olyan mechanizmus létrehozása, amely egyszerre stratégiailag biztos és stabil. Célunk egy ilyen tulajdonságokkal rendelkező mechanizmus tervezése, ami implementálható a gyakorlatban. Emellett többoldalú párosítási piacokkal is foglalkozunk, ahol a pénzbeli kifizetés megengedett. Erre egy példa, amikor a vevők és eladók között cégek közvetítenek az eladásban. Azt vizsgáljuk, hogy miként osztható el igazságosan a profit, vagyis a mag koncepcióját (amely megoldás semmilyen koalíció által nem javítható), és a stabil halmazt (amely a magnak egy kibővítése). Célunk a stabil halmaz létezésének bizonyítása, tulajdonságának leírása, és ezzel a profit optimális megosztásának meghatározása.
| Summary Summary of the research and its aims for experts
Describe the major aims of the research for experts.
The proposed research project focuses on assignment problem in matching markets with and without monetary transfers. Matching theory and cooperative game theory are two research lines that are used to model such situations. In the first part of this project, we will focus on matching markets with distributional constraints. College admission and residency matching problems are examples of such matching markets that can be described by this model. Since stable matchings à la Gale and Shapley may not exist, other stability concepts were proposed. Our aim is to provide a strategy-proof mechanism that selects a weak stable matching. This is a recent open question and our mechanism would be the first mechanism to implement such outcome. Moreover, the maximal domain for such mechanisms will be studied. In the second part of this project, we will study "fair" and "optimal" solutions for multi-sided markets where monetary transfers are allowed. Supply chains can be defined by means of this model. Our aim is two-fold. First, we will study the stable sets for multi-sided assignment games and give a characterization of core stability. Since the core may be empty and whenever it is a stable set it is the unique one, it is more appealing to study stable sets in this setting. Ours will be the first work that study stable sets in multi-sided markets. Second, we will focus on a single-valued solution, the nucleolus, which is based on dissatisfaction of agents, and hence it has fairness property. We will offer an axiomatic characterization which would be the first in the multi-sided case. Moreover, through this characterization we aim to provide an algorithm to compute the nucleolus.
What is the major research question?
Describe here briefly the problem to be solved by the research, the starting hypothesis, and the questions addressed by the experiments.
The main question of this research project is “How to make allocations in a “fair” and “optimal” way in matching markets?” To this end, we study two important markets: matching problems under distributional constraints and multi-sided assignment markets. First, we want to design a matching mechanism under distributional constraints which satisfies strategy-proofness and weak stability properties. This is an open question on this literature. Moreover, we will demonstrate its applicability to the real-life markets in order to be applied by policy makers. We conjecture that such mechanism exists depending on constrains’ structure. Hence, we will look for counterexamples in general case, and then provide the maximal domain that could be applied. Furthermore, our hypothesis is that our proposed algorithm would be computationally efficient. The second part will focus on matching markets with payments. In this setting, we conjecture that the core is the von Neumann-Morgenstern stable set if and only if the valuation matrix has a dominant diagonal. That is to say, we will look for a characterization of the core stability. Moreover, we claim that the existence of von Neumann-Morgenstern stable set for multi-sided assignment games can be obtained by means of certain type of subgames. Another question that we will pose in this setting is related to another solution concept, the nucleolus. We conjecture that consistency property is a key tool to study the nucleolus. A possible approach to this question would be considering some fairness property together with consistency. Furthermore, depending on the characterization, an algorithm to compute the nucleolus can be studied.
What is the significance of the research?
Describe the new perspectives opened by the results achieved, including the scientific basics of potential societal applications. Please describe the unique strengths of your proposal in comparison to your domestic and international competitors in the given field.
In this proposed research project, our aim is two-fold. In the first part, we plan to study markets with distributional constraints. It is observed that stability à la Gale and Shapley may fail whenever there are distributional constraints imposed in the market. We will focus on weak stability, since under distributional constraints, weak stable matchings always exist. Nevertheless, because of its structure, it is not easy to study other properties such as strategy-proofness. Our first aim is to introduce a strategy-proof mechanism that chooses a weak stable matching. As markets with distributional constraints are observed in real-life (e. g. Hungarian college admission, Japanese residency match problem), the mechanism offered should be non-technical and intuitive in order to be understood by agents in the market. This would allow policy makers to design a clearinghouse mechanism and offer it as a matching process. Our mechanism will be the first one which implements an outcome that satisfies strategy-proofness and weak stability simultaneously. The second part of this project will focus on multi-sided assignment games which can be used to describe multi-sided matching markets where monetary payments allowed. Such examples are the markets where trade between buyers and sellers are done through middlemen and supply chains. We will study the existence of stable sets and give a characterization of core stability. Since there are no results focusing on stable sets and the existence of the core is not guaranteed in general, our work can shed light on stability for multi-sided assignment markets. Another question we will consider is related to a single-valued solution, the nucleolus. It satisfies a fairness property based on dissatisfaction of agents. Our goal is to give an axiomatic characterization for the nucleolus. It will be the first characterization of the nucleolus for the multi-sided case. Moreover, this characterization may lead to a fruitful research on finding a mechanism to implement the nucleolus as an outcome for these markets and another question is to find an algorithm to compute the nucleolus.
Summary and aims of the research for the public
Describe here the major aims of the research for an audience with average background information. This summary is especially important for NRDI Office in order to inform decision-makers, media, and others.
Matching has a prominent role in economic situations. Schools must admit students, residents should be assigned to hospitals, bidders bid for paintings. The question is how to match in such environments. This can vary depending on the structure of the market and the properties that we would like to satisfy. Two important properties are stability and strategy-proofness. Roughly speaking, stability means there is no pair of agents who prefer to be matched with each other (while possibly rejecting some or all of their current partners) rather than the prescribed matching. Strategy-proofness states that no agent gets better off by misreporting their true preference. In this project, first, we will study matching markets with distributional constraints. An example of such market is the Japanese residency matching scheme. Since most residents prefer city hospitals, rural hospitals are not able to fill their positions. Thus, there are further constraints on prefectures and policy makers face a difficulty to design a clearinghouse satisfying strategy-proofness and stability. We will introduce a mechanism that satisfies these two properties. Thus, it can be implemented by policy makers. In the second part of this project, we will focus on multi-sided matching markets with monetary transfers. An example is where trade between suppliers and buyers are done through firms. We will study how to share the profit and, to this end, we will analyse solution concepts: the core (the set of allocations that cannot be improved upon by any coalition) and the stable sets (a superset of the core). Our aim is to establish the existence of stable sets and provide an optimal way to share the profit.
|
|
|
|
|
|
|
|
|
|
