Finding fair and efficient allocations

Abstract

We study the problem of fair division, where the goal is to allocate a set of items among a set of agents in a ``fair" manner. In particular, we focus on settings in which the items to be divided are either indivisible goods or divisible bads. Despite their practical significance, both these settings have been much less investigated than the divisible goods setting. In the first part of the dissertation, we focus on the fair division of indivisible goods. Our fairness criterion is envy-freeness up to any good (EFX). An allocation is EFX if no agent envies another agent following the removal of a single good from the other agent's bundle. Despite significant investment by the research community, the existence of EFX allocations remains open and is considered one of the most important open problems in fair division. In this thesis, we make significant progress on this question. First, we show that when agents have general valuations, we can determine an EFX allocation with a small number of unallocated goods (almost EFX allocation). Second, we demonstrate that when agents have structured valuations, we can determine an almost EFX allocation that is also efficient in terms of Nash welfare. Third, we prove that EFX allocations exist when there are three agents with additive valuations. Finally, we reduce the problem of finding improved guarantees on EFX allocations to a novel problem in extremal graph theory. In the second part of this dissertation, we turn to the fair division of divisible bads. Like in the setting of divisible goods, competitive equilibrium with equal incomes (CEEI) has emerged as the best mechanism for allocating divisible bads. However, neither a polynomial time algorithm nor any hardness result is known for the computation of CEEI with bads. We study the problem of dividing bads in the classic Arrow-Debreu setting (a setting that generalizes CEEI). We show that in sharp contrast to the Arrow-Debreu setting with goods, determining whether a competitive equilibrium exists, is NP-hard in the case of divisible bads. Furthermore, we prove the existence of equilibrium under a simple and natural sufficiency condition. Finally, we show that even on instances that satisfy this sufficiency condition, determining a competitive equilibrium is PPAD-hard. Thus, we settle the complexity of finding a competitive equilibrium in the Arrow-Debreu setting with divisible bads.

Die Arbeit untersucht das Problem der gerechten Verteilung (fair division), welches zum Ziel hat, eine Menge von Gegenständen (items) einer Menge von Akteuren (agents) \zuzuordnen". Dabei liegt der Schwerpunkt der Arbeit auf Szenarien, in denen die zu verteilenden Gegenstände entweder unteilbare Güter (indivisible goods) oder teilbare Pflichten (divisible bads) sind. Trotz ihrer praktischen Relevanz haben diese Szenarien in der Forschung bislang bedeutend weniger Aufmerksamkeit erfahren als das Szenario mit teilbaren Gütern (divisible goods). Der erste Teil der Arbeit konzentriert sich auf die gerechte Verteilung unteilbarer Güter. Unser Gerechtigkeitskriterium ist Neid-Freiheit bis auf irgendein Gut (envy- freeness up to any good, EFX). Eine Zuordnung ist EFX, wenn kein Akteur einen anderen Akteur beneidet, nachdem ein einzelnes Gut aus dem Bündel des anderen Akteurs entfernt wurde. Die Existenz von EFX-Zuordnungen ist trotz ausgeprägter Bemühungen der Forschungsgemeinschaft ungeklärt und wird gemeinhin als eine der wichtigsten offenen Fragen des Feldes angesehen. Wir unternehmen wesentliche Schritte hin zu einer Klärung dieser Frage. Erstens zeigen wir, dass wir für Akteure mit allgemeinen Bewertungsfunktionen stets eine EFX-Zuordnung finden können, bei der nur eine kleine Anzahl von Gütern unallokiert bleibt (partielle EFX-Zuordnung, almost EFX allocation). Zweitens demonstrieren wir, dass wir für Akteure mit strukturierten Bewertungsfunktionen eine partielle EFX-Zuordnung bestimmen können, die zusätzlich effizient im Sinne der Nash-Wohlfahrtsfunktion ist. Drittens beweisen wir, dass EFX-Zuordnungen für drei Akteure mit additiven Bewertungsfunktionen immer existieren. Schließlich reduzieren wir das Problem, verbesserte Garantien für EFX-Zuordnungen zu finden, auf ein neuartiges Problem in der extremalen Graphentheorie. Der zweite Teil der Arbeit widmet sich der gerechten Verteilung teilbarer Pflichten. Wie im Szenario mit teilbaren Gütern hat sich auch hier das Wettbewerbsgleichgewicht bei gleichem Einkommen (competitive equilibrium with equal incomes, CEEI) als der beste Allokationsmechanismus zur Verteilung teilbarer Pflichten erwiesen. Gleichzeitig sind weder polynomielle Algorithmen noch Schwere-Resultate für die Berechnung von CEEI mit Pflichten bekannt. Die Arbeit untersucht das Problem der Verteilung von Pflichten im klassischen Arrow-Debreu-Modell (einer Generalisierung von CEEI). Wir zeigen, dass es NP-hart ist, zu entscheiden, ob es im Arrow-Debreu-Modell mit Pflichten ein Wettbewerbsgleichgewicht gibt { im scharfen Gegensatz zum Arrow-Debreu-Modell mit Gütern. Ferner beweisen wir die Existenz eines Gleichgewichts unter der Annahme einer einfachen und natürlichen hinreichenden Bedingung. Schließlich zeigen wir, dass die Bestimmung eines Wettbewerbsgleichgewichts sogar für Eingaben, die unsere hinreichende Bedingung erfüllen, PPAD-hart ist. Damit klären wir die Komplexität des Auffindens eines Wettbewerbsgleichgewichts im Arrow-Debreu-Modell mit teilbaren Pflichten.