| paper | Facility Location with Minimax Envy |
| authors | Qingpeng Cai, Aris Filos-Ratsikas, Ping-Zhong Tang |
| venue | IJCAI 2016 |
| filed under | voting · distortion |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: Yes. The proposed \(\alpha\)-LRM rule is anonymous, truthful in every finite lift, has uniform additive error at most \(\varepsilon\), and admits polynomial-time construction and evaluation with polynomial representation size. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given a finite rational location-type and report set \(T\subseteq\mathbb{R}\) and rational \(\varepsilon>0\), output a compact anonymous rule \(M\) on distributions \(\mu\) over \(T\) such that every rational finite lift is truthful-in-expectation and \(\sup_{\mu}\bigl(E_{\mu}(M(\mu))-O(\mu)\bigr)\le\varepsilon\); an α-LRM formula with \(\alpha\le\min\{1/4,\varepsilon/2\}\) is an allowed representation.
High-multiplicity anonymous facility-location mechanism design: types are preferred locations \(t\in T\), society is a mass vector \(\mu\), \(M(\mu)\) is a lottery over facility locations, and the objective is \(\rho(M)=\sup_{\mu}\bigl(E_{\mu}(M(\mu))-O(\mu)\bigr)\) subject to truthfulness on every finite empirical lift.
The finite-lift semantics keep \(N\) external and make the α-LRM rule depend only on support extremes, so the synthesis can look like a compact family of finite mechanisms rather than an intrinsically nonatomic computational problem.
fatal: False
The mirror covers the constructive real-line results in Theorems 2–3, with Theorem 2 providing truthfulness and Theorem 3 providing the computational approximation anchor; it leaves the deterministic and interval lower bounds as noncomputational mechanism statements.
The strongest honest mirror is a high-multiplicity version of the paper’s strategyproof facility-location problem. The paper has no named NP-hardness, tractability, or parameterized-complexity theorem; its named results are mechanism-existence, impossibility, and approximation theorems. Thus this is an algorithmic mechanism-design mirror, not a hardness-dissolution example.
Consider a long campus, corridor, or municipality with a large population of residents choosing the location of a public facility. A type is a preferred location \(t\in T\subseteq\mathbb{R}\), together with the common distance cost \(|y-t|\). A society is a mass vector \(\mu\) over finitely many location types, where \(\mu_t\) is the fraction of residents at \(t\). The intended regime has \(N\gg \tau=|T|\): many residents belong to a relatively small number of neighbourhood or cohort types.
Let
\[ \ell(\mu)=\min \operatorname{supp}(\mu),\qquad r(\mu)=\max \operatorname{supp}(\mu),\qquad L(\mu)=r(\mu)-\ell(\mu), \]
and let \(M(\mu)\) be a lottery over facility locations. For \(L(\mu)>0\), define
\[ E_\mu(y)= \frac{\max_{t,u\in\operatorname{supp}(\mu)} \bigl(|y-t|-|y-u|\bigr)}{L(\mu)}, \]
and for a lottery \(\nu\),
\[ E_\mu(\nu)=\int E_\mu(y)\,d\nu(y). \]
The benchmark is
\[ O(\mu)=\min_y E_\mu(y), \]
which the paper’s Lemma 1 identifies with the midpoint solution \(y=(\ell(\mu)+r(\mu))/2\).
The decision variable is not merely one facility location, but an anonymous randomized mechanism \(M\) mapping every society \(\mu\) to a lottery over locations. Its objective is to minimize the worst-case additive envy approximation
\[ \rho(M)=\sup_\mu \bigl(E_\mu(M(\mu))-O(\mu)\bigr). \]
To preserve the paper’s incentive notion, I would define truthfulness through finite high-multiplicity lifts. For every rational \(\mu\) and every \(N\) for which \(N\mu_t\) is integral, expand \(\mu\) into \(N\) named agents and apply \(M\) to its empirical distribution. A one-agent deviation from \(t\) to \(t'\) must not reduce that agent’s expected distance cost:
\[ \int |y-t|\,dM(\mu) \le \int |y-t|\,dM\!\left( \mu+\frac{1}{N}(e_{t'}-e_t) \right). \]
This prevents the usual problem that truthfulness becomes vacuous for a literally nonatomic population. The continuous rule is the common limit of truthful anonymous rules on these finite expansions.
My lead mirror is:
Continuous Real-Line Minimax-Envy Mechanism Design. Given a finite location-type set \(T\subseteq\mathbb{R}\), find a truthful-in-expectation anonymous rule \(M\) over all society distributions on \(T\), with no restriction on the facility location, minimizing \(\rho(M)\). A solution is the rule \(M\), together with its worst-case additive guarantee.
This directly mirrors the paper’s strongest constructive result. Theorem 2, proved in this paper, states that every mechanism in the \(\alpha\)-LRM class is truthful-in-expectation. For a society \(\mu\), the rule places the facility at
\[ \operatorname{mid}(\mu)=\frac{\ell(\mu)+r(\mu)}2 \]
with probability \(1-2\alpha\), at
\[ \ell(\mu)-L_\alpha(\mu) \]
with probability \(\alpha\), and at
\[ r(\mu)+L_\alpha(\mu) \]
with probability \(\alpha\), where
\[ L_\alpha(\mu)=\frac{1-4\alpha}{4\alpha}L(\mu), \qquad \alpha\in(0,1/4]. \]
Theorem 3, also proved here, says that for every \(\varepsilon>0\), there exists an \(\alpha\)-LRM mechanism with additive approximation \(\varepsilon\). Thus the infimum achievable additive approximation is \(0\), although it need not be attained by one fixed positive \(\alpha\).
The transfer is unusually clean: the induced finite rule depends on the profile only through its leftmost and rightmost reported types and their midpoint, exactly as in the paper. Hence the same truthfulness and approximation proofs apply to every finite high-multiplicity lift. Evaluating the rule for a given \(\mu\) is straightforward: scan the \(\tau\) types to find the extrema and compute the three lottery points. This is naturally a Class A mirror, although the paper itself does not state a complexity theorem.
A second, independent continuous problem is the relative-interval version. For \(k>1\), define
\[ I_k(\mu)= \left[ \frac{(1+k)\ell(\mu)+(1-k)r(\mu)}2,\, \frac{(1-k)\ell(\mu)+(1+k)r(\mu)}2 \right], \]
an interval of length \(kL(\mu)\) centred at the midpoint. The question is to find a truthful mechanism supported on \(I_k(\mu)\) for every \(\mu\), minimizing the worst-case additive approximation.
Theorem 6, proved in this paper, states that for every \(k>1\), every truthful mechanism whose output always lies in \(I_k(\mu)\) has approximation at least
\[ \frac{1}{1+k}-\varepsilon \]
for every \(\varepsilon>0\). It also states that any truthful mechanism whose output is restricted to the profile interval \([\ell(\mu),r(\mu)]\) has approximation at least \(1/2\). The paper then observes that choosing
\[ \alpha=\frac{1}{2(1+k)} \]
in \(\alpha\)-LRM yields approximation at most \(1/(1+k)\), so the continuous problem has the same sharp boundary as the finite one. Theorem 5 gives the complementary infeasibility result: for every \(k\in[0,1)\), no truthful mechanism can always output inside the shorter relative interval \(I_k(\mu)\). These statements remain meaningful in the high-multiplicity model because the induced \(N\)-agent rules must satisfy the paper’s truthfulness requirement for every \(N\).
A third mirror is the fixed-campus problem:
Continuous Fixed-Interval Minimax-Envy Mechanism Design. Given \(T\subseteq[0,1]\), find a truthful-in-expectation anonymous rule \(M\) whose output is always in the fixed interval \([0,1]\), minimizing \(\rho(M)\).
Theorem 7, stated and established in this paper, says that every truthful-in-expectation mechanism for the fixed interval \([0,1]\) has approximation at least \(1/3-\varepsilon\), for every \(\varepsilon>0\). The paper’s \(\alpha\)-LRM construction with \(\alpha=1/4\) gives the matching known upper bound \(1/2\). Therefore the continuous mirror asks for the optimal truthful population rule in the range
\[ \frac13\le \inf_M \rho(M)\le \frac12. \]
The authors would plausibly recognise these as their problems with the population replaced by its empirical distribution. The outcome space was already continuous in the paper; that is not the continuization. The new object is the society \(\mu\), while distance costs, minimax envy, truthfulness, and randomization are retained.
The weakest point is that maximum envy is an unweighted maximum over agents. Duplicating a type changes its mass but usually does not change the objective at all; mass matters mainly through the mechanism’s input and incentive constraints. Also, a literal atomless population would make unilateral truthfulness vacuous, which is why the finite-lift definition is essential. Finally, because the paper has no named complexity result, this mirror supports a tractable continuous mechanism-design programme, but it does not by itself produce a discrete-hardness-versus-continuum comparison.
The negative case is strongest at the programme’s entry gate: this paper contains no named computational result to continuize. Theorem 2 is a truthfulness proof, Theorem 3 an approximation guarantee, Theorems 5 and 6 mechanism impossibilities, and Theorem 7 a lower bound on truthful mechanisms. None states the complexity of a computational problem, gives an algorithmic classification, or identifies a discrete problem whose high-multiplicity relaxation might change its complexity. The proposed mirrors therefore turn the paper into a new mechanism-synthesis programme rather than continuizing one of its computational results.
The real-line anchor does not repair this. The \(\alpha\)-LRM mechanism depends only on the leftmost and rightmost reports, their distance, and their midpoint. Under the proponent’s finite-lift definition, the paper’s proof transfers essentially verbatim to every empirical distribution. That is a valid transfer, but it is not a continuous-population phenomenon: the interior masses \(\mu_t\) are ignored, and evaluating the rule requires only scanning for two extrema. The finite-lift convention also shows the underlying difficulty. A literally nonatomic agent has no strategic influence; retaining non-vacuous truthfulness requires quantifying over an external population size \(N\) and its \(1/N\)-deviations. The result is a family of finite mechanisms indexed by \(N\), not an intrinsically new continuum computational object.
One could define the stronger problem of finding the optimal anonymous truthful rule \(M\) over the whole simplex of distributions. But that is a new infinite-dimensional mechanism-design question, not a computational relaxation supplied by this paper. Its difficulty would come from synthesizing a globally truthful rule, a difficulty already present with finitely many agents; it is not a complexity effect caused by replacing a population with masses. If one makes the rule depend substantively on masses, one has moved beyond Theorems 2 and 3 and changed the mechanism-design problem.
The relative-interval anchor is even less independent. The interval in Theorems 5 and 6 is determined entirely by the two support extremes and their distance. Multiplicity again contributes nothing. The impossibility for \(k<1\), the \(1/(1+k)\) bound, and the \(1/2\) profile-interval bound all transfer to repeated finite types without any new continuous argument. A genuinely mass-sensitive variant could use quantiles or weighted endpoints, but then it is no longer the paper’s interval model and none of these theorems anchors it. Thus the second anchor is either the same support-based restatement as the first or a new problem lacking a result from the paper.
The fixed-interval anchor does not escape this objection. Theorem 7 is still only a mechanism lower bound, not a computational statement. Moreover, the paper’s Lemmas 2 and 3 deliberately reduce the relevant analysis to profiles with two location groups. The proposed high-multiplicity society simply makes those repeated groups explicit; it does not expose a population-scale optimization problem. Asking for the optimal anonymous rule over all \(\mu\) could be mathematically worthwhile, but its value would be a new characterization in strategyproof mechanism design, not a contribution to the programme’s complexity landscape.
This is not the mistaken objection that the facility location \(y\) is already continuous; the outcome being continuous says nothing about whether the society is continuous. Nor is existing high-multiplicity work a collision. The narrower point is that the paper’s substantive results are about the geometry of truthful rules and their worst-case guarantees, while the proposed mirrors add a distributional notation without producing a computational task whose complexity depends on population multiplicity.
I cannot honestly claim that no coherent high-multiplicity story exists: a campus or municipality with many residents sharing preferred locations is plausible, and the finite-lift semantics are defensible. The stronger negative conclusion is therefore conditional but clear: as a ChoCo paper, this is a poor mirror candidate. If mechanism synthesis itself is admitted as a target of the programme, the proponent has a legitimate open problem; under the stated computational brief, however, none of the three anchors survives as a worthwhile continuous-computational mirror.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.