| paper | d4-conf-aaai-2026-1180 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Yes. BALANCED evaluated using group masses satisfies all requirements. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 3.2
statement extracted from the paper’s text layer
Given a finite-support rational distribution \(\mu\) over types \((x,g)\in\mathbb{Q}\times 2^{[m]}\), with rational group weights \(w_j\ge 0\), can one compute in time polynomial in \(m,\tau,L\) a deterministic facility rule \(F\) such that \(F^\mu(y)=\max_j w_j\sum_{(x,g):j\in g}\mu_{x,g}|x-y|\) is at most \(2\min_z F^\mu(z)\), while preserving individual strategyproofness on every finite realization? For each \(N\) with \(N\mu\) integral, a deviation by an agent of type \((x,g)\) to location \(x'\) changes the distribution to \(\mu'=\mu-\frac1N\delta_{(x,g)}+\frac1N\delta_{(x',g)}\), and must satisfy \(|F(\mu)-x|\le |F(\mu')-x|\).
A society is a finite-support rational distribution \(\mu\) over complete location-and-group types \((x,g)\), with support size \(\tau\). A facility is placed at \(y\in\mathbb{R}\), minimizing the maximum per-capita weighted group cost \(\max_j w_j\sum_{(x,g):j\in g}\mu_{x,g}|x-y|\). Individual incentives are evaluated on every finite realization of \(\mu\), where one agent’s location report changes their mass by \(1/N\).
The mirror covers Theorem 3.2 for single-facility weighted total group cost, including its strategyproofness and \(2\)-approximation guarantee. It leaves the weighted maximum group cost and multi-facility results aside.
The strongest mirror I see is the paper’s single-facility weighted total group cost result.
Take a large municipal service population. A type is a location \(x\) and the agent’s full set of group memberships \(g\subseteq[m]\). Many residents may share a type—for example, because locations are represented by neighborhood zones and group memberships by a small set of policy cohorts. The society is a finite-support rational distribution \(\mu\) over \((x,g)\), with \(\mu_{x,g}\) the population share of that type. In the intended regime, the number \(N\) of residents is much larger than the support size \(\tau\). Treating a type as complete matters here: people with different locations or group memberships remain different types.
For a facility at \(y\), define the per-capita effect of group \(j\) and the maximum group effect by
\[
E_j^\mu(y)=w_j\sum_{(x,g):j\in g}\mu_{x,g}|x-y|,
\qquad
F^\mu(y)=\max_j E_j^\mu(y).
\]
The decision is a facility location \(y\in\mathbb R\); the goal is to minimize \(F^\mu(y)\). On an empirical society of \(N\) residents, each mass is a count divided by \(N\), so the paper’s original total group costs are \(N E_j^\mu(y)\). That common factor leaves the minimizers and approximation ratios unchanged.
My lead anchor is Theorem 3.2, proved in this paper: for the finite-agent weighted total group cost objective \(E_j=w_j\sum_{i\in G_j}c(f(\theta),x_i)\), the BALANCED mechanism is strategyproof and has approximation ratio \(2\). Its mass version is concrete. Let
\[
L_j(y)=\sum_{\substack{(x,g):x\le y\\j\in g}}\mu_{x,g},
\qquad
R_j(y)=\sum_{\substack{(x,g):x>y\\j\in g}}\mu_{x,g}.
\]
Choose the leftmost support location \(y\) for which
\[
\max_j w_jL_j(y)\ge \max_j w_jR_j(y).
\]
The continuous problem is to design a deterministic anonymous rule on these societies that outputs \(y\) with \(F^\mu(y)\le 2\min_z F^\mu(z)\), while retaining the paper’s truthful-reporting condition.
For that condition, I would require the rule to be strategyproof on every finite realization of the same rational distribution. If \(N\mu_{x,g}\) is integral for every type, one agent’s misreport from \(x\) to \(x'\) changes the input to \(\mu'=\mu-\frac1N\delta_{(x,g)}+\frac1N\delta_{(x',g)}\); truthfulness requires \(|F(\mu)-x|\le |F(\mu')-x|\). Quantifying over every such \(N\) preserves the finite-agent incentive question across replications of a society. The BALANCED rule is the natural candidate: on each such realization it is exactly the paper’s rule. Its approximation proof also uses mass counts only through linear inequalities, so the \(2\)-approximation argument carries over with rational masses. A support sweep computes the rule in time polynomial in \(m,\tau,L\), where \(L\) includes the rational input bit lengths. I expect this mirror to be tractable, in the programme’s Class A sense.
I think the authors would recognize this as their weighted group-cost facility problem: it keeps the line, group memberships, weights, maximum-over-groups objective, facility decision, and individual deviations. The paper has no named NP-hardness or parameterized-complexity result to anchor; Theorem 3.2 is its strongest relevant algorithmic result.
The soft spot is the incentive semantics. In a standard atomless game, one person has zero mass and cannot change the facility, making individual strategyproofness vacuous. The finite-realization condition above avoids that collapse by retaining the effect of one person’s share at every population size, but it is an explicit high-multiplicity extension, not the usual nonatomic-game definition. I would limit the mirror to this weighted-total-cost theorem and treat whether its factor \(2\) can be improved for fixed, low-support group structures as a further question.
The strongest case against this mirror is about fit with ChoCo’s computational gap. Theorem 3.2 gives a strategyproof mechanism with a distortion guarantee; it does not analyze the complexity of a hard computational social-choice problem. BALANCED already has a direct implementation by sorting locations and balancing group counts. Compressing repeated \((x,g)\) types gives a support-based implementation, but the paper’s argument uses those counts directly. There is no pricing problem or evident complexity frontier for continuous optimization technology to unlock.
The incentive issue sharpens that concern. In an atomless society, one person’s report changes no mass, so individual strategyproofness is vacuous. The proponent avoids this by requiring strategyproofness on every finite realization of the same rational distribution. That is coherent, and it matches the programme’s high-multiplicity idea, but it makes the mirror a family of replicated finite games rather than a new nonatomic incentive model. Requiring incentives for positive-mass coalitions would create a different problem, not a better mirror of Theorem 3.2.
Those objections do not defeat the anchor. The paper has a named, constructive result; the population can plausibly have repeated location-and-group types; and the normalized objective differs from the paper’s objective only by a common population-size factor. The finite-realization definition preserves the original deviation condition, and the mechanism and approximation proof transfer naturally. High multiplicity is expressly in scope, so neither the replication interpretation nor the easy transfer is a sound reason to reject the mirror.
I cannot make a strong case that no worthwhile mirror exists. The best negative point is that this looks like a low-yield extension for ChoCo’s complexity programme, not that the continuous question is ill-posed. Theorem 3.2 remains a credible anchor, and the case against it is weak.
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.