d4-conf-wine-2021-0041 (d4-conf-wine-2021-0041)

Given \(k\ge3\), \(\eta>0\), and a rational finite-support location distribution \(\mu\) with \(N\mu_x\in\mathbb Z_{\ge0}\) and \(\sum_x\mu_x=1\), whose expanded \(N\)-resident profile is \((\sqrt{2}-\eta)\)-stable, does a deterministic anonymous strategyproof facility mechanism achieve an approximation ratio bounded in \(N,k\), when a resident's report moves mass \(\frac1N\) from \(x\) to \(y\)?

Fix integers \(k\ge3\) and \(N\ge k+1\), and \(0<\eta\le\sqrt2-1\); write \(\gamma=\sqrt2-\eta\).
A society is given by its support: the list of \(\tau\) real location types with positive binary rational masses \(\mu_x\), where \(\sum_x\mu_x=1\) and \(N\mu_x\in\mathbb Z_{\ge0}\). Here \(\tau\) is the support size, not the number of possible types; \(N\) is supplied explicitly.
Its expanded profile is the sorted list \(z_1\le\cdots\le z_N\) containing \(N\mu_x\) copies of each location. A clustering partitions this list into \(k\) nonempty consecutive blocks, each served at its left median; optimality minimizes total distance within the blocks.
The profile is \(\gamma\)-stable if its optimal clustering is unique and retains the same block boundaries uniquely after every perturbation satisfying \(z'_1=z_1\) and \((z_{i+1}-z_i)/\gamma\le z'_{i+1}-z'_i\le z_{i+1}-z_i\).
A deterministic anonymous mechanism without payments assigns each stable society a sorted tuple \(M(\mu)\in\mathbb R^k\). Put \(d(x,c)=\min_j|x-c_j|\), \(C(\mu,c)=\sum_x\mu_xd(x,c)\), and \(\operatorname{OPT}(\mu)=\min_{c\in\mathbb R^k}C(\mu,c)\).
Strategyproofness requires \(d(x,M(\mu))\le d(x,M(\mu'))\) whenever \(\mu'=\mu+N^{-1}(\delta_y-\delta_x)\) is also stable, for every supported \(x\) and every \(y\in\mathbb R\); \(\delta_t\) denotes unit mass at \(t\).
Does such a mechanism achieve \(C(\mu,M(\mu))\le\rho(N,k)\operatorname{OPT}(\mu)\) on every stable society for some finite computable bound \(\rho(N,k)\ge1\), or is every such mechanism unbounded?
Known discrete result: deterministic anonymous strategyproof mechanisms have unbounded approximation ratio for these stability factors, even when only stable deviations are considered. [Verified source](https://arxiv.org/html/2107.11977v2#S6.SS2).
The specified mass model is exactly the anonymous finite-resident model in support representation, so this target is already settled rather than open.

Conclusion and the theorem used

Every deterministic anonymous mechanism satisfying the stated strategyproofness condition has an unbounded approximation ratio. In particular, no finite computable bound \(\rho(N,k)\) exists.

We use the established discrete impossibility theorem: for every fixed \(k\ge3\), \(n\ge k+1\), and \(1\le\gamma<\sqrt2\), deterministic anonymous strategyproof mechanisms on \(\gamma\)-stable profiles of \(n\) residents have unbounded approximation ratio. The proof requires strategyproofness only for deviations between stable profiles. This is [Fotakis–Patsilinakos, Theorem 6.1 and Section 6.1](https://arxiv.org/html/2107.11977v2#S6.SS2).

The remaining proof verifies that this theorem applies exactly to the representation and incentive condition in the question.

1. Support representation preserves the domain

For a labeled resident profile \(a=(a_1,\ldots,a_N)\), define its empirical society by

\(\displaystyle \mu_a=\frac1N\sum_{i=1}^{N}\delta_{a_i}.\)

At each supported location \(x\), its mass is \(\mu_a(x)=m_x/N\), where \(m_x\) is the positive integer number of residents at \(x\). Thus its masses satisfy all the stipulated conditions. Here, consistently with the question’s stated finite-resident interpretation, rational masses are encoded using binary numerators and denominators.

Conversely, every admissible society has integer multiplicities \(m_x=N\mu_x\), and

\(\displaystyle \sum_xm_x=N\sum_x\mu_x=N.\)

Expanding these multiplicities recovers a resident profile uniquely up to permutation. Therefore admissible societies correspond bijectively to anonymous resident profiles with exactly \(N\) residents.

The stability conditions also agree. Both models sort the expanded profile, use consecutive blocks with left-median facilities, and require the same unique optimal block boundaries after every allowed contraction of consecutive gaps. These are precisely the conventions in [the source’s Section 2 and Definition 1](https://arxiv.org/html/2107.11977v2#S3).

In particular, zero gaps cause no discrepancy: their allowed perturbed lengths remain zero, so repeated locations remain repeated.

2. Individual deviations and strategyproofness are preserved

Suppose a mechanism \(M\) as in the question exists. Define a resident mechanism on stable profiles by

\(\displaystyle F(a)=M(\mu_a).\)

This mechanism is deterministic. It is anonymous because permuting the residents leaves \(\mu_a\) unchanged.

Now fix a resident \(i\), whose true location is \(x=a_i\), and let \(a^{i\to y}\) be the profile obtained by changing only that resident’s report to \(y\). Its empirical society satisfies

\(\displaystyle \mu_{a^{i\to y}}=\mu_a+\frac1N(\delta_y-\delta_x).\)

If both resident profiles are stable, their empirical societies are stable by Section 1. The assumed strategyproofness of \(M\) consequently gives

\(\displaystyle d(a_i,F(a))=d(x,M(\mu_a))\le d(x,M(\mu_{a^{i\to y}}))=d(a_i,F(a^{i\to y})).\)

Thus \(F\) is strategyproof for every individual deviation between stable resident profiles. The inequality evaluates both outcomes at the resident’s true location, exactly as required by the discrete theorem.

If the deviation removes the last resident at \(x\), that location simply disappears from the support. This changes no part of the correspondence.

3. Approximation guarantees are preserved

For any facility tuple \(c\), write the resident total cost as

\(\displaystyle S(a,c)=\sum_{i=1}^{N}d(a_i,c).\)

Grouping equal locations yields

\(\displaystyle S(a,c)=\sum_xm_xd(x,c)=N\sum_x\mu_a(x)d(x,c)=NC(\mu_a,c).\)

Minimizing over the same set of facility tuples therefore gives

\(\displaystyle S^*(a):=\min_{c\in\mathbb R^k}S(a,c)=N\operatorname{OPT}(\mu_a).\)

Suppose \(M\) satisfied the proposed guarantee with a finite value \(R=\rho(N,k)\). On every stable resident profile,

\(\displaystyle S(a,F(a))=NC(\mu_a,M(\mu_a))\le NR\operatorname{OPT}(\mu_a)=R S^*(a).\)

Hence \(F\) would have a finite approximation guarantee on the discrete stable domain. This argument also covers zero-optimum instances without dividing by the optimum.

4. Applying the impossibility theorem

The parameter assumptions imply

\(\displaystyle 1\le\gamma=\sqrt2-\eta<\sqrt2.\)

Together with \(k\ge3\) and \(N\ge k+1\), these verify the parameter hypotheses of the discrete theorem, with \(n=N\). Sections 1–3 verify its domain, anonymity, strategyproofness, and approximation hypotheses.

The theorem therefore contradicts the existence of \(F\), and consequently of \(M\) with the proposed finite guarantee. The obstruction already holds for fixed \(N\) and \(k\); encoding the same resident multiset by its support does not alter it.

⟨structured verdict parsed — rendered above⟩

The output proves the claimed impossibility under the finite-resident interpretation explicitly specified in USER_TASK. No major or minor mathematical gaps were found.

• The cited theorem applies. Theorem 6.1 covers deterministic anonymous strategyproof mechanisms with any fixed number of residents satisfying \(n\ge k+1\), for stability factors below \(\sqrt2\). Section 6.1 explicitly confirms that its argument uses only stable instances and stable deviations. Thus the prover does not incorrectly import unrestricted strategyproofness. [Theorem 6.1 and its supporting discussion](https://arxiv.org/html/2107.11977v2#S6.SS2).

• The mass representation is correct. Every resident profile produces positive supported masses \(m_x/N\). Conversely, integrality of \(N\mu_x\) and normalization give positive integer multiplicities totaling \(N\). These constructions are inverse up to resident permutation. The prover explicitly interprets “binary rational” as rational numbers with binary-encoded numerators and denominators, consistently with the task’s stated interpretation.

• Stability is preserved exactly. The source uses consecutive clusters, left medians, the same anchored contraction inequalities, and uniqueness before and after every permitted perturbation. It identifies corresponding clusterings by their block sizes. These agree with the task’s boundary convention. Zero gaps remain zero, as the prover states. [Definitions and stability conventions](https://arxiv.org/html/2107.11977v2#S3).

• The mechanism transfer preserves incentives. The definition \(F(a)=M(\mu_a)\) preserves determinism, anonymity, and sorted facility outputs. Changing one resident’s report produces exactly the signed measure update written in the proof. Both costs in the strategyproofness inequality are evaluated at that resident’s true location. Removing the last resident at a location causes no domain problem.

• The cost calculation is exact. Grouping residents by location gives \(S(a,c)=NC(\mu_a,c)\). Minimizing over the same facility tuples gives \(S^*(a)=N\operatorname{OPT}(\mu_a)\). Therefore any finite approximation guarantee transfers unchanged. The proof correctly avoids division by the optimum, so zero-optimum instances introduce no exception.

• The parameter and quantifier checks pass. The assumptions on \(\eta\) imply \(1\le\gamma<\sqrt2\), including the endpoint \(\gamma=1\). The remaining hypotheses hold with \(n=N\). For fixed \(N,k\), a proposed finite value \(\rho(N,k)\) would contradict the cited impossibility. Consequently, the conclusion excludes every finite bound, and hence every finite computable bound.

Repair feedback: None required. The argument resolves the assigned mechanism question. Its result is an approximation impossibility under incentive constraints; it does not classify computational complexity.

⟨structured verdict parsed — rendered above⟩