PaperlayerView exact revision on arXiv

Source-linked AI summary

Settling the Computational Complexity of Max-Min Allocation with Ternary Valuations

Thi Ngoc Anh Vu, Trung Thanh Nguyen, Khaled Elbassioni, Jörg Rothe

arXiv:2610.05237v1cs.GTcs.AI

TL;DR

The paper asks which small value domains make max-min allocation tractable or hard across additive and submodular valuations. The paper analyzes bi-valued and ternary valuation classes, using a matching-based construction for mixed additive valuations and reductions for submodular hardness results. For fixed odd c≥1, distinguishing OPT=T from T−1 (T>1 polynomially bounded) is NP-hard for {−2,0,c}-submodular valuations; OPT≥1 is NP-complete for explicitly represented conflict-pair valuations.

  • Problem

    The paper asks which small value domains make max-min allocation tractable or hard across additive and submodular valuations.

    Source: §1 · p. 2

  • Method

    The paper analyzes bi-valued and ternary valuation classes, using a matching-based construction for mixed additive valuations and reductions for submodular hardness results.

    Source: §1 · p. 2, §4 · p. 11, §5 · p. 11

  • Results

    For fixed odd c≥1, distinguishing OPT=T from T−1 (T>1 polynomially bounded) is NP-hard for {−2,0,c}-submodular valuations; OPT≥1 is NP-complete for explicitly represented conflict-pair valuations.

    Source: §5 · p. 11, §6 · p. 14

  • Takeaways & Limitations

    The results show that tractability for these small value sets depends on whether the valuations are additive or submodular.

    Source: §7 · p. 16

    The complexity of {2, c}-submodular valuations with odd c remains open, as does whether the half-integer case is polynomial for positive submodular valuations.

    Source: §7 · p. 17

Abstract

from arXiv · show

We study the problem of computing an allocation of indivisible items that maximizes egalitarian welfare, i.e., the utility of the worst-off agent, when agents' item values or marginal values belong to a small set. For additive valuations with values in $\{p,q\}$, where $q>p>0$ and $\gcd(p,q)=1$, we give a polynomial-time algorithm when $p=2$ and prove constant-gap hardness when $p\geq3$, already with exactly three high-valued goods per agent. We also give an $\sqrt{3/2}$-approximation for common positive bi-valued additive valuations. For mixed additive valuations in $\{-p,0,c\}$, where $p\in\{1,2\}$ and $c$ is a positive integer, a reduction to maximum-weight perfect matching resolves the conjectured tractability of $\{-2,0,c\}$-valuations. For submodular valuations with marginals in $\{-2,0,c\}$, where $c$ is odd, we establish an exact unit-gap hardness result and exponential value-query lower bounds, even when all but one agent are additive. Finally, for $\{-1,0,1\}$-submodular valuations, we prove that no finite multiplicative approximation exists unless $\p=\np$. Together, our results resolve open questions and provide a complete picture of the computational complexity of max-min allocation with ternary valuations.

1 Introduction

Maximizing egalitarian welfare protects the worst-off agent, but is computationally hard in general, motivating study of restricted value domains. This paper classifies tractability and hardness for bi-valued and ternary additive and submodular valuations.

1 Introduction

  • Egalitarian welfare is the minimum utility across agents, making its maximization a natural objective when protecting the worst-off participant matters.The paper notes applications including public and computing resources, scheduling, and humanitarian aid.Source: §1 · p. 1
  • Small value domains extend the tractable binary setting while allowing study of which arithmetic and combinatorial features drive complexity.Prior work includes polynomial solvability for binary instances and hardness for general additive valuations over goods.Source: §1 · pp. 1–2

1.1 Related work

  • Prior work left open the complexity of additive and submodular {−2, 0, c}-valuations, while establishing hardness for {−1, 0, 1}-submodular valuations [22].Earlier work also gave polynomial-time algorithms for some mixed {−1, 0, c}-valuations [20].Source: §1.1 · p. 2

1.2 Our contributions

  • For additive {2, q}-valuations, the paper gives a polynomial-time algorithm, while for each fixed p ≥3 it proves a constant approximation gap, even with exactly three highly valued goods per agent.It also presents a 3/2-approximation algorithm; the supplied passages do not specify its valuation scope.Source: §1.2 · p. 2
  • For mixed additive {−p, 0, c}-valuations with p ∈{1, 2}, a reduction to maximum-weight perfect matching yields a polynomial-time algorithm.This resolves the conjectured tractability of additive {−2, 0, c}-valuations.Source: §1.2 · p. 3

2 Preliminaries

The preliminaries define allocations, egalitarian welfare, and the valuation classes used in the paper. They also state the oracle model and explain how decision algorithms and approximation guarantees are interpreted.

2 Preliminaries

  • An allocation partitions the items among agents, and egalitarian welfare is the minimum utility among the agents.The Maximum Egalitarian Welfare problem seeks an allocation maximizing this quantity.Source: §2 · p. 3
  • A valuation is A-submodular when it has diminishing marginal gains and every marginal gain belongs to A.A-additive valuations and conflict-pair valuations are also introduced as special classes considered in the paper.Source: §2 · p. 3
  • Conflict-pair valuations are submodular with marginals in {−1, 0, 1}: holding both paired items incurs a one-unit penalty beyond singleton values.The pairs are disjoint, so the valuation is a sum of functions on disjoint item sets.Source: §2 · p. 4
  • For submodular valuations, the paper assumes a value-oracle model in which a query returns an agent’s value for a specified bundle.The paper also invokes matroid-rank functions in Section 5.Source: §2 · p. 4
  • A polynomial-time algorithm for the threshold decision version yields an optimal allocation by binary search over possible welfare values.A factor-ρ approximation returns welfare at least OPT/ρ; an FPTAS is polynomial in both input size and 1/ε.Source: §2 · p. 4

3 Bi-valued valuations

For {2, q}-additive valuations with odd q, the paper gives an exact polynomial-time algorithm based on maximum-weight matching. For p ≥3, it proves constant-gap inapproximability and gives a 3/2-approximation.

3.1 A polynomial-time algorithm for p = 2

  • For every odd q ≥3, MEW under {2, q}-additive valuations is solvable exactly in time polynomial in n and m.The algorithm tests whether a target welfare T is feasible, then constructs an allocation meeting it.Source: §3.1 · p. 4

3.1.1 Feasibility via cost function

  • The p = 2 algorithm tests target T by seeking a high assignment whose total cost, Σ_i Φ(k_i), is at most the number of goods m.Φ(k) is the minimum number of goods an agent needs to reach T when exactly k assigned goods are high-valued.Source: §3.1.1 · pp. 4–5

3.1.2 Saving and the slot decomposition

  • Marginal savings from high-valued goods are represented by slots, whose maximum filling value with k goods equals the agent’s saving σ(k).The decomposition has a lead single slot when T is odd, followed by pair slots and up to two tail single slots.Source: §3.1.2 · p. 5

3.1.3 Reduction to maximum-weight matching

  • A maximum-weight matching in a graph built from goods and agents’ slots computes the savings needed for the target-feasibility test in polynomial time.The graph has at most m + 2nm vertices and O(nm^2) edges.Source: §3.1.1 · p. 5, §3.1.3 · pp. 6–7

3.2 Approximability of the case p ≥3

  • For coprime integers q > p ≥3, approximating MEW within any factor ρ < pq/(pq −1) is NP-hard.The reduction from p-dimensional matching separates instances with a perfect matching, where OPT = pq, from those without one, where OPT ≤ pq −1.Source: §3.2 · pp. 7–8
  • For MEW with {p, q}-additive valuations where 3 < p < q, Theorem 3 gives a polynomial-time 3/2-approximation; both rounded instances are exactly solvable in polynomial time by Theorem 1.Source: §3.2 · p. 8

4 Poly-time Algorithm for {−p, 0, c}-Additivities

For additive {−p, 0, c} valuations with p ∈ {1, 2}, the paper reduces target-welfare feasibility to a maximum-weight perfect matching problem. This yields a polynomial-time algorithm for finding an allocation of maximum egalitarian welfare.

4 Poly-time Algorithm for {−p, 0, c}-Additivities

  • An allocation of maximum egalitarian welfare can be found in polynomial time for additive {−p, 0, c} valuations with p ∈ {1, 2} and positive integer c.The algorithm reduces a fixed welfare-threshold decision problem to maximum-weight perfect matching.Source: §4 · p. 8
  • After normalization, each agent’s utility is c_i g_i − p_i h_i, and target feasibility requires enough chore-absorption capacity across agents to cover all H universal chores.For an agent with g_i valued goods, f_i(g_i) is the maximum number of universal chores it can absorb while retaining utility at least T.Source: §4 · p. 9
  • The matching graph uses good vertices, incidence-specific ports, absorbers, and parity vertices to encode assignment weights and parity corrections.For odd c_i with p_i = 2, an extra absorber and a −1-weight edge represent the parity penalty.Source: §4 · p. 10
  • In the two-agent {−2, 0, 3} example, the maximum egalitarian welfare is 3, and the highlighted perfect matching has weight 8.The corresponding assignment gives agent 1 two goods and agent 2 one; the parity penalty accounts for the difference between matching weight and threshold feasibility.Source: §4 · pp. 10–11
  • The matching graph has a perfect matching exactly when a T-admissible good assignment exists, and its maximum weight equals the maximum Φ over such assignments.A T-admissible assignment gives every agent at least L_i valued goods.Source: §4 · pp. 9–10

5 Hardness for {−2, 0, c}-Submodular Valuations

For every fixed odd c, max-min allocation with {−2, 0, c}-submodular valuations has an exact unit-gap hardness result, even when all but one agent are additive. A reduction encodes CLIQUE with sparse paving matroids and chore-balanced agent valuations.

5 Hardness for {−2, 0, c}-Submodular Valuations

  • For fixed odd c, distinguishing OPT = T from OPT = T −1 is NP-hard even when all but one agent are additive.Unless P = NP, this rules out an FPTAS and polynomial-time allocation with additive error strictly below one.Source: §5 · p. 11

5.1 A sparse paving encoding of CLIQUE

  • The sparse paving matroid makes a union of s vertex-pairs independent exactly when their vertices form a clique, with rank computable in polynomial time.Its forbidden sets are unions of s whole pairs indexed by noncliques.Source: §5.1 · p. 12

5.2 The reduction

  • For a CLIQUE instance, the reduction uses k pair agents and a collector, with dummies, H = c(k − s) chores, and threshold T = cd.Pair agents are additive, while only the collector can be non-additive; every agent's valuation is (c + 2)ρ_i(S) − 2|S|.Source: §5.2 · p. 12
  • A clique of size s yields an allocation where every agent has value cd = T, using the clique pairs for the collector and c chores per remaining pair agent.The collector receives its dummies and the clique's pairs; each pair agent receives its private dummies, with chores assigned to agents outside the clique.Source: §5.2 · p. 12
  • Any allocation with welfare at least T forces a size-s clique: tightness makes each agent's held nonloops independent and the collector's pair items encode that clique.The soundness argument first bounds total welfare and then uses equality to constrain which agents can hold each item.Source: §5.2 · pp. 12–13
  • The reduction has the exact gap: OPT is T on clique instances and at most T −1 otherwise.Completeness gives T; soundness and integrality give the upper bound for non-clique instances.Source: §5.2 · p. 13
  • Every instance also has an allocation of welfare at least T −1, so the construction establishes the claimed unit gap.The lower-bound allocation uses s −1 whole pairs and one item from each of two further pairs for the collector.Source: §5.2 · p. 13

6 Approximability of {−1, 0, 1}-Submodularity

The section reduces 3-SAT to max-min allocation using explicitly represented conflict-pair valuations with marginals in {−1, 0, 1}. The reduction establishes a 0-versus-1 welfare gap, yielding NP-completeness and ruling out finite multiplicative approximation unless P = NP.

Hardness and inapproximability

  • Deciding whether OPT ≥1 is NP-complete even with at most one conflict pair and at most two value-1 items per agent; the reduction promises OPT ∈{0, 1}.Unless P = NP, no finite-ratio multiplicative approximation or fixed additive error below 1 can return an allocation for these instances.Source: §6 · p. 14

Reduction from 3-SAT

  • The reduction creates a cycle for each variable, whose two perfect matchings encode true and false, and one clause item for each clause.Each occurrence is assigned to a cycle agent; its conflict pair is activated by the good chosen when that literal is false.Source: §6 · p. 15

Completeness

  • A satisfying assignment yields a complete allocation in which every agent has value 1, so OPT ≥1.Each clause item goes to an agent representing a true literal, without activating its conflict pair.Source: §6 · p. 15

Soundness

  • If a complete allocation gives every agent value at least 1, its cycle goods define a Boolean assignment that satisfies every clause.Each agent must receive exactly one positive good, and each clause item must go to an occurrence agent whose literal is true under the assignment.Source: §6 · p. 15

Promise and gap

  • Every constructed instance has OPT ∈{0, 1}, with OPT =1 exactly when the source formula is satisfiable.An arbitrary Boolean assignment and cycle matching give a complete allocation of nonnegative welfare, while the reduction's completeness and soundness establish the exact gap.Source: §6 · pp. 15–16

Inapproximability

  • Any finite-ratio multiplicative guarantee for returning an allocation would distinguish the two promised cases, since positive welfare is integral and impossible when OPT =0.The same reduction rules out fixed additive error ε <1 when OPT =1.Source: §6 · p. 16

7 Discussion and Open Problems

The discussion places the paper’s results within a tractability boundary for small value sets and identifies open cases. It highlights that the demonstrated tractability for mixed valuations depends on additivity.

Complexity boundary

  • For positive additive values {p, q}, complexity depends on the reduced denominator p: the problem is polynomial-time solvable for p ∈{1, 2} and constant-factor hard to approximate for p ≥3.For p ≥3, longer flat runs in the savings encode exact cover.Source: §7 · p. 16

Additivity and submodularity

  • The results for mixed and submodular valuations show that the tractability of {−2, 0, c}-valuations relies on additivity.The discussion also reports hardness and query lower bounds for submodular classes.Source: §7 · pp. 16–17

Open problems

  • The complexity of {2, c}-submodular valuations with odd c remains unresolved, as does whether the half-integer case is polynomial for positive submodular valuations.The latter case is identified as the one that would complete the picture.Source: §7 · p. 17
  • Further directions include closing the approximation gap for p ≥3, between pq/(pq −1) ≤12/11 and 3/2, and extending matching to leximin and other welfare objectives.Source: §7 · p. 17

A Missing proofs from Section 3

These missing proofs decompose a sequence into lead, pair, and tail slots, then show that the parse-order filling maximizes value for each number of goods. The argument handles the final position separately and bounds arbitrary fillings by the parse-order construction.

Proof of Lemma 3

  • The sequence agrees with its alternating comparison sequence through position K −1, while its final entry is bounded by that sequence.The proof uses the choice of K and whether the final block starts at K or continues a pair.Source: A Missing proofs from Section 3 · pp. 19–20
  • The alternating sequence decomposes into an optional lead slot, pair slots of weights (s −1, s), and tail slots of weight at most s −1.A final block may form one tail slot or two tail slots, depending on its position and final entry.Source: A Missing proofs from Section 3 · p. 20
  • Filling slots in parse order with k goods collects exactly µ1 through µk, so its value is σ(k).This follows because a pair slot contributes s −1 for its first position and the full pair contributes (s −1) + s.Source: A Missing proofs from Section 3 · p. 20

Proof of Lemma 4

  • For arbitrary fillings, the proof compares lead and pair occupancy against parse order when k ≤λmax + 2P, then bounds tail-slot deficits when k exceeds that threshold.In the second case, parse order takes the earliest tail slots, which have the largest weights and smallest deficits.Source: A Missing proofs from Section 3 · pp. 20–21

B Missing proofs from Section 5

The appendix verifies a matroid construction by taking all rank-r sets outside a specified family as bases. It then uses the resulting rank function to establish submodularity and the marginal values needed for the valuation construction.

Valuation properties

  • A valuation formed from the rank function and a modular set-size term is submodular, with marginals in {−2, c}.The rank marginal is either zero or one, so the resulting marginal is respectively −2 or c.Source: B Missing proofs from Section 5 · p. 21

Matroid construction

  • Declaring the specified family of r-subsets dependent yields a rank-r matroid, verified by showing the remaining sets satisfy basis exchange.Distinct family members intersect in at most r −2 elements, so among the exchange candidates at most one is forbidden.Source: B Missing proofs from Section 5 · p. 21
  • The constructed rank function gives rank r −1 exactly to the specified r-sets, while smaller sets are independent and sets larger than r contain a basis.Source: B Missing proofs from Section 5 · p. 21

Construction size

C Missing proofs from Section 6

The missing proofs establish that conflict-pair valuations are submodular with marginals in {-1,0,1}, and that the constructed valuations have polynomial-size representations.

Range of the marginal values

  • Every marginal belongs to {-1,0,1}: unpaired items retain singleton values, while paired items have marginals determined by whether their counterpart is present.For a pair (x,y), x's marginal is 1 if y is absent and 0 otherwise; y's is 0 if x is absent and -1 otherwise.Source: C Missing proofs from Section 6 · p. 21

Submodularity

  • Conflict-pair valuations are submodular because an item's marginal can only decrease as a bundle gains its paired item.For the example, b's marginal falls from 0 to -1 when a is present, while a's falls from 1 to 0 when b is present; other items contribute additively.Source: C Missing proofs from Section 6 · pp. 21–22

Construction

  • Each constructed agent valuation has at most one disjoint conflict pair, with singleton values 1 and 0, and agents without assigned occurrences are additive.Even when a variable occurs twice in one clause, its occurrences go to different agents, so the construction satisfies the pair-disjointness condition.Source: C Missing proofs from Section 6 · p. 22

Representation size

  • When every variable occurs at least twice, n = ℓ ≤ 3M and m ≤ 4M, so the valuation representation and its construction are polynomial in the source size.Each valuation uses two positive goods, at most one zero-valued clause item, at most one conflict pair, and default singleton value -1; the full singleton-value matrix is also polynomial.Source: C Missing proofs from Section 6 · p. 22
Loading 2610.05237v1…