| paper | d4-conf-atal-2023-0099 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→P discrete result → its continuous mirror
Answer: Polynomial-time solvable in \(m,\tau,L\), with an exact rational optimal allocation and welfare. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given \(m\) slots, a rational distribution \(\mu\) over \(\tau\) supported complete job types \(t=(\ell_t,v_{t1},\ldots,v_{tm})\), and rational per-capita slot capacity \(\kappa\), choose nonnegative masses \(x_{tj}\), for \(1\le j\le m-\ell_t+1\), maximizing \(\sum_t\sum_{j=1}^{m-\ell_t+1}v_{tj}x_{tj}\), subject to \(\sum_j x_{tj}\le\mu_t\) for every \(t\) and \(\sum_t\sum_{j:\,j\le s\le j+\ell_t-1}x_{tj}\le\kappa\) for every slot \(s\). Each scheduled unit of mass receives one whole contiguous job block; unscheduled mass is allowed.
A high-multiplicity allocation model for a large appointment network: each type specifies a complete job length and slot-value vector, \(\mu_t\) is its population share, and \(x_{tj}\) is the share assigned to start at slot \(j\). Slot capacity scales with population and is represented by \(\kappa\); the objective is aggregate welfare, and each unit of mass receives an indivisible contiguous job.
The mirror covers Theorem 3’s multi-slot indivisible-job welfare allocation. It leaves aside the single-slot VCG-T results, truthfulness and individual-rationality guarantees, and the MAA approximation and mechanism guarantees.
The strongest mirror is for the multi-slot allocation problem, not for the paper’s full mechanism. Theorem 3 states that MIA is NP-complete. The authors prove it here by a polynomial reduction from MUCA, whose NP-completeness they cite as prior work [13, 29]. In MIA, each agent has a job of an integral length and a value for each possible start slot. The problem is to choose at most one start for each job, keep every job in a contiguous block of slots, respect each slot’s capacity, and maximize the sum of agents’ values. The associated threshold decision question—whether a feasible schedule reaches a given welfare—is NP-complete.
Here is a continuous version I would be willing to hand to a prover. Consider a regional appointment service with a large population of requests and a fixed menu of service lengths, urgency levels, and time-preference profiles. A type \(t\) consists of the job length \(\ell_t\) and the complete value vector \(v_{tj}\) over start slots. The society is a rational distribution \(\mu\) over its \(\tau\) supported types, with \(\sum_t\mu_t=1\). Assume the service capacity scales with its catchment population: write \(\kappa\) for the per-capita capacity in each slot. Let \(x_{tj}\) be the mass of type \(t\) scheduled to start at slot \(j\). The problem, MIA\(_\infty\), is to find a feasible \(x\) maximizing
\[ \sum_{t\in T}\sum_{j=1}^{m-\ell_t+1} v_{tj}x_{tj} \]
subject to
\[ \sum_{j=1}^{m-\ell_t+1}x_{tj}\le \mu_t \quad (t\in T), \qquad \sum_{t\in T}\sum_{\substack{j\le s\le j+\ell_t-1}}x_{tj}\le\kappa \quad (s=1,\ldots,m), \qquad x_{tj}\ge 0. \]
A solution is the rational mass assigned to each type and start slot; any remaining mass is unscheduled. Each unit of mass that is scheduled still receives one whole, contiguous job block. The continuum lets a type’s mass be divided among start times; it does not divide any individual job.
This regime is plausible where many requests recur in a few standardized profiles—for example, a large appointment network serving cohorts with the same visit length, urgency, and time-window preferences. The relevant condition is \(N\gg\tau\), with types identical in every feature the scheduling problem uses, not merely similar. For a finite population of size \(N\), the matching normalization is \(\mu_t=n_t/N\) and \(\kappa=k/N\). Capacity must therefore grow with the population for a nontrivial fixed per-capita limit; the model is not claiming that one fixed-size shop can serve a constant fraction of an arbitrarily growing catchment.
This is a tractable mirror of the computational allocation question in Theorem 3. MIA\(_\infty\) is an LP with at most \(\tau m\) variables and polynomially many constraints, so with rational input it can be solved in time polynomial in \(m,\tau\), and the input bit length. The expected classification is Class A: the continuum turns the aggregate scheduling problem into a direct linear optimization problem. A natural next question is how the finite MIA optimum compares with this LP as \(N\) grows—for instance, whether one can bound the welfare loss from rounding type-level masses to actual people. One can also ask whether any of the paper’s truthful-mechanism guarantees have a meaningful nonatomic counterpart.
The mirror covers the multi-slot welfare allocation problem and its hardness result, Theorem 3. It does not claim to continuize the paper’s dominant-strategy or individual-rationality results. The main weakness is that those guarantees matter to the paper’s application, while MIA\(_\infty\) takes the type distribution as given and answers only the underlying welfare-optimization question. Exact shared value vectors may also be a demanding assumption outside standardized cohorts. Still, that limitation does not erase the fit to Theorem 3: the paper’s NP-completeness result is about the allocation kernel itself, and the mirror preserves its job lengths, slot values, contiguity, capacities, and welfare objective.
The best objection is that the nontrivial limit may not describe the paper’s motivating setting. For a fixed store, the number of slots \(m\) and the physical capacity \(k\) stay fixed as the customer base \(N\) grows. At most \(mk\) jobs can be scheduled per period, so the scheduled fraction is at most \(mk/N\), which tends to zero. With bounded valuations, per-capita welfare also tends to zero. On that reading, the continuous population mostly disappears from the problem.
But this does not defeat the proposed mirror. It scales capacity with the catchment population, a co-modification the programme explicitly allows when the authors would recognize the resulting problem. A large appointment network with standardized request profiles is plausible; the paper’s own experiments even use a small set of valuation levels. Types can include the full value vector and job length, and each unit of mass can still receive a whole contiguous block. The mirror preserves the allocation question in Theorem 3, even though it leaves the paper’s truthfulness and participation guarantees aside. The instructions allow one such anchor to be enough.
So the fixed-store objection narrows the relevant regime, but it does not rule out a worthwhile mirror in any scenario. I can’t make an honest universal negative case: the proposed version survives the strongest objection I can ground in the paper.
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.