On the Fair Allocation to Asymmetric Agents with Binary XOS Valuations

We study the problem of allocating m indivisible goods among n agents, where each agent's valuation is fractionally subadditive (XOS). With respect to AnyPrice Share (APS) fairness, Kulkarni et al. [22] showed that, when agents have binary marginal values, a 0.1222-APS allocation can be found in polynomial time, and there exists an instance where no allocation is better than 0.5-approximate APS. Very recently, Feige and Grinberg [12] extended the problem to the asymmetric case, where agents may have different entitlements, and improved the approximation ratio to 1/6 for general XOS valuations. In this work, we focus on the asymmetric setting with binary XOS valuations, and further improve the approximation ratio to 1/2, which matches the known upper bound. We also present a polynomial-time algorithm to compute such an allocation. Beyond APS fairness, we also study the weighted maximin share (WMMS) fairness. Farhadi et al. [10] showed that a 1/n-WMMS allocation always exists for agents with general additive valuations, and that this approximation ratio is tight. We extend this result to general XOS valuations, where a 1/n-WMMS allocation still exists, and this approximation ratio cannot be improved even when marginal values are binary. This shows a sharp contrast to binary additive valuations, where an exact WMMS allocation exists and can be found in polynomial time.

Paper

Similar papers

© 2026 NYSGPT2525 LLC