Answer: Polynomial-time solvable for \(m=1\), with bit complexity \(O(\tau\log(\tau+1)L^2)\). The defined endpoint mechanism always returns the leftmost social-cost minimizer and is strategyproof under every rational clone expansion.
Theorem 1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateMechanism 1 is strategyproof and optimal for mini- mizing the social cost. Hence, when the agents only have lower thresholds, the social cost can in fact be minimized using a strategyproof mechanism. Next, we consider minimizing the maximum cost.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite rational support \(T\subseteq[0,1]\times[0,1)\) with masses \(\mu_{x,a}\ge0\) summing to \(1\), compute \(y\in[0,1]\) minimizing \(\mathrm{SC}_\mu(y)=\sum_{(x,a)\in T}\mu_{x,a}(|y-x|-a)_+/(1-a)\), and require the endpoint mechanism to be strategyproof under every rational clone expansion in which one clone may change only its reported location.
A society is given by its support: a nonempty list of \(\tau\) rational types \((x,a)\in[0,1]\times[0,1)\), each with positive binary rational mass \(\mu_{x,a}\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible types; \(L\) is the total input bit length. There is one facility, so \(m=1\); state running times in \(m,\tau,L\).
Thresholds are public and fixed; only locations may be misreported. Define \(c(y;x,a)=\max\{|y-x|-a,0\}/(1-a)\) and \(\mathrm{SC}_\mu(y)=\sum_{(x,a)}\mu_{x,a}c(y;x,a)\), for \(y\in[0,1]\). The computational problem is to output an exact rational minimizer.
Define the endpoint mechanism using \(B=\{0,1\}\cup(\{x-a,x+a:(x,a)\in T\}\cap[0,1])\): it outputs the smallest \(z\in B\) satisfying \(\sum_{x+a\le z}\mu_{x,a}/(1-a)\ge\sum_{x-a>z}\mu_{x,a}/(1-a)\).
For every positive integer \(N\) with all \(N\mu_{x,a}\) integral, a clone expansion has \(N\mu_{x,a}\) clones of type \((x,a)\), each of mass \(1/N\). A single clone may report any rational \(x'\in[0,1]\), keeping its threshold and mass fixed; aggregate the resulting reports before applying the mechanism. Strategyproofness means \(c(f(\mu);x,a)\le c(f(\mu');x,a)\) for every such deviation, evaluated at the clone's true type.
Is exact social-cost minimization for these support-encoded societies solvable in polynomial time, or is it NP-hard? Does the defined endpoint mechanism always output a minimizer and satisfy strategyproofness under every rational clone expansion?
For finite agent lists, the smallest-endpoint balance mechanism is strategyproof and minimizes social cost, and its finite candidate set gives a polynomial-time algorithm ([Zhou et al., 2023](https://www.ifaamas.org/Proceedings/aamas2023/pdfs/p2170.pdf)).
No result for exactly this support-encoded problem with the stated clone requirement was located in the literature search.
Exact social-cost minimization is polynomial-time solvable for \(m=1\). The defined endpoint mechanism returns the leftmost minimizer and is strategyproof under every rational clone expansion.
A direct implementation takes \(O(\tau\log(\tau+1)L^2)\) bit operations using schoolbook integer arithmetic. This bound uses the support size \(\tau\), without enumerating clones.
The finite-agent result appears as Mechanism 1 and Theorem 1 in [Zhou et al. (2023)](https://www.ifaamas.org/Proceedings/aamas2023/pdfs/p2170.pdf). The proof below independently establishes the stated support-encoded version, including boundary handling and the clone requirement.
Index the support by \(i\in\{1,\ldots,\tau\}\), and define
\(\ell_i=x_i-a_i,\qquad r_i=x_i+a_i,\qquad w_i=\mu_i/(1-a_i)>0.\)
Write \(u_+=\max\{u,0\}\). Since \(\ell_i\le r_i\), direct case analysis gives
\(\max\{|y-x_i|-a_i,0\}=(\ell_i-y)_++(y-r_i)_+.\)
Consequently, extending the same formula to real \(y\), the social cost is the convex, continuous, piecewise-linear function
\(F(y)=\sum_{i=1}^{\tau}w_i\bigl((\ell_i-y)_++(y-r_i)_+\bigr).\)
Its right derivative is
\(g(y)=F'_+(y)=\sum_{r_i\le y}w_i-\sum_{\ell_i>y}w_i.\)
Indeed, the right derivatives of \((\ell_i-y)_+\) and \((y-r_i)_+\) are respectively \(-1\) when \(y<\ell_i\) and \(1\) when \(y\ge r_i\), and are otherwise zero.
Thus \(g\) is nondecreasing and right-continuous. Its only possible changes occur at the endpoints \(\ell_i,r_i\). When \(a_i=0\), both endpoints coincide and the corresponding jump is \(2w_i\); the formula remains valid.
The mechanism’s balance condition is exactly \(g(z)\ge0\).
Let \(f\) be the mechanism’s output. First, this output exists: since \(\ell_i=x_i-a_i\le1\),
\(g(1)=\sum_{r_i\le1}w_i\ge0,\)
and \(1\in B\).
We claim that
\(g(t)<0\quad\text{for every }t\in[0,f),\qquad g(t)\ge0\quad\text{for every }t\in[f,1].\)
For the first assertion, choose the largest candidate \(b\in B\) satisfying \(b\le t\). It exists because \(0\in B\). There are no endpoints in \((b,t]\), so \(g(t)=g(b)\). Since \(b<f\), minimality of the selected candidate gives \(g(b)<0\).
The second assertion follows from \(g(f)\ge0\) and monotonicity of \(g\). In particular,
\(f=\min\{t\in[0,1]:g(t)\ge0\}.\)
Because \(F\) is continuous and piecewise linear, for \(u<v\) its change is the sum of its slopes times the lengths of the finitely many linear pieces, equivalently
\(F(v)-F(u)=\int_u^v g(t)\,dt.\)
If \(y<f\), all slopes on \([y,f)\) are strictly negative, hence \(F(f)<F(y)\). If \(y>f\), all slopes on \([f,y)\) are nonnegative, hence \(F(y)\ge F(f)\).
Therefore \(f\) minimizes social cost, and no point smaller than \(f\) is a minimizer. This proves that the mechanism returns the leftmost minimizer, including when the minimum is attained on an interval or at a boundary.
There are at most \(2\tau+2\) candidates. The following sweep computes \(f\).
Both kinds of endpoint contribute an increase of \(w_i\): crossing \(\ell_i\) removes a negative summand, while crossing \(r_i\) introduces a positive summand. Thus the sweep maintains exactly \(g(z)\). Section 2 proves its correctness.
For completeness, all arithmetic can be performed with integers of polynomial bit length. Write the input mass and threshold as
\(\mu_i=s_i/t_i,\qquad a_i=u_i/v_i.\)
Then
\(w_i=n_i/d_i,\qquad n_i=s_i v_i,\qquad d_i=t_i(v_i-u_i)>0.\)
The total bit length of these numerators and denominators is \(O(L)\). Set
\(D=\prod_{i=1}^{\tau}d_i,\qquad W_i=n_i(D/d_i).\)
The integer \(D\), every \(W_i\), and every sum of the \(W_i\) have \(O(L)\) bits: product bit lengths add, and summation contributes at most \(O(\log(\tau+1))\) additional bits, which is absorbed by \(O(L)\).
Replace the rational balance \(g\) by the integer balance
\(G(z)=\sum_{r_i\le z}W_i-\sum_{\ell_i>z}W_i=Dg(z).\)
Since \(D>0\), the signs agree exactly.
Constructing these integers costs \(O(\tau L^2)\) bit operations. Each rational endpoint has \(O(L)\) bits, and each exact endpoint comparison costs \(O(L^2)\). Sorting and sweeping therefore take
\(T(1,\tau,L)=O(\tau\log(\tau+1)L^2).\)
The output is a boundary or an input-derived endpoint, so its rational encoding also has \(O(L)\) bits. This establishes polynomial-time exact minimization for the specified \(m=1\) problem; no claim about larger \(m\) is needed.
Fix any permitted positive integer \(N\), and select one clone with true type \((x,a)\). Its mass is \(1/N\). Define
\(\ell=x-a,\qquad r=x+a,\qquad w=1/(N(1-a))>0.\)
Let \(H(t)\) denote the combined slope contribution of all other clones. The selected clone’s contribution is \(w\,s_x(t)\), where
\(s_x(t)=-1\text{ if }t<\ell,\quad s_x(t)=0\text{ if }\ell\le t<r,\quad s_x(t)=1\text{ if }t\ge r.\)
The middle interval is empty when \(a=0\). Hence the truthful balance is
\(g(t)=H(t)+w\,s_x(t).\)
After a report \(x'\in[0,1]\), the threshold and mass remain fixed, so the new balance is
\(\widetilde g(t)=H(t)+w\,s_{x'}(t).\)
Aggregation does not change either expression: identical reports simply have their masses added. Thus Section 2 applies to both aggregated societies. Write their outputs as \(y\) and \(\widetilde y\).
If \(\ell\le y\le r\), then \(c(y;x,a)=0\). All costs are nonnegative, so no report can improve it.
Suppose \(y<\ell\). Then \(s_x(y)=-1\), while \(s_{x'}(y)\ge-1\). Therefore
\(\widetilde g(y)\ge g(y)\ge0.\)
The minimum-crossing characterization from Section 2 implies \(\widetilde y\le y\). Both outcomes lie to the left of \(\ell\), and consequently
\(c(\widetilde y;x,a)=\frac{\ell-\widetilde y}{1-a}\ge\frac{\ell-y}{1-a}=c(y;x,a).\)
Suppose \(y>r\). For every \(t\in[r,y)\), the truthful clone contributes its largest possible slope, namely \(w\). Thus
\(\widetilde g(t)\le g(t)<0,\)
where strict negativity follows from Section 2 because \(t<y\).
Moreover, \(r\in[0,1]\), since \(0\le r<y\le1\). For every \(t\in[0,r)\), monotonicity gives
\(\widetilde g(t)\le\widetilde g(r)<0.\)
Hence \(\widetilde g(t)<0\) for every \(t\in[0,y)\). Its first nonnegative point must satisfy \(\widetilde y\ge y\). Therefore
\(c(\widetilde y;x,a)=\frac{\widetilde y-r}{1-a}\ge\frac{y-r}{1-a}=c(y;x,a).\)
These three cases exhaust all truthful outcomes and prove the required inequality for every clone and every rational location report. Since \(N\) was arbitrary, strategyproofness holds under every rational clone expansion.
⟨structured verdict parsed — rendered above⟩
The prover’s output resolves all parts of the task. The argument establishes polynomial-time exact minimization, correctness of the defined endpoint mechanism, and strategyproofness under every permitted rational clone expansion. I found no major or minor mathematical issues.
The assumptions \(a_i\in[0,1)\) and \(\mu_i>0\) ensure that \(w_i=\mu_i/(1-a_i)\) is defined and positive, and that \(\ell_i\le r_i\).
The identity
\(\max\{|y-x_i|-a_i,0\}=(\ell_i-y)_++(y-r_i)_+\)
is correct in each of the three regions separated by \(\ell_i\) and \(r_i\). It also holds when \(a_i=0\).
The right derivative formula
\(g(y)=\sum_{r_i\le y}w_i-\sum_{\ell_i>y}w_i\)
uses the correct endpoint inequalities. At \(\ell_i\), the negative contribution disappears; at \(r_i\), the positive contribution begins. Coincident endpoints contribute both changes, giving the stated jump \(2w_i\).
Convexity, continuity, piecewise linearity, monotonicity of \(g\), and right continuity of \(g\) all follow directly from the displayed hinge representation. No external theorem is needed here.
Since \(\ell_i\le1\), the negative sum in \(g(1)\) is empty. Thus \(g(1)\ge0\), and inclusion of \(1\) in \(B\) guarantees that the mechanism is defined.
For \(t<f\), the largest candidate \(b\le t\) exists because \(0\in B\). Every endpoint in \([0,1]\) belongs to \(B\), so there is no derivative change in \((b,t]\). Consequently, \(g(t)=g(b)<0\), as claimed.
Endpoints outside \([0,1]\) cause no problem: they cannot create a change between \(b\) and \(t\). Their slope contributions are already included in the formula for \(g\).
For \(t\ge f\), monotonicity gives \(g(t)\ge g(f)\ge0\). The resulting minimum-crossing characterization is therefore valid, including the boundary cases \(f=0\) and \(f=1\).
The integral identity is justified by continuity and the finite piecewise-linear decomposition of \(F\). Values of the derivative at the finitely many breakpoints do not affect the integral.
If \(y<f\), the interval has positive length and every linear piece before \(f\) has strictly negative slope. Hence \(F(f)<F(y)\). If \(y>f\), all slopes between \(f\) and \(y\) are nonnegative, so \(F(y)\ge F(f)\).
These comparisons establish both minimization and the asserted leftmost tie-breaking. Flat minimum intervals and boundary minima are covered explicitly.
The candidate bound \(2\tau+2\) is valid. Initializing at \(g(0)\) correctly accounts for endpoints at or outside the lower boundary. Subsequent endpoint updates have the stated signs, and processing every event at a candidate before checking the balance handles simultaneous endpoints correctly.
The sweep is understood in its standard sense: endpoint events are associated with their sorted coordinates and processed once. This supports the claimed sorting and sweep bound.
The arithmetic formulas
\(n_i=s_iv_i\), \(d_i=t_i(v_i-u_i)\), and \(W_i=n_i(D/d_i)\)
are correct, with \(d_i>0\) and \(D/d_i\) an integer. The total bit length of the factors is \(O(L)\), so \(D\), the scaled weights, and their sums have \(O(L)\) bits. The additional summation length \(O(\log(\tau+1))\) is absorbed by the total input length.
Schoolbook multiplication, exact division, and rational comparison therefore support the stated bound
\(T(1,\tau,L)=O(\tau\log(\tau+1)L^2)\).
The output is an exact rational boundary or endpoint with \(O(L)\) encoding length.
The running time is stated for the required value \(m=1\), and it uses support size rather than clone count.
For any permitted \(N\), the selected clone has positive weight \(1/(N(1-a))\). Keeping its threshold and mass fixed preserves this weight after its location report changes.
The expressions \(H(t)+ws_x(t)\) and \(H(t)+ws_{x'}(t)\) correctly isolate the only changing contribution. Aggregation preserves these expressions because contributions are linear in mass. The reported society remains a finite rational society with positive masses after zero-mass entries are omitted.
Thus the earlier mechanism characterization applies to both outcomes. The proof places no bound on \(N\) and does not require enumerating clones computationally.
The use of \(r\) in the last case is legitimate because \(0\le r<y\le1\). Zero thresholds, coincident endpoints, and outcomes exactly at a zero-cost endpoint are covered by the stated cases. Every permitted rational report is included.
The attribution to Mechanism 1 and Theorem 1 is accurate: the cited paper states strategyproofness and social-cost optimality for its finite-agent mechanism. [Zhou et al. (2023)](https://www.ifaamas.org/Proceedings/aamas2023/pdfs/p2170.pdf).
The support-encoded and clone-expansion conclusions are established independently in the submitted argument, so no unverified transfer from the finite-agent theorem is required. No additional clarification or repair is necessary.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.