| paper | d4-conf-ijcai-2009-0228 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
A finite type-mass affinity model preserves the paper’s coalitions, pairwise utilities, core, and welfare-gap question, so a continuous extension is recognizable. But Theorems 1, 6, and 7 are structural or welfare-bound results, not computational claims, and the experiments use exhaustive searches on small instances. The required named computational anchor is absent.
fails bit a — no named computational result to mirror
The proposed mirror focuses on the stability-gap comparison in Theorem 7; it leaves Theorem 1’s welfare characterization, Theorem 6’s general-graph bound, the other stability results, and the experiments aside.
On the required anchor test, this paper has no qualifying named computational-complexity result. It has important numbered results, but none says a problem is in P, NP-hard, FPT, or similar, and it gives no algorithm with a complexity bound.
The closest substantive result is Theorem 7, proved in the paper: in a symmetric affinity game with a non-empty core, every core coalition structure has at least half the social welfare of an optimal coalition structure; the resulting stability-gap bound of \(2\) is tight. Theorem 1, also proved here, characterizes a welfare-maximizing structure as a minimal \(k\)-cut for some \(k\), chosen to maximize welfare across the possible values of \(k\). Both are strong structural results, but neither meets the requested anchor rule. Theorem 6, also proved here, gives the contrasting result that in general affinity games the best core member’s gap can be unbounded. The paper’s small exhaustive experiments do not supply a named complexity result either.
The best positive mirror I can offer is therefore a near-miss, not an anchor-compliant case: a continuous version of the symmetric stability-gap question. Consider an atomless population of mass \(1\) with a finite set \(T\) of complete affinity types, type masses \(\mu_t\in\mathbb{Q}_{\ge 0}\) summing to \(1\), and a symmetric rational affinity matrix \(a_{tt'}\). A plausible regime is a very large online community or volunteer network where many members share one of a modest number of role and interaction profiles, so \(n\gg\tau=|T|\). A type records the member’s affinity toward every type, including its own.
For a measurable coalition \(B\), let \(x_t(B)\) be the mass of type \(t\) in it. A type-\(t\) member’s utility is
\[
u(B,t)=\sum_{t'\in T}a_{tt'}x_{t'}(B),
\]
and a partition \(\Pi\) has welfare
\[
\mathrm{SW}(\Pi)=\sum_{B\in\Pi}\sum_{t,t'\in T}a_{tt'}x_t(B)x_{t'}(B).
\]
Call \(\Pi\) core-stable if no positive-mass coalition can make almost all its members weakly better off and a positive mass strictly better off. The question is: given \((T,\mu,a)\), find the minimum-welfare core partition and the maximum-welfare partition, or report that the core is empty; determine the resulting stability gap. The output should establish core stability and optimality, and should say whether the minimum is attained. The positive-mass strict-improvement condition is the natural continuum version of the paper’s blocking condition.
This is recognizable as their affinity game: agents still form coalitions, utilities still come from pairwise affinities, and the target still compares welfare with core stability. The change is the type-level affinity kernel and divisible mass, which suit a large repeated-type population. My best expectation is that the factor-two guarantee in Theorem 7 has a good chance of extending as a Class A-style structural result. But the paper provides no complexity basis for classifying the search problem of finding the worst-welfare core partition; I would leave that open rather than claim tractability or hardness transfer.
The weak point is that the continuous core and the existence or representation of optimal core partitions need real work; Theorem 7 does not settle them. More fundamentally, because the paper has no named complexity anchor, this is a credible direction for a mirror, but it cannot satisfy the requested anchor-based case.
The strongest objection is that the paper has no named computational result to anchor a ChoCo mirror. Theorem 7 proves a tight welfare ratio for core members, assuming the core is non-empty; Theorem 1 characterizes welfare-maximizing partitions via minimum \(k\)-cuts. Neither gives an algorithm, runtime, hardness result, or complexity classification. The experiments exhaustively search small instances. So the proposed Theorem 7 extension is a plausible structural question, but it does not continue a computational result of this paper.
The best population model is still coherent: use finitely many affinity types, rational type masses, and a symmetric type-to-type affinity matrix. It fits a stylized large community with repeated roles. But a type must capture an agent’s affinities to the other agents. Keeping \(\tau\) small therefore imposes a block-homogeneous network: every member of one type relates identically to every member of another. That is a substantial restriction on the paper’s arbitrary pairwise affinity graphs, whose central feature is often individualized ties.
Even granting that restriction, asking whether the factor-two bound extends is an analytic theorem question. Turning it into “find the minimum-welfare core partition” creates a new computational problem. The proposal does not yet give that problem a finite output representation: atomless populations allow arbitrary measurable partitions, and core blocking depends on how each type’s mass is distributed among incumbent coalitions, since those cohorts can have different current utilities. A finite encoding for optimal core partitions, and attainment of the minimum, would need to be established. The paper’s proof removes agents one at a time; it supplies no direct computational formulation for the atomless case.
Theorem 1 offers a stronger alternative mirror: optimize welfare over partitions of divisible type masses. That is a legitimate new problem, but the paper’s cut characterization still supplies no computational result to continue. The honest negative case is therefore strong against treating this paper as an anchored ChoCo candidate. The broader claim that no worthwhile mirror exists in any scenario is weaker: a role-homogeneous affinity population could be a sensible object, and its computational study might be worthwhile in its own right.
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.