| paper | Sequential Blocked Matching |
| authors | Nicholas Bishop, Hau Chan, Debmalya Mandal, Long Tran-Thanh |
| venue | AAAI 2022 |
| filed under | fairalloc · chores-online |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c22r1) |
| judge confidence | high |
| authors would recognise it | unclear |
The paper proves no named result asserting computational hardness, tractability, or parameterized complexity; its numbered distortion and regret theorems do not satisfy bit (a). The proposed fluid robust-distortion questions are plausible research extensions, but they do not repair that missing computational anchor. Moreover, the capacity scaling and convexification alter the original service and randomization structure.
fails bit a — no named computational result to mirror
The proposal addresses only the offline distortion bounds in Theorems 1 and 2; it leaves the incentive-ratio results, distortion upper bounds, and online bandit-regret result without mirrors.
There is a genuine, defensible mirror here, but it is a deliberately partial one: the offline distortion problem, not the paper’s individual-incentive or bandit-learning results.
The paper contains no named NP-hardness, polynomial-time, W[1]-hardness, or FPT theorem. The cited MAXSNP-hardness remark after Theorem 3 is external and not an anchor. The useful anchors are its proved distortion bounds:
I regard Theorem 2 as the stronger lead, because its proof already reduces attention to anonymous policies—the natural setting for a population continuum.
The mirror is a large platform serving a huge population of recurring users, jobs, or employers. There are \(s\) service classes, with a mass \(\kappa_j\) of interchangeable copies of service \(j\) available per round. Scaling service capacity is necessary: keeping only one physical copy of each service while taking the population to a continuum would make the service rate vanish. Cloud-resource pools, standardized appointment slots, or repeated restaurant offers provide plausible interpretations of these service classes.
A complete agent type is \(\theta=(v_\theta,d_\theta)\), where \(v_\theta\in\Delta^{s-1}\) is the agent’s cardinal reward vector and \(d_\theta\in\{1,\ldots,\widetilde D\}^s\) gives the blocking duration after receiving each service. Its observable report is \(q(\theta)=(r_\theta,d_\theta)\), where \(r_\theta\) is the ranking induced by \(v_\theta\). The society is a distribution \(\mu\) over a finite type set \(\Theta\); \(\mu_\theta\) is the fraction of the population having that complete type. The high-multiplicity regime is \(N\gg|\Theta|\): millions of users or jobs but only a moderate number of recurring preference-and-delay profiles.
A fluid schedule uses variables \(x_{t,q,j}\geq 0\), meaning mass of observable type \(q\) assigned to service \(j\) at time \(t\). It satisfies \(\sum_jx_{t,q,j}\leq\rho_q\), where \(\rho_q\) is the reported mass of type \(q\), and the blocking constraints \(\sum_q\sum_{r:\,r\leq t<r+d_{q,j}}x_{r,q,j}\leq\kappa_j\). Thus the action is a mass transfer over types, services, and time; the objective is integrated social welfare.
The planner sees only \(\rho\), not the cardinal values inside each ranking class. Let \(\mathcal M(\rho)\) be the set of full type distributions compatible with the observed report masses. For a schedule \(x\), let \(W_\mu(x)\) be its welfare under the latent population \(\mu\), and let \(\mathrm{OPT}(\mu)\) be the welfare of the best feasible schedule that knows the full cardinal types.
My lead problem is:
Continuous Anonymous SBM—Randomized Robust Distortion. Given \(S,T,\widetilde D,\kappa\), a finite type support \(\Theta\), report masses \(\rho\), and a threshold \(\alpha\), output a probability distribution \(\Pi\) over feasible fluid schedules such that
\(\sup_{\mu\in\mathcal M(\rho)}\mathrm{OPT}(\mu)/\mathbb E_{x\sim\Pi}[W_\mu(x)]\leq\alpha\),
or correctly report that no such \(\Pi\) exists.
This is recognisably the paper’s offline SBM problem: the same agents’ ordinal information, the same cardinal-welfare benchmark, the same blocking dynamics, and the same repeated matching objective. Only sums over many repeated agents have become mass integrals. Rational fluid instances can be implemented by \(N\) copies and rounded with vanishing additive error as \(N\) grows.
The anchor is Theorem 2, proved in this paper. Its expected continuous analogue is a meaningful boundary result. The fixed-population welfare oracle is a linear program: once \(\mu\) is known, the schedule variables and blocking constraints are linear. The robust ordinal version should therefore be attacked first as a Class A convex or LP-based problem. However, Theorem 2 may leave a transferred \(\Omega(\sqrt{s})\) approximation barrier, because it already rules out overcoming the obstruction merely by randomizing. If the fluid relaxation improves that bound, that would be an important continuization result: fractional mass assignment would have dissolved a genuinely discrete scheduling obstruction. If it does not, the result would show that ordinal uncertainty, rather than population granularity, is the source of the barrier.
The secondary problem mirrors Theorem 1:
Continuous Anonymous SBM—Deterministic Robust Distortion. Under the same input, output one feasible fluid schedule \(x\) minimizing \(\sup_{\mu\in\mathcal M(\rho)}\mathrm{OPT}(\mu)/W_\mu(x)\), or decide whether the optimum is at most \(\alpha\).
The anchor is Theorem 1, also proved here. I expect the full-information fluid version to be tractable by linear programming, and I would expect the deterministic \(\Omega(s)\) bound to weaken or even disappear once mass can be split across service trajectories. Any surviving lower bound would most naturally be an information-theoretic consequence of ordinal reports, not continuum-specific computational hardness. If hardness appears, I would first look for a transfer from the finite scheduling problem rather than a new Class C phenomenon.
These two mirrors cover exactly the paper’s offline distortion results, including the deterministic/randomized separation. I would not claim that they cover Theorem 3’s incentive ratio or Theorem 6’s bandit regret. In an atomless population, one individual changes the report distribution by zero mass, so individual manipulation becomes vacuous. A nontrivial strategic extension would need deviations by a positive-mass cohort or a \(\delta\)-mass coalition; that is a new model, not an automatic continuization of the paper.
That is also the weakest point of the case. The capacity scaling and the loss of individual pivotality are real modelling choices. If the authors insist that services are unique indivisible objects and that incentives must concern one named agent, this mirror is not faithful. But for the paper’s central offline distortion question, the mirror is strong: it preserves types, reports, blocking, welfare, the ordinal-information restriction, and the exact two named lower-bound phenomena while placing the population itself—not merely the outcomes—on a continuous footing.
The negative case is strongest at the level of what counts as an anchor. Theorem 1 and Theorem 2 are not computational results. They are information-theoretic distortion lower bounds: they say that even an unboundedly powerful mechanism cannot guarantee better welfare from ordinal reports. They do not establish hardness, tractability, an approximation algorithm, or a parameterized-complexity boundary. The two proposed threshold problems are new robust-optimization problems, not continuous versions of named computational results. Under ChoCo’s stated remit, that is decisive.
Theorem 2 also does not survive as the proponent presents it. Let \(\mathcal F\) be the convex set of feasible fluid schedules and let \(W_\mu(x)\) be fluid welfare. For any distribution \(\Pi\) over schedules, its mean schedule \(\bar{x}=\mathbb E_\Pi[x]\) is feasible, and linearity gives
\[
\mathbb E_\Pi[W_\mu(x)]=W_\mu(\bar{x})
\]
for every \(\mu\). Hence randomizing over fluid schedules is exactly equivalent to choosing one fractional schedule. The paper’s separation between deterministic distortion \(\Omega(s)\) and randomized distortion \(\Omega(\sqrt{s})\) depends on randomized choices among integral, named-agent matching sequences. In the proposed continuum, that distinction has been convexified away. A lower bound on the resulting deterministic fluid problem might be interesting, but it is not a mirror of Theorem 2’s randomized-policy result.
Trying to preserve the original object creates the opposite problem. If each service remains one indivisible reusable object while the population becomes atomless, each round serves only a vanishing fraction of society. The population distribution then ceases to be the operative allocation object. To obtain nonzero mass allocations, one must replicate services or scale capacities as \(\kappa_j\). That is a plausible model for cloud-resource pools or appointment classes, but it is a new capacity-allocation model, not merely the high-multiplicity limit of SBM. The service side, feasibility structure, and implementable policies have all changed.
Theorem 1 fares only slightly better. The proposed deterministic problem fixes aggregate report masses, introduces an ambiguity set of hidden cardinal distributions, replaces integral matching sequences by fluid schedules, and adds service capacities. This may be a legitimate robust scheduling problem, but Theorem 1 supplies no computational question whose high-multiplicity version it is. Its \(\Omega(s)\) statement is a worst-case performance impossibility, not a complexity boundary. Re-proving or improving that bound for the altered fluid model would therefore be a new result motivated by the paper, rather than a continuization result about it.
There is also an unresolved type-information conflict. For ChoCo, a complete type must include everything relevant to the objective and constraints; here that means at least the cardinal reward vector \(v\) and delay vector \(d\). If the distribution over those complete types is supplied to the planner, the paper’s ordinal-information problem disappears. If it is hidden and only aggregate rankings are observed, then agents with the same reported type are not actually interchangeable for welfare purposes: they have different private \(v\)’s. In the atomless limit, one individual’s report changes aggregate mass by zero, so the paper’s incentive-ratio problem becomes vacuous. Positive-mass deviations or coalition manipulation would be a new model.
A recurring-user interpretation is not absurd, and that is the honest weakness of the negative case. One could study the proposed fluid robust-allocation problem and perhaps obtain useful LP or approximation results. But the strongest claimed anchor is erased by fractional convexification, while the other is only a noncomputational distortion bound. The paper therefore offers no worthwhile continuous computational mirror under the programme’s sharper 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.