{
  "annotation_id": "0afa09e3-02ce-4e45-a2f4-77a35693f3c0",
  "date_created": "2026-02-17T05:53:20.536000Z",
  "date_modified": "2026-02-17T05:53:20.536000Z",
  "file_hash": "69b34374d6acf99679f6b7ec7565a92256beebc65b1cbbce5bc6bc772f2156ef",
  "private": false,
  "record": {
    "abstract": "We study the problem of allocating $m$ indivisible goods among $n$ agents, where each agent\u0027s valuation is fractionally subadditive (XOS). With respect to AnyPrice Share (APS) fairness, Kulkarni et al. (2024) 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 (2025) 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. (2019) 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.",
    "arxiv_id": "2601.09299",
    "authors": [
      "Ziheng Chen",
      "Bo Li",
      "Zihan Luo",
      "Jialin Zhang"
    ],
    "categories": [
      "cs.GT"
    ],
    "license": "http://arxiv.org/licenses/nonexclusive-distrib/1.0/",
    "title": "On the Fair Allocation to Asymmetric Agents with Binary XOS Valuations",
    "url": "https://arxiv.org/abs/2601.09299",
    "version": "v1"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "1bcd9a22-cd22-4881-9934-fc7aed5e796f",
    "id": "arXiv Dataset",
    "type": "Model",
    "variant": "snapshot-2026-01-17",
    "version": "0.1.0"
  },
  "user_id": 1000002
}