| paper | Facility Location Games with Entrance Fees |
| authors | — |
| venue | AAAI 2023 |
| filed under | frontier · tools-data |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Proposition 1
statement extracted from the paper’s text layer
Given \(k\), sorted location types \(x_t\) with rational masses \(\mu_t\) summing to one, and a public entrance-fee oracle \(e\) supporting the minimizations required in Remark 1, compute exact facility locations minimizing either weighted total cost \(\sum_t \mu_t \min_j(|x_t - \ell_j| + e(\ell_j))\) or maximum positive-mass type cost.
A finite-support society of location types with rational masses; k indivisible facility locations are decision variables, and the objective is weighted total or worst-type travel-plus-entrance cost.
The paper’s oracle model leaves the finite encoding, oracle complexity, and exact output representation underspecified; the proponent suggests remedies but does not fully formalize one.
fatal: False
Directly covers Proposition 1’s total-cost and maximum-cost optimization problems for any number of facilities, and extends naturally to Theorem 2; it does not cover the full randomized and mechanism-impossibility table.
The strongest positive case is narrower than “this paper is already continuous.” Its facility locations are continuous already; the population is not. The credible mirror is to replace the finite location profile by a high-multiplicity distribution over location types, while keeping the paper’s entrance-fee function, indivisible number of facilities, strategic costs, and approximation objectives unchanged.
Let the types be \(T=\{1,\ldots,\tau\}\), where type \(t\) has location \(x_t\). A society is a mass vector \(\mu\in\Delta(T)\). For facility locations \(L=(\ell_1,\ldots,\ell_k)\), define
\[ c_e(x_t,L)=\min_j\{|x_t-\ell_j|+e(\ell_j)\}, \]
\[ TC_\infty(\mu,L)=\sum_t\mu_t c_e(x_t,L),\qquad MC_\infty(\mu,L)=\max_{t:\mu_t>0}c_e(x_t,L). \]
This is exactly the paper’s model with sums normalized by population size. If \(\mu_t=n_t/N\), expanding each type into \(n_t\) identical agents multiplies total cost by \(N\) and leaves all minimizers and approximation ratios unchanged.
The natural regime is a large municipal-service population: perhaps \(N=10^5\)–\(10^7\) residents, grouped into \(\tau=50\)–\(500\) origin zones or housing cohorts. Agents in one zone have the same location type and therefore the same cost for every facility arrangement. The entrance fee \(e(\ell)\) remains an arbitrary public location-dependent service charge. This is a genuine high-multiplicity interpretation, not fractional facilities or probabilistic outcomes.
My lead anchor is Proposition 1, proved in this paper. It states that, for any number of facilities, both the total-cost and maximum-cost optimization problems can be solved in \(O(n^3m)\) time.
The corresponding problem is:
Continuous Entrance-Fee Facility Location\(_\infty\). Given \(k\), a finitely supported rational society \(\mu\), and an entrance-fee oracle \(e\) exactly as in Remark 1 of the paper, output facility locations \(L\) minimizing either \(TC_\infty(\mu,L)\) or \(MC_\infty(\mu,L)\), together with the optimum value.
A standard finite encoding can restrict \(e\) to a rational piecewise-linear function; alternatively, one can retain the paper’s oracle model. A valid solution is an exact list of facility locations and an oracle certificate of optimality.
I expect this to be Class A. The paper’s Lemma 7 says that agents served by the same facility form a contiguous block in sorted location order. In the continuous version, the same statement applies to type blocks. Unit-count prefix sums become mass-weighted prefix sums, and the paper’s dynamic programme should run in time polynomial in \(\tau,k\), and the encoding length \(L\), rather than in the expanded population size \(N\). The one-facility subproblem on a block has objective
\[ \sum_{t\in B}\mu_t|x_t-\ell| +\Big(\sum_{t\in B}\mu_t\Big)e(\ell), \]
which is precisely the weighted version of the paper’s oracle-solvable subproblem.
This is a particularly good mirror because it is not invented around a peripheral analogy: it is the paper’s own optimization benchmark, with only multiplicities continuized. It covers both parts of Proposition 1, while making the computational gain explicit: complexity depends on the number of distinct types, not the number of repeated agents.
A second worthwhile anchor is Theorem 2, proved here. It shows that the mechanism \(m_{\mathrm{med}}\), which places the facility at the optimal location of the median agent, has total-cost approximation ratio at most
\[ 3-\frac{4}{r_e+1}, \]
and hence at most \(3\) over all entrance-fee functions.
The continuous problem is:
Continuous Median Entrance-Fee Mechanism\(_\infty\). Given \(e\) and a society \(\mu\), let
\[ q_\mu=\inf\{x:\mu((-\infty,x])\ge 1/2\} \]
be the left median location, and let
\[ x_e^*(q_\mu)\in\arg\min_{\ell}\{|q_\mu-\ell|+e(\ell)\} \]
with the paper’s tie-breaking rule. Output
\[ F_{\mathrm{med}}^\infty(e,\mu)=x_e^*(q_\mu), \]
along with its achieved value \(TC_\infty(\mu,F_{\mathrm{med}}^\infty)\) and its ratio to the optimum from Continuous Entrance-Fee Facility Location\(_\infty\).
For rational masses, this is exactly the high-multiplicity version of the paper’s median-agent mechanism. The proof of Theorem 2 uses only ordering, median mass, and inequalities between sums of costs; those become cumulative-mass inequalities and integrals without changing the structure. I would therefore expect the same bound to hold.
The strategic definition needs care. Literal unilateral strategyproofness in a completely atomless population is vacuous: one person has measure zero and cannot change the reported distribution. The faithful continuous formulation is therefore positive-mass cohort strategyproofness. A coalition is a positive submeasure \(\nu\le\mu\); it may change reports through a measurable map, producing a new reported society \(\hat\mu\). The mechanism is cohort-group-strategyproof if no such coalition can make every member strictly better off. This is recognisably related to the paper’s Definition 4, and it preserves the strategic content for large homogeneous cohorts.
I would not claim that Theorem 2 alone settles the global optimal-mechanism-design problem over all such \(F\). The clean computational question is the evaluation and implementation of the named median mechanism; the stronger question—what is the best cohort-strategyproof continuous mechanism?—is a natural follow-up.
A useful supporting anchor is Theorem 3, also proved here. Its lower-bound construction survives at the population level under the cohort interpretation. Replace the two-agent profiles by
\[ \mu^1=\tfrac12\delta_{-1}+\tfrac12\delta_{\varepsilon},\quad \mu^2=\tfrac12\delta_{-\varepsilon}+\tfrac12\delta_{1},\quad \mu^3=\tfrac12\delta_{-1}+\tfrac12\delta_{1}. \]
For the paper’s entrance-fee function with fee \(d\) at \(\pm1\) and fee \(D\) elsewhere, any mechanism beating the theorem’s stated ratio is forced to output \(-1\) on \(\mu^1\) and \(1\) on \(\mu^2\). At \(\mu^3\), either output creates a profitable deviation by a half-population cohort: the \(-\varepsilon\) cohort can report \(-1\), or the \(\varepsilon\) cohort can report \(1\). Thus the same lower-bound algebra transfers after replacing repeated agents by positive-mass types.
I would describe this as a B-like preservation of an impossibility, not as an NP-hardness result. It shows that continuization does not automatically erase the paper’s mechanism-design obstruction, but it is weaker as a ChoCo computational anchor because it requires cohort-level rather than literal individual deviations.
The weakest point is therefore the strategic semantics. The optimization mirror based on Proposition 1 is robust: it is a direct high-multiplicity version of the paper’s stated problem and should be Class A. The mechanism mirrors require an explicit positive-mass coalition convention; without it, atomless strategyproofness collapses into vacuity. I would make Proposition 1 the central result, use Theorem 2 as the constructive mechanism-design extension, and treat Theorem 3 as a boundary result rather than claim that the whole Table 2 continuizes automatically.
I cannot make an honest universal negative case. The strategic anchors are weak, but Proposition 1 survives the programme’s test.
The strongest objection to the Proposition 1 mirror is that it is almost entirely a weighted-input compression. The paper already assumes an oracle for an arbitrarily represented entrance-fee function, so it does not provide a standard finite encoding or a usual polynomial-time theorem in the first place. Retaining the oracle yields only an oracle-polynomial result; replacing it with piecewise-linear fees defines a new restricted model. Moreover, once fees are encoded sensibly, replacing repeated agents by masses appears to require only sorting distinct locations and replacing repeated additions by weighted sums. That makes the contribution look routine rather than like a new separation, LP, or complexity phenomenon.
But this is not a decisive objection under ChoCo’s rules. A finite-support distribution with rational masses is exactly the prescribed high-multiplicity object. Agents at one location have identical costs and strategic possibilities, and the contiguous-block lemma, prefix sums, and one-block objective all survive with weights. The resulting algorithm would run in \(\operatorname{poly}(\tau,k,L)\) rather than in the expanded population size. Calling that “mere compression” effectively objects to high multiplicity itself, which the programme explicitly treats as legitimate. Proposition 1 is therefore a genuine Class-A candidate.
Theorem 2 is less compelling as a computational anchor. For an atomless population, individual strategyproofness becomes vacuous because one report has zero mass. The proposed cohort-strategyproofness repairs this, but it is a newly chosen solution concept. Still, a finite weighted-cohort formulation preserves the paper’s original semantics exactly, so this is a weakness in novelty and scope, not a fundamental failure of the mirror.
Theorem 3 likewise cannot be invalidated. Its three profiles can be represented by two positive-mass types, and the deviations used in the proof can be made by an entire cohort. The lower-bound construction therefore survives perfectly well. Its limitation is that it contributes no new computational complexity question; it is a transferred impossibility result. That makes it supporting evidence, not a reason to reject the model.
Thus the best negative report would say that the mechanism-design mirrors are either strategically vacuous in the atomless limit or merely weighted restatements in the finite-cohort version, while the paper’s arbitrary-fee oracle makes the computational encoding underspecified. Those points substantially reduce the novelty of the proposal. They do not defeat the optimization mirror, however. Since Proposition 1 is a named computational result with a sensible high-multiplicity interpretation, the universal claim that no worthwhile continuous mirror exists is not supportable.
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.