Answer: Every randomized prior-free policy has an oblivious worst-case instance with ratio at least \((2k-2)/k\), for every \(k\ge 2\) and any horizon with at least two decision steps. A one-step horizon admits an optimal policy with ratio \(1\).
Proposition 2 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateNo randomized prior-free algorithm can achieve a competitive ratio better than 2L−2 L .
statement extracted from the paper’s text layer; consult the paper for the exact wording
For a finite set of recurring compatibility types \(T\), a cycle cap \(L\), and a finite horizon, arrivals and expiries change the available type masses over time. At each step, an online policy chooses feasible masses \(z_c\ge 0\) for cycle templates \(c\) of length at most \(L\), subject to \(\sum_c a_{tc}z_c\le M_t\) for every type \(t\), where \(a_{tc}\) is the number of units of type \(t\) consumed by \(c\) and \(M_t\) is its available mass. Against the clairvoyant offline optimum on the same trajectory, prove or refute that every randomized prior-free policy has an obliviously chosen trajectory with \(\mathrm{OPT}/\mathbb{E}[\mathrm{ALG}]\ge (2L-2)/L\).
A society is given by its support: the list of \(\tau\) compatibility types with positive mass, each mass a binary rational; \(\tau\) counts supported types, not all possible types. Masses are not normalized.
A known loopless directed compatibility graph on these types has \(m\) arcs. Only incompatible patient–donor pairs are represented, with no altruistic donors; every transplant has unit value. Fix a cycle cap \(k\ge 2\) and a finite horizon \(H\).
A trajectory consists of finitely many cohorts, each with a type, positive rational mass, arrival step, and expiry step. Its remaining mass is available from arrival through the step before expiry. At each step, expiries and arrivals occur before decisions; consumption is permanent. Arrivals and expiries are revealed only when they occur, and a policy may choose which currently available cohorts supply consumed mass.
A cycle template \(c\) is a cyclic sequence of \(2\le |c|\le k\) types whose consecutive arcs exist. Types may repeat, representing distinct participating units; \(a_{tc}\) counts occurrences of type \(t\). With available mass \(M_t\), a policy chooses real masses \(z_c\ge 0\) satisfying \(\sum_c a_{tc}z_c\le M_t\), earning \(\sum_c |c|z_c\); choosing zero is allowed.
A prior-free randomized policy knows the compatibility graph, cap, and horizon, but neither future events nor their distribution. Its total reward is \(\mathrm{ALG}\); \(\mathrm{OPT}\) is the maximum reward of a clairvoyant policy with the same divisible actions and cohort constraints. The entire trajectory is fixed independently of the policy's random bits. Consider only trajectories with \(\mathrm{OPT}>0\), interpreting a zero expected reward as infinite ratio. Any running times are measured in \(m,\tau,L,k,H\) and the number of cohorts, where \(L\) is the total input bit length.
Does every randomized prior-free policy, for each \(k\ge 2\), admit a finite obliviously chosen trajectory with \(\mathrm{OPT}/\mathbb{E}[\mathrm{ALG}]\ge (2k-2)/k\), or can a policy avoid this bound on every such trajectory?
For indivisible pairs, Awasthi and Sandholm establish the randomized prior-free competitive lower bound \((2k-2)/k\). [Source](https://www.cs.cmu.edu/~sandholm/onlineKidneyExchange.ijcai09.pdf)
No result settling this precise divisible-mass model was located in the literature search.
The lower bound survives divisible masses. For every \(k\ge 2\) and every randomized prior-free policy, there is an oblivious instance with two decision steps satisfying \(\mathrm{OPT}/\mathbb E[\mathrm{ALG}]\ge (2k-2)/k\).
Here the graph and support are part of the worst-case instance, as in the cited competitive lower bound. A horizon with only one decision step is a degenerate exception: maximizing the current fractional packing gives ratio \(1\), so the proposed bound fails for \(k>2\). We address the intended online setting with at least two decision steps.
The proof below adapts the short-cycle versus long-cycle construction underlying [Awasthi and Sandholm, Proposition 2](https://www.cs.cmu.edu/~sandholm/onlineKidneyExchange.ijcai09.pdf). It explicitly preserves the known support and masses across the two continuations.
Fix \(k\ge 2\). Use the \(k+1\) types \(A,B,C_1,\ldots,C_{k-1}\), each with society mass \(1\).
The graph has exactly the arcs forming the two cycles
\(A\to B\to A\)
and
\(A\to C_1\to\cdots\to C_{k-1}\to A\).
Thus the graph is loopless, has \(\tau=k+1\) supported types and \(m=k+2\) arcs, and contains no altruistic donors. All masses are positive binary rationals.
Consider two trajectories, \(T_0\) and \(T_1\). Each has exactly one cohort of mass \(1\) for each type:
| Type | Arrival | Expiry in \(T_0\) | Expiry in \(T_1\) |
|---|---|---|---|
| \(A\) | \(1\) | \(2\) | \(3\) |
| \(B\) | \(1\) | \(2\) | \(2\) |
| Each \(C_i\) | \(2\) | \(3\) | \(3\) |
Decisions occur at steps \(1\) and \(2\); expiry \(3\) is after the second decision. Any additional horizon steps are empty.
Both trajectories have the same graph, support, total mass of every type, arrival schedule, and horizon. Their only difference is \(A\)'s expiry. Because expiry is revealed only when it occurs, the policy has identical information through its first decision.
Fix an arbitrary randomized policy. Let \(X\) denote the mass of \(A\) it consumes at step \(1\).
Only \(A\) and \(B\) are available then. Any template assigned positive mass must therefore use only these two types. Since the graph is loopless and its arcs on these types are \(A\to B\) and \(B\to A\), every such template alternates between \(A\) and \(B\). It consequently contains equally many occurrences of each.
This includes templates with repeated types: a template of length \(2r\) consumes \(rz_c\) mass of each type and earns \(2rz_c\).
Summing over the chosen templates, the policy consumes exactly \(X\) mass of each of \(A,B\), earns exactly \(2X\), and satisfies \(0\le X\le 1\).
Set \(p=\mathbb E[X]\). Identical observations at step \(1\) imply that \(X\), and hence \(p\), has the same distribution in both trajectories. This argument allows arbitrary real fractional actions.
At step \(2\), both \(A\) and \(B\) expire. The remaining graph on \(C_1,\ldots,C_{k-1}\) is a directed path, so it admits no cycle template. Thus
\(\mathbb E[\mathrm{ALG}(T_0)]=2p\).
A clairvoyant policy consumes the full \(A\)-\(B\) cycle at step \(1\), earning \(2\). No reward is possible afterward, and step \(1\) can consume at most the two available units. Therefore
\(\mathrm{OPT}(T_0)=2\).
At step \(2\), \(B\) expires, while the remaining mass of \(A\) is \(1-X\). Each \(C_i\) arrives with mass \(1\).
On these available types, the graph is precisely a directed cycle of length \(k\). Every closed walk traverses it an integer number of times. Under the cap \(k\), every usable template therefore traverses it exactly once, consuming equal mass of all \(k\) types.
The policy's additional reward is consequently at most \(k(1-X)\). Pathwise,
\(\mathrm{ALG}(T_1)\le 2X+k(1-X)=k-(k-2)X\),
and hence
\(\mathbb E[\mathrm{ALG}(T_1)]\le k-(k-2)p\).
A clairvoyant policy waits and executes the full length-\(k\) cycle, earning \(k\). Conversely, if it consumes mass \(x\) of \(A\) early, the same calculation bounds its total reward by \(k-(k-2)x\le k\). Therefore
\(\mathrm{OPT}(T_1)=k\).
Write \(R=(2k-2)/k\) and \(p_*=k/(2k-2)=1/R\).
If \(p\le p_*\), choose \(T_0\). For \(p=0\), its ratio is infinite by the stipulated convention. Otherwise,
\(\mathrm{OPT}(T_0)/\mathbb E[\mathrm{ALG}(T_0)]=1/p\ge R\).
If \(p>p_*\), then necessarily \(k>2\). Choose \(T_1\). Its expected reward satisfies
\(\mathbb E[\mathrm{ALG}(T_1)]\le k-(k-2)p\le k-(k-2)p_*=k^2/(2k-2)\).
Its ratio is therefore at least
\(\mathrm{OPT}(T_1)/\mathbb E[\mathrm{ALG}(T_1)]\ge k/(k^2/(2k-2))=R\),
again interpreting a zero denominator as an infinite ratio.
The selected trajectory depends only on the policy's expected first-step consumption on the common observed prefix. It does not depend on the realized random bits. The entire trajectory can therefore be fixed before the policy runs, as required for an oblivious adversary.
For \(k=2\), \(p_*=1\), so the first case already proves the required bound \(R=1\).
The construction proves the requested lower bound in the divisible-mass model with at least two decision steps, even when the policy knows all supported types and their exact total masses. Fractional actions replace the original acceptance probability by expected consumed mass; the two reward inequalities remain valid.
This establishes a lower bound, without asserting that it is the optimal competitive ratio for the full model.
⟨structured verdict parsed — rendered above⟩
Verdict: the proof is correct for horizons with at least two decision steps. It also correctly identifies that, for a one-step horizon and \(k>2\), an optimal current-packing policy avoids the proposed bound. Thus the horizon qualification is essential, and the prover states it explicitly.
No major or minor mathematical issues were found. The argument is self-contained and does not require transferring an indivisible-model theorem to the divisible model.
The construction establishes a worst-case-instance statement: for every policy and every \(k\ge 2\), the adversary can choose the graph, society, and trajectory described in the output. This is the natural competitive-analysis interpretation of the task, and the prover explicitly states it.
It does not establish the bound separately for every prescribed compatibility graph. The output does not claim that stronger statement.
The horizon distinction is handled correctly:
The opening claim must therefore be read together with the immediately following scope qualification.
There are \(k+1\) distinct supported types. The short cycle contributes two arcs, and the long cycle contributes \(k\) arcs. Their arc sets are disjoint, including when \(k=2\), so the stated count \(m=k+2\) is correct.
The graph is loopless. Each type has one cohort of mass \(1\), a positive binary rational. Both trajectories therefore have identical support and total mass for each type.
The availability table agrees with the specified event order:
Expiry at step \(3\) is consistent with availability through the second decision.
The only differing datum is the expiry of \(A\). Since expiry information is revealed only when expiry occurs, that difference is unavailable at the first decision. The indistinguishability claim is valid even if the policy knows every supported type and its total mass.
Any positive template at step \(1\) must use only available types. The induced graph on \(A,B\) has only the two opposite arcs, so every closed cyclic sequence alternates between these types.
A template of length \(2r\) therefore has \(r\) occurrences of each type. Its consumption and reward are exactly those stated in the output.
Summing over templates gives equal consumption \(X\) of \(A\) and \(B\), reward \(2X\), and \(0\le X\le 1\). This calculation covers repeated-type templates and arbitrary real fractional actions.
Identical first-step observations imply identical distributions of \(X\) in the two trajectories. Its expectation \(p\) exists because \(X\) is bounded.
After the expiries, the available \(C_i\) induce a directed path. For \(k=2\), this is a single isolated vertex. Neither case supports a cycle template.
Hence the policy earns exactly \(2X\) overall, giving expected reward \(2p\).
The clairvoyant policy can consume the full short cycle at step \(1\), earning \(2\). There are only two units available at that step and no subsequent feasible reward. Thus \(\mathrm{OPT}(T_0)=2\).
After \(B\) expires, the available graph is exactly the directed cycle of length \(k\). Every closed walk in this graph has length a positive multiple of \(k\). The cap therefore permits only one traversal.
Each usable template consumes equal mass of all \(k\) types. Remaining \(A\)-mass \(1-X\) consequently bounds additional reward by \(k(1-X)\). The pathwise inequality
\[
\mathrm{ALG}(T_1)\le 2X+k(1-X)=k-(k-2)X
\]
is correct, including policies that deliberately leave usable mass unconsumed.
Taking expectations gives the stated bound.
Waiting and consuming the full long cycle earns \(k\). For any clairvoyant first-step consumption \(x\), the same bound is at most \(k\), since \(k\ge 2\) and \(x\ge 0\). Thus \(\mathrm{OPT}(T_1)=k\).
The threshold \(p_*=k/(2k-2)\) is correct.
When \(p\le p_*\), the ratio on \(T_0\) is \(1/p\ge (2k-2)/k\), with the specified infinite-ratio convention when \(p=0\).
When \(p>p_*\), necessarily \(k>2\), and the coefficient \(k-2\) is positive. The inequality direction is therefore correct. The critical computation is also correct:
\[
k-(k-2)p_*=\frac{k^2}{2k-2}.
\]
Dividing \(\mathrm{OPT}(T_1)=k\) by this upper bound yields the required ratio.
For \(k=2\), \(p_*=1\), so the first case covers every possible policy.
The adversary selects a trajectory using the policy's expected behavior on the common prefix, not its realized random bits. This is an oblivious selection. No efficient procedure for computing that expectation is needed for the existential lower bound.
The cited [Awasthi–Sandholm Proposition 2](https://www.cs.cmu.edu/~sandholm/onlineKidneyExchange.ijcai09.pdf) states the corresponding randomized prior-free lower bound for its model. The output uses it as construction background; all claims needed for the divisible model are proved directly.
No repair or additional mathematical clarification is required. The result establishes a competitive-ratio lower bound, with the stated horizon exception. It makes no computational-complexity classification, so the JSON field continuous_status is marked unresolved for that reason alone.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.