d4-conf-atal-2014-0412 (d4-conf-atal-2014-0412)

Given a finite type set \(T\), rational masses \(\mu_t\) summing to \(1\), and a rational piecewise-linear coalition-value function \(\phi\) on \([0,\mu]\), compute a finite list of nonzero vectors \(x^1,\ldots,x^k\) with \(\sum_j x^j=\mu\) whose total value \(\sum_j\phi(x^j)\) is within \(\varepsilon\) of the supremum over such lists. Determine the complexity in \(|T|\), the number of linear pieces, input bit length, and \(\log(1/\varepsilon)\), including whether dynamic programming over type-mass splits admits useful pruning.

A society is given by its support: a nonempty list \(T\) of \(\tau\) types with positive binary-rational masses \(\mu_t\), where \(\sum_{t\in T}\mu_t=1\). Here \(m=\tau=|T|\); support size means listed positive-mass types, not the number of possible types.
Let \(B=\prod_{t\in T}[0,\mu_t]\). The input specifies a continuous piecewise-affine function \(\phi:B\to\mathbb R\) by \(r\) rational polytopes covering \(B\), each given by linear inequalities and a rational affine formula; formulas agree on overlaps. Require \(\phi(0)=0\), but allow either sign elsewhere.
A coalition structure is any finite list of nonzero real vectors \(x^1,\ldots,x^k\in B\) with \(\sum_{j=1}^k x^j=\mu\). Repeated vectors are allowed, and there is no bound on \(k\). Its value is \(\sum_{j=1}^k\phi(x^j)\); let \(S\) be the supremum over all such lists.
Given binary-rational \(0<\varepsilon<1\), the computational problem is to output an explicit list of rational coalition vectors with value at least \(S-\varepsilon\). Let \(L\) be the total input bit length; running time includes writing the list.

Does this problem admit an algorithm polynomial in \(m,\tau,r,L,\log(1/\varepsilon)\), or is obtaining this additive guarantee NP-hard?

For finite agents with arbitrary real coalition values, every nonempty bipartition of a coalition of size \(c\le n/2\) passes IDP's size-based split filter; this is a property of that filter, not a lower bound for all algorithms. [Verified discrete result](https://ifaamas.org/AAMAS/aamas2014/proceedings/aamas/p293.pdf).
Optimal continuous resource allocation is polynomial-time computable for linear bottleneck overlapping-coalition games, a differently represented restricted model. [Verified continuous result](https://arxiv.org/pdf/1407.0420). The search located no result settling the general problem defined above.

Proven conclusion. Obtaining the additive guarantee is \(\mathrm{NP}\)-hard, even for \(m=\tau=1\) and fixed \(\varepsilon=1/4\). The reduction below has polynomial-length rational optimal solutions.

Moreover, the explicit-list requirement creates a separate, unconditional obstruction: some instances with \(m=\tau=1\) and \(r=2\) require exponentially many output coalitions.

1. Encoding Exact Cover by integer sums. We reduce from Exact Cover, a classical \(\mathrm{NP}\)-complete problem established in [Karp’s original paper](https://link.springer.com/chapter/10.1007/978-1-4684-2001-2_9).

Let the universe be \(U=\{1,\ldots,n\}\), with \(n\ge 1\), and let the listed subsets be \(C_1,\ldots,C_p\). Empty sets and duplicates can be deleted without changing whether an exact cover exists.

Define the positive integers

\[ D=n+1,\qquad E=\sum_{i=1}^{n}D^{i-1},\qquad H=nE+1,\qquad W=nH+E. \]

For each listed set, define

\[ e_j=\sum_{i\in C_j}D^{i-1}, \qquad w_j=H+e_j. \]

Let \(A=\{H,w_1,\ldots,w_p\}\). The number \(H\) serves as a padding weight. Every member of \(A\) lies between \(H\) and \(H+E\), and therefore belongs to \(\{1,\ldots,W\}\).

We claim that \(W\) is a sum of members of \(A\), with repetitions allowed, if and only if the Exact Cover instance is a yes-instance.

If an exact cover uses \(k\) sets, then \(k\le n\), because those sets are nonempty and disjoint. Their corresponding weights, together with \(n-k\) copies of \(H\), sum to \(nH+E=W\).

Conversely, suppose a multiset of \(\ell\) weights from \(A\) sums to \(W\). Since every weight is at least \(H\), and \(E<H\),

\[ \ell H\le W=nH+E<(n+1)H, \]

so \(\ell\le n\). If \(\ell\le n-1\), its sum is at most

\[ (n-1)(H+E)<nH<W, \]

where the strict inequality follows from \((n-1)E<H\). Thus \(\ell=n\).

Subtracting the \(n\) copies of \(H\), the selected set encodings must sum to \(E\). Let \(c_i\) count how many selected sets contain element \(i\), counting repetitions. Then

\[ \sum_{i=1}^{n}c_iD^{i-1} = \sum_{i=1}^{n}D^{i-1}. \]

Here \(0\le c_i\le n<D\), so neither side has carries in base \(D\). Uniqueness of base-\(D\) representation gives \(c_i=1\) for every \(i\). Hence the selected sets form an exact cover. In particular, no nonempty set is selected twice.

All constructed integers have \(O(n\log(n+1))\) bits, so this encoding is polynomial in the Exact Cover input length.

2. Constructing the permitted piecewise-affine function. Use one listed type of mass \(\mu_1=1\), so \(B=[0,1]\). Define

\[ d(u)=\min_{a\in A\cup\{0\}}|u-a|, \qquad \phi(x)=x-d(Wx). \]

This function is continuous and satisfies \(\phi(0)=0\). Its negative values are permitted by the task.

To verify the required explicit representation, sort the distinct weights as \(0=a_0<a_1<\cdots<a_s\le W\). For each \(i\in\{0,\ldots,s-1\}\), supply the following two interval polytopes and affine formulas:

• On \([a_i/W,(a_i+a_{i+1})/(2W)]\), use \(\phi(x)=(1-W)x+a_i\).
• On \([(a_i+a_{i+1})/(2W),a_{i+1}/W]\), use \(\phi(x)=(1+W)x-a_{i+1}\).

Finally, on \([a_s/W,1]\), use \(\phi(x)=(1-W)x+a_s\). A degenerate final interval may be omitted.

These intervals cover \(B\), and their formulas agree at every shared endpoint. There are at most \(2p+3\) pieces. Every coefficient and endpoint has polynomial bit length. Thus this is a polynomial-time construction in exactly the representation specified in the question.

3. An exact characterization of the coalition optimum. Define the additive semigroup

\[ \mathcal M= \left\{ \sum_{j=1}^{k}a_j: k\ge 0,\ a_j\in A \right\}, \qquad \Delta=\min_{z\in\mathcal M}|W-z|. \]

The minimum exists: its possible values are nonnegative integers, and \(0\in\mathcal M\).

We prove that \(S=1-\Delta\).

First, consider any admissible finite coalition structure \(x^1,\ldots,x^k\). For each coalition, choose a nearest weight \(b_j\in A\cup\{0\}\) to \(Wx^j\). Then \(\sum_jb_j\in\mathcal M\). Using feasibility and the triangle inequality,

\[ \begin{aligned} \sum_{j=1}^{k}\phi(x^j) &=1-\sum_{j=1}^{k}|Wx^j-b_j|\\ &\le 1-\left|W-\sum_{j=1}^{k}b_j\right|\\ &\le 1-\Delta. \end{aligned} \]

This argument applies to every finite list, regardless of its length or repeated vectors.

For the reverse inequality, choose \(z_*\in\mathcal M\) attaining \(\Delta\). Since \(H\in\mathcal M\) and \(0<H<W\),

\[ \Delta\le W-H<W. \]

Consequently, \(0<z_*<2W\). Choose a representation \(z_*=\sum_{j=1}^{k}a_j\), with \(a_j\in A\), and set \(x^j=a_j/z_*\). These are positive rational coalition vectors in \(B\), and they sum to \(1\). Moreover,

\[ \begin{aligned} \sum_{j=1}^{k}d(Wx^j) &\le \sum_{j=1}^{k}\left|\frac{Wa_j}{z_*}-a_j\right|\\ &=\left|\frac{W}{z_*}-1\right|\sum_{j=1}^{k}a_j\\ &=|W-z_*|=\Delta. \end{aligned} \]

Their value is therefore at least \(1-\Delta\). Combined with the upper bound, this proves \(S=1-\Delta\), with the maximum attained by rational coalitions.

This also proves that the reduction has short optimal outputs. Each \(a_j\ge H\), so

\[ kH\le z_*<2W, \qquad k<\frac{2W}{H}=2n+\frac{2E}{H}<2n+2. \]

Thus \(k\le 2n+1\). Every numerator and denominator in \(x^j=a_j/z_*\) has \(O(\log W)\) bits.

4. The constant-gap hardness reduction. Section 1 gives the following dichotomy:

• If an exact cover exists, then \(W\in\mathcal M\), hence \(\Delta=0\) and \(S=1\).
• If no exact cover exists, then \(W\notin\mathcal M\). Since all members of \(\mathcal M\) are integers, \(\Delta\ge 1\), hence \(S\le 0\).

Now run a hypothetical polynomial-time algorithm for the requested problem with \(\varepsilon=1/4\). On a yes-instance, its output must have value at least \(3/4\). On a no-instance, every feasible output has value at most \(0\).

Evaluating the explicit rational output is polynomial in its bit length, using the listed interval formulas. Therefore, testing whether its value is positive decides Exact Cover in polynomial time. This establishes \(\mathrm{NP}\)-hardness, even with one support type and fixed additive error. Every reduction instance has a polynomial-length exact rational optimum, as proved above.

5. The unconditional output-length obstruction. For an integer \(N\ge 1\), again use one type of mass \(1\), and define

\[ \delta=2^{-N}, \qquad \phi(x)=\min\{x/\delta,1\}. \]

This has two rational affine pieces and input length \(O(N)\). For every coalition structure,

\[ \sum_j\phi(x^j)\le\sum_jx^j/\delta=2^N. \]

Splitting the mass into \(2^N\) coalitions of size \(\delta\) attains this bound, so \(S=2^N\).

Each coalition contributes at most \(1\). Therefore, a list attaining value at least \(S-1/4\) must have

\[ k\ge 2^N-\frac14. \]

Since \(k\) is an integer, \(k\ge 2^N\). Writing this explicit list requires exponential time. Consequently, the polynomial running-time bound asked for in the question is impossible unconditionally under the stated output format.

⟨structured verdict parsed — rendered above⟩

The output proves the claimed hardness result and the separate unconditional obstruction from output length. I found no major or minor mathematical issues. Both arguments apply to the representation and feasibility requirements in USER_TASK.

• Source problem and integer encoding.

The cited source problem is Exact Cover: given an explicitly listed finite universe and a family of subsets, decide whether some subfamily contains every universe element exactly once. Its NP-completeness is the standard result invoked from [Karp’s paper](https://www2.seas.gwu.edu/~simhaweb/champalg/tsp/papers/KarpOriginal.pdf). The reduction uses this unrestricted version, so no additional restriction needs justification.

Deleting empty sets and duplicates preserves existence of an exact cover. Restricting to a nonempty universe does not affect hardness.

The constructed integers are positive, and the bounds used are correct: \(E<H\), \((n-1)E<H\), and \(H+E\le W\).

For the forward implication, an exact cover contains at most \(n\) nonempty sets. Its encodings sum to \(E\); adding \(n-k\) padding weights therefore gives exactly \(W\).

For the converse, the lower bound \(H\) on every weight forces \(\ell\le n\). If \(\ell\le n-1\), the stated upper bound gives a total strictly less than \(nH\), hence less than \(W\). Thus precisely \(n\) weights occur.

After removing their \(H\) contributions, each base-\(D\) digit count satisfies \(0\le c_i\le n<D\). The appeal to uniqueness of positional representation is valid: there are no carries, and each count must equal one. Repeated nonempty sets consequently cannot occur. This proves the claimed equivalence even though repetitions of weights are allowed.

The integer bit-length bound is correct under the standard explicit encoding of Exact Cover. The construction takes polynomial time.

• Piecewise-affine representation.

The mass \(\mu_1=1\) satisfies the task’s support requirements, giving \(m=\tau=1\) and \(B=[0,1]\).

Between consecutive sorted weights, the nearest-weight distance has precisely the two affine branches written in the output. Subtracting those branches from \(x\) gives the stated formulas for \(\phi\).

At each midpoint, the two distances coincide; at every weight, the distance is zero. Beyond the largest weight, that weight is nearest. These facts verify coverage and agreement on overlaps, including the final interval.

Since \(0\) is included among the distance centers, \(\phi(0)=0\). Negative values do not violate the task.

There are at most \(p+1\) positive distinct weights, giving at most \(2p+3\) pieces. Their endpoints and coefficients have polynomial bit length. Rational endpoints need not be dyadic: the task permits rational polytopes.

• Existence of the semigroup minimum and the universal upper bound.

The set of distances defining \(\Delta\) is a nonempty subset of the nonnegative integers, because \(0\in\mathcal M\). Therefore its minimum exists and is attained.

For any feasible finite list, nearest weights exist because the set of centers is finite. Their sum belongs to \(\mathcal M\); any selected zero centers can simply be omitted from that sum.

Feasibility gives \(\sum_j Wx^j=W\). The triangle inequality therefore proves the displayed upper bound \(1-\Delta\). It applies to arbitrary real coalition sizes, repeated vectors, and every finite list length. Thus unrestricted coalition counts do not invalidate the bound.

• Attainment and rational output size.

The comparison with \(H\in\mathcal M\) gives \(\Delta<W\). Consequently, any minimizing \(z_*\) satisfies \(0<z_*<2W\), as claimed. In particular, division by \(z_*\) is legitimate, and its semigroup representation contains at least one positive weight.

Each normalized vector \(x^j=a_j/z_*\) is positive and at most one, since \(a_j\le z_*\). Their sum is one, so this is a feasible coalition structure.

The bound on each distance is valid because its corresponding \(a_j\) is an allowed center. All terms in the ensuing absolute-value calculation share the same scalar factor, so their sum is exactly bounded by \(|W-z_*|=\Delta\).

This yields a value at least \(1-\Delta\). Together with the universal upper bound, it establishes \(S=1-\Delta\) and actual attainment.

The coalition-count estimate \(k<2n+2\) correctly implies \(k\le2n+1\). Numerators and denominators have \(O(\log W)\) bits. The claimed polynomial-length rational optimum is therefore established on both yes- and no-instances.

• Constant-gap hardness.

The integer encoding gives \(\Delta=0\) on yes-instances and \(\Delta\ge1\) on no-instances. Hence the optimum is respectively \(1\) or at most \(0\).

With \(\varepsilon=1/4\), every valid approximation output has value at least \(3/4\) on a yes-instance, while every feasible list has value at most zero on a no-instance. Testing positivity consequently distinguishes the cases.

Exact evaluation of the rational output takes polynomial time in its bit length and the constructed input length. A hypothetical polynomial-time algorithm necessarily writes a polynomial-length output, because writing time is included. Thus the decision procedure is polynomial-time under the hypothesis being contradicted.

This establishes the claimed NP-hardness of obtaining the additive guarantee, with one support type and fixed error.

• Unconditional output-length obstruction.

The second construction is continuous, satisfies \(\phi(0)=0\), and has two rational affine pieces agreeing at \(\delta\). Its input has length \(O(N)\).

The bound \(\phi(x)\le x/\delta\) gives total value at most \(2^N\). The explicitly described list of \(2^N\) coalitions of size \(\delta\) attains that value, so the stated optimum is correct.

Since each coalition contributes at most one, achieving value at least \(2^N-1/4\) requires an integer list length \(k\ge2^N\). Writing that many entries requires exponential time in this family’s input length. Repetitions being allowed does not permit compressed multiplicities under the required explicit-list format.

No repair or additional mathematical clarification is needed. The output resolves the target and correctly distinguishes its two established conclusions.

⟨structured verdict parsed — rendered above⟩