| paper | d4-conf-aaai-2014-0324 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 1
statement extracted from the paper’s text layer
Given a finite course catalog \(C\), rational per-capita capacities \(\kappa_c\), and a finite set of student types \(T\) with rational masses \(\mu_t\) summing to \(1\), compute the mass \(x_{t,B}\) of each type receiving each bundle \(B\). Each type records its wishlist, caveats, and priority cohort; the cohorts follow the four round orders of the cyclically shifted snake draft. Apply the draft with integral bundles for each individual, splitting a type's mass when a course reaches capacity and applying the paper's rollback rule to if-and-only-if caveats.
A finite-support society of student types with rational masses and per-capita course capacities. The decision variables are bundle masses \(x_{t,B}\), with \(\sum_B x_{t,B}=\mu_t\) and \(\sum_{t,B:c\in B}x_{t,B}\le\kappa_c\); the requested output is the allocation selected by the cohort-level draft and rollback rules, with no welfare objective.
The exact snake order makes each student's position consequential, so finite priority cohorts and threshold splitting can change who receives which bundle; the proponent acknowledges this change but does not establish that the authors would accept it.
fatal: False
Covers Theorem 1's draft-and-caveat allocation process through aggregate simulation. It leaves the pairwise-swapping heuristic and the unimplemented strategic proxy aside; neither has a named computational result in the paper.
The strongest positive case is a mirror of Theorem 1, proved in this paper. It says that the Quest Draft is a deterministic polynomial-time course-allocation algorithm. The proof considers \(n\) students, each with a wishlist of \(m=O(n)\) courses, four picks per student, and the paper’s at-most and if-and-only-if caveats. It bounds a pick’s update work by \(O(n^2)\), and bounds each student’s backtracking by \(m/2\), since every backtrack removes a pair of courses. The resulting stated bound is \(O(n^5)\). The paper gives no named hardness result, so this is its only suitable computational anchor.
My lead mirror is Mass Quest Draft. Take a large university cohort with a fixed course catalog across four blocks. Let \(C\) be the offerings, \(b(c)\in\{1,2,3,4\}\) the block of course \(c\), and \(\kappa_c\in\mathbb Q_{\ge0}\) its capacity per unit of population. The society is a finite set \(T\) of student types with rational masses \(\mu_t\) summing to one. A complete type records the student’s year or cohort, strict course wishlist, at-most constraints \((S,r)\), if-and-only-if course pairs, and one of a fixed number of priority cohorts. The priority cohorts have the four pick orders induced by the cyclically shifted snake draft. A natural regime has millions of students but only a modest number \(\tau=|T|\) of recurring preference, requirement, and priority profiles; course capacities scale with the cohort.
The problem is: compute the aggregate allocation produced by the corresponding mass version of the Quest Draft. At each turn, the type cohort takes mass into its highest-ranked available course in that block, subject to its current schedule and caveats. When capacity runs out partway through a cohort, split its mass at that threshold and continue with the remaining mass. Apply the paper’s rollback rule to if-and-only-if constraints: if the paired course becomes unavailable, undo the affected later picks, remove the pair for that mass, and replay the draft. The solution is \(x_{t,B}\), the mass of type \(t\) receiving bundle \(B\), where each individual bundle contains at most one course per block and obeys the caveats. Thus \(\sum_B x_{t,B}=\mu_t\) and \(\sum_{t,B:c\in B}x_{t,B}\le\kappa_c\). Each individual still gets an integral bundle; fractional values describe the share of a type receiving each bundle. This is a policy-simulation problem, so it has no welfare objective: the requested output is the allocation selected by the draft rule.
I expect this mirror to be tractable, in Class A. With fixed four-block schedules, finite support, and rational masses and capacities, the batch process appears to have finitely many course-capacity and caveat events. The main proof obligation is to show that rollback can be aggregated and that its number of events is polynomial in \(m,\tau,L\), rather than in the total population \(N\). Theorem 1 motivates that question, but its \(O(n^5)\) proof does not establish the continuous bound.
The mirror covers the draft and caveat algorithm in Theorem 1. It does not cover the pairwise course-timeslot heuristic or the unimplemented strategic proxy; neither has a named computational result here. Further questions include whether aggregated rollback always terminates with a unique output, and how closely the mass allocation approximates finite drafts as \(N\) grows.
The soft spot is the priority rule. The paper orders named individuals, while a finite-support mass model needs a bounded set of priority cohorts and a rule for splitting ties. Mass Quest Draft keeps the snake-order idea but makes that cohort-level convention explicit; it is a defensible scaled version of the authors’ allocation problem, not an exact limit of every individual ordering. If the authors require their precise person-by-person priority order, priority may itself create too many distinct types. The positive case survives because the paper presents course allocation as the underlying multi-unit assignment problem, and a large population with few recurring course-demand profiles is a sensible high-multiplicity instance regime.
The sole anchor is Theorem 1, and its mirror is weaker than it first appears. The theorem bounds the runtime of one specific procedure on \(n\) individually ordered students with submitted wishlists and caveats. It does not analyze the complexity of finding a welfare-maximizing allocation, or classify a broader allocation problem. Its central operation is replaying a particular sequence of named students.
That sequence matters to the output. Under the exact snake order, each student’s position determines their four picks, and two students with identical preferences can receive different bundles because they appear at different positions. A complete type must therefore include priority position; in a society of \(n\) students, that gives at least \(n\) types. If position is omitted, grouping students into priority cohorts requires a new rule for ordering or splitting them, and capacity cutoffs can change who gets what. Rollbacks can then change later picks too. The proposed finite cohorts are a reasonable policy variant, but they do not preserve the paper’s exact procedure.
The strongest repair is to model randomized priority as a continuous rank and follow type masses through the four linked rounds. That could yield a well-posed aggregate allocation question, but it introduces a continuum of priority values rather than the paper’s finite-support society. It asks for the aggregate behavior of a stochastic large-population draft, not a continuous version of Theorem 1’s runtime bound. A useful result would need to establish something substantive about aggregation or convergence; the theorem itself supplies no reason to expect the continuous optimization machinery ChoCo targets to be relevant.
I would not claim this rules out every worthwhile mirror. A large course-allocation system with recurring preference profiles is a plausible high-multiplicity regime, and the aggregate draft question may interest the authors. The negative case is that the sole named computational result is tightly tied to individualized priority, while the more promising mass formulation changes the object being analyzed. That makes this a weak candidate for ChoCo, rather than a convincing universal rejection.
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.