| paper | d4-conf-atal-2010-0008 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-hard, even for \(\tau=1\), \(\mu_1=1\), \(k=m\), and \(C=0\), with strict preferences. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given \(M\) courses, fixed prices \(p\), and a finite set \(T\) of student types with rational masses \(\mu_t\) summing to \(1\), where each type has budget \(b_t\), additive values \(v_{tj}\), and a succinct permissible-schedule set \(\Psi_t\subseteq\{0,1\}^M\), compute for each type a utility-maximizing affordable schedule \(x_t\in\arg\max\{\sum_j v_{tj}x_j:x\in\Psi_t,\ p\cdot x\le b_t\}\), then output aggregate demand \(d_j=\sum_{t\in T}\mu_t x_{tj}\) for each course. Each unit of mass receives an integral schedule.
A fixed-price course-demand problem over a distribution of complete student types: each type chooses an integral schedule to maximize additive utility under its budget and scheduling constraints, while rational type masses weight aggregate course demand.
Mass does not change any type’s schedule choice, so the population component only weights the aggregate of independent knapsack demands; the mirror adds no population-level price-search result.
fatal: False
The mirror covers Theorem 1’s additive-separable demand formulation and the agent-level demand computation used by the paper’s solver. It leaves the A-CEEI price search, market-clearing guarantees, and experimental running-time results outside its scope.
The strongest mirror is the paper’s student demand computation, not its entire price search. It preserves the central combinatorial choice: each student gets an integral schedule, chosen to maximize utility among schedules they can afford.
The anchor is Theorem 1, proved in this paper. It says that when an agent’s utility is additively separable across courses, the agent’s maximization objective cannot be represented with a polynomial number of constraints unless \(P=NP\). The proof identifies this demand problem with KNAPSACK OPTIMIZATION. This is a formulation lower bound, rather than a theorem about the complexity of finding A-CEEI prices; the paper also computes these demand problems in its agent-level search. My mirror is of that underlying demand problem.
Call the mirror Continuous Course-Demand Computation. An instance has \(M\) courses and a finite support \(T\) of \(\tau\) student types. Type \(t\) has rational mass \(\mu_t\), with \(\sum_{t\in T}\mu_t=1\), a budget \(b_t\), an additive utility vector \(v_t\), and a succinct description of its permissible schedules \(\Psi_t\subseteq\{0,1\}^M\), including the paper’s course-count and scheduling constraints. The instance also gives course prices \(p\). For each type, the solution is a schedule
\[ x_t\in\arg\max\left\{\sum_{j=1}^M v_{tj}x_j: x\in\Psi_t,\ \sum_{j=1}^M p_jx_j\le b_t\right\}. \]
The output includes each chosen schedule and the aggregate demand \(d_j=\sum_{t\in T}\mu_t x_{tj}\) for every course \(j\). With strict preferences, each type has a unique demanded schedule. Mass here is the fraction of students in the type; it does not make an individual student’s schedule divisible.
A fitting regime is a large course marketplace—say, a university consortium with many students in standardized degree tracks—where students use a finite vocabulary of course-value templates and share track-specific scheduling constraints. Budgets can come from a finite set of rational tiers within the mechanism’s narrow budget range. Then \(N\) can be very large while \(\tau\), the number of distinct combinations of preferences, constraints, and budget, stays much smaller. This is a regime for the demand computation the paper actually runs: given prices and a student’s budget and preferences, find the most preferred affordable schedule.
I expect this mirror to be Class B: hardness transfers. At \(\tau=1\), finding the type’s demanded schedule still contains the paper’s knapsack optimization problem. The combinatorics are in the number of courses and the schedule choices, not in the number of students. Replacing a large group of identical students with its mass removes repeated computations; it does not remove the knapsack instance. That makes the mirror faithful even though it does not promise that continuization makes this particular subproblem tractable. The authors should recognize it: it is their agent-level demand calculation, with repeated agents represented by one type and a mass.
The scope is deliberately narrow. This mirrors Theorem 1 and the demand subproblem used by the algorithm. It does not claim a complexity result for finding prices that minimize market-clearing error, or for the full A-CEEI search procedure.
The weakest point is the regime’s compression assumption. Real students’ preferences may be sufficiently individualized that the number of exact types is close to \(N\); moreover, independent continuous budget draws can make every budget distinct when budget is included in the type. The finite-template, finite-budget-tier scenario is plausible for some large, standardized allocation settings, but it is a narrower regime than arbitrary course allocation. Further questions for a prover include whether hardness persists under restricted schedule constraints, what approximation or parameterized guarantees are possible in \(M\), \(k\), and \(\tau\), and whether the full price-search problem admits useful guarantees when demand is available only through these type-level computations.
The anchor I would press on is that the proposed continuous demand problem puts the mass outside the hard computation. At fixed prices, it solves one schedule-choice problem per type and then calculates \(d_j=\sum_t\mu_t x_{tj}\). The masses do not affect any choice. With \(\tau=1\), this is exactly the paper’s individual knapsack demand problem; with larger \(\tau\), it is a batch of such problems plus a weighted sum. That is a legitimate high-multiplicity encoding, but the population contributes no new optimization question. Its value is essentially caching repeated demand calculations.
The stronger mirror would include the price search: represent students by a distribution over preferences, constraints, and budgets, scale capacities per capita, and minimize aggregate market-clearing error. That is recognizable as an extension of A-CEEI, but it is poorly supported by the paper’s formal result. Theorem 1 concerns representing an individual’s optimality condition with a polynomial-size MIP. The paper’s price search is a tabu-search algorithm supported by experiments, not a complexity characterization. The continuum version would therefore pose a new computational question rather than mirror a result this paper establishes.
There is also a real modelling tradeoff in that stronger version. With finitely many exact types and strict preferences, everyone in a type makes the same discrete demand, so all the type’s mass moves together. The aggregate demand remains discontinuous, and the population does not smooth the price search. Smoothing it with many distinct budgets or preference profiles means the support may grow with the student count. The paper’s random budgets make this especially relevant: budget is part of a complete type, so its independent draws generally distinguish students. A finite set of budget tiers gives a more compressible variant, but it is not the budget regime the paper describes.
That is the strongest negative case, but it does not establish that no worthwhile mirror exists. Course allocation is a plausible high-multiplicity setting, and a researcher could reasonably study the full aggregate price-search problem. The proponent’s demand mirror also passes the author-recognition test: it is plainly the paper’s agent-level computation with repeated types grouped together. So I would argue that this paper offers a weak ChoCo opportunity—its clearest mirror mostly batches independent knapsack queries—but I cannot honestly defend the universal claim that no scenario yields a worthwhile continuous mirror.
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.