Cooperative games with capacities  Page description

Help  Print 
Back »
 

Details of project

  
Identifier
108673
Type K
Principal investigator Biró, Péter
Title in Hungarian Kooperatív játékok kapacitásokkal
Title in English Cooperative games with capacities
Keywords in Hungarian kooperatív játékelmélet, piactervezés, mechanizmusok, stabil allokációk
Keywords in English cooperative game theory, market design, mechanisms, stable allocations
Discipline
Economics (Council of Humanities and Social Sciences)70 %
Ortelius classification: Microeconomics
Mathematics (Council of Physical Sciences)30 %
Ortelius classification: Operations research
Panel Economics
Department or equivalent Institute of Economics, (Centre for Economic and Regional Studies)
Participants Romsics, Erzsébet
Wojuteczky, Péter
Starting date 2013-09-01
Closing date 2017-08-31
Funding (in million HUF) 15.444
FTE (full time equivalent) 6.47
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.
Bizonyos gazdasági, társadalmi helyzetekben, de akár műszaki alkalmazásokban is, egyes szereplők több együttműködésben is részt vehetnek. Ezek leírására olyan kooperatív játékok a legalkalmasabbak, amelyben a játékosoknak kapacitásaik lehetnek. Példaként említhető az egyetemi felvételi és más stabil párosítási problémák, amelyek vizsgálatáért a 2012-es közgazdasági Nobel-díjat kiosztották. A kapacitásos kooperatív játékokra mindeddig meglepően kevés figyelem fordítódott, egyes speciális problémákat leszámítva. Kutatásunk célja új elméleti alapok kidolgozása, és ezek alkalmazása ismert és kevésbé ismert játékokra, piactervezési problémákra.

Kutatásunk fókuszában az átváltható hasznosságú, illetve a nem-átváltható hasznosságú kooperatív játékok kapacitásos modelljei állnak. Módszereink leginkább az operációkutatáshoz köthetők, az alkalmazások pedig a piactervezés területén lesznek.

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 kooperatív játékoknak két osztálya van, az átváltható hasznossággú játékok (TU-játékok) és a nem-átváltható hasznosságú játékok (NTU-játékok). TU-játékok esetén az együttműködő játékosok szabadon oszthatják fel egymás között a kooperációjuk hasznát. TU-játékokra több általános modell és elemzés is született az elmúlt két évben, amelyekben különböző megoldási koncepciókat vizsgálnak arra az esetre nézve, amikor egy játékos több koalícióban is részt vehet, esetleg különböző súllyal. Vannak továbbá olyan hasonló jellegű TU-játékok, például kétoldali párosító piacokokhaz kötődően, amelyeket már kimerítően tárgyaltak a szakirodalomban. Kutatásunk első alapfeladata a nemrég bevezetett megoldási koncepciók vizsgálata további speciális kapacitásos TU-játékokra, például általános párosítás feladatokra illetve cserefeladatokra. Az NTU-játékok bizonyos értelemben általánosabb modellt jelentenek a TU-játékoknál. Második kutatási feladatunk, hogy hasonló megoldási koncepciókat vezessünk be és elemezzünk NTU-játékokra. A szakirodalom itt is részletesen tárgyal néhány esetet, például a párosítás piacokat, de nagyrészt hiányoznak az általános elméletek, és több új speciális játék elemzése is fontos eredményre vezethet. Végül a harmadik problémakör a kapacitásos TU és NTU játékok összehasonlítása. Példaképpen említhető a kapacitásos NTU-játéknak számító egyetemi felvételi probléma és a TU-játékon alapuló aukciók hasonlóságainak elemzése.

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 kapacitásos kooperatív játékok modelljének pontosabb kidolgozásával és konkrét játékok elemzésével jobban megérthetjük, hogy egyes gazdasági, társadalmi szitációkban milyen megoldások bizonyulhatnak igazságosnak, hatékonynak. Ezek vajon kialakulhatnak-e decentralizált módon (a 'láthatatlan kéz' segítségével), avagy szükség lehet-e egy központi koordinációra az optimális megoldás elérésének érdekében. Nagyon konkrét alkalmazásként említhetők az iskolai és egyetemi felvételi eljárások, az aukciók, illetve vesecsere programok. Megjegyezzük, hogy ezen alkalmazások sikeressége fontos szerepet játszott a 2012-es közgazdasági Nobel díj odaítélésében is. Végső soron ugyanis ezek az alkalmazások a játékelméleti modellekre építő piactervezés megvalósult eredményei.

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.
Bizonyos gazdasági, társadalmi helyzetekben egyes szereplők több együttműködésben is részt vehetnek, ezért ezek leírására olyan kooperatív játékok a legalkalmasabbak, amelyben a játékosoknak kapacitásaik lehetnek. Példaként említhető az egyetemi felvételi és más stabil párosítási problémák, amelyek vizsgálatáért a 2012-es közgazdasági Nobel-díjat kiosztották. A kapacitásos kooperatív játékokra mindeddig meglepően kevés figyelem fordítódott, egyes speciális problémákat leszámítva. Kutatásunk célja új elméleti alapok kidolgozása, és ezek alkalmazása ismert és kevésbé ismert játékokra, piactervezési problémákra.

Gyakorlati jelentőssége a kutatásunknak főként a párosítási piacokon, úgy mint iskolai, egyetemi felvételi eljárások, aukciók és csereprogramok kérdéskörében várhatók.
Summary
Summary of the research and its aims for experts
Describe the major aims of the research for experts.
In certain economic, social situations, and even in technical applications, the agents can participate in several coalitions at a time. Cooperative games with capacities are the most appropriate models to describe such problems. As an example we may mention the college admissions and other stable matching problems, the subject that has been in the focus of the work of the 2012 Nobel Prize winners in economic sciences. However, apart from these particular problems, there has not been much work done on capacitated cooperative games so far. The aim of our research project is to establish new theoretical models that can be used to analyse well-known and novel games, and market design problems.

On research will focus on capacitated TU- and NTU-games, with application of operations research techniques.

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.
Cooperative games have two classes, games with transferable utilities (TU-games) and games with no transferable utilities (NTU-games). In case of TU-games the players in a coalition can distribute the worth of their cooperation among themselves, whilst this is not possible in NTU-games. Very recently, there have been a new line of research, general models with different solution concepts and novel theories, introduced for such TU-games where a player may participate in several coalitions, possibly with different intensities. Furthermore, there are some similar kinds of TU-games, e.g. related to two-sided matching markets, which have already been studied in the literature. The first goal in our research agenda is to apply the above novel concepts to studying further special TU-games with capacities, such as one-sided matching games (known also as stable fixtures problems) and exchange problems. NTU-games are somewhat more general models than TU-games. Our second goal is to establish general models and solution concepts for capacitated NTU-games. There is an existing literature on some particular family of games, such as network and matching problems, but the general theories are missing and many further particular games, e.g. exchange and flow problems, are yet to be described. Finally our third goal is to compare some families of TU-games with the corresponding NTU-games. In many cases there are simultaneously established wide literatures on corresponding family of games, e.g. college admissions problems and auctions, but not much attention has been paid yet to understand the similarities and differences of these games and the related theories.

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.
The impact of our research on capacitated cooperative games and particular market design problems would be a better understanding of the nature of ‘fair’ or ‘optimal’ solutions for the agents involved in certain economic or social situations. We shall also investigate under what circumstances these efficient solutions may arise as a result of some decentralised mechanisms, and in which cases we should rather establish a central coordination to achieve the objective. As major examples we can recall the school choice and the college admissions problems, the auctions and kidney exchange programs. We note that the success of the above mentioned applications has been deeply recognised by the 2012 Nobel award in economics. Essentially these applications are the final results of careful market design based on game theoretical models.

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.
In certain economic, social situations, and even in technical applications, the agents can participate in several coalitions at a time. Cooperative games with capacities are the most appropriate models to describe such problems. As an example we may mention the college admissions and other stable matching problems, the subject that has been in the focus of the work of the 2012 Nobel Prize winners in economic sciences. However, apart from these particular problems, there has not been much work done on capacitated cooperative games so far. The aim of our research project is to establish new theoretical models that can be used to analyse well-known and novel games, and market design problems.

The impact of our research in practice will be related to applications such as school choice and college admissions problems, auctions and exchange markets.




 

Final report

  
Results in Hungarian
A kutatásunkban olyan párosítási problémákat vizsgáltunk, amelyek leírhatók kooperatív játékként, ahol a résztvevők egyszerre több koalícióban is szerepelhetnek. Az egyik kutatásunkban azt feltételeztük, hogy a szereplők párokat alkothatnak és kifizetések lehetségesek a játékosok között, és elemeztük a páronként stabil, illetve a magbeli megoldások hatékony kiszámításának kérdését. A kutatásaink többi része olyan modellekre épült, ahol a kifizetés nem megengedett. Ilyen esetekre példa a rezidensek allokációja kórházakhoz, illetve az egyetemi felvételi, amely hazánkban is központi koordinációval működik. Két cikkben is foglalkoztunk a Scarf algoritmus által adott tört-megoldásokkal, amelynek létezését egy általános modellben sikerült igazolnunk. Az elméleti eredményeket alkalmaztunk a rezidensek allokációs problémájának azon esetére, amikor házaspárok közösen adhatják le jelentkezéseiket álláshelyekre. A Scarf algoritmus mellett ugyanezen kérdést egészértékű programozási technikával is megvizsgáltuk. Egészértékű programozást használtuk a hazai egyetemi felvételi specialitásainak vizsgálatakor is, illetve egy projekt allokációs alkalmazásban a Corvinus Egyetemen. Emellett további elméleti kutatásokat végeztünk a klasszikus szobatárs-problémáról, az oszthatatlan javak allokációjáról, és stabil párosítási feladatról bizonytalan preferenciák esetén. Összességében eddig hat folyóiratcikkünk került elfogadásra, és ugyanennyit tervezünk még benyújtani, vagy van már elbírálás alatt.
Results in English
We studied such matching problems that can be described with cooperative games, where players may be involved in multiple coalitions. In one research we assumed that the players may form pairs and can share their joint utilities with payments, and we studied the question of finding a pairwise stable or core solutions. The rest of our researches were concerned with models where payments are not allowed. Important examples are resident allocations to hospitals and college admissions, which is operating via a centrally coordinated scheme in Hungary as well. We studied the Scarf algorithm in two papers, first by showing that it provides a fractional stable solution in a general model, and then by applying this result for the resident allocation problem with couples. We also studied this problem with integer programming. We use the same technique to analyse the special features of the Hungarian higher education admission scheme, and for a project allocation application at Corvinus University. Besides, we investigated theoretical questions for the classical roommates problem, for the allocation of indivisible goods, and for stable matching with uncertain preferences. Altogether six papers have already been accepted at prestigious scientific journals, and another six are under revision or to be submitted shortly.
Full text https://www.otka-palyazat.hu/download.php?type=zarobeszamolo&projektid=108673
Decision
Yes





 

List of publications

  
André Veski, Biró Péter, Kaire Pöder, Triin Lauri: Efficiency and fair access in kindergarten allocation policy design, To appear in Journal of Mechanism and Institutional Design, 2017
Ágoston K Cs, Biró P, Szántó R: Stable project allocation under distributional constraints, In: Proceedins of the 10th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications . Budapest, Magyarország, 2017.05.22-2017.05.24. Kiadvány: 2017. pp. 43-52., 2017
Aziz H, Biró P, Fleiner T, Gaspers S, Haan R, Mattei N, Rastegari B: Stable matching with uncertain pairwise preferences, In: Proceedings of the 16th International Conference on Autonomous Agents and Multiagent Systems: AAMAS 2017. Sao Paulo, Brazília, 2017.05.08-2017.05.12. Kiadvány: 2017. pp. 344-352., 2017
Biró P, Fleiner T, Palincza R: Designing Chess Pairing Mechanisms, In: Proceedins of the 10th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications . Budapest, Magyarország, 2017.05.22-2017.05.24. Kiadvány: 2017. pp. 77-86., 2017
Biró P, Kern W, Paulusma D, Wojuteczky P: The stable fixtures problem with payments, GAME ECON BEHAV in press: -, 2017
Ágoston K Cs, Biró P, McBride I: Integer programming methods for special college admissions problems, J COMB OPTIM 32: (4) 1371-1399, 2016
Aziz H, Biró P, Gaspers S, Haan R, Mattei N, Rastegari B: Stable Matching with Uncertain Linear Preferences, In: Martin Gairing, Rahul Savani (szerk.) (szerk.) Algorithmic Game Theory: 9th International Symposium, SAGT 2016, Liverpool, UK, September 19–21, 2016, Proceedings. Berlin: Springer, 2016. pp. 195-206., 2016
Aziz H, Biró P, Lang J, Lesca J, Monnot J: Optimal Reallocation under Additive and Ordinal Preferences, In: AAMAS '16 International Conference on Autonomous Agents & Multiagent Systems . Singapore, Szingapúr, 2016.05.09-2016.05.13. Kiadvány: 2016. pp. 401-410., 2016
Biró P, Fleiner T: Fractional solutions for capacitated NTU-games, with applications to stable matchings, DISCRETE OPTIM 22: (Part A) 241-254, 2016
Biró P, Fleiner T, Irwing RW: Matching couples with Scarf’s algorithm, ANN MATH ARTIF INTEL 77: (3) 303-316, 2016
Biró P, Iñarra E, Molis E: A new solution concept for the roommate problem, MATH SOC SCI 79: 74-82, 2016
Biró P, McBride I: Integer programming methods for special college admissions problems, In: Zhang Z, Wu L, Xu W, Du D-Z (szerk.) (szerk.) Combinatorial optimization and applications: 8th International Conference, COCOA 2014, Wailea, Maui, HI, USA, December 19-21, 2014, Proceedings. Cham (Németország): Springer-Verlag Wien, 2014. pp. 429-443. (Lecture notes in computer science; 8881.), 2014
Peter Biro, David Manlove, Iain McBride: The Hospitals / Residents Problem with Couples: Complexity and Integer Programming Models, In Proceedings of SEA 2014: the 13th International Symposium on Experimental Algorithms, volume 8504 of Lecture Notes in Computer Science, pages 10-21, Springer, 2014, 2014
Peter Biro, Iain McBride: Integer programming methods for special college admissions problems, To appear in the proceedings of COCOA 2014: the 8th Annual International Conference on Combinatorial Optimization and Applications, LNCS, Springer, 2014
Péter Biró, Elena Inarra, Elena Molis: A new solution for the roommate problem: Q-stable matchings, CERS-HAS Discussion Papers, MT-DP-2014/22, 2014
Peter Biro, Tamas Fleiner: Fractional solutions for NTU-games, with applications to stable matchings, Discrete Optimization, 2015
Péter Biró, Walter Kern, Daniel Paulusma, Péter Wojuteczky: Stable Fixtures Problem with Payments, Proceedings of the 41st International Workshop, WG 2015, LNCS, 2015
Peter Biro, Elena Inarra and Elena Molis: A new solution for the roommate problem: The Q-stable matchings, Mathematical Social Sciences 79:74-82, 2016
Peter Biro, Tamas Fleiner, Rob Irving: Matching couples with Scarf's algorithm, Annals of Mathematics and Artificial Intelligence, 77(3):303-316, 2016
H. Aziz, P. Biro, J. Lang. J. Lesca, and J. Monnot: Optimal Reallocation under Additive and Ordinal Preferences, To appear in Proceedings of AAMAS 2016, 2016
H. Aziz, P. Biro, S. Gaspers, R. de Haan, N. Mattei and B. Rastegari: Stable Matching with Uncertain Linear Preferences, To appear in the proceedings of SAGT 2016, 2016




 

Events of the project

  
2016-12-21 16:23:41
Résztvevők változása



Back »