 |
Ezen az oldalon az NKFI Elektronikus Pályázatkezelő Rendszerében nyilvánosságra hozott projektjeit tekintheti meg.
vissza »
|
 |
Projekt adatai |
|
|
| azonosító |
128611 |
| típus |
K |
| Vezető kutató |
Cseh Ágnes |
| magyar cím |
Hatékony algoritmusok allokációs feladatokra |
| Angol cím |
Efficient algorithms for allocation problems |
| magyar kulcsszavak |
mechanizmustervezés, igazságos elosztások, párosítások |
| angol kulcsszavak |
mechanism design, fair division of goods, matchings |
| megadott besorolás |
| Gazdálkodástudomány (Bölcsészet- és Társadalomtudományok Kollégiuma) | 100 % |
|
| zsűri |
Gazdaság |
| Kutatóhely |
Közgazdaság-tudományi Intézet (HUN-REN Közgazdaság- és Regionális Tudományi Kutatóközpont) |
| résztvevők |
Biró Péter
Fleiner Tamás
Jankó Zsuzsanna
Schlotter Ildikó
|
| projekt kezdete |
2018-09-01 |
| projekt vége |
2023-08-31 |
| aktuális összeg (MFt) |
18.652 |
| FTE (kutatóév egyenérték) |
9.50 |
| állapot |
lezárult projekt |
magyar összefoglaló 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.
Célunk matematikai és számítástudományi modellekkel leírható közgazdasági allokációs 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özponti koordináció célja és a részvevők értékelési szempontjai problémánként különböző, többféle kívánalom támasztható a megoldással szemben, úgymint stabilitás, népszerűség, Pareto-optimalitás, magtulajdonság, vagy egyensúlyi helyzet. 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, és az összes megoldás struktúrájának leírása. 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, továbbá egészértékű programozási megoldóprogramokat használunk. Az ehhez szükséges eszközeinket korábbi kutatásaink során már részben kifejlesztettük (például a stabilitásfogalomnak bizonyos fixponttételekhez kapcsolásával), most 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, illetve gyakorlati alkalmazás szempontjából is 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.
Célunk különféle piacalapú allokációs modellek jobb megértése kombinatorikus módszerek bevezetésével és korábbi eredményeink felhasználásával. Kutatásunk homlokterében az egy- és kétoldalú párosítások stabilitás- és népszerűségfogalma, 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 (például paraméteres bonyolultságelmélet) bevezetésével elemezzük ezen megoldások megtalálásának bonyolultságát, mind a gyakorlatban alkalmazható, mind elméletileg jelentős eredmények megtalálására törekszünk.
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!
A tervezett kutatás fő jellemzője, hogy olyan újszerű megközelítéstől remélünk érdekes, a gyakorlati alkalmazás szempontjából jelentős tudományos eredményeket, amelyek távolinak tűnő területeket kapcsolnak össze: a közgazdaságtant, játékelméletet és a számítógépes szociológiát a matematika különböző ágaival, nevezetesen a gráf- és matroidelméletet, kombinatorikus optimalizálást, (paraméteres) bonyolultságelméletet és az algoritmusok elméletét. Korábbi eredményeink alapján ígéretesnek érezzük ezt a vállalkozást, hiszen a kutatócsoportunk egyedülálló módon egyesíti magában az ehhez szükséges kompetenciákat. Csoportunk minden tagja erős nemzetközi kapcsolatokkal rendelkezik. Ezenfelül minden szenior tag rendszeresen publikál a legszínvonalasabb számításelméleti konferenciákon és Q1-es értékelésű folyóiratokban. Emiatt eredményeink gyors, nemzetközi figyelmet keltő és minőségi publikációja várható.
A remélt eredmények elsősorban elméleti jelentőségűek, és a vizsgált piaci modellek jobb megértését várjuk tőlük. Elképzelhető emellett olyan eredmény is (például optimális megoldások közelítésére), amelyek segítségével a gyakorlatban is alkalmazható, praktikus eljárás fejleszthető ki.
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 számos jelentős és alkalmazható eredmény igényel magas fokú matematikát. Ezen interdiszciplináris megközelítés fontosságát jelzi a 2012-es közgazdasági Nobel-emlékdíj, amit Alvin Roth és Lloyd Shapley kaptak, főként a stabil allokációk elméletében elért eredményeikért.
Kutatócsoportunk öt tagja öt különböző számításelméleti vagy matematikai módszer szakértője. Közös erőfeszítésünk célja, hogy több szereplőt vagy egész társadalmat érintő kérdésekben eredményeket érjünk el. Témáink közé tartozik a javak igazságos elosztása és párosítási piacok, amelyeket az allokáció fogalom köt össze. Strukturált problémamegoldó tapasztalatunkat felhasználva olyan kérdéseket válaszolunk majd meg, mint például “Hogyan osszunk el igazságosan egy hagyatékot örökösök közt?”, “Milyen gyorsan találnak egyensúlyt a központi irányítás nélküli piacok?” és “Lehetséges a magyar felsőoktatási felvételi rendszer egyszerűsítése új programozási technikák által?”.
| angol összefoglaló 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 allocation problems in economics that can be described by models from the mathematical and computational perspective. The basic model consists of a set of participants who wish to divide a certain resource. Based on the preference structure of agents and the goal of the policymaker, various solution concepts can be used, such as stability, popularity, Pareto optimality, core, and economic equilibrium. Such models are intensively studied in various branches of economics, like computational social choice, auction theory, general equilibrium theory, and game theory.
We plan to 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, and describing the structure of all solutions. Our aim will be to propose, if possible, an efficient algorithm or to prove the intractability of the studied problem. In case of computationally hard problems we will investigate their approximability, parameterized complexity and solvability via integer programming solvers. Previously, we have already developed 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.
Our goal is a better understanding of different market-based allocation models by the introduction of mathematical methods and leaning on our previous work. We will focus on the stability and popularity notion of one and two-sided matchings, 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. We aim at theoretically interesting results with possible applications.
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 aim at significant, interesting and practically applicable scientific results that connect seemingly distant areas, such as economics, game theory, social choice theory, and computer science with various branches of mathematics, namely graph theory, algorithms, matroid theory, combinatorial optimization, and (parametrized) complexity. Based on our previous results, we believe that this is a promising venture as our research group uniquely contains all the necessary competences. All team members are extremely well connected to scientific peers abroad, and all senior team members publish regularly at major computer science conferences and in journals with rating Q1. We expect a fast, highly visible and high quality dissemination of our results.
The expected results are primarily theoretical, and we hope for a better understanding of the studied models. It is possible however, that we find results (e.g. for approximation of optimal solutions) that allow the development of practical and applicable procedures.
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 often need much deeper mathematics than before. The importance of this interdisciplinary approach is indicated by the 2012 Nobel Memorial Prize in Economics won by Alvin Roth and Lloyd Shapley mainly for their results on the theory of stable allocations.
Our team consists of five members who are experts in five different approaches in Computer Science and Mathematics. We join our forces to attack various problems arising in social choice; such as the fair division of goods or matching markets. Allocation is the unifying principle in these problems. Utilizing our experience in structured problem solving, we answer question such as ‘How to divide property between heirs fairly?’, ‘How fast do uncoordinated markets find an equilibrium?’ and ‘Can new programming models simplify the Hungarian higher education admission system?’.
|
|
|
|
|
|
|
|
| |
Közleményjegyzék |
|
|
| Á. Cseh, T. Fleiner: The complexity of cake cutting with unequal shares, ACM TRANSACTIONS ON ALGORITHMS, vol. 16, no. 3, pp. 1–21, 2020 | | Á. Cseh, K. Heeger: The stable marriage problem with ties and restricted edges, DISCRETE OPTIMIZATION, vol. 36, 2020 | | Á. Cseh, T. Fleiner, P. Harján: Pareto Optimal Coalitions of Fixed Size, Journal of Mechanism and Institution Design, vol. 4, no. 1, pp. 87–108, 2019 | | M. Mnich, I. Schlotter: Stable Matchings with Covering Constraints: A Complete Computational Trichotomy, Algorithmica, volume 82, pages 1136–1188, 2020 | | Aziz, H ; Biró, P ; Gaspers, S ; de Haan, R ; Mattei, N ; Rastegari, B: Stable matching with uncertain linear preferences, ALGORITHMICA 82 pp. 1410-1433., 2020 | | Biró, P ; Gudmundsson, J: Complexity of finding Pareto-efficient allocations of highest welfare, EUROPEAN JOURNAL OF OPERATIONAL RESEARCH , 37 p., 2020 | | Fleiner, T., Jagadeesan, R., Jankó, Z. and Teytelboym, A.: Trading Networks With Frictions, Trading Networks With Frictions, 2019 | | B. Dorn, R. de Haan, I. Schlotter: Obtaining a proportional allocation by deleting items, Algorithmica, volume 83, issue 5, pages 1559-1603, 2021 | | T. Andersson, Á. Cseh, L. Ehlers, and A. Erlanson: Organizing Time Exchanges: Lessons from Matching Markets, American Economic Journal: Microeconomics, 13 (1), 338-373, 2021 | | Á. Cseh, T. Kavitha: Popular Matchings in Complete Graphs, Algorithmica, 83(5), 1493-1523, 2021 | | Á. Cseh, A. Juhos: Pairwise preferences in the stable marriage problem, Transactions on Economics and Computation, article no. 7, 2021 | | Cseh Á, Faenza Y, Kavitha T, Powers V: Understanding Popular Matchings via Stable Matchings, SIAM JOURNAL ON DISCRETE MATHEMATICS, 2022 | | Cseh Á, Escamocher G, Genç B, Quesada L: A collection of Constraint Programming models for the three-dimensional stable matching problem with cyclic preferences, CONSTRAINTS, 2022 | | Aziz H, Cseh Á, Dickerson J P, McElfresh D C: Optimal Kidney Exchange with Immunosuppressants, AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE, 2021 | | Sziklai, B. R., Biró, P., Csató, L.: The efficacy of tournament design, Computers & Operations Research, 144, 105821., 2022 | | Biró, P., Gyetvai, M.: Online voluntary mentoring: Optimising the assignment of students and mentors, European Journal of Operational Research, 2022 | | Aziz, H., Biró, P., Fleiner, T., Gaspers, S., de Haan, R., Mattei, N., Rastegari, B.: Stable matching with uncertain pairwise preferences, Theoretical Computer Science, 909, 1-11., 2022 | | Jankó, Zs., Joó, A.: Cutting a cake for infinitely many guests, The Electronic Journal of Combinatorics, Volume 29, Issue 1, 2022 | | P. Biró, Gy. Magyarkuti: The Work of Milgrom and Wilson in the Theory and Practical Application of Auctions, FINANCIAL AND ECONOMIC REVIEW 20 : 1 pp. 127-151. , 25 p., 2021 | | P. Biró, Gy. Magyarkuti: Milgrom és Wilson munkássága az aukciók elméletében és gyakorlati alkalmazásában, Hitelintézeti Szemle, 2021 | | Fleiner, T., Jagadeesan, R., Jankó, Z. and Teytelboym, A.: Trading Networks With Frictions, Econometrica, 2019 | | Aziz H, Cseh Á, Dickerson J P, McElfresh D C: Optimal Kidney Exchange with Immunosuppressants, AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE, 2021 | | H. Aziz, Á. Cseh, G. Csáji: Computational complexity of k-stable matchings, The 16th International Symposium on Algorithmic Game Theory (SAGT), 2023 | | Á. Cseh, P. Führlich, P. Lenzner: The Swiss Gambit, The 22nd International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2023 | | K. Cechlárová, Á. Cseh, Zs. Jankó, M. Kireš, L. Miňo: A quest for a fair schedule: The Young Physicists' Tournament, Journal of Scheduling, 26:3–18, 2023 | | Á. Cseh, P. Führlich, P. Lenzner: Improving Ranking Quality and Fairness in Swiss-System Chess Tournaments, The 23rd ACM Conference on Economics and Computation (EC), 2022 | | Á. Cseh, G. Escamocher, L. Quesada: Computing relaxations for the three-dimensional stable matching problem with cyclic preferences, Constraints 28, 138–165, 2023 | | Á. Cseh, J. Peters: Three-Dimensional Popular Matching with Cyclic Preferences, The 21st International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2022 | | Á. Cseh, T. Friedrich, J. Peters: Pareto optimal and popular house allocation with lower and upper quotas, The 21st International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2022 | | S. Kraiczy, Á. Cseh, D. Manlove: On weakly and strongly popular rankings, Discrete Applied Mathematics, 340:134-152, 2023 | | H. Aziz, H. Chan, Á. Cseh, B. Li, F. Ramezani, C. Wang: Multi-Robot Task Allocation—Complexity and Approximation, The 20th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2021 | | Á. Cseh, J. Matuschke: New and simple algorithms for stable flow problems, Algorithmica, 81(6), 2557-2591, 2019 | | Á. Cseh, M. Skutella: Paths to stable allocations, International Journal of Game Theory, 48(3), 835-862, 2019 | | T. Kavitha, T. Király, J. Matuschke, I. Schlotter, U. Schmidt-Kraepelin: Popular branchings and their dual certificates, Mathematical Programming, volume 192, pages 567-595, 2022 | | T. Fleiner, Zs. Jankó, I. Schlotter, A. Teytelboym: Complexity of stability in trading networks, International Journal of Game Theory, volume 52, pp. 629-648, 2023 | | H. Aziz, I. Schlotter, T. Walsh: Computational complexity of necessary envy-freeness, Mathematical Social Sciences, 2023 | | I. Schlotter, P. Biró, T. Fleiner: The core of housing markets from an agent's perspective: Is it worth sprucing up your home?, The 17th Conference on Web and Internet Economics (WINE), 2021 | | T. Kavitha, T. Király, J. Matuschke, I. Schlotter, U. Schmidt-Kraepelin: The popular assignment problem: when cardinality is more important than popularity, The 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2022 | | I. Schlotter: Recognizing when a preference system is close to admitting a master list, The 17th International Conference and Workshops on Algorithms and Computation (WALCOM), 2023 | | Jankó, Z. and Joó, A: On generalisations of the Aharoni-Pouzet base exchange theorem, Bulletin of the London Mathematical Society, volume 55, issue 3, pages 1540-1549, 2023 | | Aziz, H., Baychkov, A., & Biró, P.: Cutoff stability under distributional constraints with an application to summer internship matching, Mathematical Programming, 1-23., 2022 | | Aziz, H., Biró, P., & Yokoo, M.: Matching market design with constraints, AAAI Conference on Artificial Intelligence (Vol. 36, No. 11, pp. 12308-12316)., 2022 | | Á. Cseh, K. Cechlárová, D.F. Manlove: Selected open problems in Matching Under Preferences, Bulletin of EATCS, number 128, June 2019, 2019 |
|
|
|
|
|
|
|
|
|
