Paper deep dive
Fair Division with Strictly Increasing Valuations: A Tight Threshold for Two-Agent EF1 and PO
Nicholas Teh
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:We study whether strictly positive marginal values restore the compatibility of envy-freeness up to one good (EF1) and Pareto optimality (PO) for indivisible goods. For two agents, we identify the exact threshold in the number of goods. Every instance with at most seven goods and strictly increasing valuations admits an allocation that is both EF1 and PO, without any submodularity assumption. In contrast, we construct an eight-good instance with normalized, integer-valued, strictly increasing, submodular valuations in which every EF1 allocation is strictly Pareto dominated. Thus, eight goods are necessary and sufficient for a two-agent counterexample. Finally, we strengthen the three-agent NP-hardness result of Chandramouleeswaran and Nimbhorkar (2026): deciding whether an EF1 and PO allocation exists remains NP-hard for normalized, integer-valued, monotone submodular valuations even when zero marginals are confined to eight fixed agent-good pairs, all involving a single agent.
Tags
Links
- Source: https://arxiv.org/abs/2607.23367v1
- Canonical: https://arxiv.org/abs/2607.23367v1
Trouble viewing inline? Open PDF directly →
Full Text
49,936 characters extracted from source content.
Expand or collapse full text
Fair Division with Strictly Increasing Valuations: A Tight Threshold for Two-Agent EF1 and PO Nicholas Teh Abstract We study whether strictly positive marginal values restore the compatibility of envy-freeness up to one good (EF1) and Pareto optimality (PO) for indivisible goods. For two agents, we identify the exact threshold in the number of goods. Every instance with at most seven goods and strictly increasing valuations admits an allocation that is both EF1 and PO, without any submodularity assumption. In contrast, we construct an eight-good instance with normalized, integer-valued, strictly increasing, submodular valuations in which every EF1 allocation is strictly Pareto dominated. Thus, eight goods are necessary and sufficient for a two-agent counterexample. Finally, we strengthen the three-agent NP-hardness result of Chandramouleeswaran and Nimbhorkar (2026): deciding whether an EF1 and PO allocation exists remains NP-hard for normalized, integer-valued, monotone submodular valuations even when zero marginals are confined to eight fixed agent-good pairs, all involving a single agent. 1 Introduction Fair division of indivisible goods is a well-studied problem in economics, operations research, and computer science. A central objective is to reconcile fairness with economic efficiency. Exact envy-freeness is often unattainable: for example, a single desirable good cannot be allocated between two agents without creating envy. This motivates relaxations such as envy-freeness up to one good (EF1), which requires that any envy can be eliminated by removing some good from the envied bundle, and the stronger notion of envy-freeness up to any good (EFX), which requires this condition to hold after the removal of any good from that bundle. Since a fair allocation may nevertheless admit a Pareto improvement, it is natural to ask whether these fairness guarantees can be achieved together with Pareto optimality (PO). For additive valuations, an allocation that is both EF1 and PO always exists [9]. The same is true for matroid-rank valuations [5]. For general monotone submodular valuations, however, recent work gives counterexamples. Mackenzie and Suzuki [15] construct a two-agent, eight-good instance in which every EF1 allocation is strictly Pareto dominated, while Chandramouleeswaran and Nimbhorkar [10] give a two-agent, six-good coverage instance with no allocation that is both EF1 and PO. Both constructions rely on zero marginal values. This motivates Open Problem 3.4 of Chandramouleeswaran and Nimbhorkar [10]: Does every instance with strictly positive marginal values admit an allocation that is simultaneously EF1 and PO? They also show that deciding whether an EF1 and PO allocation exists is NP-hard for three agents with monotone submodular valuations [10, Theorem 3]. Our first contribution answers the open problem negatively and determines the exact two-agent threshold in the number of goods. We modify the eight-good construction of Mackenzie and Suzuki [15] to obtain normalized, integer-valued, strictly increasing, submodular valuations for which every EF1 allocation is strictly Pareto dominated. We complement this counterexample with a matching existence result: every two-agent instance with at most seven goods and strictly increasing valuations admits an allocation that is both EF1 and PO. This positive result requires no submodularity assumption. Together, these results show that eight goods are necessary and sufficient for a two-agent counterexample. Our second contribution strengthens the three-agent hardness result of Chandramouleeswaran and Nimbhorkar [10]. We show that deciding whether an EF1 and PO allocation exists remains NP-hard for normalized, integer-valued, monotone submodular valuations even when zero marginals are confined to eight fixed agent-good pairs, all involving a single agent. Section 3 presents the eight-good counterexample. Section 4 proves existence for two agents with at most seven goods. Section 5 establishes the restricted NP-hardness result. 1.1 Related Work EF1 was formalized by Budish [8] and is implicit in the envy cycle elimination algorithm of Lipton et al. [14], which computes an EF1 allocation for arbitrary monotone valuations. This general existence guarantee does not impose efficiency. For additive valuations, Caragiannis et al. [9] showed that every maximum Nash welfare allocation is EF1 and PO. Barman, Krishnamurthy, and Vaish [4] subsequently gave a pseudopolynomial-time algorithm for computing such an allocation and established the stronger existence of an allocation that is EF1 and fractionally Pareto optimal. For a fixed number of agents, Mahara [16] obtained a polynomial-time algorithm for EF1 and fractional Pareto optimality. We refer to Amanatidis et al. [1] for a broader survey of discrete fair division. Beyond additive valuations, exact compatibility is known for several structured classes. Benabbou et al. [5] showed that matroid-rank valuations admit, in polynomial time, an EF1 allocation maximizing utilitarian welfare, and hence an EF1 and PO allocation. For binary valuations, Brandl, Suksompong, and Teh [7] characterize the allocation rule induced by maximum Nash welfare and leximin through EF1, strategyproofness, neutrality, and related axioms. Strictly positive marginal values have also been studied in connection with the stronger EFX requirement. Plaut and Roughgarden [17] proved that, when all agents have the same monotone valuation and all marginal values are nonzero, a leximin allocation is EFX and PO. They also showed that, for two agents with distinct general valuations, EFX and PO can be incompatible even when all marginals are nonzero. For identical monotone submodular valuations, Chandramouleeswaran and Nimbhorkar [10] proved that every leximin allocation is EF1 and PO, without requiring strict increase. These identical valuation results do not resolve the heterogeneous setting considered here. In the setting with only a few more goods than agents, Lim, Neoh, and Teh [13] study the welfare and computational consequences of imposing EFX, including the complexity of achieving EFX together with Pareto optimality. For broader valuation classes, efficiency becomes harder to reconcile with fairness. Caragiannis et al. [9] showed that maximum Nash welfare need not be EF1 for monotone submodular valuations; their positive guarantee is the weaker marginal EF1 property. They also showed that EF1 and PO may be incompatible for monotone subadditive valuations. Barman and Suzuki [3] recover compatibility with a multiplicative 1/21/2-approximation to Pareto optimality for subadditive valuations. Related questions have also been studied for chores and mixed manna. For two agents with additive valuations over goods and chores, Aziz et al. [2] give a polynomial-time algorithm for computing an EF1 and PO allocation. For general monotone chore costs, Bhaskar, Sricharan, and Vaish [6] give a polynomial-time algorithm for EF1, without an efficiency guarantee. Mahara [16] proved that additive chore instances with any number of agents admit an EF1 and fractionally Pareto-optimal allocation, while Teh [18] showed that an EF1 and PO allocation can be computed efficiently when the number of chores exceeds the number of agents by a constant. Beyond additivity, incompatibility reappears. Hosseini, Narang, and Wąs [12] exhibit a two-agent instance with identical monotone submodular coverage costs, induced by a rooted tree, that has no EF1 and PO allocation, and show that deciding existence is NP-hard even for unweighted trees. The six-good coverage construction of Chandramouleeswaran and Nimbhorkar [10] also gives a counterexample for chores. 2 Preliminaries Let N be a finite set of agents and let M be a finite set of indivisible goods. Each agent i∈Ni∈ N has a valuation function vi:2M→ℝ≥0v_i:2^M _≥ 0, normalized so that vi(∅)=0v_i( )=0. An allocation is a tuple X=(Xi)i∈NX=(X_i)_i∈ N whose bundles are pairwise disjoint and whose union is M. Thus, all allocations in this paper are complete (i.e., all goods are allocated). For S⊆MS M and g∈M∖Sg∈ M S, the marginal value of g given S is vi(g∣S)=vi(S∪g)−vi(S).v_i(g S)=v_i(S∪\g\)-v_i(S). A valuation function v is monotone if v(S)≤v(T)v(S)≤ v(T) whenever S⊆TS T. It is strictly increasing if v(g∣S)>0v(g S)>0 for every S⊆M∖gS M \g\. Since M is finite, this is equivalent to v(S)<v(T)v(S)<v(T) whenever S⊊TS T. Accordingly, “strictly increasing” and “having strictly positive marginals” refer to the same condition in this paper.111This is exactly the condition in Open Problem 3.4 of Chandramouleeswaran and Nimbhorkar [10]. A valuation is submodular if it has diminishing marginal returns, i.e., v(g∣S)≥v(g∣T)v(g S)≥ v(g T) whenever S⊆T⊆M∖gS T M \g\.222For the computational result in Section 5, each valuation function is represented by a polynomial-size description from which vi(S)v_i(S) can be evaluated in polynomial time. Following Budish [8] and Lipton et al. [14], we use EF1 as our fairness criterion. Definition 2.1 (EF1). An allocation X=(Xi)i∈NX=(X_i)_i∈ N is envy-free up to one good (EF1) if, for every ordered pair of distinct agents i,j∈Ni,j∈ N, either Xj=∅X_j= , or there exists g∈Xjg∈ X_j such that vi(Xi)≥vi(Xj∖g)v_i(X_i)≥ v_i(X_j \g\). We measure efficiency using the standard notions of Pareto dominance and Pareto optimality; see, e.g., Caragiannis et al. [9] and Barman, Krishnamurthy, and Vaish [4]. Definition 2.2 (Pareto notions). An allocation Y Pareto dominates X if vi(Yi)≥vi(Xi)v_i(Y_i)≥ v_i(X_i) for every i∈Ni∈ N, with at least one strict inequality. It strictly Pareto dominates X if vi(Yi)>vi(Xi)v_i(Y_i)>v_i(X_i) for every i∈Ni∈ N. An allocation is Pareto optimal (PO) if it is not Pareto dominated. It is weakly Pareto optimal (weak-PO) if it is not strictly Pareto dominated. Thus PO implies weak-PO. 3 An Eight-Good Counterexample with Strictly Positive Marginals We first establish the negative side of our two-agent threshold result by constructing an eight-good instance with strictly positive marginal values in which EF1 and Pareto efficiency are incompatible. The construction is obtained by perturbing the example of Mackenzie and Suzuki [15]: we fix ε=1/6 =1/6, scale all values by 1212, and add |S||S| to the value of every bundle S. The additive term makes every marginal value strictly positive, while the scaling ensures that the strict EF1 violations and strict Pareto improvements in the original instance survive the perturbation. We verify all required properties directly from the resulting integer-valued tables, so the proof is self-contained. Let M=A∪˙BM=A ∪B, where A=a1,a2,a3A=\a_1,a_2,a_3\ and B=b1,b2,b3,b4,b5B=\b_1,b_2,b_3,b_4,b_5\. For a bundle S⊆MS M, let x(S)=|S∩A|x(S)=|S∩ A| and y(S)=|S∩B|y(S)=|S∩ B|. Each agent’s value for a bundle depends only on these two type counts. u1(x,y)y=0y=1y=2y=3y=4y=5x=001326394653x=1253847505354x=2284150535455x=3294251545556 array[]c|ru_1(x,y)&y=0&y=1&y=2&y=3&y=4&y=5\\ x=0&0&13&26&39&46&53\\ x=1&25&38&47&50&53&54\\ x=2&28&41&50&53&54&55\\ x=3&29&42&51&54&55&56 array (1) u2(x,y)y=0y=1y=2y=3y=4y=5x=001326395051x=1172839465354x=2323946535455x=3475053545556 array[]c|ru_2(x,y)&y=0&y=1&y=2&y=3&y=4&y=5\\ x=0&0&13&26&39&50&51\\ x=1&17&28&39&46&53&54\\ x=2&32&39&46&53&54&55\\ x=3&47&50&53&54&55&56 array (2) For each i∈1,2i∈\1,2\, define vi(S)=ui(x(S),y(S))v_i(S)=u_i(x(S),y(S)) for every S⊆MS M. Our result is as follows. Theorem 3.1. The valuations v1v_1 and v2v_2 are normalized, integer-valued, strictly increasing, and submodular. Every EF1 allocation is strictly Pareto dominated. Consequently, no allocation is simultaneously EF1 and weak-PO, and in particular no allocation is simultaneously EF1 and PO. We use the following elementary criterion for count-based valuations. Lemma 3.2. Let M=A∪˙BM=A ∪B, where |A|=p|A|=p and |B|=q|B|=q, and let v(S)=f(|S∩A|,|S∩B|)v(S)=f(|S∩ A|,|S∩ B|). Define the A- and B-marginal arrays by ΔAf(x,y) _Af(x,y) =f(x+1,y)−f(x,y) =f(x+1,y)-f(x,y) (0≤x<p, 0≤y≤q), (0≤ x<p,\ 0≤ y≤ q), ΔBf(x,y) _Bf(x,y) =f(x,y+1)−f(x,y) =f(x,y+1)-f(x,y) (0≤x≤p, 0≤y<q). (0≤ x≤ p,\ 0≤ y<q). Suppose every entry of both arrays is positive and each array is coordinatewise nonincreasing: whenever both entries are defined and x≤x′x≤ x , y≤y′y≤ y , ΔAf(x,y)≥ΔAf(x′,y′)andΔBf(x,y)≥ΔBf(x′,y′). _Af(x,y)≥ _Af(x ,y ) _Bf(x,y)≥ _Bf(x ,y ). Then v is strictly increasing and submodular. Proof. At a bundle with type counts (x,y)(x,y), the marginal value of any unallocated A-good is ΔAf(x,y) _Af(x,y), and the marginal value of any unallocated B-good is ΔBf(x,y) _Bf(x,y). Positivity therefore gives strict increase. For submodularity, let S⊆TS T and g∉Tg∉ T. If g∈Ag∈ A, let (x,y)(x,y) and (x′,y′)(x ,y ) be the type counts of S and T, respectively. Then x≤x′x≤ x and y≤y′y≤ y , so the assumed coordinatewise monotonicity gives v(g∣S)=ΔAf(x,y)≥ΔAf(x′,y′)=v(g∣T).v(g S)= _Af(x,y)≥ _Af(x ,y )=v(g T). The argument for g∈Bg∈ B is identical. ∎ Proof of Theorem 3.1. Valuation properties. The tables give vi(∅)=ui(0,0)=0v_i( )=u_i(0,0)=0, and all entries are integers. Appendix A displays every value of ΔAui _Au_i and ΔBui _Bu_i. Each entry is at least 11, and in each array every row and every column is nonincreasing. Lemma 3.2 therefore proves that both valuations are strictly increasing and submodular. EF1 splits. Represent an allocation by a count split (x,y)(x,y): agent 1 receives x goods from A and y goods from B, while agent 2 receives the remaining (3−x,5−y)(3-x,5-y) goods. Since the agents are indifferent among goods of the same type, all allocations with the same count split have the same utilities and the same EF1 status. Consider agent 1’s comparison with agent 2. Deleting an A-good from agent 2’s bundle, when possible, leaves type counts (2−x,5−y)(2-x,5-y); deleting a B-good, when possible, leaves (3−x,4−y)(3-x,4-y). Let d1(x,y)d_1(x,y) be the smaller u1u_1-value among the applicable deletion outcomes. When agent 2’s bundle is nonempty, agent 1 satisfies EF1 exactly when u1(x,y)≥d1(x,y).u_1(x,y)≥ d_1(x,y). (3) If agent 2’s bundle is empty, this comparison is automatic. Similarly, deleting an A-good from agent 1’s bundle leaves counts (x−1,y)(x-1,y), and deleting a B-good leaves (x,y−1)(x,y-1). Let d2(x,y)d_2(x,y) be the smaller u2u_2-value among the applicable outcomes. When agent 1’s bundle is nonempty, agent 2 satisfies EF1 exactly when u2(3−x,5−y)≥d2(x,y).u_2(3-x,5-y)≥ d_2(x,y). (4) If agent 1’s bundle is empty, this comparison is automatic. For each nonautomatic comparison, define σ1(x,y)=u1(x,y)−d1(x,y),σ2(x,y)=u2(3−x,5−y)−d2(x,y). _1(x,y)=u_1(x,y)-d_1(x,y), _2(x,y)=u_2(3-x,5-y)-d_2(x,y). Thus the relevant agent satisfies EF1 if and only if the corresponding σi(x,y) _i(x,y) is nonnegative. Substituting the entries of (1)–(2) yields the following classification. An entry E marks a split that is EF1 for both agents; an entry 11 or 22 identifies the unique agent who violates EF1 at that split. y=0y=1y=2y=3y=4y=5x=01111E2x=1111E22x=211E222x=31E2222 array[]c|r&y=0&y=1&y=2&y=3&y=4&y=5\\ x=0&1&1&1&1&E&2\\ x=1&1&1&1&E&2&2\\ x=2&1&1&E&2&2&2\\ x=3&1&E&2&2&2&2 array (5) Appendix B gives the underlying values of σ1 _1 and σ2 _2. The only EF1 count splits are therefore (0,4),(1,3),(2,2),(3,1).(0,4), (1,3), (2,2), (3,1). (6) At each of these splits, both agents receive four goods. Strict Pareto domination. At split (x,y)(x,y), the utility pair is (u1(x,y),u2(3−x,5−y))(u_1(x,y),u_2(3-x,5-y)). For every EF1 split, the following table exhibits another count split that strictly improves both coordinates. EF1 splitutility pairdominating splitnew utility pair(0,4)(46,50)(1,2)(47,53)(1,3)(50,46)(0,5)(53,47)(2,2)(50,46)(0,5)(53,47)(3,1)(42,50)(1,2)(47,53) array[]c@ c@ c@ c $ EF1$ split&utility pair&dominating split&new utility pair\\ (0,4)&(46,50)&(1,2)&(47,53)\\ (1,3)&(50,46)&(0,5)&(53,47)\\ (2,2)&(50,46)&(0,5)&(53,47)\\ (3,1)&(42,50)&(1,2)&(47,53)\\ array (7) Hence every EF1 allocation is strictly Pareto dominated and therefore fails weak-PO. ∎ Remark 3.3 (How the example is obtained). Let gig_i denote agent i’s valuation in [15, Theorem 3.1] with ε=1/6 =1/6. The integer tables satisfy vi(S)=12gi(S)+|S|v_i(S)=12g_i(S)+|S|. The term |S||S| adds exactly 11 to the marginal value of every good. In the original construction, EF1 holds exactly at the balanced 44–44 splits. At every other split, the agent who violates EF1 holds at most three goods, while the envied bundle still contains at least four goods after one deletion. Adding |S||S| therefore decreases the violating agent’s own-minus-envied comparison by at least one. At a balanced split, the comparison is between a four-good own bundle and a three-good bundle after deletion, so the same term increases the comparison by one and preserves EF1. Each displayed Pareto improvement changes the bundle sizes from 44–44 to 33–55, with the identity of the agent receiving the smaller bundle depending on the split. After multiplication by 1212, each increase is at least 22. The agent whose bundle shrinks loses only one unit from the |S||S| term, while the other agent gains one unit. Both agents therefore still improve strictly. The direct verification above and in Appendices A–B makes the transformed instance independently checkable. Every marginal in Theorem 3.1 is positive, yet the instance has no EF1 and PO allocation, thus provides a negative answer to an open problem of Chandramouleeswaran and Nimbhorkar [10], that strictly positive marginal values do not guarantee an allocation that is simultaneously EF1 and PO, even for two agents with submodular valuations. 4 Existence for Two Agents with at Most Seven Goods Having shown that eight goods suffice for nonexistence, we now prove that the construction of Section 3 is minimal. Specifically, every two-agent instance with at most seven goods and strictly increasing valuations admits an allocation that is both EF1 and PO. Notably, this positive result does not require submodularity. The proof associates with each agent a threshold separating bundles that may violate EF1 from those that are automatically safe. We then show that, unless the ground set contains at least eight goods, the two agents can be assigned disjoint bundles lying above their respective thresholds. Such an allocation is EF1, and a Pareto improvement argument then yields an allocation that is simultaneously EF1 and PO. The following terminology is specific to the two-agent setting. A bundle is called EF1-violating only with respect to the allocation in which the other agent receives its complement. Definition 4.1 (EF1-violating bundles and the violation threshold). Fix a valuation v on M. For S⊆MS M, write T=M∖ST=M S. We call S EF1-violating for v if T≠∅T≠ and v(S)<v(T∖g)for every g∈T.v(S)<v(T \g\) every g∈ T. (8) Equivalently, an agent receiving S in the allocation (S,T)(S,T) violates EF1. Let ℬ(v)B(v) be the family of EF1-violating bundles. When ℬ(v)≠∅B(v)≠ , define τ(v)=maxS∈ℬ(v)v(S)τ(v)= _S (v)v(S) and (v)=R⊆M:v(R)>τ(v)U(v)=\R M:v(R)>τ(v)\. No bundle in (v)U(v) is EF1-violating. Lemma 4.2. Let v be strictly increasing and suppose ℬ(v)≠∅B(v)≠ . Choose S∈ℬ(v)S (v) with v(S)=τ(v)v(S)=τ(v), and let T=M∖ST=M S. Then |T|≥2|T|≥ 2, the family (v)U(v) is closed under supersets, and ℱ(S,T)=S∪g:g∈T∪T∖g:g∈T⊆(v).F(S,T)=\S∪\g\:g∈ T\∪\T \g\:g∈ T\ (v). (9) Proof. If |T|=1|T|=1, say T=gT=\g\, then (8) gives v(S)<v(∅)v(S)<v( ), contradicting monotonicity because ∅⊆S S. Thus |T|≥2|T|≥ 2. If R∈(v)R (v) and R⊆R′R R , monotonicity gives v(R′)≥v(R)>τ(v)v(R )≥ v(R)>τ(v), so R′∈(v)R (v). Hence (v)U(v) is closed under supersets. Finally, for each g∈Tg∈ T, strict increase gives v(S∪g)>v(S)=τ(v)v(S∪\g\)>v(S)=τ(v), while (8) gives v(T∖g)>v(S)=τ(v)v(T \g\)>v(S)=τ(v). Both kinds of bundles in (9) therefore belong to (v)U(v). ∎ Two set families 1,2⊆2MG_1,G_2 2^M are cross-intersecting if every set in 1G_1 intersects every set in 2G_2. Cross-intersection is exactly the obstruction that prevents one from choosing disjoint bundles, one from each family. The next lemma shows that the structured families in Lemma 4.2 can have this obstruction only on a ground set of at least eight goods. Lemma 4.3. Let M=S1∪˙T1=S2∪˙T2M=S_1 ∪T_1=S_2 ∪T_2 for any |T1|,|T2|≥2|T_1|,|T_2|≥ 2 and define ℱi=ℱ(Si,Ti)F_i=F(S_i,T_i) as in (9). Let p,q,r,sp,q,r,s be the sizes of the four cells formed by the two bipartitions: S2T2S1p=|S1∩S2|q=|S1∩T2|T1r=|T1∩S2|s=|T1∩T2|. array[]c|c&S_2&T_2\\ S_1&p=|S_1∩ S_2|&q=|S_1∩ T_2|\\ T_1&r=|T_1∩ S_2|&s=|T_1∩ T_2| array. (10) Then ℱ1F_1 and ℱ2F_2 are cross-intersecting if and only if p≥1,q≥2,r≥2,s≥3.p≥ 1, q≥ 2, r≥ 2, s≥ 3. (11) In particular, cross-intersection implies |M|≥8|M|≥ 8. Proof. Assume first that ℱ1F_1 and ℱ2F_2 are cross-intersecting. We begin with s. If s≤2s≤ 2, choose g∈T1g∈ T_1 and h∈T2h∈ T_2 so that T1∩T2⊆g,hT_1∩ T_2 \g,h\. If the intersection is empty, choose g and h arbitrarily. If it has one element, choose that element for both. If it has two elements, choose one as g and the other as h. In every case, (T1∖g)∩(T2∖h)=∅(T_1 \g\)∩(T_2 \h\)= , contradicting cross-intersection. Hence s≥3s≥ 3. Next suppose p=0p=0. Choose distinct g,h∈T1∩T2g,h∈ T_1∩ T_2, which is possible because s≥3s≥ 3. The goods g and h lie outside both S1S_1 and S2S_2, and g≠hg≠ h. Therefore, (S1∪g)∩(S2∪h)=∅(S_1∪\g\)∩(S_2∪\h\)= , again a contradiction. Thus p≥1p≥ 1. We now prove q≥2q≥ 2. If q=0q=0, choose x∈T1∩T2x∈ T_1∩ T_2. Then (S1∪x)∩(T2∖x)=∅(S_1∪\x\)∩(T_2 \x\)= , contradicting cross-intersection. Suppose instead that q=1q=1, and write S1∩T2=xS_1∩ T_2=\x\. The set T2∖xT_2 \x\ is disjoint from S1S_1. For every g∈T1g∈ T_1, it must nevertheless intersect S1∪gS_1∪\g\. The only possible intersection point is g, so T1⊆T2∖xT_1 T_2 \x\. It follows that T1∩S2=∅T_1∩ S_2= , hence S2⊆S1S_2 S_1. Moreover, S1∖S2=S1∩T2=xS_1 S_2=S_1∩ T_2=\x\, so S1=S2∪x∈ℱ2S_1=S_2∪\x\ _2. But S1S_1 is disjoint from every set T1∖g∈ℱ1T_1 \g\ _1, a contradiction. Therefore q≥2q≥ 2. By symmetry, r≥2r≥ 2. This proves the necessity of (11). Conversely, assume (11). Two sets of the forms S1∪gS_1∪\g\ and S2∪hS_2∪\h\ intersect in S1∩S2S_1∩ S_2, which is nonempty because p≥1p≥ 1. A set S1∪gS_1∪\g\ intersects every T2∖hT_2 \h\ because deleting one good cannot remove all q≥2q≥ 2 goods in S1∩T2S_1∩ T_2. The symmetric statement follows from r≥2r≥ 2. Finally, (T1∖g)∩(T2∖h)(T_1 \g\)∩(T_2 \h\) is obtained from T1∩T2T_1∩ T_2 by deleting at most two goods, and is therefore nonempty because s≥3s≥ 3. Thus ℱ1F_1 and ℱ2F_2 are cross-intersecting. The four cells in (10) partition M. Hence cross-intersection implies |M|=p+q+r+s≥1+2+2+3=8.∎|M|=p+q+r+s≥ 1+2+2+3=8. Theorem 4.4. Every two-agent instance with at most seven goods and strictly increasing valuations admits an allocation that is simultaneously EF1 and PO. No submodularity assumption is needed. Proof. If |M|≤1|M|≤ 1, the claim is immediate: every allocation is EF1, and assigning the only good, if any, to either agent is PO. Assume henceforth that 2≤|M|≤72≤|M|≤ 7. For either agent i, the empty bundle is EF1-violating. Indeed, for every g∈Mg∈ M, the bundle M∖gM \g\ is nonempty, so strict increase and normalization give vi(M∖g)>vi(∅)=0v_i(M \g\)>v_i( )=0. Thus ℬ(vi)≠∅B(v_i)≠ for i=1,2i=1,2. For each agent i, choose Si∈ℬ(vi)S_i (v_i) with vi(Si)=τ(vi)v_i(S_i)=τ(v_i) and Ti=M∖SiT_i=M S_i. Let i=(vi)U_i=U(v_i) and ℱi=ℱ(Si,Ti)F_i=F(S_i,T_i). By Lemma 4.2, ℱi⊆iF_i _i and |Ti|≥2|T_i|≥ 2. Suppose, for a contradiction, that no allocation gives both agents a bundle in their respective families iU_i. Then 1U_1 and 2U_2 must be cross-intersecting. To see this, suppose R1∈1R_1 _1 and R2∈2R_2 _2 were disjoint. Assign R2R_2 to agent 2 and assign all remaining goods to agent 1. Agent 1 then receives M∖R2⊇R1M R_2 R_1 which belongs to 1U_1 because 1U_1 is closed under supersets. This would be an allocation with both bundles above their thresholds, contrary to the assumption. Hence the subfamilies ℱ1F_1 and ℱ2F_2 are also cross-intersecting. Lemma 4.3 would then imply |M|≥8|M|≥ 8, contradicting |M|≤7|M|≤ 7. Therefore there exists an allocation X=(X1,X2)X=(X_1,X_2) such that vi(Xi)>τ(vi)(i=1,2).v_i(X_i)>τ(v_i) (i=1,2). (12) Neither XiX_i is EF1-violating, so X is EF1. It remains to impose Pareto optimality without crossing either threshold. Among all allocations Z satisfying vi(Zi)≥vi(Xi)v_i(Z_i)≥ v_i(X_i) for all i=1,2i=1,2, choose one, say Y, that is Pareto maximal within this finite collection. If some allocation W Pareto dominated Y, then W would satisfy the same lower bounds and belong to the collection, contradicting the choice of Y. Thus Y is globally PO. Moreover, vi(Yi)≥vi(Xi)>τ(vi)v_i(Y_i)≥ v_i(X_i)>τ(v_i), so neither YiY_i is EF1-violating. Hence Y is also EF1. It remains to impose Pareto optimality without crossing either threshold. Among all allocations Z satisfying vi(Zi)≥vi(Xi)v_i(Z_i)≥ v_i(X_i) for all i=1,2i=1,2, choose an allocation Y maximizing v1(Y1)+v2(Y2)v_1(Y_1)+v_2(Y_2) Such a maximizer exists because there are finitely many allocations. If an allocation W Pareto dominated Y, then W would satisfy the same lower bounds and v1(W1)+v2(W2)>v1(Y1)+v2(Y2)v_1(W_1)+v_2(W_2)>v_1(Y_1)+v_2(Y_2), contradicting the choice of Y. Thus Y is globally PO. Moreover, vi(Yi)≥vi(Xi)>τ(vi)v_i(Y_i)≥ v_i(X_i)>τ(v_i) for i=1,2i=1,2, so neither YiY_i is EF1-violating. Hence Y is also EF1. ∎ Thus, for two agents with strictly increasing valuations, eight is the minimum number of goods in an instance with no allocation that is both EF1 and PO. Moreover, an eight-good counterexample exists with normalized, integer-valued, strictly increasing, submodular valuations, and every EF1 allocation in that instance is strictly Pareto dominated. 5 NP-Hardness with Only Eight Zero-Marginal Agent–Good Pairs We next turn from the exact two-agent threshold to the computational complexity of the three-agent problem. Chandramouleeswaran and Nimbhorkar [10] show that deciding whether an EF1 and PO allocation exists is NP-hard for three agents with monotone submodular valuations. In their reduction, however, one agent assigns zero marginal value to every vertex good, so the number of zero-marginal agent–good pairs grows with the input. We strengthen this result by confining all zero marginals to a fixed, constant-size core. Our reduction uses the eight goods from Section 3 as the core and introduces one vertex good for each vertex of the input graph. Every vertex good has strictly positive marginal value for every agent; the only zero marginals occur for agent 3 on the eight core goods. The core forces the unique split compatible with the relevant EF1 and PO constraints, while the vertex goods encode a balanced vertex cover. Theorem 5.1 (Hardness with only eight zero-marginal pairs). It is NP-hard to decide whether a three-agent instance with normalized, integer-valued, monotone submodular valuations admits an allocation that is both EF1 and PO. This remains true under the following restriction. There is a fixed set C of eight goods such that, for every bundle R⊆MR M and every good g∈M∖Rg∈ M R: (i) if g∈M∖Cg∈ M C, then vi(g∣R)>0v_i(g R)>0 for every agent i; (i) if g∈Cg∈ C, then vi(g∣R)>0v_i(g R)>0 for i∈1,2i∈\1,2\; and (i) if g∈Cg∈ C, then v3(g∣R)=0v_3(g R)=0. Thus the only agent–good pairs with identically zero marginal value are the eight pairs (3,g)(3,g) with g∈Cg∈ C. Proof. We reduce from Balanced Vertex Cover [11, Lemma 1]. An instance is a graph G=(V,E)G=(V,E) with an even number n=|V|n=|V| of vertices, and the question is whether G has a vertex cover of size at most n/2n/2. Conitzer and Sandholm state the problem with a cover of size exactly n/2n/2. The two formulations are equivalent because any cover of size at most n/2n/2 can be enlarged to size exactly n/2n/2. If E=∅E= , the source instance is trivially a yes-instance. We map it to the fixed output obtained by applying the construction to a single-edge graph, which is also a yes-instance. Henceforth, assume m=|E|≥1m=|E|≥ 1. Construction. Let C=A∪˙BC=A ∪B be a disjoint copy of the eight goods from Section 3, with |A|=3|A|=3 and |B|=5|B|=5. For each vertex v∈Vv∈ V, add a good pvp_v. Let P=pv:v∈VP=\p_v:v∈ V\ and M=C∪˙PM=C ∪P. We call the goods in C core goods and those in P vertex goods. For R⊆MR M, define x(R)=|R∩A|x(R)=|R∩ A| and y(R)=|R∩B|y(R)=|R∩ B|. For Q⊆PQ P, let cov(Q)=|u,v∈E:pu∈Q or pv∈Q|cov(Q)=|\\u,v\∈ E:p_u∈ Q or p_v∈ Q\|. Thus cov(Q)cov(Q) is the number of graph edges covered by the vertices represented in Q. Set L=n+2L=n+2. Since m≥1m≥ 1, we will use Lm>nLm>n and 3L>n+13L>n+1. For every R⊆MR M, define w1(R) w_1(R) =L(mu1(x(R),y(R))+3cov(R∩P))+|R∩P|, =L(m\,u_1(x(R),y(R))+3cov(R∩ P))+|R∩ P|, w2(R) w_2(R) =Lmu2(x(R),y(R))+|R∩P|, =Lm\,u_2(x(R),y(R))+|R∩ P|, w3(R) w_3(R) =L|R∩P|. =L|R∩ P|. These are polynomial-size descriptions, and all three values can be computed in polynomial time from G and the fixed tables (1)–(2). Valuation properties. On the core goods, the functions D↦ui(x(D),y(D))D u_i(x(D),y(D)) are normalized, integer-valued, strictly increasing, and submodular by Theorem 3.1. Extending them to M by ignoring vertex goods preserves normalization, integrality, monotonicity, and submodularity. The coverage function covcov is normalized, monotone, and submodular: as the current set grows, a newly added vertex good can cover only fewer previously uncovered edges. The remaining terms are additive. Hence w1,w2,w3w_1,w_2,w_3 are normalized, integer-valued, monotone, and submodular. For a vertex good pvp_v, its marginal value is 3L⋅(number of newly covered edges)+13L·(number of newly covered edges)+1 for agent 1, 11 for agent 2, and L for agent 3. All three are positive. For a core good g∈Cg∈ C, every core marginal in (1)–(2) is at least 11, so whenever g∉Rg∉ R, w1(g∣R)≥Lm,w2(g∣R)≥Lm,w3(g∣R)=0.w_1(g R)≥ Lm, w_2(g R)≥ Lm, w_3(g R)=0. This proves the promised marginal restriction. Two facts about the core. We will use the following two consequences of the fixed tables. (C1) For a core split (x,y)(x,y), agent 1 receives counts (x,y)(x,y) and agent 2 receives (3−x,5−y)(3-x,5-y). Among the 2424 possible count splits, the Pareto-optimal utility pairs are exactly the eight rows below. The last two columns give the core EF1 differences σ1,σ2 _1, _2 defined in the proof of Theorem 3.1; ⋆ denotes an automatic comparison with an empty envied bundle. split (x,y)(u1(x,y),u2(3−x,5−y))σ1(x,y)σ2(x,y)(0,0)(0,56)−55⋆(1,0)(25,55)−2955(1,1)(38,54)−1541(1,2)(47,53)−327(0,5)(53,47)25−3(1,5)(54,32)29−19(2,5)(55,17)55−37(3,5)(56,0)⋆−55 array[]c|c|r|rsplit (x,y)&(u_1(x,y),u_2(3-x,5-y))& _1(x,y)& _2(x,y)\\ (0,0)&(0,56)&-55& \\ (1,0)&(25,55)&-29&55\\ (1,1)&(38,54)&-15&41\\ (1,2)&(47,53)&-3&27\\ (0,5)&(53,47)&25&-3\\ (1,5)&(54,32)&29&-19\\ (2,5)&(55,17)&55&-37\\ (3,5)&(56,0)& &-55 array This is a direct comparison of the constant-size list of utility pairs. (C2) If D1,D2⊆CD_1,D_2 C are disjoint and u1(x(D1),y(D1))≥47,u2(x(D2),y(D2))≥53,u_1(x(D_1),y(D_1))≥ 47, u_2(x(D_2),y(D_2))≥ 53, then D1D_1 has counts (1,2)(1,2), D2D_2 has counts (2,3)(2,3), and D1∪˙D2=CD_1 ∪D_2=C. Indeed, the first inequality implies either x(D1)=0,y(D1)=5x(D_1)=0,y(D_1)=5, or x(D1)≥1,y(D1)≥2x(D_1)≥ 1,y(D_1)≥ 2. The first possibility leaves no B-goods for a disjoint bundle of u2u_2-value at least 5353. In the second possibility, disjointness gives x(D2)≤2x(D_2)≤ 2 and y(D2)≤3y(D_2)≤ 3. The u2u_2-table then forces x(D2)=2,y(D2)=3x(D_2)=2,y(D_2)=3. Disjointness consequently forces x(D1)=1,y(D1)=2x(D_1)=1,y(D_1)=2, and the two bundles exhaust C. At the key split (1,2)(1,2), agent 1’s core EF1 difference is −3-3. After the core values are multiplied by m, this is a deficit of 3m3m, while covering all m edges contributes exactly 3m3m through the coverage term. This is why the coefficient 33 appears in w1w_1. Forward direction. Assume G has a vertex cover K⊆VK V with k=|K|≤n/2k=|K|≤ n/2. Let PK=pv:v∈KP_K=\p_v:v∈ K\. Choose a core bundle C1⊆C_1 C containing one A-good and two B-goods, and let C2=C∖C1C_2=C C_1. Consider the allocation X=(X1,X2,X3)X=(X_1,X_2,X_3) defined by X1=C1∪PK,X2=C2,X3=P∖PK.X_1=C_1∪ P_K, X_2=C_2, X_3=P P_K. Since K covers all m edges, the utilities are w1(X1)=50Lm+k,w2(X2)=53Lm,w3(X3)=L(n−k).w_1(X_1)=50Lm+k, w_2(X_2)=53Lm, w_3(X_3)=L(n-k). We check all six ordered EF1 comparisons. • For agent 1’s comparison with agent 2, deleting any core good from C2C_2 leaves a core bundle of u1u_1-value 5050, so w1(X1)≥50Lm=w1(X2∖g)w_1(X_1)≥ 50Lm=w_1(X_2 \g\). • For agent 2’s comparison with agent 1, delete the unique A-good g∈C1g∈ C_1. Then w2(X1∖g)=26Lm+k<53Lm=w2(X2)w_2(X_1 \g\)=26Lm+k<53Lm=w_2(X_2), where the strict inequality follows from k≤n<Lmk≤ n<Lm. • Since m≥1m≥ 1, every vertex cover is nonempty. Agent 3 can therefore delete a vertex good from PKP_K, after which she values agent 1’s bundle at L(k−1)L(k-1). Her own value satisfies L(n−k)≥L(k−1)L(n-k)≥ L(k-1) because k≤n/2k≤ n/2. The remaining comparisons hold without any deletion: w1(X3)≤3Lm+n<50Lm+kw_1(X_3)≤ 3Lm+n<50Lm+k, w2(X3)≤n<53Lmw_2(X_3)≤ n<53Lm, and w3(X2)=0≤L(n−k)w_3(X_2)=0≤ L(n-k). Thus X is EF1. We next show that X is PO. Suppose an allocation Y Pareto dominates X. To give agent 2 utility at least 53Lm53Lm, the core part of Y2Y_2 must have u2u_2-value at least 5353: with core value at most 5252, even all n vertex goods yield at most 52Lm+n<53Lm52Lm+n<53Lm. Similarly, the core part of Y1Y_1 must have u1u_1-value at least 4747. If its core value were at most 4646, then even full edge coverage and all n vertex goods would give at most L(46m+3m)+n=49Lm+n<50Lm+k.L(46m+3m)+n=49Lm+n<50Lm+k. Core fact (C2) therefore forces Y1∩CY_1∩ C to have counts (1,2)(1,2), Y2∩CY_2∩ C to have counts (2,3)(2,3), and agent 3 to receive no core good. Let Qi′=Yi∩PQ_i =Y_i∩ P and qi′=|Qi′|q_i =|Q_i |. Agent 1 must have full edge coverage in Y. If cov(Q1′)≤m−1cov(Q_1 )≤ m-1, then w1(Y1)≤L(47m+3m−3)+n<50Lm+k,w_1(Y_1)≤ L(47m+3m-3)+n<50Lm+k, where the last inequality follows from 3L>n+13L>n+1 and k≥1k≥ 1. Hence cov(Q1′)=mcov(Q_1 )=m, and agent 1’s utility comparison implies q1′≥kq_1 ≥ k. Agent 3’s comparison implies q3′≥n−kq_3 ≥ n-k. Since the vertex goods are partitioned, q1′+q2′+q3′=nq_1 +q_2 +q_3 =n. It follows that q1′=k,q2′=0,q3′=n−k.q_1 =k, q_2 =0, q_3 =n-k. All three agents then have exactly the same utility in Y as in X, contradicting the requirement that a Pareto domination be strict for at least one agent. Thus X is PO. Reverse direction. Assume the constructed instance has an allocation X=(X1,X2,X3)X=(X_1,X_2,X_3) that is both EF1 and PO. Agent 3 receives no core good. Otherwise, moving one such good from agent 3 to agent 1 would leave agents 2 and 3 unchanged and would strictly improve agent 1, because agent 1 has positive marginal value for every core good. This would contradict PO. Hence agents 1 and 2 partition the core goods. Their core split must be Pareto optimal for u1,u2u_1,u_2; otherwise, changing only the core allocation would Pareto improve the full allocation. By core fact (C1), the split is one of the eight displayed rows. We first eliminate every split listed in (C1) with σ2<0 _2<0. In each such row, σ2≤−3 _2≤-3. For every g∈X1g∈ X_1, the core part of X1∖gX_1 \g\ has u2u_2-value at least three more than agent 2’s own core bundle. For a core good this follows from the definition of σ2 _2; for a vertex good the core bundle is unchanged and hence is no smaller than any one-core-good deletion. The vertex-count terms can reduce the resulting difference by at most n. Therefore w2(X1∖g)−w2(X2)≥3Lm−n>0w_2(X_1 \g\)-w_2(X_2)≥ 3Lm-n>0 for every g∈X1g∈ X_1, so agent 2 cannot satisfy EF1 at any of these rows. At the three splits (0,0),(1,0),(1,1)(0,0),(1,0),(1,1) listed in (C1), agent 1’s core EF1 difference is at most −15-15. For every g∈X2g∈ X_2, the coverage term can increase w1(X1)−w1(X2∖g)w_1(X_1)-w_1(X_2 \g\) by at most 3Lm3Lm, and the vertex-count term can increase it by at most n. Consequently, w1(X1)−w1(X2∖g)≤−15Lm+3Lm+n<0.w_1(X_1)-w_1(X_2 \g\)≤-15Lm+3Lm+n<0. Agent 1 therefore cannot satisfy EF1 at these rows either. The only remaining core split is (1,2)(1,2): agent 1 receives one A-good and two B-goods, and agent 2 receives the other two A-goods and three B-goods. For i∈1,2,3i∈\1,2,3\, define Qi=Xi∩PQ_i=X_i∩ P, qi=|Qi|q_i=|Q_i|, and ci=cov(Qi)c_i=cov(Q_i). Agent 1’s own utility is w1(X1)=L(47m+3c1)+q1w_1(X_1)=L(47m+3c_1)+q_1. For every g∈X2g∈ X_2, w1(X2∖g)≥L(50m+3c2)+q2−1.w_1(X_2 \g\)≥ L(50m+3c_2)+q_2-1. Indeed, if g is a core good, the remaining core bundle has u1u_1-value 5050, while coverage and the vertex count are unchanged. If g is a vertex good, the core value remains 5353, coverage falls by at most m, and the vertex count falls by one; hence 53m+3(c2−m)=50m+3c253m+3(c_2-m)=50m+3c_2. Agent 1’s EF1 condition provides some g∈X2g∈ X_2 such that w1(X1)≥w1(X2∖g)w_1(X_1)≥ w_1(X_2 \g\). Combining the above facts gives us 3L(c1−c2−m)≥q2−q1−1.3L(c_1-c_2-m)≥ q_2-q_1-1. Since c1≤mc_1≤ m and c2≥0c_2≥ 0, unless c1=mc_1=m and c2=0c_2=0, the integer c1−c2−mc_1-c_2-m is at most −1-1. The left-hand side would then be at most −3L-3L, whereas the right-hand side is at least −n−1-n-1. This contradicts 3L>n+13L>n+1. Therefore c1=mc_1=m and c2=0c_2=0. The vertices represented by Q1Q_1 consequently form a vertex cover of G. Finally, agent 3’s EF1 comparison with agent 1 gives q3≥q1−1q_3≥ q_1-1. The set Q1Q_1 is nonempty because it covers a graph with at least one edge. Deleting a vertex good from X1X_1 leaves agent 3 value L(q1−1)L(q_1-1), while deleting a core good leaves value Lq1Lq_1; hence the best deletion for agent 3 is a vertex good. Using q1+q2+q3=nq_1+q_2+q_3=n, we obtain 2q1+q2≤n+12q_1+q_2≤ n+1. Since n is even and q2≥0q_2≥ 0, this implies q1≤n/2q_1≤ n/2. Thus G has a vertex cover of size at most n/2n/2, completing the reduction. ∎ Note that Theorem 5.1 does not establish NP-hardness when all three valuations are strictly increasing, since agent 3 assigns zero marginal value to the eight core goods. Rather, it eliminates all input-dependent zero marginals: every vertex good has positive marginal value for every agent, and the only zero marginals are the eight fixed pairs (3,g)(3,g) with g∈Cg∈ C. In contrast, in the reduction of Chandramouleeswaran and Nimbhorkar [10, Section 5], one agent assigns zero marginal value to every vertex good, so the number of such pairs grows with the graph. 6 Conclusion We determine the exact two-agent threshold for incompatibility between EF1 and PO under strictly increasing valuations. Every instance with at most seven goods admits an allocation satisfying both properties, without any submodularity assumption. In contrast, with eight goods, we construct normalized, integer-valued, strictly increasing, submodular valuations for which every EF1 allocation is strictly Pareto dominated. Thus, strictly positive marginal values do not restore compatibility in general, but they rule out every smaller two-agent counterexample. We also strengthen the three-agent NP-hardness frontier for monotone submodular valuations. In our reduction, every input-dependent vertex good has strictly positive marginal value for every agent, while all zero marginals are confined to one agent on the eight fixed core goods. This leaves two natural directions for future work: whether NP-hardness persists when all three valuations are strictly increasing, and, for three or more agents, the minimum number of goods required for EF1 and PO to be incompatible under strictly increasing valuations. References 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(C), 2023. Aziz et al. [2022] Haris Aziz, Ioannis Caragiannis, Ayumi Igarashi, and Toby Walsh. Fair allocation of indivisible goods and chores. Autonomous Agents and Multi-Agent Systems, 36(3), 2022. Barman and Suzuki [2026] Siddharth Barman and Mashbat Suzuki. Compatibility of fairness and Nash welfare under subadditive valuations. In Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1724–1746, 2026. Barman et al. [2018] Siddharth Barman, Sanath Kumar Krishnamurthy, and Rohit Vaish. Finding fair and efficient allocations. In Proceedings of the 19th ACM Conference on Economics and Computation (EC), pages 557–574, 2018. Benabbou et al. [2021] Nawal Benabbou, Mithun Chakraborty, Ayumi Igarashi, and Yair Zick. Finding fair and efficient allocations for matroid rank valuations. ACM Transactions on Economics and Computation, 9:1–41, 2021. Bhaskar et al. [2021] Umang Bhaskar, A. R. Sricharan, and Rohit Vaish. On approximate envy-freeness for indivisible chores and mixed resources. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM), pages 1:1–1:23, 2021. Brandl et al. [2026] Florian Brandl, Warut Suksompong, and Nicholas Teh. Fair division with binary valuations: Characterizations. In Proceedings of the 19th International Symposium on Algorithmic Game Theory (SAGT), 2026. Extended version available at arXiv:2607.10064. 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):12:1–12:32, 2019. Chandramouleeswaran and Nimbhorkar [2026] Harish Chandramouleeswaran and Prajakta Nimbhorkar. Nonexistence of simultaneously EF1 and pareto optimal allocations for submodular valuations. arXiv preprint arXiv:2607.18220, 2026. Conitzer and Sandholm [2006] Vincent Conitzer and Tuomas Sandholm. Computing the optimal strategy to commit to. In Proceedings of the 7th ACM Conference on Electronic Commerce (EC), pages 82–90, 2006. Hosseini et al. [2025] Hadi Hosseini, Shivika Narang, and Tomasz Wąs. Fair distribution of delivery orders. Artificial Intelligence, 347:104389, 2025. Lim et al. [2026] Eugene Lim, Tzeh Yuan Neoh, and Nicholas Teh. The cost of EFX: Generalized-mean welfare and complexity dichotomies with few surplus items. arXiv preprint arXiv:2601.12849, 2026. 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. When one good is not enough: EF1 and pareto optimality are not compatible for submodular valuations. arXiv preprint arXiv:2607.17811, 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. Teh [2026] Nicholas Teh. Computing fair and efficient indivisible chore allocations with bounded surplus. In Proceedings of the 19th International Symposium on Algorithmic Game Theory (SAGT), 2026. Appendix A Marginal Arrays for the Eight-Good Instance For rows indexed by x and columns indexed by y, the A-marginal arrays are ΔAu1012345x=02525211171x=1333311x=2111111ΔAu2012345x=0171513733x=115117711x=215117111. array[]c|r _Au_1&0&1&2&3&4&5\\ x=0&25&25&21&11&7&1\\ x=1&3&3&3&3&1&1\\ x=2&1&1&1&1&1&1 array array[]c|r _Au_2&0&1&2&3&4&5\\ x=0&17&15&13&7&3&3\\ x=1&15&11&7&7&1&1\\ x=2&15&11&7&1&1&1 array. (13) The B-marginal arrays are ΔBu101234x=013131377x=1139331x=2139311x=3139311ΔBu201234x=0131313111x=11111771x=277711x=333111. array[]c|r _Bu_1&0&1&2&3&4\\ x=0&13&13&13&7&7\\ x=1&13&9&3&3&1\\ x=2&13&9&3&1&1\\ x=3&13&9&3&1&1 array array[]c|r _Bu_2&0&1&2&3&4\\ x=0&13&13&13&11&1\\ x=1&11&11&7&7&1\\ x=2&7&7&7&1&1\\ x=3&3&3&1&1&1 array. (14) Every entry is positive. Within each array, every row and every column is nonincreasing, verifying the hypotheses of Lemma 3.2. Appendix B EF1 Comparison Differences Recall that d1(x,y)d_1(x,y) is the minimum value, according to agent 1, of agent 2’s bundle after one feasible deletion, and d2(x,y)d_2(x,y) is defined symmetrically for agent 2. For nonautomatic comparisons, σ1(x,y)=u1(x,y)−d1(x,y),σ2(x,y)=u2(3−x,5−y)−d2(x,y). _1(x,y)=u_1(x,y)-d_1(x,y), _2(x,y)=u_2(3-x,5-y)-d_2(x,y). Denote ⋆ when the comparison is automatic because the envied bundle is empty. Then σ1y=0y=1y=2y=3y=4y=5x=0−55−41−25−31725x=1−29−15−392529x=2−25−511274155x=3−173254155⋆ array[]c|r _1&y=0&y=1&y=2&y=3&y=4&y=5\\ x=0&-55&-41&-25&-3&17&25\\ x=1&-29&-15&-3&9&25&29\\ x=2&-25&-5&11&27&41&55\\ x=3&-17&3&25&41&55& array (15) and σ2y=0y=1y=2y=3y=4y=5x=0⋆55412711−3x=15541277−7−19x=237257−7−25−37x=31911−7−27−41−55. array[]c|r _2&y=0&y=1&y=2&y=3&y=4&y=5\\ x=0& &55&41&27&11&-3\\ x=1&55&41&27&7&-7&-19\\ x=2&37&25&7&-7&-25&-37\\ x=3&19&11&-7&-27&-41&-55 array. (16) The pairs (x,y)(x,y) for which both relevant differences are nonnegative are exactly the four splits in (6).