Fairly dividing a set of indivisible items among multiple agents is a notoriously difficult problem in computational social choice. When agents can assign arbitrary numerical values to items, standard fairness criteria—such as envy-freeness or maximizing Nash Social Welfare (NSW)—frequently run into severe computational bottlenecks (NP-hardness) or existential impossibilities. The core issue is the infinite granularity of preferences: slight, asymmetric differences in how agents value items create complex trade-offs that make optimization landscapes highly fractured.
However, a powerful line of research demonstrates that restricting the granularity of preferences—specifically to binary valuations (where an item is either desired or not, $\{0, 1\}$) or bivalued utilities (where items or chores take one of two discrete values, such as $\{1, 2\}$ or "easy" vs. "difficult")—fundamentally transforms the mathematical landscape. Flattening the preference scale eliminates the traditional friction between fairness, efficiency, and algorithmic tractability.
Collapsing the Fairness Hierarchy
In general fair division, there is a strict hierarchy of relaxations for envy-freeness. An allocation is Envy-Free up to One Item (EF1) if any perceived envy can be eliminated by removing some single item from the envied agent's bundle. A stricter standard is Envy-Free up to Any Item (EFX), which requires that envy vanishes upon removing any single item from the envied bundle. Finding EFX allocations for arbitrary valuations is famously difficult, and proving their general existence remains an open problem.
Under binary valuations, this hierarchy completely collapses. As shown by Deligkas et al. in The Complexity of Fair Division of Indivisible Items with Externalities, when an agent views all desired items as having a uniform value of 1, removing any item that contributes to envy reduces the envied bundle's perceived value by exactly 1. Consequently, EF1 and EFX become mathematically identical. This equivalence bypasses the structural complexity of EFX, guaranteeing that fair outcomes not only exist but can be discovered via polynomial-time algorithms.
Bounding Utility Ratios and Price Dynamics
Many sophisticated fair division algorithms rely on market-clearing mechanisms, such as Competitive Equilibrium with Equal Incomes (CEEI). In these frameworks, items are assigned virtual prices, and agents spend a fixed budget to buy their preferred bundles. In general settings, price-adjustment algorithms can run into infinite or pseudo-polynomial loops because the ratio between two agents' valuations can be arbitrarily large or infinitesimally small.
Discretizing preferences to bivalued cost or utility structures fixes this issue by stabilizing the underlying dynamics:
- Strongly Polynomial Termination: Murhekar et al. demonstrate in Fair and Efficient Allocations of Chores under Bivalued Preferences that limiting costs to two distinct levels strictly bounds the possible ratios of agent utilities. This structural constraint ensures that price-adjustment processes terminate in strongly polynomial time, rather than depending on the magnitude of the utilities.
- Chore Allocation Tractability: For the allocation of chores (items with negative utility), the tension between efficiency (Pareto optimality) and fairness is particularly acute. However, Ebadian et al. show in How to Fairly Allocate Easy and Difficult Chores and Murhekar shows in Fair and Efficient Chore Allocation: Existence and Computation that bivalued cost functions guarantee the polynomial-time computability of allocations that are simultaneously Pareto optimal and EF1.
- Approaching EFX for Chores: Even the elusive EFX standard becomes highly manageable under these constraints. Wu et al. leverage bivalued costs in Approximately EFX and fPO Allocations for Bivalued Chores to compute near-optimal EFX allocations alongside fractional Pareto optimality (fPO).
Aligning Incompatible Social Choice Objectives
In mechanism design, a fundamental trilemma usually dictates that an allocation rule cannot simultaneously achieve economic efficiency (Pareto optimality), fairness (envy-freeness), and truthfulness (strategyproofness). If agents can fine-tune their reported values, they can strategically misreport them to manipulate the outcome.
Binary valuations dissolve this conflict entirely. In Fair Division with Binary Valuations: One Rule to Rule Them All, Halpern et al. prove that the Maximum Nash Welfare (MNW) rule—which selects an allocation maximizing the product of agents' utilities—simultaneously satisfies Pareto efficiency, envy-freeness, and group strategyproofness.
The intuition behind this "one rule to rule them all" phenomenon lies in the discrete symmetry of the optimization landscape. An agent cannot subtly inflate or deflate a value to game the system; they can only toggle an item between "want" (1) and "don't want" (0). Misreporting a desired item as undesired simply risks losing the item entirely without shifting the relative trade-offs of other items, making honest reporting the dominant strategy. Teh et al. extend this in On Maximum Weighted Nash Welfare for Binary Valuations, showing that binary valuations preserve structural properties like monotonicity even when agents have asymmetric entitlements (weights).
Reducing Allocation to Pure Combinatorics
When utilities are arbitrary, fair division is essentially a continuous optimization problem masked as a discrete one. When utilities are binary, the problem becomes purely combinatorial, allowing researchers to deploy powerful tools from graph theory and discrete mathematics.
For instance, when the problem is bounded by structural constraints, binary preferences prevent the combinatorial explosion of possible states:
General Valuations: Continuous trade-offs ➔ Infinite price-space paths ➔ NP-Hard
Binary Valuations: 0/1 Characteristic sets ➔ Bipartite Matching / Matroids ➔ Polynomial Time
As identified by the authors of Tractable Fragments of the Maximum Nash Welfare Problem, when agent interest is restricted to a maximum of two items, the fair division problem can be solved exactly by reducing it to a maximum weight matching problem in a bipartite graph.
Furthermore, Dror et al. demonstrate in On Fair Division under Heterogeneous Matroid Constraints that binary preferences allow fair allocation algorithms to respect complex structural constraints, such as matroid independent sets (which model real-world constraints like scheduling conflicts or capacity limits). Because a binary preference acts like a characteristic function, the allocation problem maps directly onto matroid intersection frameworks, which are solvable in polynomial time.
By flattening the granularity of preference expression, binary and bivalued simplifications transform fair division from an intractable search for fractional compromises into an elegant, highly solvable combinatorial problem.
Key Foundational Work
Competitive Equilibrium with Equal Incomes for Allocation of Indivisible Objects (2015) — contributed 1 concept elements to this direction.
Fair assignment of indivisible objects under ordinal preferences (2015) — contributed 1 concept elements to this direction.
Greedy Algorithms for Maximizing Nash Social Welfare (2018) — contributed 1 concept elements to this direction.