Strategyproof facility location for concave cost functions (d4-conf-sigecom-2013-0025)

Given \(k\), finitely many location types \(T\) with positions \(z_t\), a rational distribution \(\mu\in\Delta(T)\), and a common nondecreasing concave cost function \(c\) with \(c(0)=0\), construct a randomized \(k\)-facility mechanism \(\mathcal M(\mu,c)\) that is group-strategyproof against feasible mass transfers \(\delta_{tu}\ge 0\), and guarantees \(\mathbb E[\max_{t:\mu_t>0} c(\min_j|z_t-Y_j|)]\le 2\,\mathrm{MC}^*_{\mu}\) and \(U_t(\mu)\le\mathrm{MC}^*_{\mu}\) for every supported type \(t\), while characterising its weighted social-cost guarantee.

A society is given by its support: the list of the \(\tau\) distinct location types with positive masses \(\mu_t\), each mass a binary rational, with \(\sum_t\mu_t=1\). Locations \(z_t\) are binary rationals on the real line; \(\tau\) counts supported types, not possible reports.
Fix \(k\geq1\). The public common cost function \(c:\mathbb R_{\geq0}\to\mathbb R_{\geq0}\) is continuous, nondecreasing and concave, with \(c(0)=0\). A mechanism without payments maps every finitely supported reported society to a distribution over \(Y\in\mathbb R^k\); coincident facilities are allowed.
Write \(d(z,Y)=\min_{1\leq j\leq k}|z-Y_j|\), \(U_t(\nu)=\mathbb E_{Y\sim\mathcal M(\nu,c)}[c(d(z_t,Y))]\), and \(\mathrm{MC}^*_{\mu}=\min_{Y\in\mathbb R^k}\max_{t\in T}c(d(z_t,Y))\).
Define \(\mathrm{SC}_{\mu}(\mathcal M)=\sum_{t\in T}\mu_tU_t(\mu)\) and \(\mathrm{SC}^*_{\mu}=\min_{Y\in\mathbb R^k}\sum_{t\in T}\mu_tc(d(z_t,Y))\).
A deviation chooses a finite set of rational report locations, possibly outside the original support, and rational transfers \(\delta_{tu}\geq0\) to locations \(u\neq z_t\), with \(r_t=\sum_u\delta_{tu}\leq\mu_t\) and \(\sum_tr_t>0\). The reported society is \(\nu=\mu-\sum_tr_t\mathbf e_{z_t}+\sum_{t,u}\delta_{tu}\mathbf e_u\), where \(\mathbf e_z\) is unit mass at \(z\); zero masses are omitted.
Weak group-strategyproofness means that every such deviation has some \(t\) with \(r_t>0\) satisfying \(U_t(\nu)\geq U_t(\mu)\); costs are evaluated at true locations, per unit mass, in expectation.
For computational claims, use rational piecewise-linear costs with \(m\) explicitly listed pieces, including the final unbounded piece; let \(L\) be the total input bit length and state running times in \(m,\tau,L,k\). The existence question covers all continuous costs specified above.

Does a weakly group-strategyproof randomized mechanism exist for every such society and cost function with \(\mathbb E[\max_{t\in T}c(d(z_t,Y))]\leq2\mathrm{MC}^*_{\mu}\) and \(U_t(\mu)\leq\mathrm{MC}^*_{\mu}\) for every \(t\in T\), or are these requirements incompatible?
If such a mechanism exists, what worst-case weighted social-cost approximation guarantee does its construction provide relative to \(\mathrm{SC}^*_{\mu}\)?

For finite societies of \(n\geq k+1\) agents, Equal Cost is weakly group-strategyproof, gives maximum-cost factor \(2\), social-cost factor \(n\), and expected individual cost at most the optimal maximum cost. [Verified theorem](https://arxiv.org/html/1305.3333).
No result settling exactly this rational mass-transfer model was located in the literature search.

Result

The requirements are compatible. A version of Equal Cost that depends only on the reported support is weakly group-strategyproof under the stated rational mass transfers and satisfies both requested maximum-cost guarantees.

Its weighted social-cost guarantee is
\( \mathrm{SC}_{\mu}(\mathcal M) \leq \frac{1}{\mu_{\min}}\mathrm{SC}^{*}_{\mu}, \qquad \mu_{\min}=\min_{t\in T}\mu_t. \)
This factor is asymptotically sharp for this construction. In particular, there is no bound depending only on \(\tau\) and \(k\).

The proof below uses the finite-agent Equal Cost theorem supplied in the question. The extension to rational mass transfers is proved explicitly.

1. A support-based construction

Fix the common cost function \(c\). Equal Cost has the following support-based form:

• Find the minimum length \(\ell\) for which the reported locations can be covered by at most \(k\) intervals of length \(\ell\).
• Choose a symmetric random variable \(X_{\ell,c}\) supported on \([0,\ell]\) whose expected connection cost is constant throughout that interval.
• Place facilities in successive covering intervals using alternating reflections of the same sample of \(X_{\ell,c}\).

These are the ingredients of the [Equal Cost construction and finite-agent theorem](https://arxiv.org/html/1305.3333).

Here are precise conventions that make the construction independent of multiplicities. Sort the distinct reported locations. For a candidate length, greedily start an interval at the leftmost uncovered location. At the minimum feasible length, this produces disjoint intervals
\( I_i=[\alpha_i,\alpha_i+\ell],\quad 1\leq i\leq q,\quad q\leq k. \)
If necessary, append intervals to the right, setting
\( \alpha_{q+s}=\alpha_q+s(\ell+1), \quad 1\leq s\leq k-q. \)
This gives an optimal covering by exactly \(k\) disjoint intervals. The finite-agent proof applies to this choice: it uses disjointness and optimality of the covering.

Write \(C_c(\ell)\) for the constant satisfying
\( \mathbb E[c(|x-X_{\ell,c}|)]=C_c(\ell) \quad\text{for every }x\in[0,\ell]. \)
Use the facility locations
\( Y_i= \begin{cases} \alpha_i+X_{\ell,c},&i\text{ odd},\\ \alpha_i+\ell-X_{\ell,c},&i\text{ even}. \end{cases} \)

All choices depend on the support and \(c\), and are fixed consistently across inputs. In particular, replicating agents at existing locations does not change the output distribution.

For completeness, the assigned facility is always a closest facility for every point in its interval. Indeed, the midpoint between two consecutive facilities is
\( \frac{Y_i+Y_{i+1}}2 =\frac{\alpha_i+\alpha_{i+1}+\ell}{2}, \)
independently of the sample. Since \(\alpha_{i+1}\geq\alpha_i+\ell\), this midpoint lies in the gap between the intervals. Consequently, every reported type has expected cost exactly \(C_c(\ell)\).

If \(\ell=0\), take \(X_{\ell,c}=0\); all supported locations receive a facility and have zero cost.

2. Rational transfers are finite-agent coalition deviations

Consider any society \(\mu\) and any permitted deviation \((\delta_{tu})\), with reported society \(\nu\).

Because the masses and transfers are rational and only finitely many transfers are nonzero, there is an integer \(N\geq k+1\) such that all quantities
\( N\mu_t \quad\text{and}\quad N\delta_{tu} \)
are integers.

Construct a finite society of \(N\) labelled agents, placing exactly \(N\mu_t\) agents at \(z_t\). For each transfer \(\delta_{tu}\), select \(N\delta_{tu}\) of those agents to report \(u\).

These selections can be disjoint for each true type, because
\( \sum_u N\delta_{tu}=Nr_t\leq N\mu_t. \)
The coalition is nonempty because \(\sum_t r_t>0\). Every selected agent changes its report, since transfers to \(u=z_t\) are excluded.

The truthful agent profile has support exactly \(\operatorname{supp}(\mu)\), and the deviated profile has support exactly \(\operatorname{supp}(\nu)\). Support invariance therefore gives exactly the same outcome distributions as the mass mechanism at \(\mu\) and \(\nu\).

Apply the supplied finite-agent weak group-strategyproofness theorem. Its hypotheses hold:

• there are \(N\geq k+1\) agents;
• they have the same public admissible cost function;
• their reports form a finite coalition deviation;
• coincident true locations are allowed.

Some selected agent does not strictly improve. If its true location is \(z_t\), then \(r_t>0\), and its expected costs are precisely \(U_t(\mu)\) and \(U_t(\nu)\). Thus
\( U_t(\nu)\geq U_t(\mu). \)

This proves weak group-strategyproofness for the stated mass-transfer model. The common denominator is used only in the proof; the mechanism does not enumerate these agents.

3. Maximum cost and individual cost

Let \(\ell\) be the minimum covering length for the truthful support. Then
\( \mathrm{MC}^{*}_{\mu}=c(\ell/2). \)

To justify this identity, interval midpoints achieve maximum distance at most \(\ell/2\). Conversely, facilities achieving maximum distance \(r\) cover the support by \(k\) intervals of length \(2r\), so \(\ell\leq 2r\). Greedy covering gives the same minimum feasible length whether overlapping intervals are initially permitted or not. Monotonicity of \(c\) now gives the identity.

Symmetry implies \(\mathbb E[X_{\ell,c}]=\ell/2\). Evaluating the constant expected cost at the left endpoint and applying concavity gives
\( U_t(\mu) =C_c(\ell) =\mathbb E[c(X_{\ell,c})] \leq c(\mathbb E[X_{\ell,c}]) =c(\ell/2) =\mathrm{MC}^{*}_{\mu}. \)

For every realization, each supported point has its assigned facility at distance at most \(\ell\). Hence
\( \max_{t\in T}c(d(z_t,Y)) \leq c(\ell) \leq 2c(\ell/2) =2\mathrm{MC}^{*}_{\mu}. \)
The second inequality follows from concavity and \(c(0)=0\). Taking expectations proves the requested maximum-cost bound.

4. The weighted social-cost bound

Because the masses sum to one, the individual-cost bound gives
\( \mathrm{SC}_{\mu}(\mathcal M) =\sum_t\mu_tU_t(\mu) \leq\mathrm{MC}^{*}_{\mu}. \)

For every facility configuration \(Y\), choose a type attaining its maximum cost. Its mass is at least \(\mu_{\min}\), so
\( \sum_t\mu_t c(d(z_t,Y)) \geq \mu_{\min}\max_t c(d(z_t,Y)). \)
Taking minima over \(Y\) yields
\( \mathrm{SC}^{*}_{\mu} \geq\mu_{\min}\mathrm{MC}^{*}_{\mu}. \)

Combining these inequalities proves
\( \mathrm{SC}_{\mu}(\mathcal M) \leq\frac{1}{\mu_{\min}}\mathrm{SC}^{*}_{\mu}. \)
This remains valid when the optimum is zero; no division by the optimum is needed.

Sharpness and absence of a support-count bound

Fix \(k\), an integer \(R\geq2\), and a positive rational \(\varepsilon<1/(k+1)\). Use the cost
\( c(d)=\min\{d,1\} \)
and the \(k+1\) locations
\( 0,\ R,\ 3R,\ 6R,\ldots,3(k-1)R, \)
where the last list is empty when \(k=1\). Assign mass \(1-k\varepsilon\) to \(0\), and mass \(\varepsilon\) to every other location. Thus \(\mu_{\min}=\varepsilon\).

The minimum covering length is \(R\): a shorter interval covers at most one location, whereas length \(R\) covers \(0,R\) together and the remaining locations separately.

For this cost and length, the Equal Cost law is uniform on
\( \{0,1,\ldots,R\}. \)
Indeed, for \(x\in[j,j+1]\), the costs to the two adjacent integers sum to one, and each of the other \(R-1\) integers contributes one. Therefore
\( \frac1{R+1}\sum_{i=0}^{R}\min\{|x-i|,1\} =\frac{R}{R+1}. \)
The uniqueness argument in the next section identifies this equalizing law with the construction. Consequently,
\( \mathrm{SC}_{\mu}(\mathcal M)=\frac{R}{R+1}. \)

Meanwhile,
\( \mathrm{SC}^{*}_{\mu}=\varepsilon. \)
For the upper bound, put facilities at every location except \(R\). For the lower bound, all distinct locations are separated by at least two. One facility can therefore give cost strictly below one to at most one supported type. With \(k\) facilities and \(k+1\) types, some type incurs cost one, contributing at least \(\varepsilon\).

Thus the approximation ratio is
\( \frac{R}{(R+1)\varepsilon}, \)
which approaches \(1/\varepsilon=1/\mu_{\min}\) as \(R\) increases. Letting \(\varepsilon\) decrease also proves unboundedness with fixed \(\tau=k+1\).

5. Exact implementation for rational piecewise-linear costs

An exact grid implementation gives the verified running-time bound
\( 2^{O(L)}\operatorname{poly}(m,\tau,k,L). \)
This is an exponential-time bound in the binary input length, not a polynomial-time claim.

The covering stage uses \(O(\tau^2\log\tau+k)\) rational arithmetic operations: enumerate and sort the location differences, binary-search feasibility, and perform greedy covering.

For the distribution stage, let \(Q\) be the product of the denominators of all locations and all finite cost breakpoints. Set
\( h=1/Q,\qquad B=\ell Q. \)
Then \(B\) is an integer, all breakpoints are grid points, and
\( B\leq2^{O(L)}. \)

The cases \(\ell=0\) and \(c\equiv0\) are immediate. Otherwise, write \(a_r\) for the slope of \(c\) on \((rh,(r+1)h)\), for \(0\leq r<B\). Concavity gives
\( a_0>0,\qquad a_0\geq a_1\geq\cdots\geq a_{B-1}\geq0. \)
Define
\( w_s=a_{s-1}-a_s\geq0,\qquad 1\leq s<B. \)

Set unnormalized endpoint weights \(p_0=p_B=1\), and solve
\( 2a_0p_i -\sum_{\substack{0\leq j\leq B\\j\ne i}} w_{|i-j|}p_j =0, \qquad 1\leq i<B. \)

Existence, nonnegativity, and equalization

Let \(A\) be the matrix on the interior variables. It has diagonal \(2a_0\) and off-diagonal entries \(-w_{|i-j|}\).

The following maximum principle proves both nonsingularity and nonnegativity of its inverse. Extend an interior vector \(v\) by zero outside the interior indices, and suppose \(Av\geq0\). If \(v_i=M<0\) is a minimum, then
\( 2a_0M \geq\sum_{s=1}^{B-1}w_s(v_{i-s}+v_{i+s}) \geq2M\sum_{s=1}^{B-1}w_s \geq2a_0M. \)
Here \(\sum_s w_s=a_0-a_{B-1}\leq a_0\).

If that sum is strictly below \(a_0\), the last inequality is strict, a contradiction. Otherwise, equality forces every neighbor reached by a positive \(w_s\) to have the same negative minimum. Repeated jumps eventually reach a zero boundary or exterior value, again a contradiction. Thus \(v\geq0\).

Applying this principle to both signs of a null vector proves that \(A\) is nonsingular. The endpoint contributions give a nonnegative right-hand side, so the solved interior weights are nonnegative. Reflection symmetry gives \(p_i=p_{B-i}\). Normalize the weights to sum to one.

For the resulting potential
\( F(x)=\sum_{j=0}^{B}p_jc(|x-jh|), \)
its derivative on grid cell \(r\) is
\( D_r=\sum_{j=0}^{r}a_{r-j}p_j -\sum_{j=r+1}^{B}a_{j-r-1}p_j. \)
The defining equations give \(D_i-D_{i-1}=0\). Reflection symmetry gives \(D_{B-1-r}=-D_r\). Therefore every \(D_r=0\), and continuity makes \(F\) constant throughout \([0,\ell]\).

Uniqueness

For a nonzero admissible piecewise-linear cost, write
\( c(d)=a d+\sum_j\gamma_j\min\{d,b_j\}, \)
where \(a,\gamma_j\geq0\), each \(b_j>0\), and at least one coefficient is positive.

Suppose two probability measures equalize cost on \([0,\ell]\). Let their difference be \(\sigma\), and put
\( H(s)=\sigma((-\infty,s]). \)
Their potential difference is constant, and \(\sigma\) has total mass zero. Hence its energy is zero:
\( \iint c(|x-y|)\,d\sigma(x)\,d\sigma(y)=0. \)

Direct indicator-function integration gives
\( \iint |x-y|\,d\sigma(x)\,d\sigma(y) =-2\int H(s)^2\,ds \)
and
\( \iint\min\{|x-y|,b\}\,d\sigma(x)\,d\sigma(y) =-\int[H(s)-H(s-b)]^2\,ds. \)
For the second identity, use that \((b-|x-y|)_+\) is the overlap length of \([x,x+b]\) and \([y,y+b]\).

Every term is nonpositive. A positive linear coefficient forces \(H=0\) almost everywhere. A positive capped-term coefficient forces \(H\) to be periodic almost everywhere with a positive period; because \(H\) vanishes outside a bounded interval, this also forces \(H=0\) almost everywhere. Right continuity then implies \(\sigma=0\).

Thus the computed law is unique and agrees with the Equal Cost law, independently of grid refinement.

The slope table, rational linear system, and explicit outcome distribution can all be computed in time polynomial in \(m,\tau,k,L,B\). Since \(B\leq2^{O(L)}\), the stated exponential bound follows. No expansion of the rational masses into agents is required.

⟨structured verdict parsed — rendered above⟩

Assessment: proved with minor gaps. The construction resolves the existence question using the finite-agent theorem supplied in USER_TASK. The rational-transfer reduction is sound, both maximum-cost guarantees follow, and the weighted social-cost factor is asymptotically sharp for this construction. Two statements need minor clarification; neither requires new mathematics.

• Construction and applicability of Equal Cost

Greedy covering starts each interval at the leftmost uncovered supported location. Since the intervals are closed, the next starting point lies strictly beyond the preceding interval’s right endpoint. Thus the intervals are disjoint.

Appending intervals with starting points \(\alpha_q+s(\ell+1)\) preserves disjointness and coverage. Their presence does not change the minimum feasible covering length.

The cited mechanism permits an optimal disjoint covering and then uses alternating reflections of the same random sample. Its strategyproofness argument depends on optimality and the interval geometry, rather than agent multiplicities or a particular covering tie-break. The proposed conventions therefore fit that construction. The source also defines profiles with coincident locations and evaluates randomized deviations through expected connection costs. [Equal Cost construction, Theorem 3.1, and Section 3.3](https://arxiv.org/html/1305.3333).

For general continuous admissible costs, the output relies on the verified finite-agent Equal Cost theorem supplied by the task. This is an authorized premise, rather than an independently proved continuous equalization result.

The midpoint calculation is correct for both consecutive parity patterns:
\(\frac{Y_i+Y_{i+1}}2=\frac{\alpha_i+\alpha_{i+1}+\ell}{2}\).
This midpoint lies between the two intervals. Facilities are ordered, so checking consecutive facilities suffices to establish that every point in an interval has its assigned facility among its closest facilities.

Consequently, every supported type has expected cost \(C_c(\ell)\). The case \(\ell=0\) also works: there are at most \(k\) supported locations, each receives a facility, and every true cost is zero.

• Reduction from rational transfers to a finite-agent deviation

This is the central extension, and it is correct.

There are finitely many rational masses and transfers. A common denominator, multiplied further if necessary, gives an integer \(N\geq k+1\) for which every \(N\mu_t\) and \(N\delta_{tu}\) is integral.

The inequality \(\sum_uN\delta_{tu}\leq N\mu_t\) ensures that the selected agents can be disjoint within each true type. The coalition is nonempty because the total transferred mass is positive, and every selected agent changes its report because transfers to its own true location are excluded.

The replicated truthful and deviated profiles have exactly the supports of \(\mu\) and \(\nu\), respectively. This remains true when transfers enter previously occupied locations or completely remove an original type.

Because the construction ignores multiplicities, its outcome distributions coincide with those for the replicated profiles. The finite-agent theorem then supplies a selected agent whose expected true-location cost does not decrease. Its true type satisfies \(r_t>0\), giving precisely the required inequality \(U_t(\nu)\geq U_t(\mu)\).

The denominator may depend on the deviation. That is permissible: the argument verifies each deviation separately and does not use replication as an implementation procedure.

• Optimal maximum cost and individual guarantee

The identity \(\mathrm{MC}^*_\mu=c(\ell/2)\) is justified. Interval midpoints give maximum distance at most \(\ell/2\). Conversely, any configuration with maximum distance \(r\) yields a covering by intervals of length \(2r\), so \(r\geq\ell/2\). Monotonicity transfers this distance comparison to costs.

Strict monotonicity is unnecessary; flat portions of \(c\) do not invalidate the argument.

Symmetry and bounded support give \(\mathbb E[X_{\ell,c}]=\ell/2\). Evaluating equalization at the endpoint and applying Jensen’s inequality for the concave function \(c\) therefore proves
\(U_t(\mu)=C_c(\ell)\leq c(\ell/2)=\mathrm{MC}^*_\mu\).

• Expected maximum-cost guarantee

For every realization, every supported location is within distance \(\ell\) of its assigned facility. Hence its nearest-facility cost is at most \(c(\ell)\).

Concavity and \(c(0)=0\) give \(c(\ell)\leq2c(\ell/2)\). Thus the argument establishes the requested bound even pointwise, before taking expectations.

Zero-optimum cases are handled without dividing by the optimum.

• Weighted social-cost guarantee

Summing the individual guarantee against masses totaling one gives
\(\mathrm{SC}_\mu(\mathcal M)\leq\mathrm{MC}^*_\mu\).

For each configuration, a type attaining maximum cost has mass at least \(\mu_{\min}\). Therefore
\(\sum_t\mu_tc(d(z_t,Y))\geq\mu_{\min}\max_tc(d(z_t,Y))\).
Taking minima preserves the claimed inequality
\(\mathrm{SC}^*_\mu\geq\mu_{\min}\mathrm{MC}^*_\mu\).

Combining the two inequalities proves the stated factor \(1/\mu_{\min}\), including when the optimum is zero.

• Sharpness example

The example has \(k+1\) locations, positive rational masses totaling one, and minimum mass \(\varepsilon\). Its minimum covering length is \(R\): shorter intervals cover at most one location, while an interval of length \(R\) covers the first pair.

For each integer \(j\) with \(0\leq j<R\) and each \(x\in[j,j+1]\), the costs to the adjacent integers sum to one. Each of the remaining \(R-1\) integers contributes one. The uniform law consequently equalizes cost at \(R/(R+1)\).

The social optimum calculation is also correct. Omitting the location \(R\) gives cost \(\varepsilon\). Conversely, distinct locations are separated by at least two, so one facility can provide cost strictly below one to at most one type. Some type must therefore incur cost one, contributing at least \(\varepsilon\).

The ratio \(R/((R+1)\varepsilon)\) approaches \(1/\varepsilon\), and becomes unbounded as \(\varepsilon\) decreases with \(k\) and \(\tau=k+1\) fixed.

Minor issue — scope of the introductory claim. “There is no bound depending only on \(\tau\) and \(k\)” needs the qualifier “for this construction.” The example establishes that scope, as the final JSON correctly states; it does not establish an impossibility for every eligible mechanism.

• Grid implementation

The grid scaling is valid: location differences and finite breakpoints become integer multiples of \(h=1/Q\), and \(B=\ell Q\) is integral. The binary encoding bounds both the denominator product and location magnitudes exponentially in \(L\), giving \(B\leq2^{O(L)}\).

For a nonzero admissible piecewise-linear cost, the initial slope is positive and subsequent slopes are nonnegative and nonincreasing. The stated weights \(w_s\) are therefore nonnegative.

The maximum-principle inequality has the correct direction. If \(\sum_sw_s<a_0\), a negative minimum produces a strict contradiction. In the equality case, some \(w_s\) is positive; repeatedly following that jump eventually leaves the finite interior index set and reaches a zero exterior value. This contradicts equality at the negative minimum.

Applying the principle to both signs of a null vector proves nonsingularity. A nonnegative right-hand side gives nonnegative interior weights. Reflection invariance and uniqueness give symmetric weights, and normalization is legitimate because the endpoint weights are positive.

The derivative formula checks out. Subtracting consecutive derivatives gives exactly the defining interior equations. All cell derivatives are therefore equal; reflection makes them negatives of their reflected counterparts, forcing them to vanish. Continuity then gives equalization on the whole interval.

When \(B=1\), there are no interior equations; the endpoint weights and reflection argument still work.

• Uniqueness and bit complexity

Minor issue — omitted support restriction. The uniqueness statement must explicitly restrict both probability measures to \([0,\ell]\). This is already the construction’s intended domain, but it is necessary for the energy argument.

Without that restriction, the literal statement is false. For \(c(d)=d\) and \(\ell=1\), both \((\delta_0+\delta_1)/2\) and \((\delta_{-1}+\delta_2)/2\) equalize cost on \([0,1]\), but they are different measures. Constancy only on that interval does not justify integrating the potential against mass outside it.

With the intended support restriction, the energy argument is sound. Both displayed identities have the correct signs and constants. Nonpositive summands cannot cancel; a positive linear coefficient forces \(H=0\) almost everywhere, and a positive capped coefficient forces almost-everywhere periodicity. Bounded support excludes a nonzero periodic \(H\). Right continuity then identifies the signed measure as zero.

The runtime claim is defensible as an exact distribution-construction bound. The matrix dimension is polynomial in \(B\), its rational entries have bit lengths polynomial in the input length, and exact rational solving has bit complexity polynomial in those quantities. Explicit outcomes introduce an additional polynomial dependence on \(k\). The resulting exponential bound does not establish polynomial-time solvability or hardness.

Minimum requested revisions: qualify the support-count impossibility statement as applying to this construction, and explicitly state the support restriction in the uniqueness paragraph. No major blocking issue was found.

⟨structured verdict parsed — rendered above⟩