| paper | d4-conf-ecai-2023-0003 |
| 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: A universal deterministic family, truthful on every finite individual-edge report profile, achieves $\alpha=e/(e-1)<2$ with a template-dependent constant additive loss at all sufficiently large admissible scales. Hence $\alpha_*\leq e/(e-1)<2$, settling the stated dichotomy. · discrete side: other · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given finite task classes \(J\), worker types \(\Theta\) with eligible sets \(N_\theta\subseteq J\) and capacities \(b_\theta\), rational masses \(\mu_\theta\), per-capita task supplies \(s_j\), and task values \(q_j\), let \(I_n\) be the integral realization with \(n\mu_\theta\) workers of type \(\theta\) and \(ns_j\) tasks of class \(j\). Determine the least \(\alpha\) for which a deterministic mechanism family \(M_n\), individually truthful against edge hiding at every scale, guarantees \(W(M_n(I_n))\geq \mathrm{OPT}(I_n)/\alpha-o(n)\) across fixed-support templates; does the paper's \(2\)-barrier persist?
The society is the distribution \(\mu\) over complete worker types \(\theta=(N_\theta,b_\theta)\), with task classes having values \(q_j\) and per-capita supplies \(s_j\). Its aggregate allocation has variables \(x_{\theta j}\), with \(x_{\theta j}=0\) when \(j\notin N_\theta\), \(\sum_j x_{\theta j}\leq b_\theta\mu_\theta\), and \(\sum_\theta x_{\theta j}\leq s_j\); welfare is \(\sum_{\theta,j}q_jx_{\theta j}\). The aggregate variables represent averages of integral matchings, while exact individual truthfulness is required of each finite-scale mechanism \(M_n\).
Theorem 3's two-agent gadget has not been replicated on fixed-support templates: proportional supplies make copies substitutes, and one deviation changes only \(O(1)\) assignments against \(\Theta(n)\) welfare; the proponent flags this gap but does not resolve it.
fatal: False
The mirror covers the truthful approximation results in Theorems 2 and 3. It leaves the Nash-equilibrium, \(\mathrm{PoA}\) and \(\mathrm{PoS}\), group-strategyproofness, input-class truthfulness, and capacity-reporting results aside.
The best positive case is an asymptotic high-multiplicity version of the paper’s truthful-approximation results. The paper has no named NP-hardness, polynomial-time, or parameterized-complexity theorem. Its closest computational anchors are approximation guarantees for mechanisms, with Theorem 3 giving the most useful lower bound.
Take a fixed finite set \(J\) of task classes. Class \(j\) has public value \(q_j>0\) and supply \(s_j\) per agent. A worker type is \(\theta=(N_\theta,b_\theta)\): the worker can do every task in the classes \(N_\theta\subseteq J\), and has capacity \(b_\theta\). The society is a rational distribution \(\mu\) over a finite support \(\Theta\), with \(\sum_\theta\mu_\theta=1\). At scale \(n\), there are \(n\mu_\theta\) workers of each type and \(ns_j\) copies of each task class, along a sequence of scales where these counts are integral. Workers may hide existing edges but cannot invent them; a mechanism returns an integral matching at each scale.
The continuous allocation \(x_{\theta j}\) is the number of class-\(j\) assignments to type \(\theta\), divided by \(n\). It satisfies
\[
x_{\theta j}=0\quad(j\notin N_\theta),\qquad
\sum_j x_{\theta j}\le b_\theta\mu_\theta,\qquad
\sum_\theta x_{\theta j}\le s_j.
\]
Its welfare is \(\sum_{\theta,j}q_jx_{\theta j}\). Thus the matching remains integral for each worker; fractional values describe averages over a large cohort. A plausible regime is a large institution with many workers in a modest number of roles, where workers in each role have the same eligible task classes and capacity, and standardized projects or publication slots scale with the workforce. The paper’s own worker-project and academic-publication examples fit this regime, and its Theorem 13 already studies classes of agents with shared neighborhoods and capacities.
My lead anchor is Theorem 3, proved in this paper: no deterministic truthful mechanism for MVbM can achieve approximation ratio better than \(2\). In full, for agent edge manipulation, every deterministic mechanism that is truthful cannot guarantee welfare better than half of the maximum matching welfare in the worst case. The continuous question is: what is the best asymptotic worst-case approximation ratio of any deterministic, individually truthful mechanism family \(M_n\) on these scaled societies? More precisely, determine the least \(\alpha\) for which such a family guarantees welfare at least \(\mathrm{OPT}_n/\alpha-o(n)\), uniformly over the fixed finite type and task-class templates in scope. A solution must give a truthful mechanism family and a matching asymptotic lower bound, or improve one of them. I expect the threshold to remain \(2\): the source lower bound arises from a small incentive conflict over who gets a high-value task, and that conflict seems replicable with fixed type classes and supplies proportional to population. In the programme’s terms, this is a likely hardness-transfer result, though it is an approximation impossibility, not NP-hardness.
The companion anchor is Theorem 2, stated here and proved in part here: \(MAP\) is truthful against edge hiding and has approximation ratio \(2\). The paper establishes truthfulness using Lemma 1; its ratio argument adapts the approximation result of Dobrian et al. [19] and supplies a tight example. Its continuous question is to compute the limiting aggregate allocation of \(MAP_n\), obtained by applying the paper’s mechanism to each scaled instance with a fixed public task and agent order, and prove the limiting truthfulness and factor-\(2\) guarantee. The type-level computation should be tractable: with a fixed number of types and task classes, the greedy process can advance through only finitely many type/class breakpoints rather than all \(n\) workers. The expected answer is again a tight factor of \(2\), paired with the lower bound above.
These questions mirror the mechanism-design problem, not just the underlying welfare maximization: the latter is a capacitated matching flow and is tractable. The paper’s Nash-equilibrium and PoA/PoS results are outside this proposed mirror.
The weak point is the lower-bound transfer. Theorem 3’s proof uses a two-agent, two-task instance; it does not itself prove an asymptotic bound when the number of types stays fixed and the population grows. Nor does it establish that cohort averaging or mass-level allocation preserves the same incentive constraints. A prover would need a replicated-gadget argument that respects the type structure and task supplies. That gap is real, but it is also a well-defined continuous question: does the paper’s factor-\(2\) truthful-mechanism barrier survive when the population grows while its type support stays small?
The paper has computational anchors, so “there is nothing here to mirror” would be too strong. And the population story is credible: large organizations can have many workers with the same eligibility sets and capacities. Theorem 13’s shared-agent classes support that regime. The better objection is that the proposed mirrors do not yet preserve the paper’s strategic problem when they pass to population masses.
For Theorem 3, the key lower-bound gadget has two agents and two scarce tasks. One agent hiding one edge can change who gets a task worth \(1+\varepsilon\). Replicating that gadget independently requires keeping its copies separate; with fixed worker types and task classes, copies instead become substitutes for one another. A single worker’s deviation can then change only \(O(1)\) assignments while total welfare is \(O(n)\). The factor-\(2\) argument does not simply scale with the population.
That scaling exposes the central mismatch. A society distribution records mass by type, but one worker’s report changes the distribution by only \(1/n\). The aggregate allocation limit can therefore erase the change that determines whether that worker’s payoff rises. A mass-level deviation would remain visible, but it represents a coalition or a positive fraction of the workforce changing reports, which is a different incentive question. One can retain individual truthfulness by studying finite mechanisms \(M_n\), as the proponent proposes; then the question is a high-multiplicity asymptotic mechanism-design problem. It is coherent, but it is not yet a computational question about a continuous society, and the two-agent theorem does not supply its asymptotic lower bound. Giving each gadget or priority position its own type could restore the conflict, but the support would then grow with \(n\), losing the fixed-support regime that makes the mirror attractive.
Theorem 2 has the same issue, and its proposed limit adds little on its own. At every finite scale, the paper already establishes MAP’s truthfulness and factor-\(2\) guarantee. A limiting aggregate allocation would need to preserve the per-worker incentive comparison, which the mass allocation alone does not record. With agents grouped in a fixed priority order, the allocation can be described by a finite greedy calculation over type counts; with arbitrary named priorities, the type distribution omits information that can affect MAP’s output. The first version looks like a compact description of the existing mechanism, while the second must enrich the model with priority information. Neither establishes a new continuous complexity question.
A stronger alternative would ask whether any truthful mechanism family achieves a better asymptotic ratio on fixed-support templates. That avoids merely taking MAP’s limit, but it is precisely the unproved transfer the proponent identifies. The paper’s lower bound neither answers it nor shows that replication preserves its incentive conflict. One could instead study manipulation by positive-mass groups, but that changes individual truthfulness into a coalition question.
So the negative case is about fit, not impossibility: a meaningful high-multiplicity regime exists, and the proposed asymptotic question may be worth pursuing. Its weak point is also its main one—the natural mirrors either retain finite, identity-sensitive incentives and become asymptotic discrete mechanism design, or aggregate to masses and lose the pivotal deviations that drive the paper’s results. I would not treat the stated MAP limit as a surviving continuous mirror, and I would require a clear mass-level incentive model and a genuine asymptotic lower-bound formulation before counting Theorem 3 as one.
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.