Mathematics of Economics models  Page description

Help  Print 
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.





 

Final report

 
Results in Hungarian
A projektben diszkrét közgazdasági modellekkel kapcsolatos matematikai és kiszámítási kérdéseket vizsgáltunk. A munkatervben vállalt, évi 2-3 neves folyóiratban megjelent publikációról szóló ígéretet -úgy érezzük- jelentősen túlteljesítettük, csakúgy, mint a vállalt konferencia-részvételeket és konferencia-előadásokat. Mindezeken túl szerveztünk két konferenciát is, amelyeken a témánk több külföldi szakértője is megjelent. Eredményeink bár közvetlen gazdasági hasznot nem hajtanak (és nem is látszik az ilyesfajta hasznosíthaóság lehetősége), két Élet és Tudomány cikk és egy, a Kossuth rádióban elhangzott interjú formájában járultunk hozzá a tudományos ismeretterjesztéshez. Fehívtuk a figyelmet egy, a választási törvénytervezetben fellépő anomáliára, amely javításra került. Egy konferenciára benyújtott munkánk "Best paper" díjat kapott. Munkánk elismeréseként a téma 2019-ben rendezett fő eseményén pedig egyikünk a programbizottság társelnöke, a projekt egy másik résztvevője pedig az egyik meghívott főelőadó.
Results in English
In the project, we studied discrete economic models from the mathematical and computational perspective. The two to three publications in quality journals promised in the workplan is significantly overdone just like the number of conference participations and talks. We also organized two conferences with the participation of several foreign experts of our topic. Although our results do not create direct profit for the economy, we contributed to scientific dissemination by two publications in "Élet és Tudomány" and a report on Kossuth radio. We pointed out an anomaly in the electoral law proposal that has been corrected later. One of our work received a best paper award on a conference. As a recognition of our work, one of us is the co-chair and another participant of the project is one of the main speakers of the 2019 major event of our research topic.
Full text https://www.otka-palyazat.hu/download.php?type=zarobeszamolo&projektid=108383
Decision
Yes





 

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





 

Events of the project

 
2016-10-26 16:01:44
Résztvevők változása




Back »