📈 economics

Fair Allocation with Optional Selling

This paper investigates fair allocation of indivisible goods where agents can choose to sell items at market prices, adapting standard fairness notions like MMS and EFX to this hybrid setting and establishing existence guarantees and approximation bounds for allocations that balance the distribution of goods and proceeds.

Original authors: Uriel Feige, Yotam Gafni

Published 2026-08-26

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Uriel Feige, Yotam Gafni

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Fair division is a field of mathematics and economics dedicated to solving a problem as old as human cooperation: how to split resources so that everyone feels they have received a fair share. For decades, researchers have studied how to divide things that cannot be cut, like a house, a car, or a collection of rare books. In these scenarios, the goal is to find an arrangement where no one feels envious of what another person received, or where everyone is guaranteed a minimum level of satisfaction based on their own personal preferences. However, these classic models assume that the items in question are stuck in their current form. They ignore a very common real-world option: the ability to sell an item for cash. In a divorce, for instance, a couple might decide that selling the family home and splitting the money is a better solution than one person keeping the house and the other getting nothing. This simple option of selling changes the entire landscape of what is possible, but it also introduces new complexities that previous theories did not address.

Uriel Feige and Yotam Gafni from the Weizmann Institute of Science have stepped into this gap to explore what happens when agents can choose to sell goods at market prices before dividing the remaining items and the resulting cash. Their work asks a fundamental question: if people can sell items, does it become easier or harder to guarantee a fair outcome? They found that while selling opens up more possibilities, it actually makes it harder to guarantee certain types of fairness compared to the traditional setting where selling is forbidden. The researchers developed new ways to measure fairness that account for both the value of the items people keep and the money they receive from sales. They proved that for two people, it is always possible to find a division that satisfies the strongest possible fairness standards, ensuring no one envies another's bundle even after considering the option to sell. However, as the number of people increases, the guarantees become slightly weaker. For three people, they showed that it is impossible to guarantee that everyone gets their absolute maximum possible fair share; in some cases, the best anyone can hope for is a specific fraction of that ideal share.

The researchers also investigated how well they could approximate these fair shares for larger groups. They demonstrated that for any number of people, there is always a way to divide the goods and money so that everyone receives at least two-thirds of their guaranteed minimum share. This is a significant result because it shows that even with the added complexity of selling, a very high level of fairness is still achievable. Furthermore, they found that it is possible to combine this share-based fairness with a strong sense of envy-freeness, meaning that no one would prefer to swap their entire bundle of goods and cash with another person's. They achieved this by adapting an algorithm known as the "Lone Divider" method, which involves one person proposing a split and others choosing their preferred parts. In the new setting with selling, they had to modify this approach carefully, ensuring that the person proposing the split is chosen wisely and that the bundles are structured in a specific way to prevent the sale of items from unfairly hurting the remaining participants.

One of the most striking findings in the paper is the difference between the setting with selling and the setting without it. The authors constructed a specific example involving three people and eight items where, if selling were allowed, it would be impossible to guarantee that everyone gets more than eleven-twelfths of their ideal share. In the traditional setting where items cannot be sold, the best-known limit for this same scenario is much higher, meaning that the ability to sell actually creates a wider gap between what is theoretically possible and what can be guaranteed in practice. This counterintuitive result suggests that while selling offers flexibility, it also introduces a new kind of risk where high-value items might be sold for a low price, leaving the remaining items insufficient to satisfy everyone's needs. The researchers also explored a related scenario involving chores, or tasks that people dislike, where the option to outsource the work for a fee plays the same role as selling goods. They found similar patterns, showing that the ability to pay someone else to do a task makes it harder to guarantee a perfectly fair distribution of the remaining work.

The paper also addresses the practical side of these mathematical proofs, asking whether these fair allocations can be calculated efficiently by a computer. The authors showed that for the specific case of two people, a fair division can be found in a reasonable amount of time. For larger groups, they developed algorithms that can get arbitrarily close to the ideal fair share, meaning that with enough computing power, one can find a solution that is almost as good as the theoretical best. They also proved that a specific type of fairness guarantee, based on a truncated proportional share, can be computed quickly and combined with envy-free conditions. This work provides a robust framework for understanding how markets and personal preferences interact in fair division problems, offering new tools for situations ranging from divorce settlements to the division of inherited assets. By rigorously defining what is possible when selling is an option, the researchers have clarified the limits of fairness in a world where resources can be converted into money, ensuring that we know exactly what guarantees we can rely on when the stakes are high.

Technical Summary: Fair Allocation with Optional Selling

Problem Definition

This paper addresses the problem of fair allocation of indivisible goods in a setting where agents possess subjective valuation functions over the goods, but the goods also have exogenous market prices. Unlike traditional fair division models where goods are strictly indivisible, this setting introduces an "outside option": agents can choose to sell goods at their market prices. The proceeds from these sales are divisible and have a uniform additive value for all agents.

The core challenge is to design an allocation mechanism that simultaneously decides:

Which subset of goods to sell.
How to allocate the remaining unsold goods.
How to distribute the monetary proceeds from the sold goods.

The objective is to satisfy fairness notions that adapt standard share-based and envy-based guarantees to this hybrid environment. The authors assume additive valuations for both goods and money.

Fairness Notions

The paper adapts two categories of fairness definitions:

Share-Based Notions:
- Maximin Share (MMS): Defined as the maximum value an agent can guarantee themselves by optimally deciding which goods to sell and then partitioning the remaining goods and proceeds into $n$ bundles, receiving the least valuable one. Unlike the standard MMS, the agent optimizes both the selling decision and the partition.
- Truncated Proportional Share (TPS): An extension of the TPS concept from indivisible settings, defined as the largest value $t$ such that the sum of $\max\{p(g), \min\{v(g), t\}\}$ over all goods, divided by $n$ , equals $t$ .
Envy-Based Notions:
- SEF1 and SEFX (Strong/Sellable Envy-Free): These are adaptations of EF1 and EFX. An allocation is SEFX if for any agent $i$ and any other agent $j$ , $i$ does not envy $j$ 's bundle even if $j$ were to sell one of their goods (and receive the market price) instead of keeping it. Formally, $\bar{v}_i(A_i) + P_i \ge \bar{v}_i(A_j \setminus \{g\}) + p(g)$ for every good $g \in A_j$ , where $\bar{v}_i(g) = \max\{v_i(g), p(g)\}$ .

Methodology and Algorithms

The authors employ a variety of algorithmic techniques, including variations of "Cut & Choose," "Bag-Filling," and "Lone Divider" paradigms, modified to handle the complexity introduced by optional selling.

Cut & Give (n=2): For two agents, the authors introduce a "Cut & Give" protocol. One agent (the Cutter) proposes a partition based on their MMS. If the other agent (the Giver) finds a bundle acceptable, they take it. If not, the Giver modifies the partition by selling their own intended good and canceling the Cutter's sale, creating a new bundle that satisfies both MMS and SEFX.
Bag-Filling with Virtual Goods (TPS): To achieve $n/(2n-1)$ -TPS, the algorithm uses a "moving knife" approach. Goods with high market prices are sold immediately to satisfy agents' minimum share requirements. Remaining proceeds are treated as "virtual goods." A bag-filling procedure then allocates bundles until an agent values them at the required threshold.
Canonical Partitions (Lone Divider for MMS): For general $n$ , the authors adapt the Lone Divider method. A key innovation is the construction of "canonical partitions" proposed by the agent with the highest MMS. These partitions consist of "pure bundles" (no money), "singleton bundles" (one good plus proceeds from at most one other sold good), and a single "leftovers" bundle. This structure limits the potential loss an agent suffers if a bundle they rejected is allocated to someone else, specifically bounding the loss caused by forced sales.
Handling High-Value Items: The algorithms include preliminary phases to handle goods with values significantly exceeding the MMS threshold, either by selling them to satisfy specific agents or allocating them directly, ensuring the remaining problem fits the approximation framework.

Key Results

1. Combined Share and Envy Guarantees

Two Agents ( $n=2$ ): There always exists an allocation that is simultaneously MMS and SEFX. This is a strong result, as achieving full MMS is generally impossible for $n \ge 3$ in standard settings, and here it is achieved alongside a strong envy-free notion.
General Agents ( $n \ge 2$ ): There exists an allocation that is simultaneously $n/(2n-1)$ -TPS and SEFX. The ratio $n/(2n-1)$ is proven to be the best possible approximation for TPS even without the SEFX requirement.

2. MMS Approximation Bounds

Three Agents ( $n=3$ ): The paper establishes a quantitative gap between settings with and without selling. While full MMS is guaranteed for $n=3$ with $m=8$ items in the standard indivisible setting (where the best known bound without selling is $39/40$ ), in the selling setting, there exist instances where no allocation guarantees more than $11/12$ -MMS.
General Agents ( $n \ge 4$ ): The authors provide a $2/3$ -MMS allocation. This matches the best known approximation ratio for the standard indivisible setting (without the $O(1/n)$ additive term found in some previous works).
Special Case ( $n=3$ ): By combining the general $n$ approach with the $n=2$ full-MMS algorithm, the authors achieve a $3/4$ -MMS allocation for three agents.

3. Computational Complexity

MMS Computation: Computing the exact MMS value is weakly NP-hard for $n=2$ $n = 2$ and strongly NP-hard for general $n$ $n$ . However, the paper provides:
- A pseudo-polynomial time algorithm for fixed $n$ .
- A Polynomial-Time Approximation Scheme (PTAS) for computing MMS values and partitions.
TPS Computation: TPS is efficiently computable in polynomial time.
Combined Guarantees: An FPTAS exists for allocations that are both $n/(2n-1)$ -TPS and $\epsilon$ -SEFX.

4. Extensions

Equal Proceeds: The paper analyzes a restricted setting where sale proceeds must be distributed equally among all agents. In this case, the approximation guarantee drops to $1/n$ -TPS, and the MMS guarantee can be significantly weaker than in the unrestricted case.
Chores with Outsourcing: The model is extended to chores (negative valuations) where agents can "outsource" tasks at a market cost. The results mirror the goods setting: a 2-MMS approximation is achievable, but the approximation gap is wider than in the standard indivisible chores setting.

Significance and Claims

The paper claims to provide a "Best of Both Worlds" framework for fair division when market options are available. Its primary contributions are:

Theoretical Gap Identification: It demonstrates that the introduction of selling options, while expanding the feasible set of outcomes, can paradoxically make it harder to approximate certain fairness guarantees (specifically MMS for $n=3$ ) compared to the purely indivisible setting.
Robust Algorithms: It develops novel algorithmic techniques (canonical partitions, modified Lone Divider) that successfully recover the best-known approximation ratios for MMS in the presence of selling, despite the added complexity of optimizing selling decisions.
Unified Fairness: It successfully integrates share-based guarantees (MMS/TPS) with strong envy-free notions (SEFX) in a single allocation, showing that high-quality share approximations do not necessarily preclude strong envy-freeness in this setting.

The authors emphasize that their results are tight in several cases (e.g., the $n/(2n-1)$ bound for TPS) and that the negative results (the $11/12$ gap for $n=3$ ) are provable limitations of the model, not just artifacts of current algorithmic limitations.