Maximizing $p$-Mean Social Welfare in the High-Multiplicity Setting: Few Agent Types and Few Item Types

1 Introduction

• With one agent type and unrestricted item types, maximization is strongly NP-hard for every fixed finite rational p<1 and p=−∞, ruling out an FPTAS unless P=NP.The reduction has a quantitative gap.Source: §1 · p. 3
• For fixed item types, an FPTAS covers every fixed p∈Q∪{−∞}; for fixed agent types, a PTAS covers every fixed finite rational p<1.Both results use the compact model; the FPTAS runs polynomially in compact input length and 1/ε and returns a compressed allocation.Source: §1 · p. 3
• The paper gives compact-model exact algorithms for every fixed p with one item type and for egalitarian welfare with two item types.The latter result allows an arbitrary number of agent types and binary multiplicities.Source: §1 · p. 4
• Exact allocation and rational-threshold decision are distinct complexity questions; polynomial-time construction does not automatically yield threshold comparison.The table covers exact allocation, while its hardness entries also apply to rational-threshold decision.Source: §1 · p. 4
• Exact-allocation hardness starts at two item types for fixed finite rational p<1, p≠0, and at three for Nash and egalitarian welfare.The two-type Nash case remains unsettled by these results.Source: §1 · pp. 3–4

2 Related Work

• For MNSW, guarantees progressed from 1/m to a constant factor and then welfare 1/1.45≈0.68966 [4].The 1/1.45 figure is the welfare guarantee corresponding to an approximation loss of 1.45.Source: §2 · p. 4
• For p-mean welfare, Barman et al. [5] showed exact-optimization hardness for fixed p∈(0,1), while giving an Ω(1/n) guarantee for all p≤1; Chaudhury et al. [18] paired a comparable guarantee with approximate EFX.The hardness factor becomes one because their reduction sets m=n.Source: §2 · p. 4
• In the high-multiplicity setting, Nguyen, Elbassioni, and Rothe gave a PTAS for NSW with fixed agent types and hardness for NSW and ESW with seven item types; this paper lowers both hardness bounds to three.Their work also gave a PTAS for ESW with two item types.Source: §2 · p. 5
• The paper extends prior few-type results to compact inputs: its fixed-agent-type PTAS extends the identical-valuation setting of Garg et al. [24], and its exact algorithms build on classical resource-allocation and two-job-type methods.The two-item-type egalitarian result includes a direct integer-hull proof and compressed reconstruction.Source: §2 · p. 5

3 Allocation Setting and Notation

• Item types have multiplicities, agents may be grouped into types with shared valuations, and both item and agent multiplicities are encoded in binary.A compressed allocation records each distinct bundle vector and the number of agents receiving it; total agent and item counts may be exponential in input length.Source: §3 · pp. 5–6
• Utilities are additive and nonnegative, and an allocation assigns exactly the available multiplicity of every item type.A partial allocation uses no more than each type's multiplicity and can be completed without decreasing welfare.Source: §3 · p. 5
• The welfare parameter p gives the generalized mean: p=1 corresponds to utilitarian welfare, p=0 to Nash welfare, and p=−∞ to egalitarian welfare.For p≤0, welfare is defined as zero if any agent has zero utility.Source: §3 · p. 5
• For finite p, a transformed utility function converts the welfare objective into an equivalent maximization objective on assignments where its terms are defined.The transformation uses t^p for p>0, log t for p=0, and −t^p for p<0; for p≤0 it is used only with positive utilities.Source: §3 · p. 6
• Directed rational approximations replace transformed utilities with rational coefficients, with weighted sums and comparisons computable in polynomial time without expanding binary-encoded integer weights.The approximation lemmas bound the resulting error, and the encoding length remains polynomial in the listed entries and accuracy parameter.Source: §3 · pp. 6–7

4 Hardness Results

• Hardness holds with two item types for nonzero rational p < 1, and with three types for Nash and egalitarian welfare, under both exact allocation and threshold decision.The results allow explicitly listed agents, positive integer values, multiplicities, and thresholds, all encoded in binary.Source: §4 · p. 8

4.1 Two item types and nonzero finite orders

• For every fixed rational p < 1 with p ≠ 0, exact allocation and threshold decision are NP-hard with two item types, even with positive integer values and thresholds.The Subset Sum reduction makes agents choose between two canonical bundle patterns; a quantitative gap preserves the distinction after rational approximation, and scaling yields integer data.Source: §4.1 · pp. 9–11

4.2 Three item types and Nash welfare

• Nash-welfare threshold decision and exact allocation are NP-hard with three item types, even when multiplicities, utilities, and thresholds are positive integers.The reduction uses two ordinary item families to determine agent choices and a third rewarded type to enforce a sum from Balanced-Equal-Cardinality-Partition.Source: §4.2 · p. 11
• In the Nash reduction, allocations with any nonunit agent load have log-product strictly below the ideal target by a positive gap.The construction also restricts unit-load allocations to two bundle patterns using coprimality of the item-family parameters.Source: §4.2 · p. 12
• A three-item-type Nash reduction preserves a strict yes/no welfare gap, making exact optimization reveal a balanced partition; rational coefficients and a threshold can be scaled to positive integers.The rational threshold separates partition allocations from all others, and the construction has polynomial encoding length.Source: §4.2 · pp. 13–14

4.3 Three item types and egalitarian welfare

• Egalitarian threshold decision and exact optimization are NP-hard with three item types, even with positive integer data, rank-at-most-two utilities, and a common strict item ranking.A common item price forces each agent to one of two threshold-feasible bundles; feasible allocations correspond to balanced partitions.Source: §4.3 · pp. 14–15

4.4 One agent type and an unrestricted number of item types

• For every fixed rational p < 1 or p = −∞, threshold decision and exact optimization are strongly NP-hard with one agent type and positive integer utilities.The reduction from 3-Partition makes the welfare threshold attainable exactly when every agent receives utility B.Source: §4.4 · pp. 15–16
• No FPTAS exists unless P = NP for those p-values with one agent type and unrestricted item types.An inverse-polynomial welfare gap lets an approximation distinguish yes-instances; the egalitarian case uses a 1/(2B) accuracy parameter.Source: §4.4 · pp. 16–17

5 An FPTAS for p-Mean Social Welfare with a Fixed Number of Item Types

• For fixed q and p ∈ Q ∪ {−∞}, the algorithm returns a compressed allocation with welfare at least (1−ε)OPTp in time polynomial in compact input length and 1/ε.The polynomial degree depends only on q and p, not on the number or multiplicities of agent types.Source: §5 · p. 17

5.1 Algorithmic overview

• Blocks of identical agents let the algorithm round aggregate resource use and repair any excess by balanced deletions without expanding blocks.The repair preserves a multiplicative fraction of each repaired coordinate and maintains positive utility when p ≤ 0.Source: §5.1 · p. 18

5.2 Sparse allocations and universal blocks

• Each agent type has an optimum using at most 2q distinct bundles, and O(s(1+log N)) dyadic blocks can represent any histogram of N agents over at most s bundles.The block partition is computable in time polynomial in s and the binary encoding length of N.Source: §5.2 · pp. 18–19

5.3 Configurations and objective coefficients

• Geometric-grid rounding preserves feasibility and loses at most a factor 1+η per agent; universal blocks represent the rounded bundle histograms, while a maximum-flow test checks positive-utility feasibility for p ≤ 0.The flow test has K+q+2 vertices and at most Kq+K+q arcs.Source: §5.3 · p. 20

5.4 Anchor guesses and the compressed dynamic program

• The algorithm anchors blocks for large individual coordinates and bounds residual configurations; its dynamic program uses FREE when remaining capacity covers every assignment to the remaining suffix.For each coordinate, it guesses a null anchor or an anchored block and configuration; at most (1+HS)^q guesses are considered.Source: §5.4 · pp. 21–22
• For every retained guess, the compressed dynamic program maximizes over feasible residual assignments, with at most O_q((1 + H^2/η)^q) reachable states per layer.Exact resource coordinates track remaining capacity, while free coordinates preserve a suffix feasibility certificate and allow all admissible future choices.Source: §5.4 · p. 23

5.5 Repair, approximation guarantee, and running time

• With a fixed number of item types, the algorithm is an FPTAS for every fixed p ∈ Q ∪ {−∞}, polynomial in compact input length and 1/ε, returning a compressed allocation.It repairs rounded capacity violations by removing excess items evenly from anchor blocks, then completes the allocation; the resulting welfare is at least (1 − ε)OPTp.Source: §5.5 · pp. 24–26
• For fixed numbers of agent and item types, egalitarian welfare has an exact polynomial-time algorithm in the compact binary-encoded input, returning a compressed allocation.This is recorded as a consequence of Goemans–Rothvoß.Source: §5.5 · p. 26

5.6 Exact optimal allocations with one item type

• With one item type and unrestricted agent types, an optimal allocation for every fixed p ∈ Q ∪ {−∞} is computable in compact-input polynomial time using at most two bundle sizes per agent type.The algorithm selects the largest marginal gains from implicitly represented decreasing sequences, without expanding binary multiplicities.Source: §5.6 · p. 27
• For one item type, exact optimal allocations can be constructed in polynomial time in the compact input, including balanced bundle sizes for Nash welfare and threshold search for egalitarian welfare.Nash-optimal counts differ by at most one; egalitarian optimization scales utilities to integers and binary-searches the largest feasible minimum utility.Source: §5.6 · p. 28
• At p = −1/2, rational-threshold decision with one item type is at least as hard as Sqrt-Sum, despite the immediate construction of an optimal allocation.The allocation algorithm avoids evaluating the final welfare threshold, which can involve a sum of an unbounded number of terms.Source: §5.6 · pp. 28–29

5.7 Exact egalitarian welfare with two item types

• With at most two item types, exact egalitarian-welfare maximization runs in polynomial time for arbitrary agent types and binary multiplicities, returning an optimal allocation with at most K + 2 type–bundle pairs.The algorithm tests welfare thresholds using aggregate lower boundaries and binary search, and reconstructs a compressed allocation without expanding multiplicities.Source: §5.7 · pp. 29–31

6.1 Statement

• For fixed K, p, and ε, the high-multiplicity problem admits a polynomial-time (1 − ε)-approximation, with running time polynomial in q and the binary input length.The theorem applies to additive nonnegative utilities and returns an allocation whose p-mean welfare is at least (1 − ε)OPT_p.Source: §6.1 · p. 31

6.2 Algorithmic overview

• The algorithm guesses thresholds, encodes residual agents with a constant collection of configurations, solves an aggregate allocation problem, and reconstructs a compressed allocation.Support guessing leaves only a constant number of integer variables, and a totally unimodular residual program rounds the remaining aggregate variables.Source: §6.2 · p. 31

6.3 Transformed objectives and positivity

• The algorithm uses an increasing, strictly concave transformed objective and, for p ≤ 0, first tests whether an allocation giving every agent positive utility exists.If the positive-utility flow test fails, the optimum is zero and the algorithm returns any compressed allocation.Source: §6.3 · p. 32

6.4 The residual structural lemma

• An optimal allocation partitions each type into one-good singleton agents and residual agents governed by their average-utility threshold τ_k.Singletons receive a positive-value good worth more than τ_k; residual agents receive only goods worth at most τ_k, and when τ_k > 0 their utilities lie between τ_k/2 and 2τ_k. If τ_k = 0, residual agents have zero utility.Source: §6.4 · p. 32

6.5 Guessing and rounding the residual thresholds

• Geometric threshold guesses and normalized rounded values yield finitely many regular configurations; under a correct guess, any huge good assigned to a type-k agent is that singleton’s unique positive-value good.The threshold vector can be enumerated in polynomial time for fixed K, and the number of retained regular configurations depends only on K and δ.Source: §6.5 · pp. 34–35
• For fixed K and rational δ in (0, 1/10], thresholds can be guessed so each positive residual threshold τ_k is rounded to b_τk with τ_k ≤ b_τk < (1 + δ)τ_k, while zero thresholds remain zero.For positive guessed thresholds, canonical-optimum bundles are represented by retained regular configurations, huge singletons, or retained configurations containing exactly one large good, according to the agent category and good size.Source: §6.5 · p. 35
• When b_τk = τ_k = 0 and 0 < p < 1, agents in R_k have zero utility, while agents in H_k receive exactly one positive-value good.These agents are represented by zero configurations and exact positive singletons, respectively.Source: §6.5 · p. 36
• The number of retained regular configurations across all agent types is bounded by a function of K and δ alone.Source: §6.5 · p. 36

6.6 The configuration formulation

• The exact configuration program tracks reserved goods, represented agents, and represented utilities, with constraints enforcing supply, agent counts, required resources, and removal of utility-free reservations.Some goods may remain unreserved for assignment during reconstruction.Source: §6.6 · pp. 36–37
• For a correct threshold vector, the canonical optimum induces a feasible solution of ConfIP(bτ).Lemma 14 also establishes a represented-utility bound, but its value is not present in the supplied passage.Source: §6.6 · p. 37

6.7 Solving and rounding the configuration formulation

• The rationalized configuration program preserves ConfIP(bτ)’s integral feasible solutions while replacing its objective coefficients with polynomial-length rational approximations.The signed coefficients allow the formulations to remain maximization problems.Source: §6.7 · p. 38
• For fixed K and δ, enumerating small-good supports yields polynomially many restricted programs, each with O_K,δ(1) integer variables, solvable in polynomial time by fixed-dimensional mixed-integer programming.The number of programs is q^O_K,δ(1).Source: §6.7 · pp. 38–39
• At least one restricted program retains an optimal solution of the rationalized configuration program, and the rounding assertion guarantees that rounding need not decrease its rational objective.The optimal-support guarantee applies when the rationalized program is feasible.Source: §6.7 · p. 39
• A basic feasible solution has at most F = 2D fractional components, bounded by counting tight item-capacity constraints and non-item constraints.Each tight item-capacity constraint containing fractional variables must contain at least two of them.Source: §6.7 · p. 40
• In the reduced rounding LP, each residual variable appears in its item-capacity constraint and at most one additional constraint; small-good variables have no additional constraint once weighted constraints are removed.The rounding LP removes the weighted small-value constraints.Source: §6.7 · p. 41
• A sign-adjusted constraint matrix is a submatrix of a node-arc incidence matrix, making Pred totally unimodular and integral.Integral right-hand sides and variable bounds complete the argument that Pred is an integral polytope.Source: §6.7 · p. 41
• An optimal solution of (Round-LP) can be chosen with binary values on Ifrac and objective value at least that of bf.This follows because bf lies in the nonempty, bounded integral polytope Pred.Source: §6.7 · p. 41
• For each agent type, the rounded small-good utility is at least (1 − δ)bSk; when the protected set is the complete support, it is unchanged.When |Jk| = d, at most F coordinates change, each decreasing by less than one; the other case fixes every supported coordinate as integral.Source: §6.7 · p. 42
• The rounded vector satisfies the listed feasibility constraints, while the small-value bound (66e) may not be preserved.The construction and residual definitions establish constraints (66b), (66c), (66d), (66f), and (66g), along with the weakened small-value bound (72).Source: §6.7 · pp. 41–42
• For 0 < p < 1, rounding preserves the rationalized objective, and Lemma 2 bounds the loss from approximating the exact objective coefficients.The analysis treats the represented utilities as weighted lists and applies Lemma 2 with accuracy δ.Source: §6.7 · p. 42
• For p < 0, Lemma 2 likewise bounds the objective loss from rational coefficient approximation after rounding.The objective comparison uses the weighted utility lists represented by the rounded and exact solutions.Source: §6.7 · p. 42
• For p = 0, represented utilities have total weight n, and the logarithmic bound uses log(1 + δ) ≤ δ.Constraints (66c) and (66f) ensure the total weight remains n, including for fractional configuration vectors.Source: §6.7 · p. 42

Reconstruction and completion

• Singleton agents receive one reserved good, and zero-configuration agents initially receive no good valued positively by their type.Unused goods can be assigned to one fixed agent: nonnegative utilities preserve the guarantees, and the completed allocation remains feasible.Source: §6.8 · pp. 43, 47

Assignment of large goods

• Batched large-good assignments fill every slot, giving each regular-configuration agent exactly a_r(C) goods from each class r while respecting reserved supplies.The number of generated batches is polynomial, so the large-good assignment has a polynomial-size compressed representation.Source: §6.8 · pp. 43–44

Assignment of small goods

• For each regular configuration C, the small-good bundle has rounded normalized value t(C) − 1 < s_i ≤ t(C).Here t(C) = (1 − δ)µ(C); the boundary-bundle and single-type assignments both stay within one unit below the target.Source: §6.8 · p. 46
• The small-good procedure creates O_{K,δ}(q) batches and bundle patterns and runs in time polynomial in the instance’s binary encoding length.It manipulates residual supplies and batch multiplicities rather than enumerating individual goods or agents.Source: §6.8 · p. 46

Compressed representation

• The reconstructed allocation has O_{K,δ}(q) regular bundle patterns and a polynomial-size compressed representation.Large- and small-good batch intervals are refined together, avoiding a product-sized number of patterns; identical bundles can be merged.Source: §6.8 · pp. 43, 46, 47

Utility guarantee

• Each regular-configuration agent receives utility at least (1 − 6δ)α_k w(C) from its assigned goods.The large goods supply the configuration’s large-good value; the small-good assignment supplies at least the target value minus one rounded unit.Source: §6.8 · pp. 43, 46, 47

6.8 Reconstructing a compressed allocation

• Fresh rational approximations use the reconstructed patterns’ actual utilities, with polynomial-size compressed lists avoiding enumeration of agents.For each x, Lemma 2 is applied to entries (λ, u_k(P)) indexed by P(x), whose weights sum to n.Source: §6.8 · p. 47
• For 0 < p < 1, the reconstructed score satisfies 1 + δ ≤ eQrec_p(x) ≤ Qp(x).Source: §6.8 · p. 47
• The selection rule maximizes eQrec_p for 0 < p < 1, minimizes it for p < 0, and maximizes eΛrec for p = 0.For p ≤ 0, zero-threshold vectors are discarded so every reconstructed agent has positive utility; the lemma’s comparison conclusion applies to every x.Source: §6.8 · pp. 47–48

• The proof compares the optimum with an induced integer configuration and then analyzes coefficient loss and reconstruction.For the negative-parameter case, the passage gives the intermediate bound Q_p(Z*) ≤ (1 + δ)^(2)β^(-2a)Q_p(x*), where p = −a.Source: §6.9 · pp. 48–49
• For 0 < p < 1, the analysis raises per-agent utility bounds to p and sums them to compare configuration welfare.For p < 0, it assumes positive candidates and reverses the inequality when raising a bound to a negative power.Source: §6.9 · pp. 48–49
• For p = 0, logarithms convert utility comparisons into bounds on the welfare objective.The analysis uses β = 1 − 6δ as a loss factor, with δ ≤ 1/10.Source: §6.9 · pp. 48–49

• For fixed K, p, and ε, the threshold sets and retained regular configurations have polynomially bounded sizes.The passage bounds the total threshold-set size by Oδ(LK) and the retained configurations by O_K,δ(1).Source: §6.10 · p. 49
• Each support tuple yields a restricted mixed-integer program with a constant number of integer variables, solvable in polynomial time.The algorithm enumerates at most (q + 1)^Kd support tuples.Source: §6.10 · p. 49
• Reconstruction produces polynomially many assignment batches without expanding binary-encoded agent or good multiplicities.The reconstruction algorithms produce O_K,δ(q) batches.Source: §6.10 · p. 49
• The total running time is (q + 1)^Kd poly_K,p,δ(L) = poly_K,p,ε(L), and the algorithm returns a candidate to which the approximation analysis applies.The enumeration includes a correct threshold vector and the tuple guaranteed by Lemma 15.Source: §6.10 · p. 49

7 Conclusion

• Hardness begins at two item types for fixed finite rational p < 1, p ≠ 0, and at three for Nash and egalitarian welfare.The hardness results also apply to rational-threshold decision, while polynomial exact-allocation results need not; the one-item-type case p = −1/2 contains Sqrt-Sum as a threshold problem.Source: §7 · p. 50
• For a fixed number of item types, the paper gives an FPTAS; for a fixed number of agent types, it gives a PTAS when item types are unrestricted.Both algorithms operate in the compact input model and return compressed allocations; a quantitative gap rules out an FPTAS in the latter setting unless P = NP.Source: §7 · p. 50
• The paper gives explicit compact-model proofs of classical exact algorithms for one item type and for egalitarian welfare with two item types.The algorithms follow classical resource-allocation and scheduling methods.Source: §7 · p. 50
• The exact complexity of Nash welfare with two item types remains open, as does exact polynomial-time solvability when both type counts are fixed beyond the known egalitarian case.The paper also identifies compact-input algorithms for fair allocations, including EF, EF1, EFX, PROP, PROP1, or MMS, as future research questions.Source: §7 · p. 50

A.1 Proof of Lemma 1

• For fixed nonzero rational p, bisection encloses v^p and returns a rational endpoint within the requested relative error.The comparisons are exact, including when p is negative.Source: §A.1 · p. 53
• Both procedures use polynomial time and produce outputs with polynomial encoding length in the input and accuracy parameters.For the logarithm approximation, only O(1 + log(B + 1) + log(1/η)) terms are needed.Source: §A.1 · pp. 53–54
• For p = 0, the proof writes v = 2^e y and bounds log v using truncated series for log y and log 2.The interval endpoints account for whether multiplication by e preserves or reverses endpoint order.Source: §A.1 · pp. 53–54

A.2 Proof of Lemma 4

• For positive x, the function has its unique maximum at x = a, with value γa.This follows from the derivative sign change stated in the proof.Source: §A.2 · p. 54
• When y ≥ 1, the maximum is attained uniquely at (x, y) = (0, 1), with value γa.For fixed y, the maximum occurs at x = 0, and the function then decreases over y ≥ 1.Source: §A.2 · p. 54
• Integer pairs outside the maximizing cases have a positive loss, with separate bounds for y = 0, x ≥ 1 and for y ≥ 1, x ≥ 1.The proof also bounds the loss at (0, 0) and when x = 0, y ≥ 2.Source: §A.2 · p. 54
• For x = 0 and y ≥ 2, the derivative with respect to t is bounded above by a negative quantity, yielding a loss from the value at y = 1.The proof concludes that these cases, together with the other bounds, imply inequality (9).Source: §A.2 · p. 54

A.3 Proof of Lemma 5

• For y = 0, the function has a unique minimum at x = a, with value γa.Source: §A.3 · p. 55
• For y ≥ 1, the minimum is attained uniquely at (x, y) = (0, 1), with value γa.For fixed y, the minimum occurs at x = 0, and the function increases over y ≥ 1.Source: §A.3 · p. 55
• Nonmaximizing integer pairs incur positive excess, with separate bounds for y = 0, y ≥ 1 and x ≥ 1, and x = 0, y ≥ 2.The proof uses Taylor’s theorem for the first case and derivative-based bounds for the latter cases.Source: §A.3 · p. 55

A.4 Proof of Lemma 6

• The algorithm bisects an interval containing α and compares each midpoint’s s-th power with R using exact rational comparisons.The root is used only in the analysis; the algorithm does not need to evaluate it.Source: §A.4 · p. 55
• Stopping when the interval width is at most Δ/(2sB^(s−1)) bounds the error |z^s − R| by Δ/4.The mean value theorem transfers the midpoint’s distance from α into a bound on the difference of their s-th powers.Source: §A.4 · p. 55
• The resulting z lies strictly between R0 and R1, and the bisection uses polynomial time with polynomial output length.The proof bounds the number of steps using the binary encoding lengths of R0 and R1; s is fixed.Source: §A.4 · p. 55

B An Illustrative Example for the proof of Lemma 8

• The construction yields the fixed partition 27 = 1 + 1 + 1 + 2 + 2 + 4 + 4 + 4 + 8.It terminates at level 3, where N3 = 1 < s.Source: B An Illustrative Example for the… · pp. 55–56
• Successive levels assign size-1 parts to A, B, B; size-2 parts to B, C; size-4 parts to A, B, C; and the size-8 part to A.At each level, the remaining histogram is halved after assigning the parts.Source: B An Illustrative Example for the… · p. 56
• The assigned parts recover category C's multiplicity as 2 + 4 = 6.The example uses the same fixed part sizes while category labels depend on the histogram.Source: B An Illustrative Example for the… · p. 56
• The same fixed partition can represent every histogram on at most three categories with total multiplicity 27.Part sizes depend only on N and s; labels depend on the histogram.Source: B An Illustrative Example for the… · p. 56

Exact egalitarian welfare with few agent and item types

• The construction adapts Goemans and Rothvoß's Theorem 12 to allocation constraints and a prescribed minimum utility, with fixed K and q and binary-encoded multiplicities.The theorem supplies the exact polynomial-time algorithm; the appendix constructs its required instance.Source: C Exact Egalitarian Welfare with Few… · p. 56
• For threshold T, integer points of each tagged configuration polytope encode one agent's bundle meeting T, while the singleton target specifies item totals and agent-type counts.The configuration bounds permit an empty bundle at T = 0 and retain every bundle used in a feasible allocation.Source: C Exact Egalitarian Welfare with Few… · p. 57
• An allocation reaches T exactly when its tagged configurations sum to the target, and their multiplicities reconstruct a compressed allocation using every item copy.Each configuration in the decomposition meets T, and the type-count and item-count coordinates enforce the required totals.Source: C Exact Egalitarian Welfare with Few… · pp. 57–58
• With dimension q + K and K configuration polytopes, Theorem 10 decides threshold feasibility in polynomial time and returns a compressed allocation when feasible.The fixed values of K and q keep the theorem's dimension-dependent exponent fixed.Source: C Exact Egalitarian Welfare with Few… · p. 58
• Scaling rational utilities to integers permits binary search over thresholds 0 through V, whose largest feasible value gives the exact optimum.The search uses O(log(V + 1)) feasibility tests; zero-utility cases are covered, including an optimum of zero when all items have zero utility.Source: C Exact Egalitarian Welfare with Few… · pp. 57–58
• The algorithm runs in polyK,q(L) time and outputs type-configuration pairs directly, without expanding binary-encoded populations or item multisets.The coefficient and target encodings have polynomial length, and the decomposition has polynomially many nonzero pairs with polynomial-length coordinates and multiplicities.Source: C Exact Egalitarian Welfare with Few… · p. 58