| paper | Facility Location Games with Thresholds |
| authors | — |
| venue | AAMAS 2023 |
| filed under | frontier · tools-data |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 1
statement extracted from the paper’s text layer
Given finite rational support \(T\subseteq[0,1]\times[0,1)\) with masses \(\mu_{x,a}\ge0\) summing to \(1\), compute \(y\in[0,1]\) minimizing \(\mathrm{SC}_\mu(y)=\sum_{(x,a)\in T}\mu_{x,a}(|y-x|-a)_+/(1-a)\), and require the endpoint mechanism to be strategyproof under every rational clone expansion in which one clone may change only its reported location.
A finite-support high-multiplicity lower-threshold facility-location model with complete types \((x,a)\), rational masses \(\mu\), an indivisible facility decision \(y\), weighted social cost, and clone-consistent unilateral manipulation.
Strategyproofness is vacuous for a literally atomless individual, so the mirror depends on accepting clone-consistent unilateral deviations as the high-multiplicity semantics; this limits the literal continuum interpretation but does not defeat the finite-rational formulation.
fatal: False
The mirror covers Theorems 1, 3, and 5 over one-threshold facility-location games, while leaving Theorem 2, Theorem 4, and the both-threshold Theorems 6 and 7 unaddressed.
The strongest positive case is a direct Class-A mirror of Theorem 1. The paper has no named NP-hardness, membership-in-\(\mathrm P\), or parameterized-complexity result; its named results are algorithmic mechanism-design and approximation theorems. Under a strict complexity-only anchor rule, therefore, it has no qualifying anchor. Under the broader computational-result rule, however, Theorems 1, 3, and 5 are legitimate anchors.
The natural regime is a large population using one facility along a corridor: residents of many repeated housing blocks, grouped by location and by a small number of tolerance categories. A type is \(\theta=(x,a)\) for lower thresholds, or \(\theta=(x,b)\) for upper thresholds, where location and threshold completely determine the agent’s cost. A plausible instance might have \(N=10^6\) residents but only \(\tau=200\) location–threshold types. The facility location \(y\in[0,1]\) remains the same indivisible decision as in the paper; the population, not the facility, is what is continuized.
The lead problem is Lower-Threshold Exact Facility Location\(_\infty\), mirroring Theorem 1, proved in this paper. Its instance is a finite rational type support \(T\subseteq[0,1]\times[0,1)\) and rational masses \(\mu_{x,a}\) summing to \(1\). The cost of type \((x,a)\) at facility location \(y\) is \(c_L(y;x,a)=\frac{(|y-x|-a)_+}{1-a}\). The social cost is \(\mathrm{SC}_\mu(y)=\sum_{(x,a)\in T}\mu_{x,a}c_L(y;x,a)\).
For a reported mass distribution \(\widehat\mu\), preserving each agent’s threshold while allowing her location report to change, define \(L_{\widehat\mu}(z)=\sum_{x+a\le z}\widehat\mu_{x,a}/(1-a)\) and \(R_{\widehat\mu}(z)=\sum_{x-a>z}\widehat\mu_{x,a}/(1-a)\). The problem asks for a facility location \(y\) minimizing \(\mathrm{SC}_\mu(y)\), together with a mechanism that maps every \(\widehat\mu\) to such a location under truthful reporting and is strategyproof. The continuous analogue of Mechanism 1 is to sort the finitely many endpoints \(x-a\) and \(x+a\), and return the smallest endpoint at which \(L_{\widehat\mu}(z)\ge R_{\widehat\mu}(z)\).
This is not merely an analogy. If \(q\mu_{x,a}\) is integral, replace each type by \(q\mu_{x,a}\) identical clones. Every sum in Mechanism 1 becomes exactly the corresponding weighted sum above, while \(\mathrm{SC}\) is scaled by \(q\). A one-clone misreport changes mass by \(1/q\), and Theorem 1 gives precisely the required incentive inequality. Thus strategyproofness is interpreted through rational clone expansions rather than through a literally atomless individual whose report has zero influence. The problem is solvable in polynomial time in \(\tau\) and the rational encoding length: sorting the endpoints and evaluating the weighted inequalities suffices. This is the cleanest mirror because mass affects both the objective and the optimizer, while the original cost function, report space, facility decision, and incentive notion are preserved.
A second, also convincing mirror is Upper-Threshold Median Facility Location\(_\infty\), based on Theorem 3, proved here. A type is \((x,b)\), with cost \(c_U(y;x,b)=\min\{|y-x|/b,1\}\). Given rational masses, the mechanism outputs the lower weighted median of the location marginal: a point \(y\) satisfying \(\mu\{x<y\}\le1/2\) and \(\mu\{x\le y\}\ge1/2\). The task is to compute this facility and certify the guarantee \(\mathrm{SC}_\mu(y)\le\rho\,\min_z\mathrm{SC}_\mu(z)\), where \(\rho=\max\{2,b_{\max}/b_{\min}\}\) when \(b_{\min}\le1/2\), and \(\rho=1/b_{\min}\) otherwise.
Again, clearing denominators produces exactly the finite population to which Theorem 3 applies. The weighted median is computable by sorting type locations, and the optimum can be computed by scanning the finitely many breakpoints \(x\) and \(x\pm b\). Hence this is another Class-A problem. The authors should recognize it immediately: it is their same upper-threshold facility game with repeated agents represented by masses, not a fractional facility or a changed preference model.
A third, weaker but still valid mirror is Upper-Threshold Minimax Facility Location\(_\infty\), based on Theorem 5, proved here. Its objective is \(\mathrm{MC}_\mu(y)=\max_{\mu_{x,b}>0}c_U(y;x,b)\). Let \(b_{\min}\) be the smallest threshold represented in the society, and let \(x_{\min}\) be the leftmost location among types with threshold \(b_{\min}\). The problem asks for a strategyproof mechanism and a facility \(y\) satisfying \(\mathrm{MC}_\mu(y)\le2\min_z\mathrm{MC}_\mu(z)\). The continuous mechanism simply returns \(x_{\min}\), exactly as Mechanism 5 does. The theorem transfers by clone expansion, and the paper’s cited lower bound from Procaccia and Tennenholtz [16] transfers as well, so the factor \(2\) remains tight.
This third mirror is less valuable scientifically because a maximum-cost objective depends mainly on the support of \(\mu\), not on the magnitudes of its masses. The first two are stronger ChoCo examples: they show how replacing huge repeated electorates by a small rational census produces weighted convex or quantile computations without changing the facility-location question.
The mirror covers only the one-facility line models and Theorems 1, 3, and 5. I would not claim that it covers the paper’s both-threshold results, Theorems 6 and 7, without separately checking whether the interaction between lower and upper thresholds survives the weighted proofs. Theorem 4’s lower bound is a promising further question: its constant-size rational profiles suggest that the impossibility barrier should transfer directly, rather than disappear through continuization.
The weakest point is incentive semantics. A literal atomless continuum makes unilateral strategyproofness vacuous, so the clone-consistent interpretation is essential. It is faithful for rational high-multiplicity societies, but a referee could reasonably ask whether the more genuinely continuous question—preventing every positive-mass coalition from improving—also holds. That would be a new extension, not something established by the paper. A second open issue is whether the algorithms remain efficient for succinct densities or arbitrary measures rather than finite rational supports.
Subject to that qualification, this is a good positive case. The paper’s threshold cost functions and strategyproof mechanisms survive the population mirror exactly on a large, plausible repeated-type regime, and the lead result gives a genuine mass-sensitive polynomial computation rather than merely observing that the original facility location variable was already continuous.
The case against is not that facility location lacks a plausible repeated-type story. Apartment blocks, housing estates, or cohorts sharing a location and tolerance category are perfectly imaginable. The stronger objection is that the proposed mirrors do not preserve the computational object that the paper actually studies: unilateral incentive compatibility.
A mechanism in the paper acts on a profile of named agents, and strategyproofness asks whether one particular agent can change the outcome by changing her report. A distribution \(\mu\) contains neither the population size nor an individual agent. If \(\mathcal M\) maps \(\mu\) to a facility location, then in an atomless society one person’s report changes \(\mu\) by zero, so \(\mathcal M\) is automatically strategyproof. The central incentive property has disappeared.
Clone expansion does not remove this problem; it reintroduces a finite population. For the same rational \(\mu\), different clone counts \(q\) give different individual perturbations of size \(1/q\). Fixing \(q\) produces a weighted finite-agent mechanism. Quantifying over every positive rational mass perturbation produces a new coalition- or mass-manipulation notion, not the paper’s unilateral strategyproofness. The proponent’s construction is therefore a legitimate high-multiplicity reinterpretation, but not an intrinsic continuous mechanism on societies.
This defeats the proposed mirror of Theorem 1 under the programme’s strict computational scope. The weighted version of Mechanism 1 is formally easy to define: replace sums by weighted sums and sort the endpoints. But the paper does not give a complexity theorem; it gives a strategyproof rule for a one-dimensional mechanism-design problem. The continuous version is just the same rule applied to a weighted finite profile, with the individual incentive semantics restored by cloning. It supplies no new distributional computational problem unless one changes the incentive notion. If arbitrary measures are allowed instead, the problem needs a separate representation model for densities, cumulative distributions, and reports; the paper provides none.
Theorem 3 has the same defect. A weighted median is a perfectly sensible aggregate facility rule, but it is not strategyproof for an atomless individual in any substantive sense. With finite atoms, it is simply the median mechanism applied to repeated agents. With genuine distributions, the quantities \(d_{\min}\) and \(d_{\max}\) become essential infima and suprema of the support, so arbitrarily small tails can determine the guarantee while contributing essentially nothing to social cost. Restricting the support away from such tails restores a finite weighted instance; changing the guarantee to depend on mass quantiles creates a new theorem rather than a mirror of Theorem 3. Moreover, the theorem’s ratio is a distortion bound, not a named complexity result of the kind ChoCo is intended to classify.
Theorem 5 is weaker still. The maximum-cost objective is insensitive to masses altogether: \(\mathrm{MC}_\mu(y)\) depends only on the essential support of \(\mu\). Any two societies with the same support but completely different population proportions give the same optimization problem. In a finite-atomic model, the proposed rule is merely the original leftmost minimum-threshold-agent mechanism with duplicates suppressed. In an atomless model, the “leftmost agent with minimum threshold” may not exist; replacing it by an essential infimum yields a robust support problem, not a continuous population version of the paper’s mechanism.
The paper also contains no named hardness, membership-in-\(\mathrm P\), approximation-algorithm, or parameterized-complexity result. Theorem 1 is an explicit one-dimensional rule, while Theorems 3 and 5 are approximation guarantees for mechanisms. Under a broad interpretation of “computational result,” Theorem 1 can be made into a respectable weighted high-multiplicity exercise. Under ChoCo’s stated bar, however, the proponent has shown a finite weighted restatement plus a choice of new incentive semantics, not a worthwhile continuous complexity mirror.
This is therefore a near miss rather than an airtight rejection. If ChoCo deliberately counts clone-consistent weighted mechanism design as sufficient, the lower-threshold construction is a real positive case. But on the programme’s narrower population-continuization and computational-complexity brief, none of the three anchors survives: Theorem 1 loses its incentive content in the continuum, Theorem 3 is the same weighted median plus a distortion bound, and Theorem 5 discards mass entirely.
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.