d4-conf-sagt-2019-0012

The strongest honest mirror is the computation of the paper’s minimax benchmark for average cost. I would use one anchor: Proposition 10, proved in the paper. It states that, given \(n\) candidate intervals \(K_i=[a_i,b_i]\subseteq[0,B]\) of length at most \(\delta\), Algorithm 1 computes in \(O(n\log n)\) time the facility location \(p_{\mathrm{opt}}\) minimizing worst-case regret over all choices of true locations \(\ell_i\in K_i\). In full, the objective is to find \(p_{\mathrm{opt}}\in[0,B]\) minimizing \(\max_{\ell_i\in K_i}\bigl(\frac{1}{n}\sum_i|\ell_i-p|-\min_{q\in[0,B]}\frac{1}{n}\sum_i|\ell_i-q|\bigr)\). The algorithm sorts the interval endpoints and uses the resulting structure to find the minimizer.

I would call the continuous problem Mass Minimax-Regret Facility Location. Its input is \(B\in\mathbb{Q}_{>0}\), a finite support \(T\) of interval types \(t\), each with \(K_t=[a_t,b_t]\subseteq[0,B]\) and \(b_t-a_t\leq\delta\), and rational masses \(\mu_t>0\) summing to \(1\). A type means residents with the same candidate interval and the same distance-cost rule. A completion chooses, for each type \(t\), a probability distribution \(\nu_t\) of actual ideal points supported on \(K_t\). This allows the mass of a type to contain residents whose true locations differ within their shared interval. The resulting population distribution is \(\lambda=\sum_{t\in T}\mu_t\nu_t\).

For a facility at \(p\), let \(A_\lambda(p)=\int|x-p|\,d\lambda(x)\), and let \(A^*(\lambda)=\min_{q\in[0,B]}A_\lambda(q)\). The problem asks for an exact \(p^*\in[0,B]\) minimizing \(\sup_{\nu_t:\,\mathrm{supp}(\nu_t)\subseteq K_t}\bigl(A_\lambda(p)-A^*(\lambda)\bigr)\). An instance gives \(B\), the intervals, and the rational masses in binary; a solution is an optimal location \(p^*\), with its worst-case regret value.

This has a plausible regime in the paper’s own motivating setting: a large city locating a school, with many residents giving the same block-sized interval because they lack information to identify a more precise ideal point. The population may be very large while the number \(\tau=|T|\) of distinct reported intervals is modest. The continuous object here is the resident population and its per-capita welfare calculation. The facility location was already continuous in the paper; that fact is not the basis of the mirror.

For rational masses, the type distribution also has a clean bridge to cloned finite instances: choose a common denominator \(D\) and represent type \(t\) by \(D\mu_t\) residents. The worst-case regret objective is unchanged. In fact, for fixed \(p\), it can be written as
\[ \max_{q\in[0,B]}\sum_{t\in T}\mu_t\max\bigl\{|a_t-p|-|a_t-q|,\ |b_t-p|-|b_t-q|\bigr\}. \]
This follows by writing regret as a maximum over comparison locations \(q\), then maximizing independently over each type’s possible true locations; the maximum of \(|x-p|-|x-q|\) on an interval occurs at an endpoint. The formula gives a concrete route toward an exact weighted algorithm without expanding \(D\) clones. I expect this problem to be Class A, likely solvable in time polynomial in \(\tau\) and the input bit length by handling the resulting piecewise-linear envelope. That weighted bit-complexity result is a conjecture for the mirror, not a claim proved by Proposition 10.

I would not use the paper’s Theorem 4 or Theorem 6 as anchors. Theorem 4 gives a \(3\delta/4\) implementation guarantee for an anonymous minimax-dominant mechanism under average cost; Theorem 6 gives a \(\delta/2-\epsilon\) lower bound for anonymous, finite-range mechanisms under stated conditions. Those are mechanism-performance bounds, not complexity classifications. More fundamentally, in an atomless population a single resident’s report has zero mass and cannot change an aggregate mechanism’s output. Unilateral minimax dominance then loses the strategic force it has in the paper. My mirror therefore covers Proposition 10 and the benchmark computation underlying the mechanism-design problem, not the paper’s incentive results.

The weakest point is that this is a narrow mirror of an appendix result, while the paper’s central contribution is robust mechanism design. The paper proves an \(O(n\log n)\) algorithm for explicit finite inputs, not the desired algorithm polynomial in \(\tau\) and binary input length. Still, Proposition 10 is a named algorithmic result for a benchmark the paper explicitly defines and uses, and the interval-type population fits a credible large-city regime. Natural next questions are whether the weighted algorithm is polynomial in \((\tau,L)\), whether its solution gives useful finite-population guarantees without expanding clones, and whether any analogous compression survives for the paper’s maximum-cost benchmark.