| paper | d4-conf-aaai-2026-3337 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
other→NP-hard discrete result → its continuous mirror
Answer: Attaining \(\frac{e-1}{(2e-1)\zeta}\) is \(\mathrm{NP}\)-hard for every prescribed constant \(\zeta\ge1\), even with one type and all capacities equal to one. · discrete side: other · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 2
Given \(A\) arms, \(\tau\) types with rational masses \(\mu_x\), a finite-support reward-vector law \(P_x\) for each type, per-capita arm capacities \(q_a\), a probe budget \(I\), and overhead \(\alpha\), choose a probe set \(S\), \(|S|\le I\), and assignment probabilities \(p_a(x,r_S)\). Here the observed group mass is \(\nu_S(x,r_S)=\mu_xP_x(r_S)\), and the probabilities must satisfy \(\sum_a p_a(x,r_S)=1\) and \(\sum_{x,r_S}\nu_S(x,r_S)p_a(x,r_S)\le q_a\). With \(v(x,r_S,a)=r_a\) for \(a\in S\) and \(v(x,r_S,a)=\mathbb E_{P_x}[R_a]\) otherwise, maximize \((1-\alpha(|S|))\exp\!\left(\sum_{x,r_S}\nu_S(x,r_S)\log\!\left(\sum_a p_a(x,r_S)v(x,r_S,a)\right)\right)\).
A nonatomic fair probing-and-assignment model over a finite support of driver types and probe-outcome groups, with per-capita arm capacities and geometric-mean welfare.
The mirror covers Theorem 2's offline probe selection and fair assignment; it does not establish Theorem 3's online regret guarantee or address the experiments.
The best case is the large, repeatable dispatch market: thousands of drivers per service period, but only a modest number of cohorts with the same reward distributions across service zones. A type is the full vector of a driver’s reward laws for every zone, along with the eligibility and assignment properties the model uses. Its mass is its fraction of the driver population. For example, drivers with the same home area, vehicle class, and zone-by-zone reward profile could form one type. The regime of interest has \(M\) drivers much larger than the number \(\tau\) of types.
Zones remain a finite set of arms. As the population grows, their service capacities must grow with it: write \(q_a\) for the fraction of the population that zone \(a\) can serve. That is a co-modification of the assignment model, of the kind the programme allows. Probing still selects zone categories; after observing probe results, the dispatcher assigns mass to zones subject to those capacities. This is recognizable as the paper’s problem: it keeps the probe-then-assign decision, the same arm reward information, and its fairness objective, while treating interchangeable drivers as a cohort.
My lead anchor is Theorem 3, proved in the paper’s main analysis and repeated as Theorem 6 in the appendix. It states that, for any \(\delta\in(0,1)\), OFMUP’s cumulative regret is, with probability at least \(1-\delta\), \(O\!\left(\zeta(\sqrt{MAT}+MA)\ln^c(MAT/\delta)\right)\) for some constant \(c>0\). The comparator is the per-round policy chosen with full knowledge of the reward means.
The continuous question I would hand to a prover is the Nonatomic Fair MA-MAB with Probing problem. Its input is a finite set of \(A\) zones; a finite support of \(\tau\) driver types with rational masses summing to one; a finite-support reward-vector distribution for each type; per-capita zone capacities \(q_a\); a probing budget and overhead function; and a horizon \(T\). The reward vector is part of the type’s complete description, so agents grouped together are indistinguishable in the model’s relevant respects.
At each round, the platform chooses a probe set \(S_t\), observes the reward marks for the probed zones across the population, then chooses a feasible mass-flow assignment \(y_t(x,r,a)\). This is the fraction of type \(x\) with observed probe outcomes \(r\) assigned to zone \(a\). It must assign at most the available mass of each observed type-outcome group, and total assigned mass to zone \(a\) cannot exceed \(q_a\). The group’s utility is the flow-weighted combination of probed realized rewards and unprobed means, as in the paper.
Use per-capita Nash welfare \(W_t=\exp(\int\log u_t(x,r)\,d\nu_{S_t}(x,r))\), where \(\nu_{S_t}\) is the population mass distribution over types and observed probe outcomes. The online task is to output an adaptive probing and assignment policy minimizing regret against the policy that knows the reward laws. In the nonatomic limit, the observed mass distribution of probe outcomes gives the type-level reward law directly. A natural target is to determine whether this makes regret bounded by the cost of learning the finite set of arm types, and how the corresponding finite-cohort bound depends on \(\tau,A,T\), rather than on the number \(M\) of named individuals. I expect a tractable learning problem under this ideal continuum-feedback model, with type-level pooling doing the work.
A second, worthwhile anchor is Theorem 2, also proved here and restated with proof in the appendix as Theorem 5. It says: for an optimal probe set \(S^*\), let \(j^\star\) maximize \((1-\alpha(|S_i|))f_{\mathrm{upper}}(S_i)\) over the greedy prefix candidates \(S_0,\ldots,S_I\), and set \(\zeta_0=(1-\alpha(|S_{j^\star}|))f_{\mathrm{upper}}(S_{j^\star})/\mathcal R(S_{j^\star})\). If \(\zeta\ge\max\{1,\zeta_0\}\), Algorithm 1 returns \(S^{\mathrm{pr}}\) satisfying \(\mathcal R(S^{\mathrm{pr}})\ge \frac{e-1}{2e-1}\frac{1}{\zeta}\mathcal R(S^*)\).
Its mirror is Continuum Fair Probing and Assignment. For each probe set \(S\), probing induces a mass distribution \(\nu_S\) over type and observed reward marks. An allocation is a measurable fractional flow \(y_a(x,r)\) that assigns at most the mass available at each \((x,r)\), respects zone capacities, and gives utility \(u(x,r)=\sum_{a\in S}y_a(x,r)r_a+\sum_{a\notin S}y_a(x,r)\mu_{x,a}\). Define \(\mathcal R_\infty(S)\) as \(1-\alpha(|S|)\) times the maximum per-capita Nash welfare over feasible flows. The problem is to choose a probe set and flow maximizing \(\mathcal R_\infty\); a solution is a feasible pair \((S,y)\) with an optimality certificate or a proved approximation guarantee. I expect approximation algorithms to be possible where the paper’s continuum surrogate retains its claimed submodularity: for a fixed probe set, the type-flow welfare problem is a concave optimization problem with finite input support, while probe selection can use the greedy structure. Exact optimization over probe sets need not be easy.
The manuscript’s sentence that “similar problems” are NP-hard cites earlier work; it is not a numbered hardness result asserted by this paper. Neither anchor is a hardness result, so this case supports new algorithmic questions, not a claim that the paper’s named discrete hardness dissolves.
The main soft spot is that the mirror needs real normalization and cannot inherit either theorem mechanically. A product of utilities over \(M\) people has no useful nonatomic limit, so I use the population geometric mean, which the paper itself treats as its fairness measure. But taking the \(M\)-th root also takes the \(M\)-th root of Theorem 2’s approximation ratio, which tends to one; its stated constant-factor guarantee does not survive unchanged. Likewise, Theorem 3’s finite-sample confidence analysis does not directly establish a regret bound for type masses with continuum feedback. Those are genuine questions for the mirror, not reasons to reject it: the authors’ central probe-and-assign problem remains intact, and repeated identical types make the population regime plausible.
The best case against is that the paper’s population size drives its learning problem, while its probe-selection problem is driven mainly by the number of arms. Repeating a finite set of genuinely identical agents changes the first sharply; it may leave the second largely intact.
For Theorem 3, suppose each type has infinitely many members and probing an arm reveals a fresh reward for every member, as the paper specifies. For finite-support reward laws, one probe round then reveals each probed type’s reward distribution exactly through its outcome proportions. The UCB estimation problem that motivates the theorem collapses: after the relevant arms have been probed, there is no sampling uncertainty of the kind the finite-agent regret bound controls. The taxi example makes the opposite difficulty visible: with continuously varying driver locations and rewards determined by distance, the complete reward vector may be unique to each driver, so the exact type support grows with \(M\).
One could preserve nontrivial online learning by imposing a finite observation budget across each cohort or by introducing shared, hidden demand shocks. But the former changes the paper’s rule that probing an arm yields observations for every agent; the latter replaces its independent agent–arm reward model with a common-state model. Both could be worthwhile research directions, but neither is a direct mirror of this theorem.
Theorem 2 fares better. Its finite-agent approximation ratio is \(\rho=(e-1)/((2e-1)\zeta)\). Under the natural geometric-mean normalization, that guarantee becomes \(\rho^{1/M}\), which tends to \(1\). So the theorem’s stated product guarantee does not transfer as a meaningful constant-factor guarantee for per-capita Nash welfare. The improved mass-flow formulation also needs the joint distribution of probed outcomes, since assignments can depend on the realized rewards; means alone do not specify that problem. A finite-support assumption makes the formulation finite, but it is an additional restriction on the input model.
Those points do not dispose of the stronger mirror. With finite-support types, per-capita capacities, and a fully specified reward-vector law, one can define a coherent problem: choose a probe set, observe the resulting population of type-and-outcome groups, and allocate mass to maximize per-capita Nash welfare. The fixed-probe allocation may be a tractable convex problem, while selecting probes remains a combinatorial problem over arms. That is a legitimate computational question, even though the paper’s approximation theorem does not answer it.
So the negative case is strongest against treating these theorems as carrying over: the online learning challenge largely disappears under infinite cohorts, and the offline approximation factor loses its force under population normalization. But I cannot honestly defeat the offline mirror as a worthwhile question. The type-flow version is coherent and recognizable, and ruling it out would require the very kind of “the answer is unchanged” objection the programme excludes. The case against any worthwhile continuous mirror is therefore weak.
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.