| paper | d4-conf-ecai-2025-0261 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: $\rho^*(b,B)=\min\left\{\frac{b+\sqrt{b^2+4bB}}{2B},\frac{3b}{B}\right\}$. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 6
statement extracted from the paper’s text layer
Given a finite type set \(T\), masses \(\mu\), and a monotone bounded type-symmetric game \(v(A)\) on finite multisets \(A\), what is the best worst-case welfare ratio achievable by a causal, irrevocable, non-wasteful sharing policy when type mass arrives over time and follows the paper’s greedy choice rule, compared with \(\operatorname{OPT}(\mu,v)=\max_{\lambda_A\ge0}\sum_{1\le |A|\le\delta}\lambda_Av(A)\) subject to \(\sum_A a_t(A)\lambda_A=\mu_t\) for every \(t\in T\)?
Use type masses \(\mu_t\) and a time-indexed arrival measure for each type; represent the online state by densities of finite coalition templates and their partial histories. A policy observes only the revealed arrivals and current coalition values, chooses value shares, and induces greedy choices; compare its welfare with the configuration benchmark \(\operatorname{OPT}(\mu,v)\).
The paper has atomic, identity-dependent players, while the proposed mass-arrival model does not fully define how infinitesimal arrivals assemble into finite coalitions or resolve greedy choices.
fatal: False
The mirror covers Theorem 6’s AMC-\(h\) guarantee for \(V_{\delta}\) with \(\delta\ge3\); it leaves the other irrevocable and non-irrevocable bounds outside.
The best positive case is for a high-multiplicity version of the paper’s online coalition policy design problem. But the anchor audit has a clear limit: the paper contains no named computational complexity result. Its Theorems 1–9 establish competitive-ratio bounds, not whether a problem is in P, NP-hard, fixed parameter tractable, or otherwise computationally hard. So none qualifies as an anchor under the requested standard.
The closest substantive result to extend is Theorem 6, proved here. It says that for monotone bounded games in \(V_\delta\) with \(\delta\ge3\), the AMC-\(h\) policy achieves competitive ratio \(\min\{1/2,3\mathsf{min}/\mathsf{max}\}\), using \(h=\mathsf{min}\) when \(\mathsf{max}<4\mathsf{min}\) and \(h=2\mathsf{min}\) when \(\mathsf{max}\ge4\mathsf{min}\). That is a policy guarantee, not a computational-complexity result, so it can motivate a mirror but cannot serve as a qualifying anchor.
A plausible regime is a large project with many participants drawn from a small number \(\tau\) of recurring contribution roles: for example, many firms or workers in a few industries, where coalition value depends on the roles represented. A type must include everything relevant to contribution and utility; agents of the same type must be interchangeable in the game. The regime is \(n\gg\tau\), with type masses \(\mu_t=n_t/n\). An arrival path still matters: the stream of types becomes a continuous cumulative arrival profile, and the policy sees only the prefix that has arrived.
Here is a concrete candidate extension, High-Multiplicity Online Coalition Design. Its parameters are a finite type set \(T\), masses \(\mu_t\), and bounds \(\mathsf{min},\mathsf{max}\) defining \(V_\delta\). Nature chooses a monotone, bounded game whose value depends on the multiset of types in a coalition, along with an arrival path consistent with \(\mu\). The mechanism sees arrivals and the current coalition’s relevant marginal values, but not the future path. Each arriving type chooses greedily among starting a coalition and joining an existing one; the mechanism chooses an efficient, irrevocable sharing rule. The solution is a causal rule and its worst-case guarantee, measured against the offline optimum.
Because Theorem 1 in the paper shows that an optimal coalition in \(V_\delta\) has at most \(\delta\) members, the offline benchmark has a finite configuration form. If \(\lambda_A\) is the number of coalitions of type multiset \(A\), normalized per agent, then
\[ \mathrm{OPT}_{\mathrm{mass}}(v,\mu) = \max_{\lambda_A\ge0} \sum_{1\le |A|\le\delta}\lambda_A v(A) \quad\text{subject to}\quad \sum_A a_t(A)\lambda_A=\mu_t\ \text{for every }t\in T. \]
The online outcome can likewise be represented by frequencies of coalition patterns. The proposed problem asks for the best worst-case ratio between that online welfare and \(\mathrm{OPT}_{\mathrm{mass}}\). This is a genuine population continuization: the society is represented by type masses and the number of coalition instances becomes large. The finite coalition templates are a co-modification needed because, in the paper’s bounded-value regime, optimal coalitions remain bounded in size.
I would expect this *new exact policy-design problem* to be continuum-specifically hard, if it is hard: it combines causal policy choice, greedy behavior, and adversarial arrival paths. That is only a conjecture; Theorem 6 supplies no complexity classification, and there is no hardness result here to transfer. The main follow-up questions are whether the theorem’s guarantee survives as a limit of discrete instances, whether the configuration LP makes policy synthesis tractable for fixed \(|T|\) and \(\delta\), and how to define continuous tie-breaking so it matches limits of discrete arrival orders.
The weak point is substantial: the paper permits arbitrary identity-dependent characteristic functions, while this mirror restricts attention to type-symmetric games. Also, when coalition sizes stay bounded as \(n\) grows, an individual coalition contains vanishing population mass. The mirror remains plausible for repeated-role settings, but it is best understood as a continuous extension of Theorem 6’s policy-design problem—not as a continuous version of a computational result already established by the paper.
The decisive point is that this paper has no named computational result to mirror. Theorems 1–9 prove competitive-ratio bounds for policies; they do not classify the complexity of an input problem or give algorithms for solving one. Theorem 6 is the strongest policy guarantee, but calling a policy explicit and executable does not turn its guarantee into a complexity result.
The proposed recurring-role setting is plausible, and its configuration LP is a sensible way to compute an *offline* benchmark under the added assumptions of type symmetry and bounded optimal coalition size. But that LP does not model the paper’s online policy question: it records which coalition types occur, not how they formed or how arrivals and the sharing policy shaped greedy choices. A richer mass model could track those histories, but that would be a new online mechanism-design model, not a continuous version of Theorem 6’s computational result.
The stronger proposal—computing the best causal policy for a mass arrival path—could be made into a research problem. It first needs choices the paper does not make: how the game is encoded, what information a policy observes, which policies are allowed, and how the adversary’s arrival path is represented. Under the paper’s unrestricted \(v:2^N\to\mathbb{R}^+\), instances are identity-dependent; imposing a concise role-symmetric representation makes a different model. Those choices may yield worthwhile complexity questions, but the complexity would belong to the newly specified policy-synthesis problem, not to a computational problem established by this paper.
So the negative case is strong against the proposed anchors as ChoCo mirrors, but weak as the universal claim that no scenario could support a worthwhile continuous extension. A large population with recurring roles is a credible setting. The honest conclusion is narrower: the proponent has described a plausible new direction, but has not supplied a computational result of this paper for it to mirror.
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.