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.