Paper deep dive
Settling the Computational Complexity of Max-Min Allocation with Ternary Valuations
Thi Ngoc Anh Vu, Trung Thanh Nguyen, Khaled Elbassioni, Jörg Rothe
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 the problem of computing an allocation of indivisible items that maximizes egalitarian welfare, i.e., the utility of the worst-off agent, when agents' item values or marginal values belong to a small set. For additive valuations with values in $\{p,q\}$, where $q>p>0$ and $\gcd(p,q)=1$, we give a polynomial-time algorithm when $p=2$ and prove constant-gap hardness when $p\geq3$, already with exactly three high-valued goods per agent. We also give an $\sqrt{3/2}$-approximation for common positive bi-valued additive valuations. For mixed additive valuations in $\{-p,0,c\}$, where $p\in\{1,2\}$ and $c$ is a positive integer, a reduction to maximum-weight perfect matching resolves the conjectured tractability of $\{-2,0,c\}$-valuations. For submodular valuations with marginals in $\{-2,0,c\}$, where $c$ is odd, we establish an exact unit-gap hardness result and exponential value-query lower bounds, even when all but one agent are additive. Finally, for $\{-1,0,1\}$-submodular valuations, we prove that no finite multiplicative approximation exists unless $\p=\np$. Together, our results resolve open questions and provide a complete picture of the computational complexity of max-min allocation with ternary valuations.
Tags
Links
- Source: https://arxiv.org/abs/2610.05237v1
- Canonical: https://arxiv.org/abs/2610.05237v1
Trouble viewing inline? Open PDF directly →
Full Text
91,661 characters extracted from source content.
Expand or collapse full text
Settling the Computational Complexity of Max-Min Allocation with Ternary Valuations Thi Ngoc Anh Vu †thanks: Faculty of Computer Science, Phenikaa University, Hanoi 12116, Vietnam Trung Thanh Nguyen †thanks: DataOptLab, National Economics University, Hanoi 11616, Vietnam Khaled Elbassioni †thanks: Khalifa University of Science and Technology, Abu Dhabi 127788, UAE Jörg Rothe †thanks: Institut für Informatik, MNF, Heinrich-Heine-Universität Düsseldorf, 40225, Düsseldorf, Germany October 4, 2026 Abstract We study the problem of computing an allocation of indivisible items that maximizes egalitarian welfare, i.e., the utility of the worst-off agent, when agents’ item values or marginal values belong to a small set. For additive valuations with values in p,q\p,q\, where q>p>0q>p>0 and gcd(p,q)=1 (p,q)=1, we give a polynomial-time algorithm when p=2p=2 and prove constant-gap hardness when p≥3p≥ 3, already with exactly three high-valued goods per agent. We also give an 3/2 3/2-approximation for common positive bi-valued additive valuations. For mixed additive valuations in −p,0,c\-p,0,c\, where p∈1,2p∈\1,2\ and c is a positive integer, a reduction to maximum-weight perfect matching resolves the conjectured tractability of −2,0,c\-2,0,c\-valuations. For submodular valuations with marginals in −2,0,c\-2,0,c\, where c is odd, we establish an exact unit-gap hardness result and exponential value-query lower bounds, even when all but one agent are additive. Finally, for −1,0,1\-1,0,1\-submodular valuations, we prove that no finite multiplicative approximation exists unless P=NPP=NP. Together, our results resolve open questions and provide a complete picture of the computational complexity of max-min allocation with ternary valuations. 1 Introduction In the fair division of indivisible items, the goal is to allocate a set of m indivisible resources (also referred to as goods with nonnegative value, or chores with nonpositive value) among n agents with heterogeneous preferences, typically represented by valuation functions Brandt et al. (2016b); Lang and Rothe (2024). Dating back to the work of Steinhaus (1948), fair division has become a central topic at the intersection of economics and computer science (Brandt et al., 2016a; Lang and Rothe, 2024), motivated by a wide range of applications. One of the fundamental welfare objectives studied in fair division is egalitarian welfare (Sen, 2017), which evaluates an allocation by the utility of its worst-off agent. Thus, maximizing egalitarian welfare ( MEW) seeks an allocation that maximizes the minimum utility across all agents and can be viewed as the natural computational counterpart of the Rawlsian maximin principle. This objective arises naturally in applications where protecting the least well-off participant is a primary concern, such as the allocation of public resources, computing resources, scheduling, and humanitarian aid. Egalitarian welfare has several features that make it particularly important for our purposes. First, it directly provides a guarantee to the worst-off agent, making it a natural objective in settings involving the allocation of essential resources or burdens (Moulin, 2004). Second, unlike Nash welfare, which is based on the product of individual utilities (Nash, 1950), egalitarian welfare remains meaningful for mixed manna and chores, where utilities may be negative and the product of utilities generally lacks a meaningful welfare interpretation. Third, egalitarian welfare is closely connected to other fundamental fairness notions. In particular, the maximin share of an agent is precisely the optimal egalitarian welfare obtained when partitioning the items among identical copies of that agent (Budish, 2011). Unfortunately, MEW is computationally hard in general, even for additive valuations over goods Bezáková and Dani (2005). This motivates the search for structured valuation classes under which the problem can be solved exactly or approximated efficiently. One fruitful approach to identifying the sources of computational hardness in fair division is to restrict the set of values that an agent may assign to individual items. In binary instances, each item has value 00 or 11 to each agent. Under this restriction MEW becomes polynomial-time solvable (Golovin, 2005). Related tractability results extend even to submodular valuations induced by matroid-rank functions (Babaioff et al., 2021; Viswanathan and Zick, 2023). Bi-valued instances, in which item values belong to a,b\a,b\, and ternary (or tri-valued) instances, in which they belong to a,b,c\a,b,c\, constitute natural extensions of the binary setting. On the practical side, such restricted value domains are appealing for several reasons. First, they capture coarse preference elicitation, in which agents report only a small number of preference levels—for example, whether they like, are indifferent to, or dislike an item, as naturally represented by −1,0,1\-1,0,1\-valuations and their weighted variants. Second, despite their seemingly simple structure, small value sets can already capture much of the computational difficulty of unrestricted instances, while particular choices of values may still admit efficient exact algorithms. They therefore provide a useful framework for isolating the arithmetic and combinatorial features responsible for computational hardness. A systematic classification for small value sets can pinpoint the boundary between polynomial-time solvability and computational hardness and thereby provide a finer-grained picture of the computational landscape of fair division. Motivated by this question, in this work we study the complexity of MEW for bi-valued and ternary instances, with both additive and submodular valuations. 1.1 Related work For general additive valuations over goods, MEW can be approximated within a factor of O(mε)O(m ) (Chakrabarty et al., 2009) for every fixed ε>0 >0, but is NPNP-hard to approximate within any factor smaller than 22, even when item values in 0,1,2\0,1,2\ (Bezáková and Dani, 2005; Golovin, 2005). Chakrabarty et al. (2009) gave an O(mε)O(m )-approximation in polynomial time, where m is the number of items. This gap has remained open for decades. For restricted instances (a.k.a Santa Claus problem), where the value of any item j is either 00 or pjp_j, constant-factor polynomial-time algorithms are known (Annamalai et al., 2017; Cheng and Mao, 2018; Davies et al., 2020). For more restricted case with binary and, more generally, matroid-rank valuations, MEW can be solved in polynomial time (Golovin, 2005; Halpern et al., 2020b; Babaioff et al., 2021; Viswanathan and Zick, 2023). For bi-valued goods with values 1,c\1,c\, where c is a positive integer, this remains true for submodular valuations (Cousins et al., 2023a). In tri-valued setting, Golovin (2005) studied the special case called “Big Goods/Small Goods”, where the small goods have value 00 or 11 to an agent and the big goods have value 00 or x>1x>1, and gave a O(n)O( n)-approximation. Chan et al. (2016) considered a different two-value restriction: each item has a common heavy or light value, but an agent may value it at zero. They presented a quasi-polynomial-time (3+4ε)(3+4 )-approximation when the two nonzero item values are 11 and ε . Khot and Ponnuswami (2007) generalized this setting, in which good values are in 0,1,c\0,1,c\ for any c>1c>1, and obtained an nα nα-approximation algorithm with mO(1)nO(α)m^O(1)n^O(α) running time, for any α≤n2α≤ n2. Fitzsimmons et al. (2025) established constant-gap hardness for every ternary set of distinct nonnegative values. For additive chores, MEW corresponds to makespan minimization on unrelated machines; the bi-valued case is polynomial when one cost is twice the other, with hardness outside this ratio (Lenstra et al., 1990; Chakrabarty et al., 2015). For mixtures of goods and chores, Cousins et al. (2023b) gave a polynomial-time algorithm for computing leximin allocations, and hence for solving MEW, under −1,0,c\-1,0,c\-valuations with a common positive integer c. Their algorithm further extends to order-neutral submodular valuations. They also established hardness for additive −p,c\-p,c\-valuations when p≥3p≥ 3 and c are coprime. Subsequently, Fitzsimmons et al. (2025) investigated the remaining ternary cases, showing that every −1,0,c\-1,0,c\-submodular valuation with c≥2c≥ 2 is order-neutral and establishing hardness for −1,0,1\-1,0,1\-submodular valuations. In particular, they conjectured that MEW is polynomial-time solvable for additive −2,0,c\-2,0,c\-valuations and left open the complexity of the problem for submodular −2,0,c\-2,0,c\-valuations. For other fair division problems with few utility values, we refer to (Bliem et al., 2016; Barman et al., 2018; Halpern et al., 2020a; Akrami et al., 2022; Cousins et al., 2023a; Bismuth et al., 2024; Akrami et al., 2025; Fitzsimmons et al., 2025; Jin and Tao, 2026; Garg and Murhekar, 2023; Amanatidis et al., 2021; Amanatidis et al., 2023; Aziz et al., 2019) and the references therein for the state-of-the-art results. 1.2 Our contributions Our results resolve open questions and provide a complete picture of the computational complexity of max-min allocation with ternary valuations. Table 1 summarizes the resulting compltete picture. 1. For additive valuations with values in 2,q\2,q\, with q≥3q≥ 3, we give a polynomial-time algorithm, complementing the known algorithm for p=1p=1. For each fixed p≥3p≥ 3, we prove an explicit constant approximation gap, even when every agent values exactly three goods highly, and present a 3/2 3/2-approximation algorithm. 2. For mixed additive valuations in −p,0,c\-p,0,c\, with p∈1,2p∈\1,2\ and c≥1c≥ 1, we show a polynomial time reduction to maximum-weight perfect matching, yielding a polynomial-time algorithm. 3. For every fixed odd c≥1c≥ 1, we prove a strongly NPNP-hardness result for −2,0,c\-2,0,c\-submodular valuations, even when all but one agent are additive. 4. For −1,0,1\-1,0,1\-submodular valuations, we show the nonexistence of approximation algorithm with any finite approximation factor, unless P=NPP=NP. Among others, our results (2) and (3) answer affirmatively the open question posed in Cousins et al. (2023b), while result (4) strengthens the NPNP-hardness result of the same paper by establishing a stronger inapproximability bound. Valuations Additive Submodular 0,c\0,c\, c≥1c≥ 1 P (Golovin, 2005) P (Babaioff et al., 2021; Viswanathan and Zick, 2023) 1,c\1,c\, c≥1c≥ 1 P (Cousins et al., 2023a) P (Cousins et al., 2023a) 2,c\2,c\, odd c≥3c≥ 3 P (Thm. 1) Open p,q\p,q\, 0<p<q0<p<q 32 32-appr. (Thm. 3) No PTAS (Thm. 2) 0,1,c\0,1,c\, c≥2c≥ 2 No (2+ϵ)(2+ε)-appr. Chan et al. (2016) No (2+ϵ)(2+ε)-appr. p,q,r\p,q,r\, NPNP-hard Cousins et al. (2023b) NPNP-hard −1,0,c\-1,0,c\, c≥2c≥ 2 P (Cousins et al., 2023b) P (Cousins et al., 2023b; Fitzsimmons et al., 2025) −1,0,1\-1,0,1\ P (Cousins et al., 2023b) No appr. (Thm. 6) −2,0,c\-2,0,c\, even c≥4c≥ 4 P (Cousins et al., 2023b) P (Cousins et al., 2023b; Fitzsimmons et al., 2025) −2,0,2\-2,0,2\ P (Cousins et al., 2023b) No approx. (Thm. 6) −2,0,c\-2,0,c\, odd c P (Thm. 4) No FPTAS (Thm. 5) −p,0,c\-p,0,c\ NP-hard (Cousins et al., 2023b) NP-hard (Cousins et al., 2023b) Table 1: Complexity of MEW with ternary valuations. Our new results are highlighted in bold. 2 Preliminaries Let N be a set of n agents and M a set of m indivisible items. Each agent i∈Ni∈ N is endowed with a valuation function vi:2M→ℚv_i:2^M , which assigns a rational value to every subset of items. We assume that vi(∅)=0v_i( )=0 for every i∈Ni∈ N. An allocation A=(A1,…,An)A=(A_1,…,A_n) is a partition of M into n pairwise disjoint bundles, where AiA_i denotes the bundle allocated to agent i. The egalitarian welfare (EWEW) of an allocation A is defined as EW(A)=mini∈Nvi(Ai).EW(A)= _i∈ Nv_i(A_i). We study the problem of finding an allocation that maximizes the egalitarian welfare, which we refer to as the Maximum Egalitarian Welfare ( MEW) problem. Denote by OPT the optimal value of MEW. For t∈ℤ≥0t _≥ 0, we write [t][t] for 1,…,t\1,…,t\. Definition 1 (A-submodular). Given a set of integers ⊆ℤA , a valuation function v is A-submodular if: (a) for any o∈Mo∈ M and S⊆T⊆M∖oS T M \o\, v(S∪o)−v(S)≥v(T∪o)−v(T)v(S∪\o\)-v(S)≥ v(T∪\o\)-v(T); (b) for any o∈Mo∈ M and S⊆M∖oS M \o\, v(S∪o)−v(S)∈v(S∪\o\)-v(S) In simple words, the valuation function is submodular, and the marginal gains are restricted to values in A. A special case is when v(S)=∑o∈Sv(o)v(S)= _o∈ Sv(o) for every S⊆MS M, which we call A-additive valuation. We also consider a class of special A-submodular valuations, called conflict-pair valuations, which is formally defined as follows. Definition 2 (Conflict-pair valuations). A valuation viv_i is a conflict-pair valuation if vi(o)∈−1,0,1v_i(o)∈\-1,0,1\ for all items o and there is a set Πi _i of pairwise disjoint pairs (x,y)(x,y) with vi(x)=1v_i(x)=1 and vi(y)=0v_i(y)=0, such that vi(S)=∑o∈Svi(o)−|(x,y)∈Πi:x,y∈S|,v_i(S)= _o∈ Sv_i(o)\;-\; |\(x,y)∈ _i:x,y∈ S\ |, for every non-empty subset S⊆MS M. In words, viv_i is additive except that holding both items of a conflict pair costs one unit: the good x and the item y, which is harmless on its own, cannot both be enjoyed. Since the pairs are disjoint, viv_i is a sum of functions on disjoint sets of items, each of which is either a single item or the gadget on one pair; hence viv_i is submodular and all its marginal values lie in −1,0,1\-1,0,1\. A formal proof and an example of the valuation can be found in Appendix. Lemma 1. Every conflict-pair valuation viv_i is −1,0,1\-1,0,1\-submodular. Definition 3 (Order-neutrality). A submodular valuation is order-neutral if, for every bundle S, the multiset of marginal gains obtained by adding the items of S is the same for every ordering of those items. For submodular valuations, we assume the standard value-oracle model, in which each query specifies an agent and a bundle of items and returns the agent’s value for that bundle. In Section 5, we use matroid rank functions and their standard properties; we refer the reader to Oxley (2011) for further background. Definition 4 (Approximation algorithm). For a maximization problem with nonnegative optimum, a factor-ρ approximation, ρ≥1ρ≥ 1, returns an allocation with welfare at least /ρ OPT/ρ. A PTAS achieves a factor 1+ε1+ in polynomial time for each fixed ε>0 >0; an FPTAS runs in time polynomial also in 1/ε1/ . Our multiplicative impossibility statements for mixed manna are proved on explicit nonnegative- or positive-optimum promise classes. An additive error δ≥0δ≥ 0 means returning an allocation A with EW(A)≥−δEW(A)≥ OPT-δ. A constant approximation gap rules out a PTAS unless P=NPP=NP. Consider the decision version of MEW: given an integer threshold T, the goal is to either find an allocation whose egalitarian welfare is at least T, or correctly determine that no such allocation exists. If this decision problem can be solved in polynomial time, then an optimal allocation for MEW can be computed in polynomial time by performing a binary search over the range of possible values of T. Consequently, throughout the following sections, to establish the polynomial-time solvability of MEW, it suffices to provide a polynomial-time algorithm for the decision version. 3 Bi-valued valuations In this section we assume that each agent i has a p,q\p,q\-additive valuation with q>p>0q>p>0. 3.1 A polynomial-time algorithm for p=2p=2 We consider the case when p=2p=2 and q≥3q≥ 3 is odd. Let q=2s+1,s≥1q=2s+1,\ s≥ 1. For agent i, let Hi=g∈M:vi(g)=qH_i=\g∈ M:v_i(g)=q\ be the set of goods for which i values high; all other goods are low for i. Theorem 1. For every odd q≥3q≥ 3, MEW under 2,q\2,q\-additive valuations can be solved exactly in time polynomial in n and m. To prove the theorem, it suffices to fix an integer target T≥0T≥ 0 and show that one can determine in polynomial time whether there exists an allocation with value at least T and, if so, construct such an allocation. Our main idea is to reduce this problem to computing a maximum-weight matching in an appropriately constructed graph; the details of the reduction are presented in the following sections. Since the case T=0T=0 is trivial, we henceforth assume that T≥1T≥ 1. Let K=⌈T/q⌉K= T/q , which is the minimum number of high-valued goods that, by themselves, suffice for any agent to attain value at least T. 3.1.1 Feasibility via cost function Definition 5. A high assignment is a set X of pairs (g,i)(g,i) with g∈Hig∈ H_i in which every good appears at most once. We write ki(X)k_i(X), or simply kik_i, for the number of pairs in X involving agent i. Define the cost function Φ(k)=k+⌈12(T−qk)+⌉,(k∈ℕ), (k)=k+ 12(T-qk)^+ ,~(k ), where a+=max(a,0)a^+= (a,0). It is the minimum number of goods an agent needs to reach utility T when exactly k of its goods are high: the k high goods give a value of qkqk, and each further good gives a value of at least 22. One can check that Φ(k)≥Φ(K)=K (k)≥ (K)=K for all k≥Kk≥ K. Lemma 2 (Characterization). ≥T OPT≥ T if and only if there is a high assignment X with ∑i∈NΦ(ki)≤m _i∈ N (k_i)≤ m. Given such an X, an allocation A with EW(A)≥TEW(A)≥ T can be constructed in linear time. Proof. (⇐ ) Give each agent i the kik_i (high) goods assigned to it by X, together with ⌈(T−qki)+/2⌉ (T-qk_i)^+/2 further goods not used by X; the inequality ensures enough such goods exist. The remaining goods (if exist) can be distributed arbitrarily. Every agent i values each further good at least 22, so it receives a value of at least qki+(T−qki)+≥Tqk_i+(T-qk_i)^+≥ T. (⇒ ) Suppose that there is an optimal allocation A with =EW(A)≥T OPT=EW(A)≥ T. Define the set X:=(g,i):g∈Ai∩Hi,i∈NX:=\(g,i):g∈ A_i∩ H_i,i∈ N\, a high assignment with ki=|Ai∩Hi|k_i=|A_i∩ H_i|. Agent i values the other |Ai|−ki|A_i|-k_i goods of AiA_i at exactly 22, so qki+2(|Ai|−ki)≥Tqk_i+2(|A_i|-k_i)≥ T. As |Ai|−ki|A_i|-k_i is a nonnegative integer, |Ai|−ki≥⌈(T−qki)+/2⌉|A_i|-k_i≥ (T-qk_i)^+/2 , i.e. |Ai|≥Φ(ki)|A_i|≥ (k_i). Therefore, ∑i∈NΦ(ki)≤∑i∈N|Ai|=m _i∈ N (k_i)≤ _i∈ N|A_i|=m. Finally, given X, one can construct an allocation A with EW(A)≥TEW(A)≥ T in linear time. ∎ Based on Lemma 2 our problem of computing an allocation of target T is reduced to checking if C=min∑i∈NΦ(ki(X))|X is a high assignment≤m.C\;=\; \ \Σ_i∈ N (k_i(X) )~|~X is a high assignment \≤ m. (1) Intuitively, C represents the minimum total number of goods required to ensure that every agent attains utility at least T. In what follows, we show that C can be computed in polynomial time by reducing its computation to a maximum-weight matching problem in an appropriately constructed weighted graph. This, together with the preceding arguments, completes the proof of Theorem 1. 3.1.2 Saving and the slot decomposition For 0≤k≤K0≤ k≤ K and for j∈[K]j∈[K], define • the saving σ(k):=Φ(0)−Φ(k)σ(k):= (0)- (k), which is the number of goods an agent saves by having k of its goods be high-valued rather than none. • the marginal saving of the j-th high-valued good μj:=Φ(j−1)−Φ(j) _j:= (j-1)- (j), i.e., how many fewer goods the agent needs to reach T when one more of its goods is high-valued. By telescoping, σ(k)=∑j=1kμjσ(k)= _j=1^k _j. We now represent the saving function σ by a collection of slots, which will become the vertices of a matching instance in Section 3.1.3. Definition 6 (Slots). A single slot has a weight w≥0w≥ 0 and holds at most one good. A pair slot holds at most two goods; its value is 00, s−1s-1 or 2s−12s-1 when it holds 00, 11 or 22 goods, respectively. A filling of a collection of slots with k goods places the k goods into the slots within these capacities. The value of a filling is the total weight of the filled single slots plus the values of the pair slots. The decomposition S. Parse μ1,…,μK∈s−1;s _1,…, _K∈\s-1;s\ from left to right. If the next two unparsed terms are (s−1,s)(s-1,s), turn them into a pair slot; otherwise turn the next term μj _j into a single slot of weight μj _j. The resulting ordered list of slots is S; it has total capacity K and does not depend on the agent. Let P be its number of pair slots. Lemma 3 below gives the form of the decomposition, which can be easily to check. Lemma 3. If K≥2K≥ 2, then S consists of, in order: (i) a lead single slot of weight s if T is odd, and none if T is even; (i) P pair slots (possibly empty); (i) at most two tail single slots, each of weight at most s−1s-1, in nonincreasing order of weight. We will use the following result in our analysis of the computation of a maximum-weight matching in the graph. Lemma 4. For every 0≤k≤K0≤ k≤ K, the maximum value of a filling of S with k goods equals σ(k)σ(k). Example 1. Let q=5q=5 (so s=2s=2) and T=17T=17. Then K=⌈17/5⌉=4K= 17/5 =4 and (Φ(0),Φ(1),Φ(2),Φ(3),Φ(4))=(9,7,6,4,4) ( (0), (1), (2), (3), (4) )=(9,7,6,4,4), (μ1,μ2,μ3,μ4)=(2,1,2,0)( _1, _2, _3, _4)=(2,1,2,0). Here T is odd, so μ1=s=2 _1=s=2 becomes the lead single slot; the block (μ2,μ3)=(s−1,s)=(1,2)( _2, _3)=(s-1,s)=(1,2) becomes a pair slot; and μ4=0<ν4=1 _4=0< _4=1 is truncated, because three high goods (value 1515) plus one low good (value 22) already reach 1717, and becomes a tail single slot of weight 00. Thus P=1P=1 and S consists of a lead slot, one pair slot and one tail slot (Figure 1). The maximum filling values for k=0,…,4k=0,…,4 are 0,2,3,5,50,2,3,5,5, which equal σ(k)σ(k): one good goes to the lead slot; two goods give either lead plus half a pair or a full pair, both worth 33; three goods fill the lead and the pair; the fourth good adds nothing. j=1j=1j=2j=2j=3j=3j=4j=4μj _j22112200truncatedslots Slead singleweight s=2s=2pair slotvalues 0, 1, 30,\,1,\,3tail singleweight 00 Figure 1: The decomposition S for q=5q=5 (s=2s=2) and T=17T=17, so K=4K=4. Since T is odd, μ1=s _1=s becomes the lead single slot; the block (μ2,μ3)=(s−1,s)( _2, _3)=(s-1,s) becomes a pair slot; and the truncated last term μ4=0 _4=0 becomes a tail single slot. 3.1.3 Reduction to maximum-weight matching Build an undirected graph G with edge weights as follows. • There is a good vertex g for every good g∈Mg∈ M. • There is a vertex u for every pair of agent i and single slot of weight w in S; create an edge (u,g)(u,g) of weight w for every g∈Hig∈ H_i. • There are two vertices u,u′u,u joined by an edge of weight 11 for every pair of agent i and pair slot in S; join and each of u,u′u,u to every g∈Hig∈ H_i by an edge of weight s. This is done for every i. Claim 1. The constructed graph G has at most m+2nK≤m+2nm+2nK≤ m+2nm vertices and O(nm2)O(nm^2) edges. See Figure 2 for an illustration of the graph construction. It is observed that goods are adjacent only to slot vertices, and slot vertices of different slots are never adjacent, so every edge of a matching is either an internal edge (u,u′)(u,u ) of a pair slot or joins a good to a slot vertex of some agent. g1g_1g2g_2g3g_3g4g_4ℓ1 _1u1u_1u1′u_1 t1t_1ℓ2 _2u2u_2u2′u_2 t2t_22222220022222200222222002222220022222200222222001111 agent 11 agent 22 goodsleadpairtailleadpairtaillead: weight sspair: weight sstail: weight 00 Figure 2: The graph G for q=5q=5, T=17T=17 (decomposition of Figure 1) on an instance with n=2n=2 agents and m=4m=4 goods, where H1=g1,g2,g3H_1=\g_1,g_2,g_3\ and H2=g2,g3,g4H_2=\g_2,g_3,g_4\. Each agent receives its own copy of the slot vertices: a lead vertex ℓi _i, pair vertices ui,ui′u_i,u_i joined by an internal edge of weight 11, and a tail vertex tit_i; these are joined only to the goods in HiH_i, with weights s=2s=2, s=2s=2 and 00, respectively. The good vertices are shared, so a matching assigns each good to at most one agent; g2g_2 and g3g_3 are wanted by both agents. Relative to the baseline 11 of the internal edge, a pair slot contributes 00, s−1=1s-1=1 or 2s−1=32s-1=3 with 00, 11 or 22 goods. Lemma 5. The maximum weight of a matching in G equals ω=nP+max∑i∈NX high assignmentσ(minki(X),K).ω\;=\;nP+ _X high assignment\ Σ_i∈ Nσ ( \k_i(X),K\ ). Proof. (≤) Let Y be a matching. For each agent i, the goods matched to i’s slot vertices lie in HiH_i, are distinct, and are distinct across agents; together they form a high assignment X, with ki′=ki(X)≤Kk_i =k_i(X)≤ K goods for agent i since the slots have total capacity K. The weight of Y splits over agents. A single slot of weight w contributes w if its vertex is matched to a good and 00 otherwise. A pair slot contributes at most 11 if neither vertex is matched to a good (only the internal edge can be used), s=1+(s−1)s=1+(s-1) if exactly one is, and 2s=1+(2s−1)2s=1+(2s-1) if both are. Hence agent i contributes at most P plus the value of a filling of S with ki′k_i goods, which by Lemma 4 is at most σ(ki′)=σ(minki′,K)σ(k_i )=σ( \k_i ,K\). Summing over agents gives the inequality. (≥) Let X be any high assignment. For each agent i, keep min(ki,K) (k_i,K) of its assigned goods and place them into the vertices of i’s slots in parse order; for every pair slot of i that receives no good, add its internal edge. This is a matching, and by Lemma 3 agent i contributes exactly P+σ(minki,K)P+σ( \k_i,K\). ∎ Lemma 6. C=nΦ(0)−(ω−nP)C=n\, (0)-(ω-nP), where C is defined in (1). Proof. Removing assigned goods from an agent keeps a high assignment. By definition of Φ , trimming every agent to at most K assigned goods does not increase ∑iΦ(ki) _i (k_i), so the minimum in (1) is attained with all ki≤Kk_i≤ K. In fact, Φ(ki)=Φ(minki,K) (k_i)= ( \k_i,K\) for all i. Taking Φ(ki)=Φ(0)−σ(ki) (k_i)= (0)-σ(k_i) into account, we have that C=nΦ(0)−max∑i∈NX high assignmentσ(minki(X),K), C=n\, (0)- _X high assignmentΣ_i∈ Nσ ( \k_i(X),K\ ), which is equal to nΦ(0)−(ω−nP)n (0)-(ω-nP) by Lemma 5. ∎ Note that the graph G has at most m+2nm+2nm vertices and O(nm2)O(nm^2) edges. Therefore, a maximum-weight matching in G can be computed in time polynomial in n and m (Lovász and Plummer, 1986). Consequently, both ω and C can also be computed in polynomial time. 3.2 Approximability of the case p≥3p≥ 3 In this section, we consider p,q\p,q\-additive valuations with q>p>3q>p>3. We first show that MEW is APX-hard in this setting, by using a reduction from p-dimensional matching (p-DM), which is NPNP-complete for p≥3p≥ 3 (Garey and Johnson, 1979), and defined as follows. Definition 7 (p-DM). Given disjoint sets V1,…,VpV_1,…,V_p, each of size n′n , and a set E⊆V1×⋯×VpE V_1×…× V_p of hyperedges, decide whether there are n′n pairwise disjoint hyperedges in E (a perfect matching). Theorem 2 (Inapproximability). For all coprime integers q>p≥3q>p≥ 3, it is NPNP-hard to approximate the maximum egalitarian welfare with values in p,q\p,q\ within any factor ρ<pq/(pq−1)ρ<pq/(pq-1). Proof. Given a p-DM instance ℐI with |E|=m′|E|=m hyperedges, build the following MEW instance J. • Agents: one agent iei_e for each hyperedge e∈Ee∈ E; so n=m′n=m . • Goods: one vertex good gvg_v for each vertex v∈V1∪⋯∪Vpv∈ V_1∪…∪ V_p, and q(m′−n′)q(m -n ) dummy goods. • Values: vie(gv)=qv_i_e(g_v)=q if v∈ev∈ e; every other value is p. This instance J has good values in p,q\p,q\, and its size is polynomial. Let OPT be its optimal value. It suffices to prove that if ℐI has a perfect matching then =pq OPT=pq; otherwise ≤pq−1 OPT≤ pq-1. Suppose that ℐI has a perfect matching F⊆EF E. Give each agent iei_e with e∈Fe∈ F its p incident vertex goods, worth pqpq to it. The pn′pn vertex goods are thereby all allocated. Give each of the remaining m′−n′m -n agents q dummy goods, worth pqpq. This uses all q(m′−n′)q(m -n ) dummies, and every agent has utility exactly pqpq, so ≥pq OPT≥ pq. The upper bound ≤pq OPT≤ pq follows from the averaging argument below. Every vertex good is worth at most q to anyone and every dummy is worth p to everyone. Hence for every allocation A, ∑i∈Nvi(Ai)≤pn′⋅q+q(m′−n′)⋅p=pqm′,Σ_i∈ Nv_i(A_i)\;≤\;pn · q+q(m -n )· p\;=\;pq\,m , (2) with equality only if every vertex good is given to an agent that values it q. So the average utility is at most pqpq, and ≤pq OPT≤ pq. Suppose that ℐI has no perfect matching, and that some allocation A has EW(A)≥pqEW(A)≥ pq. By (2), equality holds throughout: every agent has utility exactly pqpq, and every vertex good is held by an incident agent. It is seen that if qk+pℓ=pqqk+p =pq with integers 0≤k≤p0≤ k≤ p and ℓ≥0 ≥ 0, then k∈0,pk∈\0,p\. Agent iei_e values high only its p incident vertex goods, so k≤pk≤ p and the claim applies: each agent holds either none or all p of its incident vertex goods. Since all pn′pn vertex goods are held by incident agents, exactly n′n agents hold all p of theirs, and their hyperedges are pairwise disjoint and cover every vertex, i.e. they form a perfect matching, a contradiction. Hence <pq OPT<pq, and since utilities are integers, ≤pq−1 OPT≤ pq-1. ∎ We now to present a constant approximation for MEW. Theorem 3. There is a 3/2 3/2-approximation algorithm for MEW with p,q\p,q\-additive valuations, where 3<p<q3<p<q. Proof. Let r=q/p>1r=q/p>1 and ℐI the instance with values in 1,r\1,r\. If 2r∈ℕ2r , the instance can be solved exactly by Theorem 1. Otherwise, let a=⌊2r⌋2,b=⌈2r⌉2,a= 2r 2,b= 2r 2, so that 1≤a<r<b1≤ a<r<b. Let A∗A^* be an optimal allocation for ℐI, and let SaS^a and SbS^b be optimal allocations for the rounded instances ℐaI^a (which has values in 1,a\1,a\) and ℐbI^b (which has values in 1,b\1,b\), respectively. For every agent i and bundle X, rounding down gives arvi(X)≤via(X)≤vi(X) arv_i(X)≤ v_i^a(X)≤ v_i(X). Consequently, EW(Sa)≥EWa(Sa)≥EWa(A∗)≥arEW(S^a) ^a(S^a) ^a(A^*)≥ ar OPT. Similarly, rounding up gives EW(Sb)≥rbEW(S^b)≥ rb OPT. Now, returning the allocation S with larger welfare in the original instance therefore guarantees EW(S)≥maxar,rb⋅≥ab⋅≥23⋅.EW(S)≥ \ ar, rb \· OPT≥ ab· OPT≥ 23· OPT. Finally, note that both rounded instances have integer or half-integer high values and are solvable exactly in polynomial time by Theorem 1. Thus S is found efficiently, completing the proof. ∎ 4 Poly-time Algorithm for −p,0,c\-p,0,c\-Additivities In this section we will present a polynomial time algorithm for solving MEW, assuming that each agent i has a −pi,0,ci\-p_i,0,c_i\-additive valuation, where pi∈1,2p_i∈\1,2\ and cic_i is a positive integer. Theorem 4. An allocation of maximum egalitarian welfare can be found in time polynomial in the input length for additive −pi,0,ci\-p_i,0,c_i\ valuations, where pi∈1,2p_i∈\1,2\ and cic_i is a positive integer. Fix an integer threshold T. We reduce the decision version of MEW to the problem of finding a maximum-weight perfect matching in a suitably constructed graph. We next describe this graph and show that the weight of a maximum-weight perfect matching characterizes the feasibility of the threshold T. For every item o, let Go=i:vi(o)=ciG_o=\i:v_i(o)=c_i\ and Zo=i:vi(o)=0Z_o=\i:v_i(o)=0\. We classify an item as • a good if Go≠∅G_o≠ , • a neutral item if Go=∅G_o= and Zo≠∅Z_o≠ , • a universal chore if Go=Zo=∅G_o=Z_o= . Thus a universal chore has value −pi-p_i to every agent i. Let H be the number of universal chores. Define a bipartite incidence graph Γ between goods and agents, with (o,i)(o,i) an edge precisely when i∈Goi∈ G_o, and let did_i be the degree of agent i. A good assignment is a map σ sending each good o to an agent in GoG_o; it induces the vector g(σ)=(g1,…,gn)g(σ)=(g_1,…,g_n), where gi=|σ−1(i)|g_i=|σ^-1(i)|. Lemma 7 (Normalization). Every allocation can be transformed, without decreasing any agent’s value, so that each good goes to an agent in GoG_o and each neutral item goes to an agent in ZoZ_o. Proof. If a good o is held by h∉Goh∉ G_o, remove it from h and give it to any j∈Goj∈ G_o. Its removal cannot decrease h’s value, and j gains cjc_j. Similarly, a neutral item held by h∉Zoh∉ Z_o has value −ph-p_h to h and can be moved to any j∈Zoj∈ Z_o. These moves treat distinct items independently because the valuations are additive. ∎ In a normalized allocation, agent i holds gig_i goods, each worth cic_i, some neutral items worth zero, and hih_i universal chores, each worth −pi-p_i. Hence vi(Ai)=cigi−pihi.v_i(A_i)=c_ig_i-p_ih_i. Define Li=max0,⌈T/ci⌉,and fi(gi)=⌊(cigi−T)/pi⌋.L_i= \0, T/c_i \, ~~f_i(g_i)= (c_ig_i-T)/p_i . (3) For a nonnegative integer gig_i, the inequality cigi≥Tc_ig_i≥ T is equivalent to gi≥Lig_i≥ L_i. In that case fi(gi)≥0f_i(g_i)≥ 0 is the largest number of universal chores that agent i can absorb while keeping value at least T. These statements also hold when T is negative. Lemma 8 (Chore absorption). There is an allocation of egalitarian welfare at least T if and only if there is a good assignment σ such that, for g=g(σ)g=g(σ), gi≥Lig_i≥ L_i for all i, and ∑i=1nfi(gi)≥H _i=1^nf_i(g_i)≥ H. Proof. Suppose there is an allocation of welfare at least T, and normalize it using Lemma 7. If agent i receives gig_i goods and hih_i universal chores, then cigi−pihi≥Tc_ig_i-p_ih_i≥ T. Since gig_i is a nonnegative integer and cigi≥Tc_ig_i≥ T, we have gi≥max0,⌈T/ci⌉=Lig_i≥ \0, T/c_i \=L_i. Since hih_i is an integer and pihi≤cigi−Tp_ih_i≤ c_ig_i-T, we also have hi≤⌊(cigi−T)/pi⌋=fi(gi).h_i≤ (c_ig_i-T)/p_i =f_i(g_i). Every universal chore is allocated, so ∑ihi=H _ih_i=H, proving the necessary inequality. Conversely, assign the goods according to σ. The capacities fi(gi)f_i(g_i) are nonnegative integers with sum at least H. Distribute the H universal chores to agents with unused capacity, obtaining integers 0≤hi≤fi(gi)0≤ h_i≤ f_i(g_i) with ∑ihi=H _ih_i=H. Assign each neutral item to an agent in its nonempty set ZoZ_o. Each resulting utility satisfies cigi−pihi≥Tc_ig_i-p_ih_i≥ T, as required. ∎ Definition 8. A good assignment σ is T-admissible if gi(σ)≥Lig_i(σ)≥ L_i for every agent i. Partition the agents into N1=i:pi=1,N_1=\i:p_i=1\, N2even=i:pi=2,ci is evenN_2^even=\i:p_i=2,\ c_i is even\, N2odd=i:pi=2,ci is oddN_2^odd=\i:p_i=2,\ c_i is odd\. Set ωi=2ci _i=2c_i for i∈N1i∈ N_1 and ωi=ci _i=c_i for pi=2p_i=2. Intuitively, ωi _i measures how much assigning one good to agent i contributes to the doubled chore-absorption capacity, before the fixed and parity corrections. Define β=2T⋅|N1|+T⋅(|N2even|+|N2odd|)+[T is odd]⋅|N2even|, β=2T·|N_1|+T· (|N_2^even|+|N_2^odd| )+1[T is odd]·|N_2^even|, (4) Φ(σ)=∑o goodωσ(o)−∑i∈N2odd[gi≢T(mod2)]. (σ)=Σ_o good _σ(o)-Σ_i∈ N_2^odd1[g_i ≡ T 2]. (5) Here [⋅]1[·] denotes an indicator. Lemma 9 (Parity identity). For every good assignment σ and every integer T, 2∑i=1nfi(gi)=Φ(σ)−β(T).2 _i=1^nf_i(g_i)= (σ)-β(T). Proof. For i∈N1i∈ N_1, we have 2fi(gi)=2cigi−2T2f_i(g_i)=2c_ig_i-2T. For pi=2p_i=2, the identity 2⌊a/2⌋=a−a is odd2 a/2 =a-1\a is odd\, valid for every integer a, gives 2fi(gi)=cigi−T−[cigi−T is odd].2f_i(g_i)=c_ig_i-T-1[c_ig_i-T is odd]. (6) For i∈N2eveni∈ N_2^even, cic_i is even, so the indicator equals [T is odd]1[T is odd]. For i∈N2oddi∈ N_2^odd, cic_i is odd, so it equals [gi≢T(mod2)]1[g_i ≡ T 2]. Sum these formulas and use ∑iωigi=∑o goodωσ(o) _i _ig_i= _o good _σ(o). ∎ By Lemmas 8 and 9, there is an allocation of welfare at least T precisely when some T-admissible good assignment satisfies Φ(σ)≥=2H+β. (σ)≥=2H+β. Maximizing Φ by a weighted perfect matching. For every agent i, write Ui=di−LiU_i=d_i-L_i. The number UiU_i is the maximum number of incident goods that may be assigned to other agents while agent i still receives at least LiL_i goods. If some Ui<0U_i<0, no T-admissible assignment exists. Otherwise construct a graph ℋH as follows, with all unspecified edge weights zero. 1. Good vertices. For every good o, add a vertex xox_o. 2. Port vertices. For every incidence edge (o,i)(o,i), add a port qi,oq_i,o and an edge xoqi,ox_oq_i,o of weight ωi _i. 3. Absorber vertices. For agent i, add UiU_i ordinary absorbers ai,1,…,ai,Uia_i,1,…,a_i,U_i and join every port of i to every ordinary absorber of i. If i∈N2oddi∈ N_2^odd and Li≢T(mod2)L_i ≡ T 2, also add an extra absorber ai,0a_i,0, with no edges to ports. Denote all absorbers of i by iA_i and make iA_i a clique. 4. Parity vertices. For each agent i, add ziz_i adjacent to every vertex of iA_i. Give these edges weight −1-1 for i∈N2oddi∈ N_2^odd and zero otherwise. 5. Extra vertices. If the number of vertices constructed so far is odd, add one more vertex z0z_0. Make Z=zi:i∈NZ=\z_i:i∈ N\, together with z0z_0 if present, a clique. The graph has O(n(m+1))O(n(m+1)) vertices and O(nm2+n2)O(nm^2+n^2) edges, including the clique on Z. It has an even number of vertices. Whether it has a perfect matching is characterized by Lemma 10 below. Example 2 (The gadget graph ℋH). Consider two agents with values in −2,0,3\-2,0,3\, so that p1=p2=2p_1=p_2=2, c1=c2=3c_1=c_2=3, both agents belong to N2oddN_2^odd, and ω1=ω2=3 _1= _2=3. There are four items: o1o_1 o2o_2 o3o_3 h agent 1 3 3 0 −2-2 agent 2 3 −2-2 3 −2-2 Thus o1,o2,o3o_1,o_2,o_3 are goods and h is the only universal chore. Agent 1 is adjacent to o1,o2o_1,o_2 and agent 2 to o1,o3o_1,o_3 in Γ , so d1=d2=2d_1=d_2=2. The optimum is 3, attained by assigning o1,o2,h\o_1,o_2,h\ to agent 1, of value 4, and o3\o_3\ to agent 2, of value 3. For an upper bound, normalize any allocation. With only three goods, one agent receives at most one good and consequently has utility at most 3. For T=2T=2, we have Li=⌈2/3⌉=1L_i= 2/3 =1 and Ui=1U_i=1. Since Li≢T(mod2)L_i ≡ T 2, each agent receives an extra absorber ai,0a_i,0 not adjacent to any port. There are three good vertices, four ports, four absorbers, and the two parity vertices z1,z2z_1,z_2, giving 13 vertices; hence z0z_0 is added. Figure 3 shows the resulting graph. All good–port edges have weight 3, all edges from ziz_i to its absorbers have weight −1-1, and all other edges have weight zero. xo2x_o_2xo1x_o_1xo3x_o_3q1,o2q_1,o_2q1,o1q_1,o_1q2,o1q_2,o_1q2,o3q_2,o_3a1,1a_1,1a1,0a_1,0a2,1a_2,1a2,0a_2,0z1z_1z0z_0z2z_2agent 11agent 22 Figure 3: The graph ℋH of Example 2. Good–port edges have weight 33, dashed edges have weight −1-1, and all other edges have weight 00. Small dashed boxes mark the extra absorbers a1,0,a2,0a_1,0,a_2,0. Thick edges form the maximum-weight perfect matching of weight 88. Lemma 10 (Matching reduction). The graph ℋH has a perfect matching if and only if a T-admissible good assignment exists. Whenever either exists, the maximum weight of a perfect matching is the maximum of Φ(σ) (σ) over all such assignments. Proof. First consider the parity mechanism for one agent i in a perfect matching. Suppose uiu_i of its ports are matched to absorbers. Ports reach only ai,1,…,ai,Uia_i,1,…,a_i,U_i, so ui≤Uiu_i≤ U_i. The remaining ℓi=|i|−ui _i=|A_i|-u_i absorbers can be matched only inside the clique iA_i or to ziz_i, and ziz_i covers at most one absorber. Therefore ziz_i is matched into iA_i if and only if ℓi _i is odd. Let gi=di−uig_i=d_i-u_i be the number of ports of agent i matched to goods. For i∈N2oddi∈ N_2^odd, if ai,0a_i,0 is absent, then Li≡T(mod2)L_i≡ T 2 and ℓi=Ui−ui=gi−Li _i=U_i-u_i=g_i-L_i. If ai,0a_i,0 is present, then Li≢T(mod2)L_i ≡ T 2 and ℓi=Ui+1−ui=gi−Li+1 _i=U_i+1-u_i=g_i-L_i+1. In both cases, ℓi is odd⟺gi≢T(mod2),(i∈N2odd). _i is odd g_i ≡ T 2, (i∈ N_2^odd). (7) From matchings to assignments. Let ℳM be a perfect matching. Every xox_o is adjacent only to ports qi,oq_i,o with i∈Goi∈ G_o. Set σ(o)=iσ(o)=i when xox_o is matched to qi,oq_i,o. This defines a good assignment. Every port is adjacent only to its good and its agent’s ordinary absorbers, so the ports of agent i matched to goods correspond exactly to σ−1(i)σ^-1(i). Consequently, gi(σ)=di−ui≥di−Ui=Lig_i(σ)=d_i-u_i≥ d_i-U_i=L_i, and σ is T-admissible. The weight of ℳM is ∑oωσ(o) _o _σ(o) minus the number of i∈N2oddi∈ N_2^odd whose vertex ziz_i is matched into iA_i. By (7), this weight is Φ(σ) (σ). From assignments to matchings. Let σ be T-admissible. Match each xox_o to qσ(o),oq_σ(o),o. For each agent i, match its ui=di−gi≤Uiu_i=d_i-g_i≤ U_i remaining ports to distinct ordinary absorbers. If the number ℓi _i of remaining absorbers is odd, match one of them to ziz_i; pair the rest inside iA_i. Every vertex outside Z is now covered. Since every matching edge covers two vertices and the number of vertices in ℋH is even, the number of uncovered vertices in Z is even. They can be paired because Z is a clique. The resulting perfect matching has weight Φ(σ) (σ) by (7). The two constructions prove both claims. ∎ By Lemma 8 and 10, the proof of Theorem 4 is followed. Continuation of Example 2. The highlighted matching in Figure 3 corresponds to σ(o1)=1σ(o_1)=1, σ(o2)=1σ(o_2)=1, and σ(o3)=2σ(o_3)=2. Agent 1 uses both ports, so its two absorbers are matched to each other. Since g1=2≡T(mod2)g_1=2≡ T 2, it incurs no penalty. Agent 2 does not use q2,o1q_2,o_1, which is matched to a2,1a_2,1; the leftover absorber a2,0a_2,0 is matched to z2z_2 at cost −1-1, reflecting g2=1≢T(mod2)g_2=1 ≡ T 2. Finally, z0z_0 is matched to z1z_1. The weight is 3+3+3−1=8=Φ2(σ)3+3+3-1=8= _2(σ). Any admissible assignment has goods counts (2,1)(2,1) or (1,2)(1,2), so this is the maximum. As β(2)=2|N2odd|=4β(2)=2|N_2^odd|=4 and α(2)=2H+β(2)=6≤8α(2)=2H+β(2)=6≤ 8, the threshold T=2T=2 is feasible. 5 Hardness for −2,0,c\-2,0,c\-Submodular Valuations In this section, we consider −2,0,c\-2,0,c\-submodular valuations. In contrast to the additive case, we show that MEW is strongly NPNP-hard for this class of valuations. Theorem 5. Let c≥1c≥ 1 be a fixed odd integer. For polynomial-time computable −2,0,c\-2,0,c\-submodular valuations, it is NPNP-hard to distinguish instances with =T OPT=T from instances with =T−1 OPT=T-1, where T>1T>1 is a polynomially bounded integer. This holds even when all agents but one are additive. Consequently, unless P=NPP=NP, this class admits neither an FPTAS nor a polynomial-time algorithm returning an allocation with additive error strictly smaller than one. Lemma 11. If ρ is a matroid rank function, then v(S)=(c+2)ρ(S)−2|S|v(S)=(c+2)ρ(S)-2|S| is −2,c\-2,c\-submodular, and v(S)=cρ(S)−2(|S|−ρ(S)).v(S)=cρ(S)-2 (|S|-ρ(S) ). Thus an agent with such a valuation perceives the items that raise its rank as goods of value c and all other items as chores of value −2-2. Such valuations are order-neutral: every ordering of a bundle S has exactly ρ(S)ρ(S) marginals of value c and |S|−ρ(S)|S|-ρ(S) marginals of value −2-2. For odd positive c, every −2,0,c\-2,0,c\-submodular valuation is order-neutral as well. Indeed, the six unordered pair sums −4,−2,0,c−2,c,2c-4,-2,0,c-2,c,2c are distinct, so swapping adjacent items in an ordering preserves the unordered pair of their marginals, and therefore the entire marginal multiset. This is the argument of Fitzsimmons et al. (2025, Proposition 4.8). Hence order-neutrality alone does not yield tractability when chores have magnitude two. 5.1 A sparse paving encoding of CLIQUE Let k≥2k≥ 2 and let E=e1,e1′,…,ek,ek′E=\e_1,e _1,…,e_k,e _k\ be a set of 2k2k elements, partitioned into the pairs Pu=eu,eu′P_u=\e_u,e _u\ for u∈[k]u∈[k]. For J⊆[k]J [k], write PJ=⋃u∈JPuP_J= _u∈ JP_u. Fix an integer s with 1≤s<k1≤ s<k, and put r=2sr=2s. In the reduction, the elements of E are the pair items and s is the target clique size. Restricting CLIQUE to 1≤s<k1≤ s<k preserves NP-hardness, since its other endpoints are decidable directly. Lemma 12. Let ℱ⊆PJ:|J|=sF \P_J:|J|=s\. Then ρℱ(S)=|S|,|S|<r,r−1,S∈ℱ,r,otherwise _F(S)= cases|S|,&|S|<r,\\ r-1,&S ,\\ r,&otherwise cases is the rank function of a matroid of rank r on E. A set PJP_J with |J|=s|J|=s is independent if and only if PJ∉ℱP_J . Given a graph G on vertex set [k][k], let ℱ=PJ:|J|=s,J is not a clique of .F_G=\P_J:|J|=s,\ J is not a clique of G\. Membership in ℱF_G is decidable in polynomial time: check that the set is a union of s whole pairs and then check the edges among their indices. Thus ρℱ _F_G is polynomial-time computable, and a union of s pairs is independent exactly when its indices form a clique. 5.2 The reduction Let c be a fixed odd positive integer and let (,s)(G,s) be a CLIQUE instance on k vertices with 1≤s<k1≤ s<k. Write M_G for the matroid in Lemma 12 with ℱ=ℱF=F_G, and set: d=2kd=2k, d0=2k−2sd_0=2k-2s, H=c(k−s)H=c(k-s), T=cd.T=cd. Items. The 2k2k pair items E=e1,e1′,…,ek,ek′E=\e_1,e _1,…,e_k,e _k\, where Pu=eu,eu′P_u=\e_u,e _u\ is the pair of vertex u; for each u∈[k]u∈[k] a set DuD_u of d private dummy items; a set D0D_0 of d0d_0 private dummy items; and a set C of H chores. These sets are pairwise disjoint. Agents. There are k+1k+1 agents, with rank functions as follows: • the collector 00, with ρ0(S)=ρℱ(S∩E)+|S∩D0| _0(S)= _F_G(S∩ E)+|S∩ D_0|; • for each u∈[k]u∈[k] a pair agent u, with ρu(S)=|S∩(Pu∪Du)| _u(S)=|S∩(P_u∪ D_u)|. These are matroid rank functions: the collector takes a direct sum with the free matroid on D0D_0, and each pair agent uses a free matroid on Pu∪DuP_u∪ D_u; all unspecified items are loops. Valuations. For every agent i, define vi(S)=(c+2)ρi(S)−2|S|.v_i(S)=(c+2) _i(S)-2|S|. Each pair agent is additive: it values every item of Pu∪DuP_u∪ D_u at c and every other item at −2-2. Only the collector can be non-additive. Every chore h∈Ch∈ C is a loop for every agent, that is, ρi(S∪h)=ρi(S) _i(S∪\h\)= _i(S) for every S; hence its marginal value is −2-2 regardless of the bundle. Claim 2. For fixed c, the construction has polynomial size and all its valuations are computable in polynomial time. Lemma 13 (Completeness). If G has a clique of size s, some allocation has welfare at least T. Proof. Let J be such a clique. Give the collector D0∪PJD_0∪ P_J. This set is independent for ρ0 _0 and has size d0+2s=d_0+2s=d, so its value is cd=Tcd=T. Give each u∈Ju∈ J the set DuD_u, of value cdcd. Give each u∉Ju∉ J the set Du∪PuD_u∪ P_u and c chores. Its value is c(d+2)−2c=cdc(d+2)-2c=cd. This uses exactly c(k−s)=Hc(k-s)=H chores and allocates every item. ∎ Lemma 14 (Soundness). If some allocation has welfare at least T, then G has a clique of size s. Proof. Let A be such an allocation. For agent i, let NiN_i be the set of nonloops of ρi _i. Since r≥2r≥ 2, every pair item is a nonloop of the collector. Hence R=|⋃iNi|=2k+kd+d0,R= | _iN_i |=2k+kd+d_0, and the total number of items is R+HR+H. Tightness. For every i, ρi(Ai)≤|Ai∩Ni| _i(A_i)≤|A_i∩ N_i|. Since bundles are disjoint, ∑iρi(Ai)≤R _i _i(A_i)≤ R. Because every item is allocated, ∑ivi(Ai)≤(c+2)R−2(R+H)=cR−2H=c(kd+d)=(k+1)T. _iv_i(A_i)≤(c+2)R-2(R+H)=cR-2H=c(kd+d)=(k+1)T. Every agent has value at least t, so every value equals t and ∑iρi(Ai)=R _i _i(A_i)=R. Equality forces ρi(Ai)=|Ai∩Ni| _i(A_i)=|A_i∩ N_i| for every i, and every item of ⋃iNi _iN_i must be assigned to an agent for whom it is a nonloop. Thus each Ai∩NiA_i∩ N_i is independent; each DuD_u goes to u; and D0D_0 goes to the collector. The only items that can be loops of their holders are the universal chores in C. Pair agents keep whole pairs or nothing. For u∈[k]u∈[k], put xu=|Au∩Pu|x_u=|A_u∩ P_u|. Then ρu(Au)=d+xu _u(A_u)=d+x_u, and vu(Au)=cdv_u(A_u)=cd gives c(ρu(Au)−d)=2(|Au|−ρu(Au)).c ( _u(A_u)-d )=2 (|A_u|- _u(A_u) ). The right-hand side is even. Since c is odd, xux_u is even, and therefore xu∈0,2x_u∈\0,2\. The collector obtains a clique. Each pair item is a nonloop only for its pair agent and the collector. Consequently every pair not kept by its pair agent goes entirely to the collector, and A0∩E=PJA_0∩ E=P_J for some J⊆[k]J [k]. This set is independent in M_G. Since v0(A0)=cdv_0(A_0)=cd and |A0|≥ρ0(A0)|A_0|≥ _0(A_0), cd=cρ0(A0)−2(|A0|−ρ0(A0))≤cρ0(A0).cd=c _0(A_0)-2 (|A_0|- _0(A_0) )≤ c _0(A_0). Thus ρ0(A0)≥d _0(A_0)≥ d. But ρ0(A0)≤d0+2s=d _0(A_0)≤ d_0+2s=d, so equality holds. Independence gives ρ0(A0)=d0+2|J| _0(A_0)=d_0+2|J|, and hence |J|=s|J|=s. By Lemma 12, J is a clique. These equalities also show that the collector receives no chore. ∎ Proof of Theorem 5. Claim 2 and Lemmas 13–14 give a polynomial reduction from CLIQUE for every fixed odd c. All but one agent are additive, and Lemma 11 verifies the required marginals and submodularity. In fact the construction has the exact gap: =T, has a clique of size s,T−1,otherwise. OPT= casesT,&G has a clique of size s,\\ T-1,&otherwise. cases The total-welfare bound in the soundness proof gives ≤T OPT≤ T for every instance. Completeness gives equality on YES-instances; soundness and integrality give ≤T−1 OPT≤ T-1 on NO-instances. It remains to construct an allocation of welfare at least T−1T-1 regardless of G. Choose s−1s-1 whole pairs and two further distinct pairs; this is possible because s<ks<k. Give the collector D0D_0, those s−1s-1 whole pairs, and one item from each of the two further pairs. Its 2s2s pair items are not a union of whole pairs and therefore do not belong to ℱF_G. They are independent, and the collector’s value is T. Give every pair agent its private dummies. Each agent retaining its whole pair receives c chores. The two agents retaining exactly one pair item receive respectively (c−1)/2(c-1)/2 and (c+1)/2(c+1)/2 chores; their values are T+1T+1 and T−1T-1. The agents retaining no pair item receive no chore and have value T. The number of chores used is c(k−s−1)+c−12+c+12=c(k−s)=H.c(k-s-1)+ c-12+ c+12=c(k-s)=H. This allocates every item and proves the lower bound. Since T=2ck≥4T=2ck≥ 4, both possible optima are strictly positive. For the explicitly represented family, an allocation is a polynomial-size certificate whose welfare is polynomial-time computable, so threshold decision is NPNP-complete as well. An algorithm with additive error strictly smaller than one would return integer welfare greater than T−1T-1 on every YES-instance, and hence welfare T. No NO-instance admits such an allocation. For an assumed FPTAS, choose ε=1/(2t) =1/(2t). Its guarantee of /(1+ε)≥(1−ε) OPT/(1+ )≥(1- ) OPT gives welfare at least T−1/2T-1/2 on a YES-instance, again forcing welfare T. Since 1/ε=4ck1/ =4ck is polynomially bounded for fixed c, either algorithm would decide CLIQUE in polynomial time. ∎ Example 3 (The reduction from CLIQUE). Let G be the path on vertices 1,2,3\1,2,3\ with edges 1,2\1,2\ and 2,3\2,3\, let s=2s=2, and let c=3c=3. Then r=4r=4, d=6d=6, d0=2d_0=2, H=3H=3, t=18.t=18. There are six pair items, eighteen private dummy items for the pair agents, two dummy items for the collector, and three chores. The only nonclique pair of vertices is 1,3\1,3\, so ℱ=P1∪P3F_G=\P_1∪ P_3\. Every set of at most three pair items is independent, P1∪P3P_1∪ P_3 has rank three, and every other set of at least four pair items has rank four. In particular, P1∪P2P_1∪ P_2 and P2∪P3P_2∪ P_3 are independent. For the clique J=1,2J=\1,2\, completeness gives the following allocation, shown also in Figure 4. Here vi(Ai)=5ρi(Ai)−2|Ai|v_i(A_i)=5 _i(A_i)-2|A_i|. Agent Bundle AiA_i ρi(Ai) _i(A_i) |Ai||A_i| vi(Ai)v_i(A_i) Collector D0∪P1∪P2D_0∪ P_1∪ P_2 2+4=62+4=6 66 1818 Pair agent 11 D1D_1 66 66 1818 Pair agent 22 D2D_2 66 66 1818 Pair agent 33 D3∪P3∪CD_3∪ P_3∪ C 88 1111 1818 Using P1∪P3P_1∪ P_3 for the collector instead would reduce its value to 5⋅5−2⋅6=135· 5-2· 6=13. For the soundness argument, replace G by the empty graph on the same vertices. There are twenty-six nonchore items, so total welfare is at most 3⋅26−2⋅3=72=4t3· 26-2· 3=72=4t. If every agent had value at least eighteen, all values would equal eighteen and every nonchore item would contribute to the rank of its holder. A pair agent keeping exactly one pair item would have rank seven and odd value 35−2|Au|35-2|A_u|, so it could not attain eighteen. Thus the collector would receive two whole pairs forming an independent set, which is impossible in this instance. In fact the optimum is seventeen: give the collector D0∪P1∪e2,e3D_0∪ P_1∪\e_2,e_3\, give pair agent 11 only D1D_1, and give pair agents 2,32,3 their dummies and their remaining pair item, together with one and two chores respectively. Their values are eighteen, eighteen, nineteen, and seventeen. 112233G, s=2s=2pair agent 11+D1+D_1pair agent 22+D2+D_2pair agent 33+D3+D_3, +3+3 chorese1e_1e1′e_1 e2e_2e2′e_2 e3e_3e3′e_3 collector+D0+D_0, hidden matroid Figure 4: The instance of Example 3 for the path G with edges 1,2\1,2\ and 2,3\2,3\ and s=2s=2. Each pair item eu,eu′e_u,e_u can be counted either by pair agent u (value c) or by the collector (through the hidden sparse paving matroid, in which P1∪P3P_1∪ P_3 is dependent). Thick edges show the allocation for the clique 1,2\1,2\: the collector receives P1∪P2P_1∪ P_2 and its dummies D0D_0, pair agents 11 and 22 keep only their dummies, and pair agent 33 keeps P3P_3, its dummies, and all H=3H=3 chores. Every agent has value t=18t=18. 6 Approximability of −1,0,1\-1,0,1\-Submodularity For −1,0,c\-1,0,c\-submodular valuations with an integer c≥2c≥ 2, every valuation is order-neutral, and maximum egalitarian welfare is polynomial-time computable (Fitzsimmons et al., 2025; Cousins et al., 2023b). For c=1c=1, the pairwise sums of marginals collide, since −1+1=0+0-1+1=0+0, and non-order-neutral valuations exist. The basic example consists of two items x,yx,y with v(∅)=0v( )=0, v(x)=1v(\x\)=1, v(y)=0v(\y\)=0, v(x,y)=0.v(\x,y\)=0. Adding x and then y yields marginals (1,−1)(1,-1), whereas adding y and then x yields (0,0)(0,0). This is a conflict-pair valuation as in Definition 2. By Lemma 1, all conflict-pair valuations are −1,0,1\-1,0,1\-submodular. Theorem 6. Deciding whether ≥1 OPT≥ 1 is NP-complete for explicitly represented conflict-pair valuations, even when each agent has at most one conflict pair and values at most two items at 11. NP-hardness holds under the additional promise that ∈0,1 OPT∈\0,1\. Unless P=NPP=NP, there is no polynomial-time multiplicative approximation algorithm with a finite approximation ratio, even under the promise =1 OPT=1, when an allocation must be returned. There is also no polynomial-time algorithm that always returns an allocation with welfare at least −ε OPT- , for any fixed 0≤ε<10≤ <1. We reduce from 3-SAT (Garey and Johnson, 1979). Let φ be a formula with variables x1,…,xsx_1,…,x_s and nonempty clauses C1,…,CtC_1,…,C_t, each containing at most three literal occurrences. In this section, the capital letters s and t denote the numbers of variables and clauses of this source formula; they do not denote the agent and item sets of the allocation instance. We write n and m for the numbers of agents and items in the constructed instance. Let ovo_v be the number of occurrences of xvx_v, and put Lv=max2,ov.L_v= \2,o_v\. Variable cycles. For every variable xvx_v, create agents av,1,…,av,Lva_v,1,…,a_v,L_v and goods gv,1,…,gv,Lvg_v,1,…,g_v,L_v. Agent av,ka_v,k has singleton value 11 for gv,kg_v,k and gv,k+1g_v,k+1, with indices interpreted modulo LvL_v. Call these its left and right goods, respectively. Since Lv≥2L_v≥ 2, the two goods are distinct. The bipartite graph of these agents and their positive goods is a single even cycle, with exactly two perfect matchings: every agent takes its left good, read as xv=truex_v=true, or every agent takes its right good, read as xv=falsex_v=false. Indeed, the choice of either edge at one agent forces the choices around the entire cycle. This also holds for Lv=2L_v=2, when the graph is a four-cycle. Clause items. For each clause C, create an item yCy_C. Assign the occurrences of xvx_v injectively to agents of the v-cycle. This is possible because Lv≥ovL_v≥ o_v, and each agent is assigned at most one occurrence in the whole formula. If an occurrence of xvx_v in clause C is assigned to av,ka_v,k, give this agent singleton value 00 for yCy_C. Its conflict pair is (gv,k+1,yC),if the occurrence is positive,(gv,k,yC),if the occurrence is negative. cases(g_v,k+1,y_C),&if the occurrence is positive,\\ (g_v,k,y_C),&if the occurrence is negative. cases Thus the conflicting good is precisely the one chosen when the literal is false. An agent without an assigned occurrence has no conflict pair. All unspecified singleton values are −1-1. The valuation of each agent is the sum of its singleton values, minus one if its bundle contains both items of its conflict pair. Lemma 15. The construction has the following properties. (a) Every valuation is a conflict-pair valuation, with exactly two singleton values equal to 11, at most one singleton value equal to 00, and at most one conflict pair. (b) The instance has n=∑v=1sLv≤3t+2sn= _v=1^sL_v≤ 3t+2s agents, and m=n+t≤4t+2sm=n+t≤ 4t+2s items. In particular, it has exactly n cycle goods. It can be constructed in time polynomial in s+ts+t. Proof of Theorem 6. Membership in NPNP follows by evaluating the bundles of a proposed complete allocation using the explicit singleton values and conflict pairs. We prove correctness of the reduction and then establish the promise and approximation claims. Completeness. Let σ satisfy φ . Match each variable cycle according to σ, and assign each clause item yCy_C to an agent representing a literal of C that is true under σ. Every such agent receives its chosen good and at most one clause item, because it represents at most one occurrence. Its chosen good is not paired with that clause item, so its value is 11. Every other agent receives exactly one of its positive goods and also has value 11. All items are assigned, and hence ≥1 OPT≥ 1. Soundness. Suppose a complete allocation A gives every agent value at least 11. For each agent i, let BiB_i be its set of two positive goods. By the definition of the valuation, vi(Ai)≤|Ai∩Bi|,v_i(A_i)≤|A_i∩ B_i|, with equality if and only if AiA_i contains neither an item with singleton value −1-1 for i nor both items of a conflict pair of i. The sets Ai∩BiA_i∩ B_i are disjoint subsets of the n cycle goods. Therefore n≤∑ivi(Ai)≤∑i|Ai∩Bi|≤n.n≤Σ_iv_i(A_i)≤Σ_i|A_i∩ B_i|≤ n. Equality holds throughout. Every agent has value exactly 11, receives exactly one of its positive goods, receives no item that it values at −1-1, and holds no complete conflict pair. Every cycle good is assigned to an agent that values it positively. Thus each variable cycle is assigned according to one of its two perfect matchings, defining a Boolean assignment σ. Since the allocation is complete, each clause item yCy_C has an owner. It is valued at −1-1 by everyone except agents representing occurrences in C, so its owner is one of those occurrence agents. That agent does not hold the good paired with yCy_C. By construction, its corresponding literal is true under σ. Every clause is therefore satisfied. The promise ∈0,1 OPT∈\0,1\. For every allocation, the last two inequalities in () hold without any assumption on its welfare. Consequently, the sum of utilities is at most n, and ≤1 OPT≤ 1. For the reverse bound, choose any Boolean assignment, without requiring it to satisfy the formula, and match each cycle accordingly. For each nonempty clause C, assign yCy_C to an agent representing any one of its occurrences. The selected recipient agents are distinct: an agent represents at most one occurrence, belonging to just one clause. Each agent therefore receives one positive good and at most one clause item of singleton value zero. Its utility is 11 if no conflict is activated and 00 otherwise. This is a complete allocation of nonnegative welfare, proving ≥0 OPT≥ 0. Since utilities are integral, every constructed instance satisfies ∈0,1 OPT∈\0,1\. The completeness and soundness arguments show that its optimum is 11 exactly when φ is satisfiable, and otherwise is 00. Inapproximability. Suppose a polynomial-time algorithm returns an allocation of welfare at least /ρ OPT/ρ whenever =1 OPT=1, where 1≤ρ<∞1≤ρ<∞; the ratio may even depend on the input size. Run it on an instance of the reduction and accept precisely when its output is a valid complete allocation of strictly positive welfare. On a satisfiable instance, the promised guarantee is strictly positive, so integrality forces welfare at least 11. On an unsatisfiable instance, no valid allocation has positive welfare, regardless of the algorithm’s behavior outside its promise. This would decide 3-SAT in polynomial time. Here polynomial time has its usual total running-time meaning; alternatively, stop the algorithm at its polynomial bound for promised inputs and treat a timeout as rejection. The result concerns finding an allocation: under the promise =1 OPT=1, merely reporting the optimum value is trivial. Similarly, an additive guarantee EW(A)≥−εEW(A)≥ OPT- with ε<1 <1 forces positive welfare whenever =1 OPT=1, and gives the same contradiction. ∎ Example 4 (The reduction from 3-SAT). We illustrate Theorem 6 with φ=(x1∨¬x2)∧(¬x1∨x2). =(x_1 x_2) ( x_1 x_2). Write C1,C2C_1,C_2 for the clauses and y1,y2y_1,y_2 for their items. Both variables occur twice, so L1=L2=2L_1=L_2=2, and the instance has four agents and six items. Assign the occurrences as follows: Occurrence Agent Left good Right good Conflict pair x1x_1 in C1C_1 a1,1a_1,1 g1,1g_1,1 g1,2g_1,2 (g1,2,y1)(g_1,2,y_1) ¬x1 x_1 in C2C_2 a1,2a_1,2 g1,2g_1,2 g1,1g_1,1 (g1,2,y2)(g_1,2,y_2) ¬x2 x_2 in C1C_1 a2,1a_2,1 g2,1g_2,1 g2,2g_2,2 (g2,1,y1)(g_2,1,y_1) x2x_2 in C2C_2 a2,2a_2,2 g2,2g_2,2 g2,1g_2,1 (g2,1,y2)(g_2,1,y_2) The resulting singleton values are g1,1g_1,1 g1,2g_1,2 g2,1g_2,1 g2,2g_2,2 y1y_1 y2y_2 a1,1a_1,1 11 11 −1-1 −1-1 00 −1-1 a1,2a_1,2 11 11 −1-1 −1-1 −1-1 00 a2,1a_2,1 −1-1 −1-1 11 11 00 −1-1 a2,2a_2,2 −1-1 −1-1 11 11 −1-1 00 The assignment x1=x2=truex_1=x_2=true satisfies C1C_1 through x1x_1 and C2C_2 through x2x_2. Let every agent take its left good, assign y1y_1 to a1,1a_1,1, and assign y2y_2 to a2,2a_2,2: Aa1,1 A_a_1,1 =g1,1,y1, =\g_1,1,y_1\, Aa1,2 A_a_1,2 =g1,2, =\g_1,2\, Aa2,1 A_a_2,1 =g2,1, =\g_2,1\, Aa2,2 A_a_2,2 =g2,2,y2. =\g_2,2,y_2\. Agent a1,1a_1,1 does not hold g1,2g_1,2, the partner of y1y_1, and agent a2,2a_2,2 does not hold g2,1g_2,1, the partner of y2y_2. Every agent thus has value exactly 11. By contrast, moving y1y_1 to a2,1a_2,1 would activate the conflict pair (g2,1,y1)(g_2,1,y_1) and reduce this agent’s value to 00, reflecting that the literal ¬x2 x_2 is false. y1y_1y2y_2a1,1a_1,1vs. g1,2g_1,2a1,2a_1,2vs. g1,2g_1,2a2,1a_2,1vs. g2,1g_2,1a2,2a_2,2vs. g2,1g_2,1g1,1g_1,1g1,2g_1,2g2,1g_2,1g2,2g_2,2cycle of x1x_1cycle of x2x_2 Figure 5: The instance of Example 4 for φ=(x1∨¬x2)∧(¬x1∨x2) =(x_1 x_2) ( x_1 x_2). Each dashed box is the cycle of a variable: vertical edges (every agent takes its left good) encode true, diagonal edges encode false. Solid thin edges join agents to goods they value at 11, dashed edges join agents to clause items they value at 00, and “vs. g” names the good forming a conflict pair with the agent’s clause item. Thick edges show the allocation for x1=x2=truex_1=x_2=true, in which every agent has value 11. 7 Discussion and Open Problems We have located the boundary between tractable and intractable max-min allocation for valuations whose item values or marginals come from a small set. For positive bi-valued additive instances with values in p,q\p,q\, complexity depends only on the reduced denominator p: the problem is polynomial-time solvable for p∈1,2p∈\1,2\, and NP-hard to approximate within a constant factor for p≥3p≥ 3. For p≥3p≥ 3, longer flat runs in the savings encode exact cover. The same lens resolves the conjectured tractability of −2,0,c\-2,0,c\-valuations for mixed manna, while our hardness and query lower bounds for −2,0,c\-2,0,c\- and −1,0,1\-1,0,1\-submodular valuations show that this tractability relies on additivity. The most notable missing piece is the complexity of 2,c\2,c\-submodular valuations with c odd. Whether the half-integer case remains polynomial for positive submodular valuations is therefore open, and it is the case that would complete the picture. Further directions include closing the approximation gap for p≥3p≥ 3 (between pq/(pq−1)≤12/11pq/(pq-1)≤ 12/11 and our 3/2 3/2), extending the matching approach to leximin and other welfare objectives. Use of generative AI. The authors used GenAI iteratively to refine and improve an initial draft of this paper. The authors have verified all proofs and accept full responsibility for the accuracy and correctness of the results presented in the paper. References [1] H. Akrami, B. R. Chaudhury, M. Hoefer, K. Mehlhorn, M. Schmalhofer, G. Shahkarami, G. Varricchio, Q. Vermande, and E. van Wijland (2022) Maximizing nash social welfare in 2-value instances. In Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI), p. 4760–4767. Cited by: §1.1. [2] H. Akrami, B. R. Chaudhury, M. Hoefer, K. Mehlhorn, M. Schmalhofer, G. Shahkarami, G. Varricchio, Q. Vermande, and E. van Wijland (2025) Maximizing nash social welfare in two-value instances: delineating tractability. Mathematics of Operations Research. Cited by: §1.1. [3] G. Amanatidis, H. Aziz, G. Birmpas, A. Filos-Ratsikas, B. Li, H. Moulin, A. A. Voudouris, and X. Wu (2023) Fair division of indivisible goods: recent progress and open questions. Artificial Intelligence 322, p. 103965. Cited by: §1.1. [4] G. Amanatidis, G. Birmpas, A. Filos-Ratsikas, A. Hollender, and A. A. Voudouris (2021) Maximum nash welfare and other stories about EFX. Theoretical Computer Science 863, p. 69–85. Cited by: §1.1. [5] C. Annamalai, C. Kalaitzis, and O. Svensson (2017) Combinatorial algorithm for restricted max-min fair allocation. ACM Transactions on Algorithms 13 (3), p. 37:1–37:28. Cited by: §1.1. [6] H. Aziz, P. Biró, J. Lang, J. Lesca, and J. Monnot (2019) Efficient reallocation under additive and responsive preferences. Theoretical Computer Science 790, p. 1–15. Cited by: §1.1. [7] M. Babaioff, T. Ezra, and U. Feige (2021) Fair and truthful mechanisms for dichotomous valuations. In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI), p. 5119–5126. Cited by: §1.1, Table 1, §1. [8] S. Barman, S. K. Krishnamurthy, and R. Vaish (2018) Greedy algorithms for maximizing nash social welfare. In Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), p. 7–13. Cited by: §1.1. [9] I. Bezáková and V. Dani (2005) Allocating indivisible goods. ACM SIGecom Exchanges 5 (3), p. 11–18. Cited by: §1.1, §1. [10] S. Bismuth, I. Bliznets, and E. Segal-Halevi (2024) Fair division with bounded sharing: binary and non-degenerate valuations. In Algorithmic Game Theory, G. Schäfer and C. Ventre (Eds.), p. 89–107. Cited by: §1.1. [11] B. Bliem, R. Bredereck, and R. Niedermeier (2016) Complexity of efficient and envy-free resource allocation: few agents, resources, or utility levels. In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI’16, p. 102–108. Cited by: §1.1. [12] F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. D. Procaccia (Eds.) (2016) Handbook of computational social choice. Cambridge University Press. Cited by: §1. [13] F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. D. Procaccia (Eds.) (2016) Handbook of computational social choice. Cambridge University Press, Cambridge. External Links: ISBN 9781107060432 Cited by: §1. [14] E. Budish (2011) The combinatorial assignment problem: approximate competitive equilibrium from equal incomes. Journal of Political Economy 119 (6), p. 1061–1103. Cited by: §1. [15] D. Chakrabarty, J. Chuzhoy, and S. Khanna (2009) On allocating goods to maximize fairness. In Proceedings of the 50th IEEE Symposium on Foundations of Computer Science (FOCS), p. 107–116. Cited by: §1.1. [16] D. Chakrabarty, S. Khanna, and S. Li (2015) On (1,ϵ)(1,ε)-restricted assignment makespan minimization. In Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms (SODA), p. 1087–1101. Cited by: §1.1. [17] T-H. H. Chan, Z. G. Tang, and X. Wu (2016) On (1, epsilon)-Restricted Max-Min Fair Allocation Problem. In 27th International Symposium on Algorithms and Computation (ISAAC 2016), S. Hong (Ed.), Leibniz International Proceedings in Informatics (LIPIcs), Vol. 64, p. 23:1–23:13. Cited by: §1.1, Table 1. [18] S. Cheng and Y. Mao (2018) Restricted max-min fair allocation. In Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP), p. 37:1–37:13. Cited by: §1.1. [19] C. Cousins, V. Viswanathan, and Y. Zick (2023) Dividing good and great items among agents with bivalued submodular valuations. In Proceedings of the 19th Conference on Web and Internet Economics (WINE), p. 225–241. Cited by: §1.1, §1.1, Table 1, Table 1. [20] C. Cousins, V. Viswanathan, and Y. Zick (2023) The good, the bad and the submodular: fairly allocating mixed manna under order-neutral submodular preferences. In Proceedings of the 19th Conference on Web and Internet Economics (WINE), p. 207–224. Cited by: §1.1, §1.2, Table 1, Table 1, Table 1, Table 1, Table 1, Table 1, Table 1, Table 1, Table 1, §6. [21] S. Davies, T. Rothvoss, and Y. Zhang (2020) A tale of santa claus, hypergraphs and matroids. In Proceedings of the 31st ACM-SIAM Symposium on Discrete Algorithms (SODA), p. 2748–2757. Cited by: §1.1. [22] Z. Fitzsimmons, V. Viswanathan, and Y. Zick (2025) On the hardness of fair allocation under ternary valuations. In Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), p. 758–766. Cited by: §1.1, §1.1, §1.1, Table 1, Table 1, §5, §6. [23] M. R. Garey and D. S. Johnson (1979) Computers and intractability: a guide to the theory of NP-completeness. 1 edition, Series of Books in the Mathematical Sciences, W. H. Freeman and Company, New York. Cited by: §3.2, §6. [24] J. Garg and A. Murhekar (2023) Computing fair and efficient allocations with few utility values. Theoretical Computer Science 962, p. 113932. Cited by: §1.1. [25] D. Golovin (2005) Max-min fair allocation of indivisible goods. Technical report Technical Report CMU-CS-05-144, Carnegie Mellon University, Pittsburgh, PA. Cited by: §1.1, Table 1, §1. [26] D. Halpern, A. D. Procaccia, A. Psomas, and N. Shah (2020) Fair division with binary valuations: one rule to rule them all. In Web and Internet Economics: 16th International Conference, WINE 2020, Beijing, China, December 7–11, 2020, Proceedings, p. 370–383. Cited by: §1.1. [27] D. Halpern, A. D. Procaccia, A. Psomas, and N. Shah (2020) Fair division with binary valuations: one rule to rule them all. In Proceedings of the 16th Conference on Web and Internet Economics (WINE), p. 370–383. Cited by: §1.1. [28] J. Jin and B. Tao (2026) On pareto-optimal and fair allocations with personalized bi-valued utilities. In Web and Internet Economics, V. Bilò, Y. Cai, and Z. Huang (Eds.), Cham, p. 521–537. Cited by: §1.1. [29] S. Khot and A. K. Ponnuswami (2007) Approximation algorithms for the max-min allocation problem. In APPROX-RANDOM, Lecture Notes in Computer Science, Vol. 4627, p. 204–217. Cited by: §1.1. [30] J. Lang and J. Rothe (2024) Fair division of indivisible goods. In Economics and Computation. An Introduction to Algorithmic Game Theory, Computational Social Choice, and Fair Division, J. Rothe (Ed.), Classroom Companion: Economics, p. 605–680. Cited by: §1. [31] J. K. Lenstra, D. B. Shmoys, and É. Tardos (1990) Approximation algorithms for scheduling unrelated parallel machines. Mathematical Programming 46 (3), p. 259–271. Cited by: §1.1. [32] L. Lovász and M. D. Plummer (1986) Matching theory. North-Holland. Cited by: §3.1.3. [33] H. Moulin (2004) Fair division and collective welfare. MIT Press, Cambridge, Massachusetts. Cited by: §1. [34] J. Nash (1950) The bargaining problem. Econometrica 18 (2), p. 155–162. Cited by: §1. [35] J. Oxley (2011) Matroid theory. 2 edition, Oxford University Press. Cited by: Appendix B, §2. [36] A. Sen (2017) Collective choice and social welfare: an expanded edition. Harvard University Press, Cambridge, MA and London, England. Cited by: §1. [37] H. Steinhaus (1948) The problem of fair division. Econometrica 16 (1), p. 101–104. Cited by: §1. [38] V. Viswanathan and Y. Zick (2023) A general framework for fair allocation under matroid rank valuations. In Proceedings of the 24th ACM Conference on Economics and Computation (EC), p. 1129–1152. Cited by: §1.1, Table 1, §1. Appendix Appendix A Missing proofs from Section 3 Proof of Lemma 3. Define the alternating sequence νj=sif T−q(j−1) is odd,s−1if T−q(j−1) is even, for all 1≤j≤K. _j= casess&if T-q(j-1) is odd,\\ s-1&if T-q(j-1) is even, cases for all 1≤ j≤ K. We first prove that μj=νj, for j≤K−1, and 0≤μK≤νK. _j= _j,~ for j≤ K-1,~ and ~~0≤ _K≤ _K. (8) Indeed, let 1≤j≤K−11≤ j≤ K-1 and x=T−q(j−1)x=T-q(j-1). Since j<Kj<K we have qj<Tqj<T, so x−q=T−qj>0x-q=T-qj>0 and μj=⌈(T−q(j−1))+2⌉−⌈(T−qj)+2⌉−1=⌈x2⌉−⌈x−q2⌉−1. _j= (T-q(j-1))^+2 - (T-qj)^+2 -1= x2 - x-q2 -1. If x is even, x−qx-q is odd, so μj=x2−x−q+12−1=q−12−1=s−1. _j= x2- x-q+12-1= q-12-1=s-1. If x is odd, x−qx-q is even, so μj=x+12−x−q2−1=q+12−1=s. _j= x+12- x-q2-1= q+12-1=s. In both cases μj=νj _j= _j. Let y=T−q(K−1)y=T-q(K-1). By the choice of K, 1≤y≤q1≤ y≤ q. We have gT(K−1)=K−1+⌈y/2⌉g_T(K-1)=K-1+ y/2 and gT(K)=Kg_T(K)=K, so μK=⌈y/2⌉−1≥0 _K= y/2 -1≥ 0. If y is odd then νK=s _K=s and μK=y−12≤q−12=s _K= y-12≤ q-12=s. If y is even then y≤q−1=2sy≤ q-1=2s, νK=s−1 _K=s-1 and μK=y2−1≤s−1 _K= y2-1≤ s-1. We now prove the claim in the lemma. (i) If T is odd, then μ1=ν1=s _1= _1=s by (8) and definition of νj _j. Since a pair slot must begin with s−1s-1, this term becomes a single slot of weight s. Similar, if T is even, then μ1=ν1=s−1 _1= _1=s-1, so there is no lead single slot. (i) Let j0∈1,2j_0∈\1,2\ be the first remaining position. By (8), μj0,μj0+1,… _j_0, _j_0+1,… follows ν, which starts with s−1s-1 at j0j_0 and alternates. Group the positions j0,j0+1,…,Kj_0,j_0+1,…,K into consecutive blocks (s−1,s)(s-1,s) of ν, the last block possibly consisting of a single position. Every block lying entirely within positions 1,…,K−11,…,K-1 equals (s−1,s)(s-1,s) in μ and becomes a pair slot. Consider the block containing K: • If K is the first position of its block, then νK=s−1 _K=s-1, and μK≤s−1 _K≤ s-1 by (8). It becomes one tail slot of weight at most s−1s-1. • If K is the second position of its block, then μK−1=s−1 _K-1=s-1 and νK=s _K=s. If μK=s _K=s the block becomes a pair slot. Otherwise μK≤s−1 _K≤ s-1, and the block becomes two tail slots of weights s−1s-1 and μK≤s−1 _K≤ s-1, in this order. This proves (i). The last claim holds by construction: the parse-order filling with k goods collects exactly μ1,…,μk _1,…, _k, because a pair slot holding one good contributes s−1=μjs-1= _j for its first position j, and holding two contributes (s−1)+s(s-1)+s. ∎ Proof of Lemma 4. If K≤1K≤ 1 there is at most one slot and the claim is immediate. Let K≥2K≥ 2 and use the form of Lemma 3. Let λmax∈0,1 _ ∈\0,1\ indicate whether a lead slot exists, and let dt=(s−1)−wt≥0d_t=(s-1)-w_t≥ 0 be the deficit of tail slot t with weight wtw_t. Consider any filling with k goods. Let λ∈0,1λ∈\0,1\ indicate whether the lead slot is filled, let c be the number of pair slots holding two goods, and let R be the set of filled tail slots. Since every good contributes s−1s-1 except that the lead good contributes s, a full pair earns an extra 11, and a tail good contributes s−1−dts-1-d_t, the value of the filling is (s−1)k+λ+c−∑t∈Rdt.(s-1)\,k\;+\;λ\;+\;c\;-\;Σ_t∈ Rd_t. (9) The parse-order filling with k≤Kk≤ K goods places one good in the slot position corresponding to each of μ1,…,μk _1,…, _k, and leaves all remaining positions empty. Moreover, by the decomposition S, one can see that the parse-order filling with k goods has value μ1+⋯+μk=σ(k) _1+·s+ _k=σ(k) for every 0≤k≤K0≤ k≤ K. Therefore, it remains to show that (9) is at most the value of the parse-order filling. We distinguish two cases. Case k≤λmax+2Pk≤ _ +2P. The parse-order filling uses no tail slot, fills the lead slot if λmax=1 _ =1 and k≥1k≥ 1, and then completes c∗=⌊(k−λ∗)/2⌋c^*= (k-λ^*)/2 pairs, where λ∗=min(λmax,k)λ^*= ( _ ,k); note c∗≤Pc^*≤ P. Its value is (s−1)k+λ∗+c∗(s-1)k+λ^*+c^*. For an arbitrary filling, λ≤λ∗λ≤λ^* (since λ≤λmaxλ≤ _ and λ≤kλ≤ k) and 2c≤k−λ2c≤ k-λ, so λ+c≤λ+⌊k−λ2⌋≤λ∗+⌊k−λ∗2⌋=λ∗+c∗,λ+c\;≤\;λ+ k-λ2 \;≤\;λ^*+ k-λ^*2 \;=\;λ^*+c^*, where the middle inequality holds because λ↦λ+⌊(k−λ)/2⌋λ λ+ (k-λ)/2 is nondecreasing. As ∑t∈Rdt≥0 _t∈ Rd_t≥ 0, the claim follows. Case k>λmax+2Pk> _ +2P. The lead and pair slots hold at most λmax+2P _ +2P goods, so every filling uses at least τ∗=k−λmax−2Pτ^*=k- _ -2P tail slots, i.e. |R|≥τ∗|R|≥τ^*. Hence λ+c−∑t∈Rdt≤λmax+P−(sum of the τ∗ smallest deficits).λ+c-Σ_t∈ Rd_t\;≤\; _ +P- (sum of the τ^* smallest deficits ). The parse-order filling fills the lead slot, all P pairs, and the first τ∗τ^* tail slots, which by Lemma 3(c) have the largest weights and hence the smallest deficits. It therefore attains this bound. ∎ Appendix B Missing proofs from Section 5 Proof of Lemma 11. The rank function is submodular and |S||S| is modular. A rank marginal is either zero or one, so a marginal of v is respectively −2-2 or c. Also v(∅)=0v( )=0, and the displayed identity follows by rearranging terms. ∎ Proof of Lemma 12. Any two distinct members of ℱF differ in at least one whole pair, so they intersect in at most r−2r-2 elements. Such a family of r-subsets is the family of circuit-hyperplanes of a sparse paving matroid, obtained from the uniform matroid Ur,|E|U_r,|E| by declaring these sets dependent; see Oxley [35]. We give the basis argument to verify the construction directly. Let ℬB consist of all r-subsets of E outside ℱF. This family is nonempty: the r-subsets of any (r+1)(r+1)-set intersect pairwise in r−1r-1 elements, so at most one belongs to ℱF. To check basis exchange, take B1,B2∈ℬB_1,B_2 and x∈B1∖B2x∈ B_1 B_2. If |B2∖B1|=1|B_2 B_1|=1, exchanging x for its unique element gives B2B_2. Otherwise the sets (B1∖x)∪y(B_1 \x\)∪\y\ for y∈B2∖B1y∈ B_2 B_1 intersect pairwise in r−1r-1 elements. At most one is forbidden, so at least one is in ℬB. Thus ℬB is the basis family of a rank-r matroid. Every (r−1)(r-1)-set extends to a member of ℬB, since its distinct r-element extensions intersect in r−1r-1 elements and there are at least two such extensions. Hence every smaller set is independent. An r-set has rank r−1r-1 exactly when it belongs to ℱF. Finally, every set of more than r elements contains an (r+1)(r+1)-set and therefore a member of ℬB. These facts give the displayed rank function. ∎ Proof of Claim 2. There are k+1k+1 agents and m=2k+kd+d0+H=2k2+(c+4)k−(c+2)sm=2k+kd+d_0+H=2k^2+(c+4)k-(c+2)s items. The pair-agent valuations are additive. The collector’s rank requires only set counting and one membership test in ℱF_G, which is polynomial-time computable as explained above. The graph G, the item classes, and these evaluation rules therefore provide a polynomial-size explicit representation. ∎ Appendix C Missing proofs from Section 6 Proof of Lemma 1. Fix a bundle S and an item o∉So∉ S, and let Δ(o∣S)=vi(S∪o)−vi(S) (o S)=v_i(S∪\o\)-v_i(S). Adding o changes the additive part by vi(o)v_i(o). In the second sum, only terms of pairs containing o can change, and since the pairs in Πi _i are disjoint, o lies in at most one pair. If o lies in no pair, then Δ(o∣S)=vi(o) (o S)=v_i(o). If o=xo=x for some (x,y)∈Πi(x,y)∈ _i, the term [x∈S] 1[y∈S]1[x∈ S]\,1[y∈ S] changes from 00 to [y∈S]1[y∈ S], so Δ(x∣S)=1−[y∈S] (x S)=1-1[y∈ S]; symmetrically, if o=yo=y, then Δ(y∣S)=−[x∈S] (y S)=-1[x∈ S]. In all cases Δ(o∣S)=vi(o)−[o is paired and o¯∈S]. (o S)\;=\;v_i(o)-1 [\,o is paired and o∈ S\, ]. (10) Submodularity. Let S⊆TS T and o∉To∉ T. If o¯∈S o∈ S then o¯∈T o∈ T, so the indicator in (10) for T is at least the one for S, and hence Δ(o∣S)≥Δ(o∣T) (o S)≥ (o T). Range of the marginal values. By (10), Δ(o∣S)=vi(o)∈−1,0,1 (o S)=v_i(o)∈\-1,0,1\ if o is unpaired, Δ(x∣S)=1−[y∈S]∈0,1 (x S)=1-1[y∈ S]∈\0,1\, and Δ(y∣S)=−[x∈S]∈−1,0 (y S)=-1[x∈ S]∈\-1,0\. ∎ Example 5 (A conflict-pair valuation). Consider an agent and five items a,b,c,d,ea,b,c,d,e with v(a)=v(c)=1v(a)=v(c)=1, v(b)=v(d)=0v(b)=v(d)=0, v(e)=−1v(e)=-1, and a single conflict pair Π=(a,b) =\(a,b)\. Some values are presented in the following table. S a\a\ b\b\ a,b\a,b\ c,d\c,d\ a,b,c,d\a,b,c,d\ a,b,e\a,b,e\ additive part 11 00 11 11 22 00 # conflicts 00 00 11 00 11 11 v(S)v(S) 11 00 00 11 11 −1-1 The valuation v is submodular: the marginal value of b is 00 at bundles without a and −1-1 at bundles containing a, the marginal value of a is 11 at bundles without b and 00 at bundles containing b, and all other items contribute additively. Proof of Lemma 15. For (a), fix an agent av,ka_v,k. Set vav,k(gv,k)=vav,k(gv,k+1)=1,v_a_v,k(g_v,k)=v_a_v,k(g_v,k+1)=1, and set vav,k(yC)=0v_a_v,k(y_C)=0 if an occurrence in C is assigned to this agent. Give all remaining items singleton value −1-1. Let Πav,k _a_v,k consist of the single prescribed pair, or be empty if no occurrence is assigned. The resulting valuation has exactly the form in Definition 2. In its conflict pair, the first item has singleton value 11 and the second has singleton value 00. As the agent has at most one pair, the required disjointness is automatic. Agents without an assigned occurrence have additive valuations. Even if a variable occurs twice in the same clause, the two occurrences are assigned to different agents. Lemma 1 therefore applies to every agent. For (b), let ℓ=∑v=1Nov≤3M = _v=1^No_v≤ 3M be the total number of literal occurrences. There are n=∑vLvn= _vL_v agents, n cycle goods, and M clause items. Since max2,ov≤ov+2 \2,o_v\≤ o_v+2, we obtain n≤ℓ+2N≤3M+2N,m=n+M≤4M+2N.n≤ +2N≤ 3M+2N, m=n+M≤ 4M+2N. If every variable occurs at least twice, then n=ℓ≤3Mn= ≤ 3M and m≤4Mm≤ 4M. Each valuation is specified by its two positive goods, at most one zero-valued clause item, and at most one conflict pair, with default singleton value −1-1. Thus the representation and its construction are polynomial in the source size; writing the full singleton-value matrix is also polynomial. ∎