| paper | d4-conf-ecai-2024-0488 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
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. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 5
statement extracted from the paper’s text layer
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 population with mass \(\mu_r\) in each of finitely many propensity types \(r\), arriving at public rates \(\lambda_r(t)\). The state records mass of open tables by integral type composition \(S\); control flows assign arriving mass to those states, and each assignment earns expected welfare \(2p_r\sum_q S_qp_q\).
The full-horizon flow can use future class arrival rates, while the paper's online algorithm cannot see future arrivals; the case calls the schedule external but does not say explicitly that it is public.
fatal: False
The mirror covers Theorem 5's CLV welfare guarantee for finite propensity classes after passing to expected per-capita welfare. It does not retain individual-utility or total-welfare threshold stochastic dominance, predictor robustness in Theorem 2, density monotonicity in Theorem 4, or the welfare estimates in Theorems 7 and 8.
My strongest case is the finite-support, high-multiplicity slice of the paper’s CLV result. The paper has no named in-paper hardness theorem, so I would not use its discussion of offline hardness as an anchor. The anchor is Theorem 5, “MPCF’s Optimality for Welfare Maximization,” proved here: for any CLV weight vector \(p\in[0,1]^n\), any online algorithm \(A\), and every threshold \(k\geq 0\), (1) for each agent \(i\), the probability that \(i\) gets at least \(k\) friends in their coalition under \(A\) is at most that probability under MPCF; and (2) the probability that total social welfare is at least \(k\) under \(A\) is at most that probability under MPCF. This is a strong anchor because it compares MPCF with every online algorithm, though it establishes stochastic optimality rather than a complexity class.
Here is the regime I would put behind its mirror: a very large conference or other event whose attendees are assigned irrevocably to tables of fixed capacity \(\alpha\). Attendees fall into a fixed number \(\tau\) of propensity classes. Members of class \(r\) share the same parameter \(p_r\), and friendship edges are independently present with probability \(p_rp_s\) between classes \(r\) and \(s\), as in CLV. Exact friendships are hidden; the assignment authority sees the class and uses the corresponding expected-friend predictions. As the number of attendees \(N\) grows, each class has \(N_r/N\to\mu_r\), while \(\tau\) and \(\alpha\) stay fixed. The arrival pattern is an external schedule, not an additional personal attribute.
I would call the mirror Continuous CLV Online Coalition Welfare. An instance has a finite class set \(R\), rational \(p_r\in[0,1]\), capacity \(\alpha\), and piecewise-constant arrival rates \(\lambda_r(t)\) on \(t\in[0,1]\), with \(\int_0^1\lambda_r(t)\,dt=\mu_r\) and \(\sum_r\mu_r=1\). A coalition’s state is its composition \(S\in\mathbb{N}^{R}\), with \(|S|<\alpha\). Let \(z_S(t)\) be the mass of open coalitions in state \(S\), and \(x_{r,S}(t)\) the rate at which arriving class-\(r\) mass joins such coalitions; \(S=\mathbf 0\) means opening a new singleton. Feasibility requires \(\sum_S x_{r,S}(t)=\lambda_r(t)\), \(z_S(0)=0\), \(z_S(t)\geq0\), and, for nonempty \(S\),
\[
\dot z_S(t)=\sum_{r:S_r>0}x_{r,S-e_r}(t)-\sum_r x_{r,S}(t).
\]
A full coalition leaves the open-state system. The objective, expected welfare per attendee, is
\[
\mathcal W(x)=\int_0^1\sum_{r,S}2p_r\!\left(\sum_q S_qp_q\right)x_{r,S}(t)\,dt.
\]
The factor \(2\) counts both endpoints’ utility for each expected friendship. The question is to return a feasible online flow and its value maximizing \(\mathcal W\). The mirror’s specific claim to prove or refute is that the fluid version of MPCF is an optimizer for every such instance. It assigns arriving mass to available coalitions with maximum positive \(\sum_q S_qp_q\), splitting ties in proportion to the mass of tied coalitions; if none has positive predicted friendship, it opens singletons. That is the continuous counterpart of greedily choosing a coalition with the most predicted friends.
This seems recognizable to the authors as their problem: it preserves online arrivals, irrevocable assignments, fixed-size coalitions, uncertain friendships, the CLV relation, and utilitarian welfare. It continuizes the population by tracking normalized mass in coalition-composition states; there are \(O(N)\) tables, each still holding at most \(\alpha\) agents. For this finite-type, fixed-\(\alpha\) regime, I expect the mirror to be tractable in the programme’s Class A sense: the paper’s structural greedy rule is a candidate optimal fluid policy. That is a prediction suggested by Theorem 5, not a claim that the paper proves polynomial-time computation of every fluid trajectory. Useful follow-up questions are whether finite-\(N\) MPCF converges to this flow, at what rate, and whether any form of the theorem’s stochastic dominance survives after scaling.
My weakest point is the change in what is being compared. Theorem 5 orders finite random welfare distributions—and individual utilities—at every threshold. The fluid problem retains expected welfare per capita, but averaging into mass flows removes finite-instance randomness and does not preserve that full stochastic-dominance claim. The mirror is therefore a credible high-multiplicity optimization question, but a weaker analogue of the anchor than a theorem about continuum stochastic dominance would be.
The strongest case against Theorem 5 as a ChoCo anchor is that its distinctive claim is about finite random outcomes: MPCF stochastically dominates every online algorithm at every welfare threshold, and separately for each agent’s utility. It is a real computational result, but it is not a complexity classification or an algorithmic running-time result of the kind the programme is set up to chart.
The proposed mass-flow model also does not yet preserve the paper’s online information constraint. Choosing the trajectory \(x(t)\) by optimizing over the full horizon can use the future arrival profile \(\lambda_r(t)\). Unless that profile is public in advance, the flow is anticipatory; making it causal requires a different model of what the algorithm knows and when. Arrival order matters because it determines which coalitions an agent can join. Grouping attendees by propensity while treating their schedule as external is defensible in a planned event, but the stronger version of the mirror must say how that schedule is known and keep the policy causal.
There is a further mismatch in what survives the population limit. With fixed capacity \(\alpha\), each agent’s utility remains a bounded, discrete random variable, while normalized total welfare averages over an increasing population. The flow objective captures expected welfare per capita, but the theorem’s all-threshold ordering of total-welfare distributions is not itself a population-mass objective. One could track utility histograms for cohorts, or retain fluctuation-scale statistics, but those additions move beyond the proposed deterministic welfare flow. They may make a richer mirror, though they do not obviously produce the complexity landscape the programme seeks.
That is the negative case at its strongest: the clean flow model risks changing an online stochastic comparison into a known-profile fluid-control problem, and the theorem it anchors is not a complexity result. But it does not defeat the best mirror. A large event with finitely many propensity classes and a publicly known arrival schedule is a plausible high-multiplicity regime, and a causal fluid limit that tracks coalition-state and cohort flows could be a worthwhile computational question. I cannot honestly argue that no scenario yields a worthwhile mirror; the case against is one of fit and priority, not a fundamental obstruction.
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.