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.
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; Fleiner T; Irving R; Manlove DF: The College Admissions problem with lower and common quotas, Theoretical Computer Science 411, 3136-3153, 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
