Stable matchings and its generalizations  Page description

Help  Print 
Back »

 

Details of project

 
Identifier
69027
Type K
Principal investigator Fleiner, Tamás
Title in Hungarian Stabil párosítások és általánosításaik
Title in English Stable matchings and its generalizations
Keywords in Hungarian stabil párosítás, poliéderes kombinatorika, kooperatív játékelmélet, matroidok, greedoidok, kiválasztási függvények, gráfszínezések
Keywords in English stable matching, polyhedral combinatorics, cooperative game theory, matroids, greedoids, choice functions, graph colourings
Discipline
Mathematics (Council of Physical Sciences)100 %
Panel Mathematics and Computing Science
Department or equivalent Department of Computer Science and Information Theory (Budapest University of Technology and Economics)
Participants Biró, Péter
Starting date 2007-07-01
Closing date 2011-12-31
Funding (in million HUF) 3.210
FTE (full time equivalent) 4.00
state closed project
Summary in Hungarian
A stabil párosítások kutatása a kombinatorika, a játékelmélet és az elméleti közgazdaságtan izgalmas határterülete. A kombinatorikán belül az algoritmikus, a bonyolultságelméleti és a lineáris programozással kapcsolatos szempontok, a játékelméleten belül a kooperatív játékokkal való kapcsolat, az elméleti közgazdaságtan számára pedig bizonyos kétoldalú piaci szituációk leírása miatt érdekes. A vezető kutató korábbi kutatásaiban kidolgozott egy fixponttételeken alapuló megközelítést, mely különösen alkalmas a stabil párosítások általánosításainak tárgyalására. Számos korábbi tételt sikerült általánosítani, és ezzel együtt rengeteg új kérdés merült fel. Jelen kutatási tervezet ezeknek a kérdéseknek egy részét célozza. A stabil párosítás probléma olyan változatait vizsgáljuk, melyekben a piaci részvevők bizonyos kapacitásokkal rendelkeznek mely az együttműködési lehetőségeiket korlátozza. Az ilyen problémákra keresünk a kutatás során hatékony algoritmust, vizsgáljuk még a fixponttételes kapcsolatból származó strukturális tulajdonságokat, és keresünk további (akár gyakorlati) alkalmazásokat.
Summary
The research of stable matchings is an exciting topic on the border of
Combinatorics, Game Theory, and Econometrics. It is interesting for
Combinatorics for its algorithmic, Complexity Theoretical and linear
programming aspects, it is a particular topic in Cooperative
Game Theory, and in Econometrics it is interesting for the description of
certain two-sided market models.

The principal researcher, in his earlier works, has described an approach
based on fixed point theorems that was particularly useful for the
discussion of generalizations of stable matchings. As a consequence,
several earlier theorems were generalized, and many interesting new
questions emerged. Our present research project aims some of these
questions. We consider a form of the stable matching problem, in which the
market agents have certain capacities that restrict their possible
cooperation. We are looking for efficient algorithms for these kind of
problems, we study the structural properties following from the connection
with fixed points, and search for further (even practical) applications.





 

Final report

 
Results in Hungarian
A kutatási programunkban úgy érezzük, sikerült megvalósítani a kitűzött célokat. A csatolt publikációs listában szereplő 22 eredményünk többségét színvonalas nemzetközi folyóiratokban publikáltuk, vagy publikálni fogjuk. Számos nemzetközi konferencián vettünk részt, ahol ismertettük az eredményeinket és több kollégával szakmai együttműködést folytattunk. A kitűzött kutatási tervben az alábbi kutatási témák szerepeltek: blokkoló élek minimális száma (2 publikáció), stabil allokáció gráfokon (7 publikáció), Scarf lemma (1 publikáció), kooperatív játékelmélet (3 publikáció), gyakorlati alkalmazások (8 publikáció). Eredményeink ezeken kívül a stabil párosításoknak ill. azok általánosításainak létezésére ill. egyéb problémákban történő alkalmazásaira mutatnak rá.
Results in English
We think that we succeeded to achieve our goal. Most of our 22 results in the attached list are published or will be published in high standard international journals. We participated several conferences, gave talks on these results and collaborated with colleagues. Our original research plan contains the following research topics: minimum number of blocking edges (2 publications), stable allocation on graphs (7 publications), Scarf's lemma (1 publication), cooperative game theory (3 publications), practical applications (8 publications). Beyond these, our results point out the existence of various generalizations of stable matchings and their applicability to other problems.
Full text https://www.otka-palyazat.hu/download.php?type=zarobeszamolo&projektid=69027
Decision
Yes





 

List of publications

 
Biró P, Manlove DF, McDermid: Matching with sizes (or scheduling with processing set restrictions), Discrete Applied Mathematics közlésre elfogadta, 2012
Farooq R, Fleiner T, Tamura A: Matching with partially ordered contracts, Japan Journal of Industrial and Applied Mathematics, 2012
Fleiner T. Kamiyama N: A Matroid Approach to Stable Matchings with Lower Quotas, Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012
Biró P, Klijn F: Matching with Couples: a Multidisciplinary Survey, International Game Theory Review közlésre elfogadta, 2011
Biró P, Irving R,Schlotter I: Stable matching with couples: An empirical study, ACM Journal of Experimental Algorithmics 16, Article No.: 1.2, 2011
Fleiner T; Irving RW; Manlove DF: An algorithm for a super-stable roommates problem, Theoretical Computer Science 412(50), 7059–7065, 2011
Biró P, Manlove DF, McDermid E: "Almost stable" matchings in the Roommates problem with bounded preference lists, Theoretical Computer Science közlésre elfogadta, 2012
Biró P; McDermid E: Three-sided stable matchings with cyclic preferences, Algorithmica 58(1), 5-18, 2010
Biró P; Fleiner T; Irving R; Manlove DF: The College Admissions problem with lower and common quotas, Theoretical Computer Science 411, 3136-3153, 2010
Biró P; Manlove DF; Mittal S: Size versus stability in the Marriage problem, Theoretical Computer Science 411, 1828-1841, 2010
Biró P; Kern W; Paulusma D: Computing solutions for matching games, International Journal of Game Theory 41(1), 75-90, 2012
Biró P; Irving R; Manlove DF: Popular matchings in the Marriage and Roommates problems, Proceedings of CIAC 2010: the 7th International Conference on Algorithms and Complexity, Lecture Notes in Computer Science 6078, pp. 97-108, 2010
Fleiner T: On stable matchings and flows, Lecture Notes on Computer Science 6410, 51--62, 2010
Fleiner T; Frank A: Balanced list edge-colourings of bipartite graphs, Electronic Notes in Discrete Mathematics 36, 837-842, 2010
Cechlárová K; Fleiner T: Housing markets through graphs, Algorithmica 58(1), 19-33, 2010
Fleiner T: The stable roommates problem with choice functions, Algorithmica 58(1), 82-101, 2010
Biró P; Fleiner T: The integral stable allocation problem on graphs, Discrete Optimization 7(1-2), 64-73, 2010
Cechlárová K; Fleiner T: Stable roommates with free edges, EGRES Technical Report TR-2009-01, 2009
Jankó Zs: Stabil párositások és egyetemi felvételi ponthatárok, ELTE Matemaikai Intézet, 2009
Fleiner T: Stable matchings through fixed points and graphs, Ann. Univ. Sci. Budapest. Eötvös Sect. Math. 51, 69--116, 2009
Biró P; Manlove DF; Rizzi, R: Maximum weight cycle packing in directed graphs, with application to kidney exchange programs, Discrete Mathematics, Algorithms and Applications 1(4), 499-517, 2009
Biró P: Student admissions in Hungary as Gale and Shapley envisaged, Games and Economic Behavior (közlésre benyújtva), 2008




Back »