Algorithmen für faire Zuweisung unteilbarer Güter
Zusammenfassung der Projektergebnisse
Fair Division, d.h. gerechtes Verteilen von Dingen an Agenten, ist ein klassisches Gebiet im Schnittbereich aus Mikroökonomie und Informatik mit vielen wichtigen Anwendungen. Problemstellungen mit unteilbaren Gütern haben in den letzten Jahren viel Aufmerksamkeit erhalten, da neue Konzepte und Kriterien für solche Aufteilungen entwickelt wurden. In diesem Projekt entwickeln wir neue algorithmische Techniken zur Lösung von Fair-Division-Problemen und erzielen Ergebnisse zur Berechnungskomplexität. Allokationen, die den sog. Nash Social Welfare maximieren, erfüllen eine Reihe von Fairness- und Optimalitätsgarantien. Für die Berechnung einer solchen optimalen Allokation liefern wir eine vollständige Charakterisierung der Komplexität in sog. 2-valued-Instanzen. In 2-valued-Instanzen hat jeder Agent eine additive Bewertungsfunktion. Jedes Gut hat einen Wert, gegeben durch eine von zwei positiven ganzen Zahlen p, q, mit p > q. Wir erhalten einen überraschenden Kontrast: Für q = 1 oder q = 2 ist die Optimierung effizient durch Greedy-Algorithmen umsetzbar. Für q ≥ 3 ist sie NP-hart. Daneben untersuchen wir neue Fairnessgarantien. Die Bedeutung von „Fairness“ ist oft diskutabel, daher gibt es viele verschiedene Fairnesskonzepte. Viele konzentrieren sich auf die Vermeidung von Neid (engl. envy) unter den Agenten. Wir definieren und entwickeln effiziente Algorithmen für eine epistemische Variante des notorisch schwierigen Kriteriums der sog. Envy-Freeness bis auf jedes Gut (EFX). Unsere Resultate zeigen, dass epistemisches EFX deutlich bessere Eigenschaften hat im Sinne der Existenz und der Berechnungskomplexität. Wir nutzen Randomisierung für die Erzielung von Fairnesskriterien. Randomisierte Allokationen sollen gleichzeitig starke Garantien der Envy-Freeness im Erwartungswert (ex-ante) und relaxierte Garantien für jede einzelne Allokation im Träger (ex-post) erzielen. Unsere Arbeiten liefern effiziente Algorithmen zur Berechnung, sogar wenn Agenten verschiedene Prioritäten oder Anrechte auf den zu erzielenden Wert haben. Darüber hinaus erzielen wir noch weitere Resultate in verwandten Gebieten. Wir betrachten envy-freie und Pareto-optimale Allokationen für teilbares Mixed Manna, das aus teilbaren Dingen mit positivem (Güter) oder negativem Wert (Hausarbeiten) besteht. Wir entwickeln effiziente Algorithmen zur Berechnung in mehreren Fällen: (1) konstant viele Agenten, (2) konstant viele Dinge, (3) konstant viele Arbeiten, die die Allokation dominieren (aber beliebig viele Güter und/oder Agenten). Diese Resultate gelten sogar, wenn die Agenten für Güter nicht nur lineare, sondern SPLC-Bewertungen haben. Allgemeiner liefern unsere Arbeiten Beiträge zum verwandten Gebiet der hedonischen Spiele, in dem wir die Existenz und Berechnungskomplexität von stabilen Aufteilungen der Agentenmenge untersuchen. Die Anwendung von Ideen aus der Lerntheorie auf dieses Gebiet ist ein besonderer Fokus unserer Arbeiten.
Projektbezogene Publikationen (Auswahl)
-
When Dividing Mixed Manna Is Easier Than Dividing Goods: Competitive Equilibria with a Constant Number of Chores. Lecture Notes in Computer Science, 329-344. Springer International Publishing.
Garg, Jugal; Hoefer, Martin; McGlaughlin, Peter & Schmalhofer, Marco
-
Approximate Strategyproof Mechanisms for the Additively Separable Group Activity Selection Problem. Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, 300-306. International Joint Conferences on Artificial Intelligence Organization.
Flammini, Michele & Varricchio, Giovanna
-
Maximizing Nash Social Welfare in 2-Value Instances. Proceedings of the AAAI Conference on Artificial Intelligence, 36(5), 4760-4767.
Akrami, Hannaneh; Chaudhury, Bhaskar Ray; Hoefer, Martin; Mehlhorn, Kurt; Schmalhofer, Marco; Shahkarami, Golnoosh; Varricchio, Giovanna; Vermande, Quentin & Wijland, Ernest van
-
Competitive Equilibria with a Constant Number of Chores. Journal of Artificial Intelligence Research, 78, 1201-1219.
Garg, Jugal; McGlaughlin, Peter; Hoefer, Martin & Schmalhofer, Marco
-
New Fairness Concepts for Allocating Indivisible Items. Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, 2554-2562. International Joint Conferences on Artificial Intelligence Organization.
Caragiannis, Ioannis; Garg, Jugal; Rathi, Nidhi; Sharma, Eklavya & Varricchio, Giovanna
-
PAC Learning and Stabilizing Hedonic Games: Towards a Unifying Approach.. Proceedings of the AAAI Conference on Artificial Intelligence, 37(5), 5641-5648.
Fioravanti, Simone; Flammini, Michele; Kodric, Bojana & Varricchio, Giovanna
-
ε-fractional core stability in hedonic games. In Proc. Conf. Adv. Neural Inf. Processing Syst. (NeurIPS), pages 28723– 28734
S. Fioravanti, M. Flammini, B. Kodric & G. Varricchio
-
Best of Both Worlds: Agents with Entitlements. Journal of Artificial Intelligence Research, 80, 559-591.
Hoefer, Martin; Schmalhofer, Marco & Varricchio, Giovanna
-
Solving Woeginger’s hiking problem: Wonderful partitions in anonymous hedonic games. In Proc. 51st Int. Colloq. Autom. Lang. Programming (ICALP), volume 297 of LIPIcs, pages 48:1– 48:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik
A. Constantinescu, P. Lenzner, R. Reiffenhäuser, D. Schmand & G. Varricchio
-
Maximizing Nash Social Welfare in 2-Value Instances: Delineating Tractability. Mathematics of Operations Research.
Akrami, Hannaneh; Chaudhury, Bhaskar Ray; Hoefer, Martin; Mehlhorn, Kurt; Schmalhofer, Marco; Shahkarami, Golnoosh; Varricchio, Giovanna; Vermande, Quentin & van, Wijland Ernest
