10 papers
A Simple Polynomial-Time EFX Repair for Cancelable Valuations
Hannaneh Akrami, Arash Ashuri, Bhaskar Ray Chaudhury +2
The leximin++ proof of Plaut and Roughgarden for agents with identical monotone valuations gives a natural EFX-repair procedure: starting from an arbitrary partition, repeatedly tr…
A Counterexample to EFX Agents, Items, Submodular Valuations via SAT-Solving
Hannaneh Akrami, Alexander Mayorov, Kurt Mehlhorn +2
The existence of EFX allocations is a central open problem in discrete fair division. An allocation is EFX (envy-free up to any good) if no agent envies another agent after the rem…
Simultaneous Ordinal Maximin Share and Envy-Based Guarantees
Hannaneh Akrami, Timo Reichert
We study the fair allocation of indivisible goods among agents with additive valuations. The fair division literature has traditionally focused on two broad classes of fairness not…
Fair Division via Resource Augmentation
Hannaneh Akrami, Siddharth Barman, Alon Eden +5
We introduce and formalize the notion of resource augmentation for maximin share (MMS) fairness for the allocation of indivisible goods. Given an instance with agents and g…
Maximizing Nash Social Welfare in 2-Value Instances: Delineating Tractability
Hannaneh Akrami, Bhaskar Ray Chaudhury, Martin Hoefer +6
We study the problem of allocating a set of indivisible goods among a set of agents with \emph{2-value additive valuations}. In this setting, each good is valued either or $p/q…
The Power of Share-Based Notions in Proving Envy-Based Fairness Guarantees
Hannaneh Akrami, Uriel Feige, Ryoga Mahara +2
We study the problem of fairly allocating indivisible goods among agents with monotone valuations. We introduce a new share-based fairness notion, the residual maximin share (RMMS)…