AAMAS Conference 2026 Conference Paper
On the Fair Allocation to Asymmetric Agents with Binary XOS Valuations
- Ziheng Chen
- Bo Li
- Zihan Luo
- Jialin Zhang
We study the problem of allocating𝑚 indivisible goods among 𝑛 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-APSallocationcanbefoundinpolynomialtime, andthereexists 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/𝑛-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/𝑛-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.