| paper | d4-conf-sagt-2024-0014 |
| 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: Polynomial-time solvable in \(m,\tau,L\). All core allocations are exactly the optimal fractional maximal-clique covers with vertex demands \(\bar\rho w_v\); an allocation supported on at most \(m\) maximal cliques can be computed. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given a perfect conflict graph \(G=(V,E)\), rational base costs \(w_v\), and a finite-support population with masses \(\mu_t\) and account scales \(\rho_t\), compute and characterize per-unit-mass firm allocations \(y_Q\) with total \(\bar\rho\alpha_w(V)\) that satisfy \(\sum_{Q:Q\cap S\ne\varnothing}y_Q\ge\bar\rho\alpha_w(S)\) for every scenario \(S\subseteq V\), where \(\bar\rho=\sum_t\mu_t\rho_t\) and \(\alpha_w(S)\) is the maximum-cost stable-set value in \(G(S)\).
Types are beneficiary account classes with masses \(\mu_t\) and cost scales \(\rho_t\); the shared decision is a per-unit-mass allocation \(y_Q\) to maximal cliques \(Q\). Its total is \(\bar\rho\alpha_w(V)\), and every scenario must have enough pooled money to cover demand \(\bar\rho\alpha_w(S)\).
The mirror covers Theorem 2 and the associated nonemptiness consequence for perfect graphs with common relative asset values and access; it leaves arbitrary graphs and heterogeneous asset values outside the stated characterization.
My strongest case is a type-mass pooled-investment core. Consider a large managed fund with \(N\) beneficiary accounts. Accounts are grouped by complete financial type: each type \(t\) has mass \(\mu_t\), the same asset access and relative asset values as the others, and a rational scale factor \(\rho_t\) for its account size. Thus \(N\) may be enormous while the support size \(\tau\) stays small. A common investment desk pools the capital, and every account faces the same market scenario.
Keep the paper’s perfect asset-conflict graph \(G=(V,E)\), its maximal cliques \(\mathcal F\) as firms, and base asset costs \(w_v\). Type \(t\) has costs \(\rho_t w_v\); its diversified investment in scenario \(S\subseteq V\) is still a maximum-cost stable set, not a fractional portfolio. Write \(\alpha_w(S)=\max_{I\subseteq S\text{ stable}}\sum_{v\in I}w_v\) and \(\bar\rho=\sum_t\mu_t\rho_t\). The total capital per unit mass is \(W=\bar\rho\,\alpha_w(V)\).
The underlying question is: how should the fund allocate this per-capita capital among firms so that it can buy the optimal diversified investment for every possible scenario? Choose \(y_Q\ge 0\) for each \(Q\in\mathcal F\), with \(\sum_Q y_Q=W\). In every scenario \(S\), the available money is \(\sum_{Q\in\mathcal F:Q\cap S\ne\varnothing}y_Q\), and the aggregate per-capita cost to cover is \(\sum_t\mu_t\rho_t\alpha_w(S)=\bar\rho\alpha_w(S)\). A solution is such an allocation \(y\) satisfying the coverage inequality for every \(S\subseteq V\). This makes the clients’ population continuous; the scenario set and each individual’s diversified-investment choice remain as in the paper.
My lead anchor is Theorem 2, proved in this paper: an imputation is in the core of the stable-set game on a perfect graph if and only if it is an optimal solution to dual LP (6). Applied to this pool, it characterizes exactly the allocations satisfying the scenario conditions above: the optimal dual has asset demands \(\bar\rho w_v\), and its optimum value is \(W\). The paper’s Corollary 1, also proved here, says that this core is nonempty. The theorem is a characterization rather than a standalone runtime claim; polynomial computation follows from the paper’s use of polynomial-time perfect-graph optimization, which it cites to [GLS88]. Thus the mirror is expected to be tractable, with running time polynomial in the graph size \(n\), type support \(\tau\), and rational input bit length \(L\). The exponential family of scenarios need not be listed.
The scope is deliberately narrow: this mirrors Theorem 2’s perfect-graph core characterization and its nonemptiness consequence. It does not claim a result for arbitrary graphs or for every use of the core. Further questions include whether the result extends when types have different relative asset values or firm access, and what finite-account rounding guarantees hold for a given rational mass instance.
The weak point is that the paper’s decision-maker is one agent, while this mirror introduces a mass of beneficiaries represented by a common investment desk. If the beneficiaries do not pool capital, the model can split into separate copies and the population adds little. Even with pooling, the type masses collapse to the single scale \(\bar\rho\), so multiplicity does not create the computational gain: perfect-graph structure does. I think the pooled-fund interpretation is recognizable as a plausible high-multiplicity regime for the paper’s robust allocation problem, but this is a modest mirror rather than evidence that the paper’s central contribution is about population complexity.
The strongest objection is that the proposed client population never becomes a computational input. In the stated model, each type has costs \(\rho_t w_v\), so the aggregate scenario cost is \(\bar\rho\,\alpha_w(S)\). Dividing every allocation by \(\bar\rho\) recovers the paper’s original core instance exactly. The masses can be replaced by their single weighted average; the support size \(\tau\) carries no information relevant to the allocation problem. That makes the model a plausible scaled fund, but a weak continuization of a computational problem: it does not expose a population-dependent complexity landscape.
That objection has limits. I would not rely on the absence of a numbered runtime theorem: Theorem 2 characterizes the core through an LP, and the paper cites polynomial-time perfect-graph optimization. Nor does Corollary 1 provide an independent anchor; it follows from the same integrality argument. The proposed mirror is coherent, and the fact that its answer follows directly from the original model is not, by itself, a reason to reject the question.
A stronger mirror might give types different asset values, access, or budgets. Then the aggregate scenario requirement could be \(\sum_t\mu_t\alpha_{w^t}(S)\), rather than one scaled stable-set value. But that changes the mathematical object that Theorem 2 characterizes: its dual LP and TDI argument do not directly characterize this aggregate demand. It could still be a sensible research question, but the paper gives little basis for saying it is the same problem the authors set out to solve. The proposed homogeneous pool is closer to their game, yet its population data collapse to one scalar; the heterogeneous pool makes the population computationally relevant, yet requires a new justification and analysis.
So the case against is a concern about fit, not a decisive collision or impossibility: this paper’s robust allocation is built around one decision-maker and a set of nature’s scenarios, while the suggested clients share one pooled decision. Still, the homogeneous pool is plausible enough that I cannot honestly claim to have defeated every mirror. My negative case is weakest exactly at the authors-recognition gate: a pooled fund with many beneficiaries may be a scenario they would accept, even if its continuous population adds little to the computation.
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.