Fair Division under Binary and Bivalued Valuations

36 concepts30 papers1 proposal

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:

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.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_binary_valuation_simplification_880a939b,
  title = {binary valuation simplification},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/binary-valuation-simplification/rdr_880a939b942d441c81d04b6bad344ad3},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_binary_valuation_simplification_880a939b_v1,
  title = {binary valuation simplification},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/binary-valuation-simplification/rdr_880a939b942d441c81d04b6bad344ad3/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake