d4-conf-aaai-2016-0339 (d4-conf-aaai-2016-0339)

Given paired and altruist types \(P\cup A\), rational masses \(\mu_t\), type-to-type compatibility and edge weights, and fixed cycle and chain caps \(\ell,k\), compute a maximum-weight allocation of legal cycles and chains. A template may repeat a type label when separate participants fill its positions; for template \(q\), choose mass \(x_q\geq 0\) to maximize \(\sum_q W_qx_q\) subject to \(\sum_q a_{tq}x_q\leq\mu_t\) for every type \(t\). Does this mass-allocation problem admit a polynomial-time algorithm in the number of types and the input bit length for fixed caps?

A society is given by its support: disjoint sets \(P\) of patient–donor pair types and \(A\) of altruist donor types, each listed with positive binary-rational mass \(\mu_t\), with \(\sum_t\mu_t=1\). Let \(m=|P|\), \(\tau=|P\cup A|\); \(\tau\) counts supported types, not all possible types. Let \(L\) be the total input bit length.
Input compatibility is \(E\subseteq(P\cup A)\times P\), with signed binary-rational edge weights \(w_{uv}\), and fixed integer caps \(\ell,k\geq2\). Compatibility and weights depend only on types; a diagonal compatibility entry permits trades between distinct participants of that type.
A legal cycle template has \(r\) paired positions, where \(2\leq r\leq\ell\), and compatible edges between successive positions, including the closing edge. A legal chain template starts with one altruist position followed by paired positions, has between \(2\) and \(k\) positions including the altruist, and has compatible edges between successive positions; its final paired donor need not donate.
Type labels may repeat, but separate participants occupy all positions. For every legal template \(q\), let \(a_{tq}\) count its positions of type \(t\), and let \(W_q\) sum its edge weights with multiplicity. An allocation chooses real masses \(x_q\geq0\), with \(\sum_q a_{tq}x_q\leq\mu_t\) for every type; unused mass is allowed. Its weight is \(\sum_q W_qx_q\).

For every fixed pair of caps \(\ell,k\), is computing a maximum-weight mass allocation polynomial-time solvable in \(m,\tau,L\), or is it NP-hard?

The discrete cycle-pricing algorithm returns a negative-weight legal cycle whenever one exists; this is a pricing result, not a polynomial-time clearing algorithm ([source](https://www.cs.cmu.edu/~sandholm/capped-chain.aaai16.pdf)).
Later work corrects its chain extension and proves discrete chain pricing NP-complete when the chain cap is an input parameter ([source](https://arxiv.org/pdf/1606.00117)). No treatment of exactly the fixed-cap mass-allocation problem above was located in the search.

Polynomial-time solvability for fixed caps

Theorem. For every fixed pair of integers \(\ell,k\geq2\), a maximum-weight mass allocation can be computed exactly in time polynomial in \(m,\tau,L\).

The proof enumerates all legal type templates and solves the resulting rational linear program. It applies to the stated model, including repeated type labels, diagonal compatibility, signed weights, and unused mass.

1. Enumerating all legal templates

Write \(h=|A|=\tau-m\) and \(c=\max\{\ell,k\}\).

For each \(r\in\{2,\ldots,\ell\}\), enumerate every ordered tuple
\[ (p_1,\ldots,p_r)\in P^r. \]
Retain it precisely when
\[ (p_i,p_{i+1})\in E\quad(1\leq i<r), \qquad (p_r,p_1)\in E. \]
These tests are exactly the compatibility conditions for a legal cycle template. There are \(m^r\) candidate tuples of length \(r\).

For each \(s\in\{2,\ldots,k\}\), enumerate every ordered tuple
\[ (a,p_1,\ldots,p_{s-1})\in A\times P^{s-1}. \]
Retain it precisely when
\[ (a,p_1)\in E, \qquad (p_i,p_{i+1})\in E\quad(1\leq i<s-1). \]
These are exactly the conditions for a legal chain template. In particular, we impose no outgoing-edge condition on its final paired position. There are \(hm^{s-1}\) candidates of length \(s\).

Repeated labels are retained because the task explicitly permits them. For example, if \((p,p)\in E\), the tuple \((p,p)\) represents a legal two-position cycle with consumption \(a_{pq}=2\) and weight \(W_q=2w_{pp}\). Its two positions represent distinct participants of type \(p\).

Consequently, the number \(N\) of retained ordered templates satisfies
\[ N\leq \sum_{r=2}^{\ell}m^r+ h\sum_{s=2}^{k}m^{s-1}. \]
If \(m\geq1\), this gives
\[ N\leq(\ell-1)m^\ell+(k-1)hm^{k-1}. \]
Because the caps are fixed, this is polynomial in \(m,\tau\). If \(m=0\), there are no legal templates, and the zero allocation is optimal.

If cycle templates are identified up to cyclic rotation, the enumeration may contain multiple representations of one template. This causes no difficulty: those representations have identical consumption vectors and weights, so their variables can be replaced by their sum. Conversely, any mass assigned to that template can be assigned to one representation. Thus keeping or merging these duplicates preserves the optimum.

2. The linear program is exactly the allocation problem

Let \(Q\) be the enumerated legal templates. For each \(q\in Q\), compute its position-count vector \((a_{tq})_t\) and its edge-weight sum \(W_q\), counting every occurrence.

Consider
\[ \begin{aligned} \text{maximize}\quad& \sum_{q\in Q}W_qx_q,\\ \text{subject to}\quad& \sum_{q\in Q}a_{tq}x_q\leq\mu_t &&\text{for every }t\in P\cup A,\\ &x_q\geq0 &&\text{for every }q\in Q. \end{aligned} \]

Every feasible allocation gives a feasible vector for this program, with the same weight, because every legal template appears in the enumeration. Conversely, every feasible vector specifies nonnegative masses on legal templates satisfying all type-capacity constraints, and hence is an allocation under the task’s definition.

Therefore, the program’s optimal value and optimal allocations coincide exactly with those of the stated problem.

3. An optimum exists

The zero vector is feasible, so the feasible region is nonempty.

Let \(r_q=\sum_t a_{tq}\) be the number of positions in template \(q\). Every legal template has \(r_q\geq2\). Summing all capacity constraints and using \(\sum_t\mu_t=1\) gives
\[ 2\sum_{q\in Q}x_q \leq \sum_{q\in Q}r_qx_q = \sum_t\sum_{q\in Q}a_{tq}x_q \leq1. \]
Thus every feasible coordinate lies in \([0,1/2]\). The feasible region is closed, since it is defined by finitely many non-strict linear inequalities, and bounded. It is therefore compact. The linear objective is continuous, so it attains a maximum.

This argument also covers signed weights. No positivity assumption on the objective coefficients is needed.

4. Encoding size and exact computation

There are \(N\) variables and \(\tau\) capacity constraints, together with nonnegativity constraints.

Every incidence coefficient is an integer satisfying
\[ 0\leq a_{tq}\leq c. \]
Its encoding length is therefore bounded by a constant depending only on the fixed caps.

Each \(W_q\) is the sum of at most \(c\) input edge weights, with multiplicity. To bound its encoding length explicitly, write these occurrences as \(b_i/d_i\), with \(d_i>0\). Then
\[ \sum_{i=1}^{j}\frac{b_i}{d_i} = \frac{\displaystyle\sum_{i=1}^{j}b_i \prod_{v\ne i}d_v} {\displaystyle\prod_{i=1}^{j}d_i}, \qquad j\leq c. \]
Each input numerator and denominator has at most \(L\) bits. The displayed numerator and denominator consequently have \(O(cL+\log c)\) bits. Reducing the fraction cannot increase this bound.

The right-hand sides are the input rational masses. Hence even a dense encoding of the entire program has length polynomial in \(m,\tau,L\). Enumeration, compatibility checking, and coefficient construction also take polynomial time: each candidate has at most \(c\) positions and requires only a fixed number of compatibility tests and rational additions.

We now apply the standard polynomial-time theorem for rational linear programming: an explicitly encoded linear program with rational coefficients can be solved in time polynomial in its total binary encoding length; when it is feasible and has a finite optimum, an exact rational optimal solution can be returned.

All hypotheses hold here: the program is explicitly constructed, its coefficients are rational, its encoding length is polynomial, and Section 3 proves feasibility and attainment of a finite optimum. The returned rational coordinates specify an exact maximum-weight mass allocation.

The polynomial’s degree may depend on \(\ell,k\). The conclusion is therefore for every fixed pair of caps, as requested.

5. Relation to the cited pricing results

The earlier paper treats discrete clearing through integer programming and branch-and-price; its cycle-pricing result does not by itself establish polynomial-time clearing. [Fast Optimal Clearing of Capped-Chain Barter Exchanges](https://www.cs.cmu.edu/~sandholm/capped-chain.aaai16.pdf).

The later hardness proof concerns chains that use each vertex at most once and sets the chain cap to a quantity growing with the Hamiltonian-path instance. Its correction and hardness result therefore do not contradict the fixed-cap enumeration above. [Hardness of the Pricing Problem for Chains in Barter Exchanges](https://arxiv.org/pdf/1606.00117).

For the present problem, polynomial solvability follows directly from the polynomial number of fixed-cap templates and the continuous allocation variables.

⟨structured verdict parsed — rendered above⟩

The prover resolves the assigned problem correctly: for every fixed pair of caps, an exact maximum-weight mass allocation is computable in polynomial time. I found no mathematical errors, unjustified applications of theorems, or missing steps requiring clarification.

• Enumeration is complete and legal. Every cycle is represented by a tuple in \(P^r\), with exactly the required successive and closing compatibility checks. Every chain is represented by a tuple in \(A\times P^{s-1}\), with exactly the required successive checks. The chain length includes the altruist, and no outgoing edge is required from the final paired position.

Repeated labels and diagonal compatibility are handled correctly. In particular, the two-position cycle \((p,p)\) consumes two positions of type \(p\) and counts the diagonal edge twice. This agrees with the task’s explicit definition; distinct participants need not have distinct type labels.

• The template-count bound is correct. The candidate count is

\[ \sum_{r=2}^{\ell}m^r+h\sum_{s=2}^{k}m^{s-1}. \]
For \(m\geq1\), each cycle term is at most \(m^\ell\), and each chain term is at most \(hm^{k-1}\), giving the stated bound. Its degree depends only on the fixed caps, so it is polynomial in the requested parameters.

The \(m=0\) case is correctly separated: every permitted template requires a paired position, so none exists. The argument also accommodates \(h=0\) and instances with no compatible templates.

• Duplicate cycle representations preserve the problem. Cyclic rotations have identical position counts and edge-weight sums, including when labels repeat. Summing the corresponding variables preserves every capacity constraint and the objective. Conversely, assigning the merged mass to any one representation preserves feasibility and weight. Thus duplicate representations do not introduce additional allocation capacity.

• The LP is exactly the specified allocation model. Its coefficients count all position occurrences, and its objective counts all edge occurrences. Its nonnegative real variables and capacity inequalities match the task’s definition directly. Both directions of the claimed correspondence are justified, subject to the already established handling of duplicate representations.

No integrality condition or additional participant-level realization requirement is present in the task. Consequently, neither is missing from this formulation.

• Existence and finiteness of an optimum are established. The zero vector is feasible. Summing the capacity constraints yields

\[ 2\sum_qx_q\leq\sum_qr_qx_q\leq1, \]
because every template consumes at least two positions. Nonnegativity therefore bounds every coordinate by \(1/2\). The finite-dimensional feasible region is closed and bounded, hence compact, and the continuous objective attains a finite maximum. Signed weights do not affect this reasoning.

• The encoding-size calculation is valid. Each incidence coefficient is an integer between zero and the fixed constant \(c\). A cycle has at most \(c\) edge occurrences, and a chain has at most \(c-1\), so the claimed bound of at most \(c\) summands is valid.

In the displayed rational-sum calculation, multiplying at most \(c\) denominators produces \(O(cL)\) bits. Each numerator summand has the same order of bit length; adding at most \(c\) signed summands adds at most \(O(\log c)\) bits. Repeated occurrences cause no exception. Fraction reduction cannot increase the bound.

Thus the explicit LP, including a dense incidence matrix and nonnegativity constraints, has polynomial encoding length. Candidate generation, compatibility lookup, and coefficient arithmetic also admit polynomial-time implementation.

• The exact rational LP theorem is applied correctly. The prover states the needed theorem with rational input, binary encoding length, and exact rational optimal output. The constructed program satisfies its hypotheses: it is explicitly encoded, rational, polynomial in size, feasible, and has a finite attained optimum. This standard theorem establishes exact computation, rather than merely approximation. No additional hypothesis is needed here.

• The discussion of pricing results is accurate and does not substitute for the proof. The earlier paper describes discrete clearing using integer programming and branch-and-price. [Fast Optimal Clearing of Capped-Chain Barter Exchanges](https://www.cs.cmu.edu/~sandholm/capped-chain.aaai16.pdf).

The later paper defines negative chains using each vertex at most once and, in its Hamiltonian-path reduction, sets the cap to the instance size. It also identifies errors in the earlier chain-pricing algorithms. These statements support the prover’s explanation that this hardness result does not contradict fixed-cap enumeration for the specified continuous allocation problem. [Hardness of the Pricing Problem for Chains in Barter Exchanges](https://arxiv.org/pdf/1606.00117).

No repair or additional clarification is required. The proof establishes polynomial-time solvability for each fixed pair of caps; it makes no uniform polynomial-time claim when the caps vary with the input.

⟨structured verdict parsed — rendered above⟩