d4-conf-ijcai-2017-0051 (d4-conf-ijcai-2017-0051)

Given room-category supplies \(\rho_q\) with \(\sum_q \rho_q=1\), type masses \(\beta^1,\ldots,\beta^K\) with \(\sum_j \beta^j_t=\mu_t\) and \(\sum_t\mu_t=2\), and rational room values and roommate utilities, cohorts arrive in uniformly random order. Each cohort’s type mass must be assigned immediately, with assignments divisible across room categories and roommate pairs. Does there exist a randomized causal policy, polynomial in \(K\), \(|T|\), \(|Q|\), and the input bit length, whose expected welfare is at least \(c_b/4\) times the offline optimum over feasible type-pair and room-category allocations?

A society is encoded by its support: the list of \(\tau\) types \(T\) with positive binary-rational masses \(\mu_t\); \(\tau\) is the support size, not the number of possible types. There are \(m=|Q|\) room categories with positive binary-rational supplies \(\rho_q\), where \(\sum_q\rho_q=1\) and \(\sum_t\mu_t=2\).
The instance contains \(K\geq1\) nonempty cohorts with binary-rational masses \(\beta_t^j\geq0\), satisfying \(\sum_j\beta_t^j=\mu_t\), and nonnegative rational room values \(v_{tq}\) and directed roommate utilities \(h_{tu}\). Same-type pairing is allowed between distinct individuals and contributes \(2h_{tt}\) per unit of paired room mass.
The fixed cohorts arrive in a uniformly random permutation. Initially the policy knows only \(K,T,Q,\rho\) and total person mass \(2\); aggregate type masses and future cohorts are hidden. Each arrival reveals its mass vector, room values for its types, and both directed utilities between its types and all types seen so far, including within the cohort.
Each arriving cohort must be allocated completely before the next arrival. Room mass may be split arbitrarily: incoming mass may occupy empty rooms, fill rooms containing one earlier occupant, or form pairs within its cohort. Existing occupants cannot move or be paired again; singly occupied rooms may await later arrivals. Every room must finally contain two occupants.
Fix an ordering of \(T\). A final allocation has room masses \(x_{tuq}\geq0\) for \(t\leq u\), satisfying \(\sum_{t\leq u}x_{tuq}=\rho_q\) and \(\sum_q(2x_{ttq}+\sum_{u<t}x_{utq}+\sum_{u>t}x_{tuq})=\mu_t\).
Its welfare is \(W(x)=\sum_q\sum_{t\leq u}x_{tuq}(v_{tq}+v_{uq}+h_{tu}+h_{ut})\); \(\mathrm{OPT}\) is the maximum over these feasible allocations with full information. Let \(L\) be the total binary input length and \(c_b=(\ln 5-4/5)/5\).

Does there exist a randomized causal policy running in time polynomial in \(K,m,\tau,L\) that, for every such instance, achieves \(\mathbb{E}[W]\geq(c_b/4)\mathrm{OPT}\), with expectation over cohort order and policy randomness, or is this guarantee impossible in polynomial time?

For discrete agents arriving individually in uniformly random order, a polynomial-time online algorithm achieves competitive ratio \(c_b/4\). [Source](https://www.ijcai.org/proceedings/2017/0034.pdf)
No result settling this precise divisible cohort model was located in the literature search.

A uniform competitive bound for arbitrary cohorts

The requested ratio remains unresolved. I prove a positive constant guarantee independent of the number and sizes of the cohorts:

Theorem. There is a randomized causal policy, running in time polynomial in $K,m,\tau,L$, such that every instance satisfies
$$ \mathbb E[W]\geq \frac{1}{16384}\,\mathrm{OPT}. $$
The policy uses at most three fair random bits. It operates directly on rational masses.

This removes the dependence on $K$ from the previous partial result. However, $1/16384$ is smaller than the requested $c_b/4$, so it does not settle the target question.

1. Completion and decomposition of the optimum

Write
$$ g_{tu}=h_{tu}+h_{ut}, \qquad w_{tuq}=v_{tq}+v_{uq}+g_{tu}. $$
In particular, $g_{tt}=2h_{tt}$.

Completion lemma

Suppose a feasible partial allocation contains person mass $A$, singly occupied room mass $S$, and empty room mass $E$. Then
$$ S+2E=2-A. $$
If an incoming cohort has mass $b$, then $b\leq 2-A$. Fill singleton slots using up to $\min\{b,S\}$ incoming mass. Pair any remaining incoming mass internally and place it in empty rooms. The remaining incoming mass is at most $2E$, so this is feasible.

Internal pairing can use same-type pairs: remaining mass $a$ of a type creates paired room mass $a/2$. Thus there is no parity restriction.

The argument also applies after any feasible prescribed allocations of part of the incoming cohort. Consequently, every policy below can finish each cohort immediately. At termination, remaining capacity is zero, so every room contains two occupants.

All utilities are nonnegative. Completion therefore cannot decrease welfare already secured.

Refining an optimum by cohort membership

The offline feasible set is nonempty: for example,
$$ x_{ttq}=\frac{\mu_t\rho_q}{2}, \qquad x_{tuq}=0\quad(t<u) $$
is feasible. It is also compact, because each variable lies between zero and its category supply. Hence an optimum $x^*$ exists.

For each type $t$, define
$$ p_t^j=\frac{\beta_t^j}{\mu_t}. $$
The denominator is positive and $\sum_jp_t^j=1$.

Temporarily distinguish the two occupant positions of every room portion. Split a portion with occupant types $t,u$ among cohort labels $j,k$ in proportions $p_t^jp_u^k$. This preserves room mass and welfare. The resulting type–cohort marginal is
$$ p_t^j\mu_t=\beta_t^j. $$
For same-type pairs, both occupant positions contribute to this marginal; distinct cohort labels receive the two corresponding ordered portions.

Let $V_j$ be the room-value contribution of cohort $j$, and let $I_j$ be the roommate contribution of pairs whose occupants both belong to $j$. For distinct cohorts $i,j$, let $H_{ij}=H_{ji}$ be their between-cohort roommate contribution. Thus
$$ \mathrm{OPT} = \sum_j(V_j+I_j)+\sum_{i<j}H_{ij}. $$
Every term is nonnegative.

An internal-pair replacement lemma

For any set $\mathcal D$ of cohorts, there is a fractional allocation containing only within-cohort pairs, respecting the original room supplies, whose welfare is at least
$$ \sum_{j\in\mathcal D}(V_j+I_j). $$

To construct it, retain every optimum pair within a cohort in $\mathcal D$. Consider an optimum room portion of mass $a$ between distinct cohorts, with occupant types $t,u$ in category $q$. For each endpoint whose cohort belongs to $\mathcal D$, replace that endpoint by a same-type within-cohort pair of room mass $a/2$ in category $q$.

Such a replacement consumes exactly the endpoint's original person mass $a$, preserves its room-value contribution $av_{tq}$, and adds nonnegative roommate welfare. The two replacements together use at most the original room mass $a$. Therefore category capacities hold, and every retained cohort has exactly its original type masses.

This proves the lemma.

2. Small cohorts, large cohorts, and random prefixes

Call a cohort small if its mass
$$ b_j=\sum_t\beta_t^j $$
satisfies $b_j\leq 1/4$. Call it large otherwise. Let $N$ be the number of large cohorts. Since total person mass is $2$,
$$ N\leq 7. $$
The policy does not need to know $N$.

Decompose the optimum into five components:
$$ \begin{aligned} A_{\mathrm s}&=\sum_{j\text{ small}}(V_j+I_j),\\ A_{\mathrm l}&=\sum_{j\text{ large}}(V_j+I_j),\\ C_{\mathrm{ss}}&=\sum_{\substack{i<j\\i,j\text{ small}}}H_{ij},\\ C_{\mathrm{ls}}&=\sum_{\substack{i<j\\\text{exactly one is large}}}H_{ij},\\ C_{\mathrm{ll}}&=\sum_{\substack{i<j\\i,j\text{ large}}}H_{ij}. \end{aligned} $$
Then
$$ \mathrm{OPT} = A_{\mathrm s}+A_{\mathrm l} +C_{\mathrm{ss}}+C_{\mathrm{ls}}+C_{\mathrm{ll}}. $$

For now assume $K\geq32$, and set
$$ s=\left\lfloor\frac K8\right\rfloor, \qquad r_{\max}=\left\lfloor\frac K4\right\rfloor. $$
Positions $s+1,\ldots,r_{\max}$ are called active positions. We will use
$$ r_{\max}\leq2s+1,\qquad r_{\max}-s\geq s,\qquad s\geq\frac{3K}{32}\geq\frac K{16}. $$

Let $\mathcal P_r$ be the set of the first $r$ arriving cohorts, and write
$$ B(\mathcal P)=\sum_{j\in\mathcal P}b_j. $$
The set $\mathcal P_r$ is a uniformly random $r$-subset. Conditional on $\mathcal P_r$ and its last cohort, the preceding cohorts have uniformly random order.

Two elementary bounds will control the mass of these prefixes.

For a fixed small cohort $j$ and $r\leq r_{\max}$,
$$ \begin{aligned} \mathbb E[B(\mathcal P_r)\mid j\in\mathcal P_r] &= b_j+\frac{r-1}{K-1}(2-b_j)\\ &\leq \frac14+\frac12 =\frac34. \end{aligned} $$
Markov's inequality gives
$$ \Pr(B(\mathcal P_r)\leq1\mid j\in\mathcal P_r)\geq\frac14. $$

For two fixed small cohorts $i,j$,
$$ \begin{aligned} \mathbb E[B(\mathcal P_r)\mid i,j\in\mathcal P_r] &= b_i+b_j+ \frac{r-2}{K-2}(2-b_i-b_j)\\ &\leq\frac12+\frac12=1. \end{aligned} $$
Consequently,
$$ \Pr\left(B(\mathcal P_r)\leq\frac43 \mid i,j\in\mathcal P_r\right)\geq\frac14. $$

3. Prefix linear programs and their canonical selection

The next two policies use an optimum determined by the revealed prefix, independently of its arrival order. Here are the two programs.

The within-cohort packing program

For each small cohort $j$ in a revealed prefix $\mathcal P$, use variables
$$ p^j_{tuq}\geq0,\qquad t\leq u. $$
Maximize
$$ \sum_{j\in\mathcal P\text{ small}}\sum_q\sum_{t\leq u} w_{tuq}p^j_{tuq} $$
subject to
$$ \sum_{j\in\mathcal P\text{ small}}\sum_{t\leq u}p^j_{tuq} \leq\rho_q $$
and
$$ \sum_q\left( 2p^j_{ttq} +\sum_{u<t}p^j_{utq} +\sum_{u>t}p^j_{tuq} \right) \leq\beta_t^j. $$
Let its optimum be $F_{\mathrm{own}}(\mathcal P)$.

The internal-pair replacement lemma gives
$$ F_{\mathrm{own}}(\mathcal P) \geq \sum_{\substack{j\in\mathcal P\\j\text{ small}}}(V_j+I_j). $$

The between-cohort matching program

Its nodes are type–cohort pairs $(j,t)$ for small cohorts in $\mathcal P$. Matching is allowed only between distinct cohorts. If $z_{jt,ku}$ denotes matched mass, maximize
$$ \sum_{\{(j,t),(k,u)\}}g_{tu}z_{jt,ku} $$
subject to nonnegativity and incident-mass constraints
$$ \sum_{(k,u):\,k\ne j}z_{jt,ku}\leq\beta_t^j. $$
Let its optimum be $F_{\mathrm{cross}}(\mathcal P)$.

Restricting the refined optimum to small–small pairs inside $\mathcal P$ gives
$$ F_{\mathrm{cross}}(\mathcal P) \geq \sum_{\substack{i<j\\i,j\in\mathcal P\\i,j\text{ small}}}H_{ij}. $$

Both programs use only revealed information. All their feasible regions are nonempty and bounded.

Removing dependence on arrival order

We choose a canonical optimum of each prefix program. Cohorts with different mass vectors are ordered lexicographically using the fixed type ordering. For cohorts with identical mass vectors, impose symmetry under permutations of those cohorts.

These symmetry constraints do not change the optimal value: averaging any optimum over such permutations preserves feasibility and objective value. They can be imposed with polynomially many equalities, using transpositions of identical cohorts. After passing to the resulting variable orbits, choose a lexicographically minimal optimum in a fixed group, type, and category ordering.

This is computable by polynomially many rational linear programs. It ensures that recommendations depend only on the revealed prefix, with identical cohorts treated symmetrically.

4. Policy for small cohorts' own welfare

Split every category into a selected pool of room mass $\rho_q/2$ and a filler pool of room mass $\rho_q/2$.

The policy runs until position $r_{\max}$, or until an arrival would make cumulative mass exceed $1$, whichever happens first. On stopping, it uses the completion lemma for that arrival and all subsequent arrivals.

Before position $s+1$, put all incoming mass into within-cohort pairs in the filler pool.

At an active arrival $j$:

• Solve the within-cohort packing program for the revealed prefix.
• Take the arriving cohort's recommended pairs, scaled by

$$ \delta=\frac14. $$

• In each category, reduce all those recommended pairs by a common factor if necessary to fit the remaining selected-pool supply.
• Pair all remaining incoming mass internally in the filler pool.

While cumulative mass is at most $1$, the filler pool is sufficient: it has total room mass $1/2$, and the total person mass assigned to it is at most $1$.

Availability estimate

For analysis, consider a virtual process that executes the selected-pool rule at every active position, without the mass stopping rule. It omits filler allocations. The real and virtual selected allocations coincide through position $r$ whenever $B(\mathcal P_r)\leq1$.

Fix an active position $r$, its prefix $\mathcal P_r$, and its arriving cohort. Let $D_q$ be selected room mass already used in category $q$.

At an earlier active position $\ell$, conditional on its prefix set, the arriving cohort is uniform among its $\ell$ members. The packing constraint therefore implies
$$ \mathbb E[\text{recommended room mass in category }q] \leq\frac{\rho_q}{\ell}. $$
Actual selected mass is at most $\delta$ times recommended mass. Conditional on the current prefix and arriving cohort,
$$ \mathbb E[D_q] \leq \delta\rho_q \sum_{\ell=s+1}^{r-1}\frac1\ell \leq\delta\rho_q. $$
The final inequality follows because there are at most $s$ summands and every denominator is at least $s+1$.

Let $P_q$ be the current cohort's total recommended pair mass in category $q$. It satisfies $P_q\leq\rho_q$. For $P_q>0$, the implemented fraction is
$$ a_q= \min\left\{1,\frac{\rho_q/2-D_q}{\delta P_q}\right\}. $$
Since $\delta P_q\leq\rho_q/2$,
$$ a_q\geq1-\frac{2D_q}{\rho_q}. $$
Hence
$$ \mathbb E[a_q]\geq1-2\delta=\frac12. $$

All objective coefficients are nonnegative. Conditional on the current prefix and arriving cohort, expected selected welfare is therefore at least $\delta/2$ times that cohort's recommended objective.

Conditional on $\mathcal P_r$, its arriving cohort is uniform among its $r$ members. Summing the recommended objectives over those members gives $F_{\mathrm{own}}(\mathcal P_r)$. Thus expected welfare gained at position $r$ is at least
$$ \frac{1}{8r} \mathbb E\!\left[ F_{\mathrm{own}}(\mathcal P_r) \mathbf 1_{\{B(\mathcal P_r)\leq1\}} \right]. $$

For each small cohort, inclusion probability is $r/K$, and conditional mass-survival probability is at least $1/4$. The benchmark inequality from Section 3 consequently gives
$$ \mathbb E\!\left[ F_{\mathrm{own}}(\mathcal P_r) \mathbf 1_{\{B(\mathcal P_r)\leq1\}} \right] \geq\frac{r}{4K}A_{\mathrm s}. $$
Summing over active positions proves
$$ \mathbb E[W_{\mathrm{small\ own}}] \geq \frac{r_{\max}-s}{32K}A_{\mathrm s} \geq\frac1{512}A_{\mathrm s}. $$

5. Policy for small–small roommate welfare

Again reserve room mass $\rho_q/2$ in every category. The other half is a filler pool.

For each arriving cohort, designate fraction
$$ \delta=\frac14 $$
of each type's mass as anchor mass. Anchor occupants use reserved rooms; other occupants are paired internally in the filler pool.

The policy runs through position $r_{\max}$, stopping earlier if an arrival would make cumulative mass exceed $4/3$. On stopping, it completes that arrival and all later arrivals arbitrarily.

Before active positions, put all anchors into singleton rooms. At an active arrival $j$, solve the between-cohort matching program on the revealed prefix.

For an earlier cohort–type node $(a,t)$, let $R_{at}$ be its remaining singleton anchor mass immediately before this arrival. For every recommended edge from $(a,t)$ to an incoming type $u$, implement mass
$$ \delta\lambda z_{at,ju} \frac{R_{at}}{\delta\beta_t^a}, \qquad \lambda=\frac14. $$
Nodes with zero $\beta_t^a$ are omitted. The same pre-arrival value $R_{at}$ is used for all these edges.

Put incoming anchor mass not used by these matches into new singleton rooms.

Feasibility

For an earlier node, total implemented matching mass is at most
$$ \delta\lambda\beta_t^a \frac{R_{at}}{\delta\beta_t^a} =\lambda R_{at}\leq R_{at}. $$
For an incoming type $u$, it is at most $\delta\lambda\beta_u^j$, hence at most its anchor mass.

Total anchor person mass over the entire instance is $2\delta=1/2$. Its occupied room mass is no larger than its person mass, so the reserved pool always has enough room for new singleton anchors.

When cumulative mass is at most $4/3$, filler person mass is at most
$$ (1-\delta)\frac43=1. $$
It therefore fits in the filler pool. Room categories impose no restriction on roommate weights; prescribed matches can be distributed among the earlier singleton locations.

Anchor availability estimate

Consider the virtual anchor process without the mass stopping rule. It remains feasible because total anchor mass is at most $1/2$.

Fix an active position $r$, its prefix, and its arriving cohort. Fix an earlier small node $(a,t)$ with $\beta_t^a>0$.

At its own arrival, this node loses at most $\delta\lambda\beta_t^a$ anchor mass.

At an earlier active position $\ell$, suppose $a$ has already arrived. Conditional on that prefix set, its arriving cohort is uniform among the other $\ell-1$ cohorts. The prefix matching degree constraint therefore gives
$$ \mathbb E[ \text{recommended mass incident to }(a,t) \text{ from that arriving cohort} ] \leq\frac{\beta_t^a}{\ell-1}. $$
Implemented mass is at most $\delta\lambda$ times recommended mass. Omitting the probability that $a$ has not yet arrived only enlarges this upper bound. Consequently,
$$ \begin{aligned} \mathbb E[R_{at}] &\geq \delta\beta_t^a \left( 1-\lambda -\lambda\sum_{\ell=s+1}^{r-1}\frac1{\ell-1} \right)\\ &\geq \delta\beta_t^a(1-2\lambda) =\frac{\delta\beta_t^a}{2}. \end{aligned} $$
Indeed,
$$ \sum_{\ell=s+1}^{r-1}\frac1{\ell-1} \leq\frac{r-s-1}{s}\leq1, $$
using $r\leq r_{\max}\leq2s+1$.

Current recommendations are fixed conditional on the current prefix and arriving cohort. Linearity of expectation now shows that expected current matching welfare is at least $\delta\lambda/2$ times its recommended incident welfare.

Each edge in the prefix matching is incident to two cohorts. Averaging over the current cohort therefore gives expected gain at least
$$ \frac{\delta\lambda}{r}F_{\mathrm{cross}}(\mathcal P_r). $$

The real process agrees with this virtual process when $B(\mathcal P_r)\leq4/3$. For each fixed small–small optimum pair, its endpoints belong to $\mathcal P_r$ with probability
$$ \frac{r(r-1)}{K(K-1)}, $$
and conditional mass-survival probability is at least $1/4$. Thus
$$ \mathbb E\!\left[ F_{\mathrm{cross}}(\mathcal P_r) \mathbf 1_{\{B(\mathcal P_r)\leq4/3\}} \right] \geq \frac{r(r-1)}{4K(K-1)}C_{\mathrm{ss}}. $$
Since $\delta\lambda=1/16$, summing yields
$$ \mathbb E[W_{\mathrm{small\ cross}}] \geq \frac{\sum_{r=s+1}^{r_{\max}}(r-1)} {64K(K-1)} C_{\mathrm{ss}}. $$
There are at least $s$ summands, each at least $s$. Hence
$$ \sum_{r=s+1}^{r_{\max}}(r-1) \geq s^2 \geq\frac{9K^2}{1024} \geq\frac{K^2}{128}. $$
It follows that
$$ \mathbb E[W_{\mathrm{small\ cross}}] \geq\frac1{8192}C_{\mathrm{ss}}. $$

6. Three policies involving large cohorts

These policies use
$$ \varepsilon=\frac18. $$

Large cohorts' own welfare

Before the first large cohort, pair every incoming type internally and distribute its paired room mass proportionally to $\rho$.

Let $j$ be the first large cohort, and let $A$ be preceding person mass. Empty supply in category $q$ is
$$ \left(1-\frac A2\right)\rho_q \geq\frac{b_j}{2}\rho_q >\frac{\rho_q}{8}. $$

Solve the within-cohort allocation program for $j$ alone, requiring all its type masses to be allocated and using capacities $\rho_q$. Its optimum is at least $V_j+I_j$ by the replacement lemma. Implement fraction $\varepsilon$ of that optimum in the empty rooms, then complete the cohort and all later arrivals.

Every large cohort is first among large cohorts with probability $1/N$. Therefore, when $N>0$,
$$ \mathbb E[W_{\mathrm{large\ own}}] \geq\frac{\varepsilon}{N}A_{\mathrm l} \geq\frac1{56}A_{\mathrm l}. $$
For $N=0$, the asserted bound is zero.

Large–small roommate welfare

Before the first large cohort, place fraction $\varepsilon$ of each incoming type into singleton rooms and pair its remaining mass internally. Distribute both uniformly across categories.

After cumulative person mass $A$, this uses room mass
$$ \frac{1+\varepsilon}{2}A. $$
If a large cohort remains to arrive, then $A<7/4$, so this is less than
$$ \frac{1+1/8}{2}\cdot\frac74=\frac{63}{64}<1. $$
Thus all these singleton anchors can be preserved until the first large cohort.

To define the policy when no large cohort exists, disable anchor preservation and use arbitrary completion if the next prescribed placement would exceed supply. The preceding calculation shows that this cannot happen before a first large cohort.

When the first large cohort $r$ arrives, optimize a fractional matching between its occupants and the stored singleton anchors. The refined optimum, scaled by $\varepsilon$, supplies a feasible candidate of welfare
$$ \varepsilon\sum_{\substack{j\text{ small}\\j\text{ precedes }r}}H_{rj}. $$
Complete afterward.

For a fixed large cohort $r$ and small cohort $j$, the event that $r$ is first among large cohorts and $j$ precedes $r$ has probability
$$ \frac1{N(N+1)}. $$
Indeed, in the induced permutation of the $N$ large cohorts and $j$, cohort $j$ must be first and $r$ second. Hence
$$ \mathbb E[W_{\mathrm{large\text{-}small}}] \geq \frac{\varepsilon}{N(N+1)}C_{\mathrm{ls}} \geq\frac1{448}C_{\mathrm{ls}}. $$
Again, when $N=0$, the right-hand side is zero.

Large–large roommate welfare

Before the first large cohort, pair everyone internally and distribute room mass uniformly across categories.

For the first large cohort $i$, reserve fraction $\varepsilon$ of its type masses as singleton anchors, pairing its remaining mass internally. Preserve these anchors while subsequent small cohorts arrive, pairing those cohorts internally.

If cumulative allocated person mass is $A$, this prescribed state uses room mass
$$ \frac{A+\varepsilon b_i}{2}. $$
If a second large cohort remains, then
$$ A<\frac74, \qquad \varepsilon b_i\leq\frac14, $$
so the state is feasible.

As before, disable preservation and use arbitrary completion if a prescribed placement would exceed supply. This never happens before a second large cohort when one exists.

At the second large cohort $j$, optimize matching against the stored anchors. This obtains at least $\varepsilon H_{ij}$, then completion finishes all allocations.

For each unordered pair of large cohorts, the probability that they are the first two large cohorts is
$$ \frac2{N(N-1)}. $$
For $N\geq2$,
$$ \mathbb E[W_{\mathrm{large\ cross}}] \geq \frac{2\varepsilon}{N(N-1)}C_{\mathrm{ll}} \geq\frac1{168}C_{\mathrm{ll}}. $$
For $N\leq1$, the component $C_{\mathrm{ll}}$ is zero.

7. Combining the policies and handling small $K$

For $K\geq32$, choose the small–small matching policy with probability $1/2$, and each of the other four policies with probability $1/8$. Three fair random bits implement this mixture exactly.

The five component coefficients are at least
$$ \frac1{4096},\quad \frac1{448},\quad \frac1{16384},\quad \frac1{3584},\quad \frac1{1344}, $$
respectively. Therefore
$$ \mathbb E[W]\geq\frac1{16384}\mathrm{OPT}. $$

For $2\leq K\leq31$, use a fair mixture of two simpler policies.

The first optimizes the first cohort's within-cohort allocation, then completes arbitrarily. The replacement lemma gives
$$ \mathbb E[W_1]\geq \frac1K\sum_j(V_j+I_j). $$

The second stores the entire first cohort singly if its mass is at most $1$, then optimizes its matching with the second cohort. If the first cohort has mass greater than $1$, it simply completes arbitrarily.

For every distinct pair of cohorts, at least one has mass at most $1$, because total mass is $2$. Thus at least one orientation of that pair as the first two arrivals yields its optimum between-cohort contribution. Each ordered pair has probability $1/[K(K-1)]$, so
$$ \mathbb E[W_2]\geq \frac1{K(K-1)}\sum_{i<j}H_{ij}. $$
The fair mixture consequently guarantees
$$ \mathbb E[W] \geq\frac1{2K(K-1)}\mathrm{OPT} \geq\frac1{1860}\mathrm{OPT} \geq\frac1{16384}\mathrm{OPT}. $$

For $K=1$, the sole arrival reveals the complete instance. Solving its offline linear program gives $\mathrm{OPT}$ causally.

8. Causality and polynomial bit complexity

Information used

Every cohort is completely allocated upon arrival.

The cutoffs use only known $K$. Cohort classification uses only its revealed mass. Prefix programs use only revealed cohort vectors and values between already seen types. Reservoir matching uses only earlier singleton occupants and the incoming cohort.

The five policies never use hidden aggregate type masses, future cohort vectors, or the number $N$ of large cohorts. Those quantities appear only in the analysis.

Linear-program size and encoding

The within-cohort prefix program has $O(Km\tau^2)$ variables. The between-cohort program has $O(K^2\tau^2)$ variables. Symmetry constraints and canonical selection require only polynomially many additional constraints and optimization calls.

All coefficients come from revealed input rationals, fixed fractions, and polynomially bounded multiplicities. Their encoding lengths are polynomial in $K,m,\tau,L$.

The standard exact rational linear-programming theorem applies: each program has rational data, polynomial dimensions, and a nonempty bounded feasible region. It returns an exact rational optimum in polynomial time, with polynomial encoding length.

Canonical lexicographic selection retains this bound. Successive coordinate minimizations select faces of the same rational polytope; each selected coordinate value is attained at a vertex of that polytope.

Allocation records

Singleton occupants can be stored in records indexed by cohort, type, category, and pool. There are $O(K\tau m)$ such records. Completed pairs can be aggregated by their two types, category, and pool, requiring $O(\tau^2m)$ records.

Matching and completion use greedy transfers. For each prescribed match, transfer mass across the relevant category records until its prescribed quantity is exhausted. Each transfer exhausts a record or the remaining prescribed quantity. Thus there are polynomially many transfers.

Bit lengths of evolving masses

A count of rational operations alone would not suffice. Here the operations have a stronger property: stored masses are never multiplied by other stored masses.

For the small–small matching policy, each prescribed quantity has the form
$$ \lambda\frac{z_{at,ju}}{\beta_t^a}R_{at}. $$
The coefficient multiplying $R_{at}$ has polynomial encoding length because $z$ comes from a prefix program using original revealed input data.

For the selected-pool policy, an unclipped quantity is $\delta p^j_{tuq}$. A clipped quantity has the form
$$ C_q\frac{p^j_{tuq}}{P_q}, $$
where $C_q$ is stored residual capacity and $p^j_{tuq}/P_q$ is a coefficient of polynomial encoding length. Zero $P_q$ requires no allocation.

All remaining updates are additions, subtractions, minima, or multiplication by fixed fractions. Reservoir matching programs use original revealed masses or fixed multiples of their sums; they do not use progressively altered masses as LP data.

Let $B_0$ be a polynomial bound on the encoding length of every fresh coefficient used in allocation updates. Maintain a conceptual common denominator for all stored masses. Each multiplication by a fresh coefficient, or insertion of a fresh rational, enlarges this denominator by a factor with at most $B_0$ bits. Additions, subtractions, and minima require no further enlargement.

There are polynomially many such operations, so the common denominator has polynomial bit length. Stored masses lie between zero and $2$, and their numerators therefore also have polynomial bit length. Temporary arithmetic quantities satisfy the same polynomial bound.

This establishes polynomial bit complexity, including placement, matching implementation, and completion, without expanding masses into discrete agents.

9. What remains open

The theorem proves a uniform positive competitive ratio for the full divisible cohort model. Thus an impossibility argument ruling out every positive constant ratio would be false.

It does not establish the requested constant:
$$ \frac{c_b}{4} = \frac{\ln5-4/5}{20} > \frac1{100} > \frac1{16384}. $$
The first inequality follows from $\ln5>1$.

A stronger policy, or an upper bound excluding the particular ratio $c_b/4$, is still needed.

⟨structured verdict parsed — rendered above⟩

Verification report

The output establishes a weaker uniform guarantee, subject to one minor clarification about how the prefix linear programs omit unavailable coefficients. I found no false central step or gap requiring new mathematics in the claimed $\frac{1}{16384}$ guarantee.

It does not resolve USER_TASK: neither an algorithm attaining $c_b/4$ nor an impossibility result for that ratio is proved. The prover correctly acknowledges this limitation.

1. Completion and optimum decomposition

Completion lemma. The identity
$$ S+2E=2-A $$
correctly counts remaining occupant slots. Filling singleton slots first leaves at most $2E$ incoming mass for internal pairing. Same-type pairing makes that operation feasible for arbitrary rational masses, without an integrality restriction.

The extension to feasible prescribed allocations is valid: after those allocations, the same capacity identity applies to the remaining incoming mass. At total allocated person mass $2$, nonnegativity forces both remaining singleton mass and empty room mass to vanish.

Nonnegative utilities justify ignoring the additional welfare obtained during completion.

Existence of an optimum. The proposed allocation
$$ x_{ttq}=\frac{\mu_t\rho_q}{2} $$
satisfies both category and type constraints. The feasible set is closed and bounded in finitely many variables, so the linear welfare objective attains its maximum.

Cohort refinement. Splitting the two occupant positions using $p_t^jp_u^k$ preserves room mass, welfare, and cohort–type marginals. For same-type rooms, both positions are counted, correctly giving marginal $\beta_t^j$. The resulting decomposition
$$ \mathrm{OPT}=\sum_j(V_j+I_j)+\sum_{i<j}H_{ij} $$
has neither missing contributions nor double counting.

Internal-pair replacement. Each replacement of an endpoint of person mass $a$ by a same-type pair of room mass $a/2$ preserves that endpoint’s room-value contribution. It uses its original person mass and adds nonnegative roommate welfare. The two possible endpoint replacements consume at most the original room mass. The lemma therefore establishes the packing benchmark subsequently used.

2. Cohort classification and prefix estimates

The bound $N\leq7$ is correct because each large cohort has mass strictly greater than $1/4$, while total mass is $2$.

For $K\geq32$, the stated cutoff inequalities hold. They also imply that each harmonic sum used later contains at most $s$ terms with the stated lower bounds on its denominators.

The conditional prefix-mass formulas correctly sample the other cohorts without replacement. For the single-cohort estimate,
$$ \frac{r-1}{K-1}\leq\frac14, $$
so the remaining expected mass is at most $1/2$. For two fixed cohorts, similarly,
$$ \frac{r-2}{K-2}\leq\frac14. $$
The stated expectations and both applications of Markov’s inequality follow. The resulting survival events depend only on the prefix set, which is essential for the later conditioning arguments.

3. Prefix programs and canonical selection

The within-cohort packing benchmark follows from the replacement lemma. The between-cohort matching benchmark follows by restricting the refined optimum to the relevant edges. Its omission of room categories is legitimate because its objective measures only roommate welfare; physical room feasibility is handled separately.

Both feasible regions are nonempty and bounded.

The canonical-selection argument is valid:

• Permutations of cohorts with identical mass vectors preserve the constraints and objective.
• Averaging preserves feasibility and optimality.
• Transpositions generate the required permutation groups, so polynomially many invariance constraints suffice.
• Lexicographic optimization on the resulting optimal face can be implemented by polynomially many rational linear programs.

Consequently, recommendations are independent of the prefix’s arrival order.

Minor issue — unavailable coefficients in forced-zero variables. The displayed programs nominally include variables involving types with zero mass in the relevant cohorts, potentially including types never revealed. Their objective coefficients need not yet be known. The mass constraints force these variables to zero, so this does not undermine the argument.

Minimum clarification: explicitly state that forced-zero variables are omitted before forming the programs, so every objective coefficient actually used has been revealed.

4. Small cohorts’ own welfare

The selected-pool clipping rule respects category capacities. The filler pool suffices whenever cumulative mass is at most $1$, because internally pairing that mass requires at most $1/2$ total room mass.

The conditional availability argument is sound. After fixing the current prefix and current cohort, the preceding order remains uniform. At each earlier position, canonical recommendations and the packing constraint bound expected recommended category mass by $\rho_q/\ell$. Thus
$$ \mathbb E[D_q]\leq\delta\rho_q. $$

The clipping inequality is valid, including cases where its right-hand side is negative:
$$ a_q\geq1-\frac{2D_q}{\rho_q}. $$
It yields expected implemented fraction at least $1/2$.

No unjustified independence assumption is used: current recommendations are fixed under the conditioning, and the availability bound holds under that same conditioning. Averaging over the current cohort gives the factor $1/r$.

The real and virtual processes agree on $B(\mathcal P_r)\leq1$, because cumulative mass is nondecreasing. Combining the benchmark and survival estimate gives
$$ \mathbb E[W_{\mathrm{small\ own}}] \geq\frac{r_{\max}-s}{32K}A_{\mathrm s} \geq\frac1{512}A_{\mathrm s}. $$
The constants are correct.

5. Small–small roommate welfare

The prescribed matching masses respect both earlier singleton availability and incoming anchor mass. Using the same pre-arrival $R_{at}$ on every incident edge is safe because the total incident recommendation is bounded by $\beta_t^a$.

Reserved-room feasibility follows from total anchor person mass $1/2$. The filler pool suffices up to cumulative mass $4/3$. Matching at existing singleton locations introduces no category restriction on roommate welfare.

The anchor-availability conditioning is valid. Conditional on an earlier prefix containing cohort $a$ with $a$ preceding its last arrival, that last arrival is uniform among the other $\ell-1$ cohorts. This justifies the degree-bound average. The possible loss at $a$’s own arrival is separately bounded, so it is not omitted.

The harmonic bound consequently gives
$$ \mathbb E[R_{at}]\geq\frac{\delta\beta_t^a}{2}. $$
Current recommendations are fixed under the current-prefix conditioning, making the expected current-edge calculation valid.

Each recommended edge is counted at both cohort endpoints. This correctly changes the factor $\delta\lambda/2$ into $\delta\lambda/r$ after averaging over the current cohort.

The endpoint-inclusion probability, mass-survival factor, and summation yield
$$ \mathbb E[W_{\mathrm{small\ cross}}]\geq\frac1{8192}C_{\mathrm{ss}}. $$
The numerical bounds are correct.

6. Policies involving large cohorts

Large cohorts’ own welfare. Proportional internal pairing before the first large cohort leaves the stated category supplies. Since $b_j>1/4$, implementing an $\varepsilon$ fraction of the single-cohort optimum fits category by category. The first-large probability and $N\leq7$ give the coefficient $1/56$.

Large–small welfare. Before a remaining large cohort arrives, preceding mass is strictly below $7/4$. The prescribed placements consume less than total room supply and, because they are proportional across categories, satisfy category capacities as well. Stored anchors contain an $\varepsilon$ fraction of every preceding type mass. The scaled refined-optimum matching is therefore feasible.

The event probability
$$ \frac1{N(N+1)} $$
is correct: in the induced order of the large cohorts and the selected small cohort, the small cohort must be first and the selected large cohort second. The coefficient $1/448$ follows.

Large–large welfare. Preserving the first large cohort’s anchors consumes the stated room mass. Before a second large cohort arrives, the strict bound on $A$ ensures feasibility. Subsequent internal placements require only available total empty-room capacity; no category-specific welfare is being promised.

The stored anchors support the claimed scaled matching. The unordered-pair probability and coefficient $1/168$ are correct. The fallback rules cover cases with too few large cohorts.

7. Mixture and small-$K$ cases

The mixture probabilities sum to $1$ and can be implemented with three fair bits. Multiplying the five component bounds by their selection probabilities gives exactly the listed coefficients. Their minimum is $1/16384$.

For $2\leq K\leq31$, the first policy obtains the stated own-welfare benchmark. In the second policy, every distinct pair has an orientation whose first cohort has mass at most $1$. Storing that cohort singly is feasible, and matching with the second cohort supports the corresponding refined-optimum contribution.

The fair-mixture bound
$$ \frac1{2K(K-1)}\mathrm{OPT} $$
and its minimum $1/1860$ over this range are correct.

For $K=1$, the arrival reveals all positively supported types and their relevant values and utilities, so solving the offline program is causal.

8. Causality and polynomial bit complexity

Subject to the forced-zero-variable clarification, the policies use only revealed information. Hidden aggregate masses and $N$ appear only in the analysis.

The stated linear-program dimensions are polynomial. The exact rational linear-programming theorem applies to these nonempty bounded rational programs. Canonical coordinate optimization remains on faces of the original rational polytope, so it does not require uncontrolled coordinate encoding lengths.

The allocation-record and greedy-transfer counts are polynomial.

The bit-complexity argument addresses the relevant arithmetic risk. Evolving masses are multiplied only by fresh coefficients of polynomial encoding length. Additions, subtractions, and minima do not enlarge a conceptual common denominator once operands share it. Polynomially many coefficient insertions and multiplications therefore produce polynomial bit lengths. The reservoir programs do not use recursively modified anchor masses, so they do not introduce an unaccounted feedback mechanism.

9. What the output establishes

The weaker theorem is supported, with the minor implementation clarification identified above. It is genuine progress toward the continuous model.

The requested ratio is strictly larger:
$$ \frac{c_b}{4}=\frac{\ln5-4/5}{20}>\frac1{100}>\frac1{16384}. $$
The output’s inequality is correct. Establishing its weaker guarantee neither proves the requested guarantee nor rules it out. Thus the proper task-level classification is partial, consistent with the prover’s own claim.

⟨structured verdict parsed — rendered above⟩