Answer: Every deterministic strategyproof mechanism has unbounded worst-case welfare approximation ratio.
Theorem 3.1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateFor any $k \geq 2$, the approximation ratio of any deterministic strategyproof mechanism is unbounded, even when the preferences of the agents are known.
statement extracted from the paper’s text layer; consult the paper for the exact wording
For fixed \(k\ge2\), given finite candidate sites \(C\subseteq[0,1]\), an integer \(N\), and a society of types \(t=(x_t,\alpha_t)\) with rational masses \(\mu_t=n_t/N\), can any deterministic direct mechanism have a finite worst-case approximation ratio when approvals are known and a resident may misreport their position, changing the reported masses by \(1/N\)?
Fix \(k\geq2\) facilities. An instance consists of an integer \(N\geq2\), a nonempty finite set \(C\subseteq[0,1]\cap\mathbb Q\) of \(m\) candidate sites, and types \(t=(x_t,\alpha_t)\), where \(x_t\in[0,1]\cap\mathbb Q\) and \(\alpha_t\in\{0,1\}^k\).
A society is given by its support: the list of the \(\tau\) types with positive mass, each with its mass as a binary rational. Here \(\mu_t=n_t/N\), \(n_t\in\mathbb Z_{>0}\), and \(\sum_t n_t=N\); \(\tau\) is the support size, not the number of possible types. Let \(L\) be the total input bit length; state any running times in \(m,\tau,L,N,k\).
A deterministic direct mechanism \(M(N,C,\mu)\) chooses exactly one outcome \((j,c)\in\{1,\ldots,k\}\times C\), without payments. Type \(t\)'s utility is \(u_t(j,c)=\alpha_{t,j}(1-|x_t-c|)\), and welfare is \(W_\mu(j,c)=\sum_t\mu_tu_t(j,c)\).
Approvals are known. One resident of a supported type \(t\) may report any \(y\in[0,1]\cap\mathbb Q\), producing \(\mu'=\mu-N^{-1}\delta_{(x_t,\alpha_t)}+N^{-1}\delta_{(y,\alpha_t)}\), with identical types merged and zero masses removed.
Strategyproofness requires \(u_t(M(N,C,\mu))\geq u_t(M(N,C,\mu'))\) for every such deviation, evaluated at the resident's true type. Deterministic tie decisions are part of the mechanism.
A finite worst-case approximation ratio means that some finite \(R_k\) satisfies \(\max_{j,c}W_\mu(j,c)\leq R_kW_\mu(M(N,C,\mu))\) for every admissible instance, uniformly over \(N,C,\mu\).
Does a deterministic strategyproof mechanism with a finite worst-case approximation ratio exist for this support-encoded society model, or must every such mechanism have unbounded ratio?
For finite-agent societies, deterministic strategyproof mechanisms have unbounded welfare approximation ratio even with known approvals; randomized strategyproof mechanisms achieve the tight ratio \(k\). [Verified source](https://arxiv.org/html/2505.03391v1). No separate theorem for the support encoding was verified.
Every deterministic strategyproof mechanism has unbounded worst-case welfare approximation ratio. This holds even with \(N=2\), support size \(\tau=2\), and two distinct candidate sites.
Singleton candidate sets already give the obstruction in [Theorem 3.1 of the cited paper](https://arxiv.org/html/2505.03391v1). The following proof establishes impossibility directly in the support-encoded model, while also allowing a genuine choice between candidate sites.
Fix \(k\geq2\). Suppose, for contradiction, that a deterministic strategyproof mechanism \(M\) satisfies the required approximation inequality with some finite constant \(R_k\).
Choose an integer \(q>\max\{2,2R_k\}\), and set \(\varepsilon=1/q\). Let \(e_j\in\{0,1\}^k\) denote the approval vector approving only facility \(j\).
Consider the admissible instance with \(N=2\), candidate set \(C=\{1-\varepsilon,1\}\), and society
\(\mu=\tfrac12\delta_{(\varepsilon,e_1)}+\tfrac12\delta_{(\varepsilon,e_2)}\).
All coordinates and masses are rational, and the two supported types each represent exactly one resident.
Because \(0<\varepsilon<1/2\), a resident at \(\varepsilon\) obtains utility \(2\varepsilon\) from an approved facility at \(1-\varepsilon\), and utility \(\varepsilon\) from an approved facility at \(1\). Consequently,
\(\max_{j,c}W_\mu(j,c)=\varepsilon>0\).
Choosing any facility outside \(\{1,2\}\) would give welfare zero, contradicting the assumed finite approximation bound. Therefore \(M\) selects some facility \(a\in\{1,2\}\). Let \(b\) be the other facility. These labels refer to the mechanism’s actual deterministic decision, including its tie decision; no symmetry assumption is used.
The resident approving only \(b\) receives utility zero.
Let that resident report location \(1\). The resulting society is exactly the permitted one-resident deviation:
\(\mu'=\tfrac12\delta_{(\varepsilon,e_a)}+\tfrac12\delta_{(1,e_b)}\).
If \(M(N,C,\mu')\) selected facility \(b\), the deviating resident, evaluated at its true location \(\varepsilon\), would obtain either \(2\varepsilon\) or \(\varepsilon\), according to the chosen candidate site. Both are strictly positive.
This would improve its utility from zero, violating strategyproofness. Hence \(M(N,C,\mu')\) cannot select facility \(b\).
At society \(\mu'\), selecting facility \(a\) gives welfare at most
\(\tfrac12(2\varepsilon)=\varepsilon\).
Every facility outside \(\{a,b\}\) gives welfare zero. Since facility \(b\) is excluded, we obtain
\(W_{\mu'}(M(N,C,\mu'))\leq\varepsilon\).
In contrast, outcome \((b,1)\) gives welfare \(\tfrac12\): its sole approving resident is located at \(1\). This is optimal, because each facility is approved by at most one resident, whose utility is at most \(1\). Thus
\(\max_{j,c}W_{\mu'}(j,c)=\tfrac12\).
The claimed approximation inequality would imply
\(\tfrac12\leq R_k W_{\mu'}(M(N,C,\mu'))\leq R_k\varepsilon=R_k/q<\tfrac12\),
a contradiction.
Both societies have \(m=2\), \(\tau=2\), and \(N=2\). Their total input length is \(L=O(k+\log q)\) under ordinary binary rational encoding. One may choose \(q\) to be a power of two, so all coordinates are dyadic rationals as well.
The proof uses precisely a mass change of \(1/N\), with approvals unchanged. It requires neither an expansion into a large population nor any assumption about running time. Support encoding therefore does not remove the deterministic impossibility.
⟨structured verdict parsed — rendered above⟩
The prover resolves the target correctly. The argument establishes unbounded approximation ratio directly in the support-encoded model, even with \(N=2\), \(m=2\), and \(\tau=2\). No mathematical gaps or false steps were found.
The assumed constant \(R_k\) is uniform over all admissible instances, so choosing \(q\) after fixing \(R_k\) is legitimate. An integer \(q>\max\{2,2R_k\}\) exists, and \(\varepsilon=1/q\) is rational with \(0<\varepsilon<1/2\).
The proof implicitly uses \(R_k\geq0\) when multiplying a welfare upper bound by \(R_k\). This follows immediately from the assumed approximation inequality on any instance with positive optimal welfare: the mechanism’s welfare is nonnegative and cannot exceed the optimum, so a valid approximation constant must satisfy \(R_k\geq1\). This creates no gap.
Both candidate sites lie in \([0,1]\cap\mathbb Q\) and are distinct. The two supported types are distinct because \(e_1\neq e_2\), despite sharing a location. Their masses are positive binary rationals, each corresponds to one resident, and their counts sum to \(N=2\).
The construction is valid for every fixed \(k\geq2\); facilities beyond the first two simply have no approving residents.
Since \(\varepsilon<1/2\),
\[
1-|\varepsilon-(1-\varepsilon)|=2\varepsilon,
\qquad
1-|\varepsilon-1|=\varepsilon.
\]
Each of facilities \(1\) and \(2\) has exactly one approving resident of mass \(1/2\). Its welfare is therefore \(\varepsilon\) at \(1-\varepsilon\) and \(\varepsilon/2\) at \(1\). Every other facility has welfare zero. Consequently, the stated optimum \(\varepsilon>0\) is correct.
A finite approximation bound excludes every zero-welfare outcome here. Thus the selected facility belongs to \(\{1,2\}\). Defining \(a\) from the mechanism’s actual selection and \(b\) as the other facility handles every deterministic tie decision without assuming symmetry.
The resident of type \((\varepsilon,e_b)\) has mass \(1/2=1/N\). Reporting \(1\) removes that supported type and introduces \((1,e_b)\), leaving the other resident unchanged. The displayed society \(\mu'\) is exactly the deviation specified in the task. It remains admissible with two supported types and unchanged approvals.
Initially, the deviating resident receives zero because it approves only \(b\), while the mechanism selects \(a\).
If the mechanism selected \(b\) after the report, its utility evaluated at its true location \(\varepsilon\) would be \(2\varepsilon\) or \(\varepsilon\). Both are strictly positive. Hence either candidate site would produce a profitable deviation. Strategyproofness therefore excludes facility \(b\) at \(\mu'\), exactly as claimed.
At \(\mu'\), facility \(a\) still has only the resident at \(\varepsilon\) approving it, so its welfare is at most \(\varepsilon\). Facilities outside \(\{a,b\}\) have welfare zero. Excluding \(b\) therefore gives the stated mechanism-welfare upper bound.
Outcome \((b,1)\) has welfare \(1/2\). Every facility has at most one approving resident, and individual utility is at most \(1\), so no outcome exceeds \(1/2\). The claimed optimum is exact.
The approximation inequality then implies
\[
\frac12
\leq R_k W_{\mu'}(M(N,C,\mu'))
\leq \frac{R_k}{q}
<\frac12.
\]
The final strict inequality follows from \(q>2R_k\). This contradiction proves the claimed impossibility.
The bound \(L=O(k+\log q)\) is correct under ordinary binary rational encoding: the approval vectors require \(O(k)\) bits, and the coordinates require \(O(\log q)\) bits. Taking \(q\) to be a sufficiently large power of two preserves every inequality and makes the coordinates dyadic.
The ancillary citation is accurate: [Theorem 3.1 and its proof](https://arxiv.org/html/2505.03391v1) state the deterministic impossibility with known approvals and use a singleton candidate set. The submitted proof independently establishes the support-encoded result, so no transfer theorem is needed.
No running-time claim is made or required. The result concerns the incompatibility of strategyproofness and bounded approximation, not computational hardness.
Required clarification: None. The proof is verifiable as written.
⟨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.