Author

Kurt Mehlhorn

3 papers indexed here

We haven’t gathered this author’s papers yet. Follow them and we’ll fetch their work.

Not the right person? Other researchers publish under this name.

Preprint Oct 2026

Polynomial Algorithms for Simultaneous Share-Based and Envy-Based Guarantees

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) is a strengthening of the maximin share (MMS). A polynomial-time algorithm is known to guarantee a $2n/(3n-1)$ approximation of APS, but with...

Hannaneh Akrami, Arash Ashuri, Kurt Mehlhorn · 0 citations

Preprint Aug 2026

Complete EFX Allocations Exist for Four Additive Agents and Up to Nine Goods

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 that is envy-free up to any good in the strong, zero-tolerant sense ($\EFXo$). The case $m=9=n+5$ lies beyond the previously known frontier...

Eyad Alkassar, Mahmoud Fouz, Kurt Mehlhorn · 2 citations

Preprint Aug 2026

A Simple Polynomial-Time EFX Repair for Cancelable Valuations

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 transfer an eligible item to a minimum-valued bundle. The procedure terminates, but the standard argument gives no polynomial bound on the num...

Hannaneh Akrami, Arash Ashuri, B. Chaudhury et al. · 0 citations