| paper | d4-conf-ecai-2025-0451 |
| 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: Every deterministic strategyproof mechanism has unbounded worst-case welfare approximation ratio. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 3.1
statement extracted from the paper’s text layer
For fixed \(k\ge2\), given finite candidate sites \(C\subseteq[0,1]\), an integer \(N\), and a society of types \(t=(x_t,\alpha_t)\) with rational masses \(\mu_t=n_t/N\), can any deterministic direct mechanism have a finite worst-case approximation ratio when approvals are known and a resident may misreport their position, changing the reported masses by \(1/N\)?
Use a finite-support distribution \(\mu\) over position-and-approval types \(T\subseteq[0,1]\times\{0,1\}^k\), with \(\sum_t\mu_t=1\) and \(\mu_t=n_t/N\). A mechanism maps reports to a facility-site pair or lottery; type \(t\)'s utility for \((j,c)\) is \(\alpha_{t,j}(1-|x_t-c|)\), and welfare is its \(\mu\)-weighted sum. Truthfulness is tested against one resident's report change of mass \(1/N\); the objective is the worst-case ratio to optimal feasible welfare.
Covers the general-setting deterministic impossibility in Theorem 3.1 and the randomized lower and upper bounds in Theorems 3.2 and 3.4, with Theorem 3.3 supporting truthfulness. It leaves the known-position results in Section 4 aside.
The strongest positive case is a high-multiplicity mirror of the paper’s truthful mechanism-design problem: a large population is represented by masses on shared position-and-approval types. The paper’s numbered results are approximation bounds under strategyproofness, not NP-hardness results. So the claim here is that their strategic obstruction and randomized guarantee transfer to a continuous-population representation—not that the paper establishes a standard complexity-class result.
A plausible regime is regional facility planning with many residents concentrated in apartment blocks or neighborhoods, where residents share a location at the model’s resolution and an approval profile over facility types. Let a type be \(t=(x_t,\alpha_t)\), with \(x_t\in[0,1]\) and \(\alpha_t\in\{0,1\}^k\). The society is a distribution \(\mu\) supported on \(\tau\) such types. Take \(\mu_t=n_t/N\), where \(N\) is the population size and \(n_t\) is the number of residents of type \(t\); the intended regime has \(N\gg\tau\). Candidate sites \(C\subseteq[0,1]\) are finite. A mechanism chooses a facility-site pair \((j,c)\), or a lottery over such pairs. Its per-capita utility for type \(t\) under lottery \(p\) is
\[
u_t(p)=\sum_{j,c}p_{j,c}\alpha_{t,j}(1-|x_t-c|),
\]
and society’s welfare is \(\mathrm{SW}_\mu(p)=\sum_t\mu_tu_t(p)\).
To preserve the paper’s unilateral truthfulness condition, the continuous representation needs an explicit agent granularity: one resident has mass \(1/N\). A single resident’s report changes \(\mu\) to \(\mu-\frac1N e_t+\frac1N e_{t'}\); their incentive is evaluated using their *true* type’s utility. For the lead result, approvals remain known and only positions can be misreported, as in the theorem’s restriction. The solution to each question below is a mechanism, or a proof that the stated mechanism guarantee is impossible.
The lead anchor is Theorem 3.1, proved in this paper: *for every \(k\ge2\), every deterministic strategyproof mechanism has unbounded approximation ratio, even when agents’ preferences are known.* Its bad example survives with just two initial types and three after a deviation. For \(N=2M\), put \(M\) residents of each of two approval types at \(\varepsilon>0\), with one type approving only \(F_1\) and the other only \(F_2\), and set \(C=\{1\}\). Whichever facility the mechanism chooses, call it \(F_1\). Move one \(F_2\)-approving resident’s reported position to \(1\). Strategyproofness forces the mechanism still to choose \(F_1\): choosing \(F_2\) would give that resident positive utility instead of zero. Yet in the changed society, \(F_1\)’s welfare is \(M\varepsilon\), while \(F_2\)’s is \((M-1)(1-\varepsilon)+1\). The ratio is unbounded as \(\varepsilon\) tends to zero, for arbitrarily large \(N\) and fixed \(\tau\). This is the continuous question I find strongest:
High-Multiplicity Deterministic Truthful Facility Approximation. For each fixed \(k\ge2\), does there exist a deterministic direct mechanism, strategyproof against a single resident’s position misreport of mass \(1/N\), with a finite worst-case approximation ratio over rational type masses, candidate sets, and population sizes \(N\)? The expected answer is no: the paper’s impossibility transfers. This is B-like in the programme’s trichotomy—the obstruction is already present with a constant number of types and survives cloning. More precisely, it is an approximation impossibility, not an NP-hardness claim.
A second anchor is Theorem 3.2, also proved here: *for every \(k\ge2\), every randomized strategyproof mechanism has approximation ratio at least \(k\), even when preferences are known.* The corresponding question is to establish that lower bound for the same mass-based society and unilateral \(1/N\)-mass deviations. Replicate each of the theorem’s \(k\) single-facility approval types \(M\) times at \(\varepsilon\), so \(N=kM\), and choose a facility \(F_i\) receiving probability at most \(1/k\). Move one resident who approves only \(F_i\) to \(1\). Strategyproofness prevents the probability of \(F_i\) from increasing. As \(\varepsilon\) tends to zero, the mechanism’s welfare is at most \(1/k\) while the optimum tends to \(1\), giving the same lower bound. The paper’s Theorem 3.4, proved here, supplies the matching upper bound: its randomized mechanism has approximation ratio at most \(k\) for every \(k\ge2\). Thus the high-multiplicity minimax ratio is expected to be exactly \(k\), with the lower bound transferred and the paper’s construction furnishing the upper bound.
The scope is deliberately narrow: these mirrors cover the known-preferences, position-misreporting results in the general setting. They do not claim to mirror the known-positions preference-only results or to make the population a decision variable in an LP. The authors should recognize this as their problem represented through type masses: the facility choice, distance utility, truthful deviation, and welfare objective all remain intact. The approximation bounds even persist when the number of types stays small as the population grows.
The weakest point is also load-bearing: without the \(1/N\) strategic quantum, an atomless individual has zero effect on \(\mu\), and unilateral strategyproofness becomes vacuous. The proposed mirror therefore includes population mass as the continuous representation but retains individual-sized deviations. Removing that granularity would require a different strategic notion, such as cohort deviations, which would change the authors’ question. The result is a credible high-multiplicity mirror, but a modest one: it preserves the paper’s strategic difficulty rather than revealing a new continuous optimization landscape.
The strongest case against rests on the strategic unit. In an atomless society, one resident’s misreport does not change the distribution \(\mu\). A mechanism that sees only \(\mu\) therefore makes every resident strategyproof, and can simply choose the welfare-maximizing facility-site pair. Theorem 3.1’s impossibility and Theorem 3.2’s lower bound then lose their force; Theorem 3.4’s truthfulness guarantee is unnecessary. The same problem affects the preference-only results: an individual approval report has zero effect on the aggregate.
The proponent avoids that collapse by giving each resident mass \(1/N\). That preserves the paper’s incentives, and the claimed transfers of Theorems 3.1 and 3.2 are sound. But truthfulness now depends on which deviations are possible: the same \(\mu\) can come from populations of size \(N\) or \(2N\), with different deviation quanta. Include \(N\), and the model is a finite-agent game encoded by type counts; remove it, and the unilateral incentive constraint is unspecified. Treating positive-mass cohorts as strategic players would retain nontrivial incentives in a continuum, but it changes the solution concept from individual strategyproofness to group strategyproofness.
That leaves a credible high-multiplicity mechanism-design question, especially in the neighborhood scenario. The programme’s own rules say high multiplicity supports a mirror, so I would not dismiss it on that ground. The narrower objection is that the paper’s theorems bound the approximation ratio of truthful mechanisms; they do not classify the complexity of a computational problem over a continuous society. The proposed mirrors transfer those mechanism guarantees, rather than opening the programme’s intended complexity landscape. A new question about computation over mass distributions could be worthwhile, but it would need its own computational problem and result to mirror.
So the negative case is limited: it can argue that this paper does not fit ChoCo’s stated computational-complexity remit. It cannot honestly claim that the proponent’s high-multiplicity mirrors are ill-posed or uninteresting under a broader algorithmic mechanism-design remit.
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.