Source-linked AI summary
Fair Division Under Boolean Valuations: Beyond Normalization
Nisarg Shah, Paritosh Verma
TL;DR
The paper asks which fairness guarantees remain possible for indivisible-item division with arbitrary, nonmonotone Boolean valuations when agents may value the empty bundle differently. It characterizes EF1 and EFX existence and studies their combination with efficiency, incentives, randomization, and matroid feasibility. The resulting landscape is governed by the number of agents valuing the empty bundle at zero, with sharp positive and negative boundaries across these settings.
Problem
Fair-division results commonly assume monotone, normalized preferences, leaving the existence and tradeoffs of fairness guarantees for arbitrary mixed Boolean valuations underexplored.
Method
The paper characterizes variants of EF1 and EFX for general Boolean profiles and analyzes their compatibility with efficiency, incentive compatibility, lotteries, and common matroid constraints.
Results
The existence landscape depends on |Z|, the number of agents valuing the empty bundle at zero: the paper proves sharp EF1 conditions, resolves EFX+0 existence for negative-Boolean valuations, and gives positive and negative efficiency guarantees.
Takeaways & Limitations
The value assigned to the empty bundle is a substantive determinant of attainable fairness guarantees, rather than merely a normalization convention.
Takeaways & Limitations
Extending the matroid characterization to more agents or agent-specific matroids appears to require different reconfiguration objects and is left beyond the paper’s reach.
Abstract
from arXiv · showhide
We study fair division of indivisible items when agents have arbitrary two-level preferences: the value of each agent for any set of items is Boolean, which need not be monotone or additive. Notably, we do not impose the standard assumption of normalization, i.e., different agents may value the empty set at different Boolean levels. Since the preferences are nonmonotone, envy-freeness up to one item (EF1) and envy-freeness up to any item (EFX) each admit several variants, depending on which items are tested for removal and whether they are removed from the envious agent's bundle or the envied agent's bundle. This paper investigates the existence of these variants of EF1 and EFX, on their own and together with economic efficiency, incentive compatibility, feasibility constraints, and lottery-based randomization. Our results highlight that the existence landscape depends crucially on the number of normalized agents, who value the empty bundle at the lower Boolean level. The authors used significant assistance from GPT-5.6-Sol for deriving theoretical results, verified any AI-generated proofs for correctness, and expanded on the exposition and simplified arguments, with the aid of GPT-5.6-Sol and Claude Opus 5.
1 Introduction
The paper studies fair division with arbitrary, nonmonotone Boolean valuations without normalization, where attainable fairness and accompanying guarantees depend sharply on which agents value the empty bundle at the lower level. It resolves an EFX open question and develops results combining fairness with efficiency, strategyproofness, randomization, and matroid feasibility.
- 1 Introduction: Arbitrary Boolean valuations remove monotonicity, additivity, and normalization assumptions, extending fair-division analysis to mixed profiles with different values for the empty bundle.Prior work primarily treated normalized subclasses and focused on fairness without fully examining tradeoffs with other desiderata.
- The EF1 landscape: The number of agents in Z, those valuing the empty bundle at zero, governs the existence conditions for several EF1 variants and efficient allocations.EF1+ exists exactly when Z is nonempty, EF1− exactly when |Z| ≤ 1, EF1+ with PO exactly when Z is nonempty, and EF1− with PO exactly when |Z| = 1.
- The EFX landscape: EFX− always exists because it coincides with EF1 on Boolean valuations, whereas EFX0− requires Z to be nonempty and EFX0 has no universal guarantee.These results establish distinct existence boundaries among the four EFX variants.
- The EFX landscape: Every negative-Boolean instance admits a complete EFX+0 allocation, resolving Bérczi et al.’s open question through a peel-and-match algorithm using Hall’s theorem and induction.Previously, existence was known only for identical valuations.
- Fairness, efficiency, and incentives: A deterministic weakly group-strategyproof mechanism always outputs EFX0− and Pareto-optimal allocations by lexicographically optimizing welfare, allocated items among value-one agents, and a fixed tie-break.The mechanism strengthens earlier existence results by providing incentive compatibility and efficiency together with fairness.
- Best-of-both-worlds guarantees: If at least one agent values the empty set at zero, a lottery exists that is ex-ante envy-free while every supported allocation is Pareto optimal, EF1+, and EFX0−.This gives simultaneous ex-ante and ex-post guarantees under the stated condition.
- Matroid constraints: For two agents under a common matroid constraint, feasible EF1 is guaranteed exactly when the basis-pair exchange graph has a self-complementary component.The condition yields feasible EF1 for several matroid classes, while partition matroids make EF1 and Pareto optimality incompatible.
2 Preliminaries
The paper formalizes Boolean fair division and several nonmonotone EF1 and EFX variants, then establishes their implication relationships across normalized and mixed settings.
- Basic model: A complete allocation partitions all indivisible items among agents with arbitrary Boolean valuations, and Pareto optimality forbids any allocation that weakly benefits every agent and strictly benefits one.
- Basic model: Agent-specific translation by the empty-bundle value preserves fairness comparisons, yielding positive-Boolean valuations in the normalized setting and negative-Boolean valuations when every agent values the empty bundle at one.
- EF1 variants: EF1+ tests removing an item from the envied bundle, EF1− tests removing one from the envious bundle, and EF1+− permits removal from either side.
- EF1 variants: Under Boolean valuations, an EF1 violation occurs exactly when the envious bundle is unsafe and the envied bundle is robust for the envious agent.
- EFX variants: The four EFX relaxations test specified items from the envious and envied bundles, and each implies the weakest two-sided EF1 notion because the tested set is nonempty.
- EFX variants: The EFX variants are partially ordered, with additional implications at normalization endpoints that fail in the mixed domain because empty bundles can separate the notions.
3 EF1 Existence for Unnormalized Boolean Valuations
The paper begins by proving universal EF1 existence for arbitrary Boolean profiles, then uses the agents’ empty-bundle values to construct the guarantee in separate cases.
- Role in the paper: The universal EF1 result starts stronger existence guarantees and later combinations of fairness with Pareto optimality and incentive compatibility.
- Universal existence: Every instance with arbitrary Boolean valuations admits a complete EF1 allocation.
- Case analysis: When at least one agent values the empty bundle at zero, agents valuing it at one can receive empty bundles while the remaining items are allocated among the normalized agents.
- Case analysis: If every agent values the empty bundle at one, subtracting one yields a heterogeneous negative-Boolean instance with an EF1 allocation, and translation preserves EF1 inequalities.
4 One-Sided EF1: A Fine-Grained Existence Analysis
The existence of one-sided EF1 variants is governed exactly by the number of agents who value the empty bundle at zero. The paper gives score-based existence proofs, impossibility results, and the unique regime where both variants coexist with Pareto optimality.
- Existence trichotomy: The parameter |Z|, where Z contains agents valuing the empty bundle at zero, determines the one-sided EF1 existence trichotomy.The regimes are |Z| = 0, |Z| = 1, and |Z| ≥ 2.
- Existence trichotomy: EF1+ is guaranteed if and only if Z ≠ ∅, whereas EF1− is guaranteed if and only if |Z| ≤ 1.A Pareto-optimal EF1− allocation is guaranteed exactly when |Z| = 1.
- Proof approach: GOODSOPT and CHORESOPT maximize primary scores and then optimize secondary scores over complete allocations to establish these existence guarantees.The rules are existential constructions rather than polynomial-time algorithms because they optimize over the entire allocation set.
- Boundary cases: When Z = ∅, EF1+ may fail for every allocation, while every CHORESOPT allocation is EF1− and therefore also EFX+−.The impossibility already holds with two agents and one item having valuation 1 exactly for the empty set.
- Pareto optimality: When |Z| = 1, a complete allocation can be simultaneously Pareto optimal, envy-free, EF1+, and EF1−.This is the unique regime in which one allocation has both one-sided EF1 guarantees together with Pareto optimality.
- Boundary cases: When |Z| ≥ 2, EF1− may fail to exist, so the two one-sided guarantees overlap universally only at |Z| = 1.The weakest EFX variant is equivalent to EF1 on Boolean valuations, and every complete EF1 allocation is consequently EFX+−.
5 The EFX Landscape
The EFX landscape for arbitrary Boolean valuations is governed by normalization endpoints and the presence of agents valuing the empty bundle at zero. The paper characterizes several existence results, including a polynomial-time construction for one EFX variant and sharp impossibility boundaries for others.
- Variant landscape: EFX has four variants because nonmonotone valuations make item-removal tests depend on both the tested bundle and the removal direction.The section studies these variants separately for Boolean valuations.
- Characterization: An allocation is EFX+_0 exactly when each agent receives a deletion-secure bundle or values every other agent’s bundle at zero.Deletion-secure means the bundle has value one, or has value zero while every one-item deletion has value one.
- Existence: Every negative-Boolean instance admits a complete EFX+_0 allocation, computable in polynomial time in the value-oracle model.The construction partitions items into reference-agent-minimal blocks and uses matching and induction.
- Existence: If Z={i:vi(∅)=0} is nonempty, every Boolean instance admits a complete EFX−_0 allocation.This guarantee is tight: an instance with Z=∅ can lack such an allocation.
- Impossibility boundaries: No universal guarantee exists for either EFX+_0 or EFX−_0 on arbitrary Boolean profiles, while EFX+_0 always exists when every agent values the empty bundle at one.Thus normalization status determines which EFX guarantees are available across valuation classes.
6 Combining Fairness and Efficiency with Incentives
The paper combines Pareto efficiency, fairness, and incentives through a deterministic optimizer that selects allocations by welfare and a secondary bundle-size score. It proves weak group-strategyproofness and Pareto optimality, while preserving several fairness guarantees under suitable normalization conditions.
- Fairness: Under the relevant normalized report domain, the mechanism additionally returns EF1+ and EFX0− allocations.These fairness guarantees are stated with respect to the reported profile.
- Mechanism: The mechanism M▷ maximizes the number of agents receiving value one, minimizes the total size of their bundles, and applies fixed tie-breaking.Its output is selected from the Pareto-optimal set O+(p).
- Incentives and efficiency: M▷ is weakly group-strategyproof and Pareto optimal when agents may report any Boolean valuations.Weak group-strategyproofness rules out joint misreports that strictly benefit every coalition member.
- Limitation: The mechanism’s weak group-strategyproofness does not extend to strong group-strategyproofness.A three-agent example exhibits a coalition whose coordinated reports make every member weakly better off with one strict improvement.
7 Best of Both Worlds: Adding Ex-Ante Envy-Freeness
When at least one agent values the empty bundle at zero, uniformly randomizing over the optimizer set yields ex-ante envy-freeness while preserving strong ex-post guarantees. The result is tight at the valuation-class level because when no agent has this normalization, Pareto optimality and EF1 can be incompatible.
- Limitation: The condition Z≠∅ is tight because some profiles with Z=∅ admit no allocation that is simultaneously Pareto optimal and EF1.In those profiles, even a lottery over Pareto-optimal allocations cannot guarantee the required ex-post fairness.
- Construction: The lottery draws each allocation in O+(v) with equal probability.O+(v) is the set selected by the welfare-maximization and secondary-cost procedure.
- Main guarantee: The uniform optimizer lottery is ex-ante envy-free, and every supported allocation is Pareto optimal, EF1+, and EFX0−.This is the paper’s best-of-both-worlds guarantee whenever Z={i:vi(∅)=0} is nonempty.
- Proof idea: Swap closure pairs optimizer allocations that reverse an envy differential while preserving the optimal welfare and secondary cost.The swap operator is an involution on allocations and maps a differential of −1 to +1.
- Proof idea: Uniform randomization is ex-ante envy-free because swap closure makes the positive envy differentials at least as numerous as the negative ones.The resulting expectation inequality holds for every ordered pair of agents.
8 Matroid Constraints
Under a common matroid feasibility constraint, the paper characterizes exactly when two agents always have a feasible EF1 allocation. It also identifies positive matroid classes and shows that EF1 and Pareto optimality can conflict under partition-matroid constraints.
- Model: Feasible allocations must partition all items into disjoint bundles that are independent in the common matroid.The fairness comparison itself remains unchanged, and item deletions preserve independence.
- Characterization: For two agents, a feasible EF1 allocation exists for every Boolean profile exactly when H_K has a self-complementary connected component.The complementation map exchanges each feasible bundle with its complement.
- Reconfiguration: In the base-partition case, edges of H_K correspond exactly to symmetric exchanges between pairs of complementary bases.Thus the characterization links fair division to basis-pair reconfiguration.
- Positive classes: Strongly base-orderable, split, sparse paving, and regular matroids guarantee feasible EF1 for arbitrary Boolean valuations.Uniform and partition matroids also guarantee feasible EF1 whenever a complete feasible allocation exists.
- Efficiency conflict: A two-agent partition-matroid instance can have feasible EF1 allocations and feasible Pareto-optimal allocations separately, but none satisfying both.The incompatibility holds even with identical normalized Boolean valuations.
9 Discussion
The discussion identifies sharp dependence of attainable fairness and efficiency guarantees on the number of normalized agents. It also records open boundaries for mechanism design, matroid feasibility, and extensions beyond Boolean preferences.
- Main conclusions: The empty bundle’s Boolean level dictates which one-sided EF1 guarantees are achievable, with a sharp transition at |Z| = 1.An item can improve one bundle while worsening another, so it need not be classified as a good or chore.
- Mechanism design: Theorem 5 gives a weakly group-strategyproof and Pareto-optimal mechanism whose output is EFX0−.
- Mechanism design: At Z = ∅, for every n, m ⩾ 2, some profile admits no allocation that is simultaneously Pareto optimal and EF1.Therefore, no mechanism can guarantee both properties throughout Vn^0.
- Matroid feasibility: For two agents, feasible EF1 is guaranteed for every Boolean profile exactly when the exchange graph HK has a self-complementary component.The condition is weaker than the exchange property conjectured by White and Gabow and already holds for several matroid classes.
- Open questions: The matroid characterization remains open for arbitrary numbers of agents, while agent-specific matroids lack a single shared exchange graph.The discussion also asks whether the two-agent basis-pair exchange graph must contain a self-complementary component.
- Open questions: Extending the framework to three indifference classes is unclear because one deletion can move a bundle by more than one preference level.The unsafe-versus-robust bundle distinction no longer captures the effect of removing an item.
A Valuation classes
The paper distinguishes valuation classes by additivity, marginal signs, monotonicity, and submodularity. Boolean valuations are arbitrary nonnegative set functions and are generally incomparable with classes defined by binary marginals.
- Additivity: Additive valuations assign each bundle the sum of item values, with nonnegative item values.Binary additive valuations additionally restrict every item value to 0 or 1.
- Additivity: Additive mixed-manna valuations allow arbitrary real item values, classifying items as goods, chores, or irrelevant items by sign.
- Binary marginals: Dichotomous valuations have marginal values in {0, 1}, are monotone nondecreasing, and range over {0, 1, . . . , m}.Matroid-rank valuations are the dichotomous submodular subclass, with bundle value equal to maximum independent-set size.
- Monotonicity: Monotone nondecreasing valuations make every item a good, whereas doubly monotone valuations partition items into goods and chores by marginal sign.The partition may differ across agents, and bundle values need not be additive.
- General classes: Nonnegative valuations require only nonnegative bundle values, while arbitrary set valuations impose no requirement beyond being functions on 2^M.
- Boolean valuations: Boolean valuations are nonnegative, range over {0, 1}, and need not be monotone; they intersect dichotomous valuations exactly at monotone nondecreasing valuations of V0.Thus Boolean valuations are incomparable with classes based on binary marginals.