Facility Location with Double-Peaked Preferences (d4-conf-aaai-2015-0090)

Given rational \(b,c>0\), a rational finite-support society \(\mu=\sum_{j=1}^{\tau}p_j\delta_{x_j}\) with \(x_j\in\mathbb R\), and a target ratio \(\rho\), decide whether a polynomial-time randomized rule \(F\) exists that maps every such society to facility points \(y\in\mathbb R\), uses costs \(d(y,x)=c+\min\{|y-(x-b)|,|y-(x+b)|\}\), is truthful-in-expectation under every integral lift \(N\mu\) and one-agent report \(x\to z\), and satisfies \(\sup_{\mu}\mathbb E[SC_{\mu}(F(\mu))]/SC_{\mu}^{*}\le\rho\); if so, output such a rule.

A society is given by its support: \(\mu=\sum_{j=1}^{\tau}p_j\delta_{x_j}\), with distinct \(x_j\in\mathbb Q\), positive binary rational masses \(p_j\), and \(\sum_jp_j=1\). Here \(\tau\) is the support size, not the number of possible types.
Fix public binary rationals \(b,c>0\). One facility may be placed anywhere on \(\mathbb R\); an agent at \(x\) incurs \(d(y,x)=c+\min\{|y-(x-b)|,|y-(x+b)|\}\).
Define \(SC_\mu(y)=\sum_jp_jd(y,x_j)\) and \(SC_\mu^*=\min_{y\in\mathbb R}SC_\mu(y)\).
A rule \(F\) takes the support representation and samples a rational facility point using unbiased random bits in expected time polynomial in \(m,\tau,L\), where \(m=1\) is the number of facilities and \(L\) is the total binary input length, including the public parameters.
For every positive integer \(N\) with \(Np_j\in\mathbb Z\) for all \(j\), every support point \(x\), and every rational report \(z\), put \(\mu'=\mu+(\delta_z-\delta_x)/N\). Truthfulness requires \(\mathbb E_{Y\sim F(\mu)}d(Y,x)\le\mathbb E_{Y\sim F(\mu')}d(Y,x)\). The rule receives neither \(N\) nor agent identities.

For given binary rationals \(b,c>0\) and \(\rho\in\mathbb Q\), does a polynomial-time randomized rule satisfying this truthfulness condition and \(\sup_\mu \mathbb E_{Y\sim F(\mu)}[SC_\mu(Y)]/SC_\mu^*\le\rho\) exist? Can existence be decided and, whenever feasible, such a rule constructed?

For finite lists of agents, a truthful-in-expectation randomized mechanism has worst-case social-cost approximation ratio \(1+b/c\). [Verified discrete result](https://link.springer.com/article/10.1007/s10458-017-9361-0).
No result settling exactly the support-encoded, integral-lift approximation question above was located in the literature search.

Partial solution: a stronger constructive upper bound

The feasible range can be enlarged beyond the bound in the notes. Define
$$ U(b,c)= \begin{cases} 1+\dfrac{2b}{2c+b},& b\le 2c,\\[6pt] 1+\dfrac{b}{2c},& b\ge 2c. \end{cases} $$
The two expressions agree when $b=2c$.

I prove the following:

• If $\rho\ge U(b,c)$, a rule satisfying all the computational and truthfulness requirements exists and can be constructed in polynomial time.
• If $\rho<1+\dfrac{b}{36c+13b}$, no truthful rule exists, even without a computational restriction.
• The bound $U(b,c)$ is the exact best guarantee among the fixed mixtures of the two mechanisms constructed below. This does not establish optimality among all truthful rules.

For every $b,c>0$,
$$ U(b,c)<1+\frac bc. $$
For example, when $b=c$, the new constructive guarantee is $\frac53$, improving the previous guarantee of $2$.

The full existence question remains open in the interval between the proved lower and upper bounds.

1. Cost identities and existence of an optimum

Write
$$ f(y,x)=d(y,x)-c=\bigl||y-x|-b\bigr|. $$
The reverse triangle inequality implies
$$ |f(y,x)-f(y',x)|\le |y-y'|, \qquad |f(y,x)-f(y,x')|\le |x-x'|. $$
Consequently, $SC_\mu$ is continuous and $1$-Lipschitz. Moreover,
$$ SC_\mu(y)\ge c+|y|-\sum_jp_j|x_j|-b. $$
Thus $SC_\mu(y)$ tends to infinity as $|y|$ tends to infinity. A minimum is attained, and
$$ SC_\mu^*\ge c. $$

For later use, define
$$ g(s)= \begin{cases} s,&0\le s\le b,\\ b,&b\le s\le 2b,\\ s-b,&s\ge 2b. \end{cases} $$
Direct evaluation gives
$$ \frac{d(t-b,x)+d(t+b,x)}2=c+g(|t-x|). $$
Indeed, the two excess costs have average
$$ \frac{s+|s-2b|}{2} \quad\text{when }s\ge b, $$
and average $s$ when $s\le b$. These are precisely the displayed cases.

The function $g$ is nondecreasing, satisfies $g(0)=0$, and is $1$-Lipschitz: it is continuous and affine with slopes $1$, $0$, and $1$ on its three defining intervals.

2. Two truthful mechanisms

2.1 The weighted-median mechanism

Sort the support as $x_1<\cdots<x_\tau$, and let
$$ t=\min\left\{x_i:\sum_{j\le i}p_j\ge\frac12\right\}. $$
Let $M$ output $t-b$ or $t+b$, each with probability $\frac12$.

Fix an admissible integer $N$. In the conceptual list containing $Np_j$ copies of each $x_j$, the point $t$ is the order statistic of rank
$$ K=\left\lceil\frac N2\right\rceil. $$
This list is used only in the proof.

Suppose one copy of a true type $x$ is replaced by a report $z$, and let $t'$ be the new median.

If $x<t$, the original number of entries strictly below $t$ is less than $K$. Removing $x$ and inserting $z$ cannot increase this number above its original value. Therefore $t'\ge t$, and
$$ |t'-x|\ge |t-x|. $$

If $x>t$, removing $x$ preserves at least $K$ entries at or below $t$. Inserting $z$ cannot remove these entries. Therefore $t'\le t$, again implying
$$ |t'-x|\ge |t-x|. $$

If $x=t$, the original expected cost is $c$, which is a lower bound for every possible cost.

Since the expected cost under $M$ is $c+g(|t-x|)$ and $g$ is nondecreasing, these cases prove truthfulness. The argument applies to every admissible $N$, while the implemented rule uses neither $N$ nor identities.

2.2 The mechanism that samples a type

Let $D$ sample a support point $T$ according to $\mu$, and then output $T-b$ or $T+b$, each with probability $\frac12$.

For any true type $x$, its expected cost is
$$ C_D(\mu,x)=c+\sum_jp_jg(|x_j-x|). $$
After a report changes the society to
$$ \mu'=\mu+\frac{\delta_z-\delta_x}{N}, $$
linearity gives
$$ C_D(\mu',x)-C_D(\mu,x) = \frac{g(|z-x|)-g(0)}{N} = \frac{g(|z-x|)}N \ge 0. $$
Thus $D$ satisfies the required truthfulness condition for every integral lift.

2.3 Exact sampling in expected polynomial time

Both mechanisms output rational points of polynomial bit length.

To sample from the rational masses, write $p_j=a_j/d_j$ and choose
$$ Q=\prod_jd_j, \qquad w_j=Qp_j. $$
The $w_j$ are nonnegative integers summing to $Q$, and the bit length of $Q$ is at most the sum of the denominator bit lengths.

For $Q>1$, generate $k=\lceil\log_2Q\rceil$ unbiased bits, obtaining an integer in $\{0,\ldots,2^k-1\}$. Reject and repeat if it is at least $Q$. The acceptance probability exceeds $\frac12$, so the expected number of trials is less than $2$. Locate the accepted integer in the cumulative intervals of lengths $w_j$. The case $Q=1$ is deterministic.

Sorting, rational arithmetic, and this sampling procedure take expected time polynomial in $\tau$ and $L$. The same procedure samples any rational mixture probability used below.

3. Approximation bounds for the two mechanisms

Let
$$ A=SC_\mu^*-c\ge 0. $$

3.1 The median bound

The weighted median satisfies
$$ \mu([t,\infty))\ge\frac12, \qquad \mu((-\infty,t])\ge\frac12. $$

Suppose $y<t-b$ and put $\Delta=t-b-y$. For every $x\ge t$, both $y$ and $t-b$ lie at or to the left of $x-b$. Moving from $y$ to $t-b$ therefore decreases this agent's cost by exactly $\Delta$. For every other agent, the increase is at most $\Delta$ by Lipschitz continuity. Hence
$$ SC_\mu(t-b)-SC_\mu(y) \le \bigl(1-2\mu([t,\infty))\bigr)\Delta \le 0. $$
The symmetric argument gives $SC_\mu(t+b)\le SC_\mu(y)$ when $y>t+b$.

Since an optimum exists, these inequalities show that some optimum $y^*$ belongs to $[t-b,t+b]$. Lipschitz continuity then gives
$$ \begin{aligned} \mathbb E[SC_\mu(M(\mu))] &=\frac{SC_\mu(t-b)+SC_\mu(t+b)}2\\ &\le SC_\mu^* +\frac{|t-b-y^*|+|t+b-y^*|}{2}\\ &=SC_\mu^*+b. \end{aligned} $$
Thus
$$ \mathbb E[SC_\mu(M(\mu))]\le c+A+b. $$

3.2 The bound for sampling a type

Let $X,T$ be independent random variables with distribution $\mu$. Averaging first over the final choice of sign yields
$$ \mathbb E[SC_\mu(D(\mu))] = c+\mathbb E\,g(|T-X|). $$

Fix an optimum $y^*$. For each real $x$, define
$$ \pi(x)= \begin{cases} y^*-b,&x<y^*,\\ y^*+b,&x\ge y^*. \end{cases} $$
This choice satisfies
$$ |x-\pi(x)|=\bigl||x-y^*|-b\bigr|=f(y^*,x). $$
In particular,
$$ \mathbb E|X-\pi(X)| = \mathbb E|T-\pi(T)| =A. $$

The triangle inequality and the Lipschitz property of $g$ imply, pointwise,
$$ g(|T-X|) \le g(|\pi(T)-\pi(X)|) +|T-\pi(T)|+|X-\pi(X)|. $$
Put $p=\Pr(\pi(X)=y^*+b)$. The two projected points are independent and take values in $\{y^*-b,y^*+b\}$. Their distance is either $0$ or $2b$. Since $g(0)=0$ and $g(2b)=b$,
$$ \mathbb E\,g(|\pi(T)-\pi(X)|) = 2p(1-p)b \le\frac b2. $$
Taking expectations proves
$$ \mathbb E[SC_\mu(D(\mu))] \le c+2A+\frac b2. $$

4. The improved construction

For a fixed rational $\alpha\in[0,1]$, let $F_\alpha$ run $M$ with probability $\alpha$ and $D$ with probability $1-\alpha$.

The choice of $\alpha$ depends only on public parameters. Therefore a convex combination of the two truthfulness inequalities proves truthfulness of $F_\alpha$. Section 2.3 proves its expected polynomial runtime.

The approximation bounds give
$$ \begin{aligned} \mathbb E[SC_\mu(F_\alpha(\mu))] &\le \alpha(c+A+b) +(1-\alpha)\left(c+2A+\frac b2\right)\\ &= c+(2-\alpha)A+\frac{(1+\alpha)b}{2}. \end{aligned} $$
Dividing by $SC_\mu^*=c+A$, the resulting bound is a weighted average of
$$ 2-\alpha \quad\text{and}\quad 1+\frac{(1+\alpha)b}{2c}. $$
Consequently,
$$ \sup_\mu \frac{\mathbb E[SC_\mu(F_\alpha(\mu))]}{SC_\mu^*} \le \max\left\{ 2-\alpha,\, 1+\frac{(1+\alpha)b}{2c} \right\}. $$

Choose
$$ \alpha_*= \begin{cases} \dfrac{2c-b}{2c+b},&b\le 2c,\\[6pt] 0,&b\ge 2c. \end{cases} $$
When $b\le 2c$, this is a rational number in $[0,1]$, and
$$ 2-\alpha_* = 1+\frac{(1+\alpha_*)b}{2c} = 1+\frac{2b}{2c+b}. $$
When $b\ge 2c$, choosing $\alpha_*=0$ gives
$$ \max\left\{2,1+\frac b{2c}\right\} = 1+\frac b{2c}. $$
Thus $F_{\alpha_*}$ has approximation guarantee $U(b,c)$.

The construction improves the previous bound strictly. For $b\le 2c$,
$$ \frac{2b}{2c+b}<\frac bc, $$
because $2c<2c+b$. For $b\ge 2c$, the inequality $\frac b{2c}<\frac bc$ is immediate.

5. Exact worst-case ratio within this mixture family

The upper bound for $F_\alpha$ is exact for every fixed $\alpha\in[0,1]$.

First, for positive dyadic $\varepsilon<1$, consider
$$ \mu_\varepsilon = \frac{1-\varepsilon}{2}\delta_0 +\varepsilon\delta_b +\frac{1-\varepsilon}{2}\delta_{2b}. $$
Its weighted median is $b$, and
$$ \mathbb E[SC_{\mu_\varepsilon}(M(\mu_\varepsilon))] = c+(1-\varepsilon)b. $$
For $D$, every pair of distinct support types has $g$-distance $b$. Therefore
$$ \begin{aligned} \mathbb E[SC_{\mu_\varepsilon}(D(\mu_\varepsilon))] &= c+b\left( 1-2\left(\frac{1-\varepsilon}{2}\right)^2-\varepsilon^2 \right)\\ &= c+b\left(\frac12+\varepsilon-\frac32\varepsilon^2\right). \end{aligned} $$
Placing the facility at $b$ gives social cost $c+\varepsilon b$, so
$$ SC_{\mu_\varepsilon}^*\le c+\varepsilon b. $$
It follows, by letting positive dyadic $\varepsilon$ tend to zero, that
$$ \sup_\mu \frac{\mathbb E[SC_\mu(F_\alpha(\mu))]}{SC_\mu^*} \ge 1+\frac{(1+\alpha)b}{2c}. $$

For the other term, take a dyadic $q\in(0,\frac12)$ and rational $R>2b$, and set
$$ \nu_{q,R}=(1-q)\delta_0+q\delta_R. $$
Its weighted median is $0$. Since $g(R)=R-b$,
$$ \mathbb E[SC_{\nu_{q,R}}(F_\alpha(\nu_{q,R}))] = c+q(R-b)\bigl(\alpha+2(1-\alpha)(1-q)\bigr). $$
The facility point $b$ has social cost $c+q(R-2b)$, hence
$$ SC_{\nu_{q,R}}^*\le c+q(R-2b). $$
For fixed $q$, letting rational $R$ tend to infinity gives the lower bound
$$ \alpha+2(1-\alpha)(1-q). $$
Letting positive dyadic $q$ tend to zero then gives $2-\alpha$. Combining both families with the upper bound proves
$$ \sup_\mu \frac{\mathbb E[SC_\mu(F_\alpha(\mu))]}{SC_\mu^*} = \max\left\{ 2-\alpha,\, 1+\frac{(1+\alpha)b}{2c} \right\}. $$

The first term decreases with $\alpha$, while the second increases. If $b\le 2c$, their intersection is $\alpha_*$. If $b\ge 2c$, the second term is already at least the first at $\alpha=0$ and increases thereafter. Thus $\alpha_*$ minimizes the exact worst-case ratio within this family, and that minimum is $U(b,c)$.

This conclusion concerns only the family $F_\alpha$.

6. A lower bound for every truthful rule

For completeness, the lower bound from the notes is proved here independently of the construction.

Assume a truthful rule has a finite uniform approximation guarantee $\rho$.

6.1 Truthfulness for repeated transfers

Suppose $N\mu$ is integral and a mass $r/N$ is transferred from $x$ to $z$, where $r$ is a positive integer and the source initially has at least this mass.

Perform the transfer in $r$ steps of size $1/N$. Before each step the source still has positive mass, and $N$ remains an admissible lift. Applying truthfulness at true type $x$ at every step and adding gives
$$ \mathbb E_{F(\mu)}d(Y,x) \le \mathbb E_{F(\mu+(r/N)(\delta_z-\delta_x))}d(Y,x). $$

6.2 Four societies

For an integer $k\ge2$, define
$$ N=4^k,\qquad \varepsilon=\frac1N,\qquad q=\frac{N-1}{3N}. $$
Because $N\equiv1\pmod3$, the number $Nq$ is an integer. Both $q$ and $\varepsilon$ are positive dyadic rationals, and
$$ 3q+\varepsilon=1. $$

Each society in the following table assigns mass $q$ to each of its three listed locations, and additionally assigns mass $\varepsilon$ to $b$. Coincident locations are coalesced.

| Society | Locations receiving mass $q$ |
|---|---|
| $A$ | $0,b,\frac{4b}{3}$ |
| $B$ | $0,\frac{4b}{3},3b$ |
| $C$ | $b,\frac{7b}{3},3b$ |
| $D$ | $\frac{4b}{3},\frac{7b}{3},3b$ |

Write
$$ d_a(y)=d(y,ab),\qquad \ell_P(a)=\mathbb E_{F(P)}d_a(Y),\qquad S_P=\mathbb E_{F(P)}SC_P(Y). $$
These expectations are finite. The approximation guarantee makes $S_P$ finite; positivity of a support mass bounds the expected cost of that support type. The Lipschitz inequality in the type argument then bounds the expected cost of any other fixed type.

The repeated-transfer inequality gives
$$ \begin{aligned} T_1&=\ell_A(1)-\ell_B(1)\le0,\\ T_2&=\ell_D(7/3)-\ell_B(7/3)\le0,\\ T_3&=\ell_D(4/3)-\ell_C(4/3)\le0. \end{aligned} $$
The transfers are, respectively, mass $q$ from $b$ to $3b$ in $A$, from $\frac{7b}{3}$ to $0$ in $D$, and from $\frac{4b}{3}$ to $b$ in $D$.

6.3 Pointwise inequalities

For real $t$, define
$$ h_a(t)=\bigl||t-a|-1\bigr| $$
and
$$ \begin{aligned} u_A&=h_0+2h_1+h_{4/3},\\ u_B&=2h_0+2h_{4/3}+2h_3-h_1-h_{7/3},\\ u_C&=h_1+h_{7/3}+h_3-h_{4/3},\\ u_D&=h_{4/3}+h_{7/3}. \end{aligned} $$
The following table evaluates these functions at the complete union of their breakpoints.

| $t$ | $3u_A(t)$ | $3u_B(t)$ | $3u_C(t)$ | $3u_D(t)$ |
|---|---:|---:|---:|---:|
| $-1$ | $10$ | $16$ | $15$ | $11$ |
| $0$ | $4$ | $16$ | $9$ | $5$ |
| $\frac13$ | $4$ | $10$ | $9$ | $3$ |
| $1$ | $8$ | $6$ | $5$ | $3$ |
| $\frac43$ | $8$ | $10$ | $1$ | $3$ |
| $2$ | $4$ | $6$ | $1$ | $3$ |
| $\frac73$ | $6$ | $6$ | $5$ | $3$ |
| $3$ | $14$ | $18$ | $5$ | $3$ |
| $\frac{10}{3}$ | $18$ | $20$ | $3$ | $3$ |
| $4$ | $26$ | $20$ | $3$ | $7$ |

Every function is affine between successive listed breakpoints. Its value there is therefore bounded below by the smaller endpoint value. On the left tail, the respective slopes are $-4,-4,-2,-2$; on the right tail, they are $4,4,2,2$. Neither tail gives a smaller value. Consequently, for every real $t$,
$$ u_A(t)\ge\frac43,\qquad u_B(t)\ge2,\qquad u_C(t)\ge\frac13,\qquad u_D(t)\ge1. $$

6.4 Combining costs and truthfulness

Put $\kappa=\varepsilon/q$ and define
$$ \begin{aligned} H_A(y)&=\frac{SC_A(y)}q+d_1(y),\\ H_B(y)&=\frac{2SC_B(y)}q-d_1(y)-d_{7/3}(y),\\ H_C(y)&=\frac{SC_C(y)}q-d_{4/3}(y),\\ H_D(y)&=d_{4/3}(y)+d_{7/3}(y). \end{aligned} $$
Since $d_a(y)=c+b\,h_a(y/b)$, expansion gives
$$ \begin{aligned} H_A(y)&=4c+b\,u_A(y/b)+\kappa d_1(y),\\ H_B(y)&=4c+b\,u_B(y/b)+2\kappa d_1(y),\\ H_C(y)&=2c+b\,u_C(y/b)+\kappa d_1(y),\\ H_D(y)&=2c+b\,u_D(y/b). \end{aligned} $$
Using the pointwise inequalities and $d_1(y)\ge c$, the sum of their expectations under their respective societies is at least
$$ (12+4\kappa)c+\frac{14b}{3} = \frac{4c}{q}+\frac{14b}{3}. $$
The equality uses $3+\kappa=1/q$.

On the other hand, grouping these expectations gives exactly
$$ \frac{S_A+2S_B+S_C}{q}+T_1+T_2+T_3. $$
Since the three transfer terms are nonpositive,
$$ S_A+2S_B+S_C \ge 4c+\frac{14qb}{3}. $$

Evaluate $A$ at $b/3$ and $B,C$ at $2b$. The excess costs of the three mass-$q$ types are, respectively,
$$ \left(\frac{2b}{3},\frac b3,0\right),\qquad \left(b,\frac b3,0\right),\qquad \left(0,\frac{2b}{3},0\right). $$
The additional type at $b$ has excess cost $b/3$ in the first evaluation and $0$ in the other two. Hence
$$ \begin{aligned} SC_A^*&\le c+\left(q+\frac{\varepsilon}{3}\right)b,\\ SC_B^*&\le c+\frac{4qb}{3},\\ SC_C^*&\le c+\frac{2qb}{3}. \end{aligned} $$
Any feasible approximation factor satisfies $\rho\ge1$, because every outcome has social cost at least the optimum. The approximation guarantee therefore implies
$$ S_A+2S_B+S_C \le \rho\left(4c+\frac{(13q+\varepsilon)b}{3}\right). $$
Combining the two bounds yields
$$ \rho\bigl(12c+(13q+\varepsilon)b\bigr) \ge 12c+14qb. $$
As $k$ tends to infinity, $q$ tends to $\frac13$ and $\varepsilon$ tends to zero. Taking limits of these numerical inequalities gives
$$ \rho \ge \frac{36c+14b}{36c+13b} = 1+\frac{b}{36c+13b}. $$
No continuity assumption on the rule is involved.

7. What is decided and what remains open

Both proved thresholds are rational functions of the public inputs and can be compared with $\rho$ in polynomial time.

If
$$ \rho\ge U(b,c), $$
the explicit rule $F_{\alpha_*}$ is a polynomial-time truthful construction.

If
$$ \rho<1+\frac{b}{36c+13b}, $$
the lower-bound argument certifies impossibility.

Feasibility remains unresolved for
$$ 1+\frac{b}{36c+13b}\le\rho<U(b,c). $$
Thus this supplies a stronger partial decision procedure, but does not decide existence for every input or construct a rule for every feasible threshold.

⟨structured verdict parsed — rendered above⟩

Overall assessment

The output establishes its stated partial results: a polynomial-time truthful construction for $\rho\ge U(b,c)$, an impossibility bound for $\rho<1+\frac{b}{36c+13b}$, and the exact worst-case ratio within its specified mixture family.

I found no mathematical error or substantive proof gap in those results. However, the output does not resolve the full USER_TASK: it explicitly leaves a nonempty interval of thresholds undecided. The appropriate overall classification is partial.

Step-by-step verification

1. Cost identities and existence of an optimum

The identity
$$ d(y,x)-c=\bigl||y-x|-b\bigr| $$
is correct. The two Lipschitz inequalities follow from the reverse triangle inequality, including at the nondifferentiable points.

The coercive bound
$$ SC_\mu(y)\ge c+|y|-\sum_jp_j|x_j|-b $$
is valid. The finite support ensures the sum on the right is finite. Continuity and coercivity therefore imply attainment of the minimum. The lower bound $SC_\mu^*\ge c$ also holds.

The displayed identity for the average cost of placing at $t-b$ and $t+b$ is correct on all three ranges defining $g$. The formulas agree at $s=b$ and $s=2b$. Thus the claimed monotonicity and Lipschitz constant of $g$ are valid.

Assessment: Correct.

2. Truthfulness of the two mechanisms

For the weighted median, the threshold definition agrees with rank
$$ K=\left\lceil\frac N2\right\rceil $$
in every admissible integral lift, including even $N$ and exact cumulative mass $\frac12$.

The replacement argument is valid:

• When $x<t$, removing one entry below $t$ and inserting one report cannot increase the original number of entries below $t$. The new rank-$K$ statistic therefore cannot lie below $t$.
• When $x>t$, removing that entry preserves the original entries at or below $t$. The new statistic therefore cannot exceed $t$.
• When $x=t$, the truthful expected cost equals $c$, the pointwise minimum possible cost.

These statements remain valid when the report merges with an existing support point or removes the source point from the support. Monotonicity of $g$ gives the required expected-cost inequalities.

For the type-sampling mechanism, the expected cost is linear in the input masses. Its change under a single transfer is exactly
$$ \frac{g(|z-x|)}N\ge0. $$
This covers every admissible $N$ and every rational report.

The fixed mixture preserves truthfulness because its mixing probability depends only on the public parameters.

Assessment: Correct; the required integral-lift quantifiers are respected.

3. Computational requirements

The common denominator construction produces integer interval lengths summing to $Q$. The bit length of the product of denominators is bounded by the sum of their bit lengths, so forming this product does not introduce exponential bit complexity.

For $Q>1$, rejection sampling has acceptance probability
$$ \frac{Q}{2^{\lceil\log_2Q\rceil}}>\frac12. $$
The stated expected number of trials is therefore correct. The deterministic case $Q=1$ is covered.

Sorting, cumulative rational arithmetic, sampling the rational mixture probability, and forming the output points all require polynomial time or expected polynomial time as claimed. The output coordinates have polynomial bit length. Neither mechanism needs $N$ or agent identities.

Assessment: Correct.

4. Approximation bounds and mixture optimization

The weighted median has at least half the mass on each relevant closed half-line. The movement argument outside $[t-b,t+b]$ correctly combines an exact cost decrease for that half of the population with the Lipschitz bound for the remaining mass.

Consequently, some optimum belongs to $[t-b,t+b]$. For such an optimum, the average distance to the two endpoints is exactly $b$. This establishes
$$ \mathbb E[SC_\mu(M(\mu))]\le c+A+b. $$

For the type-sampling bound, the specified projection satisfies
$$ |x-\pi(x)|=f(y^*,x), $$
including $x=y^*$. The pointwise bound involving $g$ follows from the triangle inequality and its Lipschitz property.

The projected random variables are independent because they are functions of independent $X$ and $T$. Their probability of differing is $2p(1-p)$, giving the valid bound
$$ \mathbb E[SC_\mu(D(\mu))]\le c+2A+\frac b2. $$

The resulting mixture bound is algebraically correct. After division by $c+A$, it is a convex combination of the two stated endpoint bounds. The formula for $\alpha_*$ solves their intersection when $b\le2c$ and selects the minimizing boundary when $b\ge2c$.

The boundary $b=2c$ is consistent in both formulas. The strict comparison
$$ U(b,c)<1+\frac bc $$
is correct for every positive $b,c$.

Assessment: Correct.

5. Exact worst-case ratio within the mixture family

For $\mu_\varepsilon$, the weighted median is $b$. Every pair of distinct support points indeed has $g$-distance $b$. Both expected-cost calculations are correct.

Using the displayed feasible placement to upper-bound the optimum gives a valid lower bound on the approximation ratio. Letting positive dyadic $\varepsilon$ tend to zero yields the claimed endpoint
$$ 1+\frac{(1+\alpha)b}{2c}. $$

For $\nu_{q,R}$, the weighted median is $0$, and $g(R)=R-b$ under the stated restriction $R>2b$. The mixture numerator and the social cost at $b$ are correct.

The successive limits, first in rational $R$ and then in positive dyadic $q$, legitimately establish the supremum lower bound $2-\alpha$. No claim of an attained worst case is needed.

Together with the upper bound, these calculations prove the exact supremum and its minimization within the specified family.

Assessment: Correct. This establishes family optimality only, as the output explicitly acknowledges.

6. Lower bound for every truthful rule

The repeated-transfer argument is valid. Before every transfer, the source has positive mass and the same $N$ remains an admissible lift. Summing the truthfulness inequalities gives the stated endpoint inequality.

For $N=4^k$, the quantity
$$ Nq=\frac{N-1}{3} $$
is integral. Hence $q$ and $\varepsilon$ are positive dyadic masses satisfying $3q+\varepsilon=1$. The four societies and all three transfer directions are valid after coalescing coincident locations.

The finiteness argument is sufficient: the approximation guarantee bounds expected costs at support types, and the Lipschitz inequality transfers finiteness to the other fixed types appearing in the proof.

I checked every entry of the breakpoint table using exact rational arithmetic. All entries are correct. The table contains the complete breakpoint union, and the stated tail slopes are correct. Thus all four pointwise lower bounds follow.

The expansions of $H_A,H_B,H_C,H_D$ have the correct coefficients and constant terms. Their expectations group into
$$ \frac{S_A+2S_B+S_C}{q}+T_1+T_2+T_3. $$
Since the transfer terms are nonpositive, the direction of the resulting social-cost lower bound is correct.

The three proposed facility evaluations and their excess costs are correct, including the additional mass at $b$. Their weighted sum gives the stated coefficient $13q+\varepsilon$.

Finally, the numerical limit correctly yields
$$ \rho\ge1+\frac{b}{36c+13b}. $$
This step requires no continuity of the rule.

Assessment: Correct.

7. Coverage of the requested decision problem

The output decides feasibility in the two stated regions and constructs a valid rule throughout its feasible region. It does not determine feasibility for
$$ 1+\frac{b}{36c+13b}\le\rho<U(b,c). $$

Major issue — incomplete task coverage: The requested decision procedure must answer every input and construct a rule whenever feasible. The partial procedure does neither throughout this remaining interval.

This is an acknowledged limitation, not a false proof step. It cannot be repaired through clarification alone. The minimum additional result needed is a feasibility classification of the remaining interval, with a polynomial-time construction for any thresholds classified as feasible. Exact optimality within the mixture family does not supply that missing classification.

⟨structured verdict parsed — rendered above⟩