| paper | Facility Location Games with Fractional Preferences and Limited Resources |
| authors | — |
| venue | AAMAS 2024 |
| 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.1
statement extracted from the paper’s text layer
\(\mathrm{FL}^{\mathrm{KP}}_\infty\): Given a rational finite-support society \(\mu=\sum_{\ell=1}^{\tau}\mu_\ell\delta_{(x_\ell,p_\ell)}\) over \([0,1]\times\Delta_2\), with \(p\) public and \(x\) privately reportable, compute a deterministic rule selecting \((F_j,y)\in\{F_1,F_2\}\times[0,1]\) that is group-strategy-proof against measurable positive-mass coalitions changing positions and satisfies \(U_\mu(f(\mu))\ge\frac{1}{2}\max_{j,y}U_\mu(F_j,y)\), where \(U_\mu(F_j,y)=\int p_j(1-|x-y|)\,d\mu\); determine whether selecting \(j\in\arg\max_j\int p_j\,d\mu\) and placing it at a corresponding weighted median always achieves this guarantee.
A finite-support high-multiplicity municipal society with types \(\theta=(x,p)\), mass \(\mu_\ell\) representing resident fractions, public fractional preferences, private positions, facility choice \(j\), location \(y\), and normalized social welfare \(U_\mu\).
The paper proves group strategy-proofness for named agents, not for arbitrarily split measurable submasses, so the clone-splitting equivalence still requires a formal proof.
fatal: False
The mirror covers Theorem 3.1 through the weighted-median mechanism and also gives a report-independent population analogue of Theorem 5.4. It leaves the paper's lower bounds, nontrivial randomized guarantees, and \(k\)-facility results without established continuous strategic transfers.
The strongest honest case is an extension rather than a literal direct mirror. Facility locations already lie in a continuous interval in the paper; the new continuous object is the population itself.
A natural regime is municipal facility planning. Residents are grouped by census block or housing cohort and by a common facility-use profile. A type is \(\theta=(x,p)\), where \(x\in[0,1]\) is the block’s location and \(p=(p_1,p_2)\in\Delta_2\) is the cohort’s fractional preference for the two facilities. A society is a rational finite-support distribution \(\mu=\sum_{\ell=1}^{\tau}\mu_\ell\delta_{\theta_\ell}\), where \(\mu_\ell\) is the fraction of residents of type \(\theta_\ell\). In a city, \(n\) may be in the millions while \(\tau\) is the number of block/preference classes.
Clearing denominators turns \(\mu\) into a finite election-like population of clones, so the welfare objective is preserved exactly up to normalization. This is population continuization, not outcome-space fractionalization: the chosen facility remains indivisible, and its location remains a point in \([0,1]\).
My lead anchor is Theorem 3.1, proved in this paper: in the known-preferences setting, Mechanism 3.1 is deterministic group-strategy-proof and \(2\)-approximate.
The corresponding problem is Continuous Known-Preference Two-Facility Location, \(\mathrm{FL}^{\mathrm{KP}}_\infty\). An instance consists of a rational finite-support \(\mu\) over \((x,p)\), with the \(p\)-coordinate public and the position \(x\) privately reported, together with two facilities \(F_1,F_2\). A mechanism receives the reported position distribution and must output \((F_j,y)\), with \(y\in[0,1]\). Type \((x,p)\) has utility \(p_j(1-|x-y|)\), and social utility is \(U_\mu(F_j,y)=\int p_j(1-|x-y|)\,d\mu(x,p)\). The mechanism must be group-strategy-proof against positive-mass coalitions and achieve a constant approximation to \(\mathrm{OPT}_\infty(\mu)=\max_{j,y}U_\mu(F_j,y)\).
The continuous version of Mechanism 3.1 is explicit. Let \(a_j=\int p_j\,d\mu\), choose \(j^\star\in\arg\max_j a_j\), and locate \(F_{j^\star}\) at a \(p_{j^\star}\)-weighted median of the reported position measure: the smallest \(y\) satisfying \(\int_{x\le y}p_{j^\star}\,d\mu\ge a_{j^\star}/2\). This is computable in polynomial time by sorting the \(\tau\) support points. The weighted-median argument gives utility at least \(a_{j^\star}/2\), while every feasible facility has optimum utility at most \(a_j\); hence the ratio is at most \(2\). Thus I expect this mirror to be Class A.
This is recognisably the authors’ problem: the facility choice, fractional preferences, private positions, strategy-proofness notion, and social-utility objective are unchanged. Only sums over named residents become weighted sums over resident types. The authors’ proof already depends on aggregate support weights and ordered positions, so the weighted-median replacement is natural rather than an artificial tractable simplification.
A second, cleaner anchor is Theorem 5.4, proved in the paper: in the general setting, Mechanism 5.2 is randomized group-strategy-proof with approximation ratio \(4\). The corresponding problem, Continuous General Two-Facility Location, has the same type distribution, but both \(x\) and \(p\) are privately reported. A solution is a randomized rule mapping reports to a facility and location, strategy-proof in expectation against positive-mass coalitions, with bounded worst-case ratio.
The literal continuous analogue of Mechanism 5.2 chooses \(F_1\) or \(F_2\) uniformly and places it at \(1/2\), independently of all reports. Therefore it remains strategy-proof even under arbitrary mass deviations. Its expected social utility is at least \(1/4\), since \(1-|x-1/2|\ge1/2\) and \(p_1+p_2=1\); meanwhile \(\mathrm{OPT}_\infty(\mu)\le1\). The ratio is therefore at most \(4\). This is again Class A, although computationally unambitious because the paper’s own mechanism ignores the reports.
The main semantic caveat is incentive compatibility. In a genuinely atomless population, an individual has zero influence, so unilateral strategy-proofness becomes vacuous. For the first problem I therefore use the high-multiplicity interpretation of group strategy-proofness: a coalition is a measurable positive-mass subpopulation that may jointly change its reports. This is an explicit extension of the paper’s named-agent notion, not something to conceal as a direct equivalence. The second anchor avoids the issue because its mechanism is report-independent.
I would not claim that this paper supplies a Class B or Class C result: it contains no named NP-hardness or parameterized-complexity theorem. Nor would I automatically transfer Theorems 3.2 or 3.6, whose lower bounds concern individual deviations and whose continuous positive-mass versions require a separate proof. The natural follow-up questions are whether the factor \(2\) lower bound survives for \(\mathrm{FL}^{\mathrm{KP}}_\infty\), whether the paper’s \(4/3\) randomized result from Theorem 3.4 transfers, and whether the \(k\)-out-of-\(m\) result in Theorem 6.1 admits the same weighted-median/top-\(k\) formulation.
So the positive case is real but bounded: the paper supports a credible Class-A population mirror for its approximation mechanisms, strongest for Theorem 3.1. Its weakest point is that preserving the strategic content requires the explicit positive-mass-coalition extension; without that qualification, the continuum would erase rather than illuminate the paper’s mechanism-design question.
The strongest negative case is that the proposed mirrors change the strategic object at exactly the point where the paper’s results have content. In an atomless society, an individual has measure zero and cannot affect the reported distribution, so individual strategy-proofness becomes vacuous. Replacing finite coalitions by positive-mass coalitions is a substantive new notion, not a harmless limit. If type masses cannot split, clone fidelity fails; if they can split, the model has become a divisible-coalition game that the paper did not study.
This objection is serious for both anchors, but it does not defeat the best version of the first one. Take a rational finite-support society over \((x,p)\), interpret each support point as a cohort of cloned residents, and permit arbitrary submasses of a cohort to misreport. Then clearing denominators recovers the finite population exactly: social utility is merely scaled by the population size, facility choices remain indivisible, and the weighted-median argument extends through the usual clone interpretation. The mechanism chooses \(F_j\) from the public masses \(a_j=\int p_j\,d\mu\) and locates it at a \(p_j\)-weighted median. A coalition that moves that median cannot make every positively affected member better off, because some member must lie on the wrong side of the old median. This is an author-recognizable high-multiplicity extension, not an arbitrary re-modelling.
One can argue that this mirror is computationally unambitious: the paper already sorts the \(n\) reported positions, and replacing repeated positions by masses only changes the implementation from \(O(n\log n)\) to \(O(\tau\log\tau)\). There is no exponential type space, pricing problem, or complexity classification. But that is not a decisive objection under the programme’s rules. A numbered approximation theorem is a qualifying computational anchor, and a simple Class-A structural result is still a legitimate mirror. The paper’s citation of weighted-agent facility location is supporting high-multiplicity precedent, not a collision.
Theorem 5.4 is much weaker as an anchor. Mechanism 5.2 chooses a facility uniformly and places it at \(1/2\), regardless of every report. Its continuous guarantee,
\[ \frac12\int \bigl(p_1(1-|x-\tfrac12|)+p_2(1-|x-\tfrac12|)\bigr)\,d\mu \ge \frac14, \]
holds for any probability measure, indeed without needing a meaningful type system. The population is not doing computational work; the mechanism does not inspect \(\mu\), and the proof is only a diameter bound. A more ambitious question—optimizing over report-dependent randomized group-strategy-proof mechanisms—would be a new mechanism-design problem, but the paper supplies no result about that continuous optimization problem. Thus Theorem 5.4 should not carry the case by itself.
That still leaves Theorem 3.1. Its finite-support cohort interpretation is plausible for municipal planning, and its objective depends only on type and facility outcome, not on identity, history, or pairwise relations. The atomless-incentive objection can be avoided by using rational masses and positive-mass coalitions, while retaining exact clone correspondence. The fact that the resulting algorithm is elementary is a reason to rank the mirror modestly, not a reason to reject it.
So the honest negative case is narrow: Theorem 5.4 is a poor computational mirror, and any continuous treatment must label the strategic extension explicitly rather than calling it a direct limit. But I cannot honestly defeat Theorem 3.1 under the programme’s own standards. The requested universal “no worthwhile mirror in any scenario” verdict would therefore be overstated; this paper has at least one credible Class-A high-multiplicity mirror.
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.