In classical fair division, economics and computer science operate in tidy, isolated silos. In one silo, agents divide a collection of desirable "goods" (like jewelry or computing resources), where more is always better. In another, they divide undesirable "chores" (like hospital shifts or household cleaning), where less is always better.
But real-world allocation problems rarely respect these boundaries. A divorce settlement or an estate division contains both valuable assets (houses, cash) and burdensome liabilities (mortgages, debts). Furthermore, valuations are often subjective: a house in the countryside might be a highly prized good to one heir but an unwanted maintenance chore to another.
When we mix goods and chores—a scenario known as allocating mixed manna—or when we mix divisible resources (like money) with indivisible items (like cars), the mathematical foundations of fair division fracture. This article explores why this mixture breaks traditional algorithms and how recent research builds unified frameworks to restore fairness guarantees.
Why Mixed Manna Breaks Traditional Fair Division
To understand why mixed manna is difficult, consider how we define fairness. Two pillars of fair division are envy-freeness (no agent prefers another's bundle) and proportionality (every agent receives their fair share of the total utility).
When dealing purely with goods, algorithms typically allocate items to the agents who value them most. For chores, the logic must be completely inverted: burdens are assigned to the agents who dislike them least.
When goods and chores are combined, this clean algorithmic separation vanishes. As noted in a survey by Shengxin Liu et al., standard protocols optimized for a single utility type fail because the mathematical properties change when negative utilities are introduced. For instance, the objective functions lose monotonicity—adding an item to a bundle might make it better or worse depending on whether it is a good or a chore to that specific agent. This subjectivity is highlighted by Hadi Hosseini et al., who show that disagreements over whether an item is a benefit or a burden heavily complicate standardizing preferences.
Navigating the Non-Convex Landscape of Mixed Utilities
How do we find a competitive equilibrium—a state where prices clear the market and everyone is satisfied with their affordable bundle—when items can have negative utility?
In pure goods markets, finding an equilibrium can often be framed as maximizing a convex objective function (such as the Nash social welfare). However, introducing chores warps this optimization landscape into a non-convex space, creating severe computational hurdles.
To bypass this, Bhaskar Ray Chaudhury et al. formulated the mixed manna equilibrium problem as a Linear Complementarity Problem (LCP). By applying Lemke's scheme—a classic pivoting algorithm akin to the Simplex method—the authors provided a constructive proof that competitive equilibria always exist for mixed manna, settling long-standing conjectures about the structure of these markets.
Another breakthrough comes from designing sign-agnostic frameworks. Instead of treating positive and negative utilities with completely different mathematical machinery, Rucha Kulkarni et al. demonstrated that mixed resource allocation can be reduced to a constrained version of goods-only allocation. This insight allowed them to develop a Polynomial-Time Approximation Scheme (PTAS) for the Maximin Share (MMS) guarantee, proving that the same underlying mathematical structures can handle both resource distribution and burden sharing simultaneously.
Relaxing Fairness for Discrete Mixtures
When items are indivisible (you cannot cut a car or a specific chore in half), perfect envy-freeness is often mathematically impossible. If there is only one prize, someone will be envious. To handle this, researchers developed relaxations like Envy-Freeness up to One Item (EF1) or Envy-Freeness up to Any Item (EFX).
In the mixed setting, these relaxations must be carefully re-engineered. Haris Aziz 0001 et al. proved that an allocation that is both Pareto optimal (efficient) and proportional up to one item always exists and can be computed in polynomial time, even when agents have asymmetric weights or entitlements. For stronger guarantees like EFX and Proportionality up to any item (PropMX), Ruta Mehta et al. designed polynomial-time algorithms for restricted and separable valuation classes, bridging a major gap in how discrete mixtures are handled.
Bridging the Continuous and the Discrete
A parallel challenge in mixed fair division is the co-existence of divisible resources (like cash or land) and indivisible items (like houses or artwork). Traditional models treat these as entirely separate domains: "cake-cutting" for continuous resources and discrete assignment for indivisible items.
To bridge this binary divide, Xiaohui Bei et al. introduced a hybrid fairness framework called Envy-Freeness for Mixed goods (EFM).
The intuition behind EFM is elegant: it recognizes that divisible goods act as a "buffer" or "lubricant" to smooth out the envy caused by lumpy, indivisible goods. If a bundle contains divisible resources, you can fine-tune it to eliminate envy exactly. If it doesn't, you accept an EF1 relaxation. Specifically, EFM enforces strict, exact envy-freeness on any bundle that contains divisible resources, while allowing a relaxed, one-item margin of error only for bundles consisting entirely of indivisible items. This dual-standard ensures that the presence of flexible, divisible resources forces a higher level of equitable distribution, guaranteeing that an EFM allocation always exists.
Taking this unification a step further, Bo Li 0037 et al. introduced a personalized indivisibility ratio ($\alpha$). This parameter smoothly interpolates between classical cake-cutting ($\alpha = 0$) and pure discrete item allocation ($\alpha = 1$). By defining new criteria like $EF\alpha$ and $PROP\alpha$, the authors created a flexible mathematical bridge that allows algorithms to scale fluidly depending on the composition of the hybrid resource pool.
By moving past the artificial boundaries of "pure goods" or "pure chores," and "purely continuous" or "purely discrete" resources, mixed fair division provides a much more realistic toolkit for social choice. Whether through sign-agnostic reductions, LCP formulations, or hybrid fairness criteria like EFM, these mechanisms prove that we can systematically navigate the messy, subjective realities of real-world allocation.
Key Foundational Work
Fair Division of Mixed Divisible and Indivisible Goods (2020) — contributed 4 concept elements to this direction.
Competitive Allocation of a Mixed Manna (2020) — contributed 1 concept elements to this direction.
A polynomial-time algorithm for computing a Pareto optimal and almost proportional allocation (2019) — contributed 1 concept elements to this direction.