| paper | d4-conf-atal-2018-0203 |
| 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→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\text{-hard}\) · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3.1
statement extracted from the paper’s text layer
Given a finite horizon \(T\), resident types \(i\) with rational masses \(\mu_i\), resource types \(j\) with per-capita supplies \(q_j\), time-dependent values \(v_{tij}\), and compatibility restrictions, optimize the sum of the per-period minimum utility and a stability reward. A feasible plan is a finite-support distribution \(x_{i,h}\) over histories \(h\), where each history gives each resident an integral bundle \(b_{t,j}(h)\), \(\sum_h x_{i,h}=\mu_i\), and \(\sum_{i,h}x_{i,h}b_{t,j}(h)=q_j\) at every time and for each resource type. The per-period minimum is taken over positive-mass histories, and stability counts the mass of resource copies retained by residents between consecutive periods.
A high-multiplicity allocation model with complete resident types, rational mass on each type, and integral bundles along resident histories. Resource supplies scale per capita, and the stability reward is normalized so the total retained-resource reward remains comparable to the sum of per-period minimum utilities.
The mirror covers offline over-time allocation, including the unrestricted hardness question in Theorem 3.1 and the conditional approximation guarantee in Theorem 3.9; it leaves the online and lookahead results aside.
The strongest honest case is for a high multiplicity version of the paper’s over-time Max-Min Fair Allocation problem. Imagine a large population of residents receiving reusable equipment over several periods. Many residents have the same complete profile of valuations and eligibility for each item type. At each period, the goal is still to maximize the least-served resident’s value; across periods, keeping the same physical item with the same resident earns a stability reward. This is a plausible high multiplicity regime: the population is large, while the number \(\tau\) of distinct resident profiles is small. It preserves the paper’s finite horizon and indivisible bundles.
I would model it as follows. The input has a finite horizon \(T\), \(\tau\) resident types with rational masses \(\mu_i\) summing to \(1\), and resource types \(j\) with rational per-capita supplies \(q_j\). Copies of a resource type remain indivisible; they share the same values and eligibility across types and periods. Let \(v_{tij}\) be type \(i\)’s value for one copy of resource type \(j\) at time \(t\), with compatibility restrictions represented by forbidden assignments. A history \(h\) gives an individual an integral bundle \(b_{t,j}(h)\) at each time. The decision variable \(x_{i,h}\) is the mass of type-\(i\) residents following history \(h\). It must satisfy \(\sum_h x_{i,h}=\mu_i\) and \(\sum_{i,h}x_{i,h}b_{t,j}(h)=q_j\) for every \(t,j\). Thus the type-level plan can be fractional, but every resident represented by a history receives whole items.
For a positive-mass history, that resident’s utility at time \(t\) is \(\sum_j v_{tij}b_{t,j}(h)\). Let \(z_t\) be the minimum utility among all positive-mass histories. The stability term counts retained copies: for interchangeable copies of type \(j\), a history can retain \(\min(b_{t,j}(h),b_{t+1,j}(h))\) copies between adjacent periods. The objective is to maximize
\[
\sum_{t=1}^{T} z_t
+\kappa\sum_{t=1}^{T-1}\sum_{i,h,j}x_{i,h}\min(b_{t,j}(h),b_{t+1,j}(h)).
\]
Here \(\kappa\) is the per-capita stability reward. A finite population of size \(N\) realizes this normalization by using the paper’s per-item reward \(K_N=\kappa/N\). A solution is a finite-support collection of histories and masses; the computational question is to optimize this value, or produce an additive-\(\varepsilon\) solution. Complexity should be measured in \(T,\tau,|J|\), and the input bit length, not in the population size.
My lead anchor is Theorem 3.1, proved in this paper by a reduction from Maximum Cut (cited there as [13]). It proves that the off-line over-time problem without restrictions is NP-hard even with exactly two agents, homogeneous valuations, and binary values \(\ell_t(j,i)=\ell_t(j)\in\{0,1\}\); the corresponding static instances are trivial. The continuous question I would hand to a prover is: Over-Time Max-Min Fair Allocation\(_\infty\), unrestricted. Given the typed population, per-capita resource supplies, values, stability reward, and a rational threshold \(B\), determine whether the supremum objective over feasible mass plans is at least \(B\), or compute it to additive \(\varepsilon\). The solution is a feasible mass plan over integral bundle histories meeting that threshold or approximation guarantee. For the full general problem, my working prediction is Class C: individual bundles and the temporal overlap of those bundles may leave hard pricing problems even after population counts become masses. That is a conjecture about the continuous problem, not a claim that Theorem 3.1’s reduction carries over.
The important caveat is that the Max-Cut reduction’s hard slice has only two agents. Its combinatorics live in the resources and time steps, but spreading those two roles across large cohorts lets resource mass split among residents, which may erase the cut structure. So Theorem 3.1 is a good anchor for asking the question, but poor evidence for its answer.
A second, broader anchor is Theorem 3.9, also proved here. It says that if a polynomial-time algorithm gives a \(\rho\)-approximation for the static problem, then Algorithm 3′ gives a \(\rho/(\rho+1)\)-approximation for the off-line over-time problem with restrictions. Its continuous question is the restricted version of the typed-history problem above: compute a \(\rho/(\rho+1)\)-approximate feasible mass plan, given a \(\rho\)-approximation method for the corresponding static continuous problem. I expect Class A for this approximation question conditional on a tractable static solver: the paper’s argument compares a plan with maximum transition value against per-period approximate allocations, and that comparison has a natural mass-plan analogue. Whether the static continuous problem itself has efficient pricing is a separate question.
These mirrors cover the paper’s off-line quality-and-stability objective, including its unrestricted hard case and its restricted approximation result. They leave out the online and lookahead settings. The main follow-up questions are whether bundle-history pricing is efficient, whether solutions need only polynomially many histories, and how well continuous solutions round to finite populations.
The weakest point is the identity-sensitive stability term. A small positive mass of residents can carry a very large number of items, so the continuous model may admit plans that finite populations realize only with rare, heavily loaded residents. The per-capita normalization of stability also needs to be defended as the right regime. Those issues make the mirror less automatic than a standard high multiplicity relaxation, but they do not change the underlying question: does over-time fair allocation remain computationally hard when resident profiles are few and the population itself is represented by mass?
The paper gives me no decisive ground for a negative verdict: Theorem 3.1 is a computational hardness result, and Theorem 3.9 is a computational approximation result. The strongest objection is that their difficulty may have little to do with population multiplicity.
Theorem 3.1 fixes the population at two agents. Its Max-Cut instance is encoded in the resources and time steps: vertices become resources, and edges become periods. That reduction does not show that a large population with few resident profiles is a natural or useful regime. Scaling up the agents and supplies changes the construction, and letting resources be distributed across cohorts may erase its cut structure. This defeats an argument that the theorem’s hardness will carry over. It does not defeat asking what happens to the corresponding continuous problem.
The proponent’s best model also handles the main identity objection. Give each resident type its full valuation and eligibility profile, and represent the population by masses following complete histories of integral bundles. Those histories preserve which residents keep which goods across periods. With supplies scaled per capita, this is a coherent model for settings such as recurring equipment allocation to large cohorts. Treating it as an illegitimate mirror because it tracks identity would miss that the identity can be represented by mass on trajectories.
Theorem 3.9 is a less distinctive anchor, but the objection to it is not stronger. Its approximation guarantee comes from comparing a high-stability sequence with period-by-period approximate allocations. That comparison has a natural mass-plan analogue. The guarantee is conditional on an approximation method for the static continuous problem, so it does not establish that either problem is tractable. But the question of whether the dynamic guarantee follows from a static solver is still a valid computational question; its generic proof is not a reason to dismiss it.
The honest negative case is therefore limited. The paper does not itself establish that high multiplicity is common in its applications, and its hardest construction puts the combinatorics in resources and time rather than population size. The continuous model also needs per-capita supplies and a normalized stability reward to preserve the quality–stability trade-off. Those are substantial modeling choices, but the programme permits co-modifications when the population limit calls for them. They do not rule out a plausible regime.
So I cannot honestly defeat both anchors. The strongest version of Theorem 3.1’s mirror survives as a well-posed question, and Theorem 3.9 has a plausible aggregate analogue. My case against is weak: the paper offers little evidence that continuization will illuminate its particular hardness result, but it does not show that the mirror is not worth asking.
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.