| paper | d4-conf-sagt-2022-0008 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
other→other discrete result → its continuous mirror
Answer: \(\rho^*(\mu)=1/\tau\) for every fixed positive rational mass vector \(\mu\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 5
statement extracted from the paper’s text layer
Given a finite type set \(T\), fixed positive rational masses \(\mu_t\) with \(\sum_{t\in T}\mu_t=1\), and an adversarially revealed stream of item value vectors \(u^j\in[0,1]^T\), each assigned whole and irrevocably to one type, define \(W_t=\mu_t^{-1}\sum_j u_t^j x_{tj}\) and let \(\mathrm{OPT}_\mu\) be the offline optimum for \(\min_{t\in T}W_t\). What is the largest \(\rho\) achievable by a randomized online policy such that its expected welfare is at least \(\rho\,\mathrm{OPT}_\mu-o(\mathrm{OPT}_\mu)\) as \(\mathrm{OPT}_\mu\to\infty\), against an oblivious adversary; is it \(1/|T|\) for every fixed \(\mu\)?
A fixed-support society has rational type masses \(\mu_t\), and every member of type \(t\) shares the same additive valuation. Each arriving indivisible item has value \(u_t^j\) to type \(t\) and is assigned to one type; the type's mass-normalized welfare is \(W_t=\mu_t^{-1}\sum_j u_t^j x_{tj}\), and the objective is \(\min_t W_t\). In finite realizations, items assigned to a type can be distributed among its members to balance their utilities.
The exact reduction to τ scaled representatives means the masses add no separate algorithmic structure, which limits the mirror's novelty even though it does not invalidate the population-level question.
fatal: False
Covers the asymptotic adversarial guarantees in Theorems 1 and 5, Theorem 3's deterministic asymptotic guarantee under the same rescaling, and Theorem 4's unknown-i.i.d. guarantee. It leaves the strict-ratio results and the additive and greedy-type bounds outside the proposed mirror.
The strongest mirror I believe is a high-multiplicity version of online max-min fair allocation with a fixed number of exact valuation types. Imagine a long-running aid or voucher program serving many recipients in standardized need profiles. A recipient’s type is their complete additive valuation function over every possible arriving item. There are \(N\) recipients, but only \(\tau\) such types, with type \(t\) making up fraction \(\mu_t>0\) of the population. The regime is \(N\gg\tau\), with many recipients per type.
Here is the continuous problem. An arriving item has value vector \(u^j=(u^j_t)_{t\in T}\in[0,1]^\tau\). The online policy must assign the whole item irrevocably to one type: \(x_{tj}\in\{0,1\}\), with \(\sum_t x_{tj}=1\). The type’s scaled per-capita welfare is \(W_t=\frac{1}{\mu_t}\sum_j u^j_t x_{tj}\), and the objective is \(\min_t W_t\). The offline benchmark \(\mathrm{OPT}_\mu\) maximizes that same objective with the whole stream known. The instance includes the rational mass vector \(\mu\), the arrival model, and either the adversarial stream or the distribution generating i.i.d. value vectors. Running-time parameters are \(\tau\), the stream length \(m\), and the input bit length \(L\).
The mass normalization has a direct finite-population interpretation. Take \(N\) so each \(N\mu_t\) is an integer and give each type’s items to its least-served member. Since type members value each item identically and item values are at most \(1\), their utilities stay within \(1\) of that type’s average. Thus the type-level objective lifts to worst-individual welfare with an additive error of at most \(1\). When per-person optimal welfare grows, that error vanishes in the competitive ratio. The continuous object is the population distribution; items remain indivisible and arrivals remain online.
My lead problem is Adversarial Type Max-Min: determine the optimal asymptotic competitive ratio for randomized online policies in this model, for fixed \(\mu\) and adversarial item values. The expected answer is exactly \(1/\tau\).
The paper’s Theorem 5, proved here, is the strongest anchor for this question: in the adversarial arrival model, the asymptotic competitive ratio of any randomized algorithm is at most \(1/n\). Its proof uses Yao’s principle to construct input distributions with arbitrarily large expected offline optimum. In the type model, apply it to the \(\tau\) type representatives; for arbitrary \(\mu\), scale each coordinate by \(\mu_t\), so the type’s normalized welfare matches the representative’s utility. This gives the \(1/\tau\) upper bound.
The matching constructive anchor is Theorem 1, also proved here. Its uniform-random allocation algorithm guarantees \(\mathbb E[\mathrm{Random}(\sigma)]\ge \mathrm{Opt}/n-O(\sqrt{\mathrm{Opt}\log\mathrm{Opt}})\), where \(\mathrm{Opt}=\mathbb E[\mathrm{OPT}(\sigma)]\); the guarantee holds even against an adaptive-offline adversary. In the type model, apply it to the \(\tau\) representatives with values scaled by \(\mu_{\min}/\mu_t\), then divide out the common scaling. The error term changes with fixed \(\mu\), but the asymptotic ratio is \(1/\tau\). The policy’s action is concrete: on each arrival, choose a type uniformly at random, then give the item to a least-served member of that type in the finite realization.
A second, distinct question is i.i.d. Type Max-Min. The type masses are as above, and arriving value vectors are i.i.d. from an unknown distribution \(D\), which may be continuous; the horizon is unknown to the policy. The goal is to maximize expected minimum type welfare against the expected offline optimum. Theorem 4, proved here, says that for every \(0<\varepsilon<1\), the paper’s deterministic polynomial-time algorithm is \((1-2\varepsilon)\)-competitive when the expected offline optimum is at least \(\frac{2}{\varepsilon^2}\log\frac{\tau}{\varepsilon}\). For the mass-weighted model, use representative values \(\mu_{\min}u_t/\mu_t\); the sufficient threshold is then on \(\mu_{\min}\mathbb E[\mathrm{OPT}_\mu]\). The corresponding policy discounts a type’s value according to its accumulated scaled welfare and assigns each arriving item to the type with the highest discounted value. Its predicted direction is tractability: for large enough expected optimum, the ratio approaches \(1\). The paper uses an LP in its analysis, not as part of the allocation algorithm.
These anchors are all competitive-analysis results, not NP-hardness theorems. Together they pose a useful computational question about a continuous population: with fixed support size, adversarial arrivals have a sharp \(1/\tau\) boundary, while i.i.d. arrivals admit near-optimal online allocation. The mirror covers those asymptotic adversarial and unknown-i.i.d. results. It does not claim to mirror the paper’s strict-ratio bounds.
The weakest point is the exact-type and long-horizon assumption. The bridge to the paper’s individual max-min objective uses identical valuations within each type and an additive \(1\) balancing error; when per-person welfare stays small, that error may matter. If each recipient has idiosyncratic eligibility or preferences, \(\tau\) can grow with \(N\), removing the fixed-support advantage. In particular, I would not claim this mirror covers Theorem 9: its strict-ratio construction uses many label-specific agent roles, so its type support grows with the population. The paper’s authors should recognize the proposed model as their online fairness problem in the regime where exact valuation types are numerous in mass but few in number; the continuous question preserves the max-min objective, additive valuations, indivisible items, and irrevocable online decisions.
The strongest case against these mirrors is a representation collision. The paper has named results on online algorithms and competitive ratios, so “there is no computational result to mirror” would be wrong. The problem is that the proposed continuous type model reduces exactly to the paper’s finite-agent problem.
For fixed positive masses \(\mu_t\), set \(\hat u_t^j=(\mu_{\min}/\mu_t)u_t^j\). Then \(\hat u_t^j\in[0,1]\), and the representative agent’s utility is
\[
\sum_j \hat u_t^j x_{tj}
=\mu_{\min}\frac{1}{\mu_t}\sum_j u_t^j x_{tj}
=\mu_{\min}W_t.
\]
So the continuous objective and the finite \(\tau\)-agent objective differ only by a common scale. This is an objective-preserving change of input, with running time still parameterized by \(\tau\), \(m\), and the input bits. Masses introduce no separate computational structure.
That disposes of both adversarial anchors as *new continuization questions*. Theorem 5 applies directly to the \(\tau\) representative agents; Theorem 1’s uniform random allocation is the same policy after relabelling. Arbitrary \(\mu\) changes the coordinates, not the online problem. The i.i.d. anchor reduces the same way by pushing the distribution \(D\) through that coordinate scaling. Theorem 4 already permits continuously distributed value vectors and an unknown horizon. Its algorithm on the representative agents is the proposed discounted type policy. These are meaningful statements, but their computational content is already in the paper.
The more faithful version—\(N\) actual people, with \(N\mu_t\) people of type \(t\), and the minimum utility taken over individuals—exposes a different problem. A type’s average utility is \(W_t/N\), not \(W_t\). Distributing that type’s assigned items to its least-served members puts the minimum within \(1\) of the average, since item values are at most \(1\). Thus the average model approximates individual max-min when per-person optimum grows without bound. At bounded per-person welfare, the additive error can dominate. Tracking the distribution of accumulated utilities within each type would retain that distinction, but a literal minimum can depend on one person, whose mass vanishes in an atomless population. Preserving it requires extra individual-level state or a finite population; the simple type-mass mirror no longer suffices.
That is the best negative case: either the type-average formulation is a reparameterization of the paper’s finite problem, or the faithful individual-minimum formulation needs structure the proposed continuum discards. It does not prove that no useful scenario exists. A large, standardized population with high per-person supply is plausible, and its high-load limit is well posed. The case against is that this particular paper’s three anchors do not open a new continuous complexity landscape: their type-level versions are already the paper’s results in \(\tau\) rescaled coordinates.
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.