Paper deep dive
Maximizing $p$-Mean Social Welfare in the High-Multiplicity Setting: Few Agent Types and Few Item Types
Trung Thanh Nguyen, Khaled Elbassioni
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:The $p$-mean welfare objective unifies several classical social welfare criteria for the allocation of indivisible goods. We study its maximization under additive nonnegative utilities when item and agent multiplicities are encoded in binary. For every fixed finite rational $p<1$, $p\neq0$, we show that the problem is $\mathsf{NP}$-hard with only two item types. Nash welfare ($p=0$) and egalitarian welfare ($p=-\infty$) are NP-hard with three item types. These results hold both for computing an optimal allocation and for rational-threshold decision, and the utilities and threshold can be required to be positive integers. We also show that maximizing $p$-mean social welfare is strongly NP-hard with one agent type and an unrestricted number of item types, for every fixed finite rational $p<1$ and for $p=-\infty$. A quantitative gap in this reduction rules out an FPTAS in the latter setting unless $\mathsf{P}=\mathsf{NP}$. On the positive side, for a fixed number of item types and an arbitrary number of agent types, we give an FPTAS for every fixed $p\in\mathbb Q\cup\{-\infty\}$. Its running time is polynomial in the compact input length and in $1/\varepsilon$, and it returns a compressed allocation. For a fixed number of agent types and an unrestricted number of item types, we give a PTAS for every fixed finite rational $p<1$, also in the fully compact model. We further give explicit compact-model proofs of the classical exact allocation algorithms for one item type, and for egalitarian welfare with two item types. These results essentially settle the complexity and approximability of $p$-mean welfare maximization with few item types and/or few agent types, leaving only the exact complexity of Nash welfare maximization with two item types unresolved in the small-item-type classification.
Tags
Links
- Source: https://arxiv.org/abs/2610.04417v1
- Canonical: https://arxiv.org/abs/2610.04417v1
Trouble viewing inline? Open PDF directly →
Full Text
263,810 characters extracted from source content.
Expand or collapse full text
Maximizing p-Mean Social Welfare in the High-Multiplicity Setting: Few Agent Types and Few Item Types Trung Thanh Nguyen †thanks: DataOptLab, National Economics University, Hanoi 11616, Vietnam Khaled Elbassioni †thanks: Khalifa University of Science and Technology, Abu Dhabi 127788, UAE October 3, 2026 Abstract The p-mean welfare objective unifies several classical social welfare criteria for the allocation of indivisible goods. We study its maximization under additive nonnegative utilities when item and agent multiplicities are encoded in binary. For every fixed finite rational p<1p<1, p≠0p≠ 0, we show that the problem is NP-hard with only two item types. Nash welfare (p=0p=0) and egalitarian welfare (p=−∞p=-∞) are NP-hard with three item types. These results hold both for computing an optimal allocation and for rational-threshold decision, and the utilities and threshold can be required to be positive integers. We also show that maximizing p-mean social welfare is strongly NP-hard with one agent type and an unrestricted number of item types, for every fixed finite rational p<1p<1 and for p=−∞p=-∞. A quantitative gap in this reduction rules out an FPTAS in the latter setting unless = P= NP. On the positive side, for a fixed number of item types and an arbitrary number of agent types, we give an FPTAS for every fixed p∈ℚ∪−∞p ∪\-∞\. Its running time is polynomial in the compact input length and in 1/ε1/ , and it returns a compressed allocation. For a fixed number of agent types and an unrestricted number of item types, we give a PTAS for every fixed finite rational p<1p<1, also in the fully compact model. We further give explicit compact-model proofs of the classical exact allocation algorithms for one item type, and for egalitarian welfare with two item types. These results essentially settle the complexity and approximability of p-mean welfare maximization with few item types and/or few agent types, leaving only the exact complexity of Nash welfare maximization with two item types unresolved in the small-item-type classification. Contents 1 Introduction 2 Related Work 3 Allocation Setting and Notation 4 Hardness Results 4.1 Two item types and nonzero finite orders 4.2 Three item types and Nash welfare 4.3 Three item types and egalitarian welfare 4.4 One agent type and an unrestricted number of item types 5 An FPTAS for p-Mean Social Welfare with a Fixed Number of Item Types 5.1 Algorithmic overview 5.2 Sparse allocations and universal blocks 5.3 Configurations and objective coefficients 5.4 Anchor guesses and the compressed dynamic program 5.5 Repair, approximation guarantee, and running time 5.6 Exact optimal allocations with one item type 5.7 Exact egalitarian welfare with two item types 6 A PTAS for p-Mean Welfare with a Constant Number of Agent Types 6.1 Statement 6.2 Algorithmic overview 6.3 Transformed objectives and positivity 6.4 The residual structural lemma 6.5 Guessing and rounding the residual thresholds 6.6 The configuration formulation 6.7 Solving and rounding the configuration formulation 6.8 Reconstructing a compressed allocation 6.9 Approximation analysis 6.10 Running time 7 Conclusion References A Proofs of the Technical Lemmas in Sections and A.1 Proof of Lemma A.2 Proof of Lemma A.3 Proof of Lemma A.4 Proof of Lemma B An Illustrative Example for the proof of Lemma C Exact Egalitarian Welfare with Few Agent and Item Types 1 Introduction Fair division studies how a set of resources can be allocated among agents with possibly conflicting preferences so that the resulting allocation is fair in a well-defined sense. Much of the modern literature, motivated by applications such as course allocation, inheritance division, spectrum and bandwidth allocation, and the assignment of computational resources, has focused on the setting of indivisible goods, where each item must be allocated in its entirety to a single agent Lang and Rothe (2024); Bouveret et al. (2016). Prominent fairness notions include envy-freeness and its relaxations EF1 and EFX, proportionality and its relaxation PROP1, and the maximin share (MMS) guarantee; we refer to the survey Amanatidis et al. (2023) and the references therein for formal definitions and an overview of the extensive literature on these notions. Another natural fairness objective is to maximize the egalitarian social welfare (ESW), defined as the minimum utility attained by any agent, thereby directly promoting the welfare of the least well-off agent. Alongside fairness, efficiency is a fundamental consideration in resource allocation. A desirable allocation should make effective use of the available resources and, ideally, be Pareto optimal or optimize an appropriate social welfare objective. Two of the most prominent objectives are the utilitarian social welfare (USW), defined as the sum of the agents’ utilities, and the Nash social welfare (NSW), defined as the geometric mean of their utilities. While USW emphasizes aggregate efficiency and ESW focuses on the least well-off agent, NSW is celebrated for achieving a compelling balance between fairness and efficiency Caragiannis et al. (2016). This interplay naturally motivates the study of welfare objectives that provide a unified framework encompassing these classical criteria. One such framework is given by the family of generalized (or p-mean) welfare functions, formally defined in Section 3. By varying p∈[−∞,1]p∈[-∞,1], this family smoothly interpolates between the three classical welfare objectives: p=1p=1 gives USW divided by n and hence the same maximization problem, p=0p=0 gives NSW, and p=−∞p=-∞ gives ESW. Moreover, decreasing p places progressively greater emphasis on agents receiving lower utility, thereby providing a natural parameter for controlling the trade-off between aggregate efficiency and distributive fairness. Consequently, p-mean welfare has attracted growing research interest over the last decade Barman et al. (2020); Chaudhury et al. (2021); Barman and Sundaram (2020); Garg et al. (2022); Barman and Verma (2022); Barman et al. (2022); Viswanathan and Zick (2025); Pardeshi et al. (2024); Eckart et al. (2024); Krishna et al. (2025); Huang et al. (2025); Celine et al. (2026). Exact p-mean welfare maximization is computationally intractable in general, motivating the study of restrictions on the heterogeneity of items and agents. In many applications, the population of agents and the catalogue of items consist of a modest number of distinct types, each replicated many times. For example, course seats, shifts, machine time, and standardized resources can have many interchangeable copies, while agents sharing a role may have identical valuations. Such an instance can be described by the numbers of agent types K and item types q, the per-type utility values, and the corresponding multiplicities. Because the total numbers n of agents and m of items can be exponential in the length of this description, running time polynomial in n and m need not be polynomial in the compact input length. This distinction motivates the study of parameterized and high-multiplicity fair division; see, e.g., Woeginger (1997); Nguyen and Rothe (2014); Bliem et al. (2016); Barman et al. (2018b); Anari et al. (2018); Jansen and Maack (2019); Nguyen and Rothe (2023); Garg et al. (2022); Nguyen et al. (2024). We also note that a substantial body of work has studied fair division in the high-multiplicity setting with respect to fairness notions such as EF, EF1, EFX, and MMS; see, e.g. Aziz et al. (2023); Mahara (2023); Chaudhury et al. (2024); Davidiuk et al. (2026); Garg et al. (2024b); Ma et al. (2025); Hv et al. (2025); Shahkar and Garg (2025). We study how the numbers of item and agent types determine the complexity and approximability of p-mean welfare maximization in this compact model. Our principal contributions are as follows. • We establish NPNP-hardness with two item types for every fixed finite rational p<1p<1, p≠0p≠ 0, and with three item types for Nash and egalitarian welfare. The reductions use positive rational utilities and rational welfare thresholds; both can also be made positive integers. They prove hardness of exact allocation and of rational-threshold decision already for explicitly listed agents. We also establish strong NPNP-hardness with one agent type for every fixed finite rational p<1p<1 and for p=−∞p=-∞, with an unrestricted number of item types. A quantitative gap in this reduction rules out an FPTAS in the latter setting unless = P= NP. • For a fixed number of item types and an arbitrary number of agent types, with both multiplicities encoded in binary, we give an FPTAS for every fixed p∈ℚ∪−∞p ∪\-∞\. The running time is polynomial in the compact input length and in 1/ε1/ , and the output is a compressed allocation. • For a fixed number of agent types and an unrestricted number of item types, with both multiplicities encoded in binary, we give a PTAS for every fixed finite rational p<1p<1. For completeness, we also give explicit proofs in the compact model of two exact allocation results following from classical methods. With one item type, an optimal allocation is computable in polynomial time for every fixed p∈ℚ∪−∞p ∪\-∞\. The nonzero finite welfare parameters p below one use separable concave resource allocation Galil and Megiddo (1979); the remaining cases admit direct constructions. With two item types, egalitarian welfare is exactly solvable in polynomial time by the two-job-type methods of McCormick, Smallwood, and Spieksma McCormick et al. (2001). Both results allow an arbitrary number of agent types and binary multiplicities. Table 1 summarizes the resulting complexity of exact allocation. The polynomial-time entries concern constructing an optimal allocation; they do not automatically imply polynomial-time comparison of its welfare with an arbitrary rational threshold. This distinction is necessary even with one item type, as explained in Remark 1. q Fixed rational p<1p<1, p≠0p≠ 0 Nash: p=0p=0 Egalitarian: p=−∞p=-∞ 11 Polynomial time Galil and Megiddo (1979) Polynomial time [here] Polynomial time McCormick et al. (2001) 22 NP-hard [here] Not settled here Polynomial time McCormick et al. (2001) 33 NP-hard [here] NP-hard [here] NP-hard [here] 44 NP-hard [here] NP-hard [here] NP-hard [here] Table 1: Status established here for computing an exact optimal allocation, with at most q item types, an unrestricted number of agent types, and binary item and agent multiplicities. The hardness entries also hold for rational-threshold decision. “Not settled here” denotes the case not resolved by the results in this paper and thus remains open. References identify the classical methods underlying the polynomial-time results; their compact implementations are proved here. The marker [here] indicates a proof in this paper, including the elementary one-item-type Nash result, which is not claimed as new. The polynomial-time entries follow from Theorems 7 and 8; the hardness entries follow from Theorem 1. All fixed values of q in the table admit the compact FPTAS of Theorem 6. The utilitarian case p=1p=1 is polynomial-time solvable for every q by assigning each item type to an agent who values it most. Consequently, the item-type boundaries for exact allocation are sharp for every fixed finite rational p<1p<1, p≠0p≠ 0, and for egalitarian welfare: hardness starts at two and three types, respectively. Among the cases in the table, only two-type Nash welfare remains unsettled by our results. 2 Related Work The study of fair and efficient allocations has yielded a substantial body of algorithmic work. We express approximation guarantees as fractions of the optimal welfare; an approximation loss of α≥1α≥ 1 corresponds to a welfare guarantee of 1/α1/α. For MNSW, Nguyen and Rothe Nguyen and Rothe (2014) gave a 1/m1/m welfare guarantee, and Cole and Gkatzelis Cole and Gkatzelis (2015) obtained the first constant-factor guarantee. Barman, Krishnamurthy, and Vaish Barman et al. (2018a) gave an approximation loss of 1.451.45, corresponding to a welfare guarantee of 1/1.45≈0.689661/1.45≈ 0.68966. On the hardness side, Garg, Hoefer, and Mehlhorn Garg et al. (2024a) proved that achieving any fixed welfare guarantee greater than 7/8 7/8 is NPNP-hard. For general MESW, Chakrabarty, Chuzhoy, and Khanna Chakrabarty et al. (2009) gave an approximation loss of O~(mϵ) O(m^ε) in time mO(1/ϵ)m^O(1/ε) for ϵ≥8loglogm/logmε≥ 8 m/ m, where m is the number of items. In particular, every fixed ϵ>0ε>0 gives a polynomial-time welfare guarantee of Ω~(m−ϵ) (m^-ε), whereas taking ϵε near the stated lower bound yields a polylogarithmic approximation in quasipolynomial time. Bateni, Charikar, and Guruswami Bateni et al. (2009) obtained related guarantees for special cases. Bezáková and Dani Bezáková and Dani (2005) showed that achieving any fixed welfare guarantee greater than 1/21/2 is NPNP-hard. For p-mean welfare, Barman et al. Barman et al. (2020) proved that, for every fixed p∈(0,1)p∈(0,1), computing a 1/(m−n+1)1/(m-n+1)-approximation is NPNP-hard even under additive valuations. Their reduction sets m=nm=n, so the required factor is one and the result establishes hardness of exact optimization. They also gave an Ω(1/n) (1/n) welfare guarantee for all p≤1p≤ 1, including subadditive valuations. Chaudhury et al. Chaudhury et al. (2021) obtained a comparable welfare guarantee together with approximate EFX. A separate line of work studies instances with few agent or item types. For a fixed number of machine types, Jansen and Maack Jansen and Maack (2019) gave an EPTAS for maximizing the minimum load, corresponding to ESWESW, extending earlier work for identical agents Woeginger (1997). Their input lists jobs individually, so this running-time guarantee should be distinguished from polynomial time in binary item multiplicities. In the high-multiplicity setting, Nguyen, Elbassioni, and Rothe Nguyen et al. (2024) gave a PTAS for NSWNSW with a fixed number of agent types. They also established NPNP-hardness for ESWESW and NSWNSW with seven item types, using a modification of a scheduling reduction of Koutecký and Zink Koutecký and Zink (2020), and gave a PTAS for ESWESW with two item types. Our hardness results in Section 4 reduce the item-type bound to three for both NSWNSW and ESWESW, and establish hardness with two item types for every fixed finite rational p<1p<1, p≠0p≠ 0. Exact algorithms are available for some smaller type restrictions. Galil and Megiddo Galil and Megiddo (1979) reduce separable concave integer resource allocation to selection in implicit sorted arrays. This underlies the nonzero finite-order case p<1p<1 of the one-item-type algorithm in Section 5.6; we account explicitly for binary agent multiplicities and exact comparisons of fixed-degree algebraic numbers. McCormick, Smallwood, and Spieksma McCormick et al. (2001) give polynomial-time algorithms for high-multiplicity scheduling with two job types, including unrelated machines and compact machine classes in Theorems 5.1–5.2, and covering variants in their Section 6. The two-item-type egalitarian result in Section 5.7 is a consequence of these methods. We provide a direct integer-hull proof and compressed reconstruction for the welfare setting. Related exact allocation results with both numbers of types fixed were established by Nguyen and Rothe Nguyen and Rothe (2023) using integer-cone methods; Appendix C gives a direct application of the underlying theorem of Goemans and Rothvoß Goemans and Rothvoß (2020). Garg et al. Garg et al. (2022) gave a PTAS for p-mean welfare with symmetric agents having identical additive valuations. Our fixed-agent-type result extends this setting to a fixed number of valuation types in the compact input model. Their broader study also treats asymmetric Nash welfare; arbitrary agent weights are outside the model considered here. For identical subadditive valuations, Barman and Sundaram Barman and Sundaram (2020) obtained constant-factor guarantees for p-mean welfare in the demand-oracle model. Viswanathan and Zick Viswanathan and Zick (2025) studied a general framework for fair allocation under matroid-rank valuations, including welfare objectives and connections to strategyproofness. 3 Allocation Setting and Notation For every nonnegative integer r, write [r]:=1,…,r[r]:=\1,…,r\, with [0]:=∅[0]:= . There are n≥1n≥ 1 agents and q≥1q≥ 1 item types. Item type j∈[q]j∈[q] has multiplicity mj∈ℤ≥0m_j _≥ 0, and we put m:=∑j=1qmj,m:= _j=1^qm_j, mmax:=maxj∈[q]mjm_ := _j∈[q]m_j, and :=(m1,…,mq) m:=(m_1,…,m_q). We use the terms item and good interchangeably. When agents are grouped into K≥1K≥ 1 types, A1,…,AKA_1,…,A_K form a partition of [n][n]. Type k∈[K]k∈[K] contains nk:=|Ak|n_k:=|A_k| agents, and n=∑k=1Knkn= _k=1^Kn_k, :=(n1,…,nK) n:=(n_1,…,n_K). Utilities are additive and nonnegative. In a setting with arbitrary agents, ui,j∈ℚ≥0u_i,j _≥ 0 denotes the value that agent i assigns to one item of type j. For every count vector c=(c1,…,cq)∈ℝ≥0qc=(c_1,…,c_q) _≥ 0^q, define ui(c):=∑j=1qui,jcj.u_i(c):= _j=1^qu_i,jc_j. If i∈Aki∈ A_k, the item values depend only on the agent type, and we write them as uk,ju_k,j. In this case, define uk(c):=∑j=1quk,jcj.u_k(c):= _j=1^qu_k,jc_j. A bundle is an integral count vector xi=(xi,1,…,xi,q)∈ℤ≥0qx_i=(x_i,1,…,x_i,q) _≥ 0^q; its utility is ui(xi)u_i(x_i), or equivalently uk(xi)u_k(x_i) when i∈Aki∈ A_k. For a bundle assignment x=(x1,…,xn)x=(x_1,…,x_n), we also write ui(x):=ui(xi)u_i(x):=u_i(x_i). The assignment is an allocation if ∑i=1nxi,j=mj _i=1^nx_i,j=m_j for every j∈[q].j∈[q]. It is a partial allocation if the preceding equalities are replaced by inequalities. Since all utilities are nonnegative, every partial allocation can be completed without decreasing any agent’s utility or the resulting welfare. For finite p>0p>0, and also for −∞<p<0-∞<p<0 when every agent has positive utility, the p-mean social welfare of a bundle assignment x is PSWp(x):=(1n∑i=1nui(xi)p)1/p.PSW_p(x):= ( 1n _i=1^nu_i(x_i)^p )^1/p. We refer to p interchangeably as the welfare parameter or the order of the generalized mean. The limiting cases used in this paper are NSW(x)=PSW0(x):=(∏i=1nui(xi))1/nandESW(x)=PSW−∞(x):=mini∈[n]ui(xi).NSW(x)=PSW_0(x):= ( _i=1^nu_i(x_i) )^1/n (x)=PSW_-∞(x):= _i∈[n]u_i(x_i). For p≤0p≤ 0, we use the standard convention that PSWp(x)=0PSW_p(x)=0 whenever some agent has utility zero. We denote the optimal welfare by OPTp:=maxPSWp(x):x is an allocation.OPT_p:= \PSW_p(x):x is an allocation\. For every finite p, define the transformed utility function ϕp(t):=tp,p>0,logt,p=0,−tp,p<0. _p(t):= casest^p,&p>0,\\ t,&p=0,\\ -t^p,&p<0. cases For p>0p>0, its domain is [0,∞)[0,∞) and ϕp(0):=0 _p(0):=0; for p≤0p≤ 0, it is used only on (0,∞)(0,∞). Throughout, log denotes the natural logarithm. For any bundle assignment on which every term is defined, put Φp(x):=∑i=1nϕp(ui(xi)). _p(x):= _i=1^n _p(u_i(x_i)). For finite p, maximizing PSWpPSW_p is equivalent to maximizing Φp _p: for p>0p>0 this follows from the monotonicity of z↦z1/pz z^1/p, for p=0p=0 from the monotonicity of the logarithm, and for p<0p<0 from the fact that z↦z1/pz z^1/p is decreasing. When p≤0p≤ 0, this equivalence is applied only to positive-utility bundle assignments. For finite p≠0p≠ 0 and any bundle assignment x=(x1,…,xn)x=(x_1,…,x_n) for which the powers are defined, put Qp(x):=∑i=1nui(xi)p.Q_p(x):= _i=1^nu_i(x_i)^p. For positive-utility bundle assignments, put Λ(x):=∑i=1nlogui(xi). (x):= _i=1^n u_i(x_i). Whenever the displayed quantities are defined, they satisfy PSWp(x)=(Qp(x)n)1/p(p∈ℝ∖0),PSW0(x)=exp(Λ(x)n).PSW_p(x)= ( Q_p(x)n )^1/p (p \0\), _0(x)= ( (x)n ). The item multiplicities mjm_j are encoded in binary throughout. All algorithmic results use the fully compact representation: the input lists the K agent types, their utility vectors, and their multiplicities nkn_k in binary. Explicitly listed agents are included as the special case K=nK=n and nk=1n_k=1 for every k∈[K]k∈[K]. In general, both n and m may be exponential in the input length. A compressed allocation lists, for every agent type, each distinct bundle vector together with the number of agents receiving that bundle. The algorithms in Sections 5 and 6, and the exact algorithm recalled in Appendix C, return allocations in this representation. We study the problem PMSW of maximizing PSWpPSW_p. By an exact allocation algorithm, we mean an algorithm that returns an optimal allocation in compressed form. The rational-threshold decision problem asks whether OPTp≥τOPT_p≥τ for a given rational τ. Since welfare values may be irrational, these two tasks require separate complexity statements; see Remark 1. A polynomial-time approximation scheme (PTAS) returns, for every fixed ε∈(0,1) ∈(0,1), an allocation of welfare at least (1−ε)OPTp(1- )OPT_p in polynomial time. An efficient PTAS (EPTAS) has a running time whose polynomial degree is independent of ε , and a fully polynomial-time approximation scheme (FPTAS) runs in time polynomial also in 1/ε1/ . The welfare parameter p is fixed in each algorithmic theorem, and constants may depend on p. When a rational accuracy parameter is part of the input, the running time includes the time needed to read its encoding. We may first replace the requested accuracy εreq∈(0,1) _req∈(0,1) by a dyadic power ε=2−h =2^-h, with h∈ℤ≥1h _≥ 1 chosen so that εreq/2<ε≤εreq _req/2< ≤ _req. The new accuracy has binary encoding length O(1+log(1/ε))O(1+ (1/ )), and a (1−ε)(1- ) guarantee implies the requested guarantee. For the algorithm descriptions and their analyses, ε denotes this preprocessed accuracy; the factor of at most two does not affect the PTAS or FPTAS running-time classifications. Rational approximation of the transformed objectives. The algorithms below replace values of ϕp _p by rational coefficients. The following two lemmas give a common construction and quantify the resulting error, including when multiplicities are encoded in binary. The standard (but technical) proof of the first lemma is given in Appendix A. Lemma 1 (Directed rational approximation). Fix a finite rational p. Given a rational η∈(0,1)η∈(0,1) and a rational v in the domain of ϕp _p, one can compute a rational number ϕ~p,η(v) φ_p,η(v) satisfying vp1+η v^p1+η ≤ϕ~p,η(v)≤vp, ≤ φ_p,η(v)≤ v^p, p>0, p>0, (1) logv−log(1+η) v- (1+η) ≤ϕ~0,η(v)≤logv, ≤ φ_0,η(v)≤ v, p=0, p=0, (2) vp v^p ≤−ϕ~p,η(v)≤(1+η)vp, ≤- φ_p,η(v)≤(1+η)v^p, p<0. p<0. (3) For p>0p>0 and v=0v=0, the output is zero. The running time and output encoding length are polynomial in the binary encoding lengths of v and η, with constants depending on p. Lemma 2 (Weighted objectives and comparisons). Fix a finite rational p and a rational η∈(0,1)η∈(0,1). Let A=((λi,vi))i=1sA=(( _i,v_i))_i=1^s be a finite list of nonnegative rational weights λi _i and rational utilities viv_i in the domain of ϕp _p. Extend the objective notation to such lists by putting W(A):=∑i=1sλi,Qp(A):=∑i=1sλivip(p≠0),Λ(A):=∑i=1sλilogvi(p=0).W(A):= _i=1^s _i, Q_p(A):= _i=1^s _iv_i^p (p≠ 0), (A):= _i=1^s _i v_i (p=0). Using the coefficients from Lemma 1, define Φ~p,η(A):=∑i=1sλiϕ~p,η(vi). _p,η(A):= _i=1^s _i φ_p,η(v_i). This rational sum can be computed in time polynomial in the total encoding length of the list and of η, and it satisfies Qp(A)1+η Q_p(A)1+η ≤Φ~p,η(A)≤Qp(A), ≤ _p,η(A)≤ Q_p(A), p>0, p>0, (4) Λ(A)−W(A)log(1+η) (A)-W(A) (1+η) ≤Φ~0,η(A)≤Λ(A), ≤ _0,η(A)≤ (A), p=0, p=0, (5) Qp(A) Q_p(A) ≤−Φ~p,η(A)≤(1+η)Qp(A), ≤- _p,η(A)≤(1+η)Q_p(A), p<0. p<0. (6) If B is another such list and Φ~p,η(B)≥Φ~p,η(A) _p,η(B)≥ _p,η(A), then Qp(B)≥Qp(A)/(1+η),p>0,Λ(B)≥Λ(A)−W(A)log(1+η),p=0,Qp(B)≤(1+η)Qp(A),p<0. casesQ_p(B)≥ Q_p(A)/(1+η),&p>0,\\ (B)≥ (A)-W(A) (1+η),&p=0,\\ Q_p(B)≤(1+η)Q_p(A),&p<0. cases (7) Proof. Multiplying each bound in Lemma 1 by its nonnegative weight and summing gives (4)–(6). For p>0p>0, the assumed comparison consequently gives Qp(B)≥Φ~p,η(B)≥Φ~p,η(A)≥Qp(A)1+η.Q_p(B)≥ _p,η(B)≥ _p,η(A)≥ Q_p(A)1+η. For p=0p=0, it gives Λ(B)≥Φ~0,η(B)≥Φ~0,η(A)≥Λ(A)−W(A)log(1+η). (B)≥ _0,η(B)≥ _0,η(A)≥ (A)-W(A) (1+η). For p<0p<0, negating the assumed comparison gives Qp(B)≤−Φ~p,η(B)≤−Φ~p,η(A)≤(1+η)Qp(A).Q_p(B)≤- _p,η(B)≤- _p,η(A)≤(1+η)Q_p(A). These are the three claims in (7). Each coefficient has polynomial encoding length by the preceding lemma. Multiplying by a binary-encoded rational weight and summing over the explicitly listed entries preserves polynomial encoding length and takes polynomial time. In particular, integer weights need not be expanded into individual copies, and the numerical size of W(A)W(A) does not introduce an additional running-time factor. ∎ 4 Hardness Results We establish hardness with two item types for every fixed nonzero rational order below one, and with three item types for Nash and egalitarian welfare. The two-type reduction makes each agent choose between two prescribed bundle patterns. The three-type reductions use separate constructions for the Nash and egalitarian objectives. We then consider the complementary restriction of one agent type, where the number of item types is unrestricted. Theorem 1 (Hardness with few item types). For every fixed rational p<1p<1 with p≠0p≠ 0, deciding whether OPTp≥τOPT_p≥τ is NP-hard with two item types. For p=0p=0 and p=−∞p=-∞, the same problem is NP-hard with three item types. These assertions hold for explicitly listed agents, strictly positive integer item values, positive integer item multiplicities, and a positive integer threshold, all encoded in binary. Computing an exact optimal allocation is NP-hard under the same respective restrictions. Proof. The two-type assertion follows from Theorem 2 and Corollary 1. The three-type assertions follow from Theorems 3 and 4, respectively. ∎ We use Subset Sum for the two-type construction. For the three-type constructions, we record the following restricted form of Partition. Lemma 3 (Hardness of Balanced-Equal-Cardinality-Partition). It is NP-hard to decide, for positive integers a1,…,ana_1,…,a_n with both n and A:=∑iaiA:= _ia_i even, whether some set I⊆[n]I [n] satisfies |I|=n/2|I|=n/2 and ∑i∈Iai=A/2 _i∈ Ia_i=A/2. Proof. Given a Partition instance b1,…,btb_1,…,b_t of positive integers with sum B, form the 2t2t numbers 2b1+1,…,2bt+1,1,…,1⏟t copies.2b_1+1,…,2b_t+1, 1,…,1_t copies. Their total is 2B+2t2B+2t. A set of exactly t of these numbers has sum B+tB+t if and only if the original numbers whose shifted copies it contains have sum B/2B/2. Any selected original subset can be padded to cardinality t using the added ones. The construction is polynomial and its number of entries and total sum are even. ∎ 4.1 Two item types and nonzero finite orders We first prove two inequalities whose equality cases are the two bundle patterns used in the reduction. Their quantitative gaps allow us to replace the ideal utility coefficients by rationals while preserving the reduction. The proofs of the following technical lemmas are provided in Appendix A. Lemma 4. Fix p∈(0,1)p∈(0,1). Let a,C,Za,C,Z be positive integers such that a<C≤Za<C≤ Z, and put γ:=1−p,H:=pC+(1−p)a,α:=aγ,β:=H1/p.γ:= 1-pp, H:=pC+(1-p)a, α:=a^γ, β:=H^1/p. For all integers x,y∈0,…,Zx,y∈\0,…,Z\, F(x,y):=(αx+βy)p−x−Cy≤γa.F(x,y):= (α x+β y)^pp-x-Cy≤γ a. (8) Equality holds if and only if (x,y)=(a,0)(x,y)=(a,0) or (x,y)=(0,1)(x,y)=(0,1). For every other such pair, F(x,y)≤γa−δ+,δ+:=minp,1−p2Z2.F(x,y)≤γ a- _+, _+:= \p,1-p\2Z^2. (9) Lemma 5. Fix r>0r>0. Let a,C,Za,C,Z be positive integers such that a<C≤Za<C≤ Z and C<(1+1/r)aC<(1+1/r)a. Put γ:=r+1r,H:=(r+1)a−rC,α:=a−γ,β:=H−1/r.γ:= r+1r, H:=(r+1)a-rC, α:=a^-γ, β:=H^-1/r. For all integers x,y∈0,…,Zx,y∈\0,…,Z\ with x+y>0x+y>0, G(x,y):=(αx+βy)−r+x+Cy≥γa.G(x,y):= (α x+β y)^-rr+x+Cy≥γ a. (10) Equality holds if and only if (x,y)=(a,0)(x,y)=(a,0) or (x,y)=(0,1)(x,y)=(0,1). For every other such pair, G(x,y)≥γa+δ−,δ−:=min1,r2Z⌈r⌉+2.G(x,y)≥γ a+ _-, _-:= \1,r\2Z r +2. (11) Lemma 6. Fix a positive integer s. Given positive rational numbers R0<R1R_0<R_1, one can compute a positive rational number z such that R0<zs<R1R_0<z^s<R_1. in time polynomial in the total binary encoding length of R0R_0 and R1R_1. The encoding length of z is also polynomial. Theorem 2 (Hardness with two item types). For every fixed rational p<1p<1 with p≠0p≠ 0, computing an allocation that maximizes PSWpPSW_p is NP-hard even with two item types, explicitly listed agents, and strictly positive rational item values. The problem of deciding whether the optimal p-mean welfare is at least a given positive rational threshold is NP-hard under the same restrictions. The item multiplicities are encoded in binary. Proof. We reduce from Subset Sum. Let the instance consist of positive integers b1,…,btb_1,…,b_t and an integer target T, where 0≤T≤A:=∑i=1tbi0≤ T≤ A:= _i=1^tb_i. Choose a positive integer D depending only on p, with D≥2D≥ 2; if p=−r<0p=-r<0, also require D>rD>r. Put Q:=D(A+1),ai:=Q+bi(1≤i≤t),ai:=Q(t<i≤2t),C:=Q+A+1,n:=2t,m1:=tQ+T,m2:=t,W:=∑i=1nai=2tQ+A. splitQ&:=D(A+1),\\ a_i&:=Q+b_i (1≤ i≤ t),\\ a_i&:=Q (t<i≤ 2t),\\ C&:=Q+A+1, n:=2t,\\ m_1&:=tQ+T, m_2:=t, W:= _i=1^na_i=2tQ+A. split (12) There are n agents and two item types, with multiplicities m1m_1 and m2m_2. Call an allocation canonical if agent i receives either (ai,0)(a_i,0) or (0,1)(0,1). A full canonical allocation gives the second bundle to exactly t agents and the first bundle to the other t agents. Thus it exists if and only if exactly t of the numbers aia_i sum to m1m_1. By construction, this is equivalent to choosing some of the original numbers bib_i with sum T: any such choice can be padded to cardinality t using the additional t copies of Q. Fix the integer Z:=max2,n,m1,m2,C,a1,…,an.Z:= \2,n,m_1,m_2,C,a_1,…,a_n\. It has polynomial binary encoding length, and every coordinate of every feasible bundle is at most Z. For every i, ai<Ca_i<C and C−ai≥1C-a_i≥ 1. In the negative case, Cai≤CQ=1+1D<1+1r. Ca_i≤ CQ=1+ 1D<1+ 1r. We first construct ideal utility coefficients, which may be irrational, and then replace them by rational coefficients. The ideal instance for 0<p<10<p<1. Put γ:=(1−p)/pγ:=(1-p)/p and, for every agent i, define Hi:=pC+(1−p)ai,αi:=aiγ,βi:=Hi1/p,ui(xi):=αixi,1+βixi,2.H_i:=pC+(1-p)a_i, _i:=a_i^γ, _i:=H_i^1/p, u_i(x_i):= _ix_i,1+ _ix_i,2. By Lemma 4, ui(xi)p−xi,1−Cxi,2≤γai, u_i(x_i)^pp-x_i,1-Cx_i,2≤γ a_i, with equality precisely for the two canonical bundles. Consequently, for an allocation x, Φ(x):=∑i=1nui(xi)p≤U:=γW+m1+Cm2. (x):= _i=1^n u_i(x_i)^pp≤ U:=γ W+m_1+Cm_2. (13) Canonical allocations attain U, whereas every noncanonical allocation has value at most U−δ+U- _+, where δ+=minp,1−p/(2Z2) _+= \p,1-p\/(2Z^2). Maximizing Φ is equivalent to maximizing the p-mean. The ideal instance for p=−r<0p=-r<0. Put γ:=(r+1)/rγ:=(r+1)/r and define Hi:=(r+1)ai−rC,αi:=ai−γ,βi:=Hi−1/r,ui(xi):=αixi,1+βixi,2.H_i:=(r+1)a_i-rC, _i:=a_i^-γ, _i:=H_i^-1/r, u_i(x_i):= _ix_i,1+ _ix_i,2. The preceding bounds imply 0<Hi<ai0<H_i<a_i. For every nonempty bundle, Lemma 5 gives ui(xi)−r+xi,1+Cxi,2≥γai. u_i(x_i)^-rr+x_i,1+Cx_i,2≥γ a_i. Therefore, for an allocation x with no empty bundle, Ψ(x):=∑i=1nui(xi)−r≥L:=γW−m1−Cm2. (x):= _i=1^n u_i(x_i)^-rr≥ L:=γ W-m_1-Cm_2. (14) Canonical allocations attain L, whereas every noncanonical allocation with no empty bundle has cost at least L+δ−L+ _-, where δ−=min1,r/(2Z⌈r⌉+2) _-= \1,r\/(2Z r +2). Furthermore, L=t(2Dr−1)(A+1)+r+1rA−T>0,L=t ( 2Dr-1 )(A+1)+ r+1rA-T>0, (15) because D>rD>r and T≤AT≤ A. Minimizing Ψ is equivalent to maximizing the p-mean on allocations with positive utility for every agent. An allocation with an empty bundle has p-mean zero. Since m1≥nm_1≥ n, a positive allocation exists, obtained by giving one item of the first type to every agent and distributing the remaining items arbitrarily. Hence no optimal allocation has an empty bundle. Rational utility coefficients. We now give the required polynomial-time construction of a rational instance. Let δ denote δ+ _+ or δ− _-, according to the sign of p. We first bound the magnitude of a single transformed objective term on every feasible nonempty bundle. For 0<p<10<p<1, set E:=max⌈γ⌉,⌈1/p⌉E:= \ γ , 1/p \, and F:=2ZE+1p.F:= 2Z^E+1p. Both ideal coefficients are at most ZEZ^E, because ai≤Za_i≤ Z and Hi≤C≤ZH_i≤ C≤ Z. Thus ui(xi)≤2ZE+1u_i(x_i)≤ 2Z^E+1, and ui(xi)p/p≤Fu_i(x_i)^p/p≤ F. For p=−r<0p=-r<0, set E:=⌈γ⌉E:= γ , J:=⌈Er⌉J:= Er , F:=ZJr.F:= Z^Jr. Both ideal coefficients are at least Z−EZ^-E: this is immediate for αi _i, and for βi _i it follows from 0<Hi<ai≤Z0<H_i<a_i≤ Z and 1/r<γ≤E1/r<γ≤ E. Every nonempty integer bundle therefore has utility at least Z−EZ^-E, giving ui(xi)−r/r≤Fu_i(x_i)^-r/r≤ F. Define the rational constant cp:=1,0<p<1,max1,r2⌈r⌉+1,p=−r<0,ρ:=min14,δ8ncpF.c_p:= cases1,&0<p<1,\\ \1,r2 r +1\,&p=-r<0, cases ρ:= \ 14, δ8nc_pF \. For each i, choose positive rational approximations α^i,β^i α_i, β_i satisfying (1−ρ)αi≤α^i≤(1+ρ)αi,(1−ρ)βi≤β^i≤(1+ρ)βi.(1-ρ) _i≤ α_i≤(1+ρ) _i, (1-ρ) _i≤ β_i≤(1+ρ) _i. All ideal coefficients are fixed rational powers of positive rationals with polynomial encoding length. Apply Lemma 1 with accuracy ρ and the corresponding exponent, taking the magnitude of its output when that exponent is negative. The resulting approximation to any such power w lies in [w/(1+ρ),w][w/(1+ρ),w] or in [w,(1+ρ)w][w,(1+ρ)w]. Both intervals lie in [(1−ρ)w,(1+ρ)w][(1-ρ)w,(1+ρ)w], since 1/(1+ρ)≥1−ρ1/(1+ρ)≥ 1-ρ. This gives the required approximations in polynomial time and with polynomial encoding length: the rational ρ has polynomial encoding length, because the exponents occurring in δ and F depend only on the fixed parameter p. Write u^i(xi):=α^ixi,1+β^ixi,2 u_i(x_i):= α_ix_i,1+ β_ix_i,2. For every nonempty bundle xix_i there is an e∈[−ρ,ρ]e∈[-ρ,ρ] with u^i(xi)=(1+e)ui(xi) u_i(x_i)=(1+e)u_i(x_i). If 0<p<10<p<1, then |(1+e)p−1|≤ρ, |(1+e)^p-1 |≤ρ, because (1−ρ)p≥1−ρ(1-ρ)^p≥ 1-ρ and (1+ρ)p≤1+ρ(1+ρ)^p≤ 1+ρ; if p=−r<0p=-r<0, the derivative of z−rz^-r on [1/2,3/2][1/2,3/2] has absolute value at most r2r+1≤cpr2^r+1≤ c_p, and hence |(1+e)−r−1|≤cpρ. |(1+e)^-r-1 |≤ c_pρ. It follows that, for 0<p<10<p<1, rounding changes each summand uip/pu_i^p/p in Φ by at most ρFρ F. For p=−r<0p=-r<0, it changes each summand ui−r/ru_i^-r/r in Ψ by at most cpρFc_pρ F. Thus, in both cases, each summand changes by at most cpρFc_pρ F. Summing these bounds over all n agents shows that the absolute change in Φ or Ψ is at most ncpρF≤δ8,nc_pρ F≤ δ8, by the choice of ρ. For positive p, this also covers an empty bundle, whose term remains zero. For negative p, empty bundles continue to have zero welfare, and all nonempty bundles continue to have positive utility. All constructed item values are strictly positive. Every agent still values the second item type strictly more than the first after approximation; hence the two item types remain distinct. Indeed, in either sign case the ideal ratio βi/αi _i/ _i is greater than ai≥Q≥4a_i≥ Q≥ 4, whereas relative approximation with ρ≤1/4ρ≤ 1/4 multiplies this ratio by a factor of at least (1−ρ)/(1+ρ)≥3/5(1-ρ)/(1+ρ)≥ 3/5. Hardness of computing an optimal allocation. In a yes instance (of Subset Sum), there is a canonical allocation. For 0<p<10<p<1, its rounded transformed objective is at least U−δ/8U-δ/8, while every noncanonical allocation has rounded objective at most U−7δ/8U-7δ/8. For p=−r<0p=-r<0, its rounded transformed cost is at most L+δ/8L+δ/8, while every noncanonical positive allocation has rounded cost at least L+7δ/8L+7δ/8. Thus every optimal allocation of the rational instance is canonical in a yes instance. In a no instance no full canonical allocation exists. An exact allocation algorithm would consequently decide the source instance by checking whether its returned allocation is canonical. This check uses only integer bundle coordinates and does not require comparison of algebraic welfare values. There are only n=2tn=2t explicitly listed agents, so expanding a compressed output for this check also takes polynomial time. Hardness with a rational welfare threshold. For 0<p<10<p<1, choose a positive rational τ satisfying U−7δ8<nτp<U−δ8.U- 7δ8< nτ^pp<U- δ8. (16) The interval is positive since U≥m1≥2U≥ m_1≥ 2 and δ≤1/16δ≤ 1/16. For every allocation x of the rounded instance, PSWp(x)≥τ⟺∑i=1nu^i(xi)p≥nτp.PSW_p(x)≥τ _i=1^n u_i(x_i)^pp≥ nτ^pp. The bounds just established show that a yes instance has an allocation strictly above the threshold, whereas every allocation in a no instance is strictly below it. For p=−r<0p=-r<0, choose a positive rational τ satisfying L+δ8<nτ−r<L+7δ8.L+ δ8< nτ^-rr<L+ 7δ8. (17) For allocations with no empty bundle, PSW−r()≥τ⟺∑i=1nu^i(i)−r≤nτ−r.PSW_-r(A)≥τ _i=1^n u_i(A_i)^-rr≤ nτ^-rr. Again the yes and no instances are strictly separated. Allocations containing an empty bundle have p-mean welfare zero which is strictly less than the positive threshold τ. For completeness, both thresholds can be constructed with polynomially many rational bits. In the case 0<p<10<p<1, write p=s/dp=s/d in lowest terms. If a:=U−7δ/8a:=U-7δ/8 and b:=U−δ/8b:=U-δ/8, then (16) is equivalent to (pan)d<τs<(pbn)d. ( pan )^d<τ^s< ( pbn )^d. For the negative case write r=s/dr=s/d, and put a:=L+δ/8a:=L+δ/8 and b:=L+7δ/8b:=L+7δ/8. Condition (17) is equivalent to (nrb)d<τs<(nra)d. ( nrb )^d<τ^s< ( nra )^d. In both cases the endpoints are positive rationals of polynomial encoding length. Lemma 6 therefore computes the required rational τ in polynomial time. This proves the decision hardness as well as the allocation hardness. ∎ Corollary 1. The hardness assertions of Theorem 2 also hold with strictly positive integer item values. In the decision problem, the welfare threshold may also be required to be a positive integer. Proof. Take the rational instance constructed in the theorem. Let M be the product of the denominators of all its utility coefficients and, for the decision problem, of its threshold τ. Multiplying every utility coefficient by M produces strictly positive integers and preserves the two distinct item types. The p-mean is positively homogeneous: multiplying all utilities by M multiplies every allocation’s welfare by M. Thus the set of optimal allocations is unchanged, and the decision comparison is preserved by replacing τ with the positive integer MτMτ. The binary encoding length of M is at most the sum of the encoding lengths of the original denominators and is therefore polynomial. ∎ 4.2 Three item types and Nash welfare The preceding construction uses the nonzero power of each utility. For Nash welfare we use a different construction: two ordinary item families determine the agents’ choices, and a third item type enforces the required sum within one family. Theorem 3 (Nash-welfare hardness with three item types). For Nash welfare, deciding whether the optimum is at least a specified positive rational threshold is NP-hard with three item types and explicitly listed agents. All item multiplicities, utilities, and the threshold may be required to be positive integers of polynomial binary encoding length. Computing an exact optimal allocation is NP-hard under the same restriction. Proof. We reduce from Balanced-Equal-Cardinality-Partition, which is NP-hard by Lemma 3. Let a1,…,ana_1,…,a_n be positive integers, where n and A:=∑iaiA:= _ia_i are even. We construct one agent for each integer aia_i, so the resulting welfare instance also has exactly n agents. Set s:=n/2,B:=A/2,S:=A+1,R:=A+2,s:=n/2, B:=A/2, S:=A+1, R:=A+2, and δ:=14n3R2S2,L:=2Rδ=8n3R3S2,γ:=1n(L+A)2,ε:=γ8n.δ:= 14n^3R^2S^2, L:= 2Rδ=8n^3R^3S^2, γ:= 1n(L+A)^2, := γ8n. In particular, gcd(R,S)=1 (R,S)=1, L>RAL>RA, and every parameter has polynomial binary encoding length. An ideal construction and its gap. We first analyze real coefficients that will subsequently be replaced by positive rational numbers with a certified error bound. There is one agent for each aia_i, and there are three item types: Item typeMultiplicityValue to agent iFirst ordinarySs−B(L−ai)/SFirst rewardedB(L−ai)/S+1Second ordinaryRsVi/RVi:=Lexp(−ai/L). array[]c|c|cItem type&Multiplicity&Value to agent i\\ ordinary&Ss-B&(L-a_i)/S\\[2.0pt] First rewarded&B&(L-a_i)/S+1\\[2.0pt] Second ordinary&Rs&V_i/R array V_i:=L (-a_i/L). All multiplicities are positive integers. The three value vectors are distinct: the rewarded value exceeds the ordinary first-family value, and Vi/R<L/R<(L−ai)/SV_i/R<L/R<(L-a_i)/S, where the last inequality follows from L>RaiL>Ra_i and R−S=1R-S=1. For an allocation, let fif_i be agent i’s number of first-family items, let gig_i be its number of second-family items, and let rir_i be its number of rewarded items. Define zi:=fi/S+gi/R.z_i:=f_i/S+g_i/R. Full allocations satisfy ∑izi=n _iz_i=n and ∑iri=B _ir_i=B. It suffices to consider full allocations because every item has strictly positive value. The ideal utility for agent i is ui=(L−ai)fi/S+Vigi/R+ri.u_i=(L-a_i)f_i/S+V_ig_i/R+r_i. Since 0<Vi<L0<V_i<L and ri≤fi≤Rzir_i≤ f_i≤ Rz_i, ui≤(L+R)ziu_i≤(L+R)z_i. Suppose first that zi≠1z_i≠ 1 for at least one agent i. Each ziz_i is a nonnegative integer multiple of 1/(RS)1/(RS), and their sum is n. Therefore ∑i(zi−1)2≥2R2S2. _i(z_i-1)^2≥ 2R^2S^2. Let f(t)=tf(t)= t. For 0<t≤n0<t≤ n, since n≥1n≥ 1, f′(t)=−14t3/2≤−14n2.f (t)=- 14t^3/2≤- 14n^2. Taylor’s theorem about t=1t=1, together with f(1)=1f(1)=1 and f′(1)=1/2f (1)=1/2, yields t≤1+t−12−(t−1)28n2(0<t≤n). t≤ 1+ t-12- (t-1)^28n^2 (0<t≤ n). The same inequality holds at t=0t=0. Applying this inequality to each zi∈[0,n]z_i∈[0,n] and averaging, we obtain 1n∑izi≤1+12n∑i(zi−1)−18n3∑i(zi−1)2=1−18n3∑i(zi−1)2≤1−14n3R2S2=1−δ, 1n _i z_i≤ 1+ 12n _i(z_i-1)- 18n^3 _i(z_i-1)^2=1- 18n^3 _i(z_i-1)^2≤ 1- 14n^3R^2S^2=1-δ, where the equality uses ∑izi=n _iz_i=n. For a nonnegative vector v, write NSW(v):=(∏ivi)1/nNSW(v):=( _iv_i)^1/n. By the arithmetic–geometric mean inequality applied to z1,…,zn z_1,…, z_n, NSW(u) (u) ≤(L+R)NSW(z)≤(L+R)(1n∑izi)2≤(L+R)(1−δ)2≤(L+R)(1−δ) ≤(L+R)NSW(z)≤(L+R) ( 1n _i z_i )^2≤(L+R)(1-δ)^2≤(L+R)(1-δ) =L−R−Rδ<L−R, =L-R-Rδ<L-R, where we used ui≤(L+R)ziu_i≤(L+R)z_i, 0<δ<10<δ<1 and Lδ=2RLδ=2R. The inequality remains valid if a coordinate is zero. Write F∗:=nlogL−B/LF_*:=n L-B/L for the ideal target log-product. If all utilities are positive, then F∗−∑ilogui>F∗−nlog(L−R)=nlogL−R−BL≥nR−BL≥1L≥γ,F_*- _i u_i>F_*-n (L-R)=n LL-R- BL≥ nR-BL≥ 1L≥γ, where −log(1−x)≥x- (1-x)≥ x was applied to x=R/Lx=R/L. Thus every nonunit-load allocation has log-product strictly below F∗−γF_*-γ. An allocation with a zero utility has zero Nash welfare and also cannot attain any positive threshold. Suppose now that zi=1z_i=1 for every agent. Coprimality of R and S implies (fi,gi)∈(S,0),(0,R).(f_i,g_i)∈\(S,0),(0,R)\. Let I:=i∈[n]:(fi,gi)=(S,0)I:=\i∈[n]:(f_i,g_i)=(S,0)\ be the set of agents receiving S first-family items and put W:=∑i∈IaiW:= _i∈ Ia_i. The total number of first-family items forces |I|=s|I|=s. Every rewarded item belongs to a first-family agent, so ∑i∈Iui=sL+B−W. _i∈ Iu_i=sL+B-W. For i∉Ii∉ I, logui=logL−ai/L u_i= L-a_i/L. Jensen’s inequality therefore yields ∑ilogui≤slog(L+B−Ws)+(n−s)logL−A−WL. _i u_i≤ s (L+ B-Ws )+(n-s) L- A-WL. The interval between L and L+(B−W)/sL+(B-W)/s is contained in [L−A,L+A][L-A,L+A]. On this interval the second derivative of logt t is at most −1/(L+A)2-1/(L+A)^2. Hence Taylor’s theorem therefore gives ∑ilogui≤nlogL−A−BL−(B−W)22s(L+A)2=F∗−(B−W)2n(L+A)2. _i u_i≤ n L- A-BL- (B-W)^22s(L+A)^2=F_*- (B-W)^2n(L+A)^2. In particular, if W≠BW≠ B, integrality gives a gap (F∗−∑iloguiF_*- _i u_i) of at least γ. If W=BW=B but some first-family utility differs from L, put di:=ui−Ld_i:=u_i-L for i∈Ii∈ I. The deviations did_i are integers satisfying ∑i∈Idi=0. _i∈ Id_i=0. Since they are not all zero, at least one is positive and at least one is negative. Consequently, ∑i∈Idi2≥2.Σ_i∈ Id_i^2≥ 2. Each first-family utility lies in [L−A,L+A][L-A,L+A], because ri≤Br_i≤ B. Taylor’s theorem, together with (logt)′=−1/t2≤−1/(L+A)2( t) =-1/t^2≤-1/(L+A)^2 on this interval, gives logui≤logL+diL−di22(L+A)2. u_i≤ L+ d_iL- d_i^22(L+A)^2. Summing over i∈Ii∈ I and using the preceding observations yields ∑i∈Ilogui≤|I|logL−1(L+A)2. _i∈ I u_i≤|I| L- 1(L+A)^2. Combining this with the previously established bound for the remaining agents, we obtain ∑ilogui≤F∗−1(L+A)2≤F∗−γ, _i u_i≤ F_*- 1(L+A)^2≤ F_*-γ, giving again a log-product gap of γ. If the source instance has a balanced partition I, give each i∈Ii∈ I exactly aia_i rewarded items and S−aiS-a_i ordinary first-family items, and give each remaining agent R second-family items. All multiplicities are met exactly. The first-family utilities are L, and the total log-product is F∗F_*. Conversely, every allocation that is not of this form for some balanced partition has ideal log-product at most F∗−γF_*-γ, or zero Nash welfare. Indeed, consider an allocation with positive Nash welfare which has ∑ilogui>F∗−γ _i u_i>F_*-γ. By the above arguments, we must have zi=1z_i=1 for all i. Letting I be the set of agents receiving S first-family items and putting W:=∑i∈IaiW:= _i∈ Ia_i, we must have W=BW=B and hence, ui=Lu_i=L for every i∈Ii∈ I. Since ui=L−ai+riu_i=L-a_i+r_i, (i∈I),(i∈ I), we must have ri=air_i=a_i. Thus each i∈Ii∈ I receives exactly aia_i rewarded items and S−aiS-a_i ordinary first-family items, while each agent outside I receives exactly R second-family items. Moreover, |I|=s|I|=s and ∑i∈Iai=B _i∈ Ia_i=B, so I is a balanced partition. Replacing the ideal coefficients by rationals. For an odd integer N≥3N≥ 3, define the rational polynomial EN(t):=∑h=0N(−t)h!.E_N(t):= _h=0^N (-t)^hh!. For 0≤t≤10≤ t≤ 1, the alternating-series bounds imply EN(t)≤e−t,e−t−EN(t)≤1(N+1)!≤2−N.E_N(t)≤ e^-t, e^-t-E_N(t)≤ 1(N+1)!≤ 2^-N. Moreover, the odd partial sums are nondecreasing in N, and E3(t)=1−t+t2/2−t3/6≥E3(1)=1/3E_3(t)=1-t+t^2/2-t^3/6≥ E_3(1)=1/3 on [0,1][0,1], so EN(t)≥E3(t)≥1/3E_N(t)≥ E_3(t)≥ 1/3 for odd N≥3N≥ 3. Since 0<EN(t)≤e−t0<E_N(t)≤ e^-t for odd N, the inequality log(1+x)≤x (1+x)≤ x for x≥0x≥ 0 gives 0≤log(e−t)−logEN(t) 0≤ (e^-t)- E_N(t) =log(1+e−t−EN(t)EN(t))≤e−t−EN(t)EN(t)≤3⋅2−N. = \! (1+ e^-t-E_N(t)E_N(t) )≤ e^-t-E_N(t)E_N(t)≤ 3· 2^-N. Choose an odd N≥3N≥ 3 satisfying 3⋅2−N≤ε3· 2^-N≤ . This requires only N=O(logn+log(L+A))N=O( n+ (L+A)). In the actual reduction, replace ViV_i by the positive rational V~i:=L⋅EN(ai/L). V_i:=L· E_N(a_i/L). Use the same first-family values and all the same multiplicities. The second-family item value is now V~i/R V_i/R. The preceding bounds give e−εVi≤V~i≤Vi.e^- V_i≤ V_i≤ V_i. Consequently, for every allocation its actual utility u~i u_i satisfies e−εui≤u~i≤ui.e^- u_i≤ u_i≤ u_i. Indeed, only one nonnegative summand of the additive utility has been reduced. For allocations with positive utilities this implies ∑ilogui−nε≤∑ilogu~i≤∑ilogui. _i u_i-n ≤ _i u_i≤ _i u_i. Define a positive rational Nash-welfare threshold by t∗:=BnL+γ2nt_*:= BnL+ γ2n, and τ~:=L⋅EN(t∗). τ:=L· E_N(t_*). Here both ai/La_i/L and t∗t_* lie in [0,1][0,1]. The same logarithmic error bound applied at t∗t_* gives F∗−5γ8≤nlogτ~≤F∗−γ2.F_*- 5γ8≤ n τ≤ F_*- γ2. If the source instance is a yes-instance, the allocation corresponding to a balanced partition has log-product in the rational instance at least ∑ilogu~i≥F∗−nε=F∗−γ8, _i u_i≥ F_*-n =F_*- γ8, which is strictly above nlogτ~n τ. If the source instance is a no-instance, every positive-welfare allocation has ideal log-product at most F∗−γF_*-γ. Its actual log-product is no larger, and is therefore strictly below nlogτ~n τ. Zero-welfare allocations also fall below the positive threshold. This proves the desired equivalence using rational coefficients and a rational threshold. Encoding length and exact optimization. All exponents in the Taylor polynomials are polynomially bounded in the input bit length. Exact rational evaluation at a rational t uses numerators and denominators with O(Nbits(t)+NlogN)O(N\,bits(t)+N N) bits; for example, a common denominator is den(t)NN!den(t)^NN!. Thus the reduction constructs all coefficients and the threshold in polynomial time and with polynomial encoding length. For a yes-instance, the rational perturbation leaves a strict gap between partition allocations and every other allocation. Hence an exact optimal allocation reveals a balanced partition by checking zi=1z_i=1, the first-family set I, and ∑i∈Iai=B _i∈ Ia_i=B. These are rational and integer checks and require no exact logarithm or exponential evaluation. Multiplying all utilities and the threshold by a common product of their denominators makes every utility and the threshold a positive integer of polynomial bit length, without changing the answer. This proves all assertions. ∎ 4.3 Three item types and egalitarian welfare For the egalitarian objective, a common price on the three item types forces every feasible bundle to have a prescribed price. A small rational perturbation leaves exactly two threshold-feasible bundles at that price for each agent. Theorem 4 (Egalitarian-welfare hardness with three item types). Deciding whether an allocation of egalitarian welfare at least a specified positive rational threshold exists is NP-hard with three item types and explicitly listed agents. The item multiplicities, utilities, and threshold can all be required to be positive integers of polynomial binary encoding length. Computing an exact optimal allocation is NP-hard under the same restriction. The utility matrix may be required to have rank at most two, and all agents may be required to have the same strict ranking of the three item types. Proof. We reduce from Balanced-Equal-Cardinality-Partition, which is NP-hard by Lemma 3. Let a1,…,ana_1,…,a_n be positive integers, where n and A:=∑iaiA:= _ia_i are even. Set s:=n/2,B:=A/2,M:=3A+1,ε:=1M2,hi:=M(M+1−ai).s:=n/2, B:=A/2, M:=3A+1, := 1M^2, h_i:=M(M+1-a_i). There is one agent for each source integer and there are three item types. Their multiplicities and the value of one item to agent i are Item typeMultiplicityValue to agent i1s(M+1)−BM/hi2sM−3B(M+1+εai)/hi3B(2M+3−ε(M−3ai))/hi. array[]c|c|cItem type&Multiplicity&Value to agent i\\ 1&s(M+1)-B&M/h_i\\[2.0pt] 2&sM-3B&(M+1+ a_i)/h_i\\[2.0pt] 3&B& (2M+3- (M-3a_i) )/h_i. array The welfare threshold is 11. All multiplicities are positive integers: s≥1s≥ 1, B=A/2>0B=A/2>0, M+1>BM+1>B, and M>3BM>3B. All values are positive rationals: hi>0h_i>0 and 0<M−3ai<M0<M-3a_i<M, so the third numerator is greater than 2M+3−1/M>02M+3-1/M>0. Moreover, for every agent the three item values are strictly increasing in the displayed type order, since M<M+1+εai<2M+3−ε(M−3ai).M<M+1+ a_i<2M+3- (M-3a_i). Thus the construction has exactly three distinct item types. If v1,v2,v3v_1,v_2,v_3 denote its utility-column vectors, then v3=3v2−(1+ε)v1,v_3=3v_2-(1+ )v_1, so the utility matrix has rank at most two. A common resource price forces equality. For a bundle (x,y,z)∈ℤ≥03(x,y,z) _≥ 0^3, define its price C(x,y,z):=Mx+(M+1)y+(2M+3)z.C(x,y,z):=Mx+(M+1)y+(2M+3)z. This price is independent of the agent. Let (xi,yi,zi)(x_i,y_i,z_i) be the bundle assigned to agent i. Agent i obtains utility at least 11 precisely when C(xi,yi,zi)+ε(aiyi−(M−3ai)zi)≥hi.C(x_i,y_i,z_i)+ (a_iy_i-(M-3a_i)z_i )≥ h_i. (18) Every bundle satisfying this inequality has price at least hih_i. Otherwise, since C(xi,yi,zi)C(x_i,y_i,z_i) and hih_i are integers, C(xi,yi,zi)≤hi−1.C(x_i,y_i,z_i)≤ h_i-1. Moreover, (M+1)yi≤C(xi)<hi≤M(M+1),(M+1)y_i≤ C(x_i)<h_i≤ M(M+1), so yi<My_i<M. Using ai≤Aa_i≤ A and M=3A+1M=3A+1, we obtain εaiyi≤AM<1. a_iy_i≤ AM<1. Since M−3ai>0M-3a_i>0 and zi≥0z_i≥ 0, it follows that C(xi,yi,zi)+ε(aiyi−(M−3ai)zi)≤hi−1+εaiyi<hi,C(x_i,y_i,z_i)+ (a_iy_i-(M-3a_i)z_i )≤ h_i-1+ a_iy_i<h_i, contradicting (18). Hence C(xi,yi,zi)≥hiC(x_i,y_i,z_i)≥ h_i. The total price of all available items is M(s(M+1)−B)+(M+1)(sM−3B)+(2M+3)B=nM(M+1)−MA=∑i=1nhi. M (s(M+1)-B )+(M+1)(sM-3B)+(2M+3)B=nM(M+1)-MA=Σ_i=1^nh_i. Feasibility therefore implies ∑i=1nhi≤∑i=1nC(xi,yi,zi)≤∑i=1nhi. _i=1^nh_i≤ _i=1^nC(x_i,y_i,z_i)≤ _i=1^nh_i. Thus ∑i=1n(C(xi,yi,zi)−hi)=0. _i=1^n (C(x_i,y_i,z_i)-h_i )=0. Each summand is nonnegative, so every summand is zero. Consequently, C(xi,yi,zi)=hifor every i.C(x_i,y_i,z_i)=h_i every i. Furthermore, every item must be assigned: leaving any item unassigned would make the upper bound on the total assigned price strict, since all three item prices are positive. Every agent has exactly two feasible bundles at its forced price. Fix agent i and an integer bundle with C(xi,yi,zi)=hiC(x_i,y_i,z_i)=h_i. Reducing this equality modulo M shows that yi+3zi=kMy_i+3z_i=kM for some integer k≥0k≥ 0. Substitution gives yi=kM−3zi,xi=(M+1)(1−k)−ai+zi.y_i=kM-3z_i, x_i=(M+1)(1-k)-a_i+z_i. (19) If k≥2k≥ 2, nonnegativity of xix_i and yiy_i would imply (M+1)(k−1)+ai≤zi≤kM3.(M+1)(k-1)+a_i≤ z_i≤ kM3. This is impossible, because the left endpoint exceeds the right endpoint by (2k−3)M3+(k−1)+ai>0. (2k-3)M3+(k-1)+a_i>0. Thus k is either zero or one. When k=0k=0, nonnegativity forces yi=zi=0y_i=z_i=0, giving the bundle Pi:=(M+1−ai,0,0).P_i:=(M+1-a_i,0,0). When k=1k=1, (19) and nonnegativity of xix_i and yiy_i give (xi,yi,zi)=(zi−ai,M−3zi,zi)(x_i,y_i,z_i)=(z_i-a_i,M-3z_i,z_i), where ai≤zi≤⌊M/3⌋.a_i≤ z_i≤ M/3 . On such a bundle, the utility of agent i is ui=1+εhi(aiyi−(M−3ai)zi)=1+εhi(M(ai−zi)).u_i=1+ h_i (a_iy_i-(M-3a_i)z_i )=1+ h_i (M(a_i-z_i) ). where we use C(xi,yi,zi)=hiC(x_i,y_i,z_i)=h_i. As zi≥aiz_i≥ a_i, this utility is at most 11, and it is at least 11 if and only if zi=aiz_i=a_i. Thus, among the bundles in the case k=1k=1, exactly one meets the utility threshold, namely, Qi:=(0,M−3ai,ai).Q_i:=(0,M-3a_i,a_i). Both PiP_i and QiQ_i are nonnegative integer bundles and give agent i utility exactly 11. Thus these are precisely its two feasible bundles at price hih_i. Recovering the balanced partition. In a threshold-feasible allocation, let I be the agents receiving QiQ_i; all remaining agents receive PiP_i. The constraint of type 3 items gives ∑i∈Iai=B. _i∈ Ia_i=B. The constraint of type 2 items then gives ∑i∈I(M−3ai)=M|I|−3B=sM−3B, _i∈ I(M-3a_i)=M|I|-3B=sM-3B, so |I|=s|I|=s. Hence I is a balanced partition. Conversely, if I is a balanced partition, give QiQ_i to each agent i∈Ii∈ I and PiP_i to every other agent. The type 2 and type 3 constraints are met by the two balanced-partition equalities. The type 1 usage is ∑i∉I(M+1−ai)=(n−s)(M+1)−(A−B)=s(M+1)−B,Σ_i∉ I(M+1-a_i)=(n-s)(M+1)-(A-B)=s(M+1)-B, which also matches its stock. Every agent obtains utility exactly 11. This proves both directions of the reduction. Encoding length and exact optimization. Every stock, numerator, and denominator has polynomial binary encoding length. There are only n explicitly listed agents, and the construction uses rational arithmetic on integers with O(log(n+1)+log(A+1))O( (n+1)+ (A+1)) bits. Multiplying all utility coefficients and the threshold by the product of their denominators converts them to positive integers. The encoding length of that common multiplier is at most the sum of the individual denominator lengths, so this conversion remains polynomial. An exact optimal-allocation algorithm would decide the source problem by testing whether every returned utility is at least the threshold. These are exact rational comparisons of polynomial encoding length. Hence exact allocation optimization is NP-hard as well. ∎ The reductions with a fixed number of item types establish ordinary NP-hardness; they do not establish strong NP-hardness. Their numerical gaps need not be inverse-polynomial in the binary input length. Thus these results are consistent with the FPTAS in Section 5. 4.4 One agent type and an unrestricted number of item types Theorem 5 (Hardness with one agent type). For every fixed p∈(ℚ∩(−∞,1))∪−∞p∈(Q∩(-∞,1))∪\-∞\, the decision problem of determining whether OPTp≥τOPT_p≥τ is strongly NP-hard, even when there is only one agent type. Consequently, exact maximization of p-mean social welfare is strongly NP-hard under the same restriction. The reduction uses positive integer utilities; the number of item types is not fixed. Proof. We reduce from 3-Partition. An instance consists of positive integers a1,…,a3ra_1,…,a_3r and B such that ∑j=13raj=rB _j=1^3ra_j=rB and B4<aj<B2 B4<a_j< B2 for every j∈[3r].j∈[3r]. The question is whether the numbers can be partitioned into r triples, each having sum B. Under these restrictions, 3-Partition is strongly NP-complete. Construct an instance with r agents of a single agent type. For every j∈[3r]j∈[3r], introduce one item of value aja_j to every agent. Equivalently, one may initially regard each item as a type of multiplicity one and then merge types having the same value. Thus there are at most 3r3r item types, all utilities are positive integers, and the decision threshold is τ:=Bτ:=B. Let x be an allocation and put vi:=u1(xi)v_i:=u_1(x_i) for every i∈[r]i∈[r]. Because x assigns every item exactly once, ∑i=1rvi=∑j=13raj=rB. _i=1^rv_i= _j=1^3ra_j=rB. Thus the arithmetic mean of v1,…,vrv_1,…,v_r is B. First let p<1p<1 be finite. If p≤0p≤ 0 and some vi=0v_i=0, then the zero-utility convention gives PSWp(x)=0<BPSW_p(x)=0<B. Otherwise, the generalized-mean inequality gives PSWp(x)≤BPSW_p(x)≤ B. Since p<1p<1, equality holds if and only if v1=⋯=vr=Bv_1=·s=v_r=B. For p=−∞p=-∞, PSW−∞(x)=minivi≤BPSW_-∞(x)= _iv_i≤ B; moreover, equality implies vi≥Bv_i≥ B for every i, and the displayed sum then forces vi=Bv_i=B for every i. Hence, for every value of p in the statement, PSWp(x)≤BPSW_p(x)≤ B with equality if and only if vi=Bv_i=B for every i∈[r]i∈[r]. If the 3-Partition instance is a yes-instance, assign the three items corresponding to each triple to one agent. Every agent then has utility B, so the resulting allocation meets the threshold. Conversely, suppose that PSWp(x)≥BPSW_p(x)≥ B. The preceding equivalence gives vi=Bv_i=B for every i∈[r]i∈[r]. As B4<aj<B2 B4<a_j< B2, each bundle contains exactly three items: a bundle containing at most two items has value strictly less than B, whereas a bundle containing at least four items has value strictly greater than B. Because every item is allocated exactly once, the r bundles yield a partition into triples of sum B. Thus the original 3-Partition instance is a yes-instance. The reduction is polynomial and copies the numerical values of the 3-Partition instance without increasing them. It therefore remains a polynomial reduction when the source integers are polynomially bounded, which proves strong NP-hardness. The claim for computing an exact optimal allocation does not require an exact comparison of irrational welfare values. Given such an allocation, check whether every positive-multiplicity bundle has integer utility B. By the equivalence proved above, this happens if and only if the source instance is a yes-instance, and the check takes polynomial time for both explicit and compressed allocations. ∎ Strong hardness does not by itself rule out an FPTAS for a real-valued objective. For the preceding reduction, an inverse-polynomial gap below the optimum of a yes-instance gives the required approximation barrier. Corollary 2 (No FPTAS with one agent type). For every fixed p∈(ℚ∩(−∞,1))∪−∞p∈(Q∩(-∞,1))∪\-∞\, maximizing p-mean social welfare admits no FPTAS unless = P= NP, even with one agent type and positive integer utilities. Here the number of item types is unrestricted. Proof. Use the instances constructed in the proof of Theorem 5, restricting the source 3-Partition instances to the strongly NP-hard family in which B is polynomially bounded in the source input length. There are r identical agents and 3r3r items of total value rBrB. For every allocation x, the utilities vi:=u1(xi)v_i:=u_1(x_i) are nonnegative integers satisfying ∑i=1rvi=rB _i=1^rv_i=rB. The source instance is a yes-instance if and only if an allocation with vi=Bv_i=B for every i exists. First fix a finite rational p<1p<1 and define the positive rational constants and the rational gap parameter α:=1+maxp,02,c:=α(1−α),δ:=cr3B2.α:= 1+ \p,0\2, c:=α(1-α), δ:= cr^3B^2. (20) Thus p<α<1p<α<1 and α≥1/2α≥ 1/2. Normalize the utilities by setting zi:=vi/Bz_i:=v_i/B. Then 0≤zi≤r0≤ z_i≤ r and ∑i=1rzi=r _i=1^rz_i=r. If the utilities are not all equal to B, the integer deviations vi−Bv_i-B sum to zero and include both a positive integer and a negative integer. Consequently, ∑i=1r(zi−1)2=1B2∑i=1r(vi−B)2≥2B2. _i=1^r(z_i-1)^2= 1B^2 _i=1^r(v_i-B)^2≥ 2B^2. (21) The function f(t):=tαf(t):=t^α satisfies, for 0<t≤r0<t≤ r, f′(t)=−ctα−2≤−cr2,f (t)=-c\,t^α-2≤- cr^2, where we use r≥1r≥ 1. By continuity, the inequality also holds at t=0t=0. Taylor’s theorem around 11 gives tα≤1+α(t−1)−c2r2(t−1)2(0≤t≤r).t^α≤ 1+α(t-1)- c2r^2(t-1)^2 (0≤ t≤ r). (22) Averaging this inequality at z1,…,zrz_1,…,z_r, the linear terms cancel. For every allocation whose utilities are not all B, (21) therefore implies 1r∑i=1rziα≤1−c2r3∑i=1r(zi−1)2≤1−δ. 1r _i=1^rz_i^α≤ 1- c2r^3 _i=1^r(z_i-1)^2≤ 1-δ. (23) By monotonicity of generalized means in their order and by homogeneity, PSWp(x)≤PSWα(x)=B(1r∑i=1rziα)1/α≤B(1−δ)1/α≤B(1−δ).PSW_p(x) _α(x)=B ( 1r _i=1^rz_i^α )^1/α≤ B(1-δ)^1/α≤ B(1-δ). (24) The first inequality also holds under the zero-utility convention when p≤0p≤ 0 and some vi=0v_i=0. The last inequality uses 0<δ<10<δ<1 and 1/α>11/α>1. Suppose an FPTAS exists for this fixed p. Run it on the constructed instance with the rational accuracy parameter ε:=δ2=c2r3B2. := δ2= c2r^3B^2. On a yes-instance, OPTp=BOPT_p=B, so the returned allocation x satisfies PSWp(x)≥(1−δ/2)B>(1−δ)B.PSW_p(x)≥(1-δ/2)B>(1-δ)B. By (24), its utilities must all equal B. On a no-instance, no such allocation exists. Thus one can decide the source instance by checking whether every utility in the returned allocation equals the integer B. This check also applies to a compressed allocation by checking every bundle with positive multiplicity, and requires no evaluation or comparison of irrational welfare values. Since p is fixed, c is a fixed positive rational, and 1ε=2r3B2c 1 = 2r^3B^2c is polynomially bounded on the chosen source family. The construction, the accuracy encoding, the FPTAS running time, and the final integer checks are therefore polynomial in the source input length. This would imply = P= NP. For p=−∞p=-∞, use the same reduction and set ε:=1/(2B) :=1/(2B). Every allocation whose utilities are not all B has some integer utility at most B−1B-1, and hence has egalitarian welfare at most B−1B-1. On a yes-instance an FPTAS would return welfare at least (1−1/(2B))B=B−1/2(1-1/(2B))B=B-1/2, forcing every utility to equal B. Checking the integer utilities again decides 3-Partition in polynomial time, since 1/ε=2B1/ =2B is polynomially bounded. ∎ The restriction in Corollary 2 fixes the number K of agent types, not the number n of agents: the reduction has K=1K=1 but n=rn=r grows with the source instance. It also allows the number q of item types to grow. Thus the corollary does not preclude an FPTAS when q is fixed, nor does it establish the same obstruction for a fixed number of agents. 5 An FPTAS for p-Mean Social Welfare with a Fixed Number of Item Types In this section, the number q of item types is fixed, whereas the number K of agent types is unrestricted. Both the item multiplicities mjm_j and the agent multiplicities nkn_k are encoded in binary. In particular, the total number n of agents can be exponential in the input length. We use the notation and welfare definitions introduced in Section 3. Theorem 6. For every fixed number q of item types and every fixed p∈ℚ∪−∞p ∪\-∞\, maximizing p-mean social welfare under additive nonnegative rational utilities admits an FPTAS in the fully compact model. More precisely, for every rational ε∈(0,1) ∈(0,1), the algorithm returns a compressed allocation x such that PSWp(x)≥(1−ε)OPTpPSW_p(x)≥(1- )OPT_p in time polynomial in the compact input length, the supplied encoding length of the accuracy parameter, and 1/ε1/ . The degree of the polynomial depends only on q and p, and is independent of K, n, and ε . 5.1 Algorithmic overview The algorithm works with groups of identical agents throughout. We first show that an optimum can be chosen so that agents of each type receive at most 2q2^q distinct bundles. This statement concerns the existence of a suitable optimum; it does not require us to compute its bundles or their multiplicities. We next partition each type into a polynomial number of blocks, each containing a power-of-two number of agents. The partition depends only on nkn_k and can represent every distribution of nkn_k agents among at most 2q2^q bundles. Consequently, after rounding bundles to a geometric grid, a near-optimal allocation can be represented by assigning one configuration to each block. The main difficulty is that even one block may contain exponentially many agents. We address it by distinguishing the number of items received by an individual agent from the aggregate consumption of a block. For each item coordinate, we guess an anchor block with maximum aggregate consumption among blocks whose individual coordinate is large. A null anchor records the case in which no individual coordinate is large. The anchor configurations are fixed, and all other configurations are required to respect the guessed bounds on large coordinates. Small individual coordinates need not satisfy an aggregate anchor bound. We round aggregate resource consumptions down to suitable powers of two and process the remaining blocks in nonincreasing order of size. The dynamic program records exact residual capacities only while they could restrict the remaining blocks. Once a residual capacity is at least an upper bound on the consumption of every remaining suffix assignment, the coordinate is replaced by the symbol FREE. This certificate remains valid at later layers. Divisibility of the power-of-two block sizes bounds the number of residual capacities below the suffix bound, including in coordinates with a null anchor. Resource rounding may introduce a small excess. We remove this excess from the relevant anchor block, distributing the deletions as evenly as possible among its agents. An anchor is used only for a large individual coordinate, so every agent retains a multiplicative fraction of each repaired coordinate and hence of her utility. In particular, the repair preserves positive utility when p≤0p≤ 0. The repair, completion, and output are performed on compressed groups, without expanding any block. Algorithm 1 summarizes the construction. Algorithm 1 Compact FPTAS for a fixed number of item types 1: Agent types (nk,(uk,j)j∈[q])k∈[K](n_k,(u_k,j)_j∈[q])_k∈[K], item multiplicities (mj)j∈[q](m_j)_j∈[q], fixed p, and accuracy ε 2: Delete empty types; handle the instance with no items; choose η as in (26) 3: if p≤0p≤ 0 and the positive-utility flow test fails then 4: return a compressed allocation assigning all goods to one agent 5: Construct the universal dyadic blocks, the configuration set C, and the rational objective coefficients 6: Set Vbest←−∞V^best←-∞ 7: for each guess of a null anchor or an anchored block and configuration for every coordinate do 8: Check consistency, original capacities, and all fixed-block coordinate bounds; discard a guess that fails a check 9: Construct residual admissible sets; discard a guess with an empty set 10: Choose the powers of two Δj _j, order the residual blocks, and compute the suffix bounds Mt,jM_t,j 11: Run Algorithm 2 for this guess 12: if a profile is returned with label V>VbestV>V^best then 13: Store this profile and its guess; set Vbest←V^best← V 14: Repair each excess by balanced deletions from its anchor block 15: Give all leftover items to one agent, and merge identical bundles within each type 16: return the resulting compressed allocation 5.2 Sparse allocations and universal blocks The two structural lemmas below allow us to replace the agents by a polynomial number of blocks while retaining a suitable optimum. Lemma 7. If q≥1q≥ 1, there is an optimal allocation in which each agent type receives at most s:=2qs:=2^q distinct bundle vectors. Proof. First suppose that p<1p<1 is finite and that, when p≤0p≤ 0, an allocation with positive welfare exists. Among all optimal allocations choose one minimizing ∑i=1n‖xi‖22 _i=1^n\|x_i\|_2^2. Such a choice exists because the set of allocations is finite. Suppose that two distinct bundles x,yx,y assigned to agents of the same type have the same parity in every coordinate. Replace these two bundles by (x+y)/2(x+y)/2 and (x+y)/2(x+y)/2. Both new bundles are integral, and their total consumption is unchanged. Because the agents have the same additive utility function, their new utilities both equal the average of their previous utilities. For p<1p<1, the function ϕp _p is concave on its domain. Thus the sum of the two transformed utilities does not decrease. For p≤0p≤ 0, the two original utilities are positive, so the average remains in the domain of ϕp _p. The new allocation therefore remains optimal. On the other hand, ‖x‖22+‖y‖22−2‖x+y2‖22=12‖x−y‖22>0,\|x\|_2^2+\|y\|_2^2-2 \| x+y2 \|_2^2= 12\|x-y\|_2^2>0, contradicting the choice of the secondary objective. There is consequently at most one distinct bundle in each of the 2q2^q parity classes. For p=−∞p=-∞ and positive optimum, use the same secondary objective. Averaging two utilities cannot decrease their minimum, so the same argument applies. If p≤0p≤ 0 and the optimum is zero, every allocation is optimal. Assigning all goods to one agent and giving empty bundles to all other agents uses at most two distinct bundles within any type. Finally, suppose that p≥1p≥ 1. Starting with an optimum, combine all bundles assigned to a given type into the bundle of one agent of that type, and give its other agents empty bundles. If the original utilities within this type are v1,…,vnkv_1,…,v_n_k, its contribution to QpQ_p changes from ∑ivip _iv_i^p to (∑ivi)p( _iv_i)^p, which is no smaller. Doing this for every type preserves optimality and leaves at most two distinct bundles per type. Since q≥1q≥ 1, we have 2≤2q2≤ 2^q. ∎ A histogram on at most s categories is a vector (h1,…,ht)∈ℤ≥0t(h_1,…,h_t) _≥ 0^t, where t≤st≤ s, whose jjth coordinate records the number of units in category j. Its total multiplicity is ∑j=1thj _j=1^th_j. We may append zero coordinates to regard it as a vector of length s. Here, the categories will represent distinct bundle vectors assigned to agents of the same type, and each coordinate will record the number of agents receiving the corresponding bundle. Lemma 8. For every positive integer N and integer s≥2s≥ 2, one can compute a partition of N into O(s(1+logN))O(s(1+ N)) powers of two with the following property: every histogram on at most s categories with total multiplicity N can be represented by assigning one category to every part of the partition. The partition can be computed in time polynomial in s and the binary encoding length of N. Proof. Set N0:=N_0:=N. At level ℓ≥0 ≥ 0, if Nℓ<sN_ <s, set aℓ:=Nℓa_ :=N_ , create aℓa_ parts of size 2ℓ2 , and terminate. Otherwise, choose the unique aℓ∈s−1,sa_ ∈\s-1,s\ satisfying aℓ≡Nℓ(mod2)a_ ≡ N_ 2, create aℓa_ parts of size 2ℓ2 , and set Nℓ+1:=Nℓ−aℓ2.N_ +1:= N_ -a_ 2. Since aℓ≤Nℓa_ ≤ N_ and aℓ≡Nℓ(mod2)a_ ≡ N_ 2, the remaining total Nℓ+1=(Nℓ−aℓ)/2N_ +1=(N_ -a_ )/2 is a nonnegative integer. Rearranging the recurrence and multiplying by 2ℓ2 gives aℓ2ℓ=2ℓNℓ−2ℓ+1Nℓ+1.a_ 2 =2 N_ -2 +1N_ +1. Let L be the terminal level, where aL=NLa_L=N_L. Summing over the nonterminal levels and adding the terminal contribution yields ∑ℓ=0Laℓ2ℓ=N0−2LNL+2LaL=N0=N. _ =0^La_ 2 =N_0-2^LN_L+2^La_L=N_0=N. Thus the constructed parts have total size exactly N. At every nonterminal level Nℓ+1≤Nℓ/2N_ +1≤ N_ /2, so there are at most 1+⌊log2N⌋1+ _2N levels containing a positive residual. Each level contributes at most s parts. The recurrence and the output use binary integers of O(1+logN)O(1+ N) bits. We now show that the constructed partition can represent every histogram with at most s categories and total N. Pad the given histogram with zero entries so that it has exactly s coordinates. At a nonterminal level, let o be the number of odd-valued entries of the current histogram, whose total is NℓN_ . Then o≡Nℓ≡aℓ(mod2)o≡ N_ ≡ a_ 2 and o≤aℓo≤ a_ . Indeed, o≤so≤ s, and when aℓ=s−1a_ =s-1 the value o=so=s is excluded by parity. Remove one unit from each odd entry. The remaining entries are even. Next, remove another aℓ−oa_ -o units in pairs, each pair consisting of two units from the same category. Equivalently, perform (aℓ−o)/2(a_ -o)/2 operations, each subtracting 22 from an entry that is at least 22. All entries remain nonnegative and even. There are enough pairs because Nℓ−o2≥aℓ−o2. N_ -o2≥ a_ -o2. Assign the categories of these aℓa_ removed units to the parts created at this level. Halve the remaining histogram. It is again an integral histogram, now of total Nℓ+1N_ +1, to which the same argument applies. At a terminal level assign one part to each remaining unit. Restoring the factors 2ℓ2 shows that the parts assigned to each category sum to its original multiplicity. ∎ A numerical example illustrating the proof of Lemma 8 is given in appendix B Apply Lemma 8 to each nonempty agent type k, with N=nkN=n_k and s=2qs=2^q. Each resulting part of size b represents a block of b agents of type k. Let H be the total number of resulting blocks. Block h∈[H]h∈[H] has type k(h)k(h) and size bhb_h, where bhb_h is a power of two. These block identifiers are fixed throughout the algorithm. Writing nmax:=maxknkn_ := _kn_k, we have H=Oq(∑k=1Klog(1+nk))=Oq(Klog(1+nmax)).H=O_q ( _k=1^K (1+n_k) )=O_q (K (1+n_ ) ). (25) In particular, H is polynomial in the compact input length. Moreover, ∑h:k(h)=kbh=nk _h:k(h)=kb_h=n_k for every k, and ∑h=1Hbh=n. _h=1^Hb_h=n. All agents in a block will receive the same bundle: assigning a bundle x to a block h means giving x to each of its bhb_h agents, consuming bhxb_hx items in total. The block sizes are fixed by the lemma; the bundle assigned to each block will be chosen by the algorithm. Individual agents within a block are used only for the analysis and the final compressed repair. 5.3 Configurations and objective coefficients We now give the remaining construction and prove Theorem 6. Throughout, p and q are fixed. Delete agent types and item types of multiplicity zero, and relabel the retained types. If there are no items, return the empty bundle with multiplicity nkn_k for each retained agent type. Henceforth, q≥1q≥ 1, mj≥1m_j≥ 1, and nk≥1n_k≥ 1. Choose the rational internal accuracy η:=ε3+1/|p|,p∈ℚ∖0,ε/4,p=0,ε/3,p=−∞.η:= cases 3+1/|p|,&p \0\,\\[5.69054pt] /4,&p=0,\\ /3,&p=-∞. cases (26) Thus 0<η<1/30<η<1/3 and η=Θp(ε)η= _p( ). By the accuracy convention of Section 3, η has encoding length Op(1+log(1/ε))O_p(1+ (1/ )). Positive-utility feasibility for p≤0p≤ 0. For p≤0p≤ 0, construct a flow network with a source, an item-type vertex for each j∈[q]j∈[q], an agent-type vertex for each k∈[K]k∈[K], and a sink. The source-to-item arc has capacity mjm_j. The arc from item type j to agent type k is present if and only if uk,j>0u_k,j>0, and has capacity nkn_k. The arc from agent type k to the sink has capacity nkn_k. All capacities are integral and encoded in binary. An integral flow of value n supplies each type k with nkn_k positively valued items, which can be distributed one per agent of that type. Conversely, from an allocation with all utilities positive, choose one positively valued item from each agent’s bundle. Counting these chosen items by item type and agent type gives an integral flow of value n. Thus positive utility is feasible exactly when the maximum flow is n. This test uses K+q+2K+q+2 vertices and at most Kq+K+qKq+K+q arcs and is polynomial in the compact input length. If the test fails, the optimum is zero under the convention for p≤0p≤ 0. Return all items in the bundle of one agent, with empty bundles for the remaining agents, using binary-encoded group multiplicities. We may therefore assume below that positive welfare is feasible whenever p≤0p≤ 0. Geometric configurations. For every item type j, let Γj:=0∪(⌈(1+η)ℓ⌉:ℓ=0,…,⌈log1+ηmj⌉∩1,…,mj). _j:=\0\∪ ( \ (1+η) : =0,…, _1+ηm_j \∩\1,…,m_j\ ). Duplicate values are removed. The intersection removes values exceeding the available multiplicity. A configuration is a vector C=(c1(C),…,cq(C))∈:=∏j=1qΓjC=(c_1(C),…,c_q(C)) := _j=1^q _j. Put S:=||S:=|C| and ℓm:=1+log(1+mmax) _m:=1+ (1+m_ ). Since log(1+η)≥η/2 (1+η)≥η/2, |Γj|≤2+⌈log1+ηmj⌉| _j|≤ 2+ _1+ηm_j , and S=Oq((ℓm/η)q).S=O_q (( _m/η)^q ). The algorithm generates Γj _j exactly by successive rational multiplication by 1+η1+η, taking ceilings, and stopping when the ceiling exceeds mjm_j. No evaluation of a logarithm is needed. For an integer a∈0,…,mja∈\0,…,m_j\, let rj(a)r_j(a) be the largest grid member not exceeding a. Then a1+η≤rj(a)≤a. a1+η≤ r_j(a)≤ a. Indeed, the assertion is immediate for a=0a=0. For a≥1a≥ 1, take ℓ=⌊log1+ηa⌋ = _1+ηa . Integrality of a implies ⌈(1+η)ℓ⌉≤a (1+η) ≤ a, so this number belongs to Γj _j. Moreover, a<(1+η)ℓ+1≤(1+η)⌈(1+η)ℓ⌉≤(1+η)rj(a).a<(1+η) +1≤(1+η) (1+η) ≤(1+η)r_j(a). Choose an optimum as in Lemma 7 and round each bundle down coordinatewise to the grids. Feasibility is preserved, and additivity gives ui((rj(xi,j))j∈[q])≥ui(xi)1+ηu_i ((r_j(x_i,j))_j∈[q] )≥ u_i(x_i)1+η for every agent i. Each type still receives at most s distinct configurations. For each agent type, the configuration multiplicities (i.e., number of agents receiving each distinct configuration) form a histogram with at most s=2qs=2^q categories. By Lemma 8, we can assign one configuration to each previously constructed block so that, for every configuration, the sizes of the blocks assigned to it sum to its required multiplicity. Denote the resulting block profile by C∗=(Ch∗)h∈[H]C^*=(C_h^*)_h∈[H]. By monotonicity and homogeneity of the p-mean, ∑h=1Hbhcj(Ch∗)≤mj(j∈[q]),PSWp(C∗)≥OPTp1+η. _h=1^Hb_hc_j(C_h^*)≤ m_j (j∈[q]), _p(C^*)≥ OPT_p1+η. (27) Here and below, welfare of a block profile refers to its conceptual expansion to individual agents; this expansion is never computed. The profile C∗C^* is a comparator for the analysis. The algorithm neither computes it nor requires it to be optimal over all block configuration profiles. For p≤0p≤ 0, all its utilities are positive. Rational objective coefficients. For finite p, apply Lemma 1 with accuracy η to every type–configuration pair on the domain of ϕp _p. Write ϕ~k,p(C):=ϕ~p,η(uk(C)) φ_k,p(C):= φ_p,η(u_k(C)). Thus uk(C)p1+η u_k(C)^p1+η ≤ϕ~k,p(C)≤uk(C)p, ≤ φ_k,p(C)≤ u_k(C)^p, p>0, p>0, (28) loguk(C)−log(1+η) u_k(C)- (1+η) ≤ϕ~k,0(C)≤loguk(C), ≤ φ_k,0(C)≤ u_k(C), p=0, p=0, (29) uk(C)p u_k(C)^p ≤−ϕ~k,p(C)≤(1+η)uk(C)p, ≤- φ_k,p(C)≤(1+η)u_k(C)^p, −∞<p<0. -∞<p<0. (30) At zero utility and p>0p>0, set the coefficient to zero. For p≤0p≤ 0, exclude zero-utility configurations whenever they are considered for a block of type k. The finite-p score of block h with configuration C is bhϕ~k(h),p(C)b_h φ_k(h),p(C). For p=−∞p=-∞, the block’s contribution to the minimum is the exact rational utility uk(h)(C)u_k(h)(C), independently of bhb_h. There are at most KSKS coefficients to compute. 5.4 Anchor guesses and the compressed dynamic program Anchors for large individual coordinates. Set T:=⌈1/η⌉T:= 1/η . A coordinate j of configuration C is called large if its individual count satisfies cj(C)≥Tc_j(C)≥ T. For each j∈[q]j∈[q], guess either a null anchor gj=⊥g_j= , or a block gj∈[H]g_j∈[H] and its configuration Ggj∈G_g_j satisfying cj(Ggj)≥Tc_j(G_g_j)≥ T. If the same block is guessed for more than one coordinate, every occurrence must specify the same configuration. Let U⊆[H]U [H] be the set of distinct anchored blocks and put Lj:=bgjcj(Ggj),gj≠⊥,0,gj=⊥.L_j:= casesb_g_jc_j(G_g_j),&g_j≠ ,\\ 0,&g_j= . cases (31) There are at most (1+HS)q(1+HS)^q guesses, and |U|≤q|U|≤ q. Retain only guesses for which the fixed blocks satisfy ∑h∈Ubhcj(Gh)≤mj _h∈ Ub_hc_j(G_h)≤ m_j for every j∈[q],j∈[q], and, when p≤0p≤ 0, have uk(h)(Gh)>0u_k(h)(G_h)>0 for every h∈Uh∈ U. In addition, check all fixed blocks in all coordinates: cj(Gh)≥T⟹bhcj(Gh)≤Lj(h∈U,j∈[q]).c_j(G_h)≥ T b_hc_j(G_h)≤ L_j (h∈ U,\ j∈[q]). (32) This check applies even if block h was guessed as an anchor for a different coordinate. In particular, a null anchor for j requires every fixed block to have individual coordinate less than T in j. For each residual block h∉Uh∉ U, define its admissible configurations by h:=C∈:cj(C)<Torbhcj(C)≤Lj for every j∈[q].A_h:= \C :c_j(C)<T\ or\ b_hc_j(C)≤ L_j for every j∈[q] \. (33) When p≤0p≤ 0, also require uk(h)(C)>0u_k(h)(C)>0. Discard a guess if any residual admissible set is empty. For a retained guess, the residual capacities are aj:=mj−∑h∈Ubhcj(Gh)≥0.a_j:=m_j- _h∈ Ub_hc_j(G_h)≥ 0. (34) There is a correct guess relative to C∗C^*. For each j, if any block has cj(Ch∗)≥Tc_j(C_h^*)≥ T, choose a block maximizing bhcj(Ch∗)b_hc_j(C_h^*) among such blocks, and guess its configuration in C∗C^*. Otherwise choose gj=⊥g_j= . The same block always has the same configuration, so repeated anchors are consistent. Feasibility of C∗C^* implies that the fixed blocks fit the capacities. The maximizing choices give (32) in every coordinate and retain every residual configuration Ch∗C_h^* in hA_h. Positivity also holds when required. Hence this guess passes all checks. Rounded aggregate resources. For a retained guess and every coordinate j, choose the integer power of two Δj:=1,Lj=0orηLj/H<1,2⌊log2(ηLj/H)⌋,ηLj/H≥1. _j:= cases1,&L_j=0\ or\ η L_j/H<1,\\ 2 _2(η L_j/H) ,&η L_j/H≥ 1. cases (35) The power can be found by exact comparisons of binary integers and rationals. Define the rounded consumption of a residual block by dj(h,C):=Δj⌊bhcj(C)Δj⌋.d_j(h,C):= _j b_hc_j(C) _j . (36) If Δj=1 _j=1, this consumption is exact. If Δj>1 _j>1, then Δj≤ηLj/H _j≤η L_j/H. In every case with Lj>0L_j>0, LjΔj<2Hη. L_j _j< 2Hη. (37) Indeed, when ηLj/H<1η L_j/H<1, we have Δj=1 _j=1 and Lj<H/ηL_j<H/η. Otherwise Δj>(ηLj/H)/2 _j>(η L_j/H)/2. The fixed blocks retain their original, unrounded consumptions. Suffix bounds. Order the residual blocks as h1,…,hrh_1,…,h_r, where r:=H−|U|r:=H-|U|, so that their sizes βt:=bht _t:=b_h_t satisfy β1≥⋯≥βr _1≥·s≥ _r. Their original identifiers are unchanged. Define the individual and suffix maxima by At,j:=maxC∈htdj(ht,C), A_t,j:= _C _h_td_j(h_t,C), (t∈[r]), (t∈[r]), Mt,j:=∑ℓ=t+1rAℓ,j M_t,j:= _ =t+1^rA_ ,j (0≤t≤r). (0≤ t≤ r). The maxima exist because the retained admissible sets are nonempty. The quantity Mt,jM_t,j bounds the rounded consumption in coordinate j of every assignment to the blocks remaining after layer t. It is the sum of separate maxima; no assertion of simultaneous attainment of the maxima is needed. From (33), At,j≤Tβt+Lj,Mt,j≤HTβt+1+HLj(0≤t<r).A_t,j≤ T _t+L_j, M_t,j≤ HT _t+1+HL_j (0≤ t<r). (38) For the first inequality, a small individual coordinate contributes less than TβtT _t, whereas a large coordinate contributes at most LjL_j; rounding only reduces the contribution. The second inequality uses the ordering of the suffix block sizes and the fact that there are at most H blocks. At the terminal layer Mr,j=0M_r,j=0 by the empty-sum convention, and the second bound is needed only when t<rt<r. If r=0r=0, all suffix bounds are zero. State compression by suffix certificates. At layer t, each resource-state coordinate is either a nonnegative integer zj<Mt,jz_j<M_t,j or the symbol FREE. An integer records the exact remaining rounded capacity. The symbol records that the remaining capacity is at least Mt,jM_t,j and therefore suffices for every admissible assignment to the entire remaining suffix. A free coordinate can remain free at every later layer. To verify this, suppose that the actual rounded residual RjR_j before processing block hth_t satisfies Rj≥Mt−1,jR_j≥ M_t-1,j. For every C∈htC _h_t, Rj−dj(ht,C)≥Mt−1,j−At,j=Mt,j.R_j-d_j(h_t,C)≥ M_t-1,j-A_t,j=M_t,j. (39) Thus the next residual is nonnegative and has the required suffix certificate. The exact value of a free coordinate is unnecessary for future feasibility decisions. For an input state z at layer t−1t-1 and C∈htC _h_t, define nextt(z,C)next_t(z,C) coordinatewise as follows. A free coordinate remains free. From an integer coordinate, calculate yj:=zj−dj(ht,C)y_j:=z_j-d_j(h_t,C). If any yj<0y_j<0, the transition is undefined. Otherwise, record yjy_j when yj<Mt,jy_j<M_t,j and record FREE when yj≥Mt,jy_j≥ M_t,j. Initialize zj0z^0_j to aja_j if aj<M0,ja_j<M_0,j, and to FREE otherwise. Objective labels and transitions. The initial label includes the fixed blocks: κU:=∑h∈Ubhϕ~k(h),p(Gh),p∈ℚ,minh∈Uuk(h)(Gh),p=−∞. _U:= cases _h∈ Ub_h φ_k(h),p(G_h),&p ,\\[5.69054pt] _h∈ Uu_k(h)(G_h),&p=-∞. cases For U=∅U= , use κU=0 _U=0 for finite p and κU=+∞ _U=+∞ for p=−∞p=-∞. Given a label v, define updp(v,h,C):=v+bhϕ~k(h),p(C),p∈ℚ,minv,uk(h)(C),p=−∞.upd_p(v,h,C):= casesv+b_h φ_k(h),p(C),&p ,\\ \v,u_k(h)(C)\,&p=-∞. cases For every reachable state z at layer t, the DP label Dt(z)D_t(z) is the maximum objective value of a partial block assignment with that compressed resource state. Unreachable states are absent from the stored table and have label −∞-∞ by convention. The algorithm generates states from reachable predecessors and never enumerates all integers up to an original capacity. Algorithm 2 Compressed configuration dynamic program for a retained guess 1: Fixed configurations (Gh)h∈U(G_h)_h∈ U, ordered residual blocks h1,…,hrh_1,…,h_r, admissible sets, rounded consumptions djd_j, residual capacities aja_j, and suffix bounds Mt,jM_t,j 2: Initialize zj0←ajz^0_j← a_j if aj<M0,ja_j<M_0,j and zj0←z^0_j← FREE otherwise 3: Set D0(z0)←κUD_0(z^0)← _U, with every other state absent 4: for t=1,…,rt=1,…,r do 5: Initialize an empty table DtD_t 6: for each stored state z of Dt−1D_t-1 do 7: for each C∈htC _h_t do 8: Compute z′←nextt(z,C)z _t(z,C) 9: if the transition is defined then 10: Set v′←updp(Dt−1(z),ht,C)v _p(D_t-1(z),h_t,C) 11: if z′z is absent from DtD_t, or v′>Dt(z′)v >D_t(z ) then 12: Set Dt(z′)←v′D_t(z )← v and store predecessor (z,C)(z,C) 13: if DrD_r is empty then 14: return no reachable terminal state 15: Choose a state ztermz^term with maximum label in DrD_r 16: Recover the residual configurations by backtracking and combine them with (Gh)h∈U(G_h)_h∈ U on the original block identifiers 17: return V:=Dr(zterm)V_ g:=D_r(z^term) and the pre-repair block profile C¯ C g Lemma 9. For every retained guess, Algorithm 2 maximizes its objective over all residual admissible assignments satisfying ∑t=1rdj(ht,Cht)≤aj _t=1^rd_j(h_t,C_h_t)≤ a_j for every j. The assertion also holds when r=0r=0. Proof. For an exact state coordinate, the stored value is the actual remaining rounded capacity. For a free coordinate, its suffix certificate follows at initialization or at the transition where it first becomes free, and remains valid by (39). Thus every generated path is feasible for the rounded capacities. Conversely, consider any rounded-feasible residual assignment. Since consumptions are nonnegative, each of its prefixes is feasible. Exact coordinates therefore never reject its next configuration, while free coordinates accept every admissible suffix choice. It defines a path in the state transition graph. It remains to justify retaining only one objective label at each state. Any two histories with the same compressed state have identical exact residuals in its integer coordinates. In its free coordinates, both histories permit every admissible remaining suffix. They therefore have the same feasible future choices. Adding a fixed block score and taking the minimum with a fixed utility are both nondecreasing functions of the previous label. A history with a smaller label can never improve the result of any common continuation. Induction over the layers proves the DP invariant and the optimality of the largest terminal label. At layer r, all Mr,j=0M_r,j=0, so the only possible state is the all-free state. When r=0r=0, initialization is already at this layer, and the empty loop returns exactly the fixed profile, which fits the original capacities by the retained-guess checks. ∎ Lemma 10. Every DP layer has at most Oq((1+H2/η)q)O_q((1+H^2/η)^q) reachable states. Proof. Layer zero has one state, and the terminal layer has at most one state. Consider a nonterminal layer 1≤t<r1≤ t<r and a coordinate j. Set wt,j:=maxβt,Δjw_t,j:= \ _t, _j\. Every rounded consumption of an already processed residual block is divisible by wt,jw_t,j. Indeed, block sizes and Δj _j are powers of two. If βt≥Δj _t≥ _j, each earlier block size is divisible by βt _t and hence by Δj _j, so its aggregate consumption is rounded exactly and is divisible by βt=wt,j _t=w_t,j. If βt<Δj _t< _j, divisibility by wt,j=Δjw_t,j= _j follows directly from the definition of djd_j. Consequently, every integer state coordinate at layer t satisfies zj≡aj(modwt,j)z_j≡ a_j w_t,j, and 0≤zj<Mt,j.0≤ z_j<M_t,j. There are at most 1+Mt,j/wt,j1+M_t,j/w_t,j such integers. Including the free symbol, using (38), and observing that βt+1≤βt≤wt,j _t+1≤ _t≤ w_t,j and Δj≤wt,j _j≤ w_t,j, the number of coordinate states is at most 2+Mt,jwt,j≤2+HT+HLjΔj≤2+HT+2H2η=O(1+H2η). 2+ M_t,jw_t,j≤ 2+HT+ HL_j _j≤ 2+HT+ 2H^2η=O (1+ H^2η ). When Lj>0L_j>0, the second inequality uses (37); when Lj=0L_j=0, its corresponding term is zero. Also T=⌈1/η⌉=O(1/η)T= 1/η =O(1/η). Multiplying the coordinate bounds over the fixed number q of item types proves the claim. This counts only potential reachable residuals in the indicated congruence classes, so storing and generating the reachable states suffices. ∎ Comparison with the near-optimal block profile. Under the correct guess, every residual Ch∗C_h^* is admissible and the fixed configurations agree with C∗C^*. Therefore, ∑h∉Udj(h,Ch∗)≤∑h∉Ubhcj(Ch∗)≤mj−∑h∈Ubhcj(Ch∗)=aj. _h∉ Ud_j(h,C_h^*)≤ _h∉ Ub_hc_j(C_h^*)≤ m_j- _h∈ Ub_hc_j(C_h^*)=a_j. Lemma 9 shows that the comparator defines a feasible DP path, including the empty-loop case r=0r=0. In particular, at least one guess returns a profile. Run the DP for every retained guess and select a returned profile with maximum label. Labels for different guesses are comparable because they include all fixed and residual blocks. They are rational, except for the temporary empty-set initialization +∞+∞ in the minimum case; every returned label is finite because H≥1H≥ 1. Let C¯ C denote the selected block profile. For finite p, ∑h=1Hbhϕ~k(h),p(C¯h)≥∑h=1Hbhϕ~k(h),p(Ch∗). _h=1^Hb_h φ_k(h),p( C_h)≥ _h=1^Hb_h φ_k(h),p(C_h^*). (40) For p=−∞p=-∞, minh∈[H]uk(h)(C¯h)≥minh∈[H]uk(h)(Ch∗). _h∈[H]u_k(h)( C_h)≥ _h∈[H]u_k(h)(C_h^*). (41) Every profile assigns exactly nkn_k agents to type k, but its original item consumption may exceed the capacities because of resource rounding. 5.5 Repair, approximation guarantee, and running time Repairing original capacities. All quantities in this paragraph refer to the selected guess. For every coordinate, let νj:=max0,∑h=1Hbhcj(C¯h)−mj. _j:= \0,\ _h=1^Hb_hc_j( C_h)-m_j \. If Δj=1 _j=1, rounded residual consumptions are exact; together with the fixed blocks they fit mjm_j, so νj=0 _j=0. If Δj>1 _j>1, the difference between original and rounded consumption of one residual block is less than Δj _j. Whenever νj>0 _j>0, it follows that 0<νj<rΔj≤HΔj≤ηLj.0< _j<r _j≤ H _j≤η L_j. (42) Thus a violated coordinate has a nonnull anchor gjg_j, with Lj=bgjcj(Ggj)L_j=b_g_jc_j(G_g_j) and cj(Ggj)≥Tc_j(G_g_j)≥ T. If r=0r=0, no coordinate is violated. Remove exactly νj _j items of type j from the bgjb_g_j agents of its anchor, distributing the removals as evenly as possible. Each such agent loses at most ⌈νjbgj⌉≤ηcj(Ggj)+1≤2ηcj(Ggj), _jb_g_j ≤η c_j(G_g_j)+1≤ 2η c_j(G_g_j), (43) where the last inequality uses cj(Ggj)≥T≥1/ηc_j(G_g_j)≥ T≥ 1/η. Because 2η<12η<1, the removals are possible and leave every affected coordinate nonnegative. If a block anchors several coordinates, perform this operation separately in each of them. For each agent, an unchanged coordinate retains its full count, and every changed coordinate retains at least its (1−2η)(1-2η) fraction. Additivity and nonnegative utilities therefore give ui(xirep)≥(1−2η)ui(C¯i)for every individual agent i.u_i(x_i^rep)≥(1-2η)u_i( C_i) every individual agent i. (44) The notation C¯i C_i denotes that agent’s configuration in the conceptual expansion of C¯ C. Exactly the excess is removed in each violated coordinate, so xrepx^rep is a feasible partial allocation. Positive utilities remain positive. Monotonicity and homogeneity imply PSWp(xrep)≥(1−2η)PSWp(C¯).PSW_p(x^rep)≥(1-2η)PSW_p( C). (45) The balanced repair has a compressed implementation. In an anchor block of size b, write each excess assigned to this block as νj=bαj+ρj _j=b _j+ _j, where 0≤ρj<b0≤ _j<b. Remove αj _j items of coordinate j from every agent and one more from the first ρj _j agents in a common ordering of that block. Sort the nonzero remainder endpoints ρj _j. Agents between consecutive endpoints receive identical repaired bundles. A block with d repaired coordinates splits into at most d+1d+1 groups. Across all anchors, at most q coordinates are repaired, so the full repaired profile has at most H+qH+q groups. This computation uses only binary integers; no individual ordering is explicitly expanded. Finally, collect all unassigned items into the bundle of one agent, splitting that agent from her current group if necessary. This adds at most one group and cannot decrease welfare. Merge groups of the same type with the same bundle by adding their multiplicities. The resulting allocation x has at most H+q+1H+q+1 groups, with exact item totals and exact type multiplicities. Approximation guarantee. We verify all four cases of the welfare parameter. In weighted block notation, the quantities defined in Section 3 satisfy Qp(C)=∑h=1Hbhuk(h)(Ch)p(p∈ℚ∖0),Λ(C)=∑h=1Hbhloguk(h)(Ch)Q_p(C)= _h=1^Hb_hu_k(h)(C_h)^p (p \0\), (C)= _h=1^Hb_h u_k(h)(C_h) whenever the displayed terms are defined. For finite p, the score dominance in (40) allows us to apply Lemma 2 to the block profiles C∗C^* and C¯ C, with weights bhb_h and total weight n. Suppose first that p>0p>0. The lemma gives Qp(C¯)≥Qp(C∗)1+η.Q_p( C)≥ Q_p(C^*)1+η. Taking the positive 1/p1/p power and using (27), (45), and completion gives PSWp(x)≥1−2η(1+η)1+1/pOPTp.PSW_p(x)≥ 1-2η(1+η)^1+1/pOPT_p. (46) This conclusion also holds when OPTp=0OPT_p=0, without division by the optimum or any requirement that the utilities be positive. Suppose next that −∞<p<0-∞<p<0. The positive-utility test has passed, and all configurations considered for a block have positive utility. Lemma 2 gives Qp(C¯)≤(1+η)Qp(C∗).Q_p( C)≤(1+η)Q_p(C^*). Since 1/p<01/p<0, taking the 1/p1/p power reverses the inequality. Therefore PSWp(C¯)≥(1+η)−1/|p|PSWp(C∗),PSW_p( C)≥(1+η)^-1/|p|PSW_p(C^*), and the repair and geometric rounding give PSWp(x)≥1−2η(1+η)1+1/|p|OPTp.PSW_p(x)≥ 1-2η(1+η)^1+1/|p|OPT_p. (47) For p=0p=0, the logarithmic conclusion of the same lemma gives Λ(C¯)≥Λ(C∗)−nlog(1+η). ( C)≥ (C^*)-n (1+η). Divide by n and exponentiate to obtain PSW0(C¯)≥PSW0(C∗)/(1+η)PSW_0( C) _0(C^*)/(1+η). The binary block multiplicities cause no additional error because their sum is exactly n. Hence PSW0(x)≥1−2η(1+η)2OPT0.PSW_0(x)≥ 1-2η(1+η)^2OPT_0. (48) Finally, when p=−∞p=-∞, the DP uses exact utilities, and (41) directly gives PSW−∞(C¯)≥PSW−∞(C∗)PSW_-∞( C) _-∞(C^*). Thus PSW−∞(x)≥1−2η1+ηOPT−∞.PSW_-∞(x)≥ 1-2η1+ηOPT_-∞. (49) For every fixed a>0a>0, convexity of (1+η)−a(1+η)^-a gives (1+η)−a≥1−aη(1+η)^-a≥ 1-aη. Multiplying by 1−2η>01-2η>0 yields (1−2η)(1+η)−a≥1−(a+2)η+2aη2≥1−(a+2)η.(1-2η)(1+η)^-a≥ 1-(a+2)η+2aη^2≥ 1-(a+2)η. Applying this with a=1+1/|p|a=1+1/|p|, 22, and 11, respectively, gives PSWp(x)≥(1−(3+1/|p|)η)OPTp,p∈ℚ∖0,(1−4η)OPT0,p=0,(1−3η)OPT−∞,p=−∞.PSW_p(x)≥ cases (1-(3+1/|p|)η )OPT_p,&p \0\,\\ (1-4η)OPT_0,&p=0,\\ (1-3η)OPT_-∞,&p=-∞. cases The choice (26) proves the required (1−ε)(1- ) approximation in every case. Arithmetic and bit complexity. There are at most (1+HS)q(1+HS)^q anchor guesses. By Lemma 10, a retained guess has at most H DP layers, Oq((1+H2/η)q)O_q((1+H^2/η)^q) states per layer, and at most S candidate configurations per state. Thus the number of DP arithmetic operations, apart from polynomial table-management factors, is bounded by Oq((1+HS)qHS(1+H2/η)q) O_q ((1+HS)^qHS(1+H^2/η)^q ) =Oq(H3q+1ℓmq(q+1)η−(q2+2q)). =O_q (H^3q+1 _m^q(q+1)η^-(q^2+2q) ). (50) Constructing admissible sets, checking fixed blocks, computing suffix maxima, and recovering predecessors fit the same polynomial bounds. Sorting residual blocks and implementing tables by exact comparisons also take polynomial time. The bound on H in (25) involves only the encoding lengths of the agent multiplicities, rather than their numerical sum. Let L be the compact input encoding length, excluding the separately supplied accuracy parameter. Every block size, item capacity, anchor load, rounded consumption, and suffix maximum has polynomial encoding length in L+log(1/ε)L+ (1/ ). For example, a product bhcj(C)b_hc_j(C) has at most the sum of the encoding lengths of n and mjm_j, and a suffix sum adds at most O(logH)O( H) further bits. The same bound holds for residual capacities and their differences. Exact grid generation takes O(ℓm/η)O( _m/η) rational multiplications; its intermediate numerators and denominators have lengths Op(ℓmη(1+log(1/ε))).O_p ( _mη(1+ (1/ )) ). Thus generation of the grid also has polynomial bit complexity, even though no approximate logarithms are used. Each rational configuration utility has encoding length polynomial in L. Lemma 1 therefore gives each of the KSKS objective coefficients encoding length polynomial in L+log(1/ε)L+ (1/ ). A finite-p DP label is the sum of at most H terms, each a binary block size times one coefficient. Forming a common denominator from these at most H coefficients already bounds the numerator and denominator lengths by a polynomial in L and 1/ε1/ . Comparisons between labels are consequently exact rational comparisons of polynomial encoding length. For p=−∞p=-∞, every finite label is one rational configuration utility. The symbols used for unreachable states and the empty minimum are handled directly. Repair and completion use binary division, remainders, and sorting of at most q endpoints per anchor. Each resulting bundle coordinate is at most mjm_j, each output multiplicity is at most nkn_k, and there are at most H+q+1H+q+1 groups before identical bundles are merged. Hence both the construction time and the output length are polynomial in the compact input length and 1/ε1/ . Reading the originally supplied accuracy encoding adds only its input length. Since η=Θp(ε)η= _p( ) and q,pq,p are fixed, the complete algorithm is an FPTAS, proving Theorem 6. For comparison, when both numbers of types are fixed, exact egalitarian welfare maximization follows directly from Theorem 12 of Goemans and Rothvoß Goemans and Rothvoß (2020). We record this consequence for completeness; the reduction to integer-cone feasibility, its bit complexity, and the compressed reconstruction are given in Appendix C. Proposition 1 (Consequence of Goemans–Rothvoß). For fixed numbers K of agent types and q of item types, maximizing egalitarian social welfare under additive nonnegative rational utilities admits an exact polynomial-time algorithm when both agent and item multiplicities are encoded in binary. The running time is polynomial in the compact input length, and the algorithm returns a compressed allocation. 5.6 Exact optimal allocations with one item type The case of one item type admits an exact allocation algorithm even when the number of agent types is unrestricted. The main ingredient is the classical reduction of separable concave resource allocation to selection in sorted implicit arrays Galil and Megiddo (1979). We give the details to account for binary agent multiplicities and exact arithmetic. Theorem 7 (Optimal allocations with one item type). Suppose that q=1q=1, while the number K of agent types is unrestricted. For every fixed p∈ℚ∪−∞p ∪\-∞\, an allocation maximizing PSWpPSW_p can be computed in time polynomial in the compact input length, with both item and agent multiplicities encoded in binary. The algorithm returns a compressed allocation using at most two bundle sizes per agent type. Proof. Write ak:=uk,1a_k:=u_k,1 for the per-item value of type k, let m be the item multiplicity, and put n=∑k=1Knkn= _k=1^Kn_k. Empty agent types can be omitted. If m=0m=0, the assertion is immediate. For p≤0p≤ 0, if some ak=0a_k=0 or m<nm<n, every allocation has welfare zero. Giving all items to one agent is then optimal and has the required compressed representation. Hence, whenever p≤0p≤ 0, we may assume that every ak>0a_k>0 and m≥nm≥ n. Finite p<1p<1, p≠0p≠ 0. For 0<p<10<p<1, if every aka_k is zero, give all items to one agent; this is optimal and uses at most two bundle sizes per type. Otherwise, zero-valued types are assigned no items, and we restrict attention to the remaining types. Define b:=0,0<p<1,1,p<0,fk(x):=(akx)p,0<p<1,−(akx)p,p<0.b:= cases0,&0<p<1,\\ 1,&p<0, cases f_k(x):= cases(a_kx)^p,&0<p<1,\\ -(a_kx)^p,&p<0. cases The domain of fkf_k is [0,∞)[0,∞) in the first case and [1,∞)[1,∞) in the second. Each fkf_k is strictly increasing and strictly concave. Maximizing PSWpPSW_p is equivalent to maximizing the sum of these transformed utilities. In the negative-p case this equivalence uses the fact that raising a positive number to the power 1/p1/p reverses order. Moreover, an optimal allocation has positive welfare and hence gives at least one item to every agent. Give b items to every agent and let R:=m−bnR:=m-bn. If R=0R=0, this already gives the desired allocation. Otherwise, for each remaining type k consider the strictly decreasing sequence dk(t):=fk(b+t+1)−fk(b+t),t=0,…,R−1.d_k(t):=f_k(b+t+1)-f_k(b+t), t=0,…,R-1. (51) Each entry occurs nkn_k times, once for every agent of that type. An agent receiving z additional items contributes the prefix dk(0)+⋯+dk(z−1)d_k(0)+·s+d_k(z-1) beyond its baseline utility. Consequently, the sum of the R largest entries in the resulting multiset is an upper bound on the additional transformed welfare of any allocation. We next find these entries and show that they admit a feasible allocation. The multiset is represented implicitly by the K sequences and their binary multiplicities; it is never expanded. For a candidate value v, binary search in each decreasing sequence computes Ak(v) A_k(v) :=|t∈0,…,R−1:dk(t)>v|, := |\t∈\0,…,R-1\:d_k(t)>v\ |, Bk(v) B_k(v) :=|t∈0,…,R−1:dk(t)≥v|. := |\t∈\0,…,R-1\:d_k(t)≥ v\ |. Put A(v):=∑knkAk(v)A(v):= _kn_kA_k(v) and B(v):=∑knkBk(v)B(v):= _kn_kB_k(v). The R-th largest entry has value v precisely when A(v)<R≤B(v).A(v)<R≤ B(v). (52) To find such a value, search each sequence djd_j in turn. At a midpoint t, compute the two ranks for v=dj(t)v=d_j(t). If A(v)≥RA(v)≥ R, the desired value is strictly larger than v, so retain only indices smaller than t. If B(v)<RB(v)<R, retain only indices larger than t. Otherwise, return v. If this search exhausts the indices of one sequence, proceed to the next. Since the desired value belongs to at least one sequence, one of these searches succeeds. There are O(Klog(R+1))O(K (R+1)) candidate evaluations, each requiring O(Klog(R+1))O(K (R+1)) marginal comparisons. Thus the total number of comparisons is O(K2log2(R+1))O(K^2 ^2(R+1)). Let τ be the value returned. Initially give every type-k agent b+Ak(τ)b+A_k(τ) items. This selects all marginal entries strictly larger than τ. There remain E:=R−∑knkAk(τ)E:=R- _kn_kA_k(τ) items. Strict decrease of each sequence implies that Bk(τ)−Ak(τ)∈0,1B_k(τ)-A_k(τ)∈\0,1\. By (52), 0<E≤∑k:Bk(τ)=Ak(τ)+1nk.0<E≤ _k:\,B_k(τ)=A_k(τ)+1n_k. For the types appearing in this sum, in any order, give one more item to minE,nk \E,n_k\ of their agents, and decrease E by this amount. Stop when E=0E=0. All selected entries form prefixes for their respective agents, so this is a feasible allocation attaining the sum of the R largest marginal entries. It is therefore optimal. Each type uses at most two consecutive bundle sizes, and their multiplicities are computed with binary arithmetic. Exact comparisons and bit complexity. Write the fixed parameter as p=A/Bp=A/B in lowest terms, where A∈ℤ∖0A \0\ and B≥1B≥ 1. Comparing two entries of (51) requires the sign of a sum of at most four terms of the form ±rA/B± r^A/B. Each r is a rational number of polynomial bit length, namely a per-item value multiplied by an integer at most m+1m+1. Zero terms are treated separately; all remaining r are positive. The number of terms, and the degrees of their defining polynomials, depend only on p. For completeness, exact signs can be determined as follows. Each rA/Br^A/B is the positive root of XB−rAX^B-r^A, after clearing denominators. A constant number of resultant computations produces a nonzero integer polynomial P whose roots include the difference δ being compared. The degree of P is at most B4B^4 and its coefficient bit lengths are polynomial in the input length. Divide out the largest power of X that divides P, obtaining Q. If Q is constant, then δ=0δ=0. Otherwise, let H≥1H≥ 1 bound the absolute values of the coefficients of Q. Since Q has a nonzero integer constant coefficient, applying Cauchy’s root bound to its reciprocal polynomial gives δ≠0⟹δ≠ 0 |δ|≥11+H.|δ|≥ 11+H. Certified rational bisection of the positive B-th roots approximates δ with absolute error less than 1/(4(1+H))1/(4(1+H)) in polynomial time. An approximate absolute value at most 1/(2(1+H))1/(2(1+H)) certifies δ=0δ=0; otherwise the approximation has the correct sign. Thus each marginal comparison has polynomial bit complexity. All ranks, multiplicities, and indices also have polynomial bit length. The selection and reconstruction therefore run in polynomial time in the compact input length. In particular, this argument never compares a sum of a number of radicals that grows with K or n. Nash welfare, p=0p=0. Under the positivity assumptions made above, maximizing Nash welfare is equivalent to maximizing ∏i=1nak(i)xi=(∏k=1Kaknk)∏i=1nxi, _i=1^na_k(i)x_i= ( _k=1^Ka_k^n_k ) _i=1^nx_i, where k(i)k(i) is the type of agent i and xix_i is its item count. The first factor is independent of the allocation. If xi≥xj+2x_i≥ x_j+2, transferring one item from i to j increases their product, since (xi−1)(xj+1)−xixj=xi−xj−1>0.(x_i-1)(x_j+1)-x_ix_j=x_i-x_j-1>0. Hence a maximizing allocation has all item counts differing by at most one. Write m=hn+rm=hn+r, where 0≤r<n0≤ r<n. Give h+1h+1 items to r agents and h items to the others. The agents receiving an extra item can be assigned across types in one pass over the binary multiplicities. This gives an optimal compressed allocation with at most two bundle sizes per type. Egalitarian welfare, p=−∞p=-∞. Clear the denominators of the aka_k using a common positive integer D, and write ck:=Dak∈ℤ>0c_k:=Da_k _>0. The product of the input denominators is a valid choice of D and has polynomial bit length. For an integer threshold T≥0T≥ 0, an allocation with scaled minimum utility at least T exists if and only if ∑k=1Knk⌈Tck⌉≤m. _k=1^Kn_k Tc_k ≤ m. (53) Indeed, every type-k agent needs at least ⌈T/ck⌉ T/c_k items, and these lower bounds can be met whenever their sum is at most m. All achievable scaled utilities are integers. Binary search for the largest feasible T in [0,mmaxkck][0,m _kc_k] therefore finds the exact optimum. Each test of (53) uses polynomial-time binary arithmetic, and the number of tests is polynomial in the input length. Give each type-k agent ⌈T/ck⌉ T/c_k items and assign all leftovers to one agent. This is an optimal compressed allocation with at most two bundle sizes per type. Parameters p≥1p≥ 1. Let amax:=maxkaka_ := _ka_k. For any complete allocation, ∑i=1n(ak(i)xi)p≤amaxp∑i=1nxip≤amaxp(∑i=1nxi)p=amaxpmp. _i=1^n(a_k(i)x_i)^p≤ a_ ^p _i=1^nx_i^p≤ a_ ^p ( _i=1^nx_i )^p=a_ ^pm^p. Giving all items to one agent of a type attaining amaxa_ attains this bound. This completes the proof in every case. ∎ Remark 1 (Allocation construction and threshold decision). Theorem 7 constructs an exact optimal allocation. It does not assert a polynomial-time algorithm for comparing its welfare to an arbitrary rational threshold. This distinction matters even with one item type. To see this, consider positive integers b1,…,bn,Tb_1,…,b_n,T and the question whether ∑ibi≤T _i b_i≤ T, an instance of Sqrt-Sum. Set p=−1/2p=-1/2, take m=nm=n identical items, and give agent i per-item value 1/bi1/b_i. Every allocation with positive welfare must give exactly one item to every agent. Thus an optimal allocation is immediate, but its welfare is OPT−1/2=(n∑i=1nbi)2.OPT_-1/2= ( n _i=1^n b_i )^2. The rational threshold τ:=n2/T2τ:=n^2/T^2 has polynomial encoding length, and OPT−1/2≥τ⟺∑i=1nbi≤T.OPT_-1/2≥τ _i=1^n b_i≤ T. Hence the rational-threshold decision problem at q=1q=1 and the single fixed value p=−1/2p=-1/2 is at least as hard as Sqrt-Sum. The allocation algorithm avoids this comparison: each of its marginal comparisons involves at most four radicals, whereas evaluating the final threshold can involve a sum with an unbounded number of terms. 5.7 Exact egalitarian welfare with two item types For egalitarian welfare, the case of two item types admits an exact polynomial-time algorithm, even when the number of agent types is not fixed. This is a consequence of the two-job-type algorithms of McCormick, Smallwood, and Spieksma McCormick et al. (2001). We give a direct proof that also makes the dependence on the compact input and the reconstruction of an allocation explicit. Theorem 8. For at most two item types and an arbitrary number K of agent types, exact egalitarian-welfare maximization with nonnegative rational additive utilities is solvable in polynomial time. The running time is polynomial in the compact input length, with both item and agent multiplicities encoded in binary. The algorithm returns an optimal compressed allocation using at most K+2K+2 type–bundle pairs. Proof. If there are no item types, every agent receives the empty bundle and the optimum is zero. Otherwise, we may add an item type of multiplicity zero if there is only one item type. Write m1,m2m_1,m_2 for the two item multiplicities, nkn_k for the number of agents of type k, and uk(x,y)=akx+bkyu_k(x,y)=a_kx+b_ky for their common utility. Types of multiplicity zero can be deleted. Thus nk≥1n_k≥ 1 for every remaining type. We first solve feasibility for a common welfare threshold T, and then optimize the threshold. The integer hull for one agent type. For each type k, let Sk(T)=(x,y)∈ℤ≥02:akx+bky≥T,Pk(T)=conv(Sk(T)).S_k(T)=\(x,y) _≥ 0^2:a_kx+b_ky≥ T\, P_k(T)=conv(S_k(T)). (54) The threshold T=0T=0 is always feasible: give all items to one agent and leave the other bundles empty, using at most K+1K+1 type–bundle pairs. Suppose henceforth that T>0T>0. If ak=bk=0a_k=b_k=0 for some k, the threshold is infeasible. If exactly one coefficient is positive, then Pk(T)P_k(T) is a translated nonnegative orthant. For example, if ak>0a_k>0 and bk=0b_k=0, then Pk(T)=(⌈T/ak⌉,0)+ℝ≥02.P_k(T)=( T/a_k ,0)+R_≥ 0^2. Suppose that both coefficients are positive, and put Xk=⌈T/ak⌉X_k= T/a_k , Yk=⌈T/bk⌉.Y_k= T/b_k . Every point of Sk(T)S_k(T) dominates a point of Sk(T)∩([0,Xk]×[0,Yk])S_k(T)∩([0,X_k]×[0,Y_k]): if its first coordinate exceeds XkX_k, the point (Xk,0)(X_k,0) suffices, and the analogous statement holds for the second coordinate. Consequently, Pk(T)=conv(Sk(T)∩([0,Xk]×[0,Yk]))+ℝ≥02.P_k(T)=conv (S_k(T)∩([0,X_k]×[0,Y_k]) )+R_≥ 0^2. (55) The bounded integer hull in (55) is the integer hull of a rational polygon described by five inequalities. The standard polynomial-time integer-hull algorithm in dimension two Hartmann (1989), also used by McCormick et al. McCormick et al. (2001), therefore computes its vertices in polynomial time. The number and encoding lengths of the vertices are polynomial in the input length. The same is true of the finite lower boundary of Pk(T)P_k(T). Each Pk(T)P_k(T) is upward closed: if v∈Pk(T)v∈ P_k(T) and r∈ℝ≥02r _≥ 0^2, then v+r∈Pk(T)v+r∈ P_k(T). Indeed, Sk(T)S_k(T) is closed under addition of nonnegative integer vectors, and conv(ℤ≥02)=ℝ≥02conv(Z_≥ 0^2)=R_≥ 0^2. Its finite lower boundary is an integral polygonal chain whose successive vertices have strictly increasing first coordinates and strictly decreasing second coordinates. A translated orthant has only one such vertex. Notice also that Pk(T)∩ℤ2=Sk(T),P_k(T) ^2=S_k(T), (56) because the original covering halfplane and the nonnegative orthant are convex and contain Sk(T)S_k(T). The aggregate lower boundary. Consider the Minkowski sum P(T)=∑k=1KnkPk(T).P(T)= _k=1^Kn_kP_k(T). (57) A threshold-feasible allocation implies (m1,m2)∈P(T)(m_1,m_2)∈ P(T). To see this, distribute any unused items arbitrarily, which preserves feasibility by monotonicity. For each type k, the sum of its nkn_k feasible bundles belongs to nkPk(T)n_kP_k(T), since Pk(T)P_k(T) is convex. To construct the finite lower boundary of P(T)P(T), start with the sum of the leftmost lower vertices of the scaled polyhedra nkPk(T)n_kP_k(T). Merge their lower edges in slope order. When edges are parallel, process them successively and retain the resulting intermediate collinear points. Every segment in this representation then changes the contribution of exactly one type, from nkAn_kA to nkBn_kB, where A,BA,B are consecutive lower vertices of Pk(T)P_k(T); every other type contributes a fixed scaled vertex. The boundary has at most the sum of the numbers of local lower edges. We can record the type and the two local endpoints responsible for each segment, together with the current vertex of every other type. This construction is polynomial in the compact input length and never expands the agent multiplicities. Membership of z=(m1,m2)z=(m_1,m_2) in P(T)P(T) can now be checked in polynomial time. We prove that membership is also sufficient for an integral allocation, and give a compressed reconstruction. Locating the target. Suppose that z∈P(T)z∈ P(T). First check whether z dominates any recorded lower boundary point V. If it does not, it belongs to the closed axial triangle convV,W,(W1,V2)conv\V,W,(W_1,V_2)\ (58) for two consecutive recorded points V,WV,W, where V1<W1V_1<W_1 and V2>W2V_2>W_2. Indeed, if the first coordinate of z lies between those of V and W, membership places z on or above the segment VWVW. If z2≥V2z_2≥ V_2, then z dominates V. Otherwise it lies in the triangle (58). If z lies to the right of the finite chain, membership implies that it dominates the rightmost lower vertex. A chain consisting of one vertex gives only the domination case. Reconstruction in the domination case. Write V=∑k=1KnkAk,V= _k=1^Kn_kA_k, where AkA_k is the recorded integral vertex of Pk(T)P_k(T). Give every type-k agent bundle AkA_k. By (56), every such bundle meets the threshold. Give the nonnegative integer remainder z−Vz-V to one agent. This produces a feasible allocation with at most K+1K+1 type–bundle pairs. Reconstruction in the edge case. Suppose that z belongs to the triangle associated with a segment that changes type k. Write V=C+sA,W=C+sB,C=∑ℓ≠knℓAℓ,s=nk,V=C+sA, W=C+sB, C= _ ≠ kn_ A_ , s=n_k, where A=(a,b)A=(a,b) and B=(c,d)B=(c,d) are consecutive lower vertices of Pk(T)P_k(T), with c>ac>a and b>db>d. Give every type-ℓ agent, for ℓ≠k ≠ k, bundle AℓA_ . The remaining resource vector Z=z−CZ=z-C is integral and belongs to convsA,sB,(sc,sb).conv\sA,sB,(sc,sb)\. In particular, sa≤Z1≤sc,Z2≥sb+Z1−sac−a(d−b).sa≤ Z_1≤ sc, Z_2≥ sb+ Z_1-sac-a(d-b). (59) Set h=⌊Z1−sac−a⌋.h= Z_1-sac-a . Since the domination case was excluded, Z1<scZ_1<sc; otherwise z would dominate W. Hence 0≤h<s0≤ h<s. Define R=Z−hB−(s−h−1)A.R=Z-hB-(s-h-1)A. (60) This vector is integral. Put r=Z1−sa−h(c−a)r=Z_1-sa-h(c-a), 0≤r<c−a.0≤ r<c-a. Then R1=a+rR_1=a+r. Subtracting hd+(s−h−1)bhd+(s-h-1)b from (59) yields R2≥b+rc−a(d−b).R_2≥ b+ rc-a(d-b). The right-hand side is the second coordinate of the point on the segment ABAB with first coordinate a+ra+r. It is at least d≥0d≥ 0. Thus R is nonnegative and lies on or above ABAB. Since Pk(T)P_k(T) contains this segment and is upward closed, R∈Pk(T)R∈ P_k(T). Equation (56) gives R∈Sk(T)R∈ S_k(T). Give h agents of type k bundle B, give s−h−1s-h-1 agents bundle A, and give the remaining agent bundle R. The numbers of agents are nonnegative integers summing to s, and (60) shows that their total resource use is exactly Z. Every agent meets the threshold. After omitting zero multiplicities and merging equal bundles, type k uses at most three type–bundle pairs and every other type uses one. The total is therefore at most K+2K+2. This proves T is feasible⟺(m1,m2)∈∑k=1KnkPk(T),T is feasible (m_1,m_2)∈ _k=1^Kn_kP_k(T), (61) together with polynomial-time compressed reconstruction. All the numbers used above have polynomial encoding length. In particular, multiplication by nkn_k, comparison of slopes, and the quotient calculation defining h operate directly on binary integers and rationals. Exact optimization. Let D be the product of the denominators of all input utility coefficients. Multiplying the coefficients by D produces nonnegative integer coefficients ak′,bk′a _k,b _k. The encoding length of D is at most the sum of the denominator encoding lengths, so this scaling is polynomial in the input length. Every attained egalitarian welfare in the scaled instance is an integer, and U=maxkak′m1+bk′m2U= _k\a _km_1+b _km_2\ is an upper bound with polynomial encoding length. If U=0U=0, give all items to one agent and empty bundles to the others, using at most K+1K+1 compressed records. Otherwise, binary search over the integer thresholds 0,…,U0,…,U, using (61), finds the largest feasible threshold in O(log(U+1))O( (U+1)) calls. Reconstruct the allocation at that threshold. Dividing its welfare by D gives the exact optimum for the original instance, and does not change the allocation. The number of type–bundle pairs is at most K+2K+2, as claimed. ∎ 6 A PTAS for p-Mean Welfare with a Constant Number of Agent Types 6.1 Statement In this section, the number K of agent types is fixed, whereas the number q of good types is part of the input. We use the model, welfare conventions, and compressed-output representation from Section 3. Theorem 9. For every fixed number K of agent types, every fixed rational p<1p<1, and every ε>0 >0, maximizing p-mean social welfare under additive nonnegative utilities admits a polynomial-time approximation scheme in the high-multiplicity model. More precisely, for fixed K,p,εK,p, , the algorithm runs in time polynomial in q and in the binary encoding length of the instance and returns an allocation x satisfying PSWp(x)≥(1−ε)OPTpPSW_p(x)≥(1- )OPT_p. Remark 2. Theorem 9 concerns finite p<1p<1 and therefore includes p=0p=0, corresponding to Nash social welfare. The case p=0p=0 was previously established by Nguyen, Elbassioni, and Rothe Nguyen et al. (2024); the theorem extends the result to every fixed finite rational p<1p<1. The limiting case p=−∞p=-∞ is not claimed here. By Corollary 2, this PTAS cannot be strengthened to an FPTAS unless = P= NP, already with one agent type. Proof. If m=0m=0, return the allocation giving every agent the empty bundle. This allocation is optimal and has one compressed record per nonempty agent type. Henceforth assume m>0m>0, and therefore q≥1q≥ 1. Empty agent types may be deleted, so assume nk≥1n_k≥ 1 for every k∈[K]k∈[K]. If ε≥1 ≥ 1, any allocation satisfies the claimed guarantee. Hence, assume ε∈(0,1) ∈(0,1) and choose a positive rational δ satisfying 0<δ≤min110,ε12+2/|p|,p≠0,min110,ε14,p=0.0<δ≤ cases \ 110, 12+2/|p| \,&p≠ 0,\\[11.38109pt] \ 110, 14 \,&p=0. cases (62) 6.2 Algorithmic overview We first describe the complete algorithm at a high level. The subsequent subsections define its ingredients and prove their guarantees. The structural lemma separates, within every agent type, singleton agents from residual agents controlled by a common utility threshold. The algorithm enumerates a geometric approximation of every threshold, represents residual agents by a constant collection of configurations, and solves the resulting aggregate allocation problem. Support guessing leaves only a constant number of integer variables. A totally unimodular residual program then rounds the remaining aggregate variables, after which batched procedures reconstruct a compressed allocation. Algorithm 3 summarizes these steps. Algorithm 3 PTAS for a fixed number of agent types 1: A high-multiplicity instance, a fixed rational p<1p<1, and ε∈(0,1) ∈(0,1) 2: if m=0m=0 then 3: return the compressed allocation giving every agent the empty bundle 4: Choose δ according to (62) 5: if p≤0p≤ 0 then 6: Run the positive-utility flow test; if it fails, return any allocation 7: Construct the threshold sets 1,…,KT_1,…,T_K 8: for each enumerated threshold vector not discarded by the positivity condition do 9: Normalize and round the values and construct the retained configurations 10: Form the rationalized configuration integer program 11: for each enumerated small-good support tuple J do 12: Solve the restricted mixed-integer program; skip it if it is infeasible 13: Fix its integer variables and compute an optimal basic solution of the resulting linear program 14: Round the aggregate assignment by solving the reduced assignment LP 15: Reconstruct and store the corresponding compressed allocation 16: Evaluate all reconstructed candidates using directed rational approximations of their actual utilities 17: return the candidate with the best certified objective value 6.3 Transformed objectives and positivity We use the transformed function ϕp _p from Section 3. For every finite p<1p<1, it is increasing and strictly concave on its stated domain. For p≤0p≤ 0, apply the positive-utility flow test from Section 5.3. Its construction and proof apply to arbitrary K and q and run in polynomial time in the compact input length. If the maximum flow has value less than n, then OPTp=0OPT_p=0; return any compressed allocation and terminate. Henceforth, when p≤0p≤ 0, assume that a positive allocation exists and discard zero-utility configurations. 6.4 The residual structural lemma Lemma 11 (Balancing exchange). Let I⊆ℝI be an interval, and let Φ:I→ℝ :I be strictly concave. Suppose H,L,H−d,L+d∈IH,L,H-d,L+d∈ I, d>0d>0, and H−d>LH-d>L. Then Φ(H−d)+Φ(L+d)>Φ(H)+Φ(L). (H-d)+ (L+d)> (H)+ (L). Proof. Set λ:=d/(H−L)λ:=d/(H-L). The assumptions give 0<λ<10<λ<1, and H−d=(1−λ)H+λLH-d=(1-λ)H+λ L, L+d=λH+(1−λ)L.L+d=λ H+(1-λ)L. Strict concavity at these two convex combinations yields Φ(H−d)>(1−λ)Φ(H)+λΦ(L), (H-d)>(1-λ) (H)+λ (L), Φ(L+d)>λΦ(H)+(1−λ)Φ(L). (L+d)>λ (H)+(1-λ) (L). Adding proves the assertion. ∎ Lemma 12 (Structure of an optimal allocation). Fix a finite p<1p<1. If p≤0p≤ 0, assume that an allocation giving every agent positive utility exists. There is an optimal allocation x∗=(xi,j∗:i∈[n],j∈[q])x^*=(x_i,j^*:i∈[n],\ j∈[q]) with the following property. For every agent type k, its agent set AkA_k can be partitioned as Ak=Hk∪˙Rk,A_k=H_k ∪R_k, where Rk≠∅R_k≠ , and there is a threshold τk≥0 _k≥ 0 such that: 1. Every agent i∈Hki∈ H_k receives exactly one good having positive value to type k: ∑j:uk,j>0xi,j∗=1. _j:u_k,j>0x_i,j^*=1. If this good is of type j, then uk,j>τku_k,j> _k. 2. Every positive-value good assigned to a residual agent has value at most τk _k. That is, for every i∈Rki∈ R_k and j∈[q]j∈[q], if xi,j∗>0x_i,j^*>0 and uk,j>0u_k,j>0 then uk,j≤τk.u_k,j≤ _k. 3. If τk>0 _k>0, then every i∈Rki∈ R_k satisfies τk2≤uk(xi∗)≤2τk. _k2≤ u_k(x^*_i)≤ 2 _k. 4. If τk=0 _k=0, then uk(xi∗)=0u_k(x^*_i)=0 for every i∈Rki∈ R_k. The threshold is the average utility of the residual agents: τk=1|Rk|∑i∈Rkuk(xi∗). _k= 1|R_k| _i∈ R_ku_k(x^*_i). Proof. For 0<p<10<p<1, choose an allocation x∗x^* maximizing the transformed objective Φp _p over all allocations. For p≤0p≤ 0, choose x∗x^* to maximize Φp _p over the nonempty set of allocations giving every agent positive utility. In either case, x∗x^* maximizes PSWpPSW_p. Fix an agent type k. We construct HkH_k, RkR_k, and τk _k while leaving x∗x^* unchanged. Initially, let Hk=∅H_k= and Rk=AkR_k=A_k. While RkR_k is being constructed, write τ(Rk):=1|Rk|∑i∈Rkuk(xi∗)τ(R_k):= 1|R_k| _i∈ R_ku_k(x^*_i) for its current average utility. Suppose that some agent a∈Rka∈ R_k receives a good of type j satisfying uk,j>τ(Rk).u_k,j>τ(R_k). We claim that this is the only positive-value good received by a. Indeed, since uk(xi∗)u_k(x_i^*) has average τ(Rk)τ(R_k) over RkR_k, there is an agent b∈Rkb∈ R_k such that uk(xb∗)≤τ(Rk).u_k(x^*_b)≤τ(R_k). Moreover, b≠ab≠ a, because uk(xa∗)≥uk,j>τ(Rk).u_k(x^*_a)≥ u_k,j>τ(R_k). Suppose that a receives another positive-value good, of type j′j . Let x′x be obtained from x∗x^* by transferring this good from a to b; that is, xa,j′=xa,j′∗−1,x _a,j =x_a,j ^*-1, and xb,j′=xb,j′∗+1,x _b,j =x_b,j ^*+1, and all other entries remain unchanged. The allocation x′x is feasible. Since the selected type-j good remains with a, uk(xa′)=uk(xa∗)−uk,j′≥uk,j>τ(Rk)≥uk(xb∗),u_k(x _a)=u_k(x_a^*)-u_k,j ≥ u_k,j>τ(R_k)≥ u_k(x_b^*), whereas uk(xb′)=uk(xb∗)+uk,j′u_k(x _b)=u_k(x_b^*)+u_k,j . When p≤0p≤ 0, these inequalities also show that both affected agents retain positive utility, so x′x lies in the domain of ϕp _p. Lemma 11 now gives ϕp(uk(xa′))+ϕp(uk(xb′))>ϕp(uk(xa∗))+ϕp(uk(xb∗)). _p (u_k(x _a) )+ _p (u_k(x _b) )> _p (u_k(x_a^*) )+ _p (u_k(x_b^*) ). All other agents’ bundles are unchanged, and hence Φp(x′)>Φp(x∗) _p(x )> _p(x^*), contradicting the optimality of x∗x^*. Therefore, a receives exactly one positive-value good, namely the selected type-j good. Add a to HkH_k and remove it from RkR_k. The set RkR_k contains at least two agents before this removal. Indeed, if Rk=aR_k=\a\, then τ(Rk)=uk(xa∗)τ(R_k)=u_k(x_a^*), and no good assigned to a can have value greater than uk(xa∗)u_k(x_a^*). Hence, if r=|Rk|r=|R_k| before the removal and τ=τ(Rk)τ=τ(R_k), then r≥2r≥ 2. Since the removed agent has utility uk,j>τu_k,j>τ, the new residual average is rτ−uk,jr−1<τ. rτ-u_k,jr-1<τ. Continue removing agents in this way until no residual agent receives a good whose value is greater than the current residual average. The procedure terminates after at most |Ak|−1|A_k|-1 removals. Let HkH_k and RkR_k be the resulting sets, and put τk:=1|Rk|∑i∈Rkuk(xi∗). _k:= 1|R_k| _i∈ R_ku_k(x_i^*). Each agent placed in HkH_k receives exactly one positive-value good. The value of that good exceeded the residual average at the time of removal. Because the residual averages strictly decrease, its value also exceeds the final average τk _k. This proves property 1. Moreover, at termination, no residual agent receives a good whose value is greater than τk _k. This proves property 2. Suppose that τk>0 _k>0. If some a∈Rka∈ R_k had uk(xa∗)>2τku_k(x^*_a)>2 _k, then some b∈Rkb∈ R_k would satisfy uk(xb∗)≤τku_k(x^*_b)≤ _k. Choose any positive-value good of type j assigned to a. Property 2 gives uk,j≤τku_k,j≤ _k, and hence uk(xa∗)−uk,j>τk≥uk(xb∗).u_k(x^*_a)-u_k,j> _k≥ u_k(x^*_b). Moving this good from a to b would strictly improve the transformed objective by Lemma 11, contradicting optimality. Therefore uk(xi∗)≤2τku_k(x_i^*)≤ 2 _k for every i∈Rki∈ R_k. Conversely, suppose that some b∈Rkb∈ R_k had uk(xb∗)<τk/2u_k(x_b^*)< _k/2. Because τk _k is the residual average, there would be an agent a∈Rka∈ R_k with uk(xa∗)>τku_k(x_a^*)> _k. Agent a must receive at least two positive-value goods; otherwise its unique positive-value good would have value greater than τk _k, contrary to property 2. Choose a positive-value good of minimum value among those assigned to a, and let j be its type. Since a receives at least two positive-value goods, uk,j≤uk(xa∗)2.u_k,j≤ u_k(x^*_a)2. It follows that uk(xa∗)−uk,j≥uk(xa∗)2>τk2>uk(xb∗).u_k(x^*_a)-u_k,j≥ u_k(x^*_a)2> _k2>u_k(x^*_b). Moving this good from a to b would again contradict optimality by Lemma 11. Thus uk(xi∗)≥τk/2u_k(x_i^*)≥ _k/2 for every i∈Rki∈ R_k, proving property 3. Finally, if τk=0 _k=0, then ∑i∈Rkuk(xi∗)=0. _i∈ R_ku_k(x^*_i)=0. Nonnegativity implies uk(xi∗)=0u_k(x_i^*)=0 for every i∈Rki∈ R_k, proving property 4. When p≤0p≤ 0, this case cannot occur because x∗x^* gives every agent positive utility. Applying this construction independently to every agent type proves the lemma. ∎ 6.5 Guessing and rounding the residual thresholds Use the rational parameter δ fixed in (62). Fix also the optimal allocation x∗x^* and the sets Hk,RkH_k,R_k and thresholds τk _k given by Lemma 12. We refer to x∗x^* as the canonical optimum. This optimum and the preceding peeling construction are used only in the analysis; the algorithm computes neither of them. For every agent type k, define Uk:=∑j=1qmjuk,j.U_k:= _j=1^qm_ju_k,j. Thus UkU_k is an upper bound on the total utility that all available goods could provide to type-k agents. For every agent type k, define k+:=j∈[q]:uk,j>0.J_k^+:=\j∈[q]:u_k,j>0\. If k+≠∅J_k^+≠ , define ukmin:=minj∈k+uk,j.u_k := _j _k^+u_k,j. If k+=∅J_k^+= , then Uk=0U_k=0, every type-k agent has utility zero under every allocation, and we enumerate only the threshold guess 00. Suppose first that τk>0 _k>0. By the definition of τk _k, |Rk|τk=∑i∈Rkuk(xi∗).|R_k| _k= _i∈ R_ku_k(x_i^*). The sum on the right is positive and is composed of values of goods assigned to agents in RkR_k. It is therefore at least ukminu_k . Since |Rk|≤nk|R_k|≤ n_k, we obtain τk≥ukmin|Rk|≥ukminnk. _k≥ u_k |R_k|≥ u_k n_k. Moreover, τk≤∑i∈Rkuk(xi∗)≤Uk. _k≤ _i∈ R_ku_k(x_i^*)≤ U_k. Consequently, ukminnk≤τk≤Uk. u_k n_k≤ _k≤ U_k. For a type k with Uk>0U_k>0, let sks_k be the smallest nonnegative integer satisfying ukminnk(1+δ)sk≥Uk, u_k n_k(1+δ)^s_k≥ U_k, and define the set of threshold guesses k:=0∪ukminnk(1+δ)s:s=0,1,…,sk.T_k:=\0\∪ \ u_k n_k(1+δ)^s:s=0,1,…,s_k \. (63) If Uk=0U_k=0, define k:=0T_k:=\0\. If τk=0 _k=0, then 0∈k0 _k is a correct guess. If τk>0 _k>0, choose the smallest positive τ^k∈k τ_k _k satisfying τ^k≥τk τ_k≥ _k. By minimality, τk≤τ^k<(1+δ)τk. _k≤ τ_k<(1+δ) _k. We call such a value τ^k τ_k a correct threshold guess for type k. For fixed δ, |k|=Oδ(1+lognkUkukmin)|T_k|=O_δ (1+ n_kU_ku_k ) whenever Uk>0U_k>0. The logarithm is bounded by a polynomial in the binary encoding length of the instance. The guesses themselves also have polynomial encoding length because δ is fixed and rational. Since K is fixed, all vectors (τ^1,…,τ^K)∈1×⋯×K( τ_1,…, τ_K) _1×·s×T_K can be enumerated in polynomial time, and at least one enumerated vector is correct for every agent type. Normalization and geometric rounding. Consider a type k with τ^k>0 τ_k>0, and define αk:=δτ^k. _k:=δ τ_k. For every j∈[q]j∈[q] with uk,j>0u_k,j>0, define the rounded normalized value u¯k,j:=(1+δ)⌊log1+δ(uk,jαk)⌋. u_k,j:=(1+δ) _1+δ ( u_k,j _k ) . If uk,j=0u_k,j=0, set u¯k,j:=0 u_k,j:=0. Thus, for every uk,j>0u_k,j>0, uk,jαk(1+δ)<u¯k,j≤uk,jαk. u_k,j _k(1+δ)< u_k,j≤ u_k,j _k. (64) The exponent can be computed in polynomial time by binary search, using exact comparisons between rational powers. Among the positive-value goods, call a good of type j • small for type k if 0<u¯k,j<10< u_k,j<1; • large for type k if 1≤u¯k,j≤1/δ1≤ u_k,j≤ 1/δ; • huge for type k if u¯k,j>1/δ u_k,j>1/δ. Under a correct threshold guess, every huge good has original value greater than τk _k. Indeed, uk,j≥αku¯k,j>δτ^k1δ=τ^k≥τk.u_k,j≥ _k u_k,j>δ τ_k 1δ= τ_k≥ _k. It follows from Lemma 12 that any such good assigned to a type-k agent in x∗x^* is the unique positive-value good assigned to an agent in HkH_k. Regular configurations. Define rmax:=⌊log1+δ1δ⌋,ℛδ:=0,1,…,rmax,r_ := _1+δ 1δ , _δ:=\0,1,…,r_ \, and let Bδ:=|ℛδ|=rmax+1.B_δ:=|R_δ|=r_ +1. Every rounded large value is equal to (1+δ)r(1+δ)^r for some r∈ℛδr _δ. For a type k satisfying τ^k>0 τ_k>0, a regular configuration is a tuple C=(k(C),(ar(C))r∈ℛδ,μ(C)),C= (k(C),\,(a_r(C))_r _δ,\,μ(C) ), where • k(C)∈[K]k(C)∈[K] is an integer recording the agent type of the configuration; • ar(C)≥0a_r(C)≥ 0, for r∈ℛδr _δ, is an integer representing the number of large goods of rounded normalized value (1+δ)r(1+δ)^r; and • μ(C)≥0μ(C)≥ 0 is an integer representing a rounded-down lower requirement on the total rounded normalized value of the small goods. The estimated normalized utility of C is w(C):=∑r∈ℛδar(C)(1+δ)r+μ(C).w(C):= _r _δa_r(C)(1+δ)^r+μ(C). We retain only configurations satisfying 15δ≤w(C)≤4δ. 15δ≤ w(C)≤ 4δ. (65) For every type k with τ^k>0 τ_k>0, let kC_k denote the set of retained regular configurations C satisfying k(C)=k(C)=k. For every type k with τ^k=0 τ_k=0, define k:=∅.C_k:= . Finally, put :=⋃k:τ^k>0k.C:= _k: τ_k>0C_k. Because the agent type is included as a component of every configuration, the sets kC_k are pairwise disjoint. Because each large good contributes at least one to w(C)w(C), every retained configuration satisfies ∑r∈ℛδar(C)≤4δ _r _δa_r(C)≤ 4δ and μ(C)≤4δ.μ(C)≤ 4δ. Hence, for each type k, the number of retained regular configurations is at most (⌊4δ⌋+1)Bδ+1, ( 4δ +1 )^B_δ+1, which depends only on δ. Across all agent types, the number of regular configurations depends only on K and δ. Representation of canonical residual agents. Assume that τ^k τ_k is a correct positive guess. Fix an agent i∈Rki∈ R_k, and put Vi:=uk(xi∗)αk.V_i:= u_k(x_i^*) _k. Lemma 12 and the correctness of the guess give 12δ(1+δ)<Vi≤2δ. 12δ(1+δ)<V_i≤ 2δ. Indeed, uk(xi∗)≥τk2u_k(x_i^*)≥ _k2, αk=δτ^k<δ(1+δ)τk, _k=δ τ_k<δ(1+δ) _k, which gives the lower bound, while uk(xi∗)≤2τku_k(x_i^*)≤ 2 _k, αk≥δτk, _k≥δ _k, gives the upper bound. No huge good is assigned to i, because every huge good has original value greater than τk _k. Let LiL_i and SiS_i denote, respectively, the total rounded normalized values of the large and small goods assigned to i. Then V¯i:=Li+Si V_i:=L_i+S_i is the total rounded normalized utility of i. We get by (64) Vi1+δ<V¯i≤Vi. V_i1+δ< V_i≤ V_i. Define a regular configuration CiC_i by retaining the number of large goods in each class and setting μ(Ci):=⌊Si⌋.μ(C_i):= S_i . Its estimated normalized utility is w(Ci)=Li+⌊Si⌋.w(C_i)=L_i+ S_i . Since ⌊Si⌋>Si−1 S_i >S_i-1, we have w(Ci)>V¯i−1>Vi1+δ−1.w(C_i)> V_i-1> V_i1+δ-1. Consequently, w(Ci)>12δ(1+δ)2−1≥15δ,w(C_i)> 12δ(1+δ)^2-1≥ 15δ, where the last inequality uses δ≤1/10δ≤ 1/10. Furthermore, w(Ci)≤V¯i≤Vi≤2δ≤4δ.w(C_i)≤ V_i≤ V_i≤ 2δ≤ 4δ. Thus CiC_i is retained by (65). Because w(Ci)w(C_i) is expressed in normalized units, αkw(Ci) _kw(C_i) is the estimated utility of CiC_i on the original utility scale. From the preceding inequalities, αkw(Ci)>uk(xi∗)1+δ−αk. _kw(C_i)> u_k(x_i^*)1+δ- _k. Since uk(xi∗)≥τk/2u_k(x_i^*)≥ _k/2 and αk<δ(1+δ)τk _k<δ(1+δ) _k, we have αk<2δ(1+δ)uk(xi∗). _k<2δ(1+δ)u_k(x_i^*). It follows that αkw(Ci)>(11+δ−2δ(1+δ))uk(xi∗)≥(1−4δ)uk(xi∗), _kw(C_i)> ( 11+δ-2δ(1+δ) )u_k(x_i^*)≥(1-4δ)u_k(x_i^*), where the final inequality holds for δ≤1/10δ≤ 1/10. Representation of canonical singleton agents. Suppose that τ^k τ_k is a correct positive guess. Consider an agent i∈Hki∈ H_k, and suppose that its unique positive-value good is of type j. If u¯k,j>1/δ u_k,j>1/δ, represent i by the corresponding huge singleton. Suppose instead that u¯k,j≤1/δ u_k,j≤ 1/δ. Since uk,j>τku_k,j> _k and αk<δ(1+δ)τk _k<δ(1+δ) _k, we have u¯k,j>uk,jαk(1+δ)>1δ(1+δ)2. u_k,j> u_k,j _k(1+δ)> 1δ(1+δ)^2. In particular, this good is large. Represent i by the regular configuration having one good in the corresponding large class, no other large goods, and μ=0μ=0. Its estimated normalized utility is w(Ci)=u¯k,jw(C_i)= u_k,j. For δ≤1/10δ≤ 1/10, 15δ<w(Ci)≤1δ≤4δ, 15δ<w(C_i)≤ 1δ≤ 4δ, so this configuration is retained. Moreover, αkw(Ci)>uk,j1+δ≥(1−4δ)uk,j. _kw(C_i)> u_k,j1+δ≥(1-4δ)u_k,j. Zero-threshold types. Finally, suppose that the correct guess is τ^k=τk=0 τ_k= _k=0. By Lemma 12, every agent in RkR_k has utility zero, while every agent in HkH_k receives exactly one positive-value good. This case can occur only when 0<p<10<p<1, because for p≤0p≤ 0 the canonical optimum gives every agent positive utility. For a zero-threshold type, represent each agent in RkR_k by a zero configuration and represent each agent in HkH_k by its positive singleton with its exact, unnormalized value uk,ju_k,j. Goods having zero value to type k need not be represented and may temporarily remain unused. We summarize these observations in the following lemma. Lemma 13 (Threshold guesses and bundle representation). Fix K and a rational δ∈(0,1/10]δ∈(0,1/10] and let kT_k be defined as in (63). There exists a threshold vector (τ^1,…,τ^K)∈1×⋯×K( τ_1,…, τ_K) _1×·s×T_K that satisfies, for every k∈[K]k∈[K], τ^k=0 τ_k=0 if τk=0, _k=0, and τk≤τ^k<(1+δ)τk _k≤ τ_k<(1+δ) _k if τk>0 _k>0. Moreover, for every type k with τ^k>0 τ_k>0, every bundle xi∗x_i^* assigned to an agent i∈Aki∈ A_k in the canonical optimum can be represented in one of the following ways: 1. If i∈Rki∈ R_k, then xi∗x_i^* induces a retained regular configuration CiC_i (satisfying (65)). 2. If i∈Hki∈ H_k and its unique positive-value good is huge, then xi∗x_i^* is represented by the corresponding huge singleton. 3. If i∈Hki∈ H_k and its unique positive-value good is not huge, then xi∗x_i^* induces a retained regular configuration containing exactly that one large good. Let u~i u_i denote the represented utility on the original scale, namely u~i:=αkw(Ci),if xi∗ is represented by a regular configuration,αku¯k,j,if xi∗ is represented by a huge type-j singleton, u_i:= cases _kw(C_i),&if $x_i^*$ is represented by a regular configuration,\\[4.30554pt] _k u_k,j,&if $x_i^*$ is represented by a huge type-$j$ singleton, cases Then (1−4δ)uk(xi∗)≤u~i≤uk(xi∗).(1-4δ)u_k(x_i^*)≤ u_i≤ u_k(x_i^*). If τ^k=τk=0 τ_k= _k=0, then 0<p<10<p<1, every agent in RkR_k has utility zero, and every agent in HkH_k receives exactly one positive-value good. Such agents are represented, respectively, by zero configurations and exact positive singletons. Finally, the number of retained regular configurations over all agent types is bounded by a function of K and δ only. 6.6 The configuration formulation Fix an enumerated threshold vector (τ^1,…,τ^K)( τ_1,…, τ_K). Define +:=k∈[K]:τ^k>0and0:=k∈[K]:τ^k=0.K_+:=\k∈[K]: τ_k>0\ _0:=\k∈[K]: τ_k=0\. We call the types in +K_+ positive-threshold types and those in 0K_0 zero-threshold types. For a correct threshold vector, these sets agree, respectively, with the types satisfying τk>0 _k>0 and τk=0 _k=0. When p≤0p≤ 0, the positivity assumption implies that every true threshold τk _k is positive. We may therefore discard every enumerated threshold vector for which 0≠∅K_0≠ in this case. For every k∈+k _+, define k:=j∈[q]:0<u¯k,j<1,S_k:=\j∈[q]:0< u_k,j<1\, ℒk,r:=j∈[q]:u¯k,j=(1+δ)r,r∈ℛδ,L_k,r:=\j∈[q]: u_k,j=(1+δ)^r\, r _δ, and khuge:=j∈[q]:u¯k,j>1δ.J_k^huge:= \j∈[q]: u_k,j> 1δ \. Thus kS_k is the set of small good types, ℒk,rL_k,r is the set of large good types in class r, and khugeJ_k^huge is the set of huge good types, all relative to agent type k. Recall that kC_k is the set of retained regular configurations of type k, and =⋃k=1Kk.C= _k=1^KC_k. For k∈0k _0, we have k=∅C_k= . Variables and represented values. For every k∈[K]k∈[K] and j∈[q]j∈[q], the variable xk,jx_k,j is the number of type-j goods reserved for type-k agents. For every C∈C , the variable y(C)y(C) is the number of agents of type k(C)k(C) represented by C. For every k∈0k _0, the variable zkz_k is the number of type-k agents represented by the zero configuration. Define the set of singleton pairs ℐsing:=(k,j):k∈+,j∈khuge∪(k,j):k∈0,j∈k+.I_sing:= \(k,j):k _+,\ j _k^huge \∪ \(k,j):k _0,\ j _k^+ \. For every (k,j)∈ℐsing(k,j) _sing, define its represented utility by vk,j:=αku¯k,j,k∈+,uk,j,k∈0.v_k,j:= cases _k u_k,j,&k _+,\\[4.30554pt] u_k,j,&k _0. cases Thus, huge singletons use their rounded original-scale values, whereas positive singletons of zero-threshold types use their exact values. For every regular configuration C∈C , define its represented utility on the original scale by v(C):=αk(C)w(C).v(C):= _k(C)w(C). Define the exact transformed objective Ψp(x,y):=∑C∈ϕp(v(C))y(C)+∑(k,j)∈ℐsingϕp(vk,j)xk,j. _p(x,y):= _C _p (v(C) )y(C)+ _(k,j) _sing _p(v_k,j)x_k,j. Configuration ILP. The exact configuration formulation is the following integer linear program. maximizex,y,z x,y,zmaximize Ψp(x,y) _p(x,y) (66a) subject to: ∑k=1Kxk,j≤mj _k=1^Kx_k,j≤ m_j j∈[q], j∈[q], (66b) ∑C∈ky(C)+∑j∈khugexk,j=nk _C _ky(C)+ _j _k^hugex_k,j=n_k k∈+, k _+, (66c) ∑j∈ℒk,rxk,j≥∑C∈kar(C)y(C) _j _k,rx_k,j≥ _C _ka_r(C)y(C) k∈+,r∈ℛδ, k _+,r _δ, (66d) ∑j∈ku¯k,jxk,j≥∑C∈kμ(C)y(C) _j _k u_k,jx_k,j≥ _C _kμ(C)y(C) k∈+, k _+, (66e) zk+∑j∈k+xk,j=nk z_k+ _j _k^+x_k,j=n_k k∈0, k _0, (66f) xk,j=0 x_k,j=0 k∈[K],j∈[q] with uk,j=0, k∈[K],\ j∈[q] with u_k,j=0, (66g) xk,j∈ℤ≥0 x_k,j _≥ 0 k∈[K],j∈[q], k∈[K],\ j∈[q], (66h) y(C)∈ℤ≥0 y(C) _≥ 0 C∈, C , (66i) zk∈ℤ≥0 z_k _≥ 0 k∈0. k _0. (66j) We denote this exact integer formulation by ConfIP(^)ConfIP( τ). It is used only for analysis; the algorithm solves the rational formulation introduced below. Constraint (66b) limits the reserved supply. Constraint (66c) represents every positive-threshold agent either by a regular configuration or by a huge singleton. Constraints (66d) and (66e) reserve the resources required by the regular configurations. Constraint (66f) represents every zero-threshold agent either by a zero configuration or by an exact positive singleton. Constraint (66g) discards reservations that provide no utility. Some goods may remain unreserved and will be assigned after reconstruction. Let ℱ(^)F( τ) be the set of nonnegative real vectors (x,y,z)(x,y,z) satisfying (66b), (66c), (66d), (66e), (66f), and (66g). Let ℱIP(^)F_IP( τ) be the subset also satisfying (66h)–(66j). For 0<p<10<p<1, a zero configuration contributes ϕp(0)=0 _p(0)=0 and is therefore omitted from (66a). For p≤0p≤ 0, threshold vectors having a zero coordinate have already been discarded. Hence every represented utility appearing in (66a) is positive, and ϕp _p is well-defined. The normalization factors αk _k cannot in general be omitted. For p≠0p≠ 0, the coefficient of a regular configuration contains the factor αk(C)p _k(C)^p, which may differ between agent types. For p=0p=0, logv(C)=logαk(C)+logw(C). v(C)= _k(C)+ w(C). By constraint (66c), exactly nkn_k represented agents belong to every positive-threshold type k. Thus the terms involving logαk _k sum to the constant nklogαkn_k _k for that type. We nevertheless retain these terms so that v(C)v(C) always denotes utility on the original scale. Lemma 14 (Representation of the canonical optimum). For a correct threshold vector, the canonical optimum x∗x^* induces a feasible solution of ConfIP(^)ConfIP( τ). For every agent having positive utility in x∗x^*, its represented utility u~i u_i satisfies (1−4δ)uk(xi∗)≤u~i≤uk(xi∗),i∈Ak.(1-4δ)u_k(x_i^*)≤ u_i≤ u_k(x_i^*), i∈ A_k. (67) Proof. Fix a correct threshold vector. For every k,jk,j, set xk,j:=∑i∈Akxi,j∗,uk,j>0,0,uk,j=0.x_k,j:= cases _i∈ A_kx_i,j^*,&u_k,j>0,\\ 0,&u_k,j=0. cases (68) For k∈+k _+, let Ikreg⊆AkI_k^reg A_k be the type-k agents represented by regular configurations in Lemma 13, and use the configurations CiC_i supplied there. Set y(C):=|i∈Ik(C)reg:Ci=C|.y(C):=|\i∈ I_k(C)^reg:C_i=C\|. For k∈0k _0, set zk:=|Rk|.z_k:=|R_k|. All these variables are nonnegative integers. Ignoring zero-value assignments can only decrease item use, so the item-capacity and zero-value constraints hold. For a positive-threshold type, every agent outside IkregI_k^reg receives exactly one huge good, while no regular agent receives a huge good. This proves the corresponding agent-count equality. For a zero-threshold type, the positive-value goods are exactly the singleton goods of HkH_k, and zk=|Rk|=nk−|Hk|z_k=|R_k|=n_k-|H_k|, proving its agent-count equality. Every large or small good assigned to a positive-threshold type belongs to a regular agent’s bundle. Hence, for every k∈+k _+ and r∈ℛδr _δ, ∑j∈ℒk,rxk,j=∑i∈Ikregar(Ci)=∑C∈kar(C)y(C). _j _k,rx_k,j= _i∈ I_k^rega_r(C_i)= _C _ka_r(C)y(C). Writing Si:=∑j∈ku¯k,jxi,j∗S_i:= _j _k u_k,jx_i,j^*, we also have ∑C∈kμ(C)y(C)=∑i∈Ikreg⌊Si⌋≤∑j∈ku¯k,jxk,j. _C _kμ(C)y(C)= _i∈ I_k^reg S_i ≤ _j _k u_k,jx_k,j. These are the large- and small-capacity constraints, completing the feasibility verification. The represented-utility bound follows from Lemma 13 for positive-threshold types. For a positive singleton of a zero-threshold type, u~i=uk(xi∗) u_i=u_k(x_i^*), so the same bound holds. ∎ 6.7 Solving and rounding the configuration formulation Directed rational objective coefficients. Apply Lemma 1 with accuracy δ to each positive rational represented value v. Write c~p(v):=ϕ~p,δ(v) c_p(v):= φ_p,δ(v) for 0≤p<10≤ p<1 and c~p(v):=−ϕ~p,δ(v) c_p(v):=- φ_p,δ(v) for p<0p<0. Thus vp1+δ≤c~p(v)≤vpif 0<p<1, v^p1+δ≤ c_p(v)≤ v^p 0<p<1, (69) and vp≤c~p(v)≤(1+δ)vpif p<0.v^p≤ c_p(v)≤(1+δ)v^p p<0. (70) For p=0p=0, the same construction gives logv−δ≤c~0(v)≤logv. v-δ≤ c_0(v)≤ v. When 0<p<10<p<1, we also put c~p(0)=0 c_p(0)=0. The logarithmic bound follows from log(1+δ)≤δ (1+δ)≤δ. The lemma computes all these coefficients in polynomial time and with polynomial encoding length. Recall that v(C)=αk(C)w(C)v(C)= _k(C)w(C) is the represented value of a regular configuration C, and that vk,jv_k,j is the represented value of a singleton pair (k,j)∈ℐsing(k,j) _sing. Define the signed rational coefficient ϕ~p(v):=c~p(v),0≤p<1,−c~p(v),p<0,=ϕ~p,δ(v), φ_p(v):= cases c_p(v),&0≤ p<1,\\ - c_p(v),&p<0, cases= φ_p,δ(v), and the rational transformed objective Ψ~p(x,y):=∑C∈ϕ~p(v(C))y(C)+∑(k,j)∈ℐsingϕ~p(vk,j)xk,j. _p(x,y):= _C φ_p (v(C) )y(C)+ _(k,j) _sing φ_p(v_k,j)x_k,j. Thus every approximated objective coefficient is a rational number of polynomial encoding length. The sign in the definition of ϕ~p φ_p permits every formulation below to be written as a maximization problem. Fix an enumerated threshold vector ^:=(τ^1,…,τ^K). τ:=( τ_1,…, τ_K). Define the rationalized configuration program ConfIP~(^) ConfIP( τ) by maximizing Ψ~p(x,y) _p(x,y) over (x,y,z)∈ℱIP(^)(x,y,z) _IP( τ). It has the same integral feasible solutions as ConfIP(^)ConfIP( τ) and differs only in its objective coefficients. Guessing the support of the small-good assignment. Let D:=K(Bδ+2)D:=K(B_δ+2), F:=2D,F:=2D, and d:=⌈Fδ⌉.d:= Fδ . Here, D≥|0|+(Bδ+2)|+|D≥|K_0|+(B_δ+2)|K_+| is an upper bound on the total number of non-item constraints (66c), (66d), (66e), and (66f): for each positive-threshold type, there is exactly one agent-count constraint, BδB_δ large-class constraints, and one weighted small-value constraint. For each zero-threshold type, there is exactly one agent-count constraint and no large-class or weighted small-value constraints. For every k∈+k _+, enumerate every set Jk⊆kJ_k _k satisfying |Jk|≤d|J_k|≤ d. If |Jk|<d|J_k|<d, interpret JkJ_k as the complete support of the type-k small-good assignment. The empty set is allowed. If |Jk|=d|J_k|=d, interpret JkJ_k as the d highest-valued small good types in that support and define γk:=minj∈Jku¯k,j. _k:= _j∈ J_k u_k,j. In the second case, unguessed types of rounded value at most γk _k may still be used. Define the set of forbidden small-good types by k(Jk):=k∖Jk,|Jk|<d,j∈k∖Jk:u¯k,j>γk,|Jk|=d.D_k(J_k):= casesS_k J_k,&|J_k|<d,\\[2.84526pt] \j _k J_k: u_k,j> _k\,&|J_k|=d. cases Fix a support tuple =(Jk)k∈+J=(J_k)_k _+ and put ℐx:=(k,j):k∈+,j∈Jk.I_J^x:=\(k,j):k _+,\ j∈ J_k\. The associated restricted mixed-integer program is maximizex,y,z x,y,zmaximize Ψ~p(x,y) _p(x,y) (71a) subject to: (x,y,z)∈ℱ(^) (x,y,z) ( τ) (71b) xk,j≥1 x_k,j≥ 1 k∈+,j∈Jk, k _+,\ j∈ J_k, (71c) xk,j=0 x_k,j=0 k∈+,j∈k(Jk), k _+,\ j _k(J_k), (71d) y(C)∈ℤ≥0 y(C) _≥ 0 C∈, C , (71e) zk∈ℤ≥0 z_k _≥ 0 k∈0, k _0, (71f) xk,j∈ℤ≥0 x_k,j _≥ 0 (k,j)∈ℐx, (k,j) _J^x, (71g) xk,j∈ℝ≥0 x_k,j _≥ 0 (k,j)∈([K]×[q])∖ℐx. (k,j)∈([K]×[q]) _J^x. (71h) We denote this program by ConfMIP~(^,) ConfMIP( τ,J). Variables fixed by (66g) or (71d) may be eliminated. For each k, the number of possible sets JkJ_k is at most (qd)+∑h=0d−1(qh)≤(q+1)d. qd+ _h=0^d-1 qh≤(q+1)^d. Consequently, the total number of restricted programs is at most (q+1)Kd=qOK,δ(1),(q+1)^Kd=q^O_K,δ(1), which is polynomial for fixed K and δ. Moreover, every restricted program has at most ||+K+Kd=OK,δ(1)|C|+K+Kd=O_K,δ(1) integer variables. It can therefore be solved in polynomial time by fixed-dimensional mixed-integer linear programming Lenstra Jr. (1983). For a feasible restricted program, let ξ be the values of all variables required to be integral in (71e)–(71g) at an optimal solution. After fixing these variables to ξ, let ConfLP~(^,,) ConfLP( τ,J; ξ) denote the remaining linear program, with the constraints and rational objective of (71). Choose an optimal basic feasible solution of this program. The following lemma establishes the required rounding property. Lemma 15 (Rounding the aggregate assignment). Fix an arbitrary enumerated threshold vector τ. If ConfIP~(^) ConfIP( τ) is feasible, then among the restricted mixed-integer programs associated with the tuples =(Jk)k∈+J=(J_k)_k _+, at least one contains an optimal solution of ConfIP~(^) ConfIP( τ). For any feasible restricted mixed-integer program, the following rounding assertion holds. Solve that program optimally. Let (x^,y^,z^)( x, y, z) be an optimal basic feasible solution of the associated fixed-variable program ConfLP~(^,,) ConfLP( τ,J; ξ). Then one can compute in polynomial time a vector x¯∈ℤ≥0K×q x _≥ 0^K× q such that (x¯,y^,z^)( x, y, z) has the following properties. 1. The vector (x¯,y^,z^)( x, y, z) satisfies (66b), (66c), (66d), (66f), and (66g). 2. The singleton contribution to the rational objective satisfies ∑(k,j)∈ℐsingϕ~p(vk,j)x¯k,j≥∑(k,j)∈ℐsingϕ~p(vk,j)x^k,j. _(k,j) _sing φ_p(v_k,j) x_k,j≥ _(k,j) _sing φ_p(v_k,j) x_k,j. Since the variables y^(C) y(C) and z^k z_k do not change during the rounding, Ψ~p _p does not decrease. 3. For every k∈+k _+, define S^k:=∑j∈ku¯k,jx^k,j. S_k:= _j _k u_k,j x_k,j. Then ∑j∈ku¯k,jx¯k,j≥(1−δ)S^k≥(1−δ)∑C∈kμ(C)y^(C). _j _k u_k,j x_k,j≥(1-δ) S_k≥(1-δ) _C _kμ(C) y(C). (72) Proof. Suppose first that ConfIP~(^) ConfIP( τ) is feasible, and let (x∘,y∘,z∘)(x ,y ,z ) be an optimal solution of this program. We show that one of the restricted mixed-integer programs retains this solution. For every k∈+k _+, define the support of its small-good assignment by Tk∘:=j∈k:xk,j∘>0.T_k :=\j _k:x_k,j >0\. If |Tk∘|<d|T_k |<d, choose Jk=Tk∘J_k=T_k . The restrictions associated with JkJ_k require xk,jx_k,j to be a positive integer for every j∈Jkj∈ J_k and set xk,j=0x_k,j=0 for every j∈k∖Jkj _k J_k. These restrictions are satisfied by x∘x . Suppose instead that |Tk∘|≥d|T_k |≥ d. Choose JkJ_k to be the set of the d highest-valued members of Tk∘T_k , breaking ties arbitrarily, and define γk:=minj∈Jku¯k,j. _k:= _j∈ J_k u_k,j. Every good type in Tk∘∖JkT_k J_k has rounded value at most γk _k. Therefore, x∘x satisfies xk,j=0x_k,j=0 for every j∈k∖Jkj _k J_k such that u¯k,j>γk u_k,j> _k. Moreover, xk,j∘≥1x_k,j ≥ 1 for every j∈Jkj∈ J_k. It follows that the restricted program associated with the tuple =(Jk)k∈+J=(J_k)_k _+ contains (x∘,y∘,z∘)(x ,y ,z ) as a feasible solution. Thus at least one of the enumerated restricted programs contains an optimal solution of ConfIP~(^) ConfIP( τ). We now prove the rounding assertion for any feasible restricted program. Let (x^,y^,z^)( x, y, z) be the solution specified in the statement of the lemma. Thus, y y, z z, and the variables x^k,j x_k,j declared integral by the restrictions associated with J have been fixed at their optimal integral values. The remaining coordinates of x x form an optimal basic feasible solution of the resulting linear program. Let V be the set of indices (k,j)(k,j) corresponding to these remaining continuous variables. For every (k,j)∈(k,j) , introduce a residual variable fk,jf_k,j by xk,j=⌊x^k,j⌋+fk,j,x_k,j= x_k,j +f_k,j, 0≤fk,j≤1.0≤ f_k,j≤ 1. Equivalently, we intersect the feasible region with ⌊x^k,j⌋≤xk,j≤⌊x^k,j⌋+1 x_k,j ≤ x_k,j≤ x_k,j +1 for every (k,j)∈.(k,j) . These additional bounds contain x x. Consequently, x x remains optimal and remains a basic feasible solution of the restricted linear program. At x x, the value of the residual variable is f^k,j:=x^k,j−⌊x^k,j⌋, f_k,j:= x_k,j- x_k,j , 0≤f^k,j<10≤ f_k,j<1. Define ℐfrac:=(k,j)∈:0<f^k,j<1,I_frac:=\(k,j) :0< f_k,j<1\, E:=|ℐfrac|.E:=|I_frac|. We next bound the number of fractional components of x x. Claim 1. The basic feasible solution x x has at most F=2DF=2D fractional components. Equivalently, E≤2D=F.E≤ 2D=F. Proof. Fix every residual variable satisfying f^k,j=0 f_k,j=0 at zero and consider the resulting system on the variables indexed by ℐfracI_frac. The vector (f^k,j)(k,j)∈ℐfrac( f_k,j)_(k,j) _frac remains a basic feasible solution of this system. None of these variables is fixed by a bound constraint because 0<f^k,j<10< f_k,j<1 for every (k,j)∈ℐfrac.(k,j) _frac. Let J be the number of tight item-capacity constraints containing at least one variable indexed by ℐfracI_frac. Besides these constraints, there are at most D non-item constraints. Since the active constraints must have rank at least E on the variables indexed by ℐfracI_frac, we obtain E≤J+D.E≤ J+D. Every tight item-capacity constraint counted by J contains at least two fractional variables. Indeed, after the fixed integral values and the integral floors have been subtracted, its residual right-hand side is an integer. If the constraint contained exactly one fractional variable, tightness would force that variable to have an integral value, contradicting the definition of ℐfracI_frac. Every variable fk,jf_k,j occurs in exactly one item-capacity constraint, namely the constraint associated with good type j. Counting incidences between the J tight item-capacity constraints and the E fractional variables therefore gives 2J≤E.2J≤ E. Combining the preceding inequalities yields E≤J+D≤E2+D.E≤ J+D≤ E2+D. Hence E≤2D=F,E≤ 2D=F, which proves the claim. ∎ We now define the reduced system used to round the components indexed by ℐfracI_frac. For every (k,j)∈[K]×[q](k,j)∈[K]×[q], define its fixed integral part by xk,jint:=x^k,j,if xk,j was fixed before the residual system was constructed,⌊x^k,j⌋,if (k,j)∈.x_k,j^int:= cases x_k,j,&if $x_k,j$ was fixed before the residual system was constructed,\\ x_k,j ,&if $(k,j)∈ V$. cases The first case includes variables declared integral by the restrictions associated with J and variables fixed to zero. Thus xk,jintx_k,j^int is an integer for every (k,j)(k,j). Moreover, x^k,j=xk,jint+f^k,j x_k,j=x_k,j^int+ f_k,j for every (k,j)∈ℐfrac(k,j) _frac, whereas x^k,j=xk,jint x_k,j=x_k,j^int for every (k,j)∉ℐfrac(k,j) _frac. For every good type j∈[q]j∈[q], define the residual item capacity by Mjres:=mj−∑k=1Kxk,jint.M_j^res:=m_j- _k=1^Kx_k,j^int. For every k∈+k _+, define the residual agent-count requirement by Nkres:=nk−∑C∈ky^(C)−∑j∈khugexk,jint.N_k^res:=n_k- _C _k y(C)- _j _k^hugex_k,j^int. For every k∈0k _0, define Nkres:=nk−z^k−∑j∈k+xk,jint.N_k^res:=n_k- z_k- _j _k^+x_k,j^int. Finally, for every k∈+k _+ and r∈ℛδr _δ, define the residual large-class requirement by Lk,rres:=∑C∈kar(C)y^(C)−∑j∈ℒk,rxk,jint.L_k,r^res:= _C _ka_r(C) y(C)- _j _k,rx_k,j^int. All these residual quantities are integers. Remove the weighted small-value constraints and fix every residual variable outside ℐfracI_frac at zero. The remaining variables are f=(fk,j)(k,j)∈ℐfracf=(f_k,j)_(k,j) _frac. We solve the following linear program. maximize fmaximize ∑(k,j)∈ℐfrac∩ℐsingϕ~p(vk,j)fk,j _(k,j) _frac _sing φ_p(v_k,j)f_k,j (73a) subject to: ∑k:(k,j)∈ℐfracfk,j≤Mjres _k:(k,j) _fracf_k,j≤ M_j^res j∈[q] j∈[q] (73b) ∑j∈khuge(k,j)∈ℐfracfk,j=Nkres _ subarraycj _k^huge\\ (k,j) _frac subarrayf_k,j=N_k^res k∈+ k _+ (73c) ∑j∈k+(k,j)∈ℐfracfk,j=Nkres _ subarraycj _k^+\\ (k,j) _frac subarrayf_k,j=N_k^res k∈0 k _0 (73d) ∑j∈ℒk,r(k,j)∈ℐfracfk,j≥Lk,rres _ subarraycj _k,r\\ (k,j) _frac subarrayf_k,j≥ L_k,r^res k∈+,r∈ℛδ k _+,\ r _δ (73e) 0≤fk,j≤1 0≤ f_k,j≤ 1 (k,j)∈ℐfrac (k,j) _frac (73f) Let redP_red denote the feasible region of (Round-LP). The vector f^:=(f^k,j)(k,j)∈ℐfrac f:=( f_k,j)_(k,j) _frac belongs to redP_red. Indeed, it is obtained from x x by subtracting the fixed integral parts. Under the residual definitions above, constraints (66b), (66c), (66f), and (66d) become, respectively, (73b)–(73e). The only structural constraints omitted from (Round-LP) are the weighted small-value constraints (66e). We next verify that the polytope redP_red is integral. Every variable fk,jf_k,j occurs in its item-capacity constraint and in at most one additional constraint. More precisely, a huge-singleton variable for a positive-threshold type occurs in one agent-count constraint, a positive-singleton variable for a zero-threshold type occurs in one agent-count constraint, and a large-good variable occurs in one large-class constraint. A small-good variable occurs in no additional constraint because the weighted small-value constraints have been removed. After multiplying every agent-count and large-class row by −1-1, each column contains at most one entry equal to 11 and at most one entry equal to −1-1. The resulting matrix is a submatrix of a node-arc incidence matrix and is therefore totally unimodular. Since the right-hand sides and variable bounds in (73b)–(73f) are integral, redP_red is an integral polytope. Since f^∈red f _red and redP_red is a nonempty bounded integral polytope, (Round-LP) has an optimal solution g∈red∩0,1ℐfrac.g _red∩\0,1\^I_frac. By optimality, the value of (73a) at g is at least its value at f f. Define x¯k,j:=xk,jint+gk,j,(k,j)∈ℐfrac,xk,jint,(k,j)∉ℐfrac. x_k,j:= casesx_k,j^int+g_k,j,&(k,j) _frac,\\ x_k,j^int,&(k,j) _frac. cases By the residual definitions, (73b)–(73e) imply that x¯ x satisfies (66b), (66c), (66f), and (66d). Variables constrained by (66g) were fixed at zero and remain zero. We next prove item 2. For every (k,j)∉ℐfrac(k,j) _frac, the construction gives x¯k,j=x^k,j x_k,j= x_k,j. For every (k,j)∈ℐfrac(k,j) _frac, we have x¯k,j−x^k,j=gk,j−f^k,j. x_k,j- x_k,j=g_k,j- f_k,j. Consequently, ∑(k,j)∈ℐsingϕ~p(vk,j)(x¯k,j−x^k,j)=∑(k,j)∈ℐfrac∩ℐsingϕ~p(vk,j)(gk,j−f^k,j). _(k,j) _sing φ_p(v_k,j) ( x_k,j- x_k,j )= _(k,j) _frac _sing φ_p(v_k,j) (g_k,j- f_k,j ). Both g and f f belong to redP_red. By the choice of g, the right-hand side is nonnegative. This proves item 2. It remains to prove the small-good guarantee. Fix k∈+k _+ and recall that S^k=∑j∈ku¯k,jx^k,j. S_k= _j _k u_k,j x_k,j. Suppose first that |Jk|=d|J_k|=d. Every variable xk,jx_k,j with j∈Jkj∈ J_k was declared integral and was therefore fixed before x x was chosen. Moreover, every unguessed small-good variable with rounded value greater than γk=minj∈Jku¯k,j _k= _j∈ J_k u_k,j was fixed to zero. Consequently, every small-good coordinate of type k that belongs to ℐfracI_frac has rounded value at most γk _k. By Claim 1, at most F coordinates can change. Each such coordinate can decrease by less than one. Therefore, ∑j∈ku¯k,jx¯k,j≥S^k−Fγk. _j _k u_k,j x_k,j≥ S_k-F _k. On the other hand, the d protected variables satisfy x^k,j≥1 x_k,j≥ 1 for every j∈Jkj∈ J_k. Hence S^k≥∑j∈Jku¯k,jx^k,j≥dγk. S_k≥ _j∈ J_k u_k,j x_k,j≥ d _k. It follows that Fγk≤FdS^k≤δS^k,F _k≤ Fd S_k≤δ S_k, where the last inequality follows from d=⌈F/δ⌉d= F/δ . Therefore, ∑j∈ku¯k,jx¯k,j≥(1−δ)S^k. _j _k u_k,j x_k,j≥(1-δ) S_k. Suppose now that |Jk|<d|J_k|<d. In this case, JkJ_k is interpreted as the complete support of the small-good assignment. Every variable xk,jx_k,j with j∈Jkj∈ J_k was declared integral, and every variable xk,jx_k,j with j∈k∖Jkj _k J_k was fixed to zero. Therefore, no small-good coordinate of type k belongs to ℐfracI_frac, and ∑j∈ku¯k,jx¯k,j=S^k. _j _k u_k,j x_k,j= S_k. Finally, constraint (66e) implies S^k≥∑C∈kμ(C)y^(C). S_k≥ _C _kμ(C) y(C). Combining this inequality with the preceding two cases gives ∑j∈ku¯k,jx¯k,j≥(1−δ)S^k≥(1−δ)∑C∈kμ(C)y^(C). _j _k u_k,j x_k,j≥(1-δ) S_k≥(1-δ) _C _kμ(C) y(C). This proves item 3 and completes the proof. ∎ Loss due to the rational objective coefficients. We next quantify the loss caused by replacing the exact objective coefficients by their directed rational approximations. Fix a threshold vector τ, and let Z=(x,y,z)Z=(x,y,z) be any feasible solution of ConfIP(^)ConfIP( τ). Let Z∘=(x∘,y∘,z∘)Z =(x ,y ,z ) be an optimal solution of ConfIP~(^) ConfIP( τ). By the first conclusion of Lemma 15, some enumerated tuple ∘J gives a restricted program containing Z∘Z . Let Z^=(x^,y^,z^) Z=( x, y, z) be the optimal basic solution selected from that restricted program, and let Z¯=(x¯,y^,z^) Z=( x, y, z) be the rounded integral vector produced by the lemma. The vector Z¯ Z satisfies the constraints (66b), (66c), (66d), (66f), and (66g), as well as the weakened small-value bound (72); it need not satisfy (66e). For p≠0p≠ 0, define the exact power objective of a configuration solution by Qpconf(Z):=∑C∈v(C)py(C)+∑(k,j)∈ℐsingvk,jpxk,j,Q_p^conf(Z):= _C v(C)^py(C)+ _(k,j) _singv_k,j^px_k,j, where zero configurations, which can occur only when 0<p<10<p<1, contribute zero. For p=0p=0, define Λconf(Z):=∑C∈log(v(C))y(C)+∑(k,j)∈ℐsinglog(vk,j)xk,j. ^conf(Z):= _C (v(C))y(C)+ _(k,j) _sing (v_k,j)x_k,j. These are weighted objectives of the form considered in Lemma 2, with weights y(C)y(C) and xk,jx_k,j. For p≤0p≤ 0, all represented utilities are positive. Write Ψ~p(Z′) _p(Z ) for Ψ~p(x′,y′) _p(x ,y ) when Z′=(x′,y′,z′)Z =(x ,y ,z ). Since the selected restricted program contains Z∘Z , its optimal solution Z Z has rational objective at least that of Z∘Z . Lemma 15 ensures that rounding Z Z to Z¯ Z does not decrease this objective. Together with the optimality of Z∘Z in the rationalized configuration program, this gives Ψ~p(Z¯)≥Ψ~p(Z^)≥Ψ~p(Z∘)≥Ψ~p(Z). _p( Z)≥ _p( Z)≥ _p(Z )≥ _p(Z). Apply Lemma 2 with accuracy δ to the weighted lists represented by Z and Z¯ Z. For 0<p<10<p<1, it gives Qpconf(Z¯)≥11+δQpconf(Z).Q_p^conf( Z)≥ 11+δQ_p^conf(Z). (74) For p<0p<0, it gives Qpconf(Z¯)≤(1+δ)Qpconf(Z).Q_p^conf( Z)≤(1+δ)Q_p^conf(Z). (75) Finally, for p=0p=0, constraints (66c) and (66f) imply that the total weight of represented utilities is n, including for fractional configuration vectors. The logarithmic conclusion of the lemma, together with log(1+δ)≤δ (1+δ)≤δ, therefore gives Λconf(Z¯)≥Λconf(Z)−nδ. ^conf( Z)≥ ^conf(Z)-nδ. (76) 6.8 Reconstructing a compressed allocation For every feasible restricted mixed-integer program associated with an enumerated threshold vector, Lemma 15 produces an integral vector Z¯:=(x¯,y^,z^). Z:=( x, y, z). The vector x¯ x specifies how many goods of each type are reserved for each agent type, but it does not specify their distribution among the individual agents. We now construct such a distribution in compressed form. Lemma 16 (Compressed reconstruction). Let Z¯=(x¯,y^,z^) Z=( x, y, z) be an integral vector satisfying the conclusions of Lemma 15, including (72). Then Z¯ Z can be converted in polynomial time into a feasible compressed allocation xrecx^rec with the following properties. 1. Every agent of type k∈+k _+ represented by a regular configuration C∈kC _k receives utility at least (1−6δ)v(C)=(1−6δ)αkw(C).(1-6δ)v(C)=(1-6δ) _kw(C). 2. Every agent represented by a singleton pair (k,j)∈ℐsing(k,j) _sing receives one type-j good and, before any unused goods are assigned, satisfies uk(xirec)≥vk,j.u_k(x_i^rec)≥ v_k,j. (77) 3. Every agent represented by a zero configuration initially receives no good having positive value to its type and therefore initially has utility zero. Assigning unused goods at the end may only increase this utility. 4. For every good type j∈[q]j∈[q], at most mjm_j copies are assigned, and the number of distinct bundle patterns in xrecx^rec is OK,δ(q)O_K,δ(q). Proof. We first partition the agents of each type according to the integral variables y y, z z, and x¯ x. Fix k∈+k _+. For every C∈kC _k, choose a set Ak,C⊆AkA_k,C A_k of cardinality |Ak,C|=y^(C).|A_k,C|= y(C). For every j∈khugej _k^huge, choose a set Ak,jsing⊆AkA_k,j^sing A_k of cardinality |Ak,jsing|=x¯k,j.|A_k,j^sing|= x_k,j. Constraint (66c) implies that these sets can be chosen to form a partition of AkA_k. Now fix k∈0k _0. Choose a set Ak,0⊆AkA_k,0 A_k of cardinality |Ak,0|=z^k,|A_k,0|= z_k, and, for every j∈k+j _k^+, choose a set Ak,jsing⊆AkA_k,j^sing A_k of cardinality |Ak,jsing|=x¯k,j.|A_k,j^sing|= x_k,j. Constraint (66f) implies that these sets can be chosen to form a partition of AkA_k. For every k∈[K]k∈[K] and j∈[q]j∈[q], reserve x¯k,j x_k,j copies of type j for agents of type k. By (66b), these reservations can be chosen disjointly. All remaining copies are temporarily left unassigned. For every singleton pair (k,j)∈ℐsing(k,j) _sing, assign one reserved type-j good to each agent in Ak,jsingA_k,j^sing. It remains to distribute the goods reserved for agents represented by regular configurations. Assignment of large goods. Fix k∈+k _+ and r∈ℛδr _δ. Define Dk,r:=∑C∈kar(C)y^(C).D_k,r:= _C _ka_r(C) y(C). By constraint (66d), Dk,r≤∑j∈ℒk,rx¯k,j.D_k,r≤ _j _k,r x_k,j. (78) Thus the goods reserved for type k contain sufficiently many goods from the large-value class ℒk,rL_k,r. Fix orders k=(C1,…,Cs)C_k=(C_1,…,C_s) and ℒk,r=(j1,…,jt).L_k,r=(j_1,…,j_t). For every configuration C∈kC _k and every h∈1,…,ar(C)h∈\1,…,a_r(C)\, define a slot label (C,r,h)(C,r,h). Every agent in Ak,CA_k,C must receive one class-r good in each such slot. Algorithm 4, given below, fills these slots in batches. Algorithm 4 Batched assignment of class-r large goods to type-k agents 1: Ordered configurations (C1,…,Cs)(C_1,…,C_s); multiplicities y^(Cν) y(C_ν); demands ar(Cν)a_r(C_ν); ordered good types (j1,…,jt)(j_1,…,j_t); reserved supplies x¯k,jℓ x_k,j_ 2: A list ℬk,rB_k,r of batched assignments filling every class-r slot 3: ℬk,r←∅B_k,r← 4: for ℓ=1,…,t =1,…,t do 5: bℓ←x¯k,jℓb_ ← x_k,j_ ⊳ Remaining reserved supply of type jℓj_ 6: ℓ←1 ← 1 7: for ν=1,…,sν=1,…,s do 8: N←y^(Cν)N← y(C_ν) 9: for h=1,…,ar(Cν)h=1,…,a_r(C_ν) do 10: a←0a← 0 ⊳ Number of occurrences of slot (Cν,r,h)(C_ν,r,h) filled 11: while a<Na<N do 12: while bℓ=0b_ =0 do 13: ℓ←ℓ+1 ← +1 14: λ←minN−a,bℓλ← \N-a,b_ \ 15: Append (Cν,r,h,a+1,λ,jℓ)(C_ν,r,h,a+1,λ,j_ ) to ℬk,rB_k,r ⊳ Assign type jℓj_ to positions a+1,…,a+λa+1,…,a+λ 16: a←a+λa← a+λ 17: bℓ←bℓ−λb_ ← b_ -λ 18: return ℬk,rB_k,r A tuple (C,r,h,a+1,λ,j)(C,r,h,a+1,λ,j) in ℬk,rB_k,r means that the agents in positions a+1,…,a+λa+1,…,a+λ of the block Ak,CA_k,C receive a type-j good in their slot (C,r,h)(C,r,h). Thus a batch is stored using only a constant number of binary-encoded integers and indices; the agents in the batch are not listed individually. Algorithm 4 is well-defined. At every iteration, the total number of unfilled class-r slots is at most the total remaining reserved supply. This holds initially by (78), and each assignment decreases both quantities by λ. Hence, whenever an unfilled slot remains, the inner loop finds an index ℓ≤t ≤ t with bℓ>0b_ >0. The algorithm fills every occurrence of every slot label. Therefore, each agent represented by C receives exactly ar(C)a_r(C) goods from ℒk,rL_k,r. Moreover, it uses at most x¯k,j x_k,j copies of each good type j. Each execution of the innermost loop either exhausts one good type or completes one slot label. Consequently, for fixed k and r, the number of generated batches is at most |ℒk,r|+∑C∈kar(C).|L_k,r|+ _C _ka_r(C). Summing over all k∈+k _+ and r∈ℛδr _δ gives ∑k∈+∑r∈ℛδ(|ℒk,r|+∑C∈kar(C))≤Kq+∑C∈∑r∈ℛδar(C)=OK,δ(q). _k _+ _r _δ (|L_k,r|+ _C _ka_r(C) )≤ Kq+ _C _r _δa_r(C)=O_K,δ(q). The last equality follows because the large-value classes are disjoint for each agent type, ||=OK,δ(1)|C|=O_K,δ(1), and every retained configuration contains at most 4/δ4/δ large goods. Hence the large-good assignment is computed in polynomial time and has a polynomial-size compressed representation. Assignment of small goods. Fix k∈+k _+. For every regular configuration C∈kC _k, define its small-good target by t(C):=(1−δ)μ(C).t(C):=(1-δ)μ(C). The weakened small-good constraint gives ∑j∈ku¯k,jx¯k,j≥∑C∈kt(C)y^(C). _j _k u_k,j x_k,j≥ _C _kt(C) y(C). (79) Fix arbitrary orders of the configurations in kC_k and of the small good types in kS_k. Within each block Ak,CA_k,C, fix a conceptual ordering of its agents; assignment batches always refer to consecutive agents in this order. For every j∈kj _k, let bjb_j denote the residual number of reserved type-j goods. Initially, bj:=x¯k,j.b_j:= x_k,j. These residual supplies are maintained throughout the processing of all configuration blocks of type k. For a positive target t, the boundary type is the first positive-supply type at which the cumulative residual rounded value reaches t. The associated boundary bundle contains all residual copies of the preceding types and as many copies of the boundary type as possible without exceeding t. The invariant proved below shows that this type exists whenever the algorithm requires it. The assignment is performed in compressed form by Algorithm 5. Algorithm 5 Batched assignment of small goods to type-k agents 1: Configuration blocks Ak,CA_k,C and reserved supplies x¯k,j x_k,j for j∈kj _k 2: A compressed partial assignment of the reserved small goods to all agents represented by regular configurations 3: Initialize bj←x¯k,jb_j← x_k,j for every j∈kj _k 4: for each C∈kC _k in the fixed order do 5: Set A′←Ak,CA ← A_k,C and t←(1−δ)μ(C)t←(1-δ)μ(C) 6: if t=0t=0 then 7: Assign an empty small-good bundle to every agent in A′A and set A′←∅A ← 8: while A′≠∅A ≠ do 9: List the small good types having positive residual supply as j1,…,jℓj_1,…,j_ , in the fixed order ⊳ The invariant below implies ℓ≥1 ≥ 1 10: if u¯k,j1>t u_k,j_1>t then 11: Assign an empty small-good bundle to every agent in A′A and set A′←∅A ← 12: else 13: Let jrj_r be the first type for which the total residual value of j1,…,jrj_1,…,j_r is at least t 14: Form a boundary bundle from all residual copies of j1,…,jr−1j_1,…,j_r-1 and as many copies of jrj_r as fit without exceeding t 15: Assign the boundary bundle to one agent in A′A and update the residual supplies and A′A 16: Using the remaining copies of jrj_r, assign the largest feasible pure type-jrj_r bundle to a maximum-size batch of agents in A′A 17: Update the residual supply of jrj_r and A′A 18: return the recorded assignment batches We describe the two assignment steps more precisely. Suppose that jrj_r is the boundary type, and consider the residual supplies immediately before the boundary bundle is formed. Put R:=t−∑h=1r−1u¯k,jhbjhandhr:=⌊Ru¯k,jr⌋.R:=t- _h=1^r-1 u_k,j_hb_j_h h_r:= R u_k,j_r . The boundary bundle is P:=∑h=1r−1bjhjh+hrjr,P:= _h=1^r-1b_j_he_j_h+h_re_j_r, where je_j denotes a bundle containing one type-j good. Assign P to one agent in A′A and remove that agent from A′A . After this assignment, the residual supplies of j1,…,jr−1j_1,…,j_r-1 are zero, and bjrb_j_r is decreased by hrh_r. Next, define qr:=⌊tu¯k,jr⌋.q_r:= t u_k,j_r . If qr>0q_r>0, assign qrq_r copies of type jrj_r to each of λ:=min|A′|,⌊bjrqr⌋λ:= \|A |, b_j_rq_r \ agents in A′A . If λ>0λ>0, record these identical assignments as one batch. Remove their recipients from A′A and decrease bjrb_j_r by λqrλ q_r. If qr=0q_r=0, no copy of type jrj_r fits into an empty bundle. In the next iteration, the remaining agents in the current configuration block therefore receive empty small-good bundles (that is, they get assigned zero copies of every type j∈kj _k, but they may still receive the large goods specified by their regular configurations). Claim 2. For every agent i represented by a regular configuration CiC_i, the rounded normalized value sis_i of the small-good bundle assigned to i satisfies si≤t(Ci)s_i≤ t(C_i). Proof. Indeed, if i receives a boundary bundle, then si=∑h=1r−1u¯k,jhbjh+hru¯k,jr.s_i= _h=1^r-1 u_k,j_hb_j_h+h_r u_k,j_r. Since hr=⌊t(Ci)−∑h=1r−1u¯k,jhbjhu¯k,jr⌋,h_r= t(C_i)- _h=1^r-1 u_k,j_hb_j_h u_k,j_r , we have hru¯k,jr≤t(Ci)−∑h=1r−1u¯k,jhbjh.h_r u_k,j_r≤ t(C_i)- _h=1^r-1 u_k,j_hb_j_h. Consequently, si≤t(Ci)s_i≤ t(C_i). If i belongs to a single-type batch, then it receives qrq_r copies of type jrj_r, where qr=⌊t(Ci)u¯k,jr⌋.q_r= t(C_i) u_k,j_r . Thus si=qru¯k,jr≤t(Ci).s_i=q_r u_k,j_r≤ t(C_i). Finally, an agent receiving an empty small-good bundle has si=0s_i=0, which is at most t(Ci)t(C_i) because t(Ci)≥0t(C_i)≥ 0. Therefore, si≤t(Ci)s_i≤ t(C_i) for every assigned agent i. ∎ We next verify that the boundary type required by the algorithm always exists. Consider any stage of the algorithm for the fixed agent type k. Let kU_k be the set of type-k agents whose small-good bundles have not yet been assigned. For every i∈ki _k, let CiC_i denote the unique configuration C∈kC _k such that i∈Ak,Ci∈ A_k,C. Define Srem:=∑j∈ku¯k,jbjS_rem:= _j _k u_k,jb_j and Trem:=∑i∈kt(Ci).T_rem:= _i _kt(C_i). Thus SremS_rem is the total rounded normalized value of the reserved small goods that have not yet been assigned, whereas TremT_rem is the sum of the small-good targets of all agents whose small-good bundles have not yet been assigned. We maintain the invariant Srem≥Trem.S_rem≥ T_rem. Initially, bj=x¯k,jb_j= x_k,j for every j∈kj _k, and kU_k contains all agents represented by regular configurations of type k. Hence Srem S_rem =∑j∈ku¯k,jx¯k,j≥∑C∈kt(C)y^(C)=∑i∈kt(Ci)=Trem, = _j _k u_k,j x_k,j≥ _C _kt(C) y(C)= _i _kt(C_i)=T_rem, where the inequality follows from (79). Suppose that the algorithm assigns small-good bundles to a set B⊆kB _k of agents. For every i∈Bi∈ B, let sis_i be the rounded normalized value of the bundle assigned to i. By Claim 2, si≤t(Ci)s_i≤ t(C_i) for every i∈Bi∈ B. After this assignment, the updated quantities satisfy Srem′=Srem−∑i∈BsiS_rem =S_rem- _i∈ Bs_i and Trem′=Trem−∑i∈Bt(Ci).T_rem =T_rem- _i∈ Bt(C_i). Consequently, Srem′−Trem′=Srem−Trem+∑i∈B(t(Ci)−si)≥0.S_rem -T_rem =S_rem-T_rem+ _i∈ B (t(C_i)-s_i )≥ 0. Thus the invariant is preserved after every individual assignment and every batched assignment. Suppose that the algorithm is processing an agent with positive target t. Since this agent belongs to kU_k, the invariant gives Srem≥Trem≥t.S_rem≥ T_rem≥ t. Hence the residual small goods have total rounded normalized value at least t>0t>0. In particular, at least one residual small-good type exists. Therefore, unless its first type already has value greater than t, the smallest prefix whose total value reaches t exists, and the boundary type jrj_r is well defined. It remains to prove the lower bound on the value assigned to each agent. Consider first an agent receiving a boundary bundle. By the minimality of r, 0<R≤u¯k,jrbjr.0<R≤ u_k,j_rb_j_r. Moreover, hru¯k,jr≤Rh_r u_k,j_r≤ R and hru¯k,jr>R−u¯k,jr.h_r u_k,j_r>R- u_k,j_r. Therefore, the rounded normalized value sis_i of the boundary bundle satisfies t−u¯k,jr<si≤t.t- u_k,j_r<s_i≤ t. Since jr∈kj_r _k, we have u¯k,jr<1 u_k,j_r<1, and hence t−1<si≤t.t-1<s_i≤ t. An agent in the subsequent single-type batch receives qrq_r copies of type jrj_r. From the definition of qrq_r, qru¯k,jr≤t<(qr+1)u¯k,jr.q_r u_k,j_r≤ t<(q_r+1) u_k,j_r. Consequently, t−u¯k,jr<qru¯k,jr≤t,t- u_k,j_r<q_r u_k,j_r≤ t, so the value assigned to this agent is also greater than t−1t-1. Finally, suppose that an agent receives an empty small-good bundle. Then either t=0t=0 or the first residual small good has value greater than t. In the latter case, t<u¯k,j1<1,t< u_k,j_1<1, and therefore 0>t−10>t-1. Thus every agent i represented by a regular configuration C receives a small-good bundle of rounded normalized value sis_i satisfying t(C)−1<si≤t(C)t(C)-1<s_i≤ t(C). In particular, si≥(1−δ)μ(C)−1.s_i≥(1-δ)μ(C)-1. (80) Finally, we bound the number of batches created by the small-good assignment. Consider one configuration block Ak,CA_k,C and an iteration whose boundary type is jrj_r. The boundary bundle exhausts the residual supplies of every type j1,…,jr−1j_1,…,j_r-1. It creates one assignment batch, consisting of a single agent. After updating the residual supplies, suppose that qr>0q_r>0. The algorithm assigns qrq_r copies of type jrj_r to λ=min|A′|,⌊bjrqr⌋λ= \|A |, b_j_rq_r \ agents and records these identical bundles as one additional batch. If agents remain after this assignment, then λ=⌊bjrqr⌋.λ= b_j_rq_r . Consequently, the updated residual supply bjr′b_j_r satisfies 0≤bjr′<qr.0≤ b_j_r <q_r. If bjr′=0b_j_r =0, type jrj_r is already exhausted. Otherwise, bjr′u¯k,jr<qru¯k,jr≤t(C).b_j_r u_k,j_r<q_r u_k,j_r≤ t(C). Hence, in the next iteration, the residual copies of jrj_r precede the new boundary type and are all included in the next boundary bundle. They are therefore exhausted in that iteration. It follows that, within a fixed configuration block, every iteration either exhausts at least one small good type, terminates the block, or is followed by an iteration that exhausts its boundary type. Moreover, each iteration creates at most one boundary-bundle batch and one single-type batch, and at most one batch of empty small-good bundles is created for the entire block. Therefore, the number of batches created for Ak,CA_k,C is O(|k|+1)O(|S_k|+1). Summing over all regular configuration blocks of type k gives O(|k|(|k|+1))=OK,δ(q),O (|C_k|(|S_k|+1) )=O_K,δ(q), because |k|=OK,δ(1)|C_k|=O_K,δ(1) and |k|≤q|S_k|≤ q. The number of distinct small-good bundle patterns is at most the number of recorded batches and is therefore also OK,δ(q)O_K,δ(q). The algorithm manipulates only residual supplies and batch multiplicities. These quantities are computed by additions, subtractions, comparisons, and integer divisions applied to binary-encoded integers and rationals of polynomial encoding length. In particular, the algorithm does not enumerate individual goods or agents. It therefore constructs the compressed small-good assignment in time polynomial in the binary encoding length of the instance. The preceding procedures define the reconstructed allocation as follows. Within every block Ak,CA_k,C, both procedures use the same fixed ordering of the agents. Each recorded batch is an interval in this ordering. Take the common refinement of the interval partitions induced by all large-good and small-good batches. Its number of intervals is at most one plus the total number of their endpoints and is therefore OK,δ(q)O_K,δ(q), rather than the product of the numbers of batches. On every interval of the refinement, all agents receive the same combined bundle. Together with the singleton and zero-configuration assignments, these combined batches specify an individual allocation, which we denote by xrecx^rec. Conceptually, xi,jrecx^rec_i,j is the number of type-j goods assigned to agent i. The algorithm does not enumerate all these coordinates; instead, it stores the bundle on each nonempty interval together with the interval’s binary-encoded size. Identical bundles belonging to the same agent type can be merged by adding their multiplicities. Utility guarantee. Consider an agent i∈Ak,Ci∈ A_k,C represented by a regular configuration C∈kC _k. Define L(C):=∑r∈ℛδar(C)(1+δ)r.L(C):= _r _δa_r(C)(1+δ)^r. Thus w(C)=L(C)+μ(C).w(C)=L(C)+μ(C). The large goods assigned to i have total rounded normalized value exactly L(C)L(C). By (80), the total rounded normalized value of the goods assigned to i is at least L(C)+(1−δ)μ(C)−1≥(1−δ)w(C)−1.L(C)+(1-δ)μ(C)-1≥(1-δ)w(C)-1. Every retained regular configuration satisfies w(C)≥1/(5δ)w(C)≥ 1/(5δ). Therefore, 1≤5δw(C)1≤ 5δ w(C), and (1−δ)w(C)−1≥(1−6δ)w(C).(1-δ)w(C)-1≥(1-6δ)w(C). By (64), uk,j≥αku¯k,ju_k,j≥ _k u_k,j for every good type j having positive value to type k. Consequently, uk(xirec)≥(1−6δ)αkw(C)=(1−6δ)v(C).u_k(x_i^rec)≥(1-6δ) _kw(C)=(1-6δ)v(C). (81) Now suppose that i∈Ak,jsingi∈ A_k,j^sing. If k∈+k _+, then (k,j)(k,j) is a huge singleton pair, and uk(xirec)=uk,j≥αku¯k,j=vk,j.u_k(x_i^rec)=u_k,j≥ _k u_k,j=v_k,j. If k∈0k _0, the singleton is represented exactly, and uk(xirec)=uk,j=vk,j.u_k(x_i^rec)=u_k,j=v_k,j. Every agent in Ak,0A_k,0 initially receives no good having positive value to type k and therefore initially has utility zero. Compressed representation and completion. The preceding endpoint bound gives OK,δ(q)O_K,δ(q) regular bundle patterns. The singleton assignments contribute at most KqKq additional patterns, and the zero configurations contribute at most K patterns. Every bundle coordinate and pattern multiplicity is obtained using arithmetic on binary-encoded integers and rationals. The partial allocation therefore has a polynomial-size compressed representation and can be constructed in polynomial time. Any goods that were not used, including unreserved goods and unused reserved goods, may now be assigned to one fixed agent. This changes at most one existing bundle pattern and introduces at most one new pattern. Because all utilities are nonnegative, this completion cannot decrease any agent’s utility and preserves all the lower bounds established above. Since the reservations obey (66b) and no reserved copy is used more than once, the resulting allocation is feasible. Omit records of multiplicity zero and merge identical bundles within each agent type. This gives the required compressed allocation and proves the lemma. ∎ Selection of the final candidate. For every enumerated threshold vector not discarded above and every feasible associated restricted mixed-integer program, apply Lemma 15 followed by Lemma 16. Let X be the resulting collection of feasible reconstructed allocations. For the correct threshold vector, the first conclusion of Lemma 15 supplies an enumerated tuple ∘J whose restricted program yields a candidate. Hence ≠∅ X≠ . Every x∈x∈ X is represented by a polynomial-size collection (x)P(x) of records (k,P,λ)(k,P,λ), indicating that λ agents of type k receive the bundle pattern P=(P1,…,Pq)P=(P_1,…,P_q). Its utility to an agent of type k is uk(P)u_k(P). The objectives defined in Section 3 can be evaluated directly from this compressed representation. For p≠0p≠ 0, Qp(x)=∑(k,P,λ)∈(x)λuk(P)p,Q_p(x)= _(k,P,λ) (x)λ u_k(P)^p, and, for p=0p=0, Λ(x)=∑(k,P,λ)∈(x)λloguk(P). (x)= _(k,P,λ) (x)λ u_k(P). The rational coefficients used in the configuration formulations approximate the represented values v(C)v(C) and vk,jv_k,j. After reconstruction, however, an agent’s actual utility uk(P)u_k(P) need not equal its represented value. We therefore compute fresh rational approximations from the actual utilities of the reconstructed bundle patterns. Because (x)P(x) has polynomial size, this computation does not require enumerating the agents. For each x∈x∈ X, apply Lemma 2 with accuracy δ to the utility list with entries (λ,uk(P))(λ,u_k(P)) indexed by (x)P(x). The weights sum to n. Denote the resulting rational score by Q~prec(x) Q_p^rec(x) when 0<p<10<p<1, its negative by Q~prec(x) Q_p^rec(x) when p<0p<0, and the score by Λ~rec(x) ^rec(x) when p=0p=0. The lemma gives, using log(1+δ)≤δ (1+δ)≤δ in the logarithmic case, Qp(x)1+δ Q_p(x)1+δ ≤Q~prec(x)≤Qp(x) ≤ Q_p^rec(x)≤ Q_p(x) if 0<p<1, 0<p<1, Qp(x) Q_p(x) ≤Q~prec(x)≤(1+δ)Qp(x) ≤ Q_p^rec(x)≤(1+δ)Q_p(x) if p<0, p<0, Λ(x)−nδ (x)-nδ ≤Λ~rec(x)≤Λ(x) ≤ ^rec(x)≤ (x) if p=0. p=0. For 0<p<10<p<1, a zero-utility pattern contributes zero exactly. When p≤0p≤ 0, all enumerated vectors with a zero threshold were discarded; the reconstruction therefore gives every agent positive utility. Choose xoutx^out to maximize Q~prec Q_p^rec if 0<p<10<p<1, minimize it if p<0p<0, and maximize Λ~rec ^rec if p=0p=0. The polynomial-time guarantee in Lemma 2 applies directly to these compressed lists. The selection rule maximizes the signed rational score in all three cases. The comparison conclusion of the lemma therefore implies that, for every x∈x∈ X, Qp(xout)≥Qp(x)/(1+δ),0<p<1,Qp(xout)≤(1+δ)Qp(x),p<0,Λ(xout)≥Λ(x)−nδ,p=0. casesQ_p(x^out)≥ Q_p(x)/(1+δ),&0<p<1,\\[5.69054pt] Q_p(x^out)≤(1+δ)Q_p(x),&p<0,\\[5.69054pt] (x^out)≥ (x)-nδ,&p=0. cases (82) These bounds will be used in the approximation analysis. 6.9 Approximation analysis Put β:=1−6δ.β:=1-6δ. Since δ≤1/10δ≤ 1/10, we have 0<β<10<β<1 and 1−4δ≥β.1-4δ≥β. Let x∗x^* be the canonical optimal allocation, and let Z∗Z^* be the integer configuration solution induced by x∗x^* under the correct threshold vector, as constructed in Lemma 14. For every k∈[K]k∈[K] and i∈Aki∈ A_k, let u~i∗ u_i^* denote its represented utility in Z∗Z^*. Equation (67) gives u~i∗≥(1−4δ)uk(xi∗)≥βuk(xi∗) u_i^*≥(1-4δ)u_k(x_i^*)≥β u_k(x_i^*) whenever uk(xi∗)>0u_k(x_i^*)>0. When 0<p<10<p<1 and uk(xi∗)=0u_k(x_i^*)=0, the corresponding represented utility is also zero, so the same inequality holds. Consequently, u~i∗≥βuk(xi∗)k∈[K],i∈Ak. u_i^*≥β u_k(x_i^*) k∈[K],\ i∈ A_k. (83) Apply the coefficient-loss analysis to Z=Z∗Z=Z^*. For the correct threshold vector, let ∘J be the tuple guaranteed by the first conclusion of Lemma 15, and let ZcorrZ^corr be the resulting rounded integral vector Z¯ Z. Let xcorr∈x^corr∈ X be its reconstruction from Lemma 16. For every k∈[K]k∈[K] and i∈Aki∈ A_k, let u~icorr u_i^corr denote its represented utility in ZcorrZ^corr. If i is represented by a regular configuration, equation (81) gives uk(xicorr)≥βu~icorr.u_k(x_i^corr)≥β u_i^corr. If i is represented by a singleton pair (k,j)(k,j), then equation (77) gives uk(xicorr)≥vk,j=u~icorr≥βu~icorr,u_k(x_i^corr)≥ v_k,j= u_i^corr≥β u_i^corr, where the last inequality uses 0<β≤10<β≤ 1. Finally, a zero configuration has represented utility zero, and the completion step can only increase the actual utility of its agent. Therefore, uk(xicorr)≥βu~icorrk∈[K],i∈Ak.u_k(x_i^corr)≥β u_i^corr k∈[K],\ i∈ A_k. (84) The case 0<p<10<p<1. If Qp(x∗)=0Q_p(x^*)=0, then the optimal welfare is zero and the approximation claim is immediate. Hence assume Qp(x∗)>0Q_p(x^*)>0. Raising (83) to the positive power p and summing over the agents gives Qpconf(Z∗)≥βpQp(x∗).Q_p^conf(Z^*)≥β^pQ_p(x^*). Similarly, (84) gives Qp(xcorr)≥βpQpconf(Zcorr).Q_p(x^corr)≥β^pQ_p^conf(Z^corr). Applying, in order, (82), (84), (74), and (83) yields Qp(xout) Q_p(x^out) ≥11+δQp(xcorr)≥βp1+δQpconf(Zcorr)≥βp(1+δ)2Qpconf(Z∗)≥β2p(1+δ)2Qp(x∗). ≥ 11+δQ_p(x^corr)≥ β^p1+δQ_p^conf(Z^corr)≥ β^p(1+δ)^2Q_p^conf(Z^*)≥ β^2p(1+δ)^2Q_p(x^*). Therefore, PSWp(xout)PSWp(x∗)=(Qp(xout)Qp(x∗))1/p≥β2(1+δ)−2/p. PSW_p(x^out)PSW_p(x^*)= ( Q_p(x^out)Q_p(x^*) )^1/p≥β^2(1+δ)^-2/p. For every c>0c>0, Bernoulli’s inequality gives (1+δ)−c≥1−cδ.(1+δ)^-c≥ 1-cδ. Moreover, β2=(1−6δ)2≥1−12δ.β^2=(1-6δ)^2≥ 1-12δ. Since both β2β^2 and (1+δ)−2/p(1+δ)^-2/p belong to [0,1][0,1], it follows that β2(1+δ)−2/p≥1−(12+2p)δ.β^2(1+δ)^-2/p≥ 1- (12+ 2p )δ. Hence PSWp(xout)PSWp(x∗)≥1−(12+2p)δ. PSW_p(x^out)PSW_p(x^*)≥ 1- (12+ 2p )δ. (85) The case p<0p<0. Put a:=|p|a:=|p|, so that p=−ap=-a. The flow test in Subsection 6.3 guarantees the existence of a positive allocation and hence a positive canonical optimum. Since threshold vectors with a zero coordinate are discarded when p≤0p≤ 0, every reconstructed candidate used here is also positive. Because the exponent p=−ap=-a is negative, (83) implies Qpconf(Z∗)≤β−aQp(x∗),Q_p^conf(Z^*)≤β^-aQ_p(x^*), and (84) implies Qp(xcorr)≤β−aQpconf(Zcorr).Q_p(x^corr)≤β^-aQ_p^conf(Z^corr). Applying, in order, (82), (84), (75), and (83), we obtain Qp(xout) Q_p(x^out) ≤(1+δ)Qp(xcorr)≤(1+δ)β−aQpconf(Zcorr)≤(1+δ)2β−aQpconf(Z∗)≤(1+δ)2β−2aQp(x∗). ≤(1+δ)Q_p(x^corr)≤(1+δ)β^-aQ_p^conf(Z^corr)≤(1+δ)^2β^-aQ_p^conf(Z^*)≤(1+δ)^2β^-2aQ_p(x^*). Raising this inequality to the power −1/a-1/a reverses its direction. Therefore, PSWp(xout)PSWp(x∗)≥β2(1+δ)−2/a. PSW_p(x^out)PSW_p(x^*)≥β^2(1+δ)^-2/a. As in the positive case, β2(1+δ)−2/a≥1−(12+2a)δ.β^2(1+δ)^-2/a≥ 1- (12+ 2a )δ. Since a=|p|a=|p|, we conclude that PSWp(xout)PSWp(x∗)≥1−(12+2|p|)δ. PSW_p(x^out)PSW_p(x^*)≥ 1- (12+ 2|p| )δ. (86) The case p=0p=0. The same positivity argument applies when p=0p=0. Taking logarithms in (83) gives Λconf(Z∗)≥Λ(x∗)+nlogβ. ^conf(Z^*)≥ (x^*)+n β. Similarly, (84) gives Λ(xcorr)≥Λconf(Zcorr)+nlogβ. (x^corr)≥ ^conf(Z^corr)+n β. Applying, in order, (82), (84), (76), and (83) gives Λ(xout) (x^out) ≥Λ(xcorr)−nδ≥Λconf(Zcorr)+nlogβ−nδ≥Λconf(Z∗)+nlogβ−2nδ≥Λ(x∗)+2nlogβ−2nδ. ≥ (x^corr)-nδ≥ ^conf(Z^corr)+n β-nδ≥ ^conf(Z^*)+n β-2nδ≥ (x^*)+2n β-2nδ. Exponentiating after dividing by n yields PSW0(xout)PSW0(x∗)≥β2e−2δ. PSW_0(x^out)PSW_0(x^*)≥β^2e^-2δ. Since e−2δ≥1−2δe^-2δ≥ 1-2δ and β2≥1−12δβ^2≥ 1-12δ, we obtain PSW0(xout)PSW0(x∗)≥β2e−2δ≥1−14δ. PSW_0(x^out)PSW_0(x^*)≥β^2e^-2δ≥ 1-14δ. (87) By the choice of δ in (62), equations (85), (86), and (87) then imply PSWp(xout)≥(1−ε)PSWp(x∗)=(1−ε)OPTp.PSW_p(x^out)≥(1- )PSW_p(x^*)=(1- )OPT_p. 6.10 Running time Let L denote the binary encoding length of the instance. For fixed K, p, and ε , the parameters δ, BδB_δ, D, F, and d are constants. If Uk>0U_k>0, equation (63) gives |k|=2+⌈log1+δ(nkUkukmin)⌉=Oδ(L).|T_k|=2+ _1+δ ( n_kU_ku_k ) =O_δ(L). If Uk=0U_k=0, then |k|=1|T_k|=1. Hence the number of threshold vectors is ∏k=1K|k|=Oδ(LK), _k=1^K|T_k|=O_δ(L^K), which is polynomial because K is fixed. For each threshold vector, the rounded values in (64) can be computed in polynomial time using exact comparisons with integer powers of the fixed rational base 1+δ1+δ. The exponents have magnitude Oδ(L)O_δ(L), and the resulting rational numbers have polynomial encoding length. By (65), the number |||C| of retained regular configurations is OK,δ(1)O_K,δ(1). For every threshold vector, Section 6.7 enumerates at most (q+1)Kd(q+1)^Kd support tuples. Each resulting restricted mixed-integer program has O(Kq+||+K)O(Kq+|C|+K) variables and constraints, polynomially bounded coefficient lengths, and at most ||+K+Kd=OK,δ(1)|C|+K+Kd=O_K,δ(1) integer variables. It can therefore be solved in polynomial time by fixed-dimensional mixed-integer programming. The basic feasible solution and the integral solution of the reduced system (73) can also be computed in polynomial time; by Claim 1, that system contains at most F=2D=OK,δ(1)F=2D=O_K,δ(1) fractional coordinates. The reconstruction algorithms in Section 6.8 produce OK,δ(q)O_K,δ(q) assignment batches. Thus, the reconstructed allocation can be computed in polynomial time. By Lemma 2, the same holds for its directed rational objective approximation, without expanding the binary-encoded agent or good multiplicities. Consequently, the total running time is (∏k=1K|k|)(q+1)KdpolyK,p,δ(L)=polyK,p,ε(L), ( _k=1^K|T_k| )(q+1)^Kdpoly_K,p,δ(L)=poly_K,p, (L), where q≤Lq≤ L. Since the enumeration contains a correct threshold vector and the tuple ∘J guaranteed by Lemma 15, the approximation analysis applies to the best candidate returned by the algorithm. ∎ 7 Conclusion The exact algorithms and hardness results establish sharp item-type boundaries for computing an optimal allocation: hardness starts at two item types for every fixed finite rational p<1p<1, p≠0p≠ 0, and at three for egalitarian welfare. Nash welfare is NP-hard with three item types; its complexity with two item types remains unsettled by our results, already for explicitly listed agents and binary item multiplicities. The hardness results also apply to rational-threshold decision, whereas the polynomial exact-allocation results need not: even the one-item-type case p=−1/2p=-1/2 contains Sqrt-Sum as a threshold problem. For every fixed number of item types, we give an FPTAS for every fixed p∈ℚ∪−∞p ∪\-∞\. For a fixed number of agent types and an unrestricted number of item types, we give a PTAS for every fixed finite rational p<1p<1. Both algorithms run in the compact input model and return compressed allocations. The one-agent-type strong-hardness reduction and its quantitative gap rule out an FPTAS in the latter setting unless = P= NP. The exact algorithms for one item type and for egalitarian welfare with two item types follow classical resource-allocation and scheduling methods. Our proofs make their compact-input implementation and output explicit. Appendix C similarly records the known exact egalitarian algorithm when both numbers of types are fixed, as a consequence of Goemans and Rothvoß Goemans and Rothvoß (2020). Our work leaves several important problems open for future research. The first is to complete the picture of approximability by settling the complexity of maximizing Nash welfare with two item types. A second natural question is whether the problem can be solved exactly in polynomial time when both the number of agent types and the number of item types are constant; so far, this has been answered affirmatively only for egalitarian welfare. Finally, a promising direction is to study the computation of fair allocations under standard fairness criteria, including envy-freeness (EF) and its relaxations EF1 and EFX, proportionality (PROP) and PROP1, and the maximin share (MMS). In particular, it would be interesting to determine whether computing an allocation that satisfies such a criterion is tractable or NPNP-hard when the number of item types is small, especially when fairness is combined with efficiency requirements such as Pareto optimality or maximum Nash welfare. For instance, Aziz et al. (2023) gives an algorithm for computing an EF allocation with two item types whose running time is polynomial in n and m; an algorithm that is polynomial in n and logm m, and hence in the input size when item multiplicities are encoded in binary, would be highly desirable. Use of generative AI. The authors used ChatGPT 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] 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. [2] N. Anari, T. Mai, S. O. Gharan, and V. V. Vazirani (2018) Nash social welfare for indivisible items under separable, piecewise-linear concave utilities. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA’18, p. 2274–2290. Cited by: §1. [3] H. Aziz, J. Lindsay, A. Ritossa, and M. Suzuki (2023) Fair allocation of two types of chores. In Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems, AAMAS’ 23, p. 143–151. Cited by: §1, §7. [4] S. Barman, S. Krishnamurthy, and R. Vaish (2018) Finding fair and efficient allocations. In Proceedings of the 19th ACM Conference on Economics and Computation, p. 557–574. Cited by: §2. [5] S. Barman, U. Bhaskar, A. Krishna, and R. G. Sundaram (2020) Tight approximation algorithms for p-mean welfare under subadditive valuations. In 28th Annual European Symposium on Algorithms (ESA 2020), F. Grandoni, G. Herman, and P. Sanders (Eds.), Leibniz International Proceedings in Informatics (LIPIcs), Vol. 173, p. 11:1–11:17. Note: Full version available as arXiv:2005.07370 External Links: Link Cited by: §1, §2. [6] S. Barman, A. Khan, and A. Maiti (2022) Universal and tight online algorithms for generalized-mean welfare. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 36, p. 4793–4800. Cited by: §1. [7] 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, p. 7–13. Cited by: §1. [8] S. Barman and R. G. Sundaram (2020) Uniform welfare guarantees under identical subadditive valuations. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI-20, C. Bessiere (Ed.), p. 46–52. Cited by: §1, §2. [9] S. Barman and P. Verma (2022) Truthful and fair mechanisms for matroid-rank valuations. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 36, p. 4801–4808. Cited by: §1. [10] M. Bateni, M. Charikar, and V. Guruswami (2009) MaxMin allocation via degree lower-bounded arborescences. In Proceedings of the 41st ACM Symposium on Theory of Computing, p. 543–552. Cited by: §2. [11] I. Bezáková and V. Dani (2005) Allocating indivisible goods. ACM SIGecom Exchanges 5 (3), p. 11–18. Cited by: §2. [12] 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 25th International Joint Conference on Artificial Intelligence, p. 102–108. Cited by: §1. [13] S. Bouveret, Y. Chevaleyre, and N. Maudet (2016) Fair allocation of indivisible goods. In Handbook of Computational Social Choice, F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. Procaccia (Eds.), p. 284–310. Cited by: §1. [14] I. Caragiannis, D. Kurokawa, H. Moulin, A. Procaccia, N. Shah, and J. Wang (2016) The unreasonable fairness of maximum Nash welfare. In Proceedings of the 17th ACM Conference on Economics and Computation, p. 305–322. Cited by: §1. [15] K. F. Celine, W. Suksompong, and S. M. Yuen (2026) On the fairness of additive welfarist rules. ACM Trans. Econ. Comput. 14 (2). Cited by: §1. [16] D. Chakrabarty, J. Chuzhoy, and S. Khanna (2009) On allocating goods to maximize fairness. In 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2009), p. 107–116. Cited by: §2. [17] B. R. Chaudhury, J. Garg, and K. Mehlhorn (2024) EFX exists for three agents. J. ACM 71 (1). Cited by: §1. [18] B. R. Chaudhury, J. Garg, and R. Mehta (2021) Fair and efficient allocations under subadditive valuations. In Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Thirty-Third Conference on Innovative Applications of Artificial Intelligence, IAAI 2021, The Eleventh Symposium on Educational Advances in Artificial Intelligence, EAAI 2021, Virtual Event, February 2-9, 2021, p. 5269–5276. Cited by: §1, §2. [19] R. Cole and V. Gkatzelis (2015) Approximating the Nash social welfare with indivisible items. In Proceedings of the 47th ACM Symposium on Theory of Computing, p. 371–380. Cited by: §2. [20] V. Davidiuk, Y. Dementiev, A. Ignatiev, and D. Sagunov (2026) EFX and PO allocation exists for two types of goods. In Proceedings of the 40th AAAI Conference on Artificial Intelligence (AAAI 2026), Vol. 40, p. 16795–16802. External Links: Document Cited by: §1. [21] O. Eckart, A. Psomas, and P. Verma (2024) On the fairness of normalized p-means for allocating goods and chores. In Proceedings of the 25th ACM Conference on Economics and Computation, EC ’24, p. 1267. Cited by: §1. [22] Z. Galil and N. Megiddo (1979) A fast selection algorithm and the problem of optimum distribution of effort. Journal of the ACM 26 (1), p. 58–64. Cited by: Table 1, §1, §2, §5.6. [23] J. Garg, M. Hoefer, and K. Mehlhorn (2024) Satiation in Fisher markets and approximation of Nash social welfare. Mathematics of Operations Research 49 (2), p. 1109–1139. Cited by: §2. [24] J. Garg, E. Husić, A. Murhekar, and L. Végh (2022) Tractable fragments of the maximum Nash welfare problem. In Web and Internet Economics (WINE 2022), Lecture Notes in Computer Science, Vol. 13754, p. 239–256. Cited by: §1, §1, §2. [25] J. Garg, A. Murhekar, and J. Qin (2024) Weighted EF1 and PO allocations with few types of agents or chores. In Proceedings of the 33rd International Joint Conference on Artificial Intelligence (IJCAI 2024), p. 2799–2806. External Links: Document Cited by: §1. [26] M. X. Goemans and T. Rothvoß (2020) Polynomiality for bin packing with a constant number of item types. Journal of the ACM 67 (6). External Links: Document Cited by: Appendix C, §2, §5.5, §7, Theorem 10. [27] M. E. Hartmann (1989) Cutting planes and the complexity of the integer hull. Ph.D. Thesis, Cornell University, Department of Operations Research and Industrial Engineering, Ithaca, NY. Cited by: §5.7. [28] Z. Huang, C. S. Lee, X. Shu, and Z. Wang (2025) The long arm of nashian allocation in online p-mean welfare maximization. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025), K. Censor-Hillel, F. Grandoni, J. Ouaknine, and G. Puppis (Eds.), Leibniz International Proceedings in Informatics (LIPIcs), Vol. 334, p. 98:1–98:18. Cited by: §1. [29] V. P. Hv, P. Ghosal, P. Nimbhorkar, and N. Varma (2025) EFX exists for three types of agents. In Proceedings of the 26th ACM Conference on Economics and Computation, EC ’25, p. 101–128. Cited by: §1. [30] K. Jansen and M. Maack (2019) An EPTAS for scheduling on unrelated machines of few different types. Algorithmica 81 (10), p. 4134–4164. Cited by: §1, §2. [31] M. Koutecký and J. Zink (2020) Complexity of scheduling few types of jobs on related and unrelated machines. In Proceedings of the 31st International Symposium on Algorithms and Computation, LIPIcs, Vol. 181, p. 18:1–18:17. Cited by: §2. [32] A. Krishna, P. G. John, A. Barik, and V. Y. F. Tan (2025) P-mean regret for stochastic bandits. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 39, p. 17966–17973. Cited by: §1. [33] 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. [34] H. Lenstra Jr. (1983) Integer programming with a fixed number of variables. Mathematics of Operations Research 8 (4), p. 538–548. Cited by: §6.7. [35] J. Ma, Y. Chen, G. Chen, M. Gong, G. Lin, and A. Zhang (2025) Maximizing social welfare among EF1 allocations at the presence of two types of agents. In Proceedings of the 36th International Symposium on Algorithms and Computation (ISAAC 2025), LIPIcs, Vol. 359, p. 49:1–49:19. External Links: Document Cited by: §1. [36] R. Mahara (2023) Existence of EFX for two additive valuations. Discret. Appl. Math. 340, p. 115–122. Cited by: §1. [37] S. T. McCormick, S. R. Smallwood, and F. C. R. Spieksma (2001) A polynomial algorithm for multiprocessor scheduling with two job lengths. Mathematics of Operations Research 26 (1), p. 31–49. External Links: Document Cited by: Table 1, Table 1, §1, §2, §5.7, §5.7. [38] T. T. Nguyen, K. Elbassioni, and J. Rothe (2024) Complexity and approximation schemes for social welfare maximization in the high-multiplicity setting. In ECAI 2024 - 27th European Conference on Artificial Intelligence, 19-24 October 2024, Santiago de Compostela, Spain, U. Endriss, F. S. Melo, K. Bach, A. J. B. Diz, J. M. Alonso-Moral, S. Barro, and F. Heintz (Eds.), Vol. 392, p. 3324–3331. Cited by: §1, §2, Remark 2. [39] T. T. Nguyen and J. Rothe (2014) Minimizing envy and maximizing average Nash social welfare in the allocation of indivisible goods. Discrete Applied Mathematics 179, p. 54–68. Cited by: §1, §2. [40] T. T. Nguyen and J. Rothe (2023) Fair and efficient allocation with few agent types, few item types, or small value levels. Artificial Intelligence 314, p. 103820. External Links: Document Cited by: §1, §2. [41] K. S. Pardeshi, I. Shapira, A. D. Procaccia, and A. Singh (2024) Learning social welfare functions. In Proceedings of the 38th International Conference on Neural Information Processing Systems, NIPS ’24. Cited by: §1. [42] P. Shahkar and J. Garg (2025) Improved mms approximations for few agent types. In Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI ’25. Cited by: §1. [43] V. Viswanathan and Y. Zick (2025) A general framework for fair allocation under matroid rank valuations. ACM Trans. Econ. Comput. 13 (3). Cited by: §1, §2. [44] G. Woeginger (1997) A polynomial-time approximation scheme for maximizing the minimum machine completion time. Operations Research Letters 20 (4), p. 149–154. Cited by: §1, §2. Appendix A Proofs of the Technical Lemmas in Sections 3 and 4 A.1 Proof of Lemma 1 Proof. The case p>0p>0 and v=0v=0 is immediate, so suppose that v>0v>0, and let B be its encoding length. First let p=a/d≠0p=a/d≠ 0, where the nonzero integer a and the positive integer d are fixed. We have 2−B≤v≤2B2^-B≤ v≤ 2^B. Thus, for a sufficiently large integer constant c depending only on p, the dyadic numbers l0:=2−cBl_0:=2^-cB and u0:=2cBu_0:=2^cB satisfy 0<l0≤vp≤u00<l_0≤ v^p≤ u_0. Set ξ:=η/(1+η)ξ:=η/(1+η). Starting with the interval [l0,u0][l_0,u_0], repeatedly bisect the current interval and retain a half containing vpv^p, until the interval has width at most ξl0ξ l_0. Each comparison is exact: for a positive rational midpoint z, compare zdz^d with the rational number vav^a, also when a<0a<0. After Op(B+log(1/η))O_p(B+ (1/η)) iterations we obtain [l,u][l,u] with l≤vp≤u,l≤ v^p≤ u, u−l≤ξl0≤ξvp.u-l≤ξ l_0≤ξ v^p. For p>0p>0, output l. Then l≥(1−ξ)vp=vp/(1+η)l≥(1-ξ)v^p=v^p/(1+η). For p<0p<0, output −u-u. Then u≤(1+ξ)vp≤(1+η)vpu≤(1+ξ)v^p≤(1+η)v^p. The endpoints and the intermediate powers have encoding length polynomial in B+log(1/η)B+ (1/η). The exact stopping test also uses the encoding of η, so the complete computation has the claimed bit complexity. For p=0p=0, write v=2eyv=2^ey with e∈ℤe , 1≤y<21≤ y<2, and |e|=O(B)|e|=O(B). For a rational t∈[1,2]t∈[1,2], put z=(t−1)/(t+1)∈[0,1/3]z=(t-1)/(t+1)∈[0,1/3]. The identity logt=2∑ℓ=0∞z2ℓ+12ℓ+1 t=2 _ =0^∞ z^2 +12 +1 shows that the rational partial sum PN(t):=2∑ℓ=0N−1z2ℓ+12ℓ+1P_N(t):=2 _ =0^N-1 z^2 +12 +1 satisfies, for every integer N≥1N≥ 1, 0≤logt−PN(t)=2∑ℓ=N∞z2ℓ+12ℓ+1≤22N+1∑ℓ=N∞z2ℓ+1=2z2N+1(2N+1)(1−z2)≤34(2N+1) 9−N≤9−N. 0≤ t-P_N(t)=2 _ =N^∞ z^2 +12 +1≤ 22N+1 _ =N^∞z^2 +1= 2z^2N+1(2N+1)(1-z^2)≤ 34(2N+1)\,9^-N≤ 9^-N. Put h:=9−Nh:=9^-N. The preceding bounds give logy∈[PN(y),PN(y)+h],log2∈[PN(2),PN(2)+h]. y∈[P_N(y),P_N(y)+h], 2∈[P_N(2),P_N(2)+h]. Since logv=logy+elog2 v= y+e 2, it follows that logv∈[LN,UN], v∈[L_N,U_N], where LN:=PN(y)+ePN(2)+mine,0h,UN:=PN(y)+ePN(2)+(1+maxe,0)h.L_N:=P_N(y)+eP_N(2)+ \e,0\h, U_N:=P_N(y)+eP_N(2)+(1+ \e,0\)h. Indeed, if e≥0e≥ 0, multiplication by e preserves the endpoint order; if e<0e<0, it reverses that order. Both endpoints are rational, and UN−LN=(1+|e|)9−N.U_N-L_N=(1+|e|)9^-N. Choose N so that this width is at most η/2η/2, and output the lower endpoint LNL_N. Since log(1+η)=∫0ηdt1+t≥η1+η≥η2, (1+η)= _0^η dt1+t≥ η1+η≥ η2, this output satisfies (2). Only O(1+log(B+1)+log(1/η))O(1+ (B+1)+ (1/η)) terms are required. Their exact rational evaluation and the test for choosing N take time polynomial in the encoding lengths of v and η. The output has polynomial encoding length as well. ∎ A.2 Proof of Lemma 4 Proof. For y=0y=0, the function in (8) is F(x,0)=a1−pxpp−x.F(x,0)= a^1-px^pp-x. For real x>0x>0, its derivative is (a/x)1−p−1(a/x)^1-p-1. Consequently, its unique maximum on [0,∞)[0,∞) is attained at x=ax=a, with value γaγ a. Now let y≥1y≥ 1. The partial derivative with respect to x is α(αx+βy)p−1−1≤αβp−1−1=(aH)γ−1<0,α(α x+β y)^p-1-1≤αβ^p-1-1= ( aH )^γ-1<0, where H>aH>a. Thus, for fixed y≥1y≥ 1, the maximum is attained uniquely at x=0x=0. At x=0x=0 the function is Hyp/p−CyHy^p/p-Cy, whose derivative on [1,∞)[1,∞) is at most H−C=(1−p)(a−C)<0.H-C=(1-p)(a-C)<0. Its maximum on that interval is attained uniquely at y=1y=1 and equals H/p−C=γaH/p-C=γ a. This proves the inequality and its equality cases. It remains to bound the loss at the other integer pairs. Suppose that y=0y=0 and x>0x>0, with x≠ax≠ a. Every real number t between x and a satisfies 1≤t≤Z1≤ t≤ Z. Hence −∂2F∂x2(t,0)=(1−p)a1−ptp−2=(1−p)a1−ptpt2≥1−pZ2,- ∂^2F∂ x^2(t,0)=(1-p)a^1-pt^p-2=(1-p) a^1-pt^pt^2≥ 1-pZ^2, because a1−p≥1a^1-p≥ 1, tp≥1t^p≥ 1, and t2≤Z2t^2≤ Z^2. Since ∂F∂x(a,0)=0 ∂ F∂ x(a,0)=0, Taylor’s theorem gives F(a,0)−F(x,0)≥1−p2Z2(x−a)2≥1−p2Z2,F(a,0)-F(x,0)≥ 1-p2Z^2(x-a)^2≥ 1-p2Z^2, (88) where the last inequality uses that x and a are distinct integers. At (0,0)(0,0), the loss is γa≥1−pγ a≥ 1-p. Suppose that y≥1y≥ 1 and x≥1x≥ 1. For fixed y, the preceding partial derivative bound gives ∂F∂x(t,y)≤(aH)γ−1for every t∈[0,x]. ∂ F∂ x(t,y)≤ ( aH )^γ-1 every t∈[0,x]. Since F(0,y)≤γaF(0,y)≤γ a, integrating this inequality yields γa−F(x,y) γ a-F(x,y) ≥F(0,y)−F(x,y)=−∫0x∂F∂x(t,y)dt≥x[1−(aH)γ]≥1−(aH)γ, ≥ F(0,y)-F(x,y)=- _0^x ∂ F∂ x(t,y)\,dt≥ x [1- ( aH )^γ ]≥ 1- ( aH )^γ, where the last step uses x≥1x≥ 1 and H>aH>a. For every z∈(0,1)z∈(0,1) and γ>0γ>0, 1−zγ≥min1,γ(1−z).1-z^γ≥ \1,γ\(1-z). Indeed, if γ≥1γ≥ 1, then zγ≤z^γ≤ z; if 0<γ<10<γ<1, concavity gives zγ≤1+γ(z−1)z^γ≤ 1+γ(z-1). Applying this inequality with z=a/Hz=a/H, we obtain γa−F(x,y) γ a-F(x,y) ≥min1,γ(1−aH)=min1,γp(C−a)H=minp,1−pC−aH≥minp,1−pZ. ≥ \1,γ\ (1- aH )= \1,γ\ p(C-a)H= \p,1-p\ C-aH≥ \p,1-p\Z. (89) Here we used H−a=p(C−a)H-a=p(C-a), γ=(1−p)/pγ=(1-p)/p, C−a≥1C-a≥ 1, and H≤ZH≤ Z. Finally, suppose that x=0x=0 and y≥2y≥ 2. Since F(0,t)=Htpp−Ct,F(0,t)= Ht^pp-Ct, for every t≥1t≥ 1 we have ∂F∂t(0,t)=Htp−1−C≤H−C=−(1−p)(C−a), ∂ F∂ t(0,t)=Ht^p-1-C≤ H-C=-(1-p)(C-a), where we used p<1p<1 and hence tp−1≤1t^p-1≤ 1. Since F(0,1)=γaF(0,1)=γ a, integration gives γa−F(0,y) γ a-F(0,y) =F(0,1)−F(0,y)=−∫1y∂F∂y(0,t)dt≥(y−1)(1−p)(C−a)≥1−p, =F(0,1)-F(0,y)=- _1^y ∂ F∂ y(0,t)\,dt≥(y-1)(1-p)(C-a)≥ 1-p, (90) because y−1≥1y-1≥ 1 and C−a≥1C-a≥ 1. Equations (88), (89) and (90) imply (9). ∎ A.3 Proof of Lemma 5 Proof. The assumptions imply 0<H<a0<H<a. For y=0y=0 and real x>0x>0, G(x,0)=ar+1x−r+x,∂G∂x(x,0)=1−(ax)r+1.G(x,0)= a^r+1x^-rr+x, ∂ G∂ x(x,0)=1- ( ax )^r+1. This function has its unique minimum at x=ax=a, with value γaγ a. For y≥1y≥ 1 and x≥0x≥ 0, the partial derivative with respect to x satisfies 1−α(αx+βy)−r−1≥1−αβ−r−1=1−(Ha)γ>0.1-α(α x+β y)^-r-1≥ 1-αβ^-r-1=1- ( Ha )^γ>0. Thus the minimum for fixed y≥1y≥ 1 is attained uniquely at x=0x=0. At x=0x=0 the function is Hy−r/r+CyHy^-r/r+Cy, whose derivative on [1,∞)[1,∞) is at least C−H=(r+1)(C−a)>0.C-H=(r+1)(C-a)>0. Its minimum is therefore attained uniquely at y=1y=1, with value H/r+C=γaH/r+C=γ a. For the quantitative bound, first suppose that y=0y=0 and x≠ax≠ a. On the interval between the positive integers x and a, ∂2G∂t2(t,0)=(r+1)ar+1t−r−2≥Z−⌈r⌉−2. ∂^2G∂ t^2(t,0)=(r+1)a^r+1t^-r-2≥ Z^- r -2. Taylor’s theorem gives an excess of at least 1/(2Z⌈r⌉+2)1/(2Z r +2). If y≥1y≥ 1 and x≥1x≥ 1, increasing x from zero causes an excess of at least 1−(Ha)γ≥1−Ha=r(C−a)a≥rZ,1- ( Ha )^γ≥ 1- Ha= r(C-a)a≥ rZ, because γ>1γ>1. If x=0x=0 and y≥2y≥ 2, increasing y from one causes an excess of at least (r+1)(C−a)≥1(r+1)(C-a)≥ 1. This proves (11). ∎ A.4 Proof of Lemma 6 Proof. Put R:=R0+R12,R:= R_0+R_12, Δ:=R1−R0, :=R_1-R_0, and B:=1+⌈R1⌉.B:=1+ R_1 . We will compute a rational approximation to the positive root α:=R1/sα:=R^1/s. Since B≥1B≥ 1 and Bs≥B>RB^s≥ B>R, we have 0<α<B0<α<B. The root α is used only in the analysis; the algorithm does not need to evaluate it. Start with the rational interval [ℓ,u]=[0,B][ ,u]=[0,B], which contains α. At each step, compute its midpoint m:=ℓ+u2m:= +u2 and compare msm^s with R. If ms<Rm^s<R, replace ℓ by m; if ms>Rm^s>R, replace u by m. If ms=Rm^s=R, return z=mz=m, which already satisfies the required inequalities. Because t↦tst t^s is strictly increasing on [0,∞)[0,∞), each update retains α and halves the interval’s width. All comparisons are exact rational comparisons. Specifically, if m=a/bm=a/b and R=c/dR=c/d, with positive denominators, then comparing msm^s with R is equivalent to comparing the integers dasda^s and cbscb^s. Continue until u−ℓ≤η:=Δ2sBs−1,u- ≤η:= 2sB^s-1, and return the rational midpoint z=(ℓ+u)/2z=( +u)/2. Since α∈[ℓ,u]α∈[ ,u], we have |z−α|≤u−ℓ2≤Δ4sBs−1.|z-α|≤ u- 2≤ 4sB^s-1. The derivative of tst^s on [0,B][0,B] is at most sBs−1sB^s-1. The mean value theorem therefore gives |zs−R|=|zs−αs|≤sBs−1|z−α|≤Δ4.|z^s-R|=|z^s-α^s|≤ sB^s-1|z-α|≤ 4. Since R is the midpoint of [R0,R1][R_0,R_1], it follows that R0<R−Δ4≤zs≤R+Δ4<R1.R_0<R- 4≤ z^s≤ R+ 4<R_1. Finally, let L be the total binary encoding length of R0R_0 and R1R_1. The integer B has O(L)O(L) bits, and the positive rational number Δ satisfies Δ≥2−O(L) ≥ 2^-O(L). Thus the number of bisection steps is at most ⌈log2(Bη)⌉=⌈log2(2sBsΔ)⌉=Os(L). _2 ( Bη ) = _2 ( 2sB^s ) =O_s(L). Every endpoint and midpoint is a dyadic rational with Os(L)O_s(L) bits. Since s is fixed, the integer powers and comparisons at each step take polynomial time. This proves both the running-time and output-length bounds. ∎ Appendix B An Illustrative Example for the proof of Lemma 8 Let N=27N=27 and s=3s=3. We first construct the partition independently of the histogram. At each nonterminal level, choose aℓ∈2,3a_ ∈\2,3\ with the same parity as NℓN_ , and set Nℓ+1=(Nℓ−aℓ)/2N_ +1=(N_ -a_ )/2. This gives Level ℓNℓaℓParts created02731,1,111222,22534,4,43118 array[]c|c|c|lLevel &N_ &a_ &Parts created\\ 0&27&3&1,1,1\\ 1&12&2&2,2\\ 2&5&3&4,4,4\\ 3&1&1&8 array The construction terminates at level 33, since N3=1<sN_3=1<s. Thus the fixed partition is 27=1+1+1+2+2+4+4+4+8.27=1+1+1+2+2+4+4+4+8. Now consider the histogram h=(13,8,6)h=(13,8,6), with categories labeled A,B,CA,B,C. We assign categories to the parts as follows. At level ℓ , each unit of the current histogram represents 2ℓ2 units of the original histogram. 1. At level 00, the current histogram is (13,8,6)(13,8,6) and a0=3a_0=3. Only the first entry is odd. Remove one unit from category A, leaving (12,8,6)(12,8,6). To remove exactly three units, remove a further pair from category B, leaving (12,6,6)(12,6,6). Assign the three size-11 parts to A,B,BA,B,B, respectively. Halving the remaining histogram gives (12,6,6)/2=(6,3,3).(12,6,6)/2=(6,3,3). 2. At level 11, the current histogram is (6,3,3)(6,3,3) and a1=2a_1=2. Remove one unit from each of the odd entries, corresponding to categories B and C. Assign the two size-22 parts to these categories. Halving the remaining histogram gives (6,2,2)/2=(3,1,1).(6,2,2)/2=(3,1,1). 3. At level 22, the current histogram is (3,1,1)(3,1,1) and a2=3a_2=3. All three entries are odd, so remove one unit from each category. Assign the three size-44 parts to A,B,CA,B,C, respectively. Halving the remaining histogram gives (2,0,0)/2=(1,0,0).(2,0,0)/2=(1,0,0). 4. At level 33, the current histogram is (1,0,0)(1,0,0). This is the terminal level, so assign the single size-88 part to category A. The parts assigned to each category recover its original multiplicity: A A :1+4+8=13, :1+4+8=13, B B :1+1+2+4=8, :1+1+2+4=8, C C :2+4=6. :2+4=6. The part sizes depend only on N and s, whereas their category labels depend on the histogram. The proof shows that the same fixed partition can represent every histogram on at most three categories with total multiplicity 2727. Appendix C Exact Egalitarian Welfare with Few Agent and Item Types For completeness, we give the proof of Proposition 1. The exact polynomial-time algorithm is a direct corollary of Theorem 12 of Goemans and Rothvoß [26]; the role of the following construction is to express the allocation constraints and a prescribed minimum utility in the form required by their theorem. Throughout this appendix, both the number K of agent types and the number q of item types are fixed, and both agent and item multiplicities are encoded in binary. For a set X⊆ℤdX ^d, its integer cone is int.cone(X):=∑x∈Xλx:λx∈ℤ≥0,|x∈X:λx>0|<∞.int.cone(X):= \ _x∈ X _xx: _x _≥ 0, |\x∈ X: _x>0\ |<∞ \. The empty sum is permitted. For a rational polyhedron P, let enc(P)enc(P) denote the binary encoding length of an inequality description of P. We use the following bounded-polytope form of the integer-cone theorem. Theorem 10 (Goemans–Rothvoß, Theorem 12 [26]). Fix positive integers d and h. Given bounded rational polytopes P1,…,Ph⊆ℝdP_1,…,P_h ^d and a rational polyhedron Q⊆ℝdQ ^d, one can decide whether int.cone(⋃r=1h(Pr∩ℤd))∩Q≠∅int.cone ( _r=1^h(P_r ^d) )∩ Q≠ in time (∑r=1henc(Pr))2O(d+h)enc(Q)O(1). ( _r=1^henc(P_r) )^2^O(d+h)enc(Q)^O(1). In the affirmative case, the algorithm returns integer points x∈Pr∩ℤdx∈ P_r ^d and nonnegative integral multiplicities λr,x _r,x such that ∑r=1h∑x∈Pr∩ℤdλr,xx∈Q. _r=1^h _x∈ P_r ^d _r,xx∈ Q. The returned multiplicities have polynomial binary encoding length, and the number of pairs (r,x)(r,x) with λr,x>0 _r,x>0 is at most 22(d+h)+12^2(d+h)+1. Proof of Proposition 1. We use the notation and compressed representation from Section 3. In particular, n≥1n≥ 1. Delete agent types of multiplicity zero, so every retained nkn_k is positive. If m=0m=0, every agent receives the empty bundle and the optimum egalitarian welfare is zero. Listing the empty bundle with multiplicity nkn_k for each agent type k gives the required compressed allocation. Henceforth, assume m>0m>0 and delete item types of multiplicity zero; thus q≥1q≥ 1 and mj≥1m_j≥ 1 for every j∈[q]j∈[q]. Integral utilities and the search interval. Write uk,j=ak,j/dk,ju_k,j=a_k,j/d_k,j, where ak,j∈ℤ≥0a_k,j _≥ 0 and dk,j∈ℤ≥1d_k,j _≥ 1, and define D:=∏k=1K∏j=1qdk,j,u^k,j:=Duk,j,u^k(c):=∑j=1qu^k,jcj.D:= _k=1^K _j=1^qd_k,j, u_k,j:=Du_k,j, u_k(c):= _j=1^q u_k,jc_j. (91) All scaled item utilities are nonnegative integers. The binary encoding length of D is at most one plus the sum of the binary encoding lengths of the input denominators, so this scaling takes polynomial time and produces numbers of polynomial encoding length. Scaling every utility by the same positive factor D multiplies the minimum utility of every allocation by D and preserves its optimality. Put U:=max1,maxk∈[K],j∈[q]u^k,j,V:=max1,max∑j=1qk∈[K]mju^k,j.U:= \1, _k∈[K],\,j∈[q] u_k,j \, V:= \1, _k∈[K] _j=1^qm_j u_k,j \. (92) Every utility in the scaled instance is an integer between zero and V. Moreover, V≤qmmaxUV≤ qm_ U, so log(V+1) (V+1) is polynomially bounded by the binary encoding length of the original instance. The optimum scaled egalitarian welfare is therefore an integer in 0,…,V\0,…,V\. Feasibility of a minimum-utility threshold. Let eke_k be the kkth unit vector of ℤKZ^K. For an integer T∈0,…,VT∈\0,…,V\ and each agent type k∈[K]k∈[K], define the tagged configuration polytope Pk(T):=(c,y)∈ℝq+K:y=ek,0≤cj≤mj(j∈[q]),u^k(c)≥T.P_k(T):= \(c,y) ^q+K:y=e_k, 0≤ c_j≤ m_j\ (j∈[q]), u_k(c)≥ T \. (93) This is a bounded rational polytope, possibly empty. Its integer points are precisely the configurations giving scaled utility at least T to one agent of type k, with the last K coordinates recording that agent’s type. The configuration bounds allow an empty bundle when T=0T=0 and do not exclude any bundle in a feasible allocation. Define the singleton target polyhedron Qalloc:=(,)⊆ℝq+K.Q^alloc:=\( m, n)\ ^q+K. (94) There is an allocation with scaled egalitarian welfare at least T if and only if int.cone(⋃k=1K(Pk(T)∩ℤq+K))∩Qalloc≠∅.int.cone ( _k=1^K(P_k(T) ^q+K) )∩ Q^alloc≠ . (95) To prove the forward implication, let x be such an allocation. For each agent i∈Aki∈ A_k, the vector (xi,ek)(x_i,e_k) belongs to Pk(T)∩ℤq+KP_k(T) ^q+K. Summing these integer points over all agents gives (,)( m, n): the first q coordinates express the item-allocation equalities, and the remaining K coordinates count the agents of each type. Grouping repeated points gives the required integer-cone representation. Conversely, suppose (95) holds, and let λk,c∈ℤ≥0 _k,c _≥ 0 be the multiplicity of the tagged point (c,ek)(c,e_k) in a corresponding decomposition. Comparing the last K coordinates with the target gives ∑cλk,c=nk _c _k,c=n_k for k∈[K]k∈[K], and comparing the first q coordinates gives ∑k=1K∑cλk,ccj=mj(j∈[q]). _k=1^K _c _k,cc_j=m_j (j∈[q]). Thus, for every k, assigning configuration c to λk,c _k,c agents of type k assigns a bundle to every agent and uses exactly the available multiplicity of every item type. Every used configuration satisfies u^k(c)≥T u_k(c)≥ T, so the resulting allocation has scaled egalitarian welfare at least T. The type–configuration pairs and their multiplicities already constitute its compressed representation. Apply Theorem 10 with dimension d=q+Kd=q+K, with h=Kh=K polytopes, and with Q=QallocQ=Q^alloc. Since K and q are fixed, this decides (95) in polynomial time and, when feasible, returns a corresponding compressed allocation. Exact optimization and reconstruction. Threshold zero is feasible, since all utilities are nonnegative and all items can be assigned to an arbitrary agent. Threshold feasibility is monotone: if an allocation attains a threshold T, it attains every smaller nonnegative threshold. Binary search on 0,…,V\0,…,V\ therefore finds the largest feasible threshold T∗T^* using O(log(V+1))O( (V+1)) integer-cone feasibility tests. Invoke the same algorithm at T∗T^* to obtain a decomposition, omit zero multiplicities, and merge repeated type–configuration pairs. The resulting compressed allocation attains the exact optimum of the scaled instance, because every attainable minimum utility is an integer. Its welfare in the original instance is exactly T∗/DT^*/D. This argument also covers zero utilities. In particular, if an agent type values all available items at zero, every positive threshold is infeasible and the algorithm returns an optimal allocation of welfare zero. If all item utilities are zero, the convention in (92) gives V=1V=1 and the same search returns T∗=0T^*=0. Item types that are worthless to every agent may be retained in the polytopes; the target still ensures that all their copies are allocated. Bit complexity and compressed output. Let L denote the binary encoding length of the original instance. For each tested T, the coefficients in (93) have polynomial encoding length in L, as do the coordinates of the singleton target in (94). Equalities can be written as pairs of inequalities. Consequently, ∑k=1Kenc(Pk(T))=poly(L),enc(Qalloc)=poly(L). _k=1^Kenc(P_k(T))=poly(L), (Q^alloc)=poly(L). The exponent in Theorem 10 depends only on K and q, and the number of feasibility tests is polynomial in L. The overall running time is therefore polyK,q(L)poly_K,q(L). The returned decomposition has at most 22(q+2K)+12^2(q+2K)+1 nonzero type–configuration pairs. Every configuration coordinate lies between zero and the corresponding mjm_j, and the type-count equalities imply λk,c≤nk≤n _k,c≤ n_k≤ n for every pair. Thus every configuration and multiplicity has polynomial binary encoding length. The algorithm outputs these pairs directly, without expanding either the binary-encoded agent population or the item multisets. This proves the claimed exact polynomial-time algorithm and the polynomial size of its compressed output. ∎