| paper | Automated Design of Affine Maximizer Mechanisms in Dynamic Settings |
| authors | — |
| venue | AAAI 2024 |
| filed under | unclassified |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | unclear |
The paper contains no numbered result asserting a computational complexity or algorithmic guarantee of the required kind; Theorems 4.1–4.4 concern differentiability and convergence. The proposed fluid formulation also changes individual makespan into average load and omits the paper’s exclusion-based incentive and payment structure. Therefore no anchor satisfies both gates.
fails bit a — no named computational result to mirror
No anchor is greened; the decisive objections are the absence of a qualifying computational theorem and the loss of individual makespan and AMA incentive structure in the proposed fluid model.
fatal: True
The proposed mirror covers only dynamic truthful task scheduling and AMA parameter search; the sequential-sales, gridworld, revenue, and remaining analytic results provide no qualifying computational anchor.
The strict answer is that this paper has no qualifying named complexity anchor. It contains no numbered theorem or proposition asserting that a problem is in P, NP-hard, FPT, W[1]-hard, or similar. Its named results are analytic:
Algorithm 1 and the experiments are computational contributions, but not named complexity results. Thus, under the programme’s strict Gate-A standard, this paper has no formal anchor. The strongest positive case is conditional on accepting such an analytic computational guarantee as an anchor.
My lead mirror is Fluid-AMA Makespan Design$_\infty$, based on the paper’s dynamic truthful task-scheduling problem and anchored to Theorem 4.3 (Pointwise convergence of regularised loss), proved in this paper.
Take a large pool of workers. A type \(t\) is a complete worker description: its full cost vector \(\theta_t=(\theta_{t,1},\ldots,\theta_{t,H})\), eligibility, and any other parameter used by the mechanism. The society is a rational distribution \(\mu\in\Delta_\tau\), where \(\mu_t\) is the fraction of workers of type \(t\). A plausible regime is a cloud-computing or crowdsourcing pool with millions of workers but perhaps only tens of machine or skill-cost profiles.
Suppose task batch \(h\) contains \(q_h\) normalized, identical task instances. Let \(y_{h,t}\geq 0\) be the mass of batch \(h\) assigned to type \(t\), with
\[ \sum_t y_{h,t}=q_h. \]
The affine-maximizer follower, given type weights \(w_t\) and boosts \(b_{h,t}\), chooses the lexicographically least maximizer
\[ y_{w,b}\in\arg\max_{y} \sum_{h,t}y_{h,t}\bigl(b_{h,t}-w_t\theta_{t,h}\bigr). \]
The designer chooses \(w,b\), subject to explicit rational bounds and a normalization such as \(\sum_t\mu_tw_t=1\), to minimize the induced fluid makespan
\[ \operatorname{MS}_\infty(w,b) = \max_{t:\mu_t>0} \frac{1}{\mu_t} \sum_h \theta_{t,h}y_{w,b,h,t}. \]
The decision version asks whether some admissible \(w,b\) induce makespan at most \(K\); an approximation version asks for \(w,b\) within \(\varepsilon\) of the optimum, together with an occupancy-flow or LP certificate that \(y_{w,b}\) is the follower’s optimum.
This is recognisably the paper’s problem. Its original reward is \(r_{i,h}=-x_{i,h}t_{i,h}\); the mirror replaces the named workers by masses of exchangeable workers and replaces one-hot assignments by aggregate assignment counts. A finite \(N\)-replication with \(N\mu_t\) workers of type \(t\) and \(Nq_h\) copies of each task batch realizes the same \(y\) asymptotically. Thus this is a high-multiplicity version, not merely fractional outcomes or a noise model.
The expected classification is mixed. For fixed \(w,b\), the follower is an LP and should be polynomial-time solvable in the finite type/batch representation. The entropy-regularised follower is uniquely solvable and smooth; Theorem 4.3 gives convergence of its loss to the unregularised loss as the regularisation parameter tends to zero. Theorem 4.1 supplies the differentiability rationale for outer gradient methods under a continuous or generic type distribution.
The full exact outer problem is not established as polynomial. I would expect the fixed-regularisation, approximate-stationary-point version to be a Class-A candidate, while global exact AMA design may be continuum-specifically hard or remain open. There is no discrete hardness theorem in this paper from which hardness could transfer.
The mirror covers only the dynamic truthful task-scheduling part of the paper and its AMA parameter-search problem. I would not anchor on Lemma 4.2 or Corollary 4.4 for a revenue mirror: with atomless agents, an individual has zero influence on the aggregate policy, so pivot payments and revenue can degenerate.
That is also the weakest point of the positive case. Exact individual strategyproofness is natural in the finite-\(N\) replicas but becomes delicate in the atomless limit. The mirror is strongest when stated as a high-multiplicity limit of the paper’s finite-worker task-scheduling problem, with makespan as the objective. If a referee requires a nondegenerate continuum payment rule for every infinitesimal agent, this case fails.
The strongest negative case is decisive at the programme’s own gate: this paper has no qualifying computational anchor. Theorem 4.1, Lemma 4.2, Theorem 4.3, and Corollary 4.4 are analytic statements about differentiability and convergence. None gives a worst-case complexity bound, an exact algorithm, an approximation scheme, or a parameterized result. Algorithm 1 is a heuristic local-optimization procedure, and the experiments provide no guarantee. Thus there is no named computational result whose continuous counterpart this programme could classify.
Even granting the proponent’s broader interpretation, Fluid-AMA Makespan Design is not the claimed mirror of Theorem 4.3. The theorem is pointwise convergence for a fixed finite MDP, reward profile, and parameter vector. It gives no computable relation between the regularization parameter and an \(\varepsilon\)-error, no uniform convergence over the outer variables \(w,b\), and no convergence of globally optimal AMA parameters. The proposed decision problem—whether some \(w,b\) induce a policy with makespan at most \(K\)—is still a bilevel optimization problem. An LP certificate can certify that a proposed allocation is optimal for fixed \(w,b\); it cannot certify that the outer parameters are optimal. Rational bounds, normalization, and an approximation target would all have to be added by a new paper.
There is also a substantive mismatch in the proposed fluid objective. The paper’s makespan is a maximum over individual workers’ accumulated loads. The aggregate vector \(y_{h,t}\) records only how much work is assigned to type \(t\). It does not record how that work is distributed among workers of that type: two assignments with identical \(y\) can have completely different makespans. The formula dividing total type workload by \(\mu_t\) silently replaces maximum individual load by perfectly balanced average load. That can define a sensible divisible-scheduling problem, but it is not the paper’s makespan problem without an additional balancing theorem.
The faithful repair is worse for the proposed mirror. To preserve individual makespan, the state must distinguish workers of the same cost type by their current loads or assignment histories. Those become part of the complete type description under ChoCo’s own definition. The number of such types grows with the horizon and task multiplicities, or becomes a continuous load distribution. The result is a measure-valued dynamic-control problem, not the finite-type occupancy LP to which Theorem 4.3 applies. If one instead retains only cost types and assumes perfect fluid balancing, the interesting individual-level objective has been changed.
The strategic mechanism-design content also disappears in the atomless limit. The AMA payment formula is built around excluding a particular agent, \(asw^{(-i)}\). An infinitesimal agent has zero effect on the aggregate policy, so ordinary individual incentive constraints and exclusion payments become vacuous or degenerate. A nontrivial limit would require marginal, coalition, or per-unit incentive constraints and a new payment theory. The proponent’s formulation omits payments entirely; it is therefore a weighted fluid scheduling problem, not a continuous version of the paper’s truthful dynamic mechanism.
A revenue mirror does not repair the case. Lemma 4.2 and Corollary 4.4 concern the finite-agent AMA payment construction, whose continuum analogue has the same exclusion problem. One could invent a nondegenerate marginal-revenue model, but that would be a new nonatomic mechanism-design programme rather than a computational result inherited from this paper.
It is fair to concede that large pools of workers sharing cost profiles are a plausible high-multiplicity regime; that is not an objection. The objection is narrower and stronger: once the model is made faithful, the named theorem supplies no complexity result and the finite-type simplification loses either makespan or incentive compatibility. A standalone mean-field scheduling project might still be worthwhile, but this paper does not furnish a worthwhile continuous mirror under ChoCo’s stated computational standard.
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.