| paper | d4-conf-ecai-2025-0106 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: Yes. A single polynomial-time mechanism is truthful in expectation for whole-cohort deviations and guarantees expected welfare at least \(\tfrac12\mathrm{OPT}(\mu)\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given a finite-support distribution \(\mu\) over types \(t=(I_t,p_t)\), where \(I_t\) is a closed interval, \(p_t\in[0,1]^2\) sums to \(1\), and each type is a reporting cohort, design a randomized mechanism choosing one facility \(f_j\) and a point \(y\). Require that for every supported type \(t\) and alternate report \(t'\), its expected utility under true type \(t\) does not increase when the cohort of mass \(\mu_t\) reports \(t'\), and guarantee expected welfare at least \(\tfrac12\mathrm{OPT}(\mu)\), where \(W_\mu(f_j,y)=\sum_t\mu_t p_{t,j}\mathbf{1}[y\in I_t]\) and \(\mathrm{OPT}(\mu)=\max_{j,y}W_\mu(f_j,y)\). Seek a single mechanism for all finite rational supports with an implementation polynomial in support size \(\tau\) and input bit length \(L\).
A society is a finite-support distribution over complete interval and preference types. A cohort report replaces its type while keeping its mass fixed. The mechanism chooses a point maximizing weighted interval coverage, then chooses a facility uniformly; its objective is expected weighted social welfare and its constraint is cohort truthfulness.
Cohort reporting lets an entire mass act as one strategic bloc, whereas the paper models individual reports; high multiplicity alone does not establish that blocs can coordinate their reports.
fatal: False
Covers the two-facility, both-profiles-reported mechanism result of Theorem 2. It does not mirror the binary-preference result or the other privacy settings and lower bounds.
My lead is a narrow mirror of Theorem 2, proved in this paper. It studies the two-facility case with fractional preferences and both ranges and preferences reported. Theorem 2 says that RANDOM-FACILITY—choose the leftmost point covered by the greatest number of reported intervals, then choose either facility uniformly at random—is strategyproof and gives a \(2\)-approximation to optimal social welfare. The paper shows that this mechanism’s factor is tight on an instance where everyone has the same interval and prefers the same facility. That tightness is for this mechanism; the theorem does not establish that every strategyproof mechanism has approximation ratio at least \(2\).
The continuous society would be a distribution \(\mu\) over complete types \(t=(I_t,p_t)\), where \(I_t\) is a closed reachable interval and \(p_t=(p_{t,1},p_{t,2})\) is the type’s facility preference. Each \(\mu_t\) is the fraction of the population with that type; the input is a finite support of \(\tau\) types with binary-rational masses summing to \(1\). The outcome is still one actual facility at one point. Welfare is
\[
W_\mu(f_j,y)=\sum_t \mu_t p_{t,j}\mathbf{1}[y\in I_t],
\]
and \(\mathrm{OPT}(\mu)=\max_{j,y}W_\mu(f_j,y)\). This continuizes the population, not the facility or the agents’ utilities.
A plausible regime is a large city choosing between two services, such as a vaccination center and a vector-control center. Many residents share a modeled catchment interval and service preference, so \(n\) is large relative to \(\tau\). For example, neighborhood or age-group representatives might submit a report for each homogeneous cohort. That last feature is the mirror’s strategic assumption: a cohort of mass \(\mu_t\) is a strategic reporting unit, able to report another type while keeping its mass fixed.
Call the resulting problem Continuous Interval-Cohort Random Facility: given \(\mu\), design a randomized direct mechanism \(M\) that, for every such society, is truthful for each cohort and guarantees
\[
\mathbb E[W_\mu(M(\mu))]\ge \tfrac12\mathrm{OPT}(\mu).
\]
Cohort truthfulness means that for every supported type \(t\) and alternate report \(t'\),
\[
\mathbb E[U_t(M(\mu))]
\ge
\mathbb E[U_t(M(\mu-\mu_t\delta_t+\mu_t\delta_{t'}))],
\]
where \(U_t(f_j,y)=p_{t,j}\mathbf{1}[y\in I_t]\) uses the cohort’s true type. A solution is one mechanism, valid over all finite rational supports, with a polynomial-time implementation in \(\tau\) and the input bit length \(L\).
The paper’s mechanism extends directly: let
\[
D_\mu(y)=\sum_t\mu_t\mathbf{1}[y\in I_t],
\]
choose the leftmost maximizer of \(D_\mu\), and then choose a facility uniformly. Its expected welfare is half the mass covered at that point, while \(\mathrm{OPT}(\mu)\le\max_yD_\mu(y)\), giving the factor \(2\). For a cohort, changing its reported preference cannot affect the mechanism. If the truthful chosen point lies in its true interval, its expected utility is already \(1/2\), the largest possible under a uniform facility choice. If the point lies outside its interval, moving the cohort’s mass to another reported interval cannot make the selected point enter the true interval: coverage there cannot increase, while the old selected point’s coverage cannot decrease. So the mechanism is cohort-truthful. A weighted interval sweep computes the leftmost maximum in polynomial time in \(\tau\) and \(L\). This is a Class A mirror for the stated \(2\)-approximation task. Whether a cohort-truthful mechanism can beat \(2\) is a further question; Theorem 2 does not answer it.
The paper’s continuous point of facility placement and fractional preferences do not themselves make its population continuous. The proposed mirror does that explicitly, while retaining its facility choice, interval utility, welfare benchmark, and incentive goal. It covers Theorem 2’s two-facility, both-profiles-reported result; it does not claim to mirror the paper’s other privacy settings or its lower bounds.
The weak point is the change in strategic unit. In the paper, each individual reports; in this mirror, a homogeneous cohort reports together. For a truly nonatomic population, a single person’s report has zero effect on the distribution, so ordinary individual strategyproofness becomes vacuous. Cohort representation gives the continuous model a nontrivial incentive constraint, and the paper’s cited work on representative-based facility location makes that a recognizable variant. Still, the authors might regard it as a different strategic problem. Also, this anchor is an approximation-mechanism result, not a named complexity classification such as NP-hardness or membership in P; it supports an algorithmic mirror, but not by itself a claim that continuization dissolves discrete hardness.
The strongest objection is the incentive model, not whether a city has many residents with repeated interval and preference types. It plainly can, and Theorem 2 is a genuine algorithmic mechanism result. But its strategyproofness is about a person changing their own report. In a nonatomic population, one person has zero mass, so their report does not change \(\mu\) or the mechanism’s outcome. Individual strategyproofness then holds vacuously for every mechanism. Without that constraint, the planner can maximize welfare exactly by finding the facility and point with greatest weighted interval coverage. That is a sensible weighted optimization problem, but it has lost the paper’s central tradeoff between truthful reporting and welfare.
The best repair is the proponent’s: treat each homogeneous cohort as a strategic player able to move its mass to a different reported type. The paper’s mechanism does extend to that model: maximize \(D_\mu(y)=\sum_t\mu_t\mathbf{1}[y\in I_t]\), then choose a facility uniformly, giving the same \(2\)-approximation. The problem is that cohort reporting changes the strategic unit. High multiplicity compresses many interchangeable individuals in the input; it does not give them joint control of their mass. A census-block representative could make this a coherent institutional model, especially if all residents in the block share exactly the same utility. But that adds collective representation and aligned bloc incentives to a paper about individuals’ reports. The authors might study it, but it is not evidently the high-multiplicity version of their game.
Keeping finite populations preserves individual incentives, but then the mass distribution alone does not say how large one person’s report change is: the same \(\mu\) can represent populations of many different sizes. Retaining \(n\) and one-person deviations returns to the discrete game; taking the nonatomic limit erases those deviations. A nontrivial intermediate notion—such as incentives against finite-mass coalitions or approximate truthfulness as population size grows—would need its own motivation and definition.
So I would not claim that no facility-location scenario could support a continuous mirror. Fixed, representative cohorts are plausible, and under that assumption Theorem 2’s guarantee survives. The negative case is that the proposed anchor’s most faithful continuous version either removes its individual incentive constraint or replaces it with a bloc-level one. The latter could be a worthwhile research question, but its value depends on accepting that added strategic institution; the paper itself gives little reason to make it the focus of this continuization programme.
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.