Answer: For every fixed \(\alpha\ge2\), threshold decision and optimal-control computation are in \(\mathrm P\). The optimum is \((\alpha-1)\sum_r\mu_rp_r^2\). Every capacity admits a fluid MPCF trajectory that is strictly suboptimal.
Theorem 5 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateIn the CLV model, let p ∈[0, 1]n be a weight vector and let A be an online algorithm for our problem. Then, for any k ≥0: 1. For any agent i: P[vi(Ai(Gp)) ≥k] ≤P[vi(A⋆ i (Gp)) ≥k]. 2. P[SW(A(Gp)) ≥k] ≤P[SW(A⋆(Gp)) ≥k].
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite class set \(R\), fixed table capacity \(\alpha\), rational propensities \(p_r\), and a publicly known piecewise-constant arrival rate \(\lambda_r(t)\) on \(t\in[0,1]\), with \(\int_0^1\lambda_r(t)\,dt=\mu_r\), let friendships be independently present with probability \(p_rp_s\) and hidden from the assigning authority. Let \(z_S(t)\) be the normalized mass of open tables with composition \(S\in\mathbb{N}^R\), \(|S|<\alpha\), and \(x_{r,S}(t)\) the rate at which class-\(r\) arrivals join tables in state \(S\), where \(S=\mathbf{0}\) opens a table. Among feasible controls that use only the current table state and public schedule, maximize expected per-capita welfare \(\mathcal W(x)=\int_0^1\sum_{r,S}2p_r(\sum_q S_qp_q)x_{r,S}(t)\,dt\). Does the fluid limit of MPCF, including its minimum-total-predicted-degree tie-break and proportional splitting of exact ties, maximize this objective for every instance, and how efficiently can an optimal control be computed?
A society is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational; \(\tau\) is the support size, not the number of possible types. Here \(R\) is that support, \(m=|R|=\tau\), \(\mu_r>0\), and \(\sum_r\mu_r=1\).
Fix an integer table capacity \(\alpha\ge2\). Each type has a binary rational propensity \(p_r\in[0,1]\); distinct agents of types \(r,s\) are independently friends with probability \(p_rp_s\), and friendships remain hidden. Nonnegative arrival rates \(\lambda_r\) are constant on a common partition of \([0,1]\) into \(K\) intervals with rational endpoints and rational rates, and \(\int_0^1\lambda_r(t)\,dt=\mu_r\). The entire schedule is public.
Tables start empty; arrivals must be assigned immediately and irrevocably, with unlimited new tables and no reassignment. Write \(e_r\) for a unit vector, \(|S|=\sum_rS_r\), and \(\mathcal S=\{S\in\mathbb Z_{\ge0}^{R}:1\le|S|<\alpha\}\). Let \(z_S\) be table mass per unit total population and \(x_{r,S}\ge0\) the integrable assignment rate; \(x_{r,\mathbf0}\) opens a new singleton table.
Feasibility means \(\sum_{S\in\mathcal S\cup\{\mathbf0\}}x_{r,S}=\lambda_r\) almost everywhere and, for every \(S\in\mathcal S\), \(z_S(0)=0\), \(z_S\ge0\), and \(\dot z_S=\sum_{r:S_r>0}x_{r,S-e_r}-\sum_rx_{r,S}\). Full tables leave the open inventory; unfinished tables may remain at the end. Simultaneous inflow and outflow through a zero inventory are permitted. Controls may depend only on time, the current inventories, and the public data.
Maximize expected per-capita welfare \(\mathcal W(x)=\int_0^1\sum_{r,S\in\mathcal S\cup\{\mathbf0\}}2p_r(\sum_qS_qp_q)x_{r,S}(t)\,dt\). The decision input additionally includes a binary rational threshold \(b\).
Define fluid MPCF through finite populations of size \(N\), with exactly \(N\mu_r\) agents of each type and cumulative arrivals divided by \(N\) converging uniformly to the integrated schedule. An arriving type \(r\) chooses an available nonfull table maximizing the strictly positive score \(p_r\sum_qS_qp_q\), then minimizing \(\sum_qS_qd_q^{(N)}\), where \(d_q^{(N)}=p_q(N\sum_s\mu_sp_s-p_q)\); if no positive score exists, it opens a table. Remaining ties are uniform over individual tables, hence split proportionally to their counts. A fluid MPCF trajectory is any subsequential limit in probability of the normalized cumulative assignment flows, uniformly in time, over such arrival sequences.
Is deciding whether a feasible control satisfies \(\mathcal W(x)\ge b\) in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard, for each fixed \(\alpha\)? Does every fluid MPCF trajectory maximize \(\mathcal W\), and what is the complexity of computing an optimal control? State running times in \(m,\tau,K,L\), and \(\alpha\), where \(L\) is the total input bit length.
The discrete optimality result states that MPCF stochastically dominates every online assignment algorithm in social welfare for independent product-probability friendships ([source](https://journals.sagepub.com/doi/pdf/10.3233/FAIA240882)).
A known continuous approximation tracks singleton counts and bounds MPCF welfare, rather than optimizing the composition-flow problem above ([source](https://u.cs.biu.ac.il/~agmon/CohenECAI24Sup.pdf)). No result settling this exact continuous problem was located.
I interpret the decision question as asking whether there exists a feasible control with welfare at least \(b\), since the input does not include an encoding of a control.
For every fixed \(\alpha\ge2\), this decision problem belongs to \(\mathrm P\). In fact, the exact optimum is
\(\displaystyle \mathcal W^*=(\alpha-1)\sum_{r\in R}\mu_rp_r^2.\)
An optimal control has an explicit formula and can be computed in polynomial time. Every fluid MPCF trajectory need not be optimal: a counterexample exists for every \(\alpha\ge2\), using two types with strictly positive propensities and constant arrival rates.
The argument below uses exactly the stated feasibility rules. The optimal control is also realizable as a limit of immediate, irrevocable finite assignments.
Let \(\mathcal T=\{T\in\mathbb Z_{\ge0}^{R}:1\le |T|\le\alpha\}\). Extend the inventory definition to full tables by setting, for \(|T|=\alpha\),
\(\displaystyle z_T(t)=\int_0^t\sum_{r:T_r>0}x_{r,T-e_r}(u)\,du.\)
These extended inventories are nonnegative and absolutely continuous.
Define
\(\displaystyle P(T)=\sum_rT_rp_r,\qquad A(T)=\sum_rT_rp_r^2,\qquad F(T)=P(T)^2-A(T),\)
with all three functions equal to zero at \(\mathbf0\).
For any function \(h\) on \(\mathcal T\cup\{\mathbf0\}\) with \(h(\mathbf0)=0\), the inventory equations give, almost everywhere,
\(\displaystyle \frac{d}{dt}\sum_{T\in\mathcal T}h(T)z_T(t) =\sum_{r,S\in\mathcal S\cup\{\mathbf0\}}\bigl(h(S+e_r)-h(S)\bigr)x_{r,S}(t).\)
Indeed, each assignment removes one unit of table mass from its source composition, when nonempty, and adds one unit to its destination composition. Summing the inventory equations produces precisely these increments. All sums are finite.
For \(h=A\), the increment is \(p_r^2\). Integrating and using the arrival constraints yields
\(\displaystyle \sum_{T\in\mathcal T}A(T)z_T(1)=\sum_r\mu_rp_r^2.\)
For \(h=F\), direct calculation gives
\(\displaystyle F(S+e_r)-F(S)=2p_rP(S).\)
Consequently,
\(\displaystyle \mathcal W(x)=\sum_{T\in\mathcal T}F(T)z_T(1).\)
To bound \(F(T)\), write the propensities of the \(n=|T|\) members, including repetitions, as \(a_1,\ldots,a_n\). The identity
\(\displaystyle n\sum_{i=1}^na_i^2-\left(\sum_{i=1}^na_i\right)^2 =\sum_{i<j}(a_i-a_j)^2\)
implies
\(\displaystyle F(T)=(n-1)A(T)-\sum_{i<j}(a_i-a_j)^2\le(\alpha-1)A(T).\)
Multiplying by the nonnegative terminal inventories and summing proves
\(\displaystyle \mathcal W(x)\le(\alpha-1)\sum_r\mu_rp_r^2.\)
More precisely, the argument establishes the exact deficit identity
\(\displaystyle (\alpha-1)\sum_r\mu_rp_r^2-\mathcal W(x) =\sum_{T\in\mathcal T}z_T(1)\left[(\alpha-|T|)A(T)+\sum_{i<j}(a_i-a_j)^2\right].\)
Thus unfinished tables containing positive propensities and tables mixing unequal propensities both contribute explicitly to the welfare deficit.
For each \(r\in R\) and each integer \(j\) with \(0\le j<\alpha\), set
\(\displaystyle x^*_{r,je_r}(t)=\frac{\lambda_r(t)}{\alpha},\)
where \(0e_r=\mathbf0\). Set every other assignment rate to zero, and set \(z^*_S(t)=0\) for every open composition \(S\).
These rates are nonnegative and integrable. For each type, there are exactly \(\alpha\) designated assignment coordinates, so
\(\displaystyle \sum_Sx^*_{r,S}(t)=\lambda_r(t).\)
For every pure open composition \(je_r\), its inflow and outflow are both \(\lambda_r(t)/\alpha\). Mixed compositions have zero inflow and zero outflow. Therefore every inventory equation holds with zero inventory. This is permitted by the stated simultaneous-throughflow convention. The control depends only on time and public data.
Its welfare is
\(\displaystyle \mathcal W(x^*) =\sum_r\int_0^1\frac{\lambda_r(t)}{\alpha} \sum_{j=0}^{\alpha-1}2jp_r^2\,dt =(\alpha-1)\sum_r\mu_rp_r^2.\)
This attains the upper bound and proves the claimed optimum for every admissible schedule.
Consider the finite policy that maintains at most one unfinished table per type and assigns each arriving agent to that type’s unfinished table, opening a new table when necessary. It requires no reassignment or knowledge of future arrivals.
If \(n_r^{(N)}(t)\) type-\(r\) agents have arrived by time \(t\), the number of assignments to each position \(j\) in a pure type-\(r\) table differs from \(n_r^{(N)}(t)/\alpha\) by at most one. Hence uniform convergence of normalized arrivals implies uniform convergence of these assignment flows to
\(\displaystyle X^*_{r,je_r}(t)=\frac1\alpha\int_0^t\lambda_r(u)\,du.\)
Each open composition has inventory at most \(1/N\), so its normalized inventory converges uniformly to zero.
There is also an exact finite welfare calculation. Let \(k_r\) be the remainder of \(N\mu_r\) upon division by \(\alpha\). The policy’s expected per-capita welfare is
\(\displaystyle (\alpha-1)\sum_r\mu_rp_r^2-\frac1N\sum_rk_r(\alpha-k_r)p_r^2.\)
The loss is at most \(m\alpha^2/(4N)\). Thus the optimum is supported by ordinary finite assignments as well as by the fluid equations.
Fix \(\alpha\ge2\). Use two types, denoted \(\ell\) and \(h\), with
\(\displaystyle \mu_\ell=\mu_h=\frac12,\qquad p_\ell=\frac12,\qquad p_h=1,\qquad \lambda_\ell(t)=\lambda_h(t)=\frac12.\)
Here \(m=\tau=2\) and \(K=1\).
Take population sizes divisible by \(2\alpha\), place arrival number \(i\) at time \(i/N\), and repeat the length-\(2\alpha\) word
\(\displaystyle \ell^{\alpha-1}h\,\ell h^{\alpha-1}.\)
Each period contains exactly \(\alpha\) agents of each type. The normalized cumulative arrivals therefore converge uniformly to the specified constant-rate schedule.
MPCF fills consecutive blocks of \(\alpha\) arrivals. To prove this, initially there is no table. Once the first agent opens a table, its propensity sum is positive. Every subsequent arrival has positive propensity and therefore assigns to that table until it becomes full. During this process no other table opens. Induction repeats the argument after each completed table. There is never a choice between two available tables, so neither degree tie-breaking nor random tie-breaking affects this execution.
Each arrival period consequently creates two full tables:
This execution has a fluid limit in the definition given in the question. Explicitly, let \(c_{r,S}\) count assignments to coordinate \((r,S)\) during one period. Then
\(\displaystyle \sup_{t\in[0,1]} \left|X^{(N)}_{r,S}(t)-\frac{c_{r,S}}{2\alpha}t\right| \le\frac{2\alpha}{N}.\)
Thus every cumulative assignment coordinate converges uniformly and deterministically, hence in probability. Nonfull inventories are at most \(1/N\). Each period’s complete table chains have equal inflow and outflow at every open composition, so the limiting constant rates satisfy the fluid balance equations with zero inventory.
The optimum for this society is
\(\displaystyle \mathcal W^*=\frac{5(\alpha-1)}8.\)
In each of the two MPCF tables, there are \(\alpha-1\) unequal-propensity pairs, each with squared propensity difference \(1/4\). Applying the deficit identity to the \(2\alpha\)-agent period gives
\(\displaystyle \mathcal W_{\mathrm{MPCF}} =\frac{5(\alpha-1)}8-\frac{\alpha-1}{4\alpha} <\mathcal W^*.\)
Therefore every capacity admits a suboptimal fluid MPCF trajectory.
The cited paper states the stochastic-dominance assertion in Theorem 5. Under the explicit assignment rules in this question, it is already contradicted by a finite example. [Cohen and Agmon, Theorem 5](https://journals.sagepub.com/doi/pdf/10.3233/FAIA240882).
Take capacity \(\alpha=2\) and the four-agent arrival sequence \(\ell,h,\ell,h\), with propensities \(1/2,1,1/2,1\).
MPCF creates two mixed pairs. Their independent friendship indicators each have probability \(1/2\), giving expected total welfare \(2\).
The causal policy that pairs agents of the same propensity creates a low-low pair and a high-high pair. Their friendship probabilities are \(1/4\) and \(1\), giving expected total welfare \(5/2\).
There is a direct failure of stochastic dominance: the same-propensity policy has total welfare at least \(2\) with probability \(1\), whereas MPCF has total welfare at least \(2\) with probability \(3/4\).
Thus the cited dominance assertion cannot be applied as a valid theorem for the model specified here. The conclusions above follow independently from the flow equations and explicit assignments.
Let \(L\) be the total input bit length and put \(B=L+\lceil\log_2(\alpha+1)\rceil\). Here \(m=\tau\); no enumeration of absent types is required.
The decision algorithm computes the rational number
\(\displaystyle V=(\alpha-1)\sum_{r=1}^{m}\mu_rp_r^2\)
and answers yes exactly when \(V\ge b\). It uses \(O(m)\) rational arithmetic operations. Without reducing intermediate fractions, all numerators and denominators have \(O(B)\) bits: their lengths are bounded by sums of the input operand lengths. Using elementary integer arithmetic, a conservative bit-time bound is \(O(L+mB^2)\). For every fixed \(\alpha\), this is polynomial in \(L\).
An optimal control can be returned through the formula in Section 3 together with the input schedule. If explicit rates on each interval are required:
| Output representation | Running-time bound |
|---|---|
| Compact rule, with the \(mK\) rates \(\lambda_{r,k}/\alpha\) | \(O(L+mKB^2)\) bit operations |
| Sparse expansion listing the designated coordinates | \(O(L+mK\alpha B^2)\) bit operations |
| Dense expansion listing every assignment coordinate | \(O\!\left(L+Km\binom{m+\alpha-1}{\alpha-1}B^2\right)\) bit operations |
The dense count follows because \(\mathcal S\cup\{\mathbf0\}\) contains \(\binom{m+\alpha-1}{\alpha-1}\) compositions. Every rate is constant on the supplied partition, and all open inventories are identically zero.
Consequently, both threshold decision and optimal-control computation belong to \(\mathrm P\) for each fixed capacity.
⟨structured verdict parsed — rendered above⟩
Assessment: proved. The output resolves the intended existential decision problem, supplies an optimal control, and disproves universal optimality of fluid MPCF for every fixed capacity. I found no mathematical errors or gaps requiring clarification.
The existential interpretation is appropriate: the input specifies a society, schedule, and threshold, but no encoded control to evaluate.
The argument uses the actual support, with \(m=\tau\), and applies to every admissible schedule. Its use of simultaneous inflow and outflow at zero inventory is explicitly authorized by the task. This is a substantive feature of the specified model, not an unintended degenerate interpretation.
Extending inventories to full tables is valid: the defining integrands are nonnegative and integrable, and full tables have no outgoing assignments.
The telescoping identity correctly accounts for every assignment. Opening a singleton contributes only the destination term because \(h(\mathbf0)=0\); completing a table contributes to the extended full-table inventory. All sums are finite for any fixed instance.
For \(A\), the increment is exactly \(p_r^2\). The arrival constraints and normalization therefore give the claimed terminal identity.
For \(F\), expanding the square verifies
\(F(S+e_r)-F(S)=2p_rP(S)\).
Thus the terminal expression for welfare is correct, including unfinished tables.
The squared-difference identity has the correct coefficient: each unordered pair appears once. Consequently,
\(F(T)=(|T|-1)A(T)-\sum_{i<j}(a_i-a_j)^2\).
Since \(|T|\le\alpha\) and terminal inventories are nonnegative, the upper bound follows.
The exact deficit identity also checks out. Both terms inside its brackets are nonnegative. Zero propensities and repeated propensities cause no exception.
For each type, the designated source compositions are distinct and number exactly \(\alpha\). Their assignment rates sum to \(\lambda_r\).
At each pure open composition, the designated incoming and outgoing rates agree. No designated assignment enters or leaves a mixed composition. Hence setting every open inventory to zero satisfies the balance equations, initial conditions, and nonnegativity requirements.
The control uses only time and public data, as required. Piecewise constant input rates make it integrable.
The welfare calculation correctly uses
\(\sum_{j=0}^{\alpha-1}2j=\alpha(\alpha-1)\).
It attains the universal upper bound, establishing an attained optimum rather than merely a supremum.
The proposed finite policy is immediate, irrevocable, and causal. Keeping one unfinished table per type respects the unlimited-table model.
Assignment positions cycle through \(\alpha\) possibilities. The stated discrepancy of at most one from \(n_r^{(N)}(t)/\alpha\) is correct, uniformly over time. This establishes the asserted cumulative-flow convergence along population sizes satisfying the task’s exact-count requirement.
Each pure open composition contains at most one unfinished table, so its normalized inventory is at most \(1/N\).
The finite expected-welfare formula is correct. A remainder table of size \(k_r\) contributes \(k_r(k_r-1)p_r^2\), yielding the stated deficit \(k_r(\alpha-k_r)p_r^2/N\). The bound follows from \(k_r(\alpha-k_r)\le\alpha^2/4\) and \(p_r^2\le1\).
The example satisfies all input conditions: positive rational masses, rational propensities, constant nonnegative rates, and correct integrated arrivals.
Each repeated word contains exactly \(\alpha\) arrivals of each type. Its bounded period discrepancy establishes uniform convergence to the specified schedule.
The consecutive-block argument is valid. All propensities are strictly positive. Once a singleton opens, the sole nonfull table has positive score for every subsequent arrival and is filled before another table opens. Thus neither degree tie-breaking nor random tie-breaking affects this execution.
Population sizes divisible by \(2\alpha\) ensure complete periods and complete final tables. The coordinate convergence bound is valid; deterministic convergence also gives convergence in probability. The limiting rates satisfy the inventory equations with zero open inventory.
The optimum \(5(\alpha-1)/8\) is calculated correctly. Each completed table has exactly \(\alpha-1\) unequal-propensity pairs, each contributing \(1/4\) to the deficit. Dividing the total deficit of the two tables by \(2\alpha\) gives \((\alpha-1)/(4\alpha)\), as claimed.
This remains strictly positive at \(\alpha=2\). The construction therefore disproves “every fluid MPCF trajectory is optimal” for every permitted capacity. It does not claim that every trajectory is suboptimal.
The source does state the asserted welfare dominance in Theorem 5, and its Algorithm 1 uses the positive-score rule described by the prover. The attribution is accurate. [Cohen and Agmon, Algorithm 1 and Theorem 5](https://journals.sagepub.com/doi/pdf/10.3233/FAIA240882).
The four-agent counterexample is valid under the task’s explicit rules. MPCF makes two mixed pairs, with independent friendship probabilities \(1/2\). The competing causal policy makes same-propensity pairs with probabilities \(1/4\) and \(1\).
Expected total welfares are therefore \(2\) and \(5/2\). The claimed tail probabilities at total welfare \(2\) are also correct: \(3/4\) for MPCF and \(1\) for the competing policy.
Thus the quoted dominance assertion cannot override the explicit counterexample in this model. The continuous proof does not rely on that assertion.
Computing the optimum requires \(O(m)\) rational arithmetic operations. The intermediate bit-length claim is sound: unreduced denominator lengths grow by sums of input denominator lengths, with only constant multiplicities from squaring propensities. Numerator lengths and multiplication by \(\alpha-1\) remain \(O(B)\).
Exact comparison with the rational threshold fits the stated conservative bound \(O(L+mB^2)\).
The compact and sparse control bounds correctly account for interval rates and designated assignments. The dense composition count
\(\binom{m+\alpha-1}{\alpha-1}\)
correctly counts all nonnegative compositions of size at most \(\alpha-1\), including the empty composition.
All three output bounds are polynomial for fixed \(\alpha\). The output distinguishes the representations appropriately and does not require enumeration of absent types.
Issues and repair feedback: none. All assigned questions are resolved by the argument as written.
⟨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.