| paper | Task Allocation on Networks with Execution Uncertainty (Extended Abstract)∗ |
| authors | Yao Zhang, Xiuzhen Zhang, Dengji Zhao |
| venue | IJCAI 2023 |
| filed under | frontier · tools-data |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | no |
The paper has no numbered result about the complexity or algorithmics of a computational problem: Theorems 1–3 establish mechanism-design axioms, while Proposition 1 is an axiomatic impossibility theorem. Thus bit (a) fails regardless of whether a useful mass extension could be invented. The opponent also shows that the proposed role-template extension changes the referral structure and leaves positive masses computationally irrelevant.
fails bit a — no named computational result to mirror
No eligible result is covered; the proposed extension leaves all four named results as mechanism-design properties over an altered network model.
The strongest honest positive case is a near-miss: this paper has no qualifying named computational result, so it cannot support a ChoCo mirror under the programme’s anchor rule.
Its named results are:
These are mechanism-design properties and an impossibility theorem, not results establishing membership in \(P\), NP-hardness, parameterized complexity, approximation guarantees, or a running-time bound. Thus there are zero eligible computational anchors, and strictly speaking there is no anchor-specific continuous problem or Class A/B/C verdict to give.
The best non-qualifying extension would be a “Mass-PEV Diffusion” problem. Fix a finite role graph \(H=(\{s\}\cup R,F)\), a finite quality set \(Q\), rational masses \(\mu_r\) with \(\sum_{r\in R}\mu_r=1\), and for every role \(r\) a common quality distribution \(f_r\) and cost \(c_r\). A role represents a large cohort of workers with the same execution uncertainty, cost, and network position; the role graph describes a repeated referral-network template. Reports contain \(f'_r\), \(c'_r\), and a subset \(F'\subseteq F\) of revealed invitations. The mechanism must select a reachable role maximizing
\[
\mathbb{E}_{f'_r}[Q]-c'_r,
\]
compute the critical-role chain in \(H[F']\), and output a task-selection lottery and realized-quality-dependent payments. The solution must satisfy truthful reporting and full invitation revelation as dominant cohort actions, expected IR, and expected WBB.
This is plausible in a crowdsourcing platform with many repeated referral branches: \(\mu_r\) is the fraction of workers in each network role, and clearing denominators recovers a finite blow-up with many clone workers and few role types. Evaluation for a fixed role template would probably be tractable by enumerating roles and critical-role deletions. But that is an extension, not a result established by the paper.
The weakest point is decisive: the original mechanism’s incentives depend on named agents, individual critical paths, and a single indivisible task. In an atomless population, one worker has zero influence; replacing individual deviations by cohort deviations changes IC. Replacing the original graph by a role graph or graphon also changes the network problem. Hence the paper offers a plausible continuous-mechanism-design direction, but no defensible direct computational mirror under the stated ChoCo standard.
The negative case starts with a formal disqualification: this paper supplies no eligible computational anchor. Theorem 1, Theorem 2, and Theorem 3 assert incentive compatibility, individual rationality, and budget balance; Proposition 1 is an impossibility theorem for those same axioms plus efficiency. None gives a complexity classification, an algorithmic guarantee, an approximation result, or even a running-time bound. Under ChoCo’s explicit anchor rule, there is therefore no paper result to continuize.
The best proposed replacement, a Mass-PEV Diffusion mechanism, does not repair this. With one indivisible task, a role distribution \(\mu\) contributes only its support. If role \(r\) has value
\[ v_r=\mathbb{E}_{f_r}[Q]-c_r, \]
then selection is simply
\[ \arg\max_{r:\mu_r>0} v_r. \]
Changing a positive mass from \(1\%\) to \(50\%\) changes nothing. The task is still assigned to one worker, not to a quantity of worker mass. The threshold payments and critical-agent calculations likewise depend on which particular agents and paths exist, not on how much mass is assigned to their role. Thus the proposed continuum is not a high-multiplicity relaxation in which the mass is computationally relevant; it is a finite role problem with redundant labels.
This is not an objection to high multiplicity in general. It is specific to this problem’s combination of a single winner and a referral graph. The network cannot be recovered from a distribution over worker types: \(r_i\) is a set of named neighbours, and criticality depends on global graph structure. Cloning a role changes that structure. Parallel copies can destroy a worker’s status as a critical agent; preserving the critical worker leaves an exceptional, individually identified vertex rather than an atomless population. A finite role graph \(H\) therefore either carries all the meaningful information itself, making \(\mu\) irrelevant, or changes individual agents into collective role-agents, which is a different mechanism-design model.
Theorem 1 is especially weak as a mirror. It is imported from prior work and concerns the IDM in a deterministic single-task setting. A continuum version has only bad choices: if a worker is genuinely atomless, her deviation has no population effect and individual IC risks becoming vacuous; if she remains a pivotal bridge in the referral network, her identity and exact position must be retained, so the relevant object is still an individual graph, not a society distribution. In neither case is there a computational population problem corresponding to the theorem.
Theorem 2 does not fare better. PDM pays the selected worker according to the realised value \(q_\pi\), which is one execution draw. Replacing many identical workers by their common distribution \(f_r\) does not average that draw away: only one worker performs the task. To obtain a law-of-large-numbers or mass-quality interpretation, one must assign many tasks or a divisible task to a cohort. That would leave the paper’s single-task model and enter outcome or task-stream continuization, both outside the programme’s scope.
Theorem 3 is even more tied to individuation. Its conditions refer to “the next agent” in a critical chain, deletion of named critical children, and monotonicity of a particular agent’s reported neighbour set. In an atomless graph or graphon, pointwise critical agents are generally measure-zero and the chain is undefined or disappears. In a role-template model, the chain is restored only by inserting a finite combinatorial skeleton; the masses still do no work. The PCDM therefore cannot yield a genuine continuous-population computational question.
Finally, Proposition 1 can be restated over cohorts, but that would merely produce another axiomatic impossibility result, not a computational anchor. If individual IC is retained, atomlessness can make the impossibility degenerate; if group or role-level IC is imposed, the quantifiers and strategic agents have changed, so the result is new rather than a mirror of Proposition 1.
There is a plausible research direction here—continuum crowdsourcing with many tasks, graphon-based diffusion, and aggregate execution quality—but it would be a new mechanism-design programme. It would not continuize any named computational result in this paper, and it would rely on precisely the modelling changes the paper’s theorems do not survive. The honest negative verdict is therefore strong as a ChoCo screening decision, though not as a universal claim that no related continuous mechanism-design problem could ever be worthwhile.
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.