Best-of-Both-Worlds Fairness for Mixed Goods and Chores

Haris Aziz, Xiaolin Bu, Xinhang Lu, Simon Mackenzie, Mashbat Suzuki, Biaoshuai Tao, Toby WalsharXiv 2026 · arXiv

TL;DR

This paper resolves a major open question in fair division by proving that you can achieve perfect fairness in expectation (ex-ante envy-freeness) while guaranteeing near-perfect fairness in reality (ex-post envy-freeness up to one item) for a mix of indivisible goods and chores. The authors achieve this "best-of-both-worlds" guarantee by introducing a novel probabilistic Hall-type matrix decomposition that intricately correlates how goods and chores are bundled and randomized.

What Problem Does This Paper Address?

How do you fairly divide a set of indivisible items when one person's trash is another person's treasure? In the "mixed goods and chores" setting, an item might bring positive utility to Agent A (a good) but negative utility to Agent B (a chore)—think of a risky financial asset, or a household task like cooking.

Achieving perfect fairness (Envy-Freeness, or EF) is mathematically impossible with indivisible items (e.g., you cannot split a single item without making someone envious). To circumvent this, researchers look at randomized allocations (lotteries). A "Best-of-Both-Worlds" (BoBW) approach seeks a lottery that is perfectly fair ex ante (in expectation, before the draw) and approximately fair ex post (after the draw, satisfying Envy-Freeness up to one item, or EF1).

While BoBW solutions existed for instances with purely goods or purely chores, combining them has been a major challenge. Simply running independent lotteries for goods and chores degrades the ex-post guarantee to EF2 (envy up to two items). This paper tackles the challenge of tightly coordinating the two.

Methods

The authors develop a multi-stage algorithmic framework that splits the problem based on the number of objective chores ($n$ being the number of agents):

  1. Bundling Preprocessing: Items are carefully grouped into "meta-items" so that agents value at most one subjective good positively, and every subjective good is "chore-maximal" (meaning the addition of any chore makes its total value negative).
  2. The Easy Case ($\le n$ chores): Uses a distinct randomized combinatorial algorithm involving random agent sampling, a serial dictatorship to distribute goods, and a standard Probabilistic Serial (PS) lottery for leftovers.
  3. The Hard Case ($> n$ chores): Requires a synchronized rounding scheme. The authors introduce a novel Probabilistic Hall-Type Matrix Decomposition to intricately correlate the fractional assignments of goods and chores. To prove this decomposition exists, they:
  4. Lift discrete subset constraints into a continuous domain (Continuous Weighted Reformulation).
  5. Apply Sion's Minimax Theorem to swap optimization quantifiers, simplifying the search for a universal distribution into finding tailored distributions for fixed weight vectors.
  6. Route fractional flows through custom-designed Biased Flow Networks to ensure integrality.

Datasets

Not discussed in the paper. This is a purely theoretical paper containing mathematical proofs and algorithmic designs.

Key Insights and Ideas

  • The Necessity of Correlation: You cannot treat goods and chores as independent problems. To achieve tight ex-post fairness (EF1), the lottery must dynamically couple them—an agent should only be allocated a subjective good if they are simultaneously saddled with a chore that offsets its value.
  • Probabilistic Hall's Condition: The paper introduces a brilliant probabilistic analog to Hall's Marriage Theorem. Instead of ensuring a deterministic matching exists, it mathematically bounds the probability of a randomized matching overly concentrating on any specific subset of agents.
  • Duality to the Rescue: Solving the exponential family of constraints required for this correlated lottery seems intractable. By leveraging continuous minimax duality (Sion's Theorem), the authors simplify the task from finding one universal distribution to finding a tailored distribution for a fixed weight vector, which can then be solved via network flows.

Key Results

  • Theorem 1.1 (Main Result): Proves that ex-ante EF and ex-post EF1 are fully compatible for mixed goods and chores under additive valuations.
  • Ordinal vs. Cardinal Gap: In Appendix B, the authors evaluate an ordinal preference setting (where agents only rank items without numerical values). They prove a strict negative result: ex-ante Stochastic Dominance EF (SD-EF) is incompatible with ex-post SD-EF1, making ex-post SD-EF2 the best possible guarantee under ordinal preferences.

Limitations and Future Work

  • Computational Complexity: While the network-flow subproblems can be solved in polynomial time, the overall probabilistic Hall-type decomposition currently requires explicit enumeration of constraints, leading to an exponential-time algorithm. Developing a polynomial-time compact or oracle-based implementation is a primary open direction.
  • Economic Efficiency: The paper focuses entirely on fairness. Combining these guarantees with Pareto Optimality (PO) remains an open challenge for mixed goods and chores.
  • Beyond Additive Utilities: The current proofs rely heavily on additive utility functions. Exploring more general utility functions (like subadditive or monotone valuations) is a promising future path.

Summary updated

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.
BibTeX
@misc{aziz2026best,
  author = {Haris Aziz and Xiaolin Bu and Xinhang Lu and Simon Mackenzie and Mashbat Suzuki and Biaoshuai Tao and Toby Walsh},
  title = {{Best-of-Both-Worlds Fairness for Mixed Goods and Chores}},
  year = {2026},
  eprint = {2607.10232},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2607.10232},
}

Loading related content...

Figure