| paper | d4-conf-aaai-2016-0223 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 19 establishes \(\mathrm{PPO}\le 1\), hence equality, but says nothing about computing an outcome or the complexity of a computational task. The proposed continuous mass-partition problem is statable, yet it lacks a named computational result in the paper to anchor it.
fails bit a — no named computational result to mirror
The candidate mirror covers only the bipartite modified fractional hedonic setting of Theorem 19; it leaves the results for additively separable and fractional hedonic games, and the broader modified fractional bound, aside.
This paper contains no named computational-complexity result of the required kind: it proves no result that a problem is in P, NP-hard, FPT, or similar. Its numbered results are structural claims and bounds on the Price of Pareto Optimality. So it offers no qualifying complexity anchor for the continuization programme.
The closest positive lead is Theorem 19, proved in this paper: for a symmetric, unweighted bipartite graph with at least two vertices, the modified fractional hedonic game has \(\mathrm{PPO}\le 1\). Since a welfare-optimal partition is Pareto optimal, this means \(\mathrm{PPO}=1\). That is a welfare guarantee, not a computational-complexity result.
A plausible continuous question suggested by it would model repeated participants with finitely many compatibility types. Let \(H=(T,E)\) be a fixed finite, unweighted bipartite type graph, and let rational masses \(\mu_t>0\) sum to \(1\). A coalition is a measurable group of participants; if \(x_t\) is its mass of type \(t\), a type-\(t\) participant’s utility is
\[
u_t(x)=\frac{\sum_{s:\{t,s\}\in E}x_s}{\sum_s x_s}.
\]
A society is partitioned into such coalitions. Its welfare is the integral of participants’ utilities, and a partition is Pareto optimal if no measurable repartition weakly improves almost everyone’s utility while strictly improving a positive mass of participants. The resulting problem would be: given \(H\) and \(\mu\), compute the ratio of maximum welfare to the worst welfare among Pareto-optimal partitions, treating a zero denominator as \(+\infty\).
This is a concrete population-continuum analogue of the bipartite modified fractional hedonic game result. Theorem 19 makes \(\mathrm{PPO}=1\) a plausible conjecture for it, but does not establish that continuous claim or the complexity of computing it. The scenario is credible for large populations grouped into repeated compatibility cohorts, with the number of participants much larger than the number of types.
The weakest point is decisive for this task: the proposed question computes a welfare ratio, while the paper gives no complexity result to anchor a claim about how discrete hardness behaves under continuization. The mirror may be worth studying, but it cannot supply the requested positive complexity case from this paper’s named results.
The strongest case against using this paper for ChoCo is that it supplies no computational-complexity result to continuize. Theorem 19 is a welfare guarantee for modified fractional hedonic games on bipartite graphs; the other named results give welfare bounds or structural descriptions. None classifies the complexity of an algorithmic problem.
The proposed type-graph model is coherent: repeated compatibility cohorts can be represented by a finite bipartite graph \(H\) and rational masses \(\mu\), with coalitions described by their type masses. But asking for the Price of Pareto Optimality of those mass partitions is a new computational question. The paper’s theorem gives no algorithmic problem whose discrete complexity that question continues. To make the proposal a computational task, one would still need to specify how to represent or certify the worst Pareto-optimal mass partition, or define a decision version such as comparing the ratio with a rational threshold. Those choices may lead to worthwhile research, but they are additional modelling work, not an algorithmic consequence of this paper.
That defeats Theorem 19 as a *computational* anchor, including in the better repeated-cohort scenario. It does not establish that the resulting continuous coalition-formation problem is uninteresting. I cannot honestly defend the stronger claim that no scenario yields a worthwhile mirror: the compatibility-cohort model is plausible, and its mass-partition question could be worth studying on its own. The negative case is therefore strong against choosing this paper as evidence for ChoCo’s complexity programme, but weak as a universal claim that no useful continuous mirror exists.
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.