Servicenavigation

Project Details

Back

Projekt Print View

Algorithms for Fair Allocation of Indivisible Goods

Subject Area Theoretical Computer Science
Term from 2020 to 2024
Project identifier Deutsche Forschungsgemeinschaft (DFG) - Project number 431465915
 
Final Report Year 2024

Final Report Abstract

Fair division is a classic area at the intersection of microeconomics and computer science with many important applications. The fair allocation of indivisible items has recently gained a lot of research interest due to the development of novel concepts and criteria. In this project, we develop new efficient algorithms for such problems and provide results characterizing their computational complexity. Allocations that maximize the so-called Nash social welfare are known to provide several attractive fairness and optimality guarantees. We provide a complete characterization of the computational complexity of maximizing the Nash social welfare for a class of 2-valued instances. In 2-valued instances, each agent has an additive valuation. Every item has a value given by one of two positive integer values p, q with p > q. We discover a fascinating dichotomy: if q = 1 or q = 2, the problem can be solved efficiently with greedy algorithms. For q ≥ 3 the problem becomes NP-hard. Moreover, we propose and study new fairness guarantees. Since the details of what fairness means can certainly be a matter of debate, there exist many fairness concepts, many of them focusing on the idea of avoiding envy in the agent population. We define and propose efficient algorithms for an epistemic version of the notoriously complicated notion of envy-freeness up to any good (EFX). Our results show that epistemic EFX has much more attractive properties in terms of existence and computational complexity. We explore the power of randomization to obtain randomized allocations that simultaneously satisfy strong notions of envy-freeness in expectation (ex-ante) as well as relaxed versions for every allocation in the support (ex-post). We provide efficient algorithms to compute such allocations, even when agents have different entitlements or priorities for obtaining utility. Finally, we also provide contributions to related areas. We consider envy-free and Paretooptimal allocations for fair division of divisible mixed manna, which consists of items that can be goods or chores for the agents. We provide polynomial-time algorithms to compute such allocations in several classes, (1) when there is a constant number of agents, (2) when there is a constant number of items, or (3) when there is a constant number of chores dominating the allocation in the market (but any number of goods and/or agents). Notably, these results hold even when the agents have separable piecewise-linear concave (SPLC) utilities for goods. More generally, we also provide new insights in the related domain of hedonic games, in which we study the existence and computational complexity of computing stable partitions among a set of agents. The application of ideas from learning theory to such games is a focus of our work.

Publications

 
 

Additional Information

© 2026 DFG Disclaimer / Copyright / Privacy Policy

Textvergrößerung und Kontrastanpassung