Paper deep dive
Simultaneous Envy and Equitability Guarantees
Hadi Hosseini, Shraddha Pathak, Lirong Xia, Chengkai Zhang
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 95%
Last extracted: 8/28/2026, 3:41:35 AM
Summary
This paper investigates the compatibility of two distinct fairness notions, envy-freeness (EF) and equitability (EQ), in the fair division of indivisible items. It analyzes both deterministic and randomized (ex-ante/ex-post) allocations for goods and chores under various valuation structures (additive, binary, bivalued). Key findings include the non-existence of EF1+EQ1 allocations for n≥3 agents with normalized bivalued valuations, the existence of EF1+EQ1 for binary goods with up to seven agents, and the existence of stronger EFX+EQX guarantees for binary chores. The study also explores cross-notion best-of-both-worlds guarantees.
Entities (18)
Relation Signals (12)
Chengkai Zhang → authored → Simultaneous Envy and Equitability Guarantees
confidence 99% · Chengkai Zhang Rutgers University ... Simultaneous Envy and Equitability Guarantees
Hadi Hosseini → authored → Simultaneous Envy and Equitability Guarantees
confidence 99% · Hadi Hosseini Penn State University ... Simultaneous Envy and Equitability Guarantees
Shraddha Pathak → authored → Simultaneous Envy and Equitability Guarantees
confidence 99% · Shraddha Pathak Penn State University ... Simultaneous Envy and Equitability Guarantees
Lirong Xia → authored → Simultaneous Envy and Equitability Guarantees
confidence 99% · Lirong Xia Rutgers University ... Simultaneous Envy and Equitability Guarantees
EF1+EQ1 → existsfor → binary goods with <=7 agents
confidence 95% · Our main algorithmic result computes an EF1+EQ1 allocation for normalized binary goods with at most seven agents.
EFX+EQX → existsfor → binary chores
confidence 95% · binary chores admit the stronger EFX+EQX guarantee for any number of agents
EF1 → isrelaxationof → Envy-freeness
confidence 95% · we focus on their natural relaxations: envy-freeness up to one item (EF1)
EQ1 → isrelaxationof →
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Recent work in fair division has focused on either simultaneously satisfying closely related fairness notions or achieving a single notion across the ex-ante and ex-post worlds. We study the compatibility of two fundamentally different fairness notions: envy-freeness and equitability. For indivisible goods-only and chores-only settings, we study the existence and complexity of simultaneously satisfying their relaxations, revealing sharp contrasts between the two settings. We show that EF1+EQ1 may fail to exist even for normalized, additive valuations. Our main algorithmic result computes an EF1+EQ1 allocation for normalized binary goods with at most seven agents. In sharp contrast, binary chores admit the stronger EFX+EQX guarantee for any number of agents, even without normalization. We further initiate the study of cross-notion ex-ante--ex-post guarantees, asking whether randomized allocations can provide ex-ante guarantees for one notion while preserving ex-post guarantees for another.
Tags
Links
- Source: https://arxiv.org/abs/2608.26410v1
- Canonical: https://arxiv.org/abs/2608.26410v1
Trouble viewing inline? Open PDF directly →
Full Text
145,757 characters extracted from source content.
Expand or collapse full text
Simultaneous Envy and Equitability Guarantees Hadi Hosseini Penn State University hadi@psu.edu Shraddha Pathak Penn State University ssp5547@psu.edu Lirong Xia Rutgers University lirong.xia@rutgers.edu Chengkai Zhang Rutgers University cz521@scarletmail.rutgers.edu Abstract Recent work in fair division has focused on either simultaneously satisfying closely related fairness notions or achieving a single notion across the ex-ante and ex-post worlds. We study the compatibility of two fundamentally different fairness notions: envy-freeness and equitability. For indivisible goods-only and chores-only settings, we study the existence and complexity of simultaneously satisfying their relaxations, revealing sharp contrasts between the two settings. We show that EF1+EQ1 may fail to exist even for normalized, additive valuations. Our main algorithmic result computes an EF1+EQ1 allocation for normalized binary goods with at most seven agents. In sharp contrast, binary chores admit the stronger EFX+EQX guarantee for any number of agents, even without normalization. We further initiate the study of cross-notion ex-ante–ex-post guarantees, asking whether randomized allocations can provide ex-ante guarantees for one notion while preserving ex-post guarantees for another. 1 Introduction Fair division of indivisible items is a fundamental problem concerning the allocation of resources or tasks among a group of agents with potentially different idiosyncratic preferences over those items. The literature in this field has given rise to a rich landscape of fairness notions, motivated by both normative principles of distributive justice (Rawls, 1971) and practical considerations such as computational and existential limitations (see, e.g., Amanatidis et al. (2023)). Most existing work studies fairness notions in isolation. However, simultaneously satisfying multiple notions can better accommodate the diversity of metrics (e.g. in human preferences as discussed in Herreiner and Puppe (2009); Hosseini (2024)) while providing stronger fairness guarantees. The simultaneous guarantees have often emerged as a byproduct of axiomatic implications or algorithmic procedures, with a few recent notable exceptions (Akrami and Rathi, 2025; Akrami and Reichert, 2026; Akrami et al., 2026a; Babaioff et al., 2021). A separate line of research explores best-of-both-worlds guarantees, aiming to achieve a single fairness notion (e.g., envy-freeness) ex-ante while preserving guarantees of the approximate of the same notion ex-post (Aziz et al., 2024; Bhaskar et al., 2026; Babaioff et al., 2022). This raises a natural question: Can we simultaneously guarantee multiple, fundamentally different notions of fairness, both in deterministic allocations and across ex-ante and ex-post worlds? We consider two prominent fairness notions. The first, envy-freeness (EF) (Foley, 1966), is based on intrapersonal comparisons: each agent evaluates its own bundle against others’ bundles using its own valuation function. The second, equitability (EQ) (Dubins and Spanier, 1961), relies on interpersonal comparisons, requiring all agents to derive equal subjective value from their respective bundles. This distinction leads to different invariance properties. Envy-freeness is individually scale-invariant: rescaling an agent’s valuation preserves envy-freeness. Equitability, however, can be affected by scaling up or down a single individual’s valuation. Thus, we consider a mild normalization: all agents agree on the value of the grand bundle—a well-motivated assumption in divisible cake cutting (Brams and Taylor, 1996), online allocations (Gkatzelis et al., 2021), and in allocating mixtures of goods and chores (Barman and Verma, 2026; Hosseini et al., 2026). In the presence of indivisible items, exact EF and EQ allocations may fail to exist ex-post (e.g., one item and two agents). Thus, we focus on their natural relaxations: envy-freeness up to one item (EF1) and envy-freeness up to any item (EFX), as well as their equitability counterparts EQ1 and EQX. These notions require the corresponding fairness guarantee to hold after the hypothetical removal of one item from an appropriate bundle. Our work opens a new direction for investigating the interplay between fairness notions. We study the compatibility of two envy-based and equitability-based notions in a deterministic sense under structured valuations. Importantly, we initiate, to the best of our knowledge, the study of achieving distinct fairness guarantees across the ex-ante and ex-post worlds. In particular, we ask whether probabilistic guarantees for one notion (e.g., EF) can coexist with deterministic guarantees for another (e.g., EQ1). 1.1 Contributions We investigate the compatibility of relaxed notions of envy-freeness and equitability in deterministic allocations of indivisible items, as well as their relationships with probabilistic ex-ante guarantees. We focus on additive valuations in two settings: when all items are goods (with non-negative values) and when all items are chores (with non-positive values). Table 1 summarizes our main results. Deterministic guarantees. We show that an allocation satisfying EF1 + EQ1 may fail to exist for n≥3n≥ 3, even for normalized bivalued valuations (Proposition 1). Furthermore, deciding whether such an allocation exists is NP-hard for unnormalized instances with two agents (Theorem 1). Nonetheless, for two agents, EF1+EQ1 allocations always exist and admit polynomial-time algorithms for both goods (Theorem 2) and chores (Corollary 1) under normalization. We further show that the stronger EFX+EQX guarantee exhibits a sharp distinction between the two settings: it is achievable for goods, but may not exist for chores (Proposition 2). Our main results in this section concern binary valuation. For goods, we design an algorithm achieving EF1+EQ1 for up to seven agents (Theorem 3) and, more generally, for any number of agents with laminar approval structures (Theorem 4). The construction is technically involved (see Section 3.3). For binary chores, we show that the stronger EFX+EQX guarantee can always be satisfied (Theorem 5). Ex-ante and ex-post guarantees. For two agents, both goods and chores admit randomized allocations achieving ex-ante EF + EQ, with every allocation in the support satisfying EF1 ex-post (Theorem 6). For normalized binary instances, we further observe a sharp distinction between goods and chores. While we construct randomized allocations achieving ex-ante EF + EQ in both settings, the ex-post guarantees differ: we obtain EQ1 for goods (Theorem 7), but the stronger EF1+EQ1 guarantee for chores, which holds even without normalization and extends to restricted-additive chores (Theorem 9); the latter guarantee is due to Sun and Chen (2025), and we include a short self-contained proof of the form we need. Finally, we show that these ex-post guarantees are best possible in a precise sense: for laminar binary goods the ex-post EF1 guarantee cannot be strengthened to EFX (Proposition 11), and for restricted-additive chores neither EF1 nor EQ1 can be strengthened to its “up to any item” counterpart (Proposition 12). Table 1: Summary of our main results: ✓ = an allocation always exists; ✗ = it may fail to exist; P = it exists and can be computed in polynomial time; ? = it is an open problem; and (general) refers to cases where results hold without normalization. Unless stated otherwise, all instances are additive and normalized. A randomized guarantee is a randomized allocation that satisfies the stated ex-ante notions exactly, while every allocation in its support satisfies the stated ex-post guarantee. Theorem 9 and Corollary 2 follow from Sun and Chen (2025); all other entries are established in this paper. Domains Valuation Types Agents Deterministic Guarantees Randomized Guarantees Guarantee Ref. Ex-ante Ex-post Ref. Goods Additive 22 EFX+EQX ✓ [Prop. 2] EQ EFX ✗ [Prop. 10] EF1+EQ1 P [Thm. 2] EF+EQ EF1 P [Thm. 6] Binary n≤7n≤ 7 EF1+EQ1 P [Thm. 3] Arbitrary ? EF+EQ EQ1 P [Thm. 7] Binary & laminar Arbitrary EF1+EQ1 P [Thm. 4] EF+EQ EF1+EQ1 P [Thm. 8] Chores Additive 22 EFX+EQX ✗ [Prop. 2] EF+EQ EF1 P [Thm. 6] EF1+EQ1 P [Cor. 1] Binary (general) Arbitrary EFX+EQX P [Thm. 5] EF+EQ EF1+EQ1 P [Thm. 9] Rest.-add. (general) EF1+EQ1 P [Cor. 2] 1.2 Related Work Fair division of indivisible items has developed into a rich research area at the intersection of economics, artificial intelligence, and theoretical computer science; we refer to Brandt et al. (2016) and Amanatidis et al. (2023) for broad overviews. Here we discuss the lines of work most relevant to this paper. Envy-freeness and its relaxations. Envy-free allocations of indivisible items may fail to exist even in trivial instances, which has motivated a hierarchy of relaxations. Lipton et al. (2004) introduced the envy-cycle-elimination procedure, which guarantees, for arbitrary monotone valuations, an allocation in which envy is bounded by a single item; the resulting notion was later formalized as EF1 by Budish (2011) and has become the standard benchmark; EF1 allocations always exist and can be computed in polynomial time. The stronger notion EFX (Caragiannis et al., 2019) is known to exist for two agents and for identical (general monotone) valuations via the leximin++ solution (Plaut and Roughgarden, 2020)—a technique we reuse for our two-agent EFX+EQX guarantee—for three additive agents (Chaudhury et al., 2020), and for dichotomous valuations, i.e., valuations with binary marginals (Babaioff et al., 2021; Bu et al., 2023). Very recently, its general existence was refuted for monotone submodular valuations (Akrami et al., 2026b; Mackenzie and Suzuki, 2026); the additive case remains a central open problem in the field. Our results concern the opposite frontier: even where EF1—the weakest notion in this hierarchy—is trivially achievable, we show it can be incompatible with equitability. Equitability and its relaxations. The systematic study of EQ1 and EQX for indivisible goods was initiated by Freeman et al. (2019), who showed that leximin allocations are EQX (and Pareto optimal when all values are strictly positive), gave a pseudopolynomial-time algorithm for EQ1+PO, and delineated the complexity of combining equitability with welfare objectives. The companion paper on chores (Freeman et al., 2020) established EQ1+PO in pseudopolynomial time and showed that, in contrast to goods, leximin may violate EQ1; Sun et al. (2023) completed the complexity landscape of equitability together with welfare maximization for both goods and chores. Beyond additive valuations, Hosseini et al. (2026) showed that EQ1 allocations exist and are efficiently computable for two agents with general valuations and for many agents under doubly monotone valuations, while existence may fail—and is intractable to decide—in general, and Barman and Verma (2026) established equitability within additive margins for non-negative valuations. Finally, two recent works connect equitability to envy: Wang and Wei (2025) characterize when EQ and EF can be achieved simultaneously when monetary subsidies are allowed, and Wang et al. (2026) show that EF1 is always compatible with an equitability notion imposed across groups of agents. Our work complements these by studying the compatibility of individual-level relaxations (EQ1/EQX with EF1/EFX) without transfers. Simultaneous fairness guarantees. A recurring theme in fair division is whether several desiderata can be achieved by a single allocation. The most prominent combinations pair fairness with efficiency: maximum Nash welfare allocations are EF1+PO (Caragiannis et al., 2019), equitable analogues were given by Freeman et al. (2019); Freeman et al. (2020), and the long-standing existence question of EF1+PO for chores was recently resolved positively (Mahara, 2026). Closer to our agenda are combinations of two fairness notions. Garg and Sharma (2025) map out the logical implications among more than twenty fairness notions; their question—whether every allocation satisfying one notion satisfies another—is complementary to ours, which asks whether some allocation satisfies both. Akrami and Rathi (2025) and Akrami and Reichert (2026) combined MMS approximations with EFX/EF1, and Akrami et al. (2026a) achieved EF1 and epistemic-EFX simultaneously. To the best of our knowledge, the envy-equitability axis has so far been addressed only with monetary transfers (Wang and Wei, 2025), at the group level (Wang et al., 2026), or within a single notion across the stages of a randomized allocation (Bhaskar et al., 2026); our paper provides the first systematic study of deterministic and randomized compatibility between item-level relaxations of envy-freeness and equitability, for both goods and chores. Structured valuation classes. Restricted preference domains often admit substantially stronger guarantees. For binary (dichotomous) marginals, truthful mechanisms yield Lorenz-dominating allocations that are simultaneously EFX and MNW (Babaioff et al., 2021); for matroid-rank valuations, MNW allocations are EF1 and utilitarian-optimal (Benabbou et al., 2020), and a range of justice criteria can be computed efficiently, also under entitlements (Viswanathan and Zick, 2023; Suksompong and Teh, 2023; Bu et al., 2023). For bivalued goods, MNW implies EFX (Amanatidis et al., 2021), and for personalized bivalued goods, Jin and Tao (2025) characterized Pareto optimality and proved that EFX allocations always exist. These results sharpen the message of our impossibility construction: on normalized personalized-bivalued instances with strictly positive values, EFX allocations exist (Jin and Tao, 2025) and EQX allocations exist via leximin (Freeman et al., 2019), yet we show that no allocation may satisfy even EF1 and EQ1 together. Our positive results for normalized binary goods (up to seven agents, and any number of agents under laminar approval sets) identify binary structure as a route to compatibility as well. Fair division of chores. Fairness notions for chores are not mirror images of their goods counterparts, and the chores landscape is generally harder: EFX allocations need not always exist for additive chores (He and Tao, 2026), whereas exact EFX (with PO) is achievable in polynomial time for binary chores (Tao et al., 2025). On the equitability side, Freeman et al. (2020) and Sun et al. (2023) give existence and complexity results for EQ1 chores. Our binary-chores algorithm complements Tao et al. (2025): instead of pairing EFX with efficiency, we pair it with EQX, again without normalization and for any number of agents; for the broader class of restricted-additive chores we obtain EF1+EQ1. Randomized allocations and best-of-both-worlds fairness. The “best of both worlds” (BoBW) paradigm asks for randomized allocations that are exactly fair in expectation while every realized allocation retains an approximate guarantee: Aziz et al. (2024) showed that ex-ante EF together with ex-post EF1 is always achievable in polynomial time (and that adding efficiency leads to impossibilities). For binary valuations, Halpern et al. (2020) show that lexicographically tie-broken MNW is group-strategyproof, EF1, and Pareto optimal, and that fractional MNW can be implemented as a lottery over deterministic MNW allocations. Subsequent work obtained share-based BoBW guarantees (Babaioff et al., 2022), extensions to subadditive valuations (Feldman et al., 2024), and strengthened ex-post guarantees toward EFX: in particular, Bu et al. (2024) achieve ex-ante EF with ex-post EFX for two agents, and with ex-post EFX+fractional-PO for bivalued goods. Closest to our randomized results is the recent BoBW treatment of equitability by Bhaskar et al. (2026): randomized allocations that are ex-ante EQ and ex-post EQ1 always exist for two agents, but may fail to exist for three or more agents, where existence is strongly NP-hard to decide; positive results reappear under binary valuations. For chores, Sun and Chen (2025) give a mechanism, RandChore, that is group strategyproof in expectation and simultaneously ex-ante EF, EQ and PROP and ex-post EF1, EQ1 and PROP1, as well as ex-ante and ex-post PO, whenever costs are 11-restricted additive—exactly the restricted-additive chores of Section 4.3. With the exception of Sun and Chen (2025), all of the above relax a single fairness family across the two stages (or combine envy with shares). Our randomized allocations are instead cross-notion: they are simultaneously ex-ante EF and ex-ante EQ, while every support allocation satisfies item-level relaxations of the two notions—ex-post EF1 for normalized two-agent instances (via the two-agent partitions of Kyropoulou et al., 2020, which are EF1 under either assignment of bundles), ex-post EQ1 for normalized binary goods (strengthened to ex-post EF1+EQ1 under laminar approval sets), and—by the result of Sun and Chen (2025) recalled in Section 4.3—ex-post EF1+EQ1 for restricted-additive chores. We further show that the ex-post components of the last two guarantees are best possible (Section D.2). 2 Preliminaries Problem instance. For any k∈ℕk , let [k]≔1,2,…,k[k] \1,2,…,k\. An instance consists of a set of n agents, N=[n]N=[n], a set of m items, M=o1,o2,…,omM=\o_1,o_2,…,o_m\, and a valuation profile v1,v2,…,vn\v_1,v_2,…,v_n\. Each agent i∈Ni∈ N has an additive valuation function vi:2M→ℝv_i:2^M satisfying vi(∅)=0v_i( )=0 and vi(S)=∑o∈Svi(o)v_i(S)= _o∈ Sv_i(o) for every S⊆MS M, where we write vi(o)v_i(o) instead of vi(o)v_i(\o\) for simplicity. An instance is a goods-instance if for every i∈Ni∈ N and o∈Mo∈ M vi(o)≥0v_i(o)≥ 0, and it is a chores-instance if vi(o)≤0v_i(o)≤ 0 for every i∈Ni∈ N and o∈Mo∈ M. We sometimes use g or c instead of o to refer to a good or a chore, respectively. Valuations. A valuation profile is normalized if vi(M)=vj(M)v_i(M)=v_j(M) for every i,j∈Ni,j∈ N. It is identical if vi=v_i=v for every i∈Ni∈ N. It is binary if for every i∈Ni∈ N and o∈Mo∈ M, vi(o)∈0,1v_i(o)∈\0,1\ in case of goods, and vi(o)∈0,−1v_i(o)∈\0,-1\ for chores. A valuation profile is bivalued if, for every agent i, there exist pi,qi∈ℝp_i,q_i such that vi(o)∈pi,qiv_i(o)∈\p_i,q_i\ for every item o∈Mo∈ M. If every o∈Mo∈ M has a base value v(o)v(o) and vi(o)∈0,v(o)v_i(o)∈\0,v(o)\ for every agent i∈Ni∈ N, then the instance is restricted additive. Both bivalued and restricted additive instances are generalizations of binary valuations. Allocation. An allocation A=(A1,…,An)A=(A_1,…,A_n) is an n-partition of the set of items M, i.e., ⋃i∈NAi=M _i∈ NA_i=M and Ai∩Aj=∅A_i∩ A_j= for every distinct i,j∈Ni,j∈ N. Each bundle AiA_i is allocated to agent i, and we refer to vi(Ai)v_i(A_i) as agent i’s (realized) utility; in chores instances, we call −vi(Ai)-v_i(A_i) her disutility (or cost). A randomized allocation A (a.k.a. lottery) is a probability distribution over deterministic allocations A(1),…,A(k)A^(1),…,A^(k). Let pℓ∈[0,1]p_ ∈[0,1] denote the probability of A(ℓ)A^( ) for every ℓ∈[k] ∈[k] and ∑ℓ∈[k]pℓ=1. _ ∈[k]p_ =1. Deterministic Fairness. An allocation A is equitable (EQ) if vi(Ai)=vj(Aj)v_i(A_i)=v_j(A_j) for every i,j∈Ni,j∈ N. In a goods instance, an allocation A is equitable up to one good EQ1 if for every i,j∈Ni,j∈ N such that Aj≠∅A_j≠ we have vi(Ai)≥vj(Aj∖g)v_i(A_i)≥ v_j(A_j \g\) for some g∈Ajg∈ A_j. It is equitable up to any good (EQX) if the inequality holds for every g∈Ajg∈ A_j. For chores, A is EQ1 (respectively, EQX) if, for every i,j∈Ni,j∈ N with Ai≠∅A_i≠ , the inequality vi(Ai∖c)≥vj(Aj)v_i(A_i \c\)≥ v_j(A_j) holds for some (respectively, every) c∈Aic∈ A_i. An allocation A is envy-free (EF) if vi(Ai)≥vi(Aj)v_i(A_i)≥ v_i(A_j) for all i,j∈Ni,j∈ N. In a goods instance, A is envy-free up to one good EF1 if for every i,j∈Ni,j∈ N such that Aj≠∅A_j≠ , we have vi(Ai)≥vi(Aj∖g)v_i(A_i)≥ v_i(A_j \g\) for some good g∈Ajg∈ A_j. It is envy-free up to any good (EFX) if the inequality holds for every g∈Ajg∈ A_j. For chores, A is EF1 (respectively, EFX) if, for every i,j∈Ni,j∈ N with Ai≠∅A_i≠ , the inequality vi(Ai∖c)≥vi(Aj)v_i(A_i \c\)≥ v_i(A_j) holds for some (respectively, every) c∈Aic∈ A_i. Note that under identical valuations the corresponding envy and equitability notions coincide. Randomized (ex-ante) Fairness. A randomized allocation A is ex-ante equitable if all agents have the same expected utility; i.e., for every i,j∈Ni,j∈ N, ∑ℓ∈[k]pℓvi(Ai(ℓ))=∑ℓ∈[k]pℓvj(Aj(ℓ)). _ ∈[k]p_ v_i(A_i^( ))= _ ∈[k]p_ v_j(A_j^( )). It is ex-ante envy-free if no agent envies another in expectation; i.e., for every i,j∈Ni,j∈ N, ∑ℓ∈[k]pℓvi(Ai(ℓ))≥∑ℓ∈[k]pℓvi(Aj(ℓ)). _ ∈[k]p_ v_i(A_i^( ))≥ _ ∈[k]p_ v_i(A_j^( )). A satisfies a fairness notion ex-post if every allocation in its support satisfies that notion; e.g., A is ex-post EF1 if every A(ℓ)A^( ) in A is EF1. 3 Deterministic Guarantees 3.1 Fundamental Barriers To warm up, we show that EF1 and EQ1 remain incompatible even under normalized and bivalued valuations, and deciding whether an instance admits such a solution is NP-hard even for two agents. Proposition 1. For n≥3n≥ 3 agents with normalized bivalued valuations, an EF1+EQ1 allocation may not exist. Proof Sketch. The instance consists of m=2nm=2n goods and is depicted below: agents 1,…,n−11,…,n-1 value g1g_1 at 11 and every other good at ε , while agent n values every good at δ:=1+(2n−1)ε2nδ:= 1+(2n-1) 2n, where ε>0 >0 is small enough that (2n−1)ε<δ(2n-1) <δ. g1g2⋯g2nagents 1,…,n−11ε⋯εagent nδ⋯δ array[]c|c&g_1&g_2&·s&g_2n\\ 1,…,n-1&1& &·s& \\ agent n&δ&δ&·s&δ array Since some agent i<ni<n misses g1g_1 and thus realizes utility below δ, EQ1 forces agent n to receive at most one good; by pigeonhole, some agent then holds at least three goods, whom agent n EF1-envies. The full proof, and an analogous construction for chores, appears in Section A.1. Notably, all but one agent have identical valuations: although the envy-based and equitability-based notions coincide under identical valuations, a single deviating agent already destroys simultaneous existence. ∎ Remark 1. Personalization is essential to Proposition 1: under a common bivalued domain, where vi(o)∈p,qv_i(o)∈\p,q\ with the same p>q≥0p>q≥ 0 for all agents, normalization forces every agent to value the same number of items at p, so no agent can play the role of the flat agent n above. This class contains binary valuations (q=0q=0), for which we obtain positive results below; for q>0q>0, the existence of EF1+EQ1 allocations is an intriguing open problem; an exhaustive search over instances with up to five agents produced no counterexample. Beyond non-existence, deciding whether a given (possibly unnormalized) instance admits an EF1+EQ1 allocation is intractable. Theorem 1. For two agents with additive (possibly unnormalized) valuations, deciding whether an allocation that is both EF1 and EQ1 exists is NP-hard. The proof is deferred to Section A.2; it establishes a general case for the up-to-k-item versions of both notions. The normalization assumption is necessary for the simultaneous satisfaction of EF1 and EQ1. Consider two agents and four goods, where one agent values every good at 1 and the other values every good at 0. No EF1 solution that allocates all the items is EQ1. Furthermore, we show next that even under normalized binary valuations, neither EF1 nor EQ1 can, in general, be strengthened to their respective “up to any” counterparts. This motivates the study of restricted valuations, such as two-agent instances and binary valuations (Section 3.2 and Section 3.3), and probabilistic compatibility across ex-ante and ex-post worlds (Section 4). Towards positive results, we first consider normalized two-agent instances with general additive valuations. We then turn to binary valuations, where simultaneous guarantees can be obtained for larger number of agents. 3.2 Two-Agent Instances Notice that the impossibility in Proposition 1 applies to instances with at least three agents. For two-agent goods instances, normalization is sufficient to guarantee the simultaneous existence of the stronger notions EFX and EQX. However, EFX+EQX allocations need not exist for chores instances, even for two agents. Proposition 2. For normalized goods instances with two agents, an EFX+EQX allocation always exists. However, such an allocation may not exist for normalized chores instances with two agents. The existence guarantee follows via the leximin++ allocation for the instance that maximizes the value of the worst-off agent, and subject to that maximizes the number of items in the bundle of this agent. The complete proof as well as the counterexample for chores are presented in Section A.4. Although EFX+EQX may fail for chores, both goods and chores admit the weaker combination EF1+EQ1 in polynomial time. For goods, the algorithm maintains bundles A1,A2A_1,A_2 and realized utilities Ui=vi(Ai)U_i=v_i(A_i). At each iteration, an agent i with lower realized utility receives a remaining good g that maximizes vi(g)−vj(g)v_i(g)-v_j(g). Algorithm 1 Greedy-Balance for two-agent goods Input: A normalized two-agent goods instance Output: An allocation (A1,A2)(A_1,A_2) 1: Initialize A1,A2←∅A_1,A_2← , U1,U2←0U_1,U_2← 0, and R←MR← M. 2: while R≠∅R≠ do 3: if U1≤U2U_1≤ U_2 then 4: Choose g∈argmaxh∈Rv1(h)−v2(h)g∈ _h∈ R\v_1(h)-v_2(h)\. 5: A1←A1∪gA_1← A_1∪\g\ and U1←U1+v1(g)U_1← U_1+v_1(g). 6: else 7: Choose g∈argmaxh∈Rv2(h)−v1(h)g∈ _h∈ R\v_2(h)-v_1(h)\. 8: A2←A2∪gA_2← A_2∪\g\ and U2←U2+v2(g)U_2← U_2+v_2(g). 9: end if 10: R←R∖gR← R \g\. 11: end while 12: return (A1,A2)(A_1,A_2). The following invariant connects the equitability and envy comparisons. Lemma 1. At every stage of Algorithm 1, v1(A1)≥v2(A1) and v2(A2)≥v1(A2).v_1(A_1)≥ v_2(A_1) and v_2(A_2)≥ v_1(A_2). Proof. We prove the first inequality; the second is symmetric. Define Δ(g)=v1(g)−v2(g) (g)=v_1(g)-v_2(g). Suppose that, at some stage, Δ(A1)<0 (A_1)<0. Since the valuations are normalized, Δ(M)=0 (M)=0, and hence there exist g∈A1g∈ A_1 and h∉A1h∉ A_1 such that Δ(g)<0<Δ(h). (g)<0< (h). Consider the iteration in which g was assigned to agent 11. The good h must already have been allocated; otherwise, the algorithm would have selected h instead of g. Thus, h was assigned earlier to agent 2. At that earlier iteration, however, g was still available and satisfied Δ(g)<Δ(h) (g)< (h). Since agent 22 chooses a remaining good minimizing Δ(⋅) (·), the algorithm should have selected g rather than h, a contradiction. ∎ Theorem 2. For normalized goods instances with two agents, Algorithm 1 computes an EF1+EQ1 allocation in polynomial time. Proof. Let A=(A1,A2)A=(A_1,A_2) be the returned allocation. Without loss of generality, assume v1(A1)≤v2(A2).v_1(A_1)≤ v_2(A_2). Let g be the last good assigned to agent 22. Immediately before receiving g, agent 22 had lower realized utility than agent 11. Moreover, every good allocated after g was assigned to agent 11. By monotonicity, v1(A1)≥v2(A2∖g),v_1(A_1)≥ v_2(A_2 \g\), establishing EQ1. It remains to prove EF1. Assume agent 11 envies agent 22. Since A2∖gA_2 \g\ was agent 2’s bundle at an intermediate stage of the algorithm, we apply Lemma 1 at that stage. Combining with the EQ1 guarantee above gives v1(A1)≥v2(A2∖g)≥v1(A2∖g),v_1(A_1)≥ v_2(A_2 \g\)≥ v_1(A_2 \g\), which is precisely the EF1 condition. The case in which agent 2 envies agent 1 is symmetric. The algorithm performs m iterations and can be implemented in polynomial time. ∎ The same balancing idea, with the inequalities and selection rule adjusted for disutilities, yields the analogous result for chores; see Section A.4 for a complete proof. Corollary 1. For normalized chores instances with two agents, Algorithm 5 computes an EF1+EQ1 allocation in polynomial time. 3.3 Binary Valuations The incompatibility result of Proposition 1 for bivalued valuations raises the question of whether EF1+EQ1 allocations exist under the more structured setting of binary valuations. Binary valuations are both practically relevant and theoretically well studied, forming the basis of many recent advances in fair division (Halpern et al., 2020; Barman et al., 2018; Babaioff et al., 2021; Benabbou et al., 2020; Bu et al., 2023) 3.3.1 Goods We focus on simultaneously achieving EF1+EQ1, and design a polynomial-time algorithm when there are at most seven agents. We further discuss the challenges in extending this approach beyond n=7n=7.11 1 In a sharp contrast, Theorem 5 shows that for chores, stronger notions of EFX and EQX can be simultaneously guaranteed for any n and without normalization. Algorithm description. The algorithm proceeds in three phases: a flow computation first constructs an egalitarian-optimal partial allocation that raises every agent to the largest utility level t attainable by all agents simultaneously; utility-preserving swaps then bring the residual goods into a structured form; and, finally, each remaining good is “scattered” to an agent who does not value it. A detailed description: Our algorithm starts by removing all goods valued by no agent and storing them in J. Let t be the largest integer for which every agent can simultaneously receive t valued goods. Among all partial allocations P=(P1,…,Pn)P=(P_1,…,P_n) satisfying t≤|Pi|≤t+1for every i∈N,t≤|P_i|≤ t+1 every i∈ N, where every good in PiP_i is valued by i, choose one maximizing the number of assigned goods (equivalently, the number of agents receiving t+1t+1 goods). Both t and P can be found by integral network flow. Let R=M∖⋃i∈NPiR=M _i∈ NP_i. In the residual alternating graph, direct an edge from an agent i to each good in PiP_i, and direct an edge from an unowned good or a good owned by another agent to each agent who values it. Let S be the set of agents reachable from R. For Z:=R∪⋃i∈SPiZ:=R∪ _i∈ SP_i and each g∈Zg∈ Z, define the type of g by τ(g):=i∈S:vi(g)=1.τ(g):=\i∈ S:v_i(g)=1\. As shown below, τ(g)τ(g) is a nonempty subset of S. We call g proper-type if τ(g)⊊Sτ(g) S, and full-type if τ(g)=Sτ(g)=S. Algorithm 2 Level-and-Scatter for at most seven agents 0: A normalized binary goods instance with n≤7n≤ 7 agents 0: An allocation (A1,…,An)(A_1,…,A_n) 1: Remove from M all goods that every agent values at 00 and store them in J. 2: Compute the maximum feasible egalitarian level t and set B←t+1B← t+1. 3: Compute a maximum partial allocation P=(P1,…,Pn)P=(P_1,…,P_n) such that every good in PiP_i is valued by i and t≤|Pi|≤Bt≤|P_i|≤ B for every i. 4: Let R←M∖⋃i∈NPiR← M _i∈ NP_i. 5: Construct the residual alternating graph and let S be the set of agents reachable from R. 6: while there exist g∈Rg∈ R, h∈Sh∈ S, and g′∈Phg ∈ P_h such that τ(g)=Sτ(g)=S and τ(g′)≠Sτ(g )≠ S do 7: Ph←(Ph∖g′)∪gP_h←(P_h \g \)∪\g\. 8: R←(R∖g)∪g′R←(R \g\)∪\g \. 9: end while 10: Initialize Ai←PiA_i← P_i for every i∈Ni∈ N. 11: for each g∈Rg∈ R do 12: Set T←τ(g)T←τ(g). 13: Choose j∈N∖Tj∈ N T such that vi(Aj∪g)≤Bv_i(A_j∪\g\)≤ B for every i∈Ti∈ T. 14: Aj←Aj∪gA_j← A_j∪\g\. 15: end for 16: Distribute the goods in J arbitrarily. 17: return (A1,…,An)(A_1,…,A_n). The difficulty is that a residual good cannot be assigned to an agent who values it without increasing that agent’s realized utility from t+1t+1 to t+2t+2, thereby violating EQ1. We therefore assign each residual good g to an agent outside its type τ(g)τ(g), who values it at zero. Such an assignment must also ensure that no agent in τ(g)τ(g) values the recipient’s resulting bundle above t+1t+1, as otherwise EF1 may fail. Lemmas 2-5 reduce the absence of a feasible recipient to a counting obstruction. Lemma 6 rules out this obstruction for n≤7n≤ 7, separately for residual goods of proper and full type. We next establish the structural and counting properties needed for this argument. The proofs of the following lemmas are deferred to the end of this subsection. Lemma 2. Let P, R, and S be as defined immediately before the swap phase. Then: 1. every agent in S receives exactly B=t+1B=t+1 goods in P; 2. every good in Z=R∪⋃i∈SPiZ=R∪ _i∈ SP_i is valued only by agents in S; and 3. every good valued by an agent outside S is assigned to an agent outside S. Consequently, for k:=vi(M)k:=v_i(M), we have k≤∑j∉S|Pj|.k≤ _j∉ S|P_j|. Proof. If some i∈Si∈ S had |Pi|=t|P_i|=t, an alternating path from a residual good to i could be augmented. All internal agents on the path would keep the same number of valued goods, while i would gain one. The resulting partial allocation would still give every agent between t and B valued goods and would assign one additional good, contradicting the maximality of P. This proves the first claim. The goods reachable in the residual alternating graph are exactly R∪⋃i∈SPiR∪ _i∈ SP_i. From every reachable good there is an outgoing edge to each agent who values it (other than its owner, who is already in S when the good is assigned inside S); hence every such valuer is reachable and belongs to S. This proves the second claim. For the third, a good valued by an agent outside S can therefore belong neither to R nor to a bundle PiP_i with i∈Si∈ S. All k goods valued by that agent are consequently contained in the bundles outside S, whose total cardinality is ∑j∉S|Pj| _j∉ S|P_j|. ∎ Lemma 3. If R≠∅R≠ , then |N∖S|≥2|N S|≥ 2. Proof. Maximality of the egalitarian level t implies that some agent receives only t goods in P. By Lemma 2(1), this agent lies outside S, so N∖SN S is nonempty. If N∖S=jN S=\j\, then |Pj|=t|P_j|=t and Lemma 2(3) gives k≤tk≤ t. On the other hand, R≠∅R≠ implies S≠∅S≠ , and every agent in S receives t+1t+1 valued goods, so k≥t+1k≥ t+1, a contradiction. ∎ Assume henceforth that R≠∅R≠ , and write s:=|S|,r:=|N∖S|,B:=t+1.s:=|S|, r:=|N S|, B:=t+1. By Lemma 3, r≥2r≥ 2. Moreover, at least one agent outside S receives B−1B-1 goods, and every other outside agent receives at most B. Lemma 2(3) therefore yields the mass bounds k≤∑j∉S|Pj|≤rB−1,k≤ _j∉ S|P_j|≤ rB-1, (1) and, for every i∈Si∈ S, k−B≤(r−1)B−1.k-B≤(r-1)B-1. (2) Lemma 4. Each iteration of the swap phase preserves every agent’s utility, the maximality of P, the set Z, and the property that every good in Z is valued only by agents in S. The swap phase terminates, and at termination either no good g∈Rg∈ R has τ(g)=Sτ(g)=S, or every good in ⋃i∈SPi _i∈ SP_i has type S. Proof. The agent h values both exchanged goods: g is valued by every agent in S, while g′∈Phg ∈ P_h is valued by its recipient. Thus h’s utility and bundle size remain B, and all other bundles are unchanged. Exactly one assigned and one residual good are exchanged, so the number of assigned goods, and hence the maximality of P, are preserved. The exchange takes place entirely within Z, so Z and its closure property are unchanged. Finally, the number of full-type goods in R decreases by one in every swap, because g has type S and g′g does not; hence the phase terminates after at most |M||M| swaps. If a full-type residual good remains at termination, the absence of a further swap implies that no bundle PhP_h with h∈Sh∈ S contains a good whose type is a proper subset of S. ∎ Lemma 5. Immediately before any iteration of the scattering phase, vi(Aj)≤Bfor all i,j∈N.v_i(A_j)≤ B all i,j∈ N. (3) Let g be the residual good processed in that iteration, let T=τ(g)T=τ(g), and write q=|T|q=|T|. If no feasible recipient exists, then some agent i∈Ti∈ T values at least B⌈n−q⌉B n-qq (4) goods contained in bundles whose recipients lie outside T. Proof. The invariant (3) holds initially because |Pj|≤B|P_j|≤ B for every j. When a good of type T is assigned, its value is zero to agents outside T, while the choice of its recipient preserves the bound for agents in T. Thus the invariant is maintained inductively. There are n−qn-q candidate recipients in N∖TN T. If a candidate j cannot receive g, then, by the invariant, some i∈Ti∈ T must satisfy vi(Aj)=Bv_i(A_j)=B; otherwise adding g would preserve the cap for every valuer. Charge each blocked bundle to one such agent. Some i∈Ti∈ T is charged at least ⌈(n−q)/q⌉ (n-q)/q bundles. These disjoint bundles each contain B goods valued by i, which proves the claim. ∎ The following elementary inequalities are the only point at which the bound of seven agents is used. Lemma 6. Let n=s+r≤7n=s+r≤ 7 with r≥2r≥ 2. Then ⌈n−q⌉ n-qq ≥r−1 ≥ r-1 for every 1≤q≤s−1, every 1≤ q≤ s-1, (5) ⌈rs⌉ rs ≥r−s. ≥ r-s. (6) Proof. For 1≤q≤s−11≤ q≤ s-1, q(r−1)≤(s−1)(r−1)=sr−n+1.q(r-1)≤(s-1)(r-1)=sr-n+1. Since s+r=ns+r=n and n≤7n≤ 7, sr≤⌊n24⌋≤2n−2.sr≤ n^24 ≤ 2n-2. Therefore q(r−1)≤n−1<nq(r-1)≤ n-1<n, or equivalently (n−q)/q>r−2(n-q)/q>r-2, which proves (5). For (6), if r≤s+1r≤ s+1, then r−s≤1≤⌈r/s⌉r-s≤ 1≤ r/s . If r≥s+2r≥ s+2, the inequality s+r≤7s+r≤ 7 implies s≤2s≤ 2. For s=1s=1 the claim is immediate. For s=2s=2, we have r≤5r≤ 5 and ⌈r/2⌉≥r−2=r−s r/2 ≥ r-2=r-s. ∎ The two possible kinds of residual goods—proper type and full type—are handled separately next. Lemma 7. If a residual good g satisfies τ(g)=T⊊Sτ(g)=T S, then the scattering phase has a feasible recipient for g. Proof. Let q=|T|≤s−1q=|T|≤ s-1 and suppose that g has no feasible recipient. By Lemmas 5 and 6, some i∈Ti∈ T values at least (r−1)B(r-1)B goods in bundles of agents outside T, and therefore outside her original bundle PiP_i. However, PiP_i contains B of the k goods valued by i, so (2) implies that at most (r−1)B−1(r-1)B-1 goods valued by i lie outside PiP_i, a contradiction. ∎ Lemma 8. If a residual good g satisfies τ(g)=Sτ(g)=S after the swap phase, then the scattering phase has a feasible recipient for g. Proof. By Lemma 4, every good in the sBsB-good core ⋃h∈SPh _h∈ SP_h is valued by every agent in S. Thus, for each i∈Si∈ S, the number of i-valued goods outside this core is at most k−sB≤(r−s)B−1,k-sB≤(r-s)B-1, (7) where the inequality follows from (1). Because the residual full-type good itself lies outside the core and is valued by i, we also have k−sB≥1k-sB≥ 1. Thus, if r≤sr≤ s, the displayed upper bound is already a contradiction and no full-type residual good can remain; it remains to consider r≥s+1r≥ s+1. A full-type good can be assigned only to one of the r agents outside S. If every one of these bundles were blocked, Lemma 5 would give some i∈Si∈ S that values at least B⌈rs⌉≥(r−s)B rs ≥(r-s)B goods in outside bundles, where the last inequality follows from Lemma 6. This contradicts (7). Hence a feasible recipient exists. ∎ The preceding lemmas cover all configurations. Indeed, if R≠∅R≠ , then S≠∅S≠ and Lemma 3 gives r≥2r≥ 2. Every residual type is nonempty and is either a proper subset of S or equal to S; Lemmas 7 and 8 handle these two exhaustive cases. For n≤2n≤ 2, these conditions are incompatible, so R must be empty. Lemma 6 applies to every listed pair (s,r)(s,r). Theorem 3. For normalized binary goods instances with at most seven agents, Algorithm 2 computes an EF1 + EQ1 allocation in polynomial time. Proof. If R=∅R= , no scattering is needed. Every realized utility is t or B=t+1B=t+1, and each PjP_j has at most B goods. Adding junk goods does not affect any value. Hence the allocation is EQ1, and vi(Aj)=vi(Pj)≤B≤vi(Pi)+1=vi(Ai)+1v_i(A_j)=v_i(P_j)≤ B≤ v_i(P_i)+1=v_i(A_i)+1 for all i,ji,j, which implies EF1. Now suppose R≠∅R≠ . Lemma 4 shows that the swap phase terminates without changing any utility or closure property. During the scattering phase, every residual good has either proper or full type, so Lemmas 7 and 8 guarantee a feasible recipient at every iteration, regardless of the processing order. The returned allocation is therefore complete. Every scattered good is assigned to an agent outside its type and is thus worth zero to its recipient. The junk goods are worth zero to everyone. Consequently, all realized utilities remain in t,t+1\t,t+1\, which implies EQ1. Moreover, the invariant (3) continues to hold after all residual and junk goods are assigned. Therefore, for all agents i,ji,j, vi(Aj)≤t+1≤vi(Ai)+1.v_i(A_j)≤ t+1≤ v_i(A_i)+1. If i envies j, the integer-valued utilities differ by exactly one and AjA_j contains a good valued by i; removing that good eliminates the envy. Thus the allocation is EF1. Finally, t and the maximum partial allocation P can be computed by polynomial-time integral flow. The alternating reachable set is found by graph search, the swap phase performs at most |M||M| swaps, and the scattering phase performs at most |M||M| assignments with polynomially many value checks. Hence the algorithm runs in polynomial time. ∎ The seven-agent bound enters the analysis only through Lemma 6; Remark 4 in Section A.5 explains exactly how the counting argument breaks for n≥8n≥ 8, and why we nevertheless conjecture existence for arbitrary number of agents. The bound on the number of agents can be removed when the agents’ approval sets have additional structure. For each agent i, let Γi:=g∈M:vi(g)=1 _i:=\g∈ M:v_i(g)=1\ denote her approval set. A family of approval sets is laminar if any two sets are disjoint or one contains the other. Theorem 4. For normalized binary goods instances with laminar approval sets, EF1+EQ1 allocations always exist and can be computed in polynomial time, even when the instance has an arbitrary number of agents. Proof. Normalization and laminarity imply that any two agents have either identical or disjoint approval sets. Thus, the agents can be partitioned into groups N1,…,NqN_1,…,N_q of identical agents whose approval sets Γ(1),…,Γ(q) ^(1),…, ^(q) are pairwise disjoint. Since the instance is normalized, every approval set has the same size, say k. Let r=maxℓ|Nℓ|r= _ |N_ | and u=⌊k/r⌋u= k/r . Within each group, assign every agent either u or u+1u+1 goods from the group’s approval set whenever possible. Any remaining goods are distributed as evenly as possible among the agents of a group of size r. Every agent consequently receives utility u or u+1u+1, yielding EQ1. Moreover, no bundle contains more than u+1u+1 goods from any single approval set. Hence every agent values every bundle by at most u+1u+1 while receiving utility at least u, which establishes EF1. ∎ The binary assumption in Theorem 4 is essential: there exists a normalized restricted-additive goods instance with three agents and laminar approval sets that admits no EF1+EQ1 allocation. Agent i’s approval set is Γi=o∈M:vi(o)>0 _i=\o∈ M:v_i(o)>0\, and a family of approval sets is laminar if any two of its members are either disjoint or nested. The proof of Theorem 4 uses the following structural observation. Observation 1. In a normalized, restricted-additive instance with laminar approval sets, any two agents i,ji,j either have disjoint approval sets or satisfy vi=vjv_i=v_j. Proof. By laminarity, assume Γi⊆Γj _i _j (otherwise the sets are disjoint). Restricted additivity gives vi(M)=∑o∈Γiv(o)v_i(M)= _o∈ _iv(o) and vj(M)=∑o∈Γjv(o)v_j(M)= _o∈ _jv(o), with every base value v(o)>0v(o)>0 for o∈Γjo∈ _j. If Γi⊊Γj _i _j, then vi(M)<vj(M)v_i(M)<v_j(M), contradicting normalization. Thus Γi=Γj _i= _j, and both agents value each o∈Γio∈ _i at v(o)v(o) and everything else at 00, i.e., vi=vjv_i=v_j. ∎ Consequently, such an instance partitions the agents into groups of identical agents with pairwise disjoint approval sets, which is exactly the structure used in Theorem 4. The binary assumption in Theorem 4 cannot be dropped: Proposition 3. For three agents with normalized restricted-additive valuations and laminar approval sets, an allocation of goods that is both EF1 and EQ1 may fail to exist. Proof. Consider m=7m=7 goods: one heavy good h with base value v(h)=6v(h)=6, and six light goods ℓ1,…,ℓ6 _1,…, _6 with v(ℓk)=1v( _k)=1. The approval sets are Γ1=Γ2=h,Γ3=ℓ1,…,ℓ6, _1= _2=\h\, _3=\ _1,…, _6\, each agent valuing the goods in her approval set at their base values and all other goods at 00: h ℓ1 _1 ℓ2 _2 ℓ3 _3 ℓ4 _4 ℓ5 _5 ℓ6 _6 a1a_1 66 00 00 00 00 00 00 a2a_2 66 00 00 00 00 00 00 a3a_3 00 11 11 11 11 11 11 Every agent values the grand bundle at 66 (the instance is normalized), the valuations have the form vi(o)∈0,v(o)v_i(o)∈\0,v(o)\ (restricted additive), and the two distinct approval sets h\h\ and ℓ1,…,ℓ6\ _1,…, _6\ are disjoint, hence laminar. In any allocation, at least one of agents a1,a2a_1,a_2 realizes utility 00, since their common approval set contains the single good h. To maintain EQ1 against this zero-utility agent, agent a3a_3 can receive at most one good from her approval set Γ3=ℓ1,…,ℓ6 _3=\ _1,…, _6\. Hence at least five light goods go to agents a1a_1 and a2a_2, so one of them receives at least three light goods. Agent a3a_3’s value for that bundle is at least 33, and at least 22 after the removal of any single good, while her own utility is at most 11; hence she EF1-envies that agent. Therefore no allocation is simultaneously EF1 and EQ1. ∎ 3.3.2 Chores The situation is considerably more favorable for chores. In particular, neither normalization nor a bound on the number of agents is required, and both fairness guarantees can be strengthened from their “up to one” versions to their “up to any” versions. Theorem 5. For binary chores instances, an EFX+EQX allocation always exists and can be computed in polynomial time, even when the instance has an arbitrary number of agents and unnormalized valuations. Notation. For binary chores we use the following notation. The set of chores that have value 00 for agent i is denoted by Mi0:=c∈M:vi(c)=0M_i^0:=\c∈ M:v_i(c)=0\. We write M0:=⋃i∈NMi0M^0:= _i∈ NM_i^0 for the set of chores that are zero-valued for some agent, and M1:=M∖M0M^1:=M M^0 for the chores valued −1-1 by all agents. We also need these sets restricted to a subset of active agents N¯⊆N N N: M1(N¯) M^1( N) :=c∈M:vi(c)=−1∀i∈N¯, :=\c∈ M:\ v_i(c)=-1\ ∀ i∈ N\, M0(N¯) M^0( N) :=M∖M1(N¯). :=M M^1( N). Algorithm description. The algorithm first partitions M1M^1, the chores disliked by everyone, as evenly as possible into n bundles, each containing either k=⌊|M1|/n⌋k= |M^1|/n or k+1k+1 chores; we call bundles of size k rich and bundles of size k+1k+1 poor. The remaining chores (in M0M^0) are then assigned while preserving the invariant that no bundle’s value drops below −(k+1)-(k+1) from any relevant agent’s perspective. To achieve this, the algorithm repeatedly runs the Chores-Subroutine (Algorithm 3): whenever an agent i still has unallocated zero-valued chores and values some bundle BjB_j at exactly −k-k, the subroutine adds all currently unallocated chores of Mi0M_i^0 to BjB_j; agent i’s value for BjB_j is unchanged (still −k-k), and a tracker tjt_j records that agent i was the last agent to alter BjB_j. After the subroutine terminates, every remaining unallocated chore is disliked by all agents recorded in some tracker. If enough chores remain, one chore is added to every rich bundle, which yields EF+EQ among the currently active agents and an EFX+EQX completion overall. Otherwise, the poor bundles are finalized and the algorithm recurses on the remaining rich bundles and active agents, after returning to the unallocated pool all previously assigned chores that are not universally disliked within the reduced active set. We first prove three observations about properties of the Chores-Subroutine and the partial allocation obtained from it. Observation 2. Suppose that, after an execution of Chores-Subroutine, the unallocated set U is nonempty. Then every rich bundle has a nonzero tracker. Moreover, distinct rich bundles have distinct trackers. Consequently, the trackers of the rich bundles and the rich bundles are in bijection, and the number of untracked active agents equals the number of poor bundles. 0: Active agents N¯⊆N N N, target values −k,−(k+1)-k,-(k+1), bundles Bjj∈N¯\B_j\_j∈ N, unallocated set U 0: Updated bundles Bjj∈N¯\B_j\_j∈ N, trackers tjj∈N¯\t_j\_j∈ N, and unallocated set U 1: Initialize trackers tj←0t_j← 0 for all j∈N¯j∈ N. 2: while ∃i,j∈N¯∃\,i,j∈ N s.t. Mi0∩U≠∅M_i^0∩ U≠ and vi(Bj)=−kv_i(B_j)=-k do 3: Bj←Bj∪(Mi0∩U)B_j← B_j∪(M_i^0∩ U) 4: U←U∖Mi0U← U M_i^0 5: tj←it_j← i 6: end while 7: return Bjj∈N¯\B_j\_j∈ N, tjj∈N¯\t_j\_j∈ N, U Algorithm 3 Chores-Subroutine 0: A binary chores instance. 0: An EFX+EQX allocation A=(A1,…,An)A=(A_1,…,A_n). 1: Let k:=⌊|M1|/n⌋k:= |M^1|/n . 2: Partition M1M^1 into bundles B1,…,BnB_1,…,B_n with |Bj|∈k,k+1|B_j|∈\k,k+1\ for all j∈[n]j∈[n]. 3: Unallocated set U←M0U← M^0; active agents N¯←N N← N. 4: Rich bundles R←j∈N¯:|Bj|=kR←\j∈ N:|B_j|=k\ and poor bundles P←j∈N¯:|Bj|=k+1P←\j∈ N:|B_j|=k+1\. 5: (Bj,tj,U)←Chores-Subroutine(N¯,k,Bj,U)(\B_j\,\t_j\,U)← Chores-Subroutine( N,k,\B_j\,U) 6: while U≠∅U≠ do 7: Consider untracked active agents F:=i∈N¯:∄j s.t. tj=iF:=\i∈ N:\ j\ s.t. t_j=i\; and arbitrarily assign them the poor bundles, i.e., Aii∈F←Bjj∈P\A_i\_i∈ F←\B_j\_j∈ P (by Observation 2, |F|=|P||F|=|P|). 8: if (Case 1) |U|≥|R||U|≥|R| then 9: Add one chore from U to each rich bundle Bjj∈R\B_j\_j∈ R; remove these chores from U. 10: Assign rich bundles as Ai←BjA_i← B_j if tj=it_j=i. 11: Distribute each remaining c∈Uc∈ U to any agent i∈N¯i∈ N with vi(c)=0v_i(c)=0, by adding c to AiA_i; set U←∅U← , and return A=(A1,…,An)A=(A_1,…,A_n). 12: else 13: (Case 2) // 0<|U|<|R|0<|U|<|R| 14: Finalize the agents in F and redefine the active agents as N¯←N¯∖F N← N F. Also relabel each remaining rich bundle by its tracker: for each j∈Rj∈ R with tj=it_j=i, rename BjB_j as BiB_i. 14: // Active agents and bundles now share the index set N¯ N. 15: Pick any |U||U| bundles in N¯ N and give each bundle one item from U; these are the new poor bundles P. Redefine R←N¯∖PR← N P. 15: // U is empty at this stage, but the next for-loop returns some items to U. 16: for all j∈N¯j∈ N do 17: Return to U all items previously added to BjB_j from M0(N¯)M^0( N), i.e., U←U∪(Bj∖M1(N¯))U← U∪(B_j M^1( N)); Bj←Bj∩M1(N¯)B_j← B_j∩ M^1( N). // By Observation 4, no item added in line 15 is returned to U. 18: end for 19: (Bjj∈N¯,tjj∈N¯,U)←Chores-Subroutine(N¯,k,Bj,U)(\B_j\_j∈ N,\t_j\_j∈ N,U)← Chores-Subroutine( N,k,\B_j\,U) 20: end if 21: end while 22: Final assignment: For each j with tj≠0t_j≠ 0, set Atj←BjA_t_j← B_j. Assign the remaining bundles to the remaining agents via any bijection. 23: return A=(A1,…,An)A=(A_1,…,A_n) Algorithm 4 EFX+EQX for Binary Chores Proof. Distinct bundles have distinct nonzero trackers because an agent can alter at most one bundle in Chores-Subroutine: after agent i acts once, all currently unallocated chores that she values at zero are removed from U. It remains to show that every rich bundle is tracked. At the beginning of each call to Chores-Subroutine, every rich bundle consists of exactly k chores that are disliked by every active agent. Suppose some rich bundle BjB_j remains untracked after the subroutine. Since U≠∅U≠ , choose c∈Uc∈ U. By construction U⊆M0(N)U M^0(N), so some active agent i has vi(c)=0v_i(c)=0. Since BjB_j is untracked, it was never modified and vi(Bj)=−kv_i(B_j)=-k. Thus the pair i,ji,j still satisfies the while-loop condition of Chores-Subroutine, contradicting termination. Hence all rich bundles have distinct trackers. Since |N|=|R|+|P||N|=|R|+|P|, exactly |P||P| active agents are untracked. ∎ Observation 3. Consider the bundles Bjj∈N¯\B_j\_j∈ N obtained after running the Chores-Subroutine. For every i∈N¯i∈ N such that Mi0∩U≠∅M_i^0∩ U≠ , we have vi(Bj)≤−(k+1)v_i(B_j)≤-(k+1) for every bundle in Bjj∈N¯\B_j\_j∈ N. Proof. If there existed a bundle BjB_j with vi(Bj)=−kv_i(B_j)=-k, then, by the condition of the while-loop in the subroutine, we would have Mi0∩U=∅M_i^0∩ U= , a contradiction. (No bundle can have value above −k-k for any agent, since the bundles start with at least k universally disliked chores.) ∎ Next, notice that an agent i alters at most one bundle in the Chores-Subroutine: after her first iteration, all items that are zero-valued for i (i.e., all of Mi0∩UM^0_i∩ U) are assigned, and the while-loop condition is never again satisfied for i. Thus, unless a tracker equals 00, no two trackers are marked with the same agent. Observation 4. Consider the bundles Bjj∈N¯\B_j\_j∈ N obtained after running the Chores-Subroutine, and consider an agent i∈N¯i∈ N such that tj=it_j=i for some j. Then vi(c)=−1v_i(c)=-1 for every c∈Uc∈ U. Proof. Consider the iteration in which tjt_j was set to i. In this iteration, all items in U that are zero-valued for i (i.e., Mi0∩UM_i^0∩ U) are added to the bundle BjB_j. Thus every item remaining in U afterwards has value −1-1 for i, and the subroutine never adds items back to U. ∎ Proof of Theorem 5. First, we show that each step in the algorithm is well-defined. Then, we argue termination and the two fairness guarantees in the output allocation. Well-defined. Whenever U≠∅U≠ , Observation 2 shows that every rich bundle has a distinct tracker and that exactly |P||P| active agents are untracked. Thus, the poor bundles can be assigned bijectively to the untracked agents. In Case 2, the remaining active agents are exactly the trackers of the rich bundles; thus, relabeling the rich bundles by the indices of new active agents is well-defined. Termination. Each iteration of the while-loop in the Chores-Subroutine removes the nonempty set Mi0∩UM_i^0∩ U from U, strictly decreasing |U||U|; thus the subroutine terminates after at most |M||M| iterations. For the main algorithm, observe that whenever Case 1 (line 8) applies, U is set to ∅ and the algorithm terminates. It therefore suffices to bound the number of Case 2 executions. In Case 2, the active agent set N¯ N is updated to N¯∖F N F, and hence decreases by |F|=|P||F|=|P|. The only possible Case 2 execution with P=∅P= is the first one; since Case 2 has |U|>0|U|>0, it creates a nonempty new set of poor bundles. Thus, after at most one Case 2 execution that does not decrease |N¯|| N|, every subsequent Case 2 execution strictly decreases it. Hence Case 2 is executed at most n+1n+1 times. The algorithm therefore terminates after polynomially many iterations. A structural observation. Every item allocated in line 15 belongs to M1(N¯)M^1( N). Indeed, line 7 assigns the current poor bundles to agents F=i∈N¯:∄j s.t. tj=iF=\i∈ N: j s.t. t_j=i\. After the agents in F are finalized and removed in Case 2, the remaining active agents are exactly those with tj=it_j=i for some j. For each such agent i, Observation 4 gives vi(c)=−1v_i(c)=-1 for all c∈Uc∈ U. Every item of U is therefore a chore of value −1-1 to every agent in the current N¯ N, i.e., U⊆M1(N¯)U M^1( N), so the items drawn from U in line 15 lie in M1(N¯)M^1( N). If the algorithm terminates in Case 1. Suppose the algorithm terminates through Case 1. After one chore from U is added to each rich bundle, every currently active agent has realized utility −(k+1)-(k+1). Moreover, every active agent values every active bundle at most −(k+1)-(k+1): for a tracked agent this follows from Observation 4, while for an untracked agent who has a zero-valued chore in U it follows from Observation 3; if she has no such chore, she dislikes every chore added in Case 1. Now consider an agent i finalized in an earlier Case 2 execution. Her bundle was a poor bundle and therefore consists of exactly k+1k+1 chores, each valued −1-1 by i. Hence, for every c∈Aic∈ A_i, vi(Ai∖c)=−kv_i(A_i \c\)=-k. Every bundle contains at least the original k chores from M1M^1, which are valued −1-1 by every agent, and therefore vi(Aj)≤−kv_i(A_j)≤-k for every i,ji,j. Thus every previously finalized agent satisfies EFX as well. Moreover, every previously finalized poor bundle consists of k+1k+1 chores that were disliked by every agent who remained active at the time it was finalized. Since the current active-agent set is a subset of that set, every currently active agent values every previously finalized bundle at −(k+1)-(k+1). Finally, the remaining chores distributed in line 11 are zero-valued to their recipients. Hence they do not change any recipient’s realized utility and can only weakly decrease how other agents value that recipient’s bundle. Consequently, all agents have realized utility −(k+1)-(k+1), so EQ (and hence EQX) holds, and the EFX guarantee established above is preserved. Therefore the final allocation is EFX+EQX. For the rest of the proof, we assume that the algorithm terminates without executing Case 1. EQX. Suppose vi(Ai)=−kv_i(A_i)=-k and vj(Aj)=−(k+1)v_j(A_j)=-(k+1) for two agents i,ji,j (by construction all realized utilities lie in −k,−(k+1)\-k,-(k+1)\). We show that AjA_j consists of exactly k+1k+1 items, each of value −1-1 to j, which suffices to ensure A satisfies EQX. Bundle BjB_j became poor either in line 2 (initial partition of M1M^1) or by acquiring one item in line 15; by the structural observation, this item lies in M1(N¯)M^1( N) and hence has value −1-1 for j. The for-loop in lines 17-19 removes every item not in M1(N¯)M^1( N)—in particular every item that is zero-valued for its tracked recipient—from every active bundle before further items are added, and the items distributed in line 11 are always zero-valued for their recipients. Hence AjA_j consists of exactly k+1k+1 items, each valued −1-1 by j, and for every c∈Ajc∈ A_j, vj(Aj∖c)=−k=vi(Ai),v_j(A_j \c\)=-k=v_i(A_i), establishing EQX. EFX. Every final bundle contains at least k chores from the original set M1M^1, so vi(Aj)≤−kv_i(A_j)≤-k for all i,ji,j. Since every realized utility lies in −k,−(k+1)\-k,-(k+1)\, if agent i envies agent j, necessarily vi(Ai)=−(k+1)v_i(A_i)=-(k+1) and vi(Aj)=−kv_i(A_j)=-k. We show |Ai|=k+1|A_i|=k+1 with every item of AiA_i valued −1-1 by i, which suffices to ensure that A satisfies EFX. The for-loop in lines 17-19 removes every zero-valued item from every active bundle, so AiA_i consists either of k+1k+1 items from line 2, or of k items from line 2 plus one item from line 15. The line-2 items lie in M1M^1 (value −1-1 to all agents), and by the structural observation the line-15 item, if present, lies in M1(N¯)M^1( N) (also value −1-1 to i). Hence every item in AiA_i has value −1-1 for i, and for every c∈Aic∈ A_i, vi(Ai∖c)=−k=vi(Aj),v_i(A_i \c\)=-k=v_i(A_j), establishing EFX. ∎ 4 Ex-ante and Ex-post Guarantees In this section, we seek randomized allocations that are simultaneously EF+EQ ex-ante while retaining approximate fairness ex-post. For two agents, we obtain ex-post EF1(Section 4.1). Our most striking result is establishing a sharp contrast between goods and chores. For binary goods, our ex-post guarantee is EQ1 (Section 4.2), whereas for chores, the ex-post guarantee can be strengthened to EF1+EQ1, even without the normalization assumption, and extends more generally to restricted additive valuations (Section 4.3). 4.1 Two-Agent Instances The key is to ensure that the support of the randomized allocation consists only of EF1 allocations, regardless of which agent receives which bundle. We achieve this through a discrete version of exact division (consensus halving); for two agents, it always exists and can be computed in polynomial time (Kyropoulou et al., 2020). Theorem 6. For two-agent normalized instances (goods or chores), an ex-ante EF+EQ and ex-post EF1 randomized allocation always exists. Proof. We first consider goods. By the Exact1 result of Kyropoulou et al. (2020), there exists a partition X,Y\X,Y\ of M such that both agents consider both bundles to be EF1; that is, for every agent i∈1,2i∈\1,2\ and every side Z∈X,YZ∈\X,Y\, if agent i receives Z then there is a good g in the other side with vi(Z)≥vi((M∖Z)∖g)v_i(Z)≥ v_i((M Z) \g\). Consider the uniform distribution over the two allocations (X,Y)(X,Y) and (Y,X)(Y,X). Every allocation in the support is EF1 by the choice of the partition, so the randomized allocation is ex-post EF1. For the ex-ante guarantees, each agent receives each side with probability 1/21/2, so for both agents i and both bundles Z, [vi(own bundle)]=vi(X)+vi(Y)2=vi(M)2,E[v_i(own bundle)]= v_i(X)+v_i(Y)2= v_i(M)2, and the same computation applies to the other agent’s bundle. By normalization, v1(M)=v2(M)v_1(M)=v_2(M), so both agents obtain the same expected utility (ex-ante EQ), and each agent’s expected value for the other agent’s bundle equals the expected value of her own (ex-ante EF). For chores, apply the goods argument to the nonnegative cost functions di=−vid_i=-v_i, which are additive and normalized. The resulting partition X,Y\X,Y\ satisfies, for each agent i and each side Z, di(Z)≥di((M∖Z)∖c)for some c∈M∖Z.d_i(Z)\ ≥\ d_i ((M Z) \c\ ) some c∈ M Z. Written for the orientation in which agent i receives the side M∖ZM Z, this states precisely that there is a chore c in her own bundle with vi((M∖Z)∖c)≥vi(Z)v_i ((M Z) \c\ )≥ v_i(Z), i.e., chores-EF1. As Z ranges over both sides, both orientations are EF1 for both agents, and the uniform distribution over the two orientations is ex-post EF1 and, exactly as above, ex-ante EF+EQ. ∎ The ex-post guarantee in Theorem 6 cannot generally be strengthened to EFX. See the counter-example in Appendix D. 4.2 Binary Goods For general additive valuations, agent-independent EF1 partitions do not extend beyond two agents, as such partitions may not exist for n≥3n≥ 3. We therefore turn to binary valuations. In this setting, an allocation satisfying ex-ante EF and ex-post EF1 can be obtained by computing a fractional maximum Nash welfare (MNW) solution and implementing it as a randomized allocation supported on deterministic MNW allocations (Halpern et al., 2020). However, MNW solutions provide no equitability guarantees, either ex-ante or ex-post, since equitability may require sacrificing welfare. This is in contrast to MNW, which maximizes the geometric mean of agents’ values, and therefore yields Pareto-optimal allocations. For normalized binary goods, the uniform fractional allocation is simultaneously EF and EQ ex-ante. We show that it can be implemented as a distribution over deterministic allocations in which every agent receives either the floor or ceiling of her fractional approved utility; hence every realization is EQ1. The complete proof, based on total unimodularity, follows. Theorem 7. For normalized binary goods instances with an arbitrary number of agents, ex-ante EF+EQ and ex-post EQ1 allocation always exists. Proof. Let Γi=g∈M:vi(g)=1 _i=\g∈ M:v_i(g)=1\ be agent i’s approved goods. By normalization, all approval sets have the same size; write k:=|Γi|k:=| _i| for this common value. Set ℓ=⌊k/n⌋ = k/n and u=⌈k/n⌉u= k/n , and consider the polytope =x≥0:∑ixig=1(g∈M),ℓ≤∑g∈Γixig≤u(i∈N).P= \x≥ 0:\ aligned & _ix_ig=1&&(g∈ M),\\ & ≤ _g∈ _ix_ig≤ u&&(i∈ N) aligned \. Its constraint matrix is the node-edge incidence matrix of a bipartite graph whose two sides are the goods and the agents: each variable xigx_ig has a coefficient 11 in the row of good g, and a coefficient 11 in the row of agent i if and only if g∈Γig∈ _i (columns of non-approved pairs have only their good-row entry). Such matrices are totally unimodular, and all bounds are integral, so every vertex of P is integral. An integral point of P assigns each good to exactly one agent and gives every agent either ℓ or u approved goods; hence every vertex corresponds to a deterministic allocation whose realized utilities all lie in ℓ,u\ ,u\. The equal-share point x∗x^* with xig∗=1/nx^*_ig=1/n for all i,gi,g lies in P, because each approved degree equals ∑g∈Γi1/n=k/n∈[ℓ,u] _g∈ _i1/n=k/n∈[ ,u]. A standard bipartite-flow decomposition expresses x∗x^*, in polynomial time, as a convex combination of polynomially many integral vertices of P. Take this convex combination as the randomized allocation. Because the decomposition preserves x∗x^*, every agent receives every good with probability exactly 1/n1/n. Thus, from any agent i’s perspective, every random bundle (her own and every other agent’s) has expected value k/nk/n; hence the randomized allocation is ex-ante EF, and the expected realized utilities are all equal to k/nk/n, so it is also ex-ante EQ. Finally, consider any allocation in the support and two agents i,ji,j. Realized utilities lie in ℓ,u\ ,u\ with u−ℓ≤1u- ≤ 1. If vi(Ai)≥vj(Aj)v_i(A_i)≥ v_j(A_j), the EQ1 condition for the pair (i,j)(i,j) holds after removing any good (or vacuously if Aj=∅A_j= ). Otherwise vi(Ai)=ℓv_i(A_i)= and vj(Aj)=u=ℓ+1v_j(A_j)=u= +1; then AjA_j contains a good g approved by j, and vj(Aj∖g)=u−1=ℓ≤vi(Ai)v_j(A_j \g\)=u-1= ≤ v_i(A_i). Hence every support allocation is EQ1. ∎ Laminar binary goods. Under the laminar structure of Theorem 4, however, the ex-post guarantee can be strengthened to EF1+EQ1. As in the construction of Theorem 7, ex-ante equitability again forces us to hand goods to agents who do not value them. Under laminarity, however, any two approval sets are identical or disjoint, so we can cut every approval set into the same number of balanced blocks, let each group of identical agents rotate cyclically through the blocks of its own set, and give the surplus blocks to fixed outside agents, who value them at zero; see Section D.1 for the complete proof. Theorem 8. For normalized binary goods instances with laminar approval sets, an ex-ante EF+EQ and ex-post EF1+EQ1 randomized allocation always exists and can be computed in polynomial time, even when the instance has an arbitrary number of agents. In Section D.2 we show that the ex-post guarantee cannot be strengthened to EFX, even for laminar approval sets and even when we do not impose any ex-post equitability requirement or ex-ante envy requirement. 4.3 Chores: Escaping Normalization for Binary Valuations and Beyond For chores, stronger guarantees are available ex-post, and they require neither normalization nor any bound on the number of agents. This was established by Sun and Chen (2025) through their group-strategyproof (in-expectation) mechanism RandChore, which for 11-restricted additive costs—precisely the restricted-additive chores of our model—returns a randomized allocation that is ex-ante EF, EQ and PROP and ex-post EF1, EQ1 and PROP1, while additionally being ex-ante and ex-post PO. Restricting their guarantee to the two notions we study yields the following statement. Theorem 9 (Sun and Chen, 2025, Theorem 4.4). For restricted-additive chores instances, not necessarily normalized, an ex-ante EF+EQ and ex-post EF1+EQ1 randomized allocation can be computed in polynomial time for arbitrary number of agents. For completeness, we record a short self-contained proof of the statement in this form. The construction below can be seen as a partial derandomization of RandChore: it fixes, rather than randomizes, the assignment of the chores that some agent values at zero, and it rotates a single round-robin partition instead of drawing a fresh permutation. Proof. Let M0M^0 contain the chores that some agent values at zero, and assign each c∈M0c∈ M^0 permanently to such an agent; let Z1,…,ZnZ_1,…,Z_n be the resulting allocation. Every chore is in M1:M∖M0M^1:M M^0 and has the same value v(c)<0v(c)<0 for every agent. We now construct a common EF1+EQ1 partition of M1M^1, so that a uniform random assignment of this partition among the agents leads to an ex-ante EF+EQ randomized allocation with the desired ex-post guarantees. Since agents are identical on M1M^1, every EF1 allocation is also EQ1. Moreover, any EF1 allocation (B1,…,Bn)(B_1,…,B_n) on M1M^1 is such that all bundles BpB_p are EF1 for all agents since the valuations are identical; one such allocation can be computed via round robin. Now we construct a randomized allocation supported on n EF1+EQ1 allocations as follows: For r=0,…,n−1r=0,…,n-1, define σr(i)=1+((i−1+r)modn) _r(i)=1+((i-1+r) n) and Ai(r)=Bσr(i)∪Zi.A_i^(r)=B_ _r(i)∪ Z_i. The uniform distribution over these n allocations gives each agent every BpB_p exactly once. Therefore [vi(Ai)]=v(M1)/nE[v_i(A_i)]=v(M^1)/n for every i, proving ex-ante EQ. For i≠ji≠ j, [vi(Aj)]=v(M1)n+vi(Zj)≤v(M1)n=[vi(Ai)],E[v_i(A_j)]= v(M^1)n+v_i(Z_j)≤ v(M^1)n=E[v_i(A_i)], which proves ex-ante EF. ∎ In Section D.2 we show that the ex-post guarantee is tight, i.e. we present a binary chores instance with two agents and two chores in which no ex-ante EF+EQ randomized allocation is ex-post EFX or ex-post EQX. The counter-example, however, is not normalized, and an interesting open problem is whether an ex-ante EF+EQ and ex-post EFX+EQX allocation always exists for binary normalized chores. Since every allocation in the support of the randomized allocation constructed in Theorem 9 is simultaneously EF1 and EQ1, we obtain the following deterministic guarantee as an immediate consequence. Corollary 2. For unnormalized, restricted-additive chores instances, an EF1+EQ1 allocation always exists, and such allocations can be computed in polynomial time. 5 Concluding Remarks Our work studies the simultaneous satisfaction of fundamentally different fairness notions, within and across the deterministic and randomized settings, revealing a sharp distinction between goods and chores. It leaves several intriguing open directions, including the existence of EF1+EQ1 allocations for additive goods with n≥8n≥ 8 under normalized binary valuations, and more generally for non-personalized bivalued valuations. Conceptually, our work initiates the study of cross-notion best-of-both-worlds fairness beyond envy and equitability, where ex-ante guarantees for one fairness notion are combined with ex-post guarantees for another. AI Usage Disclosure The proof for Theorem 3 was obtained with the help of GPT-5.6 and Claude-Fable. The authors first established the result for n=3n=3 agents themselves, and subsequently extended it to n=5n=5 and then n=7n=7 agents with AI assistance. Additionally, the authors used GPT-5.6 for editorial suggestions and writing the draft. All mathematical arguments and the final text were reviewed and verified by the authors. Acknowledgments The authors acknowledge the National Science Foundation (NSF) for financial support. H and SP were supported through CAREER Awards IIS-2144413 and IIS-2107173, and LX and CZ were supported by Awards 2450124, 2517733, and 2518373. References Akrami and Rathi [2025] Hannaneh Akrami and Nidhi Rathi. Achieving maximin share and EFX/EF1 guarantees simultaneously. In Proceedings of the 39th AAAI Conference on Artificial Intelligence (AAAI), pages 13529–13537, 2025. Akrami and Reichert [2026] Hannaneh Akrami and Timo Reichert. Simultaneous ordinal maximin share and envy-based guarantees. arXiv preprint arXiv:2602.15566, 2026. Akrami et al. [2026a] Hannaneh Akrami, Ryoga Mahara, Kurt Mehlhorn, and Nidhi Rathi. Achieving ef1 and epistemic efx guarantees simultaneously. arXiv preprint arXiv:2602.11732, 2026a. Akrami et al. [2026b] Hannaneh Akrami, Alexander Mayorov, Kurt Mehlhorn, Shreyas Srinivas, and Christoph Weidenbach. A counterexample to EFX for n≥3n≥ 3 agents, m≥n+5m≥ n+5 items, submodular valuations via SAT-solving. arXiv preprint arXiv:2604.18216, 2026b. Amanatidis et al. [2021] Georgios Amanatidis, Georgios Birmpas, Aris Filos-Ratsikas, Alexandros Hollender, and Alexandros A. Voudouris. Maximum nash welfare and other stories about EFX. Theoretical Computer Science, 863:69–85, 2021. Amanatidis et al. [2023] Georgios Amanatidis, Haris Aziz, Georgios Birmpas, Aris Filos-Ratsikas, Bo Li, Hervé Moulin, Alexandros A. Voudouris, and Xiaowei Wu. Fair division of indivisible goods: Recent progress and open questions. Artificial Intelligence, 322:103965, 2023. Aziz et al. [2024] Haris Aziz, Rupert Freeman, Nisarg Shah, and Rohit Vaish. Best of both worlds: Ex ante and ex post fairness in resource allocation. Operations Research, 72(4):1674–1688, 2024. Babaioff et al. [2021] Moshe Babaioff, Tomer Ezra, and Uriel Feige. Fair and truthful mechanisms for dichotomous valuations. In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI), pages 5119–5126, 2021. Babaioff et al. [2022] Moshe Babaioff, Tomer Ezra, and Uriel Feige. On best-of-both-worlds fair-share allocations. In Proceedings of the 18th Conference on Web and Internet Economics (WINE), pages 237–255, 2022. Barman and Verma [2026] Siddharth Barman and Paritosh Verma. Fair division beyond monotone valuations with applications to equitable graph partitioning. In Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 6613–6641. SIAM, 2026. Barman et al. [2018] Siddharth Barman, Sanath Kumar Krishnamurthy, and Rohit Vaish. Greedy algorithms for maximizing nash social welfare. In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, pages 7–13, 2018. Benabbou et al. [2020] Nawal Benabbou, Mithun Chakraborty, Ayumi Igarashi, and Yair Zick. Finding fair and efficient allocations when valuations don’t add up. In Proceedings of the 13th International Symposium on Algorithmic Game Theory (SAGT), 2020. Bhaskar et al. [2026] Umang Bhaskar, Vishwa Prakash HV, Aditi Sethia, and Rakshitha. Best of both worlds guarantees for equitable allocations. In Proceedings of the 40th AAAI Conference on Artificial Intelligence (AAAI), pages 16682–16690, 2026. Brams and Taylor [1996] Steven J Brams and Alan D Taylor. Fair Division: From cake-cutting to dispute resolution. Cambridge University Press, 1996. Brandt et al. [2016] Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel D. Procaccia, editors. Handbook of Computational Social Choice. Cambridge University Press, 2016. Bu et al. [2023] Xiaolin Bu, Jiaxin Song, and Ziqi Yu. EFX allocations exist for binary valuations. In International Joint Conference on Theoretical Computer Science – Frontier of Algorithmic Wisdom (IJTCS-FAW), pages 252–262, 2023. Bu et al. [2024] Xiaolin Bu, Zihao Li, Shengxin Liu, Xinhang Lu, and Biaoshuai Tao. Best-of-both-worlds fair allocation of indivisible and mixed goods. In Proceedings of the 20th Conference on Web and Internet Economics (WINE), 2024. Budish [2011] Eric Budish. The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. Journal of Political Economy, 119(6):1061–1103, 2011. Caragiannis et al. [2019] Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel D. Procaccia, Nisarg Shah, and Junxing Wang. The unreasonable fairness of maximum nash welfare. ACM Transactions on Economics and Computation, 7(3):1–32, 2019. Chaudhury et al. [2020] Bhaskar Ray Chaudhury, Jugal Garg, and Kurt Mehlhorn. EFX exists for three agents. In Proceedings of the 21st ACM Conference on Economics and Computation (EC), pages 1–19, 2020. Dubins and Spanier [1961] Lester E Dubins and Edwin H Spanier. How to cut a cake fairly. The American Mathematical Monthly, 68(1P1):1–17, 1961. Feldman et al. [2024] Michal Feldman, Simon Mauras, Vishnu V. Narayan, and Tomasz Ponitka. Breaking the envy cycle: Best-of-both-worlds guarantees for subadditive valuations. In Proceedings of the 25th ACM Conference on Economics and Computation (EC), pages 1236–1266, 2024. Foley [1966] Duncan Karl Foley. Resource allocation and the public sector. Yale University, 1966. Freeman et al. [2019] Rupert Freeman, Sujoy Sikdar, Rohit Vaish, and Lirong Xia. Equitable allocations of indivisible goods. In Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI), pages 280–286, 2019. Freeman et al. [2020] Rupert Freeman, Sujoy Sikdar, Rohit Vaish, and Lirong Xia. Equitable allocations of indivisible chores. In Proceedings of the 19th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), pages 384–392, 2020. Garg and Sharma [2025] Jugal Garg and Eklavya Sharma. Exploring relations among fairness notions in discrete fair division. arXiv preprint arXiv:2502.02815, 2025. Gkatzelis et al. [2021] Vasilis Gkatzelis, Alexandros Psomas, and Xizhi Tan. Fair and efficient online allocations with normalized valuations. In Proceedings of the 35th AAAI conference on artificial intelligence, volume 35, pages 5440–5447, 2021. Halpern et al. [2020] Daniel Halpern, Ariel D. Procaccia, Alexandros Psomas, and Nisarg Shah. Fair division with binary valuations: One rule to rule them all. In Proceedings of the 16th Conference on Web and Internet Economics (WINE), pages 370–383, 2020. He and Tao [2026] Wentao He and Biaoshuai Tao. EFX for additive chores: Nonexistence, Pareto incompatibility, and bi-valued existence. arXiv preprint arXiv:2606.08872, 2026. Herreiner and Puppe [2009] Dorothea K Herreiner and Clemens D Puppe. Envy freeness in experimental fair division problems. Theory and decision, 67(1):65–100, 2009. Hosseini [2024] Hadi Hosseini. The fairness fair: Bringing human perception into collective decision-making. In Proceedings of the 38th AAAI Conference on Artificial Intelligence, volume 38, pages 22624–22631, 2024. Hosseini et al. [2026] Hadi Hosseini, Vishwa Prakash HV, Aditi Sethia, and Jatin Yadav. The landscape of almost equitable allocations. In Proceedings of the 25th International Conference on Autonomous Agents and Multiagent Systems, AAMAS ’26, page 2032–2040, 2026. Jin and Tao [2025] Jiarong Jin and Biaoshuai Tao. On Pareto-optimal and fair allocations with personalized bi-valued utilities. In Proceedings of the 21st Conference on Web and Internet Economics (WINE), 2025. Kyropoulou et al. [2020] Maria Kyropoulou, Warut Suksompong, and Alexandros A. Voudouris. Almost envy-freeness in group resource allocation. Theoretical Computer Science, 841:110–123, 2020. Lipton et al. [2004] Richard J. Lipton, Evangelos Markakis, Elchanan Mossel, and Amin Saberi. On approximately fair allocations of indivisible goods. In Proceedings of the 5th ACM Conference on Electronic Commerce (EC), pages 125–131, 2004. Mackenzie and Suzuki [2026] Simon Mackenzie and Mashbat Suzuki. Counterexamples to EFX for submodular and subadditive valuations. arXiv preprint arXiv:2605.06451, 2026. Mahara [2026] Ryoga Mahara. Existence of fair and efficient allocation of indivisible chores. In Proceedings of the 37th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 6742–6766, 2026. Plaut and Roughgarden [2020] Benjamin Plaut and Tim Roughgarden. Almost envy-freeness with general valuations. SIAM Journal on Discrete Mathematics, 34(2):1039–1068, 2020. Rawls [1971] John Rawls. A Theory of Justice. Harvard University Press, Cambridge, MA, 1971. Suksompong and Teh [2023] Warut Suksompong and Nicholas Teh. Weighted fair division with matroid-rank valuations: Monotonicity and strategyproofness. Mathematical Social Sciences, 126:48–59, 2023. Sun and Chen [2025] Ankang Sun and Bo Chen. Randomized strategyproof mechanisms with best of both worlds fairness and efficiency. European Journal of Operational Research, 324(3):941–952, 2025. Sun et al. [2023] Ankang Sun, Bo Chen, and Xuan Vinh Doan. Equitability and welfare maximization for allocating indivisible items. Autonomous Agents and Multi-Agent Systems, 37, 2023. Tao et al. [2025] Biaoshuai Tao, Xiaowei Wu, Ziqi Yu, and Shengwei Zhou. On the existence of EFX (and Pareto-optimal) allocations for binary chores. Theoretical Computer Science, 1042:115248, 2025. Viswanathan and Zick [2023] Vignesh Viswanathan and Yair Zick. A general framework for fair allocation under matroid rank valuations. In Proceedings of the 24th ACM Conference on Economics and Computation (EC), 2023. Wang et al. [2026] Ying Wang, Jiaqian Li, Tianze Wei, Hau Chan, and Minming Li. Centralized group equitability and individual envy-freeness in the allocation of indivisible items. In Proceedings of the 40th AAAI Conference on Artificial Intelligence (AAAI), 2026. Wang and Wei [2025] Yuanyuan Wang and Tianze Wei. Achieving equitability with subsidy. arXiv preprint arXiv:2505.23251, 2025. Appendix A Omitted Material from Section 3 A.1 Fundamental Barriers Complete proof of Proposition 1. Consider again the instance depicted in the proof sketch above: there are n≥3n≥ 3 agents and m=2nm=2n goods; for every i∈[n−1]i∈[n-1], vi(g1)=1v_i(g_1)=1 and vi(gj)=εv_i(g_j)= for all j≥2j≥ 2, where ε>0 >0 is sufficiently small so that (2n−1)ε<δ(2n-1) <δ with δ:=1+(m−1)εm=1+(2n−1)ε2n,δ:= 1+(m-1) m= 1+(2n-1) 2n, and agent n values every good at δ. Every agent values the grand bundle at 1+(2n−1)ε1+(2n-1) , so the instance is normalized. Consider any allocation A. Since n≥3n≥ 3, there exists an agent i∈[n−1]i∈[n-1] who does not receive g1g_1; hence vi(Ai)≤(2n−1)ε<δv_i(A_i)≤(2n-1) <δ. We claim that agent n can receive at most one good. Otherwise, after removing any good from AnA_n, agent n’s remaining utility is at least δ, contradicting EQ1 with respect to i. Thus, at least 2n−12n-1 goods are allocated among the first n−1n-1 agents. By the pigeonhole principle, one of these agents, say j, receives at least three goods. Agent n values her own bundle at most δ, whereas, for every g∈Ajg∈ A_j, we have vn(Aj∖g)≥2δ>δ≥vn(An)v_n(A_j \g\)≥ 2δ>δ≥ v_n(A_n). Hence agent n EF1-envies agent j, establishing that no allocation is simultaneously EF1+EQ1. ∎ An analogous construction rules out the chores setting. The following proposition is the chores analogue of Proposition 1. Proposition 4. For n≥3n≥ 3 agents with normalized bivalued valuations, an allocation of chores that is both EF1 and EQ1 may fail to exist. Proof. We first provide an instance for every n≥4n≥ 4 and then a separate one for n=3n=3. For n≥4n≥ 4, let m=2nm=2n. The first n−2n-2 agents (the flat agents) have identical disutilities vi(c)=−δ:=−12nv_i(c)=-δ:=- 12n for every chore c. The last two agents, n−1n-1 and n, assign disutility −(1−(2n−1)ε)-(1-(2n-1) ) to chore c1c_1 (the heavy chore) and disutility −ε- to every other chore (the light chores), where ε>0 >0 is chosen so that (2n−1)ε<δ(2n-1) <δ. Every agent has total disutility −1-1, so the instance is normalized, and every valuation is bivalued. Suppose some flat agent receives at least two chores. After removing any one chore from her bundle, its remaining disutility is at most −δ-δ. Since the heavy chore c1c_1 can be assigned to at most one of agents n−1n-1 and n, the other of these two agents receives only light chores and thus incurs cost at most (2n−1)ε<δ(2n-1) <δ. Therefore EQ1 is violated between the flat agent and this agent. Hence every one of the first n−2n-2 agents receives at most one chore. Consequently, the flat agents together receive at most n−2n-2 chores, leaving at least 2n−(n−2)=n+22n-(n-2)=n+2 chores for agents n−1n-1 and n. By the pigeonhole principle, one of these two agents receives at least ⌈(n+2)/2⌉≥3 (n+2)/2 ≥ 3 chores. Even after removing any single chore, her bundle still contains at least two chores, each costing her at least ε , so its remaining cost is at least 2ε2 . Since at most one flat agent can receive the heavy chore c1c_1 and there are n−2≥2n-2≥ 2 flat agents, some flat agent holds no heavy chore and at most one light chore, so agents n−1n-1 and n value her bundle at cost at most ε (possibly 00 if the bundle is empty). Thus the overloaded agent has cost at least 2ε2 after removing any one chore, while she values this flat agent’s bundle at cost at most ε , contradicting EF1. Hence no allocation simultaneously satisfies EF1 and EQ1. Now consider n=3n=3. Fix 0<ε<1/120< <1/12 and take eight chores with the following disutilities: c1cj(j=2,…,8)Agent 1−12.5−12.5Agent 2−(86−7ε)−(2+ε)Agent 3−93−1 array[]c|c&c_1&c_j\ (j=2,…,8)\\ 1&-12.5&-12.5\\ Agent 2&-(86-7 )&-(2+ )\\ Agent 3&-93&-1 array Every agent’s total disutility is −100-100, so the instance is normalized and bivalued. Agent 1 cannot receive two or more chores: after removing any one of them, her remaining disutility is at most −12.5-12.5, whereas one of agents 2 and 3 does not receive the heavy chore c1c_1; since agent 1 holds at least two of the eight chores, that agent holds at most six light chores and incurs cost at most 6(2+ε)<12.56(2+ )<12.5 (as ε<1/12 <1/12), violating EQ1. Moreover, agent 1 cannot receive zero chores. Otherwise, all eight chores are distributed between agents 2 and 3, so one of them receives at least four chores. After removing her most costly chore, that agent still incurs strictly positive cost from at least three chores, while agent 1’s bundle is empty and has cost 00, an EF1 violation. Therefore agent 1 receives exactly one chore. If agent 1 receives a light chore instead of c1c_1, the remaining seven chores are divided between agents 2 and 3, and one of them receives at least four chores. After removing her most costly chore, the remaining at least three light chores still have strictly greater cost (to her) than agent 1’s single light chore, violating EF1. Hence necessarily A1=c1A_1=\c_1\. The remaining seven light chores must then be split between agents 2 and 3. If some agent receives at least five of them, she EF1-envies the other even after removing one chore, so one agent receives three chores and the other four. In either split, agent 3’s cost is at most 44, whereas agent 2’s cost after removing one chore is at least 2(2+ε)=4+2ε>42(2+ )=4+2 >4, contradicting EQ1. Therefore, no allocation simultaneously satisfies EF1 and EQ1 for n=3n=3. ∎ A.2 Computational Barriers We prove a more general statement, for which we need the “up to k goods” versions of our fairness notions. Definition 1. For an integer k≥1k≥ 1, an allocation A is envy-free up to k goods (EF-k) if, for every pair of agents i,j∈Ni,j∈ N, there exists a subset S⊆AjS A_j with |S|≤k|S|≤ k such that vi(Ai)≥vi(Aj∖S)v_i(A_i)≥ v_i(A_j S). Similarly, A is equitable up to k goods (EQ-k) if, for every pair i,j∈Ni,j∈ N, there exists a subset S⊆AjS A_j with |S|≤k|S|≤ k such that vi(Ai)≥vj(Aj∖S)v_i(A_i)≥ v_j(A_j S). For k=1k=1 these notions coincide with EF1 and EQ1, so the following theorem contains Theorem 1 as the special case k=1k=1. Theorem 10. For two agents with additive (possibly unnormalized) valuations and any fixed integer k≥1k≥ 1, deciding whether an allocation that is both EF-k and EQ-k exists is NP-hard. Proof. We reduce from the classical Partition problem: given positive integers x1,…,xnx_1,…,x_n, decide whether they can be partitioned into two subsets with equal sum. Let T=∑i=1nxiT= _i=1^nx_i; we may assume T is even, as otherwise the instance is trivially a NO-instance. Construction. Create a fair-division instance with two agents A and B and the following goods: • n ordinary goods o1,…,ono_1,…,o_n; • 3k3k dummy goods d1,…,d3kd_1,…,d_3k. The additive valuations are ordinary oidummy dtAxiDBxi0 array[]c|c&ordinary o_i&dummy d_t\\ A&x_i&D\\ B&x_i&0 array where D is any integer with D>TD>T (e.g., D=T+1D=T+1, which has polynomial size). We claim that the instance admits a complete EF-k+EQ-k allocation if and only if the Partition instance is solvable. (⇒ ) From a fair allocation to a partition. Let tAt_A and tBt_B denote the numbers of dummies allocated to A and B, so tA+tB=3kt_A+t_B=3k. Claim 1: tA≤kt_A≤ k. Suppose tA>kt_A>k and consider EQ-k for the ordered pair (B,A)(B,A). After removing any at most k goods from A’s bundle, at least one dummy remains, so the remaining value (to A) is at least D>TD>T. But B’s realized utility is at most T. Hence vB(B)≥vA(A∖S)v_B(B)≥ v_A(A S) fails for every admissible S, contradicting EQ-k. Claim 2: tB≤tA+kt_B≤ t_A+k. Suppose tB>tA+kt_B>t_A+k and consider EF-k for the ordered pair (A,B)(A,B). After removing any at most k goods from B’s bundle, B still retains at least tB−k>tAt_B-k>t_A dummies, so A values the remaining bundle at least (tB−k)D≥(tA+1)D=tAD+D>tAD+T(t_B-k)D≥(t_A+1)D=t_AD+D>t_AD+T. On the other hand, A’s own total value is at most tAD+Tt_AD+T. Hence A still envies B after every admissible removal, contradicting EF-k. Combining Claims 1 and 2 with tA+tB=3kt_A+t_B=3k yields tA=kt_A=k and tB=2kt_B=2k. Now let SAS_A and SBS_B be the sets of ordinary goods assigned to A and B, and write sA=vA(SA)s_A=v_A(S_A) and sB=vB(SB)s_B=v_B(S_B), so sA+sB=Ts_A+s_B=T. Claim 3: sA≤sBs_A≤ s_B. Suppose sA>sBs_A>s_B and consider EQ-k for the pair (B,A)(B,A). The most value-reducing removal of at most k goods from A’s bundle removes her k dummies, leaving value sA>sB=vB(B)s_A>s_B=v_B(B); any other removal leaves at least one dummy and value at least D>T≥sBD>T≥ s_B. Either way EQ-k fails. Claim 4: sA≥sBs_A≥ s_B. Suppose sA<sBs_A<s_B and consider EF-k for the pair (A,B)(A,B). The most value-reducing removal (from A’s perspective) of at most k goods from B’s bundle removes k dummies, leaving value kD+sB>kD+sA=vA(A)kD+s_B>kD+s_A=v_A(A); any other removal leaves at least k+1k+1 dummies and value at least (k+1)D>kD+T≥kD+sA(k+1)D>kD+T≥ kD+s_A. Either way A still envies B, contradicting EF-k. Claims 3 and 4 yield sA=sB=T/2s_A=s_B=T/2, so the ordinary goods split into two sets of equal sum, i.e., the Partition instance is a YES-instance. (⇐ ) From a partition to a fair allocation. Suppose SA,SBS_A,S_B partition the ordinary goods with equal sums T/2T/2. Allocate to A the goods SAS_A plus any k dummies, and to B the goods SBS_B plus the remaining 2k2k dummies. Then vA(A)=T/2+kDv_A(A)=T/2+kD and vB(B)=T/2v_B(B)=T/2. For EF-k: agent B does not envy A (she values A’s bundle at T/2=vB(B)T/2=v_B(B)), and removing k dummies from B’s bundle leaves value T/2+kDT/2+kD to agent A, eliminating her envy. For EQ-k: removing the k dummies from A’s bundle leaves both realized utilities equal to T/2T/2; all other ordered comparisons are immediate. Thus the allocation is EF-k+EQ-k. The construction is computable in polynomial time, which completes the reduction. ∎ A.3 Limits of Strengthening EF1+EQ1 The main text notes that, even under normalization and binary valuations, neither of the two guarantees in EF1+EQ1 can generally be strengthened. The following construction makes this precise. Proposition 5. For six agents with normalized binary valuations, an allocation of goods that is EF1+EQX, and likewise one that is EFX+EQ1, may fail to exist. Both parts use the same instance; the two claims are established as Propositions 6 and 7 below. Let n=6n=6 and m=18m=18, and let L and R be disjoint sets of nine goods. Agent 1 approves exactly the goods in L: v1=(1,…,1⏟L,0,…,0⏟R),v_1=( 1,…,1_L, 0,…,0_R), while every agent p∈2,…,6p∈\2,…,6\ approves exactly the goods in R: vp=(0,…,0⏟L,1,…,1⏟R).v_p=( 0,…,0_L, 1,…,1_R). All valuations are binary and normalized. For an allocation A, write x x =|A1∩L|, =|A_1∩ L|, y y =|A1∩R|, =|A_1∩ R|, ap a_p =|Ap∩L|, =|A_p∩ L|, bp b_p =|Ap∩R| =|A_p∩ R| for p∈2,…,6p∈\2,…,6\. The realized utilities are u1=xu_1=x and up=bpu_p=b_p, and x+∑p=26ap=9,y+∑p=26bp=9.x+ _p=2^6a_p=9, y+ _p=2^6b_p=9. (8) Proposition 6. The above instance admits no EF1+EQX allocation. Proof. Suppose, for contradiction, that an allocation A satisfies both EF1 and EQX. Let μ=minx,b2,…,b6μ= \x,b_2,…,b_6\ denote the minimum realized utility. Since utilities are integral, EQX implies that every agent has utility either μ or μ+1μ+1. Moreover, if an agent holds a good that she values at 00, removing that good does not change the value of her bundle; hence such an agent must have utility exactly μ. Consequently, for every p∈2,…,6p∈\2,…,6\, y>0⟹x=μ,ap>0⟹bp=μ.y>0 x=μ, a_p>0 b_p=μ. (9) The EF1 comparisons of agent 1 against agent p, and of agent p against agent 1, give ap≤x+1,y≤bp+1(p∈2,…,6).a_p≤ x+1, y≤ b_p+1 (p∈\2,…,6\). (10) Case 1: y=0y=0. Then ∑p=26bp=9 _p=2^6b_p=9 by (8). If μ=0μ=0, then every utility is at most 11, so ∑pbp≤5<9 _pb_p≤ 5<9, which is impossible; hence μ≥1μ≥ 1. Since every bp∈μ,μ+1b_p∈\μ,μ+1\ and ∑pbp=9 _pb_p=9, we get μ=1μ=1 and (b2,…,b6)(b_2,…,b_6) consists of four 22’s and one 11, and x∈1,2x∈\1,2\. By (9), the four agents with utility 22 cannot hold any goods from L. Therefore all 9−x≥79-x≥ 7 goods from L not assigned to agent 1 belong to the unique agent with utility 11, i.e., ap≥7>x+1a_p≥ 7>x+1 for that agent, contradicting (10). Case 2: y>0y>0. Then x=μx=μ by (9). If x=0x=0, then every bp∈0,1b_p∈\0,1\, so 9−y=∑pbp≤59-y= _pb_p≤ 5 and hence y≥4y≥ 4, contradicting y≤bp+1≤2y≤ b_p+1≤ 2 from (10). Moreover, 5μ≤∑pbp=9−y≤85μ≤ _pb_p=9-y≤ 8 gives μ≤1μ≤ 1; therefore x=μ=1x=μ=1, and every bp∈1,2b_p∈\1,2\. Let h be the number of agents with bp=2b_p=2. Then 5+h=∑pbp=9−y5+h= _pb_p=9-y, so h=4−yh=4-y, and 5−h=1+y5-h=1+y agents have utility 11. By (9), only these 1+y1+y agents may receive goods from L, and by (10) each receives at most x+1=2x+1=2 of them. Since they must receive all 9−x=89-x=8 goods of L not held by agent 1, we get 2(1+y)≥82(1+y)≥ 8, i.e., y≥3y≥ 3. But a utility-11 agent exists, and (10) requires y≤bp+1=2y≤ b_p+1=2 for her, a contradiction. ∎ Proposition 7. The same instance admits no EFX+EQ1 allocation. Proof. Suppose an allocation A satisfies both EFX and EQ1, and let μ be the minimum realized utility. Under EQ1, all utilities lie in μ,μ+1\μ,μ+1\. Since ∑pbp≤9 _pb_p≤ 9 over five agents, μ≤1μ≤ 1. Suppose μ=0μ=0. Then x,bp≤1x,b_p≤ 1 for all p, so 9−y=∑pbp≤59-y= _pb_p≤ 5 and y≥4y≥ 4. If x>0x>0, then A1A_1 contains an L-good, which every agent p values at zero; EFX from a utility-00 agent p toward agent 1 would require bp≥vp(A1∖L-good)=y≥4b_p≥ v_p(A_1 \$L$-good\)=y≥ 4, which is impossible. Thus x=0x=0, and removing any R-good from A1A_1 leaves value y−1≥3y-1≥ 3 to agent p, still above bp≤1b_p≤ 1, again contradicting EFX. Hence μ=1μ=1, so x,bp∈1,2x,b_p∈\1,2\. Every bundle ApA_p contains an R-good, which agent 1 values at zero. Consequently, EFX from agent 1 toward p requires ap=v1(Ap∖R-good)≤xa_p=v_1(A_p \$R$-good\)≤ x for every p. Since ∑pap=9−x _pa_p=9-x, the case x=1x=1 would give 9−x=8>5≥∑pap9-x=8>5≥ _pa_p, a contradiction; therefore x=2x=2. Since x=2x=2, the bundle A1A_1 contains an L-good, which every agent p values at zero, so EFX from p toward agent 1 requires bp≥yb_p≥ y for every p. Summing gives 9−y≥5y9-y≥ 5y, hence y≤1y≤ 1. If y=0y=0, the values (b2,…,b6)(b_2,…,b_6) are four 22’s and one 11; if y=1y=1, they are three 22’s and two 11’s. A utility-22 agent cannot receive any L-good: otherwise a utility-11 agent q would still see both of that agent’s R-goods after removing the zero-valued L-good, i.e., vq(Ap∖L-good)≥2>1=bqv_q(A_p \$L$-good\)≥ 2>1=b_q, violating EFX. Thus all 9−x=79-x=7 goods of L not held by agent 1 must go to the one or two utility-11 agents, whose combined capacity is at most 2x=4<72x=4<7 by the bound ap≤xa_p≤ x. This final contradiction completes the proof. ∎ A.4 Two-Agent Instances Existence for goods. Assume without loss of generality that the common grand-bundle value is positive and scale it to one; if v1(M)=v2(M)=0v_1(M)=v_2(M)=0, then all goods are zero-valued for both agents (values are nonnegative) and any allocation is trivially EFX+EQX. Following Plaut and Roughgarden [2020], a leximin++ allocation is one that (i) maximizes the minimum realized utility, (i) subject to that, maximizes the number of items held by an agent with the minimum utility, and (i) subject to that, maximizes the larger utility. Proposition 8. For two agents with normalized valuations, every leximin++ allocation of goods is both EFX and EQX. Proof. Let A=(A1,A2)A=(A_1,A_2) be a leximin++ allocation and relabel the agents so that v1(A1)≤v2(A2)v_1(A_1)≤ v_2(A_2). EQX. Suppose EQX fails. Then there exists g∈A2g∈ A_2 with v1(A1)<v2(A2∖g)v_1(A_1)<v_2(A_2 \g\). Transfer g to agent 1, i.e., consider A′=(A1∪g,A2∖g)A =(A_1∪\g\,A_2 \g\). Agent 2’s new utility remains strictly above the old minimum v1(A1)v_1(A_1). If v1(g)>0v_1(g)>0, agent 1’s utility strictly increases, so the minimum utility strictly increases. If v1(g)=0v_1(g)=0, the minimum utility is unchanged while the minimum-utility agent holds strictly more items. Both cases contradict leximin++ optimality, so A is EQX. EFX. First, the two agents cannot envy each other simultaneously: swapping their bundles would strictly increase both realized utilities, contradicting leximin++ optimality. If agent 2 envied agent 1 while agent 1 did not envy agent 2, normalization would give v2(A2)<1/2v_2(A_2)<1/2 and v1(A1)≥1/2v_1(A_1)≥ 1/2, contradicting v1(A1)≤v2(A2)v_1(A_1)≤ v_2(A_2). Hence any envy is from agent 1 toward agent 2, in which case v1(A1)<1/2v_1(A_1)<1/2. Suppose EFX fails, i.e., there is g∈A2g∈ A_2 with v1(A1)<v1(A2∖g)v_1(A_1)<v_1(A_2 \g\). Consider the two parts X=A1∪gX=A_1∪\g\ and Y=A2∖gY=A_2 \g\, and let agent 2 choose her preferred part, with agent 1 receiving the other. Agent 2’s new utility is at least maxv2(X),v2(Y)≥v2(M)/2=1/2 \v_2(X),v_2(Y)\≥ v_2(M)/2=1/2. Agent 1 receives either Y, which she values strictly above A1A_1, or X, which weakly improves her utility and, in case of a tie (v1(g)=0v_1(g)=0), strictly increases her number of items. In every case the leximin++ objective strictly improves, a contradiction. Hence A is EFX. ∎ Remark 2. Although computing a leximin++ allocation is computationally hard in general, it can be computed in polynomial time for binary valuations. Non-existence for chores. We now show that the guarantee of Proposition 8 does not carry over to chores: under the all-item convention for EFX/EQX, even two agents with normalized valuations may admit no EFX+EQX allocation. Proposition 9. For two agents with normalized valuations, an allocation of chores that is both EFX and EQX may fail to exist, already with three chores. Proof. Consider three chores c1,c2,c3c_1,c_2,c_3 and the valuations c1c_1 c2c_2 c3c_3 Agent 11 00 −1-1 −2-2 Agent 22 −2-2 −1-1 00 Both agents value the grand bundle at −3-3, so the instance is normalized. The instance is symmetric under simultaneously exchanging the two agents and the chores c1↔c3c_1 c_3 (keeping c2c_2 fixed): this relabeling maps each valuation function onto the other, and it maps an allocation (A1,A2)(A_1,A_2) to an allocation whose bundles have the same values to their owners and to the other agent. Hence an allocation is EFX (resp. EQX) if and only if its image is, and it suffices to rule out the allocations with |A1|≤1|A_1|≤ 1; the cases |A1|≥2|A_1|≥ 2 are their images under the symmetry. Case A1=∅A_1= . Then A2=c1,c2,c3A_2=\c_1,c_2,c_3\ with v2(A2)=−3v_2(A_2)=-3, while v1(A1)=0v_1(A_1)=0. Removing the zero-valued chore c3c_3 from A2A_2 leaves v2(A2∖c3)=−3<0=v1(A1)v_2(A_2 \c_3\)=-3<0=v_1(A_1), so EQX fails. Case A1=c1A_1=\c_1\. Then v1(A1)=0v_1(A_1)=0 and A2=c2,c3A_2=\c_2,c_3\ with v2(A2)=−1v_2(A_2)=-1. Removing the zero-valued chore c3c_3 from A2A_2 leaves v2(A2∖c3)=−1<0=v1(A1)v_2(A_2 \c_3\)=-1<0=v_1(A_1), so EQX fails. Case A1=c2A_1=\c_2\. Then v1(A1)=−1v_1(A_1)=-1 and A2=c1,c3A_2=\c_1,c_3\ with v2(A2)=−2v_2(A_2)=-2. Removing c3c_3 from A2A_2 leaves v2(A2∖c3)=−2<−1=v1(A1)v_2(A_2 \c_3\)=-2<-1=v_1(A_1), so EQX fails. Case A1=c3A_1=\c_3\. Then A2=c1,c2A_2=\c_1,c_2\, and agent 2 values agent 1’s bundle at v2(A1)=v2(c3)=0v_2(A_1)=v_2(\c_3\)=0, while v2(A2)=−3v_2(A_2)=-3, so agent 2 envies agent 1. Removing c2c_2 (agent 2’s least costly chore in her bundle) leaves v2(A2∖c2)=−2<0=v2(A1)v_2(A_2 \c_2\)=-2<0=v_2(A_1), so the envy persists after the removal of some chore, and EFX fails. In every case, EFX or EQX is violated; by the symmetry noted above, the same holds for all remaining allocations. Hence no allocation of this instance is simultaneously EFX and EQX. ∎ Remark 3. The violations above hinge on zero-valued chores and the all-item convention adopted in this paper. Under the weaker convention in which only negatively valued chores may be removed, the instance of Proposition 9 does admit an EFX+EQX allocation, e.g., A1=c1A_1=\c_1\ and A2=c2,c3A_2=\c_2,c_3\. The algorithm for chores mirrors Greedy-Balance for goods (Algorithm 1), with the roles of the two agents adjusted for disutilities: the next chore is assigned to the agent with the currently higher utility (i.e., smaller burden), and each agent takes a remaining chore with the largest value difference in her favor. Algorithm 5 Greedy-Balance for two-agent chores Input: A normalized two-agent chores instance Output: An allocation (A1,A2)(A_1,A_2) 1: Initialize A1,A2←∅A_1,A_2← , U1,U2←0U_1,U_2← 0, and R←MR← M. 2: while R≠∅R≠ do 3: if U1≥U2U_1≥ U_2 then 4: Choose c⋆∈argmaxc∈Rv1(c)−v2(c)c ∈ _c∈ R\v_1(c)-v_2(c)\. 5: A1←A1∪c⋆A_1← A_1∪\c \ and U1←U1+v1(c⋆)U_1← U_1+v_1(c ). 6: else 7: Choose c⋆∈argmaxc∈Rv2(c)−v1(c)c ∈ _c∈ R\v_2(c)-v_1(c)\. 8: A2←A2∪c⋆A_2← A_2∪\c \ and U2←U2+v2(c⋆)U_2← U_2+v_2(c ). 9: end if 10: R←R∖c⋆R← R \c \. 11: end while 12: return (A1,A2)(A_1,A_2). The cross-bundle dominance invariant of Lemma 1 holds verbatim; its proof is independent of the signs of the values. Lemma 9. At every stage of Algorithm 5, v1(A1)≥v2(A1)andv2(A2)≥v1(A2).v_1(A_1)≥ v_2(A_1) v_2(A_2)≥ v_1(A_2). Proof. We prove the first inequality; the second is symmetric. Define Δ(c)=v1(c)−v2(c) (c)=v_1(c)-v_2(c); normalization gives Δ(M)=0 (M)=0. Suppose that at some stage Δ(A1)=v1(A1)−v2(A1)<0 (A_1)=v_1(A_1)-v_2(A_1)<0. Since Δ(M)=0 (M)=0, there exist c∈A1c∈ A_1 with Δ(c)<0 (c)<0 and d∉A1d∉ A_1 with Δ(d)>0 (d)>0. Consider the iteration in which c was assigned to agent 1. At that moment d must already have been allocated: otherwise the algorithm, which assigns to agent 1 a remaining chore maximizing Δ(⋅) (·), would have chosen d instead of c. Thus d was assigned earlier to agent 2. At that earlier iteration c was still available with Δ(c)<0<Δ(d) (c)<0< (d); since agent 2 receives a remaining chore minimizing Δ(⋅) (·), the algorithm would have chosen c rather than d, a contradiction. ∎ Proof of Corollary 1. Let A=(A1,A2)A=(A_1,A_2) be the returned allocation. EQ1. Without loss of generality, assume v1(A1)≤v2(A2)v_1(A_1)≤ v_2(A_2). The ordered comparison from agent 2 is immediate: since values are nonpositive, removing any chore from A2A_2 only increases its value, so v2(A2∖c)≥v2(A2)≥v1(A1)v_2(A_2 \c\)≥ v_2(A_2)≥ v_1(A_1) for every c∈A2c∈ A_2 (and the condition is vacuous if A2=∅A_2= ). For the comparison from agent 1, if A1=∅A_1= then 0=v1(A1)≤v2(A2)≤00=v_1(A_1)≤ v_2(A_2)≤ 0 forces v2(A2)=0v_2(A_2)=0 and the condition holds trivially. Otherwise, let cℓc_ be the last chore assigned to agent 1, at some iteration tℓt_ , and let A1(tℓ),A2(tℓ)A_1(t_ ),A_2(t_ ) denote the bundles held immediately before that assignment. Since the algorithm assigned cℓc_ to agent 1, we have v1(A1(tℓ))=U1≥U2=v2(A2(tℓ))v_1(A_1(t_ ))=U_1≥ U_2=v_2(A_2(t_ )) at that moment. Moreover A1∖cℓ=A1(tℓ)A_1 \c_ \=A_1(t_ ), and every chore allocated after iteration tℓt_ went to agent 2, which can only decrease her utility, so v2(A2)≤v2(A2(tℓ))v_2(A_2)≤ v_2(A_2(t_ )). Combining, v1(A1∖cℓ)=v1(A1(tℓ))≥v2(A2(tℓ))≥v2(A2),v_1(A_1 \c_ \)=v_1(A_1(t_ ))≥ v_2(A_2(t_ ))≥ v_2(A_2), which is the EQ1 condition for agent 1. EF1. Suppose agent 1 envies agent 2, i.e., v1(A1)<v1(A2)v_1(A_1)<v_1(A_2). By Lemma 9, v2(A2)≥v1(A2)v_2(A_2)≥ v_1(A_2), hence v1(A1)<v2(A2)v_1(A_1)<v_2(A_2), and in particular A1≠∅A_1≠ . The EQ1 argument above then yields a chore cℓ∈A1c_ ∈ A_1 with v1(A1∖cℓ)≥v2(A2)≥v1(A2)v_1(A_1 \c_ \)≥ v_2(A_2)≥ v_1(A_2), which is exactly the EF1 condition. The case in which agent 2 envies agent 1 is symmetric. The algorithm performs one greedy step per chore and thus runs in polynomial time. ∎ A.5 Why the Barrier at Seven Agents? Remark 4. The analysis of Algorithm 2 is local: when a residual good with valuer set T (|T|=q|T|=q) cannot be scattered, every candidate bundle already holds t+1t+1 goods valued by some member of T, so by pigeonhole one valuer sees at least (t+1)⌈(n−q)/q⌉(t+1) (n-q)/q goods in other bundles—contradicting the mass bound k≤r(t+1)−1k≤ r(t+1)-1 precisely when ⌈(n−q)/q⌉≥r−1 (n-q)/q ≥ r-1 (Lemma 6). The number of blocking configurations available to an adversary grows with s⋅r≤⌊n2/4⌋s· r≤ n^2/4 , while the saturation mass that the normalized budgets can afford grows only linearly, as 2n−22n-2; since ⌊n2/4⌋≤2n−2 n^2/4 ≤ 2n-2 holds exactly for n≤7n≤ 7—with equality at n=7n=7—the counting argument closes at seven with zero slack and first fails at n=8n=8 (already for q=2q=2). PuP_u PvP_v Pj1P_j_1 Pj2P_j_2 Pj3P_j_3 Pj4P_j_4 Pj5P_j_5 Pj†P_j R z1uz^u_1 z2uz^u_2 z1vz^v_1 z2vz^v_2 o1o_1 o2o_2 o3o_3 o4o_4 o5o_5 o6o_6 o7o_7 o8o_8 o9o_9 o10o_10 o11o_11 g1g_1 g2g_2 u 1 1 0 0 1 1 1 1 1 1 0 0 0 0 1 1 1 v 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 j1j_1 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 0 0 j2j_2 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 0 0 j3j_3 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 0 0 j4j_4 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 0 0 j5j_5 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 0 0 j†j 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 0 0 cu,⋅c_u,· 22 00 2=t+1\;2=t+1\; 2=t+1\;2=t+1\; 2=t+1\;2=t+1\; 00 00 11 cv,⋅c_v,· 00 22 2=t+1\;2=t+1\; 00 00 2=t+1\;2=t+1\; 2=t+1\;2=t+1\; 11 Figure 1: An eight-agent instance (m=17m=17, k=11k=11) on which the scattering phase stalls from the displayed maximum partial allocation. Columns are grouped by bundle; bold entries mark each good’s owner. The six outside agents j1,…,j5,j†j_1,…,j_5,j collectively value only o1,…,o11o_1,…,o_11, so the egalitarian level is t=1t=1, every bundle holds t+1=2t+1=2 goods except Pj†P_j , and the goods g1,g2g_1,g_2 (type u,v\u,v\) are residual. The two bottom rows give the counts cu,Pj:=vu(Pj)c_u,P_j:=v_u(P_j) and cv,Pj:=v(Pj)c_v,P_j:=v_v(P_j): every bundle is saturated for u (red) or for v (blue), in an anti-correlated pattern—u’s slack sits at Pj4,Pj5P_j_4,P_j_5, v’s at Pj2,Pj3P_j_2,P_j_3—while a u,v\u,v\-good needs room in both rows at the same bundle. Only Pj†P_j (yellow) offers such a slot, and only once: after g1g_1 enters it, g2g_2 cannot be scattered, although every per-agent count is far below its budget. An EF1+EQ1 allocation exists nonetheless (assign g1,g2g_1,g_2 to u, releasing the freely scatterable singletons z1u,z2uz^u_1,z^u_2). Notice that the barrier is stemming from the choice of partial allocation, not the instance. Importantly, beyond seven agents, scattering no longer succeeds from every maximum partial allocation. Consider n=8n=8 (Figure 1): agents u,vu,v and j1,…,j5,j†j_1,…,j_5,j , and m=17m=17 goods with k=11k=11: goods z1u,z2uz^u_1,z^u_2 valued by u\u\; z1v,z2vz^v_1,z^v_2 by v\v\; g1,g2g_1,g_2 by u,v\u,v\; and o1,…,o11o_1,…,o_11, each valued by all six outside agents, where o1,o2,o11o_1,o_2,o_11 are additionally valued by both u and v, o3,…,o6o_3,…,o_6 by u, and o7,…,o10o_7,…,o_10 by v. The outside agents collectively value only eleven goods, so t=1t=1. In the maximum partial allocation that gives the z-goods to their valuers, o1,2o_1,2 to j1j_1, o3,4o_3,4 to j2j_2, o5,6o_5,6 to j3j_3, o7,8o_7,8 to j4j_4, o9,10o_9,10 to j5j_5, and o11o_11 to j†j , the residual goods are g1,g2g_1,g_2, and every bundle is saturated for u or for v in an anti-correlated pattern: u’s slack sits at j4,j5j_4,j_5, v’s at j2,j3j_2,j_3, yet a u,v\u,v\-good needs room in both rows at the same bundle, which only j†j offers—once. After g1g_1 enters j†j , the good g2g_2 cannot be placed and the scattering phase stalls, even though every per-agent count is good; here the swap phase rescues the run (the residual type equals S=u,vS=\u,v\, so g1,g2g_1,g_2 can be swapped into u’s bundle, releasing freely scatterable singletons). The example shows that beyond seven agents, the scattering phase need not succeed from every maximum partial allocation, even when an EF1+EQ1 allocation exists. Thus, extending the approach appears to require either stronger structural transformations before scattering or a more careful choice of the initial maximum partial allocation. Identifying such a rule with a provable guarantee is an interesting direction for future work. Appendix B A Simpler Algorithm for Five Agents For five agents, the swap phase and the use of non-valuers inside S are not needed: the following simpler version of Level-and-Scatter assigns every residual good to an agent outside S. We include it because both the algorithm and its case analysis are simpler than those required for Theorem 3. Algorithm 6 Simple-Level-and-Scatter for five agents 0: A normalized binary goods instance with five agents 0: An allocation (A1,…,A5)(A_1,…,A_5) 1: Remove all junk goods from M and store them in J. 2: Compute the maximum feasible egalitarian level t. 3: Compute a maximum partial allocation P=(P1,…,P5)P=(P_1,…,P_5) such that every good in PiP_i is valued by i and t≤|Pi|≤t+1t≤|P_i|≤ t+1 for every i. 4: Let R←M∖⋃i∈NPiR← M _i∈ NP_i. 5: Construct the residual alternating graph and let S be the set of agents reachable from R. 6: Initialize Ai←PiA_i← P_i for every i∈Ni∈ N. 7: for each g∈Rg∈ R do 8: Choose j∈N∖Sj∈ N S such that vi(Aj∪g)≤t+1v_i(A_j∪\g\)≤ t+1 for every i∈Si∈ S. 9: Aj←Aj∪gA_j← A_j∪\g\. 10: end for 11: Distribute the goods in J arbitrarily. 12: return (A1,…,A5)(A_1,…,A_5). Theorem 11. For five agents with normalized binary valuations, Algorithm 6 computes, in polynomial time, an allocation of goods satisfying both EF1 and EQ1. Proof. Let k be the common number of goods valued by each agent. If R is empty, every utility is t or t+1t+1, and each partial bundle PjP_j has cardinality at most t+1t+1. Adding junk goods does not affect any value. The allocation is therefore EQ1, and vi(Aj)≤t+1≤vi(Ai)+1v_i(A_j)≤ t+1≤ v_i(A_i)+1 for every i,ji,j, which implies EF1 under binary valuations. Suppose that R≠∅R≠ . Lemma 3 gives |N∖S|≥2|N S|≥ 2, so |S|∈1,2,3|S|∈\1,2,3\. We show that the scattering step is feasible in all three cases. Case 1: |S|=3|S|=3. Let N∖S=p,qN S=\p,q\. Lemma 2(3), together with the fact that at least one outside agent receives only t goods, gives k≤|Pp|+|Pq|≤2t+1.k≤|P_p|+|P_q|≤ 2t+1. Each i∈Si∈ S therefore values at most k−(t+1)≤tk-(t+1)≤ t goods outside PiP_i, including all residual goods. Assigning any residual good to either p or q consequently keeps both outside bundles worth at most t+1t+1 to every agent in S. Case 2: |S|=1|S|=1. Write S=iS=\i\. Every residual good is valued only by i, and Lemma 2(3) gives k≤∑j∉S|Pj|≤4t+3.k≤ _j∉ S|P_j|≤ 4t+3. Thus, outside PiP_i, there are at most k−(t+1)≤3t+2k-(t+1)≤ 3t+2 goods valued by i. The four outside bundles have combined capacity 4(t+1)4(t+1) under the cap t+1t+1. If no outside bundle could receive the next i-valued residual good, all four bundles would already have value t+1t+1 for i, requiring 4(t+1)>3t+24(t+1)>3t+2 such goods outside PiP_i, a contradiction. Case 3: |S|=2|S|=2. Write S=1,2S=\1,2\. The three outside bundles contain at most 3t+23t+2 goods in total, so for each i∈Si∈ S, k−(t+1)≤2t+1.k-(t+1)≤ 2t+1. If a residual good is valued by only one agent i∈Si∈ S, failure would mean that all three outside bundles already have value t+1t+1 for i, requiring 3(t+1)>2t+13(t+1)>2t+1 goods valued by i outside PiP_i, a contradiction. If the good is valued by both agents and no outside bundle can receive it, each of the three outside bundles is saturated for agent 1 or agent 2. By the pigeonhole principle, one of these agents saturates at least two bundles and therefore values at least 2(t+1)=2t+22(t+1)=2t+2 goods outside her own bundle, contradicting the bound 2t+12t+1. Thus every residual good can be assigned. By Lemma 2(2), agents outside S value every residual good at zero, so no realized utility changes and all utilities remain in t,t+1\t,t+1\; hence EQ1 holds. The construction also keeps every bundle worth at most t+1t+1 to every agent, so vi(Aj)≤vi(Ai)+1v_i(A_j)≤ v_i(A_i)+1 for all i,ji,j. As in the proof of Theorem 3, binary valuations make this inequality equivalent to EF1. The flow computation, graph search, and scattering steps are all polynomial-time operations. ∎ Appendix C An Alternative Argument for Three Agents For three agents, we record a self-contained argument based on Hall’s theorem; it is subsumed by Theorem 3 but uses considerably lighter machinery. Theorem 12. For three agents with normalized binary valuations, an allocation of goods satisfying both EF1 and EQ1 always exists. Proof. Let N=1,2,3N=\1,2,3\ be the agents and M the goods. Since the valuations are binary and normalized, there exists an integer t such that every agent values exactly t goods at 11. We may assume that every good is valued by at least one agent: goods valued at 00 by all agents can be set aside and distributed arbitrarily at the end, since they affect neither utilities nor EF1/EQ1. We first construct a maximal balanced partial allocation. Let u be the largest integer such that there exists a partial allocation in which every agent receives exactly u goods that she values at 11; equivalently, a maximum balanced b-matching in the bipartite graph between agents and goods. We claim u≥⌊t/3⌋u≥ t/3 . Suppose no balanced partial allocation of size k exists. By Hall’s condition for b-matchings, there exists a nonempty subset of agents X such that |N(X)|<k|X||N(X)|<k|X|, where N(X)N(X) is the set of goods valued by agents in X. Since every agent values exactly t goods, |N(X)|≥t|N(X)|≥ t, and since |X|≤3|X|≤ 3, it follows that t≤|N(X)|<3kt≤|N(X)|<3k, i.e., k>t/3k>t/3. Hence a balanced partial allocation of size ⌊t/3⌋ t/3 always exists. Let (A1,A2,A3)(A_1,A_2,A_3) be a maximal balanced partial allocation; each bundle contains exactly u goods valued by its owner, so vi(Aj)≤|Aj|=uv_i(A_j)≤|A_j|=u for all i,j∈Ni,j∈ N, and the partial allocation is both EF and EQ. Let S be the set of unallocated goods, and for each agent i let di=|g∈S:vi(g)=1|d_i=|\g∈ S:v_i(g)=1\|. Without loss of generality assume d1≤d2≤d3d_1≤ d_2≤ d_3. We complete the allocation by case analysis; throughout, “capacity” arguments refer to keeping vi(Aj)≤u+1v_i(A_j)≤ u+1 for all i,ji,j, which, together with all realized utilities lying in u,u+1\u,u+1\, implies EQ1 and (under binary valuations) EF1 exactly as in the proof of Theorem 3. Case 1: d1≥3d_1≥ 3. Every agent has at least three valued goods in S, so by Hall’s theorem there is a system of distinct representatives assigning one additional valued good to each agent. This yields a balanced partial allocation of size u+1u+1, contradicting the maximality of u. Case 2: d1=2d_1=2. If d3≥3d_3≥ 3, Hall’s theorem again yields a balanced partial allocation of size u+1u+1, a contradiction; hence d1=d2=d3=2d_1=d_2=d_3=2. The unique barrier to a system of distinct representatives occurs when |S|=2|S|=2 and all three agents value both remaining goods. In this case, allocate one remaining good to agent 1 and the other to agent 2. The realized utilities become (u+1,u+1,u)(u+1,u+1,u), so EQ1 holds; moreover every agent values every bundle at most u+1u+1 while realizing at least u, so EF1 holds as well. Case 3: d1=1d_1=1. If d2≥3d_2≥ 3, or d2=2d_2=2 and d3≥3d_3≥ 3, Hall’s theorem yields a contradiction with maximality. Two subcases remain. Subcase 3.1: d2=d3=2d_2=d_3=2. The only obstruction occurs when |S|=2|S|=2, agent 1 values exactly one remaining good, and agents 2 and 3 value both. Allocate the good valued by agent 1 to agent 1 and the other good to agent 2. The utilities are (u+1,u+1,u)(u+1,u+1,u) and the same reasoning as in Case 2 applies. Subcase 3.2: d2=1d_2=1. First allocate one valued good from S to agent 1; if agent 2 still has a valued unallocated good, allocate one such good to agent 2. All remaining goods are valued only by agent 3. We distribute them between A1A_1 and A2A_2 so that v3(A1)≤u+1v_3(A_1)≤ u+1 and v3(A2)≤u+1v_3(A_2)≤ u+1. Such a distribution exists: agent 3 values exactly t goods, of which u lie in A3A_3, so at most t−ut-u remaining goods are valued by agent 3, while the bundles A1,A2A_1,A_2 currently satisfy v3(A1),v3(A2)≤uv_3(A_1),v_3(A_2)≤ u and thus have combined capacity 2(u+1)2(u+1); from u≥⌊t/3⌋u≥ t/3 we get 3u+2≥t3u+2≥ t, i.e., t−u≤2u+2t-u≤ 2u+2, so a greedy distribution respects both caps. Every agent’s realized utility lies in u,u+1\u,u+1\, which gives EQ1, and every bundle is worth at most u+1u+1 to every agent, which gives EF1. Case 4: d1=0d_1=0. Subcase 4.1: d2≥2d_2≥ 2 and d3≥3d_3≥ 3. We derive a contradiction with the maximality of u. If agent 2’s bundle contains a good valued by agent 1, reassign that good to agent 1, then assign two valued goods from S to agent 2 and one valued good from S to agent 3. Otherwise agent 3’s bundle must contain a good valued by agent 1 (agent 1 values t≥u+1t≥ u+1 goods, hence some valued good lies outside A1A_1; since d1=0d_1=0, it lies in A2∪A3A_2∪ A_3): reassign it to agent 1, then assign one valued good from S to agent 2 and two valued goods from S to agent 3. In either case every agent’s utility increases to u+1u+1, and by Hall’s theorem the required distinct goods in S exist because d2≥2d_2≥ 2 and d3≥3d_3≥ 3. This contradicts maximality. Subcase 4.2: d2=d3=2d_2=d_3=2. If |S|=2|S|=2, allocate one remaining good to agent 2 and the other to agent 3; the utilities become (u,u+1,u+1)(u,u+1,u+1), which satisfies EQ1 and EF1 as before. If |S|≥3|S|≥ 3, arguments analogous to Subcase 4.1 again produce a balanced partial allocation of size u+1u+1, contradicting maximality. Subcase 4.3: d2=1d_2=1. Allocate one valued good to agent 2. The remaining goods are valued only by agent 3; distribute them between A1A_1 and A2A_2 subject to v3(A1),v3(A2)≤u+1v_3(A_1),v_3(A_2)≤ u+1, which is possible by the same capacity argument as in Subcase 3.2. All utilities lie in u,u+1\u,u+1\ and all bundles are worth at most u+1u+1 to every agent, so EQ1 and EF1 hold. Subcase 4.4: d2=0d_2=0. All remaining goods are valued only by agent 3; distribute them between A1A_1 and A2A_2 as in Subcase 4.3. The same argument applies. In every case we obtain a complete allocation satisfying EF1 and EQ1. ∎ Appendix D Omitted Material from Section 4 Proposition 10. For two agents with normalized valuations, a randomized allocation that is ex-ante EQ and ex-post EFX may fail to exist, even in goods instances. Proof. Take three goods with (v1(g1),v1(g2),v1(g3)) (v_1(g_1),v_1(g_2),v_1(g_3)) =(0.1, 0.5, 0.4), =(0.1,\,0.5,\,0.4), (v2(g1),v2(g2),v2(g3)) (v_2(g_1),v_2(g_2),v_2(g_3)) =(1, 0, 0). =(1,\,0,\,0). Both grand-bundle values equal one, so the instance is normalized. We first show that in any EFX allocation, g1g_1 must go to agent 2. Suppose instead that g1∈A1g_1∈ A_1. If A1A_1 also contained g2g_2 or g3g_3, then A1A_1 would contain a good that agent 2 values at zero; removing it would leave agent 2’s value for A1A_1 at least 1>v2(A2)=01>v_2(A_2)=0, so agent 2’s envy would persist, violating EFX. If A1=g1A_1=\g_1\, then agent 1’s utility is 0.10.1, while v1(A2∖g2)=0.4v_1(A_2 \g_2\)=0.4 and v1(A2∖g3)=0.5v_1(A_2 \g_3\)=0.5, so agent 1’s envy survives every single-good removal, again violating EFX. Next, g2g_2 must go to agent 1: if A2⊇g1,g2A_2 \g_1,g_2\, then agent 1’s own value is at most v1(g3)=0.4v_1(g_3)=0.4, while removing g1g_1 from A2A_2 leaves value at least v1(g2)=0.5v_1(g_2)=0.5, so EFX fails. Consequently, the only EFX allocations are A=(g2,g1,g3)andA′=(g2,g3,g1),A=(\g_2\,\g_1,g_3\) A =(\g_2,g_3\,\g_1\), and both are indeed EFX. Their realized utility pairs are (0.5,1)(0.5,1) and (0.9,1)(0.9,1), respectively. Every randomized allocation supported on these allocations gives agent 1 expected realized utility at most 0.90.9, strictly below agent 2’s expected realized utility of 11. Hence no randomized allocation supported on EFX allocations is ex-ante EQ. ∎ D.1 Randomized Guarantees for Laminar Binary Goods Instances Setup. Since the valuations are binary, vi(M)=|Γi|v_i(M)=| _i| for every agent i, so normalization means that all approval sets have the same cardinality; write k:=|Γi|k:=| _i|, a single constant shared by all agents. Binary valuations are restricted additive, so Observation 1 applies: any two agents have either identical or disjoint approval sets. Let Γ(1),…,Γ(T) ^(1),…, ^(T) be the distinct approval sets—so they are pairwise disjoint and |Γ(ℓ)|=k| ^( )|=k for every ℓ —and let Nℓ:=i∈N:Γi=Γ(ℓ)N_ :=\i∈ N: _i= ^( )\ be the corresponding group of identical agents, nℓ:=|Nℓ|n_ :=|N_ |, so that ∑ℓnℓ=n _ n_ =n. Let J:=M∖⋃ℓ∈[T]Γ(ℓ)J:=M _ ∈[T] ^( ) denote the goods that no agent values; thus M is the disjoint union of J and Γ(1),…,Γ(T) ^(1),…, ^(T), and vi(g)=0v_i(g)=0 for every g∈Jg∈ J and every i. Finally, set r:=maxℓ∈[T]nℓ,u:=⌊kr⌋, r:= _ ∈[T]n_ , u:= kr , s:=k−ru∈0,1,…,r−1, s:=k-ru∈\0,1,…,r-1\, and note that r≤∑ℓnℓ=nr≤ _ n_ =n. All part indices below live in ℤrZ_r, i.e., they are taken modulo r. The construction. Step 1 (parts). For every ℓ∈[T] ∈[T], fix an ordered partition of Γ(ℓ) ^( ) into r pairwise disjoint, possibly empty blocks B0ℓ,…,Br−1ℓB _0,…,B _r-1 of which exactly s have size u+1u+1 and the remaining r−sr-s have size u. This is feasible because s(u+1)+(r−s)u=ru+s=ks(u+1)+(r-s)u=ru+s=k. (When k<rk<r we have u=0u=0 and r−kr-k of the blocks are empty.) Note that every approval set is cut into the same number r of blocks, including those of groups with nℓ<rn_ <r. Step 2 (labels). For every ℓ , fix an injective map σℓ:Nℓ→ℤr _ :N_ _r and put Sℓ:=σℓ(Nℓ)S_ := _ (N_ ), so |Sℓ|=nℓ≤r|S_ |=n_ ≤ r. Step 3 (fillers). For every ℓ , fix an injective map φℓ:ℤr∖Sℓ⟶N∖Nℓ. _ :\ Z_r S_ \ \ N N_ . Such a map exists: |ℤr∖Sℓ|=r−nℓ|Z_r S_ |=r-n_ , |N∖Nℓ|=n−nℓ|N N_ |=n-n_ , and r≤nr≤ n gives r−nℓ≤n−nℓr-n_ ≤ n-n_ . (If T=1T=1, then r=n1=nr=n_1=n and S1=ℤrS_1=Z_r, so φ1 _1 is the empty map; and whenever r−nℓ≥1r-n_ ≥ 1 we have nℓ<r≤n_ <r≤ n, so N∖Nℓ≠∅N N_ ≠ .) We emphasise the two properties of φℓ _ that the proof uses: it is injective, and its image avoids NℓN_ . No relation between φℓ _ and φℓ′ _ is required for ℓ≠ℓ′ ≠ ; a single agent may serve as a filler for many groups. Step 4 (the r allocations). Fix an arbitrary partition (J1,…,Jn)(J_1,…,J_n) of the junk goods J, the same in every round. For every t∈ℤrt _r and every agent i∈Nℓi∈ N_ , define A(t)i:=Bℓσℓ(i)+t∪⋃ℓ′:i∈φℓ′(ℤr∖Sℓ′)Bℓ′φℓ′−1(i)+t∪Ji.A^(t)_i:=B _ _ (i)+t\ ∪\!\!\! _ :\,i∈ _ (Z_r S_ )\!\!\!B _ _ ^-1(i)+t\ ∪\ J_i. The randomized allocation A is the uniform distribution over A(0),…,A(r−1)A^(0),…,A^(r-1); its support has size r≤nr≤ n. Lemma 10 (Validity). For every t∈ℤrt _r, A(t)A^(t) is an allocation of M. Proof. Fix t and ℓ . The translation x↦x+tx x+t is a bijection of ℤrZ_r, so it maps the partition Sℓ,ℤr∖Sℓ\S_ ,\ Z_r S_ \ of ℤrZ_r to the partition Sℓ+t,(ℤr∖Sℓ)+t\S_ +t,\ (Z_r S_ )+t\ of ℤrZ_r. In round t the blocks of Γ(ℓ) ^( ) that are handed out are exactly those indexed by Sℓ+tS_ +t—one to each member of NℓN_ , distinct because σℓ _ is injective—together with those indexed by (ℤr∖Sℓ)+t(Z_r S_ )+t—one to each filler, distinct because φℓ _ is injective. Hence every index p∈ℤrp _r is issued exactly once, so the blocks of Γ(ℓ) ^( ) are distributed exactly once each. As ℓ ranges over [T][T] and the sets Γ(1),…,Γ(T),J ^(1),…, ^(T),J are pairwise disjoint with union M, and (J1,…,Jn)(J_1,…,J_n) partitions J, every good is assigned to exactly one agent. Finally, the pieces constituting a single bundle Ai(t)A^(t)_i are blocks of distinct approval sets together with JiJ_i, hence pairwise disjoint. ∎ Lemma 11 (Realized utilities and the cap). Fix t∈ℤrt _r and let i∈Nℓi∈ N_ . Then vi(Ai(t))=|Bσℓ(i)+tℓ|∈u,u+1,v_i (A^(t)_i )= |B _ _ (i)+t |∈\u,u+1\, and vi(Aj(t))≤u+1v_i (A^(t)_j )≤ u+1 for every agent j. Proof. Agent i values only the goods of Γ(ℓ) ^( ), so blocks of other approval sets and junk goods contribute 00 to any value computed by i; consequently vi(Aj(t))=|Aj(t)∩Γ(ℓ)|v_i(A^(t)_j)=|A^(t)_j∩ ^( )| for every j. We claim that every bundle contains at most one block of Γ(ℓ) ^( ). Indeed, a member j∈Nℓj∈ N_ receives her own block Bσℓ(j)+tℓB _ _ (j)+t and no filler block of her own group, because the image of φℓ _ avoids NℓN_ ; and an agent j∉Nℓj∉ N_ receives a block of Γ(ℓ) ^( ) only if j=φℓ(q)j= _ (q), in which case q is unique by injectivity of φℓ _ , so she receives exactly the one block Bq+tℓB _q+t. Since every block has size at most u+1u+1, this proves vi(Aj(t))≤u+1v_i(A^(t)_j)≤ u+1. Applying the claim to j=ij=i gives vi(Ai(t))=|Bσℓ(i)+tℓ|v_i(A^(t)_i)=|B _ _ (i)+t|, which lies in u,u+1\u,u+1\ by Step 1. ∎ Lemma 12 (Ex-post guarantees). Every A(t)A^(t) is simultaneously EF1 and EQ1. Proof. Fix t, write A:=A(t)A:=A^(t), and let i∈Nℓi∈ N_ and j be agents with Aj≠∅A_j≠ . EF1. If vi(Aj)≤vi(Ai)v_i(A_j)≤ v_i(A_i), then any g∈Ajg∈ A_j satisfies vi(Ai)≥vi(Aj∖g)v_i(A_i)≥ v_i(A_j \g\) because values are nonnegative. Otherwise Lemma 11 forces vi(Aj)=u+1v_i(A_j)=u+1 and vi(Ai)=uv_i(A_i)=u. In particular vi(Aj)≥1v_i(A_j)≥ 1, so AjA_j contains a good g with vi(g)=1v_i(g)=1; for this g, vi(Aj∖g)=u=vi(Ai).v_i(A_j \g\)=u=v_i(A_i). Note that g must be chosen among the goods that i approves: deleting an arbitrary good of AjA_j—for instance a junk good, or a good of another group’s approval set—need not decrease vi(Aj)v_i(A_j) at all. EQ1. If vj(Aj)≤vi(Ai)v_j(A_j)≤ v_i(A_i), any g∈Ajg∈ A_j works, again by non-negativity. (This case covers, in particular, a nonempty bundle AjA_j with vj(Aj)=0v_j(A_j)=0, which contains no good that j approves; there the removed good is an arbitrary, zero-valued one.) Otherwise Lemma 11, applied to j and to i, gives vj(Aj)=u+1v_j(A_j)=u+1 and vi(Ai)=uv_i(A_i)=u. Then AjA_j contains a good g with vj(g)=1v_j(g)=1, and vj(Aj∖g)=u=vi(Ai).∎v_j(A_j \g\)=u=v_i(A_i). Lemma 13 (Ex-ante guarantees). The randomized allocation A is ex-ante EQ and ex-ante EF; indeed every agent has expected utility exactly k/rk/r. Proof. Fix i∈Nℓi∈ N_ . For fixed σℓ(i) _ (i), the map t↦σℓ(i)+t _ (i)+t is a bijection of ℤrZ_r, so by Lemma 11, ∑t∈ℤrvi(Ai(t))=∑t∈ℤr|Bσℓ(i)+tℓ|=∑p∈ℤr|Bpℓ|=|Γ(ℓ)|=k. _t _rv_i (A^(t)_i )= _t _r |B _ _ (i)+t |= _p _r |B _p |= | ^( ) |=k. As the randomized allocation is uniform over the r rounds, [vi(Ai)]=k/rE[v_i(A_i)]=k/r. Crucially, this value does not depend on i or on ℓ , because every approval set has the same size k; hence A is ex-ante EQ. (here cutting every Γ(ℓ) ^( ) into the same number r of blocks is used: cutting Γ(ℓ) ^( ) into nℓn_ blocks would give the members of a group with nℓ<rn_ <r the larger expected utility k/nℓk/n_ .) For ex-ante EF, fix j≠ij≠ i and recall from the proof of Lemma 11 that vi(Aj(t))=|Aj(t)∩Γ(ℓ)|v_i(A^(t)_j)=|A^(t)_j∩ ^( )| and that Aj(t)A^(t)_j contains at most one block of Γ(ℓ) ^( ). We distinguish three cases. 1. j∈Nℓj∈ N_ . Then j receives the block Bσℓ(j)+tℓB _ _ (j)+t in round t, and the computation above with σℓ(j) _ (j) in place of σℓ(i) _ (i) gives [vi(Aj)]=k/rE[v_i(A_j)]=k/r. 2. j=φℓ(q)j= _ (q) for some (necessarily unique) q∈ℤr∖Sℓq _r S_ . Then j receives the block Bq+tℓB _q+t in round t, and since t↦q+t q+t is again a bijection of ℤrZ_r, [vi(Aj)]=1r∑t∈ℤr|Bq+tℓ|=kr.E[v_i(A_j)]= 1r _t _r |B _q+t |= kr. 3. Otherwise j receives no block of Γ(ℓ) ^( ) in any round, so [vi(Aj)]=0E[v_i(A_j)]=0. In every case [vi(Aj)]≤k/r=[vi(Ai)]E[v_i(A_j)]≤ k/r=E[v_i(A_i)], which is ex-ante EF. ∎ Proof of Theorem 8. By Lemma 10 the randomized allocation is supported on r≤nr≤ n deterministic allocations, by Lemma 12 every one of them is EF1+EQ1, and by Lemma 13 the randomized allocation is ex-ante EF+EQ. For the running time, the groups NℓN_ and the sets Γ(ℓ) ^( ) are obtained by comparing the n approval sets pairwise, the balanced partitions of Step 1 and the injections of Steps 2 and 3 are constructed greedily, and the r≤nr≤ n allocations of Step 4 are then written down directly; every step is polynomial in n and m. ∎ Remark 5. Ex-ante envy-freeness holds with equality rather than strictly: from agent i’s perspective, the r agents in Nℓ∪φℓ(ℤr∖Sℓ)N_ ∪ _ (Z_r S_ ) all have expected value exactly k/rk/r, and every other agent has expected value 00. Note also that our construction need not satisfy the ex-post guarantee EQX: an agent with realized utility u+1u+1 may also hold junk goods or blocks approved only by other groups, and removing such a zero-valued good from her bundle does not lower her utility, so an agent with realized utility u still fails the EQX comparison against her. D.2 Tight Examples for Ex-post Guarantees in Randomized Allocations Both Theorem 8 and Theorem 9 pair exact ex-ante EF+EQ with ex-post EF1+EQ1. In this section, we show that these ex-post guarantees cannot be strengthened to their “up to any item” counterparts. The incompatibility arises from combining the ex-ante with the ex-post and not due to the stronger deterministic ex-post guarantees; Theorem 5 always guarantees a deterministic EFX+EQX allocation. Proposition 11. There is a normalized binary goods instance with four agents, five goods, and laminar approval sets in which no ex-ante EQ randomized allocation is ex-post EFX. Consequently, the ex-post EF1 guarantee of Theorem 8 cannot be strengthened to EFX. Proof. Let N=1,2,3,4N=\1,2,3,4\ and M=a1,a2,b1,b2,zM=\a_1,a_2,b_1,b_2,z\, where agents 1,2,31,2,3 approve Γ1=Γ2=Γ3=a1,a2 _1= _2= _3=\a_1,a_2\, agent 44 approves Γ4=b1,b2 _4=\b_1,b_2\, and the good z is approved by nobody. Every agent values M at 22, so the instance is normalized, and any two approval sets are either identical or disjoint, and hence the family is laminar. We claim that every EFX allocation A satisfies v4(A4)≥ 1and∑i=13vi(Ai)= 2.v_4(A_4)\ ≥\ 1 _i=1^3v_i(A_i)\ =\ 2. (11) The first part of (11). Suppose v4(A4)=0v_4(A_4)=0, i.e., b1,b2∉A4b_1,b_2∉ A_4. If a single agent i held both b1b_1 and b2b_2, then i≠4i≠ 4 and, taking g=b1g=b_1, we would get v4(Ai∖g)≥v4(b2)=1>0=v4(A4)v_4(A_i \g\)≥ v_4(b_2)=1>0=v_4(A_4), contradicting EFX for the pair (4,i)(4,i). Hence b1∈Ai1b_1∈ A_i_1 and b2∈Ai2b_2∈ A_i_2 for two distinct agents i1,i2∈1,2,3i_1,i_2∈\1,2,3\. Moreover, if Ai1A_i_1 contained a good g≠b1g≠ b_1, then v4(Ai1∖g)≥v4(b1)=1>0v_4(A_i_1 \g\)≥ v_4(b_1)=1>0, again contradicting EFX for (4,i1)(4,i_1). Therefore Ai1=b1A_i_1=\b_1\ and, symmetrically, Ai2=b2A_i_2=\b_2\; in particular vi1(Ai1)=0v_i_1(A_i_1)=0. The remaining goods a1,a2,za_1,a_2,z are thus split between agent 44 and the unique remaining agent y∈1,2,3y∈\1,2,3\. For x∈4,yx∈\4,y\, EFX for the pair (i1,x)(i_1,x) requires vi1(Ax∖g)≤vi1(Ai1)=0v_i_1(A_x \g\)≤ v_i_1(A_i_1)=0 for every g∈Axg∈ A_x; consequently, if AxA_x contains one of a1,a2a_1,a_2, then AxA_x contains nothing else. Consequently, if either A4A_4 or AyA_y contains one of a1,a2a_1,a_2, that bundle must be a singleton. But A4∪AyA_4∪ A_y must contain all three goods a1,a2,za_1,a_2,z. Since these three goods must be distributed between only two bundles, some bundle must contain one of a1,a2a_1,a_2 together with another good, a contradiction. The second part of (11). No agent holds both a1a_1 and a2a_2: if agent x did, pick any i∈1,2,3∖xi∈\1,2,3\ \x\, which exists because |1,2,3|=3|\1,2,3\|=3; then vi(Ai)=0v_i(A_i)=0 while vi(Ax∖a1)≥vi(a2)=1v_i(A_x \a_1\)≥ v_i(a_2)=1, contradicting EFX for (i,x)(i,x). Next, agent 44 holds neither a1a_1 nor a2a_2: suppose a1∈A4a_1∈ A_4. By the first part, A4A_4 also contains a good of b1,b2\b_1,b_2\, so |A4|≥2|A_4|≥ 2; and since a2∉A4a_2∉ A_4, at least two agents of 1,2,3\1,2,3\ receive no good of a1,a2\a_1,a_2\ and hence have utility 00. Picking such an agent i and any g∈A4∖a1g∈ A_4 \a_1\ gives vi(A4∖g)≥vi(a1)=1>0=vi(Ai)v_i(A_4 \g\)≥ v_i(a_1)=1>0=v_i(A_i), contradicting EFX for (i,4)(i,4). Hence a1a_1 and a2a_2 are held by two distinct agents of 1,2,3\1,2,3\, so exactly two of these agents have utility 11 and the third has utility 00, which gives ∑i≤3vi(Ai)=2 _i≤ 3v_i(A_i)=2. Now let A be any ex-post EFX randomized allocation and write μi=[vi(Ai)] _i=E[v_i(A_i)]. Taking expectations in (11) yields μ1+μ2+μ3=2 _1+ _2+ _3=2 and μ4≥1 _4≥ 1. If A were ex-ante EQ, all four expectations would equal a common value μ, so that 3μ=23μ=2 and simultaneously μ≥1μ≥ 1, which is impossible. ∎ Proposition 12. There is a binary chores instance with two agents and two chores in which no ex-ante EF+EQ randomized allocation is ex-post EFX, and none is ex-post EQX. Consequently, neither the ex-post EF1 nor the ex-post EQ1 guarantee of Theorem 9 can be strengthened to EFX or EQX, respectively. Proof. Let N=1,2N=\1,2\ and M=c1,c2M=\c_1,c_2\ with v1(c1)=v2(c1)=v2(c2)=−1v_1(c_1)=v_2(c_1)=v_2(c_2)=-1 and v1(c2)=0v_1(c_2)=0. The instance is binary, hence restricted additive with base value v(c)=−1v(c)=-1, and it is unnormalized. If agent 11 receives both chores, then both EFX and EQX fail for the pair (1,2)(1,2) with c=c2c=c_2, because v1(A1∖c2)=−1<0=v1(A2)=v2(A2)v_1(A_1 \c_2\)=-1<0=v_1(A_2)=v_2(A_2); symmetrically, both fail with c=c1c=c_1 when agent 22 receives both chores. The two remaining allocations, A∗=(c1,c2)andA†=(c2,c1),A =(\c_1\,\c_2\) A =(\c_2\,\c_1\), are EFX and EQX: every bundle is a singleton, so deleting its unique chore leaves the empty bundle, of value 00, which is at least the value of any bundle in a chores instance. Hence every ex-post EFX (or ex-post EQX) randomized allocation is supported on A∗,A†\A ,A \. Writing p for the probability of A∗A , we obtain [v1(A1)]=−pE[v_1(A_1)]=-p and [v2(A2)]=−1E[v_2(A_2)]=-1, so ex-ante EQ forces p=1p=1, i.e., the deterministic allocation A∗A . But A∗A is not ex-ante EF, since v1(A1)=−1<0=v1(A2)v_1(A_1)=-1<0=v_1(A_2). ∎ Remark 6. Proposition 11 settles only the envy coordinate for laminar binary goods, and we did not find a corresponding obstruction for equitability. An exhaustive search over all normalized binary goods instances with laminar approval sets, at most four agents and at most seven goods, together with selected larger instances with up to six agents, produced no instance in which ex-ante EF+EQ is incompatible with ex-post EF1+EQX. Whether Theorem 8 can be strengthened to ex-post EF1+EQX is an intriguing open question.