Causes of Stability in Dynamic Coalition Formation

The proponent states a plausible continuous group-deviation problem, and the opponent's objections expose modeling choices rather than proving every such extension impossible. However, the supplied paper contains no numbered computational theorem: its only NP-hardness statement is an unnumbered sentence referring to the full version. Therefore bit (a) fails under the required objective test, making the grade red.

The objection that survived

The paper's unit, identity-specific resentment has no canonical scaling under divisible mass, and counting every arbitrarily small positive-mass deviation as one step makes shortest convergence depend on event granularity.

What the mirror covers

The proposed mirror covers only the Section 6 shortest-convergence hardness claim, especially CS dynamics with resentment; it leaves the numbered convergence, cycling, equivalence, simulation, and axiomatic results without computational mirrors.

Open questions for a prover

The case FOR (proponent)

The strongest honest positive case is for the paper’s “Shortest Converge Sequences” problem, using the claim in Section 6 that, in the full version, deciding whether an ASHG can reach stability within a prescribed number of steps is NP-hard for CS, IS, CNS, and NS dynamics, including resentful agents. I would lead with the CS/resentful case.

There is an important qualification: in the supplied AAAI paper this result is only reported in prose. It has no printed Theorem, Lemma, Proposition, or Corollary number. I therefore cannot honestly present it as a compliant numbered anchor without consulting the full version and quoting its exact statement. The numbered results in the supplied text—Theorems 3.1–3.4, 4.1, 4.4–4.6 and the related propositions—are convergence, cycling, or equivalence results, not complexity-class results.

Subject to that anchor defect, the mirror I would propose is Typed Mass Shortest-Convergence for Resentful ASHGs.

An instance contains finitely many current agent-state types \(S\). A type includes everything relevant to the dynamics: its rational population mass \(\mu_s\), current coalition label, and rational additive utility \(v_s(r)\) for an agent of every current type \(r\). Thus two agents are the same type only when they have the same current utility vector, coalition status, and history-relevant parameters. The total mass is one.

For a coalition \(P\), a type-\(s\) agent’s utility is

\[ U_s(P)=\sum_{r\in P}\mu_r v_s(r). \]

A CS mass deviation chooses rational amounts \(q_s\), with \(0\le q_s\le\mu_s\), not all zero. The selected mass \(q_s\) from each type forms a new coalition \(X\); those agents leave their previous coalitions. The deviation is admissible precisely when every selected type strictly prefers \(X\) to its former coalition:

\[ \sum_s q_s v_r(s) > U_r(P_r) \]

for every selected type \(r\). Each agent still belongs to one coalition; only the population multiplicities are divisible.

Under resent, every non-deviating member of a former coalition lowers her utility for each selected departing sub-type by one, exactly mirroring the paper’s group-deviation update. The affected cohorts are split into new state types when necessary. The question is:

Given such an initial typed society, an initial coalition structure, and an integer \(K\), does there exist a sequence of at most \(K\) positive-mass CS deviations, with the resent updates applied after every deviation, that ends in a state with no positive-mass CS deviation?

A solution is an explicit sequence of rational mass vectors \(q^{(1)},\ldots,q^{(\ell)}\), \(\ell\le K\), together with the induced coalition and utility states. The objective is the minimum number of deviations, not the amount of mass moved.

This is recognisably the authors’ problem: it retains ASHG utilities, group deviations, CS stability, resent, changing utilities, and shortest convergence. It does not replace coalitions by fractional memberships or replace stability by average welfare. The only continuization is that a large cohort can be divided among coalitions.

A plausible regime is a large organisation, university, or public-sector labour market with many repeated role-cohorts: hundreds of thousands of agents but perhaps dozens of initial types such as “junior software engineer in Berlin,” “senior designer,” or “research assistant in laboratory A.” Pairwise utility depends on role, qualifications, and location rather than on personal identity. Resentment records that a cohort leaving a team becomes less welcome there. Initially the number of types can be tiny compared with the population; after \(K\) deviations, the number of history states is bounded by a function of the initial types and \(K\), rather than by the number of agents.

I would expect this problem to be Class B: hardness transfers, although proving that is an open task for the mirror. The hardness in shortest convergence appears to lie in selecting coalitions and arranging a sequence of improving deviations, not merely in representing many separate voters. A finite ASHG can be embedded by giving each named agent a rational mass \(1/n\) and a distinct type. The real proof obligation is stronger: fractional splitting must not create shortcuts that destroy the reduction. One would need role-cohort gadgets with strict utility margins, or a discretization theorem showing that every successful mass execution can be rounded to a bounded-loss discrete execution.

This mirror also generates useful follow-up problems: the corresponding IS, CNS, and NS mass problems; appreciation instead of resent; approximation of the minimum number of deviations; and whether the continuous shortest execution always has a polynomial-bit rational witness. The paper’s Theorem 3.3, proved here, suggests a separate tractability direction: whether its resentful, individually rational NS convergence guarantee extends to typed mass dynamics. Theorem 4.5 similarly suggests a mass analogue for appreciative CNS dynamics. Those are promising Class-A questions, but they are not valid complexity anchors in the supplied paper.

My weakest point is therefore twofold. First, the only actual NP-hardness anchor is unnumbered in the provided version, so the paper fails the brief’s formal anchor requirement unless the full version supplies a numbered theorem. Second, the paper’s central dynamics are fundamentally individual and identity-sensitive. In a genuinely atomless population, one individual’s move has zero mass and cannot change other agents’ utilities; my mirror avoids that degeneracy by studying positive-mass CS deviations. That is natural for the paper’s group-deviation result, but it is not a faithful mirror of its individual NS dynamics. Thus I believe there is a serious, author-recognisable continuous problem here, probably with transferred hardness, but I would not claim a fully admissible positive verdict until the full-version theorem number and the mass-splitting reduction were supplied.

The case AGAINST (opponent, writing after the proponent)

The negative case is strongest on the record supplied: this paper does not actually provide an admissible named computational anchor. Its only complexity claim is the unnumbered sentence in Section 6 about “Shortest Converge Sequences,” explicitly deferred to the full version. The numbered results concern convergence, cycling, and equivalences, not computational complexity. Theorems 3.3 and 4.5 therefore cannot rescue the case: they are analytic convergence guarantees, not complexity results.

Assume, however, that the full version supplies a numbered NP-hardness theorem. The proposed mirror still has a deeper problem. The paper’s dynamics are driven by identity-specific history. When agent \(k\) leaves, every affected agent decreases her utility for that particular \(k\). That is not merely a utility attached to a role or preference type.

The proposed labour-market story therefore works only at time zero. Once some junior engineers leave one team and others do not, or once members of the same cohort have left different numbers of times, they no longer have the same complete type. Their current coalition, resentment level, and utilities toward particular departing subgroups differ. Keeping them in one type loses precisely the history that drives the paper’s convergence results. Refining them into history-cohorts restores correctness, but destroys the claimed small type space. After \(K\) deviations, cohorts can repeatedly split according to departure history and coalition membership; with \(K\) given in binary, the resulting state is not a fixed finite distribution over a moderate type set. It is a dynamically generated measure over histories and coalition compositions.

There is also no canonical atomless limit of the resentment update. In the finite game, one individual’s departure changes another agent’s utility by one, independently of the population size. In a normalized mass model, a departing mass \(q\) could naturally change aggregate utility by an amount proportional to \(q\). Then an individual departure has vanishing effect in the continuum, and the mechanism responsible for the paper’s convergence results disappears. Alternatively, one can make any positive-mass departure trigger a full unit decrement. Then an arbitrarily small mass has the same effect as a macroscopic group, and the result depends on whether an identical cohort moves in one step or is split into many tiny deviations. Both are defensible new dynamics; neither is a representation-independent high-multiplicity version of the paper’s dynamics.

The same issue appears in the proposed shortest-path objective. Since a deviation costs one step regardless of how much mass moves, a continuum execution can use arbitrarily small positive subgroups. A “shortest” execution is then governed by event granularity rather than population structure. Preventing this would require a minimum-mass constraint or a mass-dependent deviation cost. That could be a sensible new problem, but it would no longer be the paper’s shortest-convergence problem.

The proponent’s discrete embedding does not establish a high-multiplicity mirror either. Assigning each named agent mass \(1/n\) and a distinct type is just a fractional encoding of the original instance; it has no multiplicity compression. Conversely, forcing repeated role-types introduces fractional splitting and history effects that can create executions unavailable in the discrete reduction. Preventing those shortcuts would require new gadgets or a new restricted model, not a routine continuization.

A measure-valued model over complete histories might be mathematically interesting, but it is no longer the programme’s clean continuous society \(\mu\) over a fixed finite type space. It becomes a reachability problem over an evolving, potentially unbounded state distribution. That may belong to dynamic mean-field control or hybrid systems rather than to the proposed high-multiplicity computational mirror.

So I would reject the anchor as currently presented, both because the supplied paper lacks a numbered computational result and because the proposed mass version cannot preserve the paper’s essential identity-and-history mechanism while retaining a finite, stable type space. The universal claim is not airtight: with a carefully specified fractional resentment law and a history-distribution state, one could invent a worthwhile new model. But that concession also identifies the weakness of the positive case: the worthwhile object would be a new dynamic continuum system, not a faithful continuization of this paper’s computational result.

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.