Stabil párosítások és általánosításaik  részletek

súgó  nyomtatás 
vissza »

 

Projekt adatai

 
azonosító
69027
típus K
Vezető kutató Fleiner Tamás
magyar cím Stabil párosítások és általánosításaik
Angol cím Stable matchings and its generalizations
magyar kulcsszavak 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
angol kulcsszavak stable matching, polyhedral combinatorics, cooperative game theory, matroids, greedoids, choice functions, graph colourings
megadott besorolás
Matematika (Műszaki és Természettudományok Kollégiuma)100 %
zsűri Matematika–Számítástudomány
Kutatóhely Számítástudományi és Információelméleti Tanszék (Budapesti Műszaki és Gazdaságtudományi Egyetem)
résztvevők Biró Péter
projekt kezdete 2007-07-01
projekt vége 2011-12-31
aktuális összeg (MFt) 3.210
FTE (kutatóév egyenérték) 4.00
állapot lezárult projekt
magyar összefoglaló
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.
angol összefoglaló
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.





 

Zárójelentés

 
kutatási eredmények (magyarul)
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á.
kutatási eredmények (angolul)
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.
a zárójelentés teljes szövege https://www.otka-palyazat.hu/download.php?type=zarobeszamolo&projektid=69027
döntés eredménye
igen





 

Közleményjegyzék

 
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




vissza »