Hannaneh Akrami after the defense of her doctoral thesis. Photo: Private.
On March 13, 2025, Hannaneh Akrami successfully defended her PhD thesis entitled “Share-Based and Envy-Based Approaches to Fair Division of Indivisible Goods”. Hannaneh Akrami joined Saarland University and the Max Planck Institute for Informatics in 2019 as a doctoral candidate under the supervision of Professor Kurt Mehlhorn. She was a member of both the Saarbrücken Graduate School of Computer Science and the International Max Planck Research School on Trustworthy Computing. Her doctoral degree was awarded by Saarland University.
The abstract of her Thesis :
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 this thesis, 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-4n/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.
Editor:
Philipp Zapf-Schramm
Max Planck Institute for Informatics
Phone: +49 681 9325 5409
Email: pzs@mpi-inf.mpg.de