d4-conf-ecai-2014-0223 (d4-conf-ecai-2014-0223)

Given a finite category set \(O\), a policy word \(\Pi\) over types \(\{A,B\}\), masses \(\mu_A=\mu_B=1/2\), supply \(q_o=1/2\) for each \(o\in O\), rational additive valuations \(v_A,v_B\), and a feasible baseline mass flow with bundle distributions \(\beta_A,\beta_B\), does there exist a feasible alternative flow under the same policy and supplies with distributions \(\alpha_A,\alpha_B\) such that, for each type \(\theta\), there is a coupling \(\kappa_\theta\) of \(\beta_\theta\) and \(\alpha_\theta\) supported on pairs \((S,S')\) satisfying \(v_\theta(S')\ge v_\theta(S)\), with positive mass on strictly improving pairs? Each unit of mass receives an integral bundle \(S\subseteq O\); at a policy position, the called cohort's mass picks one available category, with mass tracked by bundle history and cumulative category use bounded by supply.

A society is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational; \(\tau\) is the support size, not the number of possible types. Here the support is \(\{A,B\}\), with \(\mu_A=\mu_B=1/2\), so total mass is one.
Input consists of a nonempty category set \(O\), with \(m=|O|\), a policy \(\Pi\in\{A,B\}^{m}\), supplies \(q_o=1/2\), nonnegative rational additive valuations \(v_A,v_B\), and an explicitly listed feasible rational baseline flow. Let \(L\) be the total input bit length, including the baseline's nonzero transitions and their bundle labels.
A flow starts each type's entire mass with the empty bundle. At position \(t\), every unit of type \(\Pi_t\) must add exactly one category absent from its current bundle; the other type's bundles stay unchanged.
Mass at each bundle history may split arbitrarily among such additions, with conservation of mass. Cumulative consumption of each category at every position is at most its supply; flows may have nonnegative real masses. There are no non-manipulators, subsequent trades, or monetary payments.
Write \(\beta_\theta\) and \(\alpha_\theta\) for the baseline and alternative terminal bundle measures, each of total mass \(1/2\). An alternative is an improvement if, for each \(\theta\), a coupling \(\kappa_\theta\) of these measures is supported on pairs \((S,S')\) with \(v_\theta(S')\ge v_\theta(S)\), and for at least one type the coupling assigns positive mass to pairs satisfying strict inequality. Utility ties are allowed; no sincere-picking requirement is imposed.

Is deciding whether such an alternative flow exists solvable in polynomial time in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard?

The discrete problem of finding a Pareto-improving joint picking strategy without trades or payments is \(\mathrm{NP}\)-complete even with two manipulators, additive valuations, and no non-manipulator ([verified full version](https://recherche.noiraudes.net/resources/papers/ECAI14-full.pdf)).
No result settling this exact continuous mass-flow and bundle-coupling problem was located in the literature search.

1. Classification. The decision problem is \(\mathrm{NP}\)-complete, even with the specified support size \(\tau=2\), masses and supplies equal to \(1/2\), and a baseline that never splits mass.

The hardness construction adapts the numerical gadget in Proposition 5 of [Bouveret and Lang’s full version](https://recherche.noiraudes.net/resources/papers/ECAI14-full.pdf). The crucial additional argument below proves that arbitrary fractional splitting cannot create an improvement in a negative partition instance.

2. A terminal-measure characterization. Let \(r_\theta\) denote the number of occurrences of type \(\theta\) in the policy. Every terminal bundle of that type has cardinality \(r_\theta\): each occurrence adds exactly one previously absent category.

For terminal measures \(\alpha_A,\alpha_B\), define category consumption by
\(C_o=\sum_{\theta\in\{A,B\}}\sum_{S\ni o}\alpha_\theta(S)\).
Because categories are never removed or repeated within a bundle, this equals cumulative consumption at the terminal position. Thus any feasible flow satisfies \(C_o\le 1/2\). Moreover,
\(\sum_{o\in O}C_o=(r_A+r_B)/2=m/2\).
Consequently, every category’s terminal consumption equals \(1/2\).

Conversely, suppose each \(\alpha_\theta\) has total mass \(1/2\), is supported on bundles of cardinality \(r_\theta\), and satisfies the category capacities. For each terminal bundle, order its categories and route its assigned mass along the path that adds them at successive occurrences of its type. Superposing these paths gives a flow with conservation and the required additions. At every position, consumption of each category is at most its terminal consumption, so all intermediate capacities hold.

Therefore, these terminal conditions characterize feasible flows.

3. The reduction. Start with positive integers \(s_1,\ldots,s_n\), encoded in binary, with
\(\sum_{i=1}^{n}s_i=2K\), where \(K\) is a positive integer. The question is whether some index subset sums to \(K\). This even-total restriction of \(\mathrm{PARTITION}\) remains \(\mathrm{NP}\)-hard: doubling every integer in an unrestricted instance preserves its answer and makes its total even.

Create the categories
\(O=\{z,g_1,\ldots,g_n,d_1,\ldots,d_n\}\),
so \(m=2n+1\). Use the policy \(\Pi=AB^nA^n\), where the powers denote repetitions. Set all supplies and both type masses to \(1/2\).

The additive valuations are:

| Category | \(v_A\) | \(v_B\) |
|---|---:|---:|
| \(g_i\) | \(s_i\) | \(s_i\) |
| \(d_i\) | \(0\) | \(0\) |
| \(z\) | \(K-1/2\) | \(K+1/2\) |

These valuations are nonnegative because \(K\ge 1\).

Let \(G=\{g_1,\ldots,g_n\}\) and \(D=\{d_1,\ldots,d_n\}\). The baseline sends all of type \(A\)’s mass to \(\{z\}\cup D\) and all of type \(B\)’s mass to \(G\). Explicitly, \(A\) first adds \(z\), \(B\) adds the categories \(g_1,\ldots,g_n\), and \(A\) then adds \(d_1,\ldots,d_n\). Every addition carries mass \(1/2\).

This baseline is feasible: each category is consumed exactly once by mass \(1/2\). Its terminal measures are
\(\beta_A=\tfrac12\delta_{\{z\}\cup D}\) and
\(\beta_B=\tfrac12\delta_G\),
where \(\delta_S\) is the unit point mass at \(S\). The baseline utilities are respectively \(K-1/2\) and \(2K\).

4. A partition gives an improvement. Suppose \(J\subseteq\{1,\ldots,n\}\) satisfies \(\sum_{i\in J}s_i=K\), and put \(j=|J|\). Positivity of the integers and the total \(2K\) imply \(1\le j\le n-1\).

Choose \(D_A\subseteq D\) with \(|D_A|=n+1-j\), which is possible because \(1\le j\le n-1\). Set
\(S_A=\{g_i:i\in J\}\cup D_A\)
and
\(S_B=\{z\}\cup\{g_i:i\notin J\}\cup(D\setminus D_A)\).

These bundles partition \(O\), and their cardinalities are
\(|S_A|=n+1\) and
\(|S_B|=1+(n-j)+(j-1)=n\).
They therefore match the two types’ numbers of picks. Sending mass \(1/2\) to each bundle is feasible by Section 2.

Their utilities are \(v_A(S_A)=K>K-1/2\) and
\(v_B(S_B)=2K+1/2>2K\).
For each type, coupling its baseline point mass to its new point mass strictly improves all its mass. Hence the constructed instance is positive.

5. A fractional improvement gives a partition. Now suppose an improving flow exists, with arbitrary nonnegative real masses.

Because each baseline measure is concentrated on one bundle, its coupling condition implies that every positive-mass alternative bundle satisfies
\(v_A(S)\ge K-1/2\) for type \(A\), or
\(v_B(S)\ge 2K\) for type \(B\).

Normalize the alternative measures to probability distributions:
\(P_\theta(S)=2\alpha_\theta(S)\).
Define
\(w(S)=\sum_{i:g_i\in S}s_i\),
\(x_\theta=P_\theta(z\in S)\), and
\(W_\theta=\sum_S P_\theta(S)w(S)\).
Every \(w(S)\) is an integer.

For every positive-probability type-\(A\) bundle:

• If \(z\notin S\), then \(w(S)\ge K-1/2\), and integrality gives \(w(S)\ge K\).
• If \(z\in S\), nonnegativity gives \(w(S)\ge 0\).

Thus \(W_A\ge K(1-x_A)\).

For every positive-probability type-\(B\) bundle:

• If \(z\notin S\), then \(w(S)\ge 2K\).
• If \(z\in S\), then \(w(S)+K+1/2\ge 2K\), so integrality gives \(w(S)\ge K\).

Thus \(W_B\ge 2K-Kx_B\).

The supply of \(z\), after normalization, gives \(x_A+x_B\le 1\). The supplies of the integer-valued categories give
\(W_A+W_B=\sum_i s_i\bigl(P_A(g_i\in S)+P_B(g_i\in S)\bigr)\le 2K\).
Combining these inequalities yields

\(\displaystyle 2K\ge W_A+W_B \ge 3K-K(x_A+x_B) \ge 2K. \)

Every inequality must therefore be an equality. In particular,
\(W_A=K(1-x_A)\) and \(W_B=2K-Kx_B\).

The corresponding bundlewise lower bounds have nonnegative slack. Their expected slack is zero, so every positive-probability bundle has zero slack. This proves the following exhaustive table:

| Type | Contains \(z\)? | Forced \(w(S)\) | Utility |
|---|---|---:|---:|
| \(A\) | Yes | \(0\) | \(K-1/2\) |
| \(A\) | No | \(K\) | \(K\) |
| \(B\) | Yes | \(K\) | \(2K+1/2\) |
| \(B\) | No | \(2K\) | \(2K\) |

Strict improvement has positive mass for at least one type. Because its baseline is a point mass, this requires a positive-mass alternative bundle with utility strictly above that type’s baseline utility. By the table, any such bundle has \(w(S)=K\).

Hence its index subset \(\{i:g_i\in S\}\) solves the original partition instance. This proves soundness for arbitrary real splitting.

The construction has polynomial bit length. There are \(2n+1\) categories, the valuation numerators have polynomial encoding length, and the baseline contains only linearly many transitions with polynomial-size bundle labels. Thus the reduction proves \(\mathrm{NP}\)-hardness under the stated encoding.

6. Membership in \(\mathrm{NP}\). It remains to justify polynomial-size certificates despite permitting real masses.

Aggregate the given baseline into terminal atoms \(S_{\theta,i}\) with positive rational masses \(b_{\theta,i}\). Let \(R\) be their total number. Both \(R\) and the bit lengths of these aggregated masses are polynomially bounded by the explicit input length.

Introduce a variable \(y_{\theta,i,T}\) for every bundle \(T\) satisfying
\(|T|=r_\theta\) and
\(v_\theta(T)\ge v_\theta(S_{\theta,i})\).
It represents coupling mass from baseline atom \(S_{\theta,i}\) to terminal bundle \(T\). Impose nonnegativity and the equations

\(\displaystyle \sum_T y_{\theta,i,T}=b_{\theta,i}\)

for every baseline atom, and

\(\displaystyle \sum_{\theta,i,T:\,o\in T}y_{\theta,i,T}=\tfrac12\)

for every category \(o\).

By Section 2, this system exactly describes feasible terminal couplings with weak improvement. Strict improvement is equivalent to positivity of the linear objective

\(\displaystyle \sum_{\theta,i,T:\,v_\theta(T)>v_\theta(S_{\theta,i})}y_{\theta,i,T}. \)

Although there can be exponentially many variables, this is a finite, nonempty, bounded rational polytope: the baseline supplies a feasible point, and each variable is bounded by its baseline row mass. A linear objective attains its maximum at a vertex.

There are \(R+m\) equality rows. Any vertex has at most \(R+m\) positive variables. Indeed, if the corresponding columns were linearly dependent, a sufficiently small positive and negative perturbation along that dependence would preserve the equations and nonnegativity, contradicting extremality.

Those positive coordinates have polynomial bit length. Select a nonsingular square subsystem determining them. Its coefficients belong to \(\{0,1\}\), its dimension is at most \(R+m\), and its right-hand side has polynomial bit length. Cramer’s rule gives polynomial-bit rational coordinates: the integer determinants have bit length bounded by a polynomial in \(R+m\), and clearing the rational right-hand-side denominators also requires only polynomially many bits.

Consequently, whenever an improvement exists, one exists with a polynomial-size list of rational coupling entries. A verifier checks bundle cardinalities, utility comparisons, all mass equations, and positive strict-improvement mass using exact rational arithmetic in polynomial time.

Together with the reduction, this establishes \(\mathrm{NP}\)-completeness. In particular, a polynomial-time algorithm in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\).

⟨structured verdict parsed — rendered above⟩

Verdict

The prover’s claim is proved. The argument establishes \(\mathrm{NP}\)-completeness for the exact continuous mass-flow and bundle-coupling problem in USER_TASK. I found no major or minor mathematical issues.

The decisive step is Section 5: its inequalities apply to arbitrary real splitting and force every weakly improving terminal bundle to attain its stated lower bound. Positive strict-improvement mass then certifies a partition.

Step-by-step verification

1. Terminal-measure characterization

This characterization is correct in both directions.

Each type’s terminal bundles have cardinality \(r_\theta\), since every occurrence of that type adds exactly one category absent from the current bundle. Consequently,
\[ \sum_{o\in O}C_o =\sum_{\theta\in\{A,B\}}r_\theta\alpha_\theta(2^O) =\frac{r_A+r_B}{2} =\frac m2. \]
There are \(m\) categories, each with capacity \(1/2\). Thus all terminal category capacities must be saturated.

For the converse, the prescribed paths add each terminal bundle’s categories at successive occurrences of its type. Superposition preserves mass conservation, and no path repeats a category. Consumption of any category is nondecreasing over positions and bounded by its terminal consumption, so terminal feasibility implies every intermediate capacity constraint.

This reasoning also covers \(r_\theta=0\): that type’s only possible terminal bundle is the empty bundle, and its mass stays there.

Assessment: Correct. The characterization uses precisely the flow rules in the task and introduces no additional picking requirement.

2. Source problem and construction

The even-total restriction of positive-integer \(\mathrm{PARTITION}\) is justified. Doubling every input integer preserves equality of the two partition sums and produces an even total. An originally odd-total instance remains negative after doubling.

The policy \(\Pi=AB^nA^n\) has length \(2n+1\), with
\[ r_A=n+1,\qquad r_B=n. \]
The category set has the same size. All valuations are nonnegative, including \(v_A(z)=K-1/2\), because \(K\ge1\).

The baseline obeys the policy, adds distinct categories within each type’s bundle, and consumes each category with exactly mass \(1/2\). Its utilities are correctly computed as \(K-1/2\) and \(2K\).

The attribution to the numerical gadget in Proposition 5 is consistent with the [cited full version](https://recherche.noiraudes.net/resources/papers/ECAI14-full.pdf). The continuous hardness claim is supported by the prover’s own subsequent argument, rather than inferred from the discrete theorem.

Assessment: Correct and within the required input restrictions.

3. Partition implies improvement

If a subset \(J\) sums to \(K\), positivity of the integers and total sum \(2K\) imply
\[ 1\le j=|J|\le n-1. \]
Therefore the requested dummy subset exists: its size \(n+1-j\) lies between \(2\) and \(n\).

The constructed bundles partition the category set. Their cardinalities are correctly computed:
\[ |S_A|=n+1,\qquad |S_B|=1+(n-j)+(j-1)=n. \]
Assigning mass \(1/2\) to each bundle saturates every category capacity and is feasible by Section 2.

The utilities are
\[ v_A(S_A)=K,\qquad v_B(S_B)=K+(K+1/2)=2K+1/2. \]
Both exceed their baseline utilities. Coupling each baseline atom to its corresponding alternative atom satisfies the required marginals and strictly improves positive mass.

Assessment: Correct.

4. Fractional improvement implies partition

This is the central soundness argument, and each step checks out.

Because each baseline terminal measure has a single atom, a weakly improving coupling requires every positive-mass alternative bundle to meet the corresponding baseline utility threshold. Normalization by \(P_\theta(S)=2\alpha_\theta(S)\) produces probability distributions.

For type \(A\), absence of \(z\) gives the integer threshold \(w(S)\ge K\); presence of \(z\) gives \(w(S)\ge0\). Hence
\[ W_A\ge K(1-x_A). \]

For type \(B\), absence of \(z\) gives \(w(S)\ge2K\). Presence of \(z\) gives
\[ w(S)\ge K-1/2, \]
which, by integrality, means \(w(S)\ge K\). Hence
\[ W_B\ge2K-Kx_B. \]

Normalized supply constraints yield
\[ x_A+x_B\le1,\qquad W_A+W_B\le2K. \]
The resulting chain is valid:
\[ 2K\ge W_A+W_B \ge3K-K(x_A+x_B) \ge2K. \]
Every inequality therefore holds with equality. Since \(K>0\), this also forces \(x_A+x_B=1\). The two separate expected lower bounds must both be attained.

The passage from expected equality to bundlewise equality is justified. There are finitely many bundles, every slack is nonnegative, and any positive-probability bundle with positive slack would make the expected slack positive.

The resulting table correctly identifies the utilities in all four cases. Strict improvement is possible only for an \(A\)-bundle without \(z\), or a \(B\)-bundle containing \(z\). Both cases force \(w(S)=K\). Such a positive-mass bundle exists whenever the coupling gives positive mass to strict improvement, and its good-category indices constitute a partition solution.

Assessment: Correct for arbitrary nonnegative real masses. No rationality or deterministic-allocation assumption enters this direction.

5. Encoding size

The construction has polynomial size under the specified encoding.

There are \(2n+1\) categories and policy positions. Computing \(K\) and encoding the half-integer valuations require polynomially many bits. The baseline has linearly many transitions; explicitly recording their bundle labels still requires only polynomial space.

Assessment: Correct. The reduction establishes \(\mathrm{NP}\)-hardness with fixed support size \(\tau=2\).

6. Membership in \(\mathrm{NP}\)

The certificate argument is sound.

Aggregating explicitly represented terminal baseline atoms yields polynomially many atoms and polynomial-bit rational masses. The coupling variables permit exactly those target bundles that have the required cardinality and weakly improve the source atom’s utility.

The baseline-atom equations impose the first coupling marginals. Summing coupling entries into target bundles defines the second marginals. The category equations enforce feasible terminal consumption. Equality rather than inequality is justified by Section 2’s saturation argument.

The strict-improvement objective counts precisely the coupling mass on strictly improving pairs. Since all variables are nonnegative, positive objective value is equivalent to the required positive strict-improvement mass.

The polytope is finite-dimensional, nonempty, closed, and bounded:

• There are finitely many candidate bundles.
• The baseline provides a feasible coupling.
• Each variable is bounded by its baseline atom’s mass.

Thus the stated linear objective attains its maximum at a vertex. If any improvement exists, the maximum is positive.

The support bound is also valid. At a vertex, positive-variable columns must be linearly independent; otherwise a sufficiently small perturbation in both directions preserves nonnegativity and the equations. Therefore at most \(R+m\) variables are positive, regardless of dependencies among the equality rows.

Selecting independent rows gives a nonsingular square system for those positive coordinates. Its matrix has entries in \(\{0,1\}\). For dimension \(k\le R+m\), determinant magnitudes are at most \(k!\), so their bit lengths are polynomial. Clearing the polynomially many rational right-hand-side denominators also uses polynomially many bits. The claimed polynomial-bit coordinate bound follows.

The resulting certificate lists polynomially many bundle labels and rational coupling masses. All listed checks, including strict positivity, use exact rational arithmetic in polynomial time.

Assessment: Correct. The exponential number of potential variables does not invalidate this existence-of-certificate argument.

Issues and repair feedback

No repair is required. The proof resolves the stated decision problem, including arbitrary real splitting, utility ties, explicit baseline encoding, and fixed support size.

The conclusion is \(\mathrm{NP}\)-completeness; a polynomial-time algorithm would therefore imply \(\mathrm{P}=\mathrm{NP}\).

⟨structured verdict parsed — rendered above⟩