 |
Here you can view and search the projects funded by NKFI since 2004
Back »
|
 |
Details of project |
|
|
| Identifier |
108383 |
| Type |
K |
| Principal investigator |
Fleiner, Tamás |
| Title in Hungarian |
Közgazdasági modellek matematikája |
| Title in English |
Mathematics of Economics models |
| Keywords in Hungarian |
Kombinatorika, elméleti közgazdaságtan, algoritmusok, lakáspiacok, hozzárendelési játékok, közgazdasági egyensúly, magmegoldás, nukleolusz, társadalmi választások |
| Keywords in English |
Combinatorics, Econometrics, algorithms, housing markets, assignment games, economic equilibrium, core, nucleolus, social choice |
| Discipline |
| Mathematics (Council of Physical Sciences) | 60 % | | Ortelius classification: Mathematics | | Economics (Council of Humanities and Social Sciences) | 40 % | | Ortelius classification: Economics |
|
| 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
Cseh, Ágnes
Jankó, Zsuzsanna
Schlotter, Ildikó
Sziklai, Balázs Róbert
|
| Starting date |
2013-09-01 |
| Closing date |
2018-08-31 |
| Funding (in million HUF) |
8.391 |
| FTE (full time equivalent) |
8.15 |
| 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.
Kutatási tervünk célja diszkrét közgazdasági modellekkel kapcsolatos matematikai és kiszámítási kérdések tanulmányozása. Az alapmodellben véges sok részvevő szeretne egymás közt felosztani egy bizonyos fajta erőforrást. Mivel a különböző részvevők értékelési szempontjai különbözők lehetnek, többféle, ezen szempontokat figyelembe vevő kívánalom lehet a megoldással szemben, úgymint stabilitás, Pareto-optimalitás, magtulajdonság, egyensúlyi helyzet, nukleolusz stb. A közgazdaságtan különféle ágai (játékelmélet, általános egyensúlyelmélet, aukciók elmélete) behatóan foglalkoznak ezekkel a kérdésekkel.
Különböző diszkrét közgazdasági modellekben fogjuk a megoldások tulajdonságait és azok struktúráját vizsgálni, illetve az alábbi problémákkal kapcsolatos algoritmikus kérdéseket tanulmányozunk: a megoldás létezésének eldöntése, optimális megoldás keresése, az összes megoldás struktúrájának leírása, stb. Célunk, hogy hatékony algoritmust találjunk vagy megmutassuk hogy a kérdéses problémára ilyen nem várható. Az NP-teljes problémák esetén a megoldás közelíthetőségét és paraméteres bonyolultságát vizsgáljuk. Az ehhez szükséges eszközeinket korábbi kutatásaink során már részben kifejlesztettük (pl a stabilitásfogalomnak bizonyos fixponttételekhez kapcsolásával), de mindezeket tovább is fejlesztjük. További módszereinket a játékelméletből, kombinatorikából, gráfelméletből, matroidelméletből, kombinatorikus optimalizálásból és a bonyolultságelmélet eszköztárából kölcsönözzük. Ezek együttes felhasználásától remélünk új, az elmélet ill. gyakorlati alkalmazás szempontjából jelentős, érdekes eredményeket.
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.
Ld az előző összefoglalót.
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!
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.
A tervezett kutatás fő jellemzője, hogy olyan újszerű megközelítéstől remélünk jelentős és érdekes, a gyakorlatban is alkalmazható tudományos eredményeket, amelyek távolinak tűnő területeket kapcsolnak össze: a közgazdaságtant, játékelméletet, valamint a matematika különböző ágait, nevezetesen a gráfelméletet, kombinatorikus optimalizálást, (paraméteres) bonyolultságelméletet és az algoritmusok elméletét. Korábbi eredményeink alapján alapján ígéretesnek érezzük ezt a vállalkozást, hiszen a kutatócsoportunk egyedülálló módon egyesíti magában a szükséges kompetenciákat.
A remélt eredmények egyrészt elméleti jelentőségűek, és a vizsgált piaci modellek jobb megértését várjuk tőlük, másrészt olyan, gyakorlatban alkalmazható eljárásokra számítunk, amelyek segítségével a megoldás hatékonyan közelíthető vagy található meg.
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.
Az utóbbi években világossá vált, hogy a közgazdaságtan játékelmélettel rokon területén az érdekes és alkalmazható eredmények az eddiginél jóval több matematikát igényelnek. Más kutatások mellett példa erre több korábbi eredményünk, amelyekben a stabil párosítások és fixponttételek kapcsolatára mutattunk rá. A stabil párosítások elméletének fontosságát jelzi a 2012-es közgazdasági Nobel díj, amit Roth és Shapley kaptak, főként a stabil allokációk elméletében elért eredményeikért. Úgy érezzük, itt szerzett versenyelőnyünket meg tudjuk őrizni, és (külföldi szerzőtársainkkal együttműködve) a kutatás élvonalában tudunk maradni.
Célunk, hogy korábbi eredményeink kiterjesztése révén különféle piacalapú modellekben bizonyítsunk eredményeket, találjunk alkalmazásokat ill. e modellek vizsgálatába matematikai módszereket vezessünk be. Kutatásunk homlokterében az egy- és kétoldalú piacok stabilitás-fogalmával és igazságos osztozkodással kapcsolatos vizsgálatok, valamint társadalmi választással kapcsolatos kérdések állnak. Olyan algoritmusokat fejlesztünk, amelyek különféle kívánalmaknak megfelelő megoldást találnak változatos piaci szituációkban. Amellett, hogy új eszközök (pl paraméteres bonyolultságelmélet) bevezetésével elemezzük ezen megoldások megtalálásának bonyolultságát, keressük az alkalmazható és elmélet szempontból jelentős eredményeket is. Célunk eredményeink minél szélesebb körű megismertetése pl az EU által támogatott Matching in Practice kutatócsoporbeli aktív részvétellel vagy nemzetközi workshopok szervezésével, mint amilyen az általunk szervezett Match-Up 2012 volt, vagy amelyet 2013 nyarára tervezünk a Nobel díjas Al Roth részvételével.
| Summary Summary of the research and its aims for experts
Describe the major aims of the research for experts.
The aim of this project is to study discrete economic models from the mathematical and computational perspective. The basic model consists of a finite set of participants who wish to divide some kind of resources. As participating agents may have different preferences, various solution concepts could be used that reflect these differences: stability, Pareto optimality, core, economic equilibrium, nucleolus etc. Such models are intensively studied in various branches of economics, like computational social choice, auction theory, general equilibrium theory, game theory etc.
We shall study the properties and the structure of the solutions in different variants of discrete economic models and we shall also consider algorithmic questions connected with the following problems: deciding the existence of the solution, finding an optimal solution, describing the structure of all solutions etc. Our aim will be to propose, if possible, an efficient algorithm or to prove the intractability of the studied problem. In case of NP-complete problems we shall study their approximability and parameterized complexity. Previously, we have already developped some of the necessary tools (like connecting the notion of stability to fixed point theorems) and we shall expand them further. Furthermore, by combining routine techniques of game theory, combinatorics, graph theory, matroid theory, combinatorial optimization and complexity theory, we hope to find new and interesting results that are significant for the theory or practical applications.
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.
See the previous summary.
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 main characteristic of the planned research is that we expect significant, interesting and practically applicable scientific results that
connect seemingly distant areas like economics, game theory and various branches of mathematics, namely graph theory, matroid theory, combinatorial optimization, (parametric) complexity theory and the theory of algorithms. Based on our previous results, we think that this is a promising ventrure as our research group uniquely contains all the necessary competences.
The expected results are significant on one hand for the theory, and we hope a better understanding of the studied market models. On the other hand, we aim practically applicable efficient procedures that help to find or approximate solutions.
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 recent years, it became apparent that interesting and applicable results in game theory related economics need much deeper mathematics than it used to involve. Examples are (besides other ongoing research projects) our former results linking stable matchings and fixed point theorems. The growing interest for the theory of stable matchings is indicated by the 2012 Nobel Memorial Prize in Economics won by Roth and Shapley mainly for their results on the theory of stable allocations. We think that we can keep our advantage coming from our former research and results and (cooperating with our foreign coauthors) we can still produce cutting edge research.
Our goal is to discover such results by extending our previous work, finding new applications and introducing novel mathematical methods in handling different market-based models. Our study will focus on the stability notion of one-sided and two-sided market situations, diverse fair division problems and social choice theory. As a result, we expect efficient algorithms that find solutions with various properties in different market models. Also, we shall analyze the complexity of finding these solutions by introducing novel tools like parametrized complexity to the area. Also, we look for theoretically interesting results with possible applications. We also aim to disseminate our results to the wider public, for example by our acitve participation in the Matching in Practice research group (supported by the EU) or by organizing workshops such like the MatchUp 2012 organized by us or the one we plan for the summer of 2013 with Nobel laureate Al Roth.
|
|
|
|
|
|
|
|
| |
List of publications |
|
|
| Fleiner T: On stable matchings and flows, ALGORITHMS 7: (1) 1-14, 2014 | | Cechlarova K, Eirinakis P, Fleiner T, Magos D, Mourtos I, Potpinkova E: Pareto optimality in many-to-many matching problems, DISCRETE OPTIM 14: 160-169, 2014 | | 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 | | Britta Dorn, Ildikó Schlotter: Having a Hard Time? Explore Parameterized Complexity!, In: Ulle Endriss (editor), Trends in Computational Social Choice, Chapter 11. AI Access, (to appear), 2017 | | Ildikó Schlotter, Piotr Faliszewski, Edith Elkind: Campaign management under approval-driven voting, Algorithmica, volume 77, issue 1, pp. 84-115, 2017 | | Matthias Mnich, Ildikó Schlotter: Stable marriage with covering constraints: A complete computational trichotomy, SAGT 2017: the 10th International Symposium on Algorithmic Game Theory, 2017 | | Katarína Cechlárová, Tamás Fleiner, Ildikó Schlotter: Possible and necessary allocations under serial dictatorship with incomplete preference lists, ADT 2017: the 5th International Conference on Algorithmic Decision Theory, 2017 | | Britta Dorn, Ronald de Haan, Ildikó Schlotter: Obtaining a proportional allocation by deleting items, ADT 2017: the 5th International Conference on Algorithmic Decision Theory, 2017 | | A. Cseh: Popular matchings, In: Ulle Endriss (editor), Trends in Computational Social Choice, Chapter 6, 2017 | | A. Cseh, J. Matuschke: New and simple algorithms for stable ow problems, WG 2017 proceedings, 2017 | | A. Cseh, R. W. Irving and D. F. Manlove: The Stable Roommates problem with short lists, Theory of Computing Systems (SAGT special issue, accepted), 2017 | | A. Cseh, T. Kavitha: Popular edges and dominant matchings, Mathematical Programming (published online), 2017 | | Cseh, C-C. Huang and T. Kavitha: Popular matchings with two-sided preferences and one-sided ties, SIAM Journal on Discrete Mathematics (accepted), 2017 | | Biró P, Fleiner T: Fractional solutions for capacitated NTU-games, with applications to stable matchings, DISCRETE OPTIM 22: (Part A) 241-254, 2016 | | Britta Dorn, Ildikó Schlotter: Having a Hard Time? Explore Parameterized Complexity!, In: Ulle Endriss (editor), Trends in Computational Social Choice, Chapter 11. AI Access, 2017 | | Cseh Ágnes: Hogyan lesz minden játékos elégedett? A tortaszeletelés tudománya., Élet és Tudomány 73(28) 870-872, 2018 | | Cseh Ágnes: Matematika a párkapcsolatokban. Tiltott frigyek, házasságszédelgés és válás., Élet és tudomány, 73(4) 111-113, 2018 | | Cechlarova K, Fleiner T, Manlove DF, McBride I, Potpinkova E: Modelling practical placement of trainee teachers to schools, CEJOR 23: (3) 547-562, 2015 | | Cechlarova K, Eirinakis P, Fleiner T, Magos D, Manlove DF, Mourtos I, Ocelakova E, Rastegari B: Pareto Optimal Matchings in Many-to-Many Markets with Ties, LECT NOTES ARTIF INT 9347: 27-39, 2015 | | Katarína Cechlárová, Eva Potpinková, Ildikó Schlotter: Refining the complexity of the sports elimination problem, Discrete Applied Mathematics, volume 199, pp. 172-186, 2016 | | Haris Aziz, Ildikó Schlotter, Toby Walsh: Control of Fair Division, Proceeding of the 25th International Joint Conference on Artificial Intelligence (IJCAI 2016), New York City, USA, pages 67-73, 2016 | | Cechlarova K, Fleiner T: Pareto optimal matchings with lower quotas, MATH SOC SCI 88: 3-10, 2017 | | Cechlárová K, Eirinakis P, Fleiner T, Magos D, Manlove D, Mourtos I, Ocel̆áková E, Rastegari B: Pareto Optimal Matchings in Many-to-Many Markets with Ties, THEOR COMPUT SYST 59: (4) 700-721, 2016 | | Cechlarova K, Fleiner T, Manlove DF, McBride I: Stable matchings of teachers to schools, THEOR COMPUT SCI 653: 15-25, 2016 | | Solymosit Tamás, Sziklai Balázs: Characterization sets for the nucleolus in balanced games, Operations Research Letters vol. 44 pp. 520-524, 2016 | | Sziklai Balázs, Fleiner Tamás, Solymosi Tamás: On the core and nucleolus of directed acyclic graph games, Mathematical Programming, Ser. A, First online: 18 August 2016, 2016 | | Katarína Cechlárová, Eva Potpinková, Ildikó Schlotter: Refining the complexity of the sports elimination problem, Discrete Applied Mathematics, volume 199, pp. 172-186, 2016 | | Haris Aziz, Ildikó Schlotter, Toby Walsh: Control of Fair Division, Proceeding of the 25th International Joint Conference on Artificial Intelligence (IJCAI 2016), New York City, USA, pages 67-73, 2016 | | Biró P, Fleiner T, Irwing RW: Matching couples with Scarf's algorithm, ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE, 2016 | | Cechlarova K, Eirinakis P, Fleiner T, Magos D, Manlove DF, Mourtos I, Ocelakova E, Rastegari B: Pareto Optimal Matchings in Many-to-Many Markets with Ties, LECT NOTES ARTIF INT 9347: 27-39, 2015 | | Péter Biró, László Á. Kóczy, Balázs Sziklai: Fair apportionment in the view of the Venice Commission?s recommendation, Mathematical Social Sciences 77, 32-41, 2015 | | László Á. Kóczy, Balázs Sziklai: Electing the Pope, Homo Oeconomicus 32(1): 101-116, 2015 | | Cechlárová K, Fleiner T, Jankó Z: House-swapping with divorcing and engaged pairs, DISCRETE APPL MATH 206: 1-8, 2016 | | Fleiner T, Jankó Z: On Weighted Kernels of Two Posets, ORDER 33: (1) 51-65, 2016 | | Fleiner T, Kamiyama N: A matroid approach to stable matchings with lower quotas, MATH OPER RES 41: (2) 734-744, 2016 | | Biró P, Fleiner T: Fractional solutions for capacitated NTU-games, with applications to stable matchings, DISCRETE OPTIM n/a: , 2015 | | Cechlarova K, Fleiner T, Manlove DF, McBride I, Potpinkova E: Modelling practical placement of trainee teachers to schools, CEJOR 23: (3) 547-562, 2015 | | Fleiner T, Jankó Z: On Weighted Kernels of Two Posets, ORDER n/a: , 2015 | | Cechlarova Katarina, Fleiner Tamas, Potpinkova Eva: Assigning evaluators to research grant applications: the case of Slovak Research and Development Agency, SCIENTOMETRICS 99: (2) 495-506, 2014 | | Fleiner Tamás, Jankó Zsuzsanna: Choice Function-Based Two-Sided Markets, ALGORITHMS 7: (1) 32-59, 2014 | | Cseh A, Fleiner T: The Complexity of Cake Cutting with Unequal Shares, Algorithmic Game Theory: 11th International Symposium, SAGT 2018, 2018 |
|
|
|
|
|
|
|
|
|
