Fair Division Under Boolean Valuations: Beyond Normalization

arXiv:2608.29497 · cs.GT · Submitted 2026-08-30 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: I'm Tom.

Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.

Tom: We're looking at the paper: "Fair Division Under Boolean Valuations: Beyond Normalization".

Title and authors: Jane: So what do they actually find regarding these different fairness goals? They are trying to establish the existence of these variants of EF1 and EFX alongside economic efficiency, incentive compatibility, and feasibility constraints <ref:2608.29497#pg1>.

Lu: The main finding is that the existence landscape is heavily dependent on the number of normalized agents who value the empty bundle at a lower Boolean level <ref:2608.29497#pg2>.

Tom: They uncover conditions under which fine-grained variants of EF1, and four specific variants of EFX given by Bérczi et al., actually exist, including resolving an open question about EFX plus zero for negative Boolean valuations <ref:2608.29497#pg4>.

Meng: So if this count is zero, or one, or two or more, the whole structure of what's possible changes fundamentally. That feels like a lot to track when you're trying to deploy something at scale <ref:2608.29497#pg2>.

Jane: They also analyze how these fairness notions are built by looking at how envy is eliminated, formalizing them in Section two and Table one <ref:2608.29497#pg4>.

Tom: They show that the weakest notion, EFX minus, always exists because it coincides with EF1 on the Boolean domain <ref:2608.29497#pg4>.

The paper's summary: Lu: For improving these results, they present two score-based allocation rules: GOODSOPT and CHORESOPT <ref:2608.29497#pg4>. These rules maximize certain welfare scores and minimize cost scores, respectively.

Tom: And the goods side rule is shown to be Pareto optimal if that count of agents valuing the empty bundle at zero is not empty <ref:2608.29497#pg2>.

Jane: They also design a deterministic mechanism called M delta, which outputs an EFX zero minus and Pareto optimal allocation when reports are in Vn zero <ref:2608.29497#pg4>.

Meng: So, for deployment, this means we have some concrete algorithms to aim for when the conditions are right, like when that count is one <ref:2608.29497#pg2>. But what happens if we don't hit those specific conditions?

Tom: If the count is one, they characterize EF1 allocations based on that size Z, showing a trichotomy: zero, one, or more than two <ref:2608.29497#pg2>.

Jane: And they prove that an allocation is both Pareto optimal and EF1 minus if and only if that count of agents valuing the empty bundle at zero is exactly one <ref:2608.29497#pg2>.

The paper's improvements: Tom: So to wrap up, the main thing we learned from "Fair Division Under Boolean Valuations: Beyond Normalization" is that the value of the empty bundle really dictates which version of EF1 you can actually achieve <ref:2608.29497#pg2>.

Jane: And there's a sharp transition when that count is one, which seems to be the most vivid part of their findings <ref:2608.29497#pg2>.

Lu: The open questions are whether a strategyproof rule can guarantee EF1 on reports with one level, V1, for any number of agents and items <ref:2608.29497#pg4>, and which matroids guarantee a feasible EF1 allocation for every Boolean profile and every number of agents <ref:2608.29497#pg4>.

Meng: From a deployment standpoint, the limitation they point out is that characterization for matroid constraints depends on finding a self-complementary component in the exchange graph H K <ref:2608.29497#pg4>. That's not something you can just plug into every arbitrary resource problem.

Lalam: They also showed that if that count of agents valuing the empty bundle at zero is not empty, there exists a lottery over allocations that is ex-ante envy-free and every allocation in its support is Pareto optimal, EF1 plus, and EFX zero minus <ref:2608.29497#pg4>.

Tom: So we've got these tools for creating allocations that are both fair and efficient under these nonmonotone settings. It's a lot of theory to digest.

Jane: Yeah, it opens up a whole new way to think about fairness when the preferences aren't as nice as they usually are <ref:2608.29497#pg3>.

Lu: The next step is definitely exploring preferences with three indifference classes <ref:2608.29497#pg2>.

Meng: I'm still thinking about the practical cost of running these kinds of allocation rules when we have real traffic instead of just theoretical profiles.

Lalam: It’s a solid piece of theory, and it shows us exactly where the complexity hides in these kinds of division problems.

Conclusion: Jane: So we looked at the paper "Fair Division Under Boolean Valuations: Beyond Normalization" and what they found is that whether you can actually get a fair split really depends on how many agents value having nothing at all <ref:2608.29497#pg2>.

Tom: Yeah, and they break it down into a trichotomy based on that count of agents valuing the empty bundle at zero, which is either zero, one, or more than two <ref:2608.29497#pg2>.

Lu: And that count dictates exactly which fine-grained versions of EF1 and EFX actually exist in these scenarios <ref:2608.29497#pg4>.

Meng: So for deployment, it means we have to know if we're going to be able to get a Pareto optimal and envy-free split or if the structure just breaks down at scale <ref:2608.29497#pg2>.

Lalam: And they did show us a mechanism, M delta, that can give you a Pareto optimal and EFX zero minus allocation when reports are in Vn zero <ref:2608.29497#pg4>.

Jane: It’s interesting how they link that count of one directly to getting EF1 minus and Pareto optimality <ref:2608.29497#pg2>.

Tom: That's the critical number, so if you can guarantee that count is one, you get a very specific outcome <ref:2608.29497#pg2>.

Lu: And they also proved that if that count of agents valuing the empty bundle at zero is not empty, there’s a lottery over allocations where every single result is both Pareto optimal and EF1 plus <ref:2608.29497#pg4>.

Meng: But what about when you have those matroid constraints we talked about before? The paper says the condition depends on finding a self-complementary component in the exchange graph H K <ref:2608.29497#pg4>. That sounds like it might be hard to check in a production environment.

Jane: It does sound complicated, but it gives us a concrete mathematical way to characterize when feasibility is guaranteed for every Boolean profile and every number of agents <ref:2608.29497#pg4>.

Tom: Anyway, the whole point of this paper "Fair Division Under Boolean Valuations: Beyond Normalization" is that it shows us exactly what conditions must be met to achieve these fairness goals when valuations aren't nice or additive <ref:2608.29497#pg2>.

Lu: It sets up the next big thing, which is exploring preferences with three indifference classes <ref:2608.29497#pg2>.

Jane: Right, moving to preferences with three levels sounds like a natural progression from this work.

University of Toronto

cs.GT

Submitted: 2026-08-30

Updated: 2026-11-18

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 99/100

The gist: Fair division of indivisible items when agents have arbitrary two-level preferences is studied, and results highlight that the existence landscape depends crucially on the number of normalized agents…

Key concepts

|Z|
This parameter counts how many normalized agents value the empty bundle (the bundle with nothing) at a Boolean level lower than their actual valuation. It is the crucial factor determining the existence landscape for various fairness outcomes, such as EF1 and EFX.
EF1
Envy-freeness up to one item means that no agent can envy another agent's bundle if we consider only one item difference. The paper investigates different variants of this fairness, showing that its existence depends on the size of |Z|.
EFX
Envy-freeness up to any item requires a stronger condition where no agent can envy another agent's bundle regardless of how many items are compared. The analysis shows that achieving EFX variants is also tied directly to the value of |Z|.

Terminology

Summary

Fair division of indivisible items when agents have arbitrary two-level preferences is studied, and results highlight that the existence landscape depends crucially on the number of normalized agents who value the empty bundle at a lower Boolean level <ref:2608. p. 0

Where the paper says it

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.

29497#pg2>. This paper investigates the existence of various fairness variants (EF1 and EFX) alongside economic efficiency, incentive compatibility, feasibility constraints, and randomization under nonmonotone valuations <ref:2608. p. 0
Where the paper says it

Since the preferences are nonmonotone, envyfreeness 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.

29497#pg4>.

Pruning redundant reasoning tokens

The study focuses on fair division of indivisible items when agents have arbitrary two-level preferences where the value of each agent for any set of items is Boolean and need not be monotone or additive <ref:2608.29497#pg2>. The paper investigates the existence landscape for envyfreeness up to one item (EF1) and envy-freeness up to any item (EFX), noting that these admit several variants depending on which items are tested for removal and whether they are removed from the envied agent’s bundle or the envied agent’s bundle <ref:2608. p. 0

Where the paper says it

Since the preferences are nonmonotone, envyfreeness 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.

29497#pg4>. The results highlight that the existence landscape depends crucially on the number of normalized agents who value the empty bundle at a lower Boolean level <ref:2608. p. 0
Where the paper says it

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.

29497#pg2>. Specifically, it uncovers conditions under which fine-grained variants of EF1, and the four variants of EFX given by Bérczi et al. p. 0
Where the paper says it

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. Specifically, we uncover the conditions under which fine-grained variants of EF1, and the four variants of EFX, given by Bérczi et al.

[8] exist, including the resolution of an open question regarding EFX+0 for negative-Boolean valuations <ref:2608. p. 0
Where the paper says it

Specifically, we uncover the conditions under which fine-grained variants of EF1, and the four variants of EFX, given by Bérczi et al. This includes the resolution of an open question posed by them: a variant of EFX, namely EFX+ 0 , always exists for negative-Boolean valuations.

29497#pg4>.

How the training signal is built

The paper analyzes various variants of EF1 and EFX relaxations based on how envy is eliminated, formalizing them in Section 2.1 and Table 1 <ref:2608. p. 0

Where the paper says it

6-Sol and Claude Opus 5. 1 arXiv:2608.

29497#pg4>. It establishes that the weakest notion, EFX+−, coincides with EF1 on the Boolean domain and thus always exists <ref:2608. p. 3
Where the paper says it

2, and Figure 1 maps their relationships with the three variants of EF1. The weakest notion, EFX+ −, coincides with EF1 on the Boolean domain and hence always exists (Proposition 3); EFX0 − is guaranteed whenever Z ̸= ∅, and this characterizing condition is tight because a profile with Z = ∅ may fail to admit EFX0 − allocations (Lemma 1 and Theorem 4); and the stronger notion, EFX0 0 , admits no universal guarantee [8].

29497#pg4>. The analysis of one-sided notions shows that their existence is governed by the size of the set Z = NZ where agents value the empty bundle at zero <ref:2608. p. 8
Where the paper says it

4 One-Sided EF1: A Fine-Grained Existence Analysis Section 3 settles the existence of the two-sided notion, EF1+ −. The one-sided notions behave very differently, with the size of the set Z = {i : vi(∅) = 0} governing their existence exactly.

29497#pg2>. For instance, EF1+ and PO allocations are guaranteed if and only if Z ≠ ∅ <ref:2608. p. 9
Where the paper says it

For Boolean profiles, universal existence of the one-sided notions is governed by |Z|: |Z| = 0 |Z| = 1 |Z| ⩾ 2 EF1+ ✗ ✓ ✓ EF1− ✓ ✓ ✗ PO ∧ EF1+ ✗ ✓ ✓ PO ∧ EF1− ✗ ✓ ✗ where ✓ means every instance in that column admits such an allocation and ✗ means some instance admits none. Equivalently: EF1+ (with or without PO) is guaranteed iff Z ̸= ∅; EF1− is guaranteed iff |Z| ⩽ 1; and a Pareto-optimal EF1− allocation is guaranteed iff |Z| = 1.

29497#pg2>.

Where the gains come from

The paper presents two score-based allocation rules: GOODSOPT, which maximizes Wp and minimizes Cp, and CHORESOPT, which maximizes W′p and maximizes C′p <ref:2608.29497#pg4>. These algorithms are used to establish existence guarantees for one-sided notions; for example, the goods-side rule is shown to be Pareto optimal if Z ≠ ∅ <ref:2608. p. 8

Where the paper says it

The one-sided notions behave very differently, with the size of the set Z = {i : vi(∅) = 0} governing their existence exactly. We show that the guarantees for EF1+ and EF1−, both alone and in conjunction with Pareto optimality, are controlled by whether |Z| is 0, 1, or at least 2.

29497#pg2>. Furthermore, a deterministic weakly group-strategyproof mechanism M▷ is designed that outputs an EFX0− and PO allocation when reports are in Vn0 <ref:2608. p. 4
Where the paper says it

’s result on the existence of EFX0 − allocations [8, Theorem 7] for the normalized setting. 2 We give a simple weakly group-strategyproof mechanism that always outputs an EFX0 − and PO allocation.

29497#pg4>.

The paper characterizes the existence of EF1 allocations based on the size of Z, summarized in Theorem 2, which establishes a trichotomy based on Z = 0, Z = 1, or Z ≥ 2 <ref:2608.29497#pg2>. It also proves that an allocation is Pareto optimal and EF1− if and only if Z = 1 <ref:2608. p. 0

Where the paper says it

For the setting where all agents value the empty bundle at zero, we show that fairness can be achieved along with other guarantees: there always exists a lottery over indivisible allocations that is ex-ante envy-free and ex-post Pareto optimal (PO) and EF1; additionally, there is a weakly group-strategyproof mechanism that outputs EF1 and PO allocations. Finally, we study a setting where agents have a matroid feasibility constraint on bundles (the same constraint applies to every agent); we characterize exactly when two agents are guaranteed a feasible EF1 allocation.

29497#pg2>. The characterization for two agents under matroid feasibility constraints relates the existence of a feasible EF1 allocation to the existence of a self-complementary component in the exchange graph HK <ref:2608. p. 4
Where the paper says it

We characterize, for two agents, exactly which matroids guarantee a feasible EF1 allocation for all Boolean profiles (Theorem 7). Notably, the characterizing condition (existence of a self-complementary component of the symmetric basis-pair exchange graph) connects the problem to the reconfiguration conjectures of White [19] and Gabow [13] in matroid theory.

29497#pg4>.

The paper demonstrates that if Z ≠ ∅, there exists a lottery over allocations that is ex-ante envy-free and every allocation in its support is Pareto optimal, EF1+, and EFX0− <ref:2608.29497#pg4>. This uniform optimizer lottery (p unif) is shown to be ex-ante envy-free <ref:2608. p. 0

Where the paper says it

This includes the resolution of an open question posed by them: a variant of EFX, namely EFX+ 0 , always exists for negative-Boolean valuations. For the setting where all agents value the empty bundle at zero, we show that fairness can be achieved along with other guarantees: there always exists a lottery over indivisible allocations that is ex-ante envy-free and ex-post Pareto optimal (PO) and EF1; additionally, there is a weakly group-strategyproof mechanism that outputs EF1 and PO allocations.

29497#pg4>. Furthermore, for two agents under matroid constraints, a complete feasible EF1 allocation is guaranteed whenever the matroid is strongly base-orderable, split, sparse paving, or regular <ref:2608. p. 4
Where the paper says it

Notably, the characterizing condition (existence of a self-complementary component of the symmetric basis-pair exchange graph) connects the problem to the reconfiguration conjectures of White [19] and Gabow [13] in matroid theory. Known reconfiguration theorems yield feasible EF1 for strongly base-orderable, split, sparse paving, and regular matroids (Corollary 1).

29497#pg4>. The incompatibility between EF1 and Pareto optimality under partition-matroid constraints is also shown <ref:2608. p. 1
Where the paper says it

3 Basis-pair reconfiguration and positive classes . 4 EF1 and Pareto optimality can conflict under a partition matroid .

29497#pg4>.

The paper addresses the open question regarding EFX+0 for negative-Boolean valuations, proving that every instance with vi ∈ V1 for every agent admits a complete EFX+0 allocation <ref:2608.29497#pg4>. The existence of EFX0− is guaranteed if and only if Z is nonempty <ref:2608. p. 2

Where the paper says it

It is likewise natural for agents to assign a nonzero value to the empty bundle: a student might prefer taking no courses in a semester to taking an uninteresting course; if the items are perceived as chores, the empty bundle can be more valuable than nonempty bundles. The existence of desirable allocations without any assumptions like normalization and monotonicity is therefore just as fundamental a question as its counterpart, yet this question remains underexplored.

29497#pg4>. The mechanism M▷ is shown to be weakly group-strategyproof and returns a Pareto-optimal allocation when reports are in Vn0 <ref:2608. p. 0
Where the paper says it

For the setting where all agents value the empty bundle at zero, we show that fairness can be achieved along with other guarantees: there always exists a lottery over indivisible allocations that is ex-ante envy-free and ex-post Pareto optimal (PO) and EF1; additionally, there is a weakly group-strategyproof mechanism that outputs EF1 and PO allocations. Finally, we study a setting where agents have a matroid feasibility constraint on bundles (the same constraint applies to every agent); we characterize exactly when two agents are guaranteed a feasible EF1 allocation.

29497#pg4>.

The paper establishes that the uniform optimizer lottery p unif is ex-ante envy-free <ref:2608.29497#pg4>. The support of this lottery satisfies supp(p unif) = O+(v), and every allocation in its support is Pareto optimal, EF1+, and EFX0− <ref:2608. p. 4

Where the paper says it

We show that if Z ̸= ∅, i. , at least one agent values the empty set at zero, then there exists a lottery over allocations that is ex-ante envy-free, and every allocation in its support is Pareto optimal, EF1+, and EFX0 − (Theorem 6).

29497#pg4>. The swap operator Tij maps S−1 into S+1 in the set O+(v) <ref:2608. p. 0
Where the paper says it

6-Sol and Claude Opus 5. 1 arXiv:2608.

29497#pg4>.

The results conclude that the value of the empty bundle dictates which one-sided version of EF1 can be achieved, with a sharp transition at |Z| = 1 being particularly vivid <ref:2608.29497#pg2>. The open questions concern whether a strategyproof rule can guarantee EF1 on Vn1 for arbitrary n and m <ref:2608. p. 6

Where the paper says it

[8] prove EFX0 −, and hence EF1, for normalized Boolean valuations [8, Theorem 7]. They also prove the stronger EFX+ 0 guarantee for identical negative-Boolean valuations [8, Theorem 9] and pose an open problem of whether the existence result holds for non-identical negative-Boolean valuations [8, Question 16].

29497#pg4> and which matroids guarantee a feasible EF1 allocation for every Boolean profile and every number of agents <ref:2608. p. 4
Where the paper says it

We consider a fair division setting where allocated bundles must be independent sets of a matroid. We characterize, for two agents, exactly which matroids guarantee a feasible EF1 allocation for all Boolean profiles (Theorem 7).

29497#pg4>. The next domain to explore is preferences with three indifference classes <ref:2608. p. 4
Where the paper says it

Only the order of the two values matters for every fairness notion considered here. 4 Consequently, all results extend verbatim to arbitrary preferences with two indifference classes by mapping the lower class to zero and the higher class to one.

29497#pg2>. The analysis of matroid constraints shows that the characterization depends on a self-complementary component in the exchange graph HK <ref:2608. p. 4
Where the paper says it

We characterize, for two agents, exactly which matroids guarantee a feasible EF1 allocation for all Boolean profiles (Theorem 7). Notably, the characterizing condition (existence of a self-complementary component of the symmetric basis-pair exchange graph) connects the problem to the reconfiguration conjectures of White [19] and Gabow [13] in matroid theory.

29497#pg4>. The AI disclosure notes that many proofs were derived by OpenAI Codex based on explicit questions and literature connections <ref:2608.29497#pg2>.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Improve allocation guarantees for general Boolean valuations by explicitly linking fairness outcomes to a single parameter, |Z|, which represents agents valuing the empty bundle at zero. This allows AI systems to determine exactly which fine-grained variants of EF1 and EFX exist based on this count, rather than assuming normalization or monotonicity.

  2. Develop mechanisms that combine fairness with economic efficiency by implementing the GOODSOPT algorithm to maximize a welfare score and then minimizing a cost score, providing allocations that are both Pareto optimal and envy-free up to one item under specific conditions like |Z| = 1.

  3. Enhance mechanism design capabilities by utilizing Algorithm 3, which is a deterministic weakly group strategyproof mechanism for the normalized setting (V0), ensuring that the output allocation is not only Pareto optimal but also satisfies EF1+ and EFX0− relative to the reported profile.

  4. Introduce randomization into allocation strategies by using the uniform optimizer lottery, which draws from the set of allocations returned by GOODSOPT, yielding an ex-ante envy-free lottery whose support consists of Pareto optimal and EF1+ allocations when Z is non-empty.

  5. Extend feasibility analysis for resource allocation problems constrained by matroids by characterizing the necessary and sufficient condition on the exchange graph HK that guarantees a feasible EF1 allocation for every Boolean profile in the two-agent case.

Abstract

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 paper presents a wide range of positive and negative results that collectively highlight an interesting phenomenon: the landscape of achievable guarantees depends crucially on the number of normalized agents, who value the empty bundle at the lower Boolean level.

Sources

Related papers