| paper | Optimizing Multiple Simultaneous Objectives for Voting and Facility Location |
| authors | — |
| venue | AAAI 2023 |
| filed under | voting · distortion |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 3.4
Given explicit finite facilities F, finite complete client types T with rational distances d(t,A), rational mass distribution μ, and rational 0<λ<ρ≤1, output a facility A minimizing the maximum of Cλμ(A)/OPTλ and Cρμ(A)/OPTρ, where Cθμ(A) is the total distance of the worst θ mass and OPTθ is its minimum over F; determine the tight worst-case guarantee f(ρ/λ).
High-multiplicity spatial voting or facility location with finite facility set F, typed population masses μ, worst-fraction costs Cθ, and one discrete facility choice optimized simultaneously for several approximation ratios.
The mirror covers Theorems 3.4 and 4.3 and gives a mass interpretation of Proposition 4.1; it leaves the paper's facility-at-client refinements, broader ordered-median consequences, and bounded-support tightness questions unresolved.
The strongest positive case is a high-multiplicity mirror of the paper’s spatial voting/facility-location model. My lead anchor is Theorem 3.4, proved by Han, Jerrett, and Anshelevich rather than imported from prior work. The paper states the theorem in the main text, with some proof details deferred to the authors’ full version.
Take a finite set \(F\) of candidate facility locations and a finite set \(T\) of client types. A type is a complete distance profile \(d(t,\cdot)\) to every location in \(F\); two clients are the same type exactly when they are indistinguishable for the problem. The society is a rational distribution \(\mu\in\mathbb Q^T\), where \(\mu_t\) is the fraction of clients of type \(t\). The metric on \(T\cup F\) remains arbitrary and rational. Thus the facility choice remains discrete, exactly as in the paper; only the client population is continuized.
For \(0<\theta\le1\), define the continuous \(\theta\)-centrum cost of facility \(A\) by
\[ C_\theta^\mu(A) = \max\left\{ \sum_{t\in T} y_t d(t,A): 0\le y_t\le\mu_t,\ \sum_t y_t=\theta \right\}. \]
This is the total distance of the worst \(\theta\)-fraction of the population, allowing the boundary type to be split fractionally. If \(\mu_t=n_t/n\) and \(\theta=k/n\), then \(C_\theta^\mu(A)=c_k(A)/n\). Hence all approximation ratios are preserved exactly.
The continuous problem mirroring Theorem 3.4 is:
Continuous Two-Centrum Selection. Given \((F,T,d,\mu)\) and rational \(0<\lambda<\rho\le1\), output a facility \(A\in F\) minimizing
\[ > \max\left\{ > \frac{C_\lambda^\mu(A)}{\min_{B\in F}C_\lambda^\mu(B)}, > \frac{C_\rho^\mu(A)}{\min_{B\in F}C_\rho^\mu(B)} > \right\}. > \]
In particular, find a facility achieving the bound \(f(\rho/\lambda)\), where \(f\) is the paper’s function
\[ > f(x)= > \begin{cases} > \sqrt{x},&1\le x\le4,\\ > 1-x^{-1}+\sqrt{x^{-2}-2x^{-1}+2},&x>4. > \end{cases} > \]
This is a very faithful mirror. The original \(k\) and \(p\) become population fractions \(\lambda\) and \(\rho\); “the \(k\) worst clients” becomes “the worst \(\lambda\) mass”; and the action is still to choose one permissible facility or candidate. The paper’s proof only uses metric inequalities, sums of largest costs, and the individual optimum facilities \(O_k\) and \(O_p\). Those arguments extend to weighted masses by replacing sums with the corresponding tail-mass LP. In fact, the continuous algorithm can compute each \(O_\theta\) by sorting the \(\tau\) type distances, evaluate the two candidates, and return the better one. Its running time is polynomial in \(|F|,\tau\), the encoding length, and the number of thresholds.
The natural regime is a large municipality or electorate with many repeated client profiles: for example, millions of residents represented by a few dozen or few hundred census, commuting, or ideological cells, with a finite set of proposed facility sites or candidates. Members of one cell have the same distance or utility profile to all possible sites. The objectives can literally be “the worst 1% of residents,” “the worst 10%,” and “the whole population,” which is at least as natural as specifying \(k=547\) named clients. This is not outcome-space continuity or random noise: the candidate set remains discrete, and the continuous object is specifically the distribution of voters/clients.
The second useful anchor is Theorem 4.3, also proved by the authors rather than cited from elsewhere. It generalizes the result to \(q\) simultaneous centrum objectives. Let \(K=\{\theta_1,\ldots,\theta_q\}\subset(0,1]\). The corresponding continuous problem is:
Continuous Multi-Centrum Selection. Given \((F,T,d,\mu)\) and rational population fractions \(\theta_1,\ldots,\theta_q\), output a facility \(A\in F\) minimizing the maximum approximation ratio over these objectives, or at least one satisfying
\[ > \frac{C_{\theta_i}^\mu(A)} > {\min_{B\in F}C_{\theta_i}^\mu(B)} > \le \beta_q > \qquad\text{for every }i, > \]
where \(\beta_q\) is the unique value in \([1+\sqrt2,3)\) satisfying
\[ > (\beta_q-2)^{q-1}\beta_q=1. > \]
The paper proves that one of the individually optimal facilities \(O_{\theta_i}\) achieves this guarantee. Again, the continuous version is computationally explicit: calculate the \(q\) individual optima, evaluate their \(q\)-dimensional performance vectors, and choose the best. The expected classification is Class A. The main new questions are whether the \(\beta_q\) guarantee is tight for every \(q\), whether one can compute the exact Pareto-best facility more structurally, and whether compressed type representations yield faster algorithms when \(m\) or \(q\) is large.
The paper’s Proposition 4.1 strengthens this second mirror rather than serving as a separate anchor: for three objectives there is an instance in which every facility is at least \(\beta_3\)-bad for one objective. Any such witness with repeated client profiles can be converted directly into a finite distribution by assigning its repeated clients mass. More generally, rational discrete witnesses can be lifted exactly by taking a common denominator for the masses. The remaining question is whether the paper’s lower-bound constructions admit very small \(\tau\), which would establish tightness specifically in the high-multiplicity regime.
The authors should recognise this as their problem. They explicitly motivate the setting both as facility location and as spatial social choice, identify voters with clients, and discuss objectives such as the worst 10% of clients. The mirror preserves the arbitrary metric, finite candidate set, single-facility decision, separate objective optima, and simultaneous approximation requirement. It does not replace the problem by a line metric, a lottery over facilities, a weighted sum, or a fractional facility location.
The weakest point is that this paper has no named NP-hardness, P-versus-NP, W[1]-hardness, or FPT theorem. Its named computational results are approximation and tightness theorems. Moreover, with an explicitly listed finite facility set, the continuous problem is algorithmically fairly straightforward: evaluating a weighted centrum objective is just sorting or a small LP, and one can enumerate facilities. Thus this is a legitimate but modest ChoCo mirror; it does not yet expose the kind of deep pricing or continuum-specific hardness boundary found in continuous swap bribery.
Still, the mirror is honest and exact. For every discrete profile, setting \(\mu_t=n_t/n\) and \(\theta=k/n\) reproduces the paper’s objective up to the common factor \(1/n\); conversely, every rational continuous instance expands into a high-multiplicity discrete instance. The paper therefore supplies a clean Class-A test case for the programme: simultaneous fairness over population quantiles survives continuization, and its approximation theorems become statements about percentages of society rather than counts of named clients.
The strongest negative case is that the proposed mirror is formally valid but computationally too thin to justify a ChoCo project.
For Theorem 3.4, the continuous tail cost \(C_\theta^\mu(A)\) is just a weighted order statistic. Given a finite type table, sort the \(\tau\) distances to each facility, split at most one boundary type, and scan the explicit facility set \(F\). Thus every \(O_\theta\), and even the exact facility minimizing the maximum of the two ratios, is computable by direct enumeration in roughly \(O(|F|\tau\log\tau)\) time per threshold. The proof of Theorem 3.4 transfers by replacing sums with weighted sums; it introduces no separation problem, continuous optimization issue, or new complexity boundary. The paper itself presents the result as a tight approximation theorem for this finite facility-selection setting. [AAAI version](https://ojs.aaai.org/index.php/AAAI/article/view/25703)
A stronger opponent could ask for all population quantiles simultaneously, rather than two fixed fractions. That still does not rescue the anchor under the paper’s input model. For each facility, \(C_\theta^\mu(A)\) is piecewise linear, with breakpoints at cumulative type masses. Ratios between facilities are therefore piecewise rational-linear and can be checked over finitely many breakpoints and crossings. The apparent continuum of objectives remains a finite calculation over the support. If one instead supplies a genuinely continuous density or an implicit metric oracle, the resulting difficulty comes from that new representation, not from the paper’s theorem or its population model.
Theorem 4.3 has the same problem. Replacing \(k_i/n\) by \(\theta_i\) gives a faithful weighted version, but the proposed algorithm merely computes the \(q\) individual optima, evaluates their \(q\)-dimensional performance vectors, and selects one. The \(\beta_q\) guarantee is a structural inequality, not a complexity result. Increasing \(q\) changes the approximation constant, not the algorithmic nature of the problem. A Pareto or minimax formulation over the explicit facility set is still solved by enumeration.
Proposition 4.1 does not repair this. A rational lower-bound instance can indeed be turned into a mass distribution, but that establishes only a transferred approximation witness. Unless the witnesses are shown to use a bounded number of genuinely repeated distance profiles, it says nothing specifically about the high-multiplicity regime; the support may simply grow with the original number of clients. Even with constant support, it would remain tightness evidence for an elementary Class-A problem, not a computational obstruction.
The usual stronger objections are unavailable here. The objective is anonymous, so identity is not lost; worst-percentile service is a natural municipal or electoral quantity; positive fractions avoid the zero-mass degeneracy; and existing high-multiplicity facility-location work would support rather than undermine the model. The paper also does contain numbered approximation theorems, so the decisive “no named computational result” objection cannot honestly be used.
Accordingly, this is not a convincing universal negative case. The census-cell interpretation is natural, and the weighted tail formulation is an exact population mirror. The fair criticism is only that it is a modest baseline rather than a rich ChoCo target: the negative case can challenge its research value, but it cannot defeat Theorems 3.4 and 4.3 as legitimate continuous mirrors.
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.