d4-conf-ecai-2024-0120 (d4-conf-ecai-2024-0120)

For each \(N\), let a society be a rational distribution \(\mu\) over finitely many locations \(x\in[0,1]\), with \(N\mu_x\in\mathbb{Z}_{\ge 0}\). Among deterministic rule families \(F_N\) that choose one facility location and remain strategyproof when a resident reports \(r\) instead of \(x\), changing the society to \(\mu+N^{-1}(\delta_r-\delta_x)\), determine the limiting Pareto frontier of worst-case approximation ratios for maximum distance and minimum utility as \(N\to\infty\). Does the pair \((2,3/2)\) remain optimal?

A society is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational; \(\tau\) is the support size, not the number of possible types. Here types are locations in \([0,1]\), masses sum to \(1\), and there is one facility, \(m=1\).
For each integer \(N\geq1\), let \(\mathcal S_N\) contain these societies satisfying \(N\mu_x\in\mathbb Z_{\geq0}\). A deterministic rule \(F_N:\mathcal S_N\to[0,1]\) depends only on the distribution, hence is anonymous. Locations and reports may be real; for algorithmic claims use binary rational locations and state running times in \(m,\tau,L,\log N\), where \(L\) is the total input bit length.
A resident at \(x\) has utility \(1-|x-y|\) from facility location \(y\). Require strategyproofness: \(|x-F_N(\mu)|\leq|x-F_N(\mu+N^{-1}(\delta_r-\delta_x))|\) for every \(\mu\in\mathcal S_N\), occupied \(x\), and report \(r\in[0,1]\), where \(\delta_z\) is unit mass at \(z\).
Define \(D(\mu,y)=\max_{x\in\operatorname{supp}\mu}|x-y|\), \(U(\mu,y)=1-D(\mu,y)\), \(D^*(\mu)=\min_{y\in[0,1]}D(\mu,y)\), and \(U^*(\mu)=\max_{y\in[0,1]}U(\mu,y)\).
Let \(R_D(F_N)=\sup_{\mu\in\mathcal S_N}D(\mu,F_N(\mu))/D^*(\mu)\) and \(R_U(F_N)=\sup_{\mu\in\mathcal S_N}U^*(\mu)/U(\mu,F_N(\mu))\); set \(0/0=1\) and positive-over-zero ratios to \(+\infty\).
Let \(\mathcal A\subseteq[1,+\infty]^2\) consist of pairs \((a,b)\) for which a strategyproof family satisfies \(\limsup_{N\to\infty}R_D(F_N)\leq a\) and \(\limsup_{N\to\infty}R_U(F_N)\leq b\). Its limiting Pareto frontier is the coordinatewise minimal part of \(\overline{\mathcal A}\), with closure in the extended-real product topology; impose no consistency or continuity between different \(N\).
Target. What is this limiting Pareto frontier? Does \((2,3/2)\) remain Pareto optimal, or can an asymptotic guarantee improve either coordinate without worsening the other?
Nearest known results. For finite populations, MIDORNEAREST places the facility at \(1/2\) when it lies between the extreme occupied locations, and otherwise at the occupied location nearest \(1/2\); it simultaneously achieves ratios \((2,3/2)\), and each coordinate is individually optimal among deterministic strategyproof mechanisms. [Source](https://cgi.cse.unsw.edu.au/~twalsh/wecai24.pdf)
No result explicitly determining the limiting frontier under the stated distribution and resident-report model was located in the literature search.

Result

The limiting Pareto frontier is exactly \(\{(2,3/2)\}\). More precisely,
\[ \mathcal A=[2,+\infty]\times[3/2,+\infty]. \]
Thus neither coordinate of \((2,3/2)\) can be improved asymptotically, even if the other coordinate is unrestricted.

We prove the lower bounds directly in the resident-report model. The achieving rule is MIDORNEAREST, as identified in [Walsh, Theorem 1](https://cgi.cse.unsw.edu.au/~twalsh/wecai24.pdf); we also verify its strategyproofness and guarantees here.

1. Optimal values and an outcome-preservation lemma

For a society \(\mu\), write \(\ell=\min\operatorname{supp}\mu\), \(h=\max\operatorname{supp}\mu\), and \(w=h-\ell\). For every facility location \(z\),
\[ D(\mu,z)=\max\{|\ell-z|,|h-z|\}. \]
The triangle inequality gives \(w\leq|\ell-z|+|h-z|\leq2D(\mu,z)\). The midpoint \(z=(\ell+h)/2\) attains equality. Consequently,
\[ D^*(\mu)=w/2,\qquad U^*(\mu)=1-w/2. \]

Lemma. Fix \(N\) and a strategyproof rule \(F_N\). If \(F_N(\mu)=y\), moving one resident from any occupied location \(x\) to \(y\) preserves the outcome.

Proof. Let \(\nu=\mu+N^{-1}(\delta_y-\delta_x)\). If \(x=y\), the conclusion is immediate. Otherwise, \(\nu\) has a resident at \(y\), and that resident can report \(x\), returning the distribution to \(\mu\). Strategyproofness at \(\nu\) therefore gives
\[ |y-F_N(\nu)|\leq|y-F_N(\mu)|=0. \]
Hence \(F_N(\nu)=y\). Applying this argument successively permits any finite sequence of resident moves to the same outcome \(y\). No coalition-strategyproofness assumption is needed. \(\square\)

2. Lower bounds for every population size

Fix \(N\geq2\) and an arbitrary strategyproof rule \(F_N\). Begin with
\[ \mu_0=N^{-1}\delta_0+(N-1)N^{-1}\delta_1, \qquad y=F_N(\mu_0). \]

If \(y\geq1/2\), successively move all residents at \(1\) to \(y\). The lemma shows that the final society \(\nu\) still has outcome \(y\), and its support is \(\{0,y\}\).

If \(y<1/2\), move the resident at \(0\) to \(y\). Again the outcome remains \(y\), and the support is \(\{y,1\}\).

In either case, the facility is an endpoint of the occupied interval, whose width is
\[ s=\max\{y,1-y\}\geq1/2. \]
Both support points have positive mass, and every intermediate society has masses that are integer multiples of \(N^{-1}\). The possibly real report \(y\) is permitted by the hypotheses.

At the final society,
\[ D(\nu,F_N(\nu))=s,\qquad D^*(\nu)=s/2, \]
so the distance ratio is exactly \(2\).

For utility,
\[ U(\nu,F_N(\nu))=1-s,\qquad U^*(\nu)=1-s/2. \]
If \(s=1\), the utility ratio is \(+\infty\). Otherwise,
\[ \frac{1-s/2}{1-s}-\frac32 =\frac{s-1/2}{1-s}\geq0. \]
Thus the same two-type witness proves
\[ R_D(F_N)\geq2,\qquad R_U(F_N)\geq3/2 \quad\text{for every }N\geq2. \]

These inequalities hold separately for each rule. Therefore every strategyproof family, without any consistency between population sizes, satisfies
\[ \limsup_{N\to\infty}R_D(F_N)\geq2,\qquad \limsup_{N\to\infty}R_U(F_N)\geq3/2. \]

3. A family attaining both bounds

For every \(N\), define
\[ F_N(\mu)=\min\{h,\max\{\ell,1/2\}\}. \]
This projects \(1/2\) onto the occupied interval \([\ell,h]\). The formula depends only on the support and is therefore anonymous.

Strategyproofness

For \(N=1\), the rule returns the sole resident’s report, so truthful reporting gives distance zero.

For \(N\geq2\), fix the reports of all residents except one. Let \(a\) and \(b\) be the minimum and maximum of those fixed reports, and let \(t\) be the remaining resident’s report.

There are three exhaustive cases:

• If \(a\leq1/2\leq b\), the outcome is always \(1/2\).
• If \(b<1/2\), the outcome is \(\min\{1/2,\max\{b,t\}\}\), the projection of \(t\) onto \([b,1/2]\).
• If \(a>1/2\), the outcome is \(\min\{a,\max\{1/2,t\}\}\), the projection of \(t\) onto \([1/2,a]\).

In the constant case, reporting cannot change utility. In either projection case, every possible outcome lies in a fixed closed interval, and truthful reporting selects the point of that interval closest to the resident’s true location. No alternative report can give a smaller distance. This proves the required resident-report strategyproofness.

Approximation guarantees

Let \(d=D(\mu,F_N(\mu))\). The outcome lies in \([\ell,h]\), so \(d\leq w\). If \(w>0\), this gives
\[ \frac{D(\mu,F_N(\mu))}{D^*(\mu)} =\frac{d}{w/2}\leq2. \]
If \(w=0\), the outcome is the sole occupied location, and the stipulated distance ratio is \(1\).

We also have \(d\leq1/2\). Indeed, when the occupied interval contains \(1/2\), the outcome is \(1/2\). When the interval lies entirely to one side of \(1/2\), its width is at most \(1/2\), and the outcome is its endpoint nearest \(1/2\).

Combining \(d\leq w\) with \(2d\leq1\) gives \(3d\leq1+w\). Therefore
\[ 1-\frac w2\leq\frac32(1-d). \]
Since \(1-d\geq1/2>0\), division yields
\[ \frac{U^*(\mu)}{U(\mu,F_N(\mu))} =\frac{1-w/2}{1-d}\leq\frac32. \]

For every \(N\geq2\), the society \(N^{-1}\delta_0+(N-1)N^{-1}\delta_{1/2}\) attains both bounds. Thus this family has \(R_D(F_N)=2\) and \(R_U(F_N)=3/2\) for every such \(N\).

Computation from the support

For binary rational locations, the rule requires only finding the two extreme occupied locations and comparing them with \(1/2\). It never expands the society into \(N\) resident records.

With \(m=1\), elementary rational comparisons give a conservative running time of \(O(\tau L^2+\log N)\) bit operations, including reading \(N\) if supplied separately.

4. Closure and the Pareto frontier

Section 2 excludes every guarantee pair having first coordinate below \(2\) or second coordinate below \(3/2\). Section 3 supplies one family satisfying every guarantee pair with coordinates at least those thresholds. Hence
\[ \mathcal A=[2,+\infty]\times[3/2,+\infty]. \]

Each coordinate interval is closed in the extended-real topology, so \(\overline{\mathcal A}=\mathcal A\). Its unique coordinatewise minimal point is \((2,3/2)\). This completely determines the limiting Pareto frontier.

⟨structured verdict parsed — rendered above⟩

The argument settles the intended limiting-frontier question: the unique Pareto-minimal pair is \((2,3/2)\). I found no substantive mathematical error. There is one minor clarification concerning the meaning of “binary rational” masses.

• Optimal values are correctly computed.

The support is finite and nonempty because the masses sum to \(1\), so its extreme locations \(\ell\) and \(h\) exist. For any \(z\in[0,1]\), the greatest distance over the support is attained at an extreme, giving
\[ D(\mu,z)=\max\{|\ell-z|,|h-z|\}. \]
The triangle-inequality lower bound and the midpoint attainment establish \(D^*(\mu)=w/2\). Consequently, \(U^*(\mu)=1-w/2\). These formulas also cover \(w=0\).

• The outcome-preservation lemma is valid in the intended resident-report domain.

An occupied location contains at least one resident because its mass is a positive integer multiple of \(1/N\). Moving one resident therefore preserves nonnegative masses and total mass \(1\).

If \(x\ne y\), the resulting society has positive mass at \(y\). A resident there can report \(x\), exactly recovering \(\mu\). The displayed strategyproofness inequality forces the new outcome to equal \(y\).

Repetition is legitimate: after each move the outcome remains \(y\), so the lemma applies again. This uses individual strategyproofness only.

• The lower-bound witnesses work, including boundary outcomes.

Under the intended interpretation that rational masses are encoded in binary, \(\mu_0\) belongs to \(\mathcal S_N\) for every \(N\ge2\).

If \(y\ge1/2\), the final support is \(\{0,y\}\); if \(y<1/2\), it is \(\{y,1\}\). Each support point has positive mass. The statements remain correct when \(y=0\) or \(y=1\): the prescribed moves then leave the society unchanged.

In both branches, the outcome is an endpoint of an interval of width \(s=\max\{y,1-y\}\ge1/2\). Thus its distance ratio is exactly \(2\).

For \(s<1\), the utility calculation is correct:
\[ \frac{1-s/2}{1-s}-\frac32 =\frac{s-1/2}{1-s}\ge0. \]
For \(s=1\), the achieved utility is zero while optimal utility is \(1/2\), so the stipulated ratio is \(+\infty\).

Allowing real locations and reports is essential here and is explicitly authorized by the task.

• The passage to arbitrary families is justified.

The lower bounds hold independently for each admissible population size covered by the argument. There is no exchange of quantifiers and no assumed relationship between different rules \(F_N\). Consequently, the pointwise bounds imply the claimed lower bounds on both limsups.

• The attaining rule is strategyproof.

For \(N=1\), truthful reporting yields distance zero.

For \(N\ge2\), removing the potentially deviating resident leaves a nonempty fixed population, so \(a\) and \(b\) exist. The three cases are exhaustive, including equality with \(1/2\). The formulas given in each case correctly describe the rule.

In either nonconstant case, every achievable outcome lies in the specified fixed interval, and truthful reporting gives the closest point in that interval to the resident’s true location. This verifies the required inequality for every alternative real report, including reports that merge or remove support locations.

• Both upper bounds and their attainment are correct.

The rule’s outcome lies in \([\ell,h]\), so \(d\le w\). For \(w>0\), this establishes the distance bound \(2\); for \(w=0\), the stated convention gives ratio \(1\).

The case analysis establishing \(d\le1/2\) is correct. Adding \(d\le w\) and \(2d\le1\) gives \(3d\le1+w\), which is exactly the inequality needed for the utility bound. Division is valid because \(1-d\ge1/2\).

On the specified support \(\{0,1/2\}\), the outcome is \(1/2\), the width and achieved maximum distance are both \(1/2\), and the ratios are exactly \(2\) and \(3/2\).

The attribution to [Walsh’s Theorem 1](https://cgi.cse.unsw.edu.au/~twalsh/wecai24.pdf) matches its stated guarantees. The prover independently verifies the properties needed here, so the argument does not depend on an unstated application of that theorem.

• The computation and frontier conclusions follow.

Scanning the support for its extremes requires no expansion into individual resident records. Standard binary rational comparisons support the conservative bound \(O(\tau L^2+\log N)\) for fixed \(m=1\).

The lower bounds exclude either coordinate below its threshold; the attaining family supplies every pair above both thresholds. Therefore the claimed rectangle for \(\mathcal A\) follows. Its coordinate intervals are closed in the extended-real topology, and its unique coordinatewise minimal point is \((2,3/2)\).

The sole minor issue is an encoding clarification. “Binary rational” can mean a rational with a binary numerator-and-denominator encoding, or specifically a dyadic rational. The prover uses the former interpretation without stating it. Under the latter interpretation, the asserted witness for every \(N\ge2\) is not always admissible: for example, its masses at \(N=3\) are not dyadic. The minimum clarification is to state explicitly which encoding is intended and qualify the population-size claim accordingly if dyadic masses are intended. This does not undermine the limiting conclusion, but the literal every-population-size statement needs that clarification.

⟨structured verdict parsed — rendered above⟩