Efficient algorithms for allocation problems  Page description

Help  Print 
Back »

 

Details of project

 
Identifier
128611
Type K
Principal investigator Cseh, Ágnes
Title in Hungarian Hatékony algoritmusok allokációs feladatokra
Title in English Efficient algorithms for allocation problems
Keywords in Hungarian mechanizmustervezés, igazságos elosztások, párosítások
Keywords in English mechanism design, fair division of goods, matchings
Discipline
Business and Management (Council of Humanities and Social Sciences)100 %
Panel Economics
Department or equivalent Institute of Economics, (Centre for Economic and Regional Studies)
Participants Biró, Péter
Fleiner, Tamás
Jankó, Zsuzsanna
Schlotter, Ildikó
Starting date 2018-09-01
Closing date 2023-08-31
Funding (in million HUF) 18.652
FTE (full time equivalent) 9.50
state running project





 

Final report

 
Results in Hungarian
OTKA projektünk keretében matematikai és számítástudományi modellekkel leírható közgazdasági allokációs kérdéseket tanulmányoztunk. 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. Kutatásunk homlokterében az eredeti tervvel összhangban 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 álltak. Olyan algoritmusokat fejlesztettü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 elemeztük ezen megoldások megtalálásának bonyolultságát, mind a gyakorlatban alkalmazható megoldásokat fejlesztettünk ki, illetve több cikk esetén valós problémákra adtunk megoldást, amelyeket több alkalommal fel is használtak. A csoport 5 állandó tagja és 5, időnként cserélődő hallgatója összesen 41 publikációt jelentetett meg a projekt témáiban.
Results in English
In the framework of our OTKA project, we studied economic allocation issues that can be described by mathematical and computational models. In the basic model, a finite number of participants wish to allocate a certain type of resource among themselves. Since the goal of central coordination and the evaluation criteria of the participants differ from problem to problem, there are several requirements for the solution, such as stability, popularity, Pareto optimality, core property, or equilibrium. The various branches of economics (game theory, general equilibrium theory, auction theory) deal with these issues in depth. In line with the original plan, the focus of our research has been on the notions of stability and popularity of one- and two-sided markets, fair sharing, and social choice. We have developed algorithms that find solutions to different scenarios in diverse market situations. In addition to introducing new tools (e.g. parametric complexity theory) to analyse the complexity of finding these solutions, we have developed both practical solutions and, for several articles, solutions to real problems that were then indeed used in applications. The 5 permanent members of the group and 5 (occasionally changing) students have published a total of 41 papers on the project topics.
Full text https://otka-palyazat.hu/download.php?type=zarobeszamolo&projektid=128611
Decision
Yes





 

List of publications

 
Á. 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




Back »