| paper | d4-conf-ecai-2025-0480 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→other discrete result → its continuous mirror
Answer: Such a mechanism exists in \(2^{O(k)}\operatorname{poly}(m,\tau,L,\log N)\) time. It is exactly strategyproof in expectation and satisfies \(D_F(\mu,x_t;x_t)=\mathrm{OPT}^{\max}_\infty(\mu,\kappa)\) for every truthful type. · discrete side: other · adjudication: proved
full proof & adversarial review →
Lemma 10
statement extracted from the paper’s text layer
Given a bounded rational interval \(B\), \(k\) facilities, a population scale \(N\), and integer capacities \(c_1,\ldots,c_k\) summing to \(N\), represent the agents by a distribution \(\mu\) over reported ideal locations, where each mass is a multiple of \(1/N\). Can one construct a randomized mechanism running in time \(2^{O(k)}\operatorname{poly}(\tau,L,\log N)\) that outputs facility locations and a feasible integral assignment, is exactly strategyproof when one agent changes their report (moving mass \(1/N\)), and gives every agent expected distance at most \(2\,\mathrm{OPT}^{\max}_\infty(\mu,\kappa)\)? Here \(\kappa_i=c_i/N\), and \(\mathrm{OPT}^{\max}_\infty\) is the minimum essential maximum distance when facilities lie in \(B\), assigned mass may be split among them, and facility \(i\) receives at most \(\kappa_i\) mass.
A one-dimensional high-multiplicity facility-location mechanism: location types carry masses \(\mu_x=n_x/N\); facility capacities scale as shares \(\kappa_i=c_i/N\); the mechanism chooses facility locations and an integral assignment for the \(N\) agents, while its approximation benchmark permits fractional assignment of mass.
Exact incentives depend on a deviation of mass \(1/N\), so the mirror covers a scalable high-multiplicity regime rather than a fully atomless strategic limit.
fatal: False
The mirror covers Lemma 10's maximum-cost ratio of \(2\) for arbitrary capacities without spare capacity. It leaves Lemma 10's social-cost ratio of \(n/2\), Lemma 9's lower bound, and the other capacity settings and results untouched.
The strongest mirror is the paper’s maximum-cost result for arbitrary capacities with no spare capacity. The paper does not give a named NP-hardness or polynomial-time classification. Its best named computational anchors are approximation results.
The lead anchor is Lemma 10, proved in this paper: for arbitrary facility capacities whose total equals the number of agents, Mechanism 3 is strategyproof and achieves approximation ratios \(n/2\) for social cost and \(2\) for maximum cost. I would mirror only the maximum-cost part. The social-cost bound depends directly on \(n\), so it has no comparably clean population limit.
Here is a concrete high-multiplicity question. Take a bounded rational interval \(B\), \(k\) facilities, a population scale \(N\), and integer capacities \(c_1,\ldots,c_k\) summing to \(N\). Represent the population by a distribution \(\mu\) on ideal locations \(x\in B\), with each mass \(\mu_x=n_x/N\). A type is the ideal location; agents of that type have the same distance costs and all other attributes used by the model. The regime is a large regional service population—say, residents choosing ideal locations along a corridor—with \(N\) large and support size \(\tau\) much smaller than \(N\). Capacities scale with the population as shares \(\kappa_i=c_i/N\).
Call the question HM-Max2: for each such domain, construct a randomized mechanism that maps every reported histogram to facility locations and a feasible assignment, runs in time \(2^{O(k)}\operatorname{poly}(\tau,L,\log N)\), and has maximum expected distance at most twice the continuous optimum. The benchmark \(\mathrm{OPT}^{\max}_\infty(\mu,\kappa)\) is the minimum possible essential maximum distance when facilities are placed in \(B\), mass may be split among facilities, and facility \(i\) receives at most \(\kappa_i\) mass. The mechanism must be exactly strategyproof: one agent’s misreport moves mass \(1/N\) from their true location \(x\) to a reported location \(y\), and cannot lower that agent’s expected distance.
A solution is a mechanism algorithm, together with proofs of its capacity feasibility, one-agent incentive constraint, approximation guarantee, and running time. This is not answered merely by writing a fractional assignment LP: the mechanism has to remain strategyproof after every one-agent change to the histogram. I would expect an FPT-in-\(k\) result to be plausible. The one-dimensional order and interval structure behind Mechanism 3 suggest that its dynamic program might be compressed from population-sized states to support-sized states. Whether that compression preserves exact incentives is the central question.
A useful second anchor is Lemma 9, also proved here: with at least two facilities, every randomized strategyproof mechanism in the equal-capacity setting with spare capacity has maximum-cost approximation ratio at least \(3/2\). Its separate mirror, HM-Max3/2, asks whether that lower bound still holds for high-multiplicity location distributions, with equal capacity shares whose total exceeds one, against the continuous maximum-cost benchmark. I expect the bound to transfer if its bad profiles can be represented by a fixed number of location types and replicated as \(N\) grows. This is a ratio-bound question, not a computational hardness classification.
These mirrors cover the maximum-cost results in Lemmas 10 and 9; they do not attempt to continuize the paper’s entire contribution. The continuous object is the population distribution. Facility locations were already continuous in the paper, and that alone is not the mirror.
The weak point is the incentive model. A strict atomless population makes a single agent’s deviation have zero mass, so ordinary individual strategyproofness can become vacuous. HM-Max2 avoids that by retaining a declared scale \(N\) and testing deviations of mass \(1/N\). That makes it a high-multiplicity mirror with a finite strategic grain, rather than a pure atomless model. An alternative would impose truthfulness against positive-mass cohorts, but that changes the paper’s individual-strategyproofness question. The declared scale is the more faithful bridge here: it keeps the original incentive constraint while making the society available as a compact distribution over types.
The strongest negative is a mismatch between what these lemmas establish and what ChoCo is trying to chart. Lemma 10 gives a strategyproof mechanism and approximation ratios; Lemma 9 bounds the ratios achievable by any randomized strategyproof mechanism. The paper’s dynamic program implements a mechanism, but these anchors do not classify the complexity of a computational problem. A continuous version of either ratio claim would primarily be a new mechanism-design guarantee, not a missing complexity result of the kind the programme is organized around.
HM-Max2 is strongest when stated with a finite scale \(N\), rational masses, scaled capacities, and deviations of size \(1/N\). That is also where its main limitation appears: the scale is essential to the incentive constraint. Keep it, and the strategic problem is still the finite-agent game, written as a histogram. Remove it and take a nonatomic limit, and an individual’s report changes no mass, so individual strategyproofness becomes vacuous. Requiring truthful behavior under positive-mass deviations would avoid that, but would replace the paper’s individual incentive condition with a different one.
There is a credible large-population scenario for the histogram—for example, residents sharing a finite set of service locations, with facility capacities scaling with the population. So “there can be no repeated types” is not a sound objection. But the best version of HM-Max2 then asks for a compact implementation of the paper’s mechanism on repeated-agent inputs. The paper’s dynamic program already orders agents by location and partitions them into capacity-sized contiguous groups; its relevant cut locations can be represented by weighted quantiles of the support. That makes a support-based implementation plausible. If this yields an interesting runtime theorem, it would be useful high-multiplicity algorithmics, but it would not rescue the claimed continuous strategic limit: exact incentives still rely on the finite grain.
HM-Max3/2 faces the same fork. For a pure continuum, the individual strategyproofness premise behind the lower bound no longer constrains the mechanism, so the \(3/2\) claim is not a faithful limit of Lemma 9. With finite-grain deviations, it becomes a lower bound for a restricted family of finite strategic games encoded by distributions. A replicated witness might establish it, or the restriction might permit a different mechanism; either way, the result concerns finite-scale mechanism design. A cohort-deviation formulation would pose a new game and would not mirror the lemma’s guarantee.
This negative case is not airtight. The programme explicitly treats high-multiplicity formulations as valuable, and a support-sensitive implementation of Mechanism 3 could be a worthwhile result on its own. The case against is narrower: these two anchors offer a weak fit to ChoCo’s computational-complexity agenda, and neither has a faithful limit that preserves the paper’s individual incentive condition while making the population genuinely continuous.
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.