1 citations · 1 across the 11 of their papers we have counts for
10 papers · 1 filter
Polynomial Algorithms for Simultaneous Share-Based and Envy-Based Guarantees
Hannaneh Akrami, Arash Ashuri, Kurt Mehlhorn
We study the simultaneous achievement of share-based and envy-based fairness in the allocation of indivisible goods with nonnegative additive valuations. The AnyPrice share (APS) i…
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…
Complete EFX Allocations Exist for Four Additive Agents and Up to Nine Goods
Eyad Alkassar, Mahmoud Fouz, Kurt Mehlhorn
We prove that every fair-division instance with four agents, additive valuations over the non-negative reals, and at most nine indivisible goods admits a \emph{complete} allocation…
EFX Allocations Exist on Multi-Graphs
Mahyar Afshinmehr, Arash Ashuri, Pouria Mahmoudkhan +2
We study the fair allocation of indivisible goods among agents, with a focus on limiting envy. A central fairness notion is envy-freeness up to any good (EFX), which requires that…
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…
EFX Allocations Exist on Triangle-Free Multi-Graphs
Mahyar Afshinmehr, Arash Ashuri, Pouria Mahmoudkhan +1
We study the fair allocation of indivisible goods among agents, with a focus on limiting envy. A central open question in this area is the existence of EFX allocations-allocations…
Maximizing Nash Social Welfare in 2-Value Instances: A Simpler Proof for the Half-Integer Case
Kurt Mehlhorn
A set of indivisible goods is to be allocated to a set of agents. Each agent has an additive valuation function over goods. The value of a good for agent …
Approximate EFX and Exact tEFX Allocations for Indivisible Chores: Improved Algorithms
Mahyar Afshinmehr, Matin Ansaripour, Alireza Danaei +1
We explore the fair distribution of a set of indivisible chores among agents, where each agent's costs are evaluated using a monotone cost function. Our focus lies on two f…
MMS Approximations Under Additive Leveled Valuations
Mahyar Afshinmehr, Mehrafarin Kazemi, Kurt Mehlhorn
We study the problem of fairly allocating indivisible goods to a set of agents with additive leveled valuations. A valuation function is called leveled if and only if bundles of la…
Welfare-Optimal Serial Dictatorships have Polynomial Query Complexity
Ioannis Caragiannis, Kurt Mehlhorn, Nidhi Rathi
Serial dictatorship is a simple mechanism for coordinating agents in solving combinatorial optimization problems according to their preferences. The most representative such proble…