| paper | d4-conf-aaai-2022-0349 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Answer: Yes: a uniformly efficiently computable online policy family satisfies the stated asymptotic approximation guarantee. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given a finite bipartite graph \((I,J,E)\), arrival rates \(\lambda_j\), supply masses \(b_i\), and singleton groups with targets \(\mu_j>0\), let type \(j\) arrive as a deterministic mass flow of rate \(\lambda_j\) over \([0,1]\). Each arriving mass unit must be assigned immediately and irrevocably to a feasible supplier or rejected, subject to supplier capacities. What is the best worst-case competitive ratio of causal fluid policies against the clairvoyant fluid optimum for maximizing \(\min_{j\in J} X_j/(\Lambda\mu_j)\), where \(X_j\) is the mass served and \(\Lambda=\sum_j\lambda_j\)?
A finite set of demand and supply types, fixed compatibility edges, deterministic arrival mass rates \(\lambda_j\), supply capacities measured in mass, and singleton fairness targets \(\mu_j\). The decision is a causal assignment of arriving mass; the objective is Max-A, compared against the optimal mass allocation.
The mirror covers the Max-A allocation problem and Theorems 1–3; it leaves aside the finite Poisson-arrival guarantees, the experiments, and the RSR objective.
The strongest mirror I believe in is a fluid, high-multiplicity version of EPORA. Keep the paper’s graph, protected groups, objective, and online horizon. Replace individual requests and integer stock by divisible demand mass and per-type supply mass. This is a natural limit when the number of requesters and supplies grows while the number of types stays fixed: if type \(j\)’s Poisson rate and supply capacity are both multiplied by \(N\), then arrivals divided by \(N\) converge to a deterministic flow as \(N\) grows.
A plausible regime is a large vaccine rollout over many weeks. A demand type could be a county–race cohort, with the same eligibility and feasible providers; a supply type could be a county–vaccine-product stock. The paper’s Minnesota setup has 435 county–race demand types and 261 county–product supply types. With many more requesters and doses than types, treating each type’s population and stock as mass is credible. The actual downsampled experiment includes supply types of capacity one, so it is not itself wholly in the smooth-capacity regime.
Here is the common fluid model behind my questions. The input is a bipartite graph \((I,J,E)\), type arrival rates \(\lambda_j\) over \([0,1]\), supply capacities \(b_i\) measured in mass units, protected groups \(G\subseteq 2^J\), and targets \(\mu_g\). Write \(\Lambda=\sum_j\lambda_j\). Type \(j\) arrives as a deterministic flow at rate \(\lambda_j\). A policy assigns mass immediately and irrevocably as it arrives. If \(y_{ij}(t)\) is the assignment rate, then \(\sum_i y_{ij}(t)\leq\lambda_j\), and \(\int_0^1\sum_j y_{ij}(t)\,dt\leq b_i\). Its objective is the same Max-A objective, now measured in mass:
\[
\min_{g\in G}
\frac{\sum_{j\in g}\sum_i\int_0^1 y_{ij}(t)\,dt}{\Lambda\mu_g}.
\]
A mass assignment is an average over infinitesimal requesters; each requester still receives either service or no service.
Theorem 1 is my lead anchor. As printed, it says that an LP-based sampling algorithm SAMP achieves online competitive ratio \(g(1,b)\geq\max(1-1/e,\;1-1/\sqrt{2\pi b})\), where \(b=\min_i b_i\) and \(g(s,b)=\mathbb{E}[\min(\operatorname{Pois}(b/s),b)]/b\). The theorem is proved in this paper; the monotonicity fact about \(g\) used in its proof is cited from earlier work.
The corresponding named problem is Fluid EPORA–General: given the fluid instance above, compute a causal allocation schedule maximizing Max-A and its value. This is a precise analogue of their underlying allocation problem, not a problem about the LP encoding. Let \(x_{ij}=\int_0^1y_{ij}(t)\,dt\). The fluid optimum is exactly the paper’s benchmark LP with constraints \(\sum_i x_{ij}\leq\lambda_j\), \(\sum_{j\in g}\sum_i x_{ij}\geq s\Lambda\mu_g\), and \(\sum_jx_{ij}\leq b_i\). Any feasible LP solution is implementable causally by setting \(y_{ij}(t)=x_{ij}\) throughout the horizon. Since the arrival flow is known and deterministic, the clairvoyant fluid benchmark is the same optimum. The expected direction is tractable: solve the LP and return its allocation schedule, giving competitive ratio \(1\). This is the lead because it mirrors the paper’s general-group result and turns its stochastic benchmark into an exact fluid optimum.
Theorem 2 gives a useful specialized anchor. It says that for homogeneous groups, where each group is one demand type, SAMP-S achieves competitive ratio \(\kappa g(s^*,b)\). Here \(\kappa=\min_j\lambda_j/(\Lambda\mu_j)\), \(b=\min_i b_i\), and \(s^*\) is the optimal value of LP (12). The theorem is proved here. The named fluid problem is Fluid EPORA–Singleton: restrict Fluid EPORA–General to singleton groups, and compute the exact maximum minimum target attainment and a schedule achieving it. It is precisely LP (12), now an exact flow formulation rather than an upper bound on a stochastic optimum, so I also expect it to be tractable. The parameter \(\kappa\) still describes a bottleneck in the achievable fairness value; the fluid model removes the extra loss from uncertain individual arrivals, not the shortage of a type relative to its target.
Theorem 3 is the boundary anchor. It states that the competitive analyses for SAMP and SAMP-S are tight, and that no algorithm can achieve competitive ratio greater than \(\sqrt{3}-1\) even for homogeneous groups. The theorem is proved here, with its lower-bound construction in Appendix B. The corresponding Fluid EPORA–Singleton Competitive-Ratio Frontier asks for the best worst-case competitive ratio of causal policies against the clairvoyant fluid optimum over all nontrivial singleton-group instances. Its solution is ratio \(1\): on every instance, an optimal flow schedule can be computed from the known input and followed causally. Thus the \(\sqrt{3}-1\) barrier should not carry over. In the paper’s lower-bound construction, rare types may fail to arrive during the finite horizon; in the fluid mirror, their prescribed mass arrives deterministically and can be reserved for. This is a meaningful answer about where the discrete online barrier stops helping, not a claim that Theorem 3 is wrong in its stochastic model.
The scope here is Theorems 1–3 and the Max-A allocation problem they analyze. The paper has named computational results, but no named NP-hardness, P, or parameterized-complexity classification; these anchors concern competitive ratios and online algorithms. Useful follow-on questions are how fast the finite stochastic model approaches the fluid value as capacities and arrival counts grow, what happens when the number of types grows with population, and whether shared arrival shocks preserve a nontrivial online gap.
The weakest point is also the key modelling change: the fluid limit removes the independent Poisson fluctuations that create the paper’s online-versus-clairvoyant gap. An author could reasonably say that this is a limiting version of their problem rather than a replacement for the finite stochastic problem. I think the mirror remains credible because it keeps their feasibility graph and Max-A objective, and because Theorem 1’s bound itself tends to \(1\) as the minimum capacity grows. The right claim is that fluid EPORA is a tractable high-multiplicity analogue, not that it captures every finite-market effect.
The strongest case against is that the paper’s central difficulty comes from finite, unpredictable arrivals. High multiplicity removes that feature under the paper’s independent Poisson model. If rates and capacities are both multiplied by \(N\), then normalized arrival counts have fluctuations of order \(N^{-1/2}\). With a fixed set of types, each type’s flow becomes predictable. If capacities do not grow with the population, the ASR objective instead collapses as arrivals overwhelm supply. Neither scaling preserves the paper’s original online tension.
That is what undermines the proposed mirror of Theorem 1. In Fluid EPORA–General, the schedule faces known deterministic flows. The variables \(x_{ij}\) are exactly those in the paper’s benchmark LP, and a feasible solution can be followed as the flow arrives. This defines a coherent fluid model, but its causal-decision feature has disappeared: there is no unrevealed realization for the clairvoyant benchmark to see. The mirror therefore captures the aggregate allocation constraints while losing the online comparison the theorem analyzes.
Theorem 2 has the same problem. Restricting groups to singletons preserves its fairness constraints and its \(\kappa\) parameter, but does not restore arrival uncertainty. Those constraints remain properties of the input flows; they do not create a new online decision problem. A continuum over singleton types also needs care: point types have zero mass, so the paper’s minimum-over-groups metric cannot simply be applied to them. Grouping types into positive-mass cohorts avoids that issue, but no longer tests the rare-type bottleneck that motivates the singleton result.
Theorem 3’s lower-bound construction makes the mismatch clearest. It uses \(n\) rare types, each with arrival rate \(1/n\), a unique unit-capacity supplier, and target share \(1/n^2\). Each rare type has only \(1/n\) expected arrivals. If \(n\) is fixed while the population is scaled up, those arrivals concentrate and the construction’s finite-arrival uncertainty disappears. To keep each rare type’s expected count small, \(n\) must grow with the population, so those types are not high-multiplicity cohorts. In a type-space limit, their vanishing masses also make a minimum over singleton groups degenerate. This is a real boundary on what that particular worst-case construction can say about a fixed-support fluid regime.
One could retain macroscopic online uncertainty by adding shared shocks to arrivals, or by making rates unknown. But those changes replace the paper’s independent homogeneous Poisson model with a different source of uncertainty. They may define worthwhile problems; they do not rescue a mirror that preserves this paper’s assumptions.
This is a substantial objection to the exact deterministic-flow anchors, but it does not support the universal claim that no worthwhile mirror exists. The paper’s county–race cohorts are a plausible high-multiplicity regime, and a finite-population-to-fluid convergence question could be useful even if its limit is simple. Under the programme’s stated standard, I cannot honestly say the negative case defeats every 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.