2025/06/20 by Paul W. Goldberg, Kasper Høgh, Alexandros Hollender · 1 voice
Computer Science · Decision Sciences · #Auction Theory and Applications #Game Theory and Applications #Multi-Agent Systems and Negotiation
paper · doi:10.1016/j.tcs.2025.115367
openalex publication_date 2025/06/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/23
We consider the problem of sharing a set of indivisible goods among agents in a fair manner, namely such that the allocation is envy-free up to any good (EFX). We focus on the problem of computing an EFX allocation in the two-agent case and characterize the computational complexity of the problem for most well-known valuation classes. We present a simple greedy algorithm that solves the problem when the agent valuations are weakly well-layered, a class which contains gross substitutes and budget-additive valuations. For the next largest valuation class we prove a negative result: the problem is PLS -complete for submodular valuations. All of our results also hold for the setting where there are many agents with identical valuations. • We study the computational complexity of computing EFX allocations for two agents. • When the two agents have submodular valuations, we show that computing an EFX allocation is PLS-complete. • The problem can be solved efficiently when the two agents have gross substitutes or budget-additive valuations.