11 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…
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…
Optimizing Car Resequencing on Mixed-Model Assembly Lines: Algorithm Development and Deployment
Andreas Karrenbauer, Bernd Kuhn, Kurt Mehlhorn +1
The mixed-model assembly line (MMAL) is a production system used in the automobile industry to manufacture different car models on the same conveyor, offering a high degree of prod…