1 citations · 1 across the 11 of their papers we have counts for
12 papers
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…
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…
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…
Gabow's Cardinality Matching Algorithm in General Graphs: Implementation and Experiments
Matin Ansaripour, Alireza Danaei, Kurt Mehlhorn
It is known since 1975 (\cite{HK75}) that maximum cardinality matchings in bipartite graphs with nodes and edges can be computed in time . Asymptotically fas…
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…