{"ID":6536398,"CreatedAt":"2026-07-14T01:21:01.169441415Z","UpdatedAt":"2026-07-14T08:33:44.272455028Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.10232","arxiv_id":"2607.10232","title":"Best-of-Both-Worlds Fairness for Mixed Goods and Chores","abstract":"We study the fundamental problem of fairly dividing indivisible items among agents with additive utilities. In our model, an item can be a good yielding non-negative utilities to some agents and simultaneously a chore yielding negative utilities to others. We take the best-of-both-worlds perspective and our goal is to construct a randomized allocation that is exactly fair ex ante while also being supported on ex post approximately fair allocations. The fairness notions examined in this paper are envy-freeness (EF) and its well-known relaxation envy-freeness up to one item (EF1). Our main result is that ex-ante EF and ex-post EF1 can be achieved simultaneously. To achieve this, we introduce a novel probabilistic Hall-type matrix decomposition that intricately correlates the fractional assignments of goods and chores. We resolve this decomposition problem by combining continuous minimax duality -- via Sion's minimax theorem -- with carefully designed biased flow networks.","short_abstract":"We study the fundamental problem of fairly dividing indivisible items among agents with additive utilities. In our model, an item can be a good yielding non-negative utilities to some agents and simultaneously a chore yielding negative utilities to others. We take the best-of-both-worlds perspective and our goal is to...","url_abs":"https://arxiv.org/abs/2607.10232","url_pdf":"https://arxiv.org/pdf/2607.10232v1","authors":"[\"Haris Aziz\",\"Xiaolin Bu\",\"Xinhang Lu\",\"Simon Mackenzie\",\"Mashbat Suzuki\",\"Biaoshuai Tao\",\"Toby Walsh\"]","published":"2026-07-11T09:44:19Z","proceeding":"cs.GT","tasks":"[\"cs.GT\"]","methods":"[]","has_code":false}