Decentralized Online Learning by Selfish Agents in Coalition Formation

Theorem 1 supplies the required named computational result. However, the proposed \(\phi_r^t\)-mirror replaces independently learning agents with a common type-level policy and replaces individual Nash regret with a type-level aggregate gap. Preserving the paper's information model requires a measure over private histories and learner states, which is a new mean-field model rather than a continuous restatement the authors would recognise as Theorem 1.

The objection that survived

The exchangeability caveat does not repair the fact that independent feedback and randomization create divergent histories, so \(\mu\) and \(\phi_r^t\) do not determine individual regret; per-capita normalization also changes the feedback-noise model.

What the mirror covers

The attempted mirror covers Theorem 1 and uses Lemmas 1–2 structurally, but it leaves the individual-history learning process and its estimation analysis without a faithful continuous counterpart.

Open questions for a prover

The case FOR (proponent)

My strongest case is a single-anchor mirror of Theorem 1, proved in this paper, for the D1S-FW algorithm. The theorem establishes that, with the stated step sizes, the algorithm achieves \(R_T\le O((n+n^3+n^4)\sqrt{T}+n^4\log(nT/\delta))\) with probability at least \(1-\delta\). Lemma 1 and Lemma 2 support the mirror structurally, but I would not treat them as separate anchors: Theorem 1 is the paper’s central named algorithmic result.

The natural continuous object is a high-multiplicity decentralized online hedonic game. Let \(R=\{1,\ldots,\tau\}\) be the set of agent types, with mass vector \(\mu\in\Delta_\tau\). A type records the complete information relevant to coalition utility: its role, skills, collaboration characteristics, pairwise feedback distributions, and hence its expected utility \(d_{r,s}\) from interacting with type \(s\). Symmetry requires \(d_{r,s}=d_{s,r}\). A finite population with \(N_r\) agents of type \(r\) is represented by \(\mu_r=N_r/N\).

Let \(A=\{1,\ldots,K\}\) be the candidate coalitions or project rooms. At round \(t\), \(\phi_r^t(a)\) is the fraction of type-\(r\) mass assigned to coalition \(a\); thus coalition \(a\) contains mass \(q_s^t(a)=\mu_s\phi_s^t(a)\) of type \(s\). The normalized expected utility of a type-\(r\) agent choosing \(a\) is

\[ u_r(a;\phi^t)=\sum_{s=1}^{\tau}\mu_s\phi_s^t(a)d_{r,s}. \]

The agent receives only a scalar bandit feedback \(Y_r^t\) from the coalition she joined, with \(\mathbb E[Y_r^t\mid a,\phi^t]=u_r(a;\phi^t)\), together with the local composition of that coalition. She does not see other coalitions’ utilities or other types’ histories. This is the population version of the paper’s additive utility and one-sample feedback model.

The relevant Nash gap is

\[ \Delta_r(\phi)=\max_{a\in A}u_r(a;\phi) -\sum_{a\in A}\phi_r(a)u_r(a;\phi). \]

A policy is \(\varepsilon\)-Nash stable when \(\Delta_r(\phi)\le\varepsilon\) for every type with positive mass. To preserve the paper’s worst-agent objective, define continuous Nash regret by

\[ R_H^\mu=\sum_{t=1}^{H}\max_{r:\mu_r>0}\Delta_r(\phi^t). \]

I would call this problem Continuous Decentralized Online Learning in Additively Separable Hedonic Games, or CDOL-ASHG. Its input is \(\tau\), \(K\), rational masses \(\mu\), a horizon \(H\), and access to the unknown bounded feedback distributions. Its output is a decentralized update rule producing \(\phi^1,\ldots,\phi^H\), using one local feedback sample per round, with the objective of minimizing worst-case \(R_H^\mu\). Equivalently, given \(\varepsilon\) and \(\delta\), it asks for an update rule that produces an \(\varepsilon\)-Nash-stable policy, or a certified low-regret sequence, with probability at least \(1-\delta\).

This is recognisably the authors’ problem. Coalitions remain discrete labels, utilities remain selfish and additively separable, feedback remains local and bandit, and the process remains online and decentralized. Only the society has been continuized: individual identities are replaced by masses of agents sharing the same complete utility type. Time is still discrete, and this is not continuity of the outcome space.

The high-multiplicity regime is plausible in the paper’s own project-team setting. Imagine a large open-source or freelance-development platform with \(N\) developers, repeatedly assigning themselves to \(K\) project rooms at successive milestones. Developers can share types based on role, seniority, technical domain, location, and collaboration style. Their pairwise team synergies need only depend on these stable categories. A realistic instance might have \(N\) in the tens or hundreds of thousands but \(\tau\) in the tens or low hundreds, with \(K\) perhaps between 20 and 200. The continuous instance describes the fraction of developers of each type entering each room. It is not claiming that every election or every small team has this structure; it identifies a genuine large-cohort regime.

The expected complexity classification is Class A, at least for approximate stability. The paper’s Lemma 2 writes an individual gradient coordinate as an inner product between a coalition-composition vector and an unknown preference vector. In the type model, this becomes

\[ u_r(a;\phi)=\left\langle (\mu_s\phi_s(a))_{s=1}^{\tau}, (d_{r,s})_{s=1}^{\tau} \right\rangle. \]

Thus the unknown vector has dimension \(\tau\), rather than the number \(n\) of named agents. The feasible policy space is the product of \(\tau\) simplices, with \(\tau K\) coordinates; each best-response step is simply a maximization over \(K\) coalitions. The potential from Lemma 1 becomes

\[ \Phi_\mu(\phi)= \frac12\sum_{a\in A}\sum_{r,s} \mu_r\mu_s d_{r,s}\phi_r(a)\phi_s(a), \]

whose coordinate gradient is proportional to the type’s utility vector. This suggests that the Frank-Wolfe and one-sample regression analysis should yield a regret bound of the form \(\widetilde O(\operatorname{poly}(\tau,K)\sqrt{H})\), and hence polynomial sample complexity in \(\tau\), \(K\), and \(1/\varepsilon\), independent of \(N\). That would be the continuous analogue of Theorem 1.

The discrete bridge is also clean. Downward, a rational mass vector \(\mu\) is a high-multiplicity discrete game with \(N_r=N\mu_r\) agents of type \(r\); fractional coalition masses can be rounded to integer assignments with vanishing additive error as \(N\) grows. Upward, setting \(\tau=N\), \(\mu_r=1/N\), and giving every agent a distinct type recovers the original individual model. The continuous version is therefore a relaxation of the population dimension, not a different social objective.

The mirror generates several worthwhile questions: can the theorem’s dependence on \(n\) be replaced formally by dependence on \(\tau\) and \(K\); how should finite-population rounding affect Nash gaps; can the result avoid dependence on the smallest positive mass \(\mu_r\); and what happens when same-type agents retain independent private histories rather than following a common type-level policy? Exact Nash stability at \(\varepsilon=0\) may remain difficult, while the paper’s finite-horizon approximate guarantee is the natural target.

The weakest point is the type-symmetric learning assumption. In the paper, agents of the same utility profile may still accumulate different private histories and therefore use different policies. A literal nonatomic limit also makes an individual’s effect on coalition composition vanish and may average away some of the original interaction noise. I would not claim that this mirror covers every independently learning finite population. Its claim is narrower: in a genuine cohort regime where agents are exchangeable in their utility and learning specification, the type-mass policy is the correct high-multiplicity object. That is enough to make Theorem 1’s computational question continuous without pretending that the entire paper, or every hedonic-game instance, has one universal mirror.

The case AGAINST (opponent, writing after the proponent)

The proponent has chosen the paper’s only serious anchor: Theorem 1. It is a named algorithmic result, so the paper passes the source gate. But the proposed mirror does not preserve the object to which that theorem applies.

The original learner is not characterized merely by agent \(i\)’s preference row \((d_{i,j})_j\). At round \(t\), her behaviour also depends on her private history \(h_i^t\), her previous policy \(\phi_i^t\), her individual observations, and her independent randomization. Two agents with identical utility parameters therefore cease to be interchangeable after the first noisy round. A faithful clone expansion of a type-mass instance would need to track a distribution such as

\[ \nu_t(r,h,\phi), \]

over types, private histories, and current policies. The proposed \(\phi_r^t\) is only an average policy. It does not determine any individual’s best response or regret.

This matters because Theorem 1 uses the worst individual:

\[ R_T=\sum_{t=1}^T\max_i \bigl(V_i^\star(\phi_{-i}^t)-V_i(\phi^t)\bigr). \]

Under independent local learning, the continuum analogue is an essential supremum over internal histories, not

\[ \sum_t\max_r \Delta_r(\phi^t). \]

An aggregate policy can be close to equilibrium while a positive fraction of a type—or merely a rare set of agents—has a badly estimated policy. Replacing the essential supremum by a maximum over utility types changes the guarantee. Replacing it by a mass-weighted average changes the stability objective still further.

There are only two ways to make the proponent’s finite-dimensional \(\phi_r\) exact. Either all agents of type \(r\) share their samples and update one common policy, which violates the paper’s decentralization and private-history assumptions, or one assumes that their feedback and randomization are identical, in which case the learning problem largely disappears. Treating each type as one representative learner is also a different game: it has one learner per type, not many selfish agents learning independently.

Adding histories to the type description does not repair the mirror. With real-valued bandit feedback, the history space is already uncountable; even with finite feedback it grows exponentially with the horizon. A finite type count \(\tau\) then no longer compresses the population, and the claimed polynomial dependence on \(\tau\) does not follow. The proponent’s upward construction with \(\tau=N\) distinct types merely atomizes the population; it is not a meaningful high-multiplicity bridge.

There is a second degeneration. The paper’s feedback is an additive sum of independently drawn pairwise utilities,

\[ v_i^t=\sum_{j\ne i}v_{i,j}^t. \]

For \(N\) cloned agents, the proponent’s normalized utility \(u_r\) implicitly divides this sum by population scale. Under the paper’s independence assumption, the normalized feedback variance then shrinks on the order of \(1/N\). The one-sample bandit difficulty that drives Theorem 1 vanishes in the continuum. If the sum is left unnormalized, utilities and regret grow with \(N\), so there is no finite limiting model. Introducing common coalition shocks would preserve nontrivial noise, but that is another substantive change to the paper’s information model.

The proposed potential

\[ \Phi_\mu(\phi) = \frac12\sum_{a,r,s} \mu_r\mu_s d_{r,s}\phi_r(a)\phi_s(a) \]

is mathematically legitimate for a new nonatomic, type-symmetric potential game. It does not establish that Theorem 1 has a continuous mirror. The corresponding Frank–Wolfe result would concern a redesigned model with common type policies, different information sharing, and usually a type-average or almost-everywhere objective.

That redesigned mean-field learning problem might be worthwhile in its own right. This is the honest weakness in the negative case: a large platform with exchangeable cohorts gives a plausible extension. But it is not a direct high-multiplicity continuization of the paper’s decentralized online-learning theorem. Under a strict mirror standard, Theorem 1 therefore fails on identity/history fidelity, and the only surviving version is a re-modeling rather than a continuous mirror of this paper.

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.