Share-based and envy-based approaches to fair division of indivisible goods

Abstract

The fair allocation of resources among agents with individual preferences is a fundamental problem at the intersection of computer science, social choice theory, and economics. This dissertation examines scenarios where the resources to be allocated are a set of indivisible goods. Two primary categories of fairness concepts are considered: share-based and envy-based criteria. Each category encompasses desirable notions of fairness, each with distinct advantages and limitations. In the first part of the dissertation, we study a share-based fairness notion known as the maximin share (MMS). Since MMS allocations do not always exist, we study relaxed MMS allocations and establish positive results in various settings. In particular, we establish the existence of (3/4 + 3/3836)-MMS allocations for agents with additive valuations, and (3/13)-MMS allocations for agents with fractionally subadditive (XOS) valuations. In addition, we consider ordinal approximations of MMS and prove the existence of 1-out-of-4⌈n/3⌉ MMS allocations in the additive setting. The second part of the dissertation focuses on envy-based fairness notions. For indivisible items, the most prominent envy-based criterion is envy-freeness up to any item (EFX). Although the existence of EFX allocations remains open in many general settings, we contribute to this area by proving the existence of EFX allocations for three agents under minimal constraints on their valuations. Furthermore, we establish the existence of relaxed forms of EFX, including epistemic EFX, and approximate EFX with charity. In the third and final part of this thesis, we move beyond single fairness criteria—whether share-based or envy-based—to establish the existence of allocations that satisfy multiple fairness guarantees. Specifically, we prove the existence of (partial) allocations that are 2/3-MMS and EFX simultaneously. This line of research, while less established, represents a promising direction for future research.

Die faire Aufteilung von Ressourcen zwischen Akteuren mit individuellen Präferenzen ist ein grundlegendes Problem an der Schnittstelle von Informatik, Sozialwahltheorie und Wirtschaftswissenschaften. In dieser Dissertation werden Szenarien untersucht, in denen die zu verteilenden Ressourcen eine Reihe von unteilbaren Gütern sind. Es werden zwei Hauptkategorien von Fairnesskonzepten betrachtet: anteilsbasierte und neidbasierte Kriterien. Jede Kategorie umfasst wünschenswerte Vorstellungen von Fairness, die jeweils ihre eigenen Vorteile und Grenzen haben. Im ersten Teil dieser Arbeit untersuchen wir einen anteilsbasierten Fairnessbegriff, der als Maximin-Share (MMS) bekannt ist. Da MMS-Zuteilungen nicht immer existieren, untersuchen wir relaxierte MMS-Zuteilungen und zeigen positive Ergebnisse in verschiedenen Situationen. Insbesondere beweisen wir die Existenz von (3/4 + 3/3836)-MMS-Zuteilungen für Agenten mit additiven Bewertungen und (3/13)-MMS-Zuteilungen für Agenten mit fraktionell subadditiven (XOS) Bewertungen. Zusätzlich betrachten wir ordinale Approximationen von MMS und beweisen die Existenz von 1-aus-4⌈n/3⌉ MMS-Zuteilungen in dem additiven Fall. Der zweite Teil der Dissertation befasst sich mit neidbasierten Fairnesskonzepten. Für unteilbare Güter ist das bekannteste neidbasierte Kriterium die Neidfreiheit bis auf ein beliebiges Gut (EFX). Obwohl die Existenz von EFX-Zuteilungen in vielen allgemeinen Kontexten offen bleibt, leisten wir einen Beitrag zu diesem Gebiet, indem wir die Existenz von EFX-Zuteilungen für drei Agenten unter minimalen Beschränkungen ihrer Bewertungen beweisen. Darüber hinaus etablieren wir die Existenz von relaxierten Formen von EFX, einschließlich epistemischem EFX, und approximiertem EFX mit Spenden. Im dritten und letzten Teil dieser Arbeit gehen wir über einzelne Fairnesskriterien hinaus — sei es anteilsbasiert oder neidbasiert — und beweisen die Existenz von Zuteilungen, die mehrere Fairnessgarantien erfüllen. Insbesondere beweisen wir die Existenz von (teilweisen) Zuteilungen, die gleichzeitig 2/3-MMS und EFX sind. Dieser Forschungszweig ist zwar weniger etabliert, stellt aber eine vielversprechende Richtung für zukünftige Forschung dar.