| paper | d4-conf-aaai-2017-0044 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Polynomial-time solvable in \(m,\tau,L\), independently of the refinement size \(n\). · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 5
statement extracted from the paper’s text layer
Given an interval \([a,b]\) and a finite-support rational distribution \(\mu\) over residents’ ideal locations, design a deterministic mechanism that takes the reported distribution \(\nu\), chooses a facility location \(x(\nu)\), and assigns per-capita payments \(p(r,\nu)\le 0\). Require that the mechanism be OSP with monitoring on every finite equal-mass refinement of \(\mu\), where an agent of true location \(t\) who reports \(r\) incurs cost \(\max\{|t-x(\nu)|,|r-x(\nu)|\}-p(r,\nu)\). On truthful reports, the facility must minimize \(\int |t-x|\,d\mu(t)\).
Use the weighted leftmost median \(x(\nu)=\inf\{z:\nu([a,z])\ge \tfrac12\}\) and charge \(p(r,\nu)=|r-x(\nu)|-(b-a)\) per capita. On each finite equal-mass refinement, truthful reporting gives monitored cost \(b-a\), while any lie gives cost at least \(b-a\); the truthful facility location minimizes the population’s average travel cost.
The refinement condition retains finite individual deviations, so it does not establish a nonvacuous OSP notion for a genuinely atomless population; the weighted-median computation also adds little complexity.
fatal: False
Covers Theorem 5’s optimal OSP facility-location mechanism with monitoring and charges. It leaves aside the scheduling results, the no-monitoring approximation bounds, the no-money lower bounds, and the optimized payment results.
The strongest mirror I believe is facility location with monitoring and charges, anchored on Theorem 5. Proved in this paper, it says that on a common interval \([a,b]\), the interval mechanism chooses the leftmost median of the reported locations and sets \(p_i=|x_i-f(x)|-(b-a)\). It returns an optimal facility location, is OSP with monitoring, and charges agents rather than paying them.
A plausible high-multiplicity setting is a city choosing a site for a public facility. There may be millions of residents but relatively few distinct neighborhoods or registered addresses. A type is a resident’s ideal location, together with the same travel-cost rule and monitoring conditions; \(\mu_t\) is the share of residents of type \(t\). Thus \(N\) can be large while the truthful support \(\tau\) is modest.
My proposed problem is \(\mathrm{FL}_{\infty}^{\mathrm{OSP,mon,charge}}\). Its input is \([a,b]\) and a finite-support rational distribution \(\mu\) over locations. A report profile induces a distribution \(\nu\) of reported locations; equivalently, mass of each true type is transferred among reported locations. The task is to give a deterministic mechanism that chooses a facility \(x(\nu)\), assigns per-capita payments \(p(r,\nu)\le 0\), and is OSP with monitoring on every finite equal-mass refinement of the input society. On truthful reports, it must minimize
\[ C_\mu(x)=\int |t-x|\,d\mu(t). \]
A solution is a rule and an OSP proof, not just a formula for the best location. The rule suggested by Theorem 5 is the weighted leftmost median,
\[ x(\nu)=\inf\{z:\nu([a,z])\ge \tfrac12\}, \qquad p(r,\nu)=|r-x(\nu)|-(b-a). \]
For a resident with true location \(t\) who reports \(r\), monitoring gives cost \(\max\{|t-x|,|r-x|\}-p(r,\nu)\). Truthful reporting gives cost \(b-a\); every lie gives at least \(b-a\). The rule is therefore OSP at each finite refinement, while its truthful outcome minimizes the population’s aggregate travel cost. With rational support points and masses, the weighted median and the compressed payment rule are computable in polynomial time in the report support size and bit length. I expect this mirror to be tractable.
This is a population continuization: the input and objective use a mass distribution over resident types. The facility’s real-valued location is already in the paper; it is not the point of the mirror. The co-modification is the natural replacement of the sum of residents’ costs by its population average.
The main limitation is strategic. In a purely atomless model, one person has zero mass, so individual OSP can become vacuous. I therefore define the continuous question through a refinement-stable family: the measure-level rule must remain OSP for every finite high-multiplicity realization. That preserves the paper’s individual incentive notion, but leaves open whether authors seeking a genuinely atomless notion of OSP would accept this as their continuous problem.
I would not use Theorem 4’s no-money impossibility as an anchor for this case: it imposes a different transfer constraint. A natural next question is whether its lower bound has a meaningful refinement-stable limit when population shares replace unit counts.
The strongest objection is about fit to ChoCo’s computational agenda. Theorem 5 is an implementability result: monitoring makes an optimal OSP mechanism possible, and the interval bound lets the authors charge agents instead of paying them. Theorem 1 already supplies the general mechanism construction; the facility-location algorithm is the median. For a rational distribution over \(\tau\) locations, the corresponding weighted median is easy to compute. There is no hard pricing problem or complexity boundary here for continuous optimization to expose.
That objection is limited. An easy Class A result can still be a worthwhile mirror, and the proposed city with many residents at a modest number of ideal locations is a credible high-multiplicity regime. Shared location and cost make those residents a legitimate type; the fact that the paper’s original facility location problem has finitely many agents does not rule out that regime.
The deeper concern is what “continuous OSP” means. The proposed refinement-stable definition keeps finite individuals and tests their unilateral deviations, so it asks for the finite-agent OSP property across refinements of a mass distribution. In a genuinely atomless population, one resident’s report does not change the reported distribution or the facility location. Theorem 5’s monitoring charge can still make truth-telling optimal, but the result then rests on a fixed per-capita charge and the general monitoring construction, rather than a nontrivial interaction between population mass and the OSP constraint. That makes the mirror look like a direct extension of the paper’s mechanism, not a new computational question. Still, refinement stability is a coherent choice, and I can’t rule out the authors recognizing it as their problem.
The no-money follow-up is also hard to dismiss outright. Its \(n\)-dependent bound does not itself define a limit, and an atomless formulation needs a clear account of what OSP compares when one person has zero mass. But asking for a guarantee uniform over finite refinements would be a well-posed alternative, so this concern does not defeat that possible mirror either.
I can make a negative case that the paper offers little of ChoCo’s intended complexity landscape, and that its strongest mirror may be a routine weighted-median extension. I cannot honestly establish that no worthwhile mirror exists: Theorem 5 survives the stronger objections, and the city regime is plausible. The negative case is therefore weak on the programme’s stated test.
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.