Suppose many people each report a point in space, such as where they would like a shared facility built or which setting of a vector of policy knobs they prefer. A planner then picks one point for everyone. Each person prefers outcomes closer to their own true point. On a line, the median of the reports has a special property: nobody can pull it toward themselves by lying. The rule is strategyproof, meaning truth-telling is always a best response. In many dimensions this property is hard to keep. The natural "center" is the geometric median, the point minimizing total Euclidean distance, and it can be manipulated. Known theorems say that the strongest form of truthfulness forces the planner to let a single agent decide.
This note starts from an observation that is easy to state and, as far as the research file shows, has not been exploited. Squared Euclidean distance splits into a sum over coordinates in any orthonormal basis. A median taken separately along each axis of a fixed rotated basis, with fixed extra "phantom" points added on each axis, is therefore exactly strategyproof for every choice of rotation and phantoms. That gives a family of truthful rules whose free parameters grow only linearly in dimension. We propose to fit those parameters to a known prior over where agents tend to be. The rules stay exactly truthful however well or badly the fitting goes. Our core claim is that the efficiency lost to truthfulness depends on the effective dimension of the agent distribution, not on the ambient dimension $d$. We also claim that a learned rotation with learned phantoms recovers most of the gap to the manipulable geometric median on anisotropic data at $d=50$–$100$, where hand-designed truthful rules lose a factor that grows with $d$.
Core Claim
The mechanism takes reports $x_1,\dots,x_n\in\mathbb{R}^d$, a fixed orthogonal matrix $U$, and fixed phantom values $p_{k,1},\dots,p_{k,n+1}$ for each axis $k$. It outputs
$$ f(x)=U^\top z,\qquad z_k=\mathrm{med}\big((Ux_1)_k,\dots,(Ux_n)_k,\;p_{k,1},\dots,p_{k,n+1}\big). $$
Because $\|y-x_i\|^2=\sum_k ((Uy)_k-(Ux_i)_k)^2$, a misreport by agent $i$ changes each axis median only in the way a one-dimensional misreport would. Moulin's phantom median is strategyproof on each axis, so no misreport can reduce any term of the sum. Nothing about $U$ or $p$ depends on the reports. They may be chosen from public information, including a prior density $\rho$ over agent locations.
This does not contradict Group-Strategyproof mechanisms for facility location with Euclidean distance, which proves that deterministic group-strategyproof rules in strictly convex spaces are dictatorships. Coalitions can profitably coordinate against a coordinate-wise median. That paper itself notes that plain strategyproofness escapes its lower bounds, reaching $2-1/n$ for maximum cost. We target individual strategyproofness and say so openly. A simple chain of inequalities also shows why rotation choice is the lever. Write $\mathrm{SC}_2$ and $\mathrm{SC}_1$ for total Euclidean and total Manhattan (coordinate-sum) distance, measured in the rotated coordinates, and $g$ for the geometric median. The coordinate-wise median $m$ minimizes the Manhattan cost, and $\|v\|_2\le\|v\|_1\le\sqrt d\,\|v\|_2$. Together these give
$$ \mathrm{SC}_2(m)\le \mathrm{SC}_1(m)\le \mathrm{SC}_1(g)\le \sqrt{d}\,\mathrm{SC}_2(g). $$
The $\sqrt d$ penalty is paid only when the displacement vectors $x_i-g$ are spread across many rotated axes. If $\rho$ concentrates on a few directions and $U$ aligns with them, the ratio should behave like the square root of the effective rank of the spread, not of $d$. This is the "curse of dimensionality" question in its familiar form. High-dimensional PDE solvers escape exponential grids by exploiting structure and dimension-free Monte Carlo rates, as in the Black-Scholes error analysis of Analysis of the generalization error: Empirical risk minimization over deep artificial neural networks overcomes the curse of dimensionality in the numerical approximation of Black-Scholes partial differential equations, which gets $\mathcal{O}(d\varepsilon^{-2})$ parameters. Here we avoid the $K^d$ menu that a discretized truthful rule would need. The truthful structure is a product of one-dimensional rules, and its expected cost is estimated by Monte Carlo with an error rate that does not depend on $d$.
Relation to Prior Work
Three strands motivate the gap. The survey Mechanism Design for Facility Location Problems: A Survey and the capacity result of The Capacity Constrained Facility Location Problem establish phantom medians as the canonical truthful family on the line, where they are uniquely strategyproof under capacities. Facility Location Games with Scaling Effects derives phantoms from a terrain function, but only in one dimension. We keep their phantom machinery, move it to rotated axes in $\mathbb{R}^d$, and fit phantoms from a prior instead of deriving them in closed form. The Euclidean group-strategyproofness paper above constrains the design by ruling out coalition-proof deterministic rules, which is why we give up the group property.
Two learning approaches supply the contrast. Certifying Strategyproof Auction Networks trains networks that are only approximately truthful and finds certified regret "generally higher than empirical regrets", with verification cost that scales poorly. A Scalable Neural Network for DSIC Affine Maximizer Auction Design gets exact truthfulness only by restricting outcomes to a fixed menu of 128–1024 candidates, and it uses money. Our rules are exactly truthful over a continuous output space without payments. Learning touches only efficiency.
Strategic Facility Location via Predictions gives up dominant-strategy truthfulness for Price of Anarchy guarantees, meaning bounds on how bad equilibrium outcomes can be. We keep dominant-strategy truthfulness and use the prediction-like information, the prior, only to set parameters that do not depend on the reports.
The differentiable generalized geometric median of Augmented Normalization: Differentiating the Generalized Geometric Median supplies a reference point and a training tool. Its $\phi$-interpolated argmin is the manipulable efficiency target, and its gradient-through-argmin ideas inform the smoothed training objective.
Research Program
The work has four parts.
The first part is a theory component. It proves exact strategyproofness of rotated phantom medians and of any report-independent random mixture over rotations, which is truthful for every draw. It then bounds the expected ratio of the rule to the geometric median in terms of the covariance spectrum of $\rho$. The target is a bound governed by the ratio of the squared trace to the Frobenius norm, a standard effective-rank measure, when $U$ is the eigenbasis. It also gives a matching lower-bound construction on isotropic data, where no rotation helps.
The second part is the learning procedure. $U$ is parameterized through a matrix exponential of a skew-symmetric matrix, with $d(n+1)$ phantom values alongside it. These are trained to minimize Monte Carlo estimates of expected social cost or maximum cost under $\rho$. During training the hard median is replaced by a soft sort. At deployment the hard median is used, so truthfulness is never approximated.
The third part is an honest accounting of when learning beats simple choices such as a principal-component basis with no phantoms.
The fourth part is a scoped extension to capacitated and terrain-weighted costs. Here separability can break, and we will say precisely which terrain functions preserve it.
Baselines
The naive reference is the coordinate-wise median in the standard basis with no phantoms. It is exactly truthful and costs nothing to design. It is run on the same sampled profiles as every other method. Beating it means lower expected social cost at equal $n$ and $d$, with the gap widening in $d$ for anisotropic data.
The strongest truthful competitor built by hand is the coordinate-wise median in the principal-component basis of $\rho$, estimated from the same prior samples our learner sees. This is also our key ablation. If learned $U$ and phantoms do not beat it by a margin exceeding Monte Carlo error, the learning component adds nothing.
We add two further ablations. One learns phantoms in a fixed principal-component basis. The other learns the rotation with no phantoms. Together they separate the contributions of the two parameter groups.
The truthful randomized reference is random dictatorship and the random two-dictator rule, drawn from the characterization in Group-Strategyproof mechanisms for facility location with Euclidean distance. Its known social-cost ratio grows roughly like $n/2$. Beating it should be easy and serves as a sanity check.
The strongest learned competitor is a regret-penalized network in the style of Certifying Strategyproof Auction Networks, adapted to output a location. It gets the same prior samples and the same number of gradient steps as our learner, plus matched hyperparameter search. Its expected cost may be lower. We will report its empirical best-response regret, computed by gradient-based misreport search. Beating it means matching its cost within a stated tolerance at zero regret.
We also report the Harmonic mechanism of Strategic Facility Location via Predictions, using a prediction computed from the prior. Its cost is measured at computed equilibria rather than truthful reports.
The geometric median serves as the efficiency ceiling. We report its manipulation gain, since it is not truthful.
On reported numbers, the file contains no reported result on Lacuna for expected social cost of truthful high-dimensional facility location. The only related empirical statement is that the median mechanism's utility gap in the 50m×50m crowdsourcing simulation of Task Allocation and Mobile Base Station Deployment in Wireless Powered Spatial Crowdsourcing is "approaching zero" as workers grow, with no exact percentage reported. The strongest numbers available are therefore the theoretical ratios above. These are the $2-1/n$ maximum-cost bound under plain strategyproofness and the $n/2-1$ lower bound versus $n/2$ upper bound for social cost under randomized group-strategyproofness, both from the Euclidean paper. Every empirical number in our comparison will be produced by us under shared seeds.
Why not just…?
Why not just run the coordinate-wise median in the principal-component basis? This is the most serious threat, and it may capture most of the gain on Gaussian-like data. The research file's framing suggests coordinate projections fail under Euclidean distance. That is true for coalitions, but for individual truthfulness the median in any fixed basis is valid. The deciding experiment is the ablation above, run on non-Gaussian priors: mixtures, heavy-tailed data, and correlated binary vectors. On such data the principal axes of the covariance need not be the axes along which medians are cheap. If learning wins nowhere, the contribution shrinks to the effective-dimension theory plus the principal-component recipe. We would report that outcome as such.
Why not just use random dictatorship? It is truthful and simple, but its social-cost ratio grows linearly in $n$ per Group-Strategyproof mechanisms for facility location with Euclidean distance. Our rules' ratio is bounded by $\sqrt d$ regardless of $n$. The experiments will show the crossover explicitly as $n$ grows.
Why not just train a network with a regret penalty? Its truthfulness is only empirical. Certifying Strategyproof Auction Networks finds certified regret exceeding empirical regret, and its verification scales poorly exactly where $d$ is large. If such a network achieves much lower cost with regret that a strong misreport search cannot detect, that would undercut the value of exact structure. We measure precisely this.
Why not just relax to equilibrium guarantees with predictions? The Harmonic mechanism's robustness degrades to $\mathcal{O}(1/\epsilon^2)$ under bad predictions (Strategic Facility Location via Predictions). Its equilibria also require agents to know each other's locations. We report its cost under both accurate and deliberately misspecified priors next to ours. Our rules lose efficiency under a wrong prior but never lose truthfulness.
Proposed Experiments
We use four classes of data. Synthetic priors are Gaussians with controlled spectra, from isotropic to rank-$r$ plus noise, together with Gaussian mixtures and Student-t distributions. These are run at $d\in\{2,10,50,100\}$ and $n\in\{5,25,101\}$. As a real, correlated, high-dimensional source of ideal points, we use CelebA attribute vectors and learned CelebA features, the dataset studied in Augmented Normalization: Differentiating the Generalized Geometric Median. For a two-dimensional sanity check we reproduce the 50m×50m worker layout from the crowdsourcing paper. For the capacitated extension we use client coordinates from the facility-location instances in FrontierCO: Real-World and Large-Scale Evaluation of Machine Learning Solvers for Combinatorial Optimization.
Metrics are three: expected social cost and maximum cost relative to the geometric median, estimated on held-out profiles with confidence intervals; empirical manipulation gain from gradient-based misreport search, which should be exactly zero for our rules and serves as an implementation check; and design cost in wall-clock time and parameters.
There are three decisive checks. First, on the rank-$r$ family the learned rule's cost ratio should flatten in $d$ at fixed $r$, while the standard-basis median's ratio keeps rising toward the $\sqrt d$ envelope. Second, on isotropic data every rotation should perform alike, confirming the lower bound, and learning should gain nothing. Third, on mixtures and CelebA, learned $U$ and phantoms should beat the principal-component median by more than sampling error. If the third check fails, the paper's claim narrows to the theory and the simple recipe.
References
- Group-Strategyproof mechanisms for facility location with Euclidean distance
- Analysis of the Generalization Error: Empirical Risk Minimization over Deep Artificial Neural Networks Overcomes the Curse of Dimensionality in the Numerical Approximation of Black-Scholes Partial Differential Equations
- Mechanism Design for Facility Location Problems: A Survey
- The Capacity Constrained Facility Location Problem
- Facility Location Games with Scaling Effects
- Certifying Strategyproof Auction Networks
- A Scalable Neural Network for DSIC Affine Maximizer Auction Design
- Strategic Facility Location via Predictions
- Augmented Normalization: Differentiating the Generalized Geometric Median
- Task Allocation and Mobile Base Station Deployment in Wireless Powered Spatial Crowdsourcing
- FrontierCO: Real-World and Large-Scale Evaluation of Machine Learning Solvers for Combinatorial Optimization