| paper | Possible and Necessary Allocations via Sequential Mechanisms |
| authors | H. Aziz, T. Walsh, Lirong Xia |
| venue | IJCAI 2015 |
| filed under | fairalloc · theory |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\text{-hard}\), already for \(k=2\), and for every fixed \(k\ge 2\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 22
statement extracted from the paper’s text layer
Given finite preference types \(T\) with rational masses \(\mu_t\), course types \(O\) with rational capacities \(\sigma_o\) satisfying \(\sum_{o\in O}\sigma_o=k\), strict rankings \(\succ_t\), and a distinguished type \(t^\star\), does there exist a finite-block priority word \(w:[0,1]\to T\) with rational breakpoints and type masses \(\mu_t\), whose alternating left-to-right and right-to-left scans allocate each infinitesimal agent an integral bundle of \(k\) distinct courses, such that every member of type \(t^\star\) receives exactly its top-\(k\) courses?
A high-multiplicity sequential course-allocation model with preference types \(T\), population mass \(\mu\), course-type capacities \(\sigma\), and a finite-block priority word \(w\) coupled to its reversal. The induced variables \(Y_{t,o}\) record aggregate mass receiving course type \(o\), while each microscopic agent still receives an integral, duplicate-free bundle; the decision target is \(Y_{t^\star,o}=\mu_{t^\star}\) for every top-\(k\) course \(o\).
The reverse-order coupling between first- and second-round positions may require an unbounded or measurable schedule representation, so the proposed mirror does not yet have a settled finite computational encoding or a proved configuration-LP formulation.
fatal: False
The mirror covers the top-\(k\) POSSIBLESET component of Theorem 22; it leaves the NECESSARYITEM and NECESSARYSUBSET components, the characterization theorems, and the remaining Table 1 results untreated.
My strongest positive case is anchored in Theorem 22, proved in this paper. It states that, for every \(k\ge2\), under balanced-alternation policies, top-\(k\) POSSIBLESET is \(\mathrm{NP}\)-complete; in the same theorem, NECESSARYITEM and NECESSARYSUBSET are \(\mathrm{coNP}\)-complete. The proof is given here, by a reduction from EXACT 3-COVER for \(k=2\), with padding for larger \(k\). I use the top-\(k\) POSSIBLESET part as the lead anchor.
The paper’s problem is: given agents with strict rankings over indivisible items, can a distinguished agent receive exactly her top \(k\) items under some policy of the form \(\pi\triangleright\operatorname{inv}(\pi)\)? The continuous analogue I would propose is Balanced-Alternation Cohort Top-\(k\) POSSIBLESET\(_\infty\).
An instance consists of a finite set \(T\) of complete preference types, rational masses \(\mu_t\) with \(\sum_t\mu_t=1\), a finite catalogue \(O\) of course types, rational capacities \(\sigma_o\) with \(\sum_o\sigma_o=k\), and a distinguished type \(t^\star\). Every agent of type \(t\) has the same strict ranking \(\succ_t\) over \(O\). Each individual receives exactly \(k\) distinct courses; only the aggregate assignment is fractional. Thus \(Y_{t,o}\) denotes the mass of type \(t\) receiving course \(o\), with \(0\le Y_{t,o}\le\mu_t\).
A balanced-alternation policy is represented by a finite-block word \(w:[0,1]\to T\) whose type masses are \(\mu_t\). In round one, the population is scanned from left to right according to \(w\); in round two it is scanned right to left; the direction alternates in later rounds. Each infinitesimal agent picks her most-preferred available course, subject to capacity and the no-duplicate-course condition. This is the mass-limit version of \(\pi\triangleright\operatorname{inv}(\pi)\), while the rounds and each individual’s bundle remain discrete.
The decision question is:
\[ \text{Does there exist a balanced-alternation word }w \]
such that every member of the distinguished cohort receives her top \(k\) courses? Equivalently, if \(K(t^\star)\) is the set of the first \(k\) courses in \(\succ_{t^\star}\), ask whether the resulting aggregate assignment satisfies
\[ Y_{t^\star,o}=\mu_{t^\star} \quad\text{for every }o\in K(t^\star), \]
and \(Y_{t^\star,o}=0\) for every other course. Because individuals cannot receive the same course twice, this aggregate condition says that almost every member of the cohort receives exactly her top-\(k\) bundle.
This is a natural high-multiplicity course-allocation regime. Think of a large MBA or professional-school cohort: thousands of students, perhaps a few dozen or hundred complete preference types determined by programme, prerequisites, and career track. Course capacities scale with the cohort, and the registrar uses a balanced alternating picking policy. The relevant regime is \(N\gg\tau\): many students of each type, but comparatively few distinct types. The paper itself names Harvard course allocation as an application, so the authors should recognise the mechanism and policy class immediately. What changes is only the population representation: named students become masses of observationally identical students.
The finite-to-continuous bridge is direct. With \(N\) clones of each type, set \(n_t=N\mu_t\) and create \(N\sigma_o\) copies of each course type. A finite balanced-alternation order induces a type word \(w_N\), and its normalized allocation converges to \(Y\). Conversely, every rational finite-block word can be realized by a sufficiently large cloned finite instance. Thus the mirror is not merely “fractional courses”: every microscopic student still receives an integral bundle, while fractional values arise only because we aggregate many identical students.
I expect this mirror to be Class A, although only as a conjectural programme result, not as something proved by the paper. The X3C reduction in Theorem 22 relies on all-or-nothing choices among individually named agents. In the mass model, a preference type may be split across several priority intervals. The exact-cover obstruction can therefore become a fractional mass-flow condition. The first and reversed passes should plausibly admit a configuration-LP or transportation formulation over type/course-history states. The target-cohort constraints are linear, and the number of possible individual histories is finite for fixed \(k\), even though the original policy space is enormous.
That expected collapse is precisely the interesting question. If splitting type mass destroys the X3C integrality, Theorem 22’s discrete hardness was population-driven and disappears in the continuum. If, instead, the order constraints retain an integral linear-ordering obstruction despite repeated types, hardness transfers and the mirror is Class B. Either outcome would be informative. A continuum-specific hardness result would also be possible if the measurable interleaving itself creates a new difficult optimization problem.
The main weakness is that sequential allocation depends on the complete interleaving of turns, not merely on the vector \(\mu\). A naive type-level model that processes each type in one block would erase the paper’s central object and be too weak. My proposal preserves interleaving explicitly through the priority word \(w\), at the cost of making the policy variable infinite-dimensional before compression. A second, unavoidable difference is that a measure-zero named individual cannot be queried meaningfully in an atomless society. I therefore replace the paper’s distinguished agent by a positive-mass homogeneous cohort and ask whether the whole cohort can receive the target bundle. That is a genuine high-multiplicity lift, but not a literal pointwise restatement.
The mirror covers only the top-\(k\) POSSIBLESET result of Theorem 22. It does not claim to continuize the paper’s characterization theorems or every entry in Table 1. Natural follow-up problems are the corresponding cohort NECESSARYITEM question, approximate target mass \(Y_{t^\star,o}\ge\theta\), fixed-\(\tau\) versus variable-\(\tau\) complexity, finite-population rounding guarantees, and the probability that a randomly chosen policy gives the cohort its top bundle.
The strongest negative case is that Theorem 22 does not actually expose a population-continuation problem. Its hardness construction is built around a finite permutation of individually named agents and individually named items. The relation \(m=kn\) is essential: increasing the number of agents requires increasing the number of indivisible items, while the reduction uses those item identities to encode the exact-cover instance. Replicating agents alone therefore does not produce a high-multiplicity instance of the same problem.
The natural repair is the proponent’s course-cohort model: replace items by course types with capacities, let many students share preference types, and ask whether an entire positive-mass cohort receives its top \(k\) courses. This is sensible as a new capacitated allocation problem, but it is not yet a continuous mirror of Theorem 22. It changes unique indivisible items into interchangeable copies and changes a distinguished agent into a cohort-wide requirement. That may be the right model for Harvard-style courses, but the paper’s theorem provides no reason that this is the correct continuation rather than a different mechanism inspired by the same story.
More seriously, the proposed policy variable is not computationally specified. A type word \(w\) must preserve the entire relative order of agents, because the second pass is tied to the reverse position of the same agent. Thus an agent at position \(x\) in the first pass is paired with the agent at \(1-x\) in the second pass. Aggregate variables such as \(Y_{t,o}\) forget precisely this pairing information. Two assignments can have identical type-course marginals while only one can arise from a single common priority order and its reversal.
Restoring that information requires a measure over complete picking histories together with a measure-preserving order or involution. If \(w\) is allowed to be an arbitrary measurable function, the existence problem has no ordinary finite encoding. If it is restricted to finite-block words, the number of blocks is an unbounded part of the witness, and the proposed bridge covers only rational finite-block schedules—not the full limit of finite policies. If one bounds the number of blocks or forces each type to appear contiguously, one obtains a new restricted policy class rather than the balanced-alternation class studied in the paper.
This also undermines the suggested configuration-LP route. The columns cannot simply be course bundles: they must encode complete first-pass histories, second-pass choices, and the reverse-order coupling between them. The consistency constraints saying that all agents arise from one common order are nonconvex. A configuration LP might eventually be found, but it is not supplied by the population limit, and its pricing problem could retain the entire permutation structure of Theorem 22.
The target-agent substitution has a similar problem. A fixed positive-mass cohort asks whether all members receive the bundle, which is materially stronger than whether one named agent does. A cohort of mass \(\varepsilon\) that is meant to approximate one agent disappears as \(\varepsilon\to0\); a fixed \(\varepsilon\) defines a different robust allocation question. The same issue affects the proposed continuous NECESSARYITEM and NECESSARYSUBSET variants, whose universal quantification would range over an unspecified space of measurable priority words.
So the proponent has not yet supplied a finite, computationally defined mirror; they have supplied a promising modelling direction requiring several substantive choices. The honest limitation of this negative case is that the underlying course-allocation regime is genuinely high-multiplicity, and a carefully designed cohort-and-capacity model could be worthwhile. What Theorem 22 fails to establish is that such a model is its continuous mirror, rather than a new sequential capacitated-allocation problem.
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.