| paper | d4-conf-atal-2021-0123 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 3.3
statement extracted from the paper’s text layer
Given a finite horizon \(H\), resource classes \(R\) with per-capita supplies \(\rho_r\), agent types \(A\) with utilities \(w_{ar}\), bounded patience and occupation-time laws, and a known finite-support rational law over arriving cohort-mass vectors \(\xi_t\), does there exist a causal policy, computable in time polynomial in the encoded instance size, such that for every \(\varepsilon>0\), \(\mathbb{E}[\mathrm{ALG}] \geq (1/2-\varepsilon)\mathbb{E}[\mathrm{OPT}]\)? The policy allocates waiting type mass to resource classes over time; \(\mathrm{OPT}\) is the feasible fluid allocation that knows the cohort trajectory in advance.
A continuum of households grouped into complete types \(a\in A\), with type mass arriving each period and resource capacity scaled to population. Decision variables \(y_{ar,t}\) are matched masses; each household receives an integral service, while type-level allocations and aggregate resource occupancy are represented by mass. The objective is expected matched utility, compared with the expected utility of the clairvoyant feasible fluid allocation.
With independent household arrivals and proportionally scaled supply, fluctuations may vanish relative to welfare, making the causal-versus-clairvoyant gap uninformative; retaining order-one uncertainty requires aggregate cohort shocks beyond that canonical limit.
fatal: False
The mirror covers Theorem 3.3's competitive guarantee for LP-based online allocation. It leaves the greedy analysis, other LP results, MDP and reinforcement-learning algorithms, and experiments outside the question.
My lead is Fluid OM-RR-PA with patient cohorts, a continuous-population mirror of the paper’s online allocation problem.
The anchor is Theorem 3.3, proved in this paper. It says that in OM-RR-PA with non-identical reusable resources, known adversarial arrival distributions, and known bounded distributions for agent waiting times and resource occupation times, the authors’ online algorithm OAA-NID achieves competitive ratio \(1/2-\varepsilon\) for every \(\varepsilon>0\), relative to the expected offline optimum. OAA-NID uses an optimal solution to the paper’s LP-NID and estimates resource availability by simulation. This is an algorithmic performance result, not a hardness or running-time classification; the paper has no comparable named hardness result to anchor instead.
Here is a precise continuous question. An instance has a finite horizon \(H\), resource classes \(r\in R\) with supply \(\rho_r\) per unit of eligible population, and a finite support \(A\) of \(\tau\) agent types. A type \(a\) specifies its utility \(w_{ar}\) for each resource class, its bounded patience-time distribution \(D_a\), and its bounded occupation-time distribution \(K_{ar}\). Each period reveals a cohort-mass vector \(\xi_t\): its \(a\)-coordinate is the mass of type \(a\) arriving then. The joint law of the cohort vectors is known and has a finite, rationally encoded support. A policy sees the current cohort and the history, but not future cohorts. It may match any feasible mass of waiting agents to resource classes, or leave them waiting; mass that reaches its patience limit departs. A mass assigned to a resource class receives the full service represented by that class, and occupies resource mass according to the type’s occupation-time law. The supply scales with population, while each household still receives an integral service. The objective is to maximize expected total matched utility, \(\mathbb E[\sum_{t,a,r} w_{ar}y_{ar,t}]\), where \(y_{ar,t}\) is the mass of type \(a\) matched to class \(r\) at time \(t\). The benchmark \(\mathrm{OPT}\) is the feasible fluid allocation that knows the full cohort trajectory in advance.
The prover’s task is: for every \(\varepsilon>0\), construct an efficient causal policy for this problem such that
\[
\mathbb E[\mathrm{ALG}] \geq (1/2-\varepsilon)\mathbb E[\mathrm{OPT}].
\]
A solution is the policy and a proof of feasibility and the guarantee. Its computational question is whether such policies can be found in time polynomial in the horizon, type and resource support sizes, encoded cohort-law support, and input bit length. I expect this to be Class A: the paper’s expected-allocation LP is a direct blueprint, and finite type support makes the fluid allocation variables explicit. Whether the same ratio follows in this fluid model is the question, not something Theorem 3.3 already proves.
A plausible regime is a large homelessness-services system with thousands of eligible households per year, but relatively few operational profiles. A profile could capture standardized need and outcome-score bands, expected utility from each intervention, waiting tolerance, and service-duration law. Many households can share those inputs even though each household is individually served. Daily or weekly cohort sizes and profiles can still fluctuate, preserving the paper’s online uncertainty. For example, \(\rho_r\) can express transitional-housing slots per eligible household, rather than fixing supply while the population grows.
The paper’s finite LP already uses probabilities, but its input is still a finite list of named agents \(V\), with per-agent arrival probabilities. Its decision variables are assignment marginals, not masses of interchangeable agents. This mirror replaces that finite list with cohorts of type mass, so it is not a restatement of the paper’s LP. It keeps the central problem intact: online, nonmyopic allocation under patience, reusable capacity, heterogeneous utility, and uncertain future arrivals. The further questions are whether the \(1/2\) guarantee is tight for fluid cohorts and whether the continuous optimum is the limit of large finite populations with the same type proportions.
The weak point is the type regime. Exact utility and duration profiles can be nearly unique in real data, so a useful finite \(\tau\) may require standardized or binned profiles. That could distort welfare if the bins are crude. Cohort-level uncertainty and per-capita resource supply are also explicit extensions of the paper’s one-agent-per-round model. Still, the paper’s homelessness application gives a concrete setting for the population regime, and these extensions preserve the allocation question rather than replacing it with outcome-space continuity or a static matching problem.
Theorem 3.3 is a real algorithmic anchor: OAA-NID uses the LP-NID solution to obtain a \(1/2-\varepsilon\) competitive ratio against the expected offline optimum. The strongest objection is that the ratio’s source of difficulty may disappear under the most natural high-multiplicity limit.
If many independent households of each type arrive and resource supply grows proportionally, the law of large numbers makes arrival and resource-occupancy proportions nearly deterministic. With a fixed horizon and bounded utilities and durations, the fluctuations are typically \(O(\sqrt n)\) against welfare of order \(n\). In that regime, a fluid controller can plan against the known arrival path, and the gap between causal and clairvoyant allocation can vanish. The paper’s central online uncertainty then contributes little to the limiting question.
The proponent preserves a nontrivial gap by allowing cohort masses to have persistent, order-one fluctuations. That is coherent, and policy shocks or seasonal changes could motivate it. But it adds aggregate uncertainty that does not arise from having many independent agents; the main computational challenge becomes online allocation under common shocks. It also requires scaling service capacity with population, which fits the programme’s rules but makes the homelessness example a growing system with proportional transitional-housing supply rather than the fixed-capacity system in the paper. These choices weaken the claim that the fluid theorem is a direct mirror of the paper’s result.
This is not enough to rule out a worthwhile mirror. A large system with proportional capacity and aggregate demand shocks is plausible, and Theorem 3.3 gives an identifiable result to investigate. The negative case is therefore weak at its hardest point: it can question whether the paper’s central guarantee remains informative in the natural fluid limit, but it cannot show that every credible continuous-population version loses the online 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.