| paper | d4-conf-aaai-2021-0544 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Polynomial-time solvable for \(m=\tau=2\); a stable arrangement always exists and can be computed using at most one pool. All possible limiting local masses and type-average errors are characterized above. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 0.9
Given rational masses \(\mu_s,\mu_\ell\) summing to one, sample counts \(n_s<n_\ell\), parameters \(\mu_e,\sigma^2\), and a population scale \(H\), compute a stable measurable partition of the two type masses into federation pools and local learners. For a type \(t\) in a pool whose other-client mass fractions are \(q_s,q_\ell\), use \(A(q)=n_s q_s+n_\ell q_\ell\), \(B(q)=n_s^2q_s+n_\ell^2q_\ell\), and expected error \(E_{t,H}(q)=\frac{\mu_e}{n_t+HA(q)}+\sigma^2\frac{HB(q)+H^2A(q)^2}{(n_t+HA(q))^2}\); stability rules out any positive-mass move that strictly improves the movers’ error and leaves destination incumbents weakly better off. Determine the high-multiplicity behavior as \(H\to\infty\).
Two client types, distinguished by sample counts, carry masses \(\mu_s,\mu_\ell\). A partition assigns those masses to federation pools or local learning; pool utilities use the paper’s expected-error formula with aggregate sample supplies scaled by \(H\). Stability is defined by admissible positive-mass moves. As \(H\to\infty\), every positive-mass pool has limiting error \(\sigma^2\), while local learning for type \(t\) has error \(\mu_e/n_t\).
The proposed utility omits the population scale \(H\); with it included, positive-pool error converges to \(\sigma^2\) and infinitesimal individual moves have no pool effect, changing the finite theorem’s stability incentives.
fatal: False
The mirror covers Theorem 0.9’s efficient construction for uniform federation with two sample-count classes; it leaves the expected-error formulas and the coarse- and fine-grained federation results aside.
The best positive case is the paper’s uniform-federation result for two sample-size classes. It studies almost exactly the right computational object: assigning agents to federating coalitions so that no agent has a stability-improving move.
The anchor is Theorem 0.9, proved constructively by Donahue and Kleinberg. For uniform federation with small and large players, where \(n_s<n_\ell\) and \(n_\ell>\mu_e/\sigma^2\), it says that an individually stable arrangement exists and gives a computationally efficient algorithm to find one. The AAAI version defers the proof details to the authors’ full version; the result is theirs, not a cited theorem. [The published paper](https://ojs.aaai.org/index.php/AAAI/article/download/16669/16476)
Here is a concrete mirror. Imagine a large population of clients contributing local estimates to federated mean estimation. There are two types: clients with \(n_s\) samples and clients with \(n_\ell\) samples. They share the paper’s assumptions about expected sampling noise \(\mu_e\) and variation in true means \(\sigma^2\); they know their sample counts but not the other clients’ realized means. A plausible regime is millions of devices in two standardized data-volume tiers, so the population is large while the type support is two. The type records the information relevant to expected utility under the paper’s model.
Call the problem Continuum Uniform-Federation Individual Stability. Its input is a population scale \(H\), rational type masses \(\mu_s,\mu_\ell\) summing to one, \(n_s<n_\ell\), and rational \(\mu_e,\sigma^2\), with \(n_\ell>\mu_e/\sigma^2\). A solution partitions the type mass into federating pools or local learners. For a type-\(t\) client in a pool with other-agent masses \(q=(q_s,q_\ell)\), let
\[
A(q)=n_s q_s+n_\ell q_\ell,\qquad B(q)=n_s^2q_s+n_\ell^2q_\ell.
\]
The pool’s uniform weighted model gives that client expected error
\[
E_t(q)=\frac{\mu_e}{n_t+A(q)}
+\sigma^2\frac{B(q)+A(q)^2}{(n_t+A(q))^2}.
\]
At \(q=0\), this is the local-learning error \(\mu_e/n_t\). The question is to output a measurable mass partition with no stability-improving type-mass move: no positive mass of one type can move to another pool or to local learning, strictly lower its expected error, and be admitted while every destination incumbent weakly benefits. This keeps the paper’s model, utility and individual-stability idea, while allowing coalition composition to be fractional.
I expect this two-type problem to be tractable. The paper’s construction organizes the arrangement around the number of large players who can join a pool containing small players. In the mirror, that becomes a threshold in one continuous mass variable; the displayed utilities are rational functions of the pool masses. That is a credible route to an exact low-dimensional algorithm, though the paper’s theorem does not establish this continuous result or give a parameterized running-time bound. Natural next questions are whether the result extends to support size \(\tau>2\), whether the continuous solution can be rounded to a discrete individually stable arrangement, and whether core stability admits a similarly useful characterization.
The scope here is deliberately narrow: it mirrors Theorem 0.9’s uniform-federation stability problem, not the paper’s coarse- or fine-grained federation results. The paper supplies no named hardness result, so this case is about whether an algorithmic result survives continuization, not whether discrete hardness dissolves.
The weak point is the stability notion. In the finite game, one agent’s move changes a pool’s composition and can cause its incumbents to reject that agent. In a continuum, an infinitesimal mover has no effect on the pool unless stability is defined through positive mass transfers. The mass-move definition above is a plausible continuous coalition question, but the authors might regard it as a changed stability concept rather than a direct mirror of individual stability. The connection remains strong at the level of the model and computational goal; that change in move semantics is the part a referee would need to accept.
Theorem 0.9 is a genuine computational anchor, and a population of standardized clients in two data-volume tiers is plausible. The strongest objection is about what happens to the game’s incentives in the high-multiplicity limit, not whether the original result qualifies.
Let \(H\) be the number of clients, and let \(q_s,q_\ell\) be the fractions of other clients in a pool. Write \(A=n_s q_s+n_\ell q_\ell\) and \(B=n_s^2q_s+n_\ell^2q_\ell\). With the paper’s independent sampling and parameter draws, a type-\(t\) client’s expected error in that pool scales as
\[
E_{t,H}(q)=\frac{\mu_e}{n_t+HA}
+\sigma^2\frac{HB+H^2A^2}{(n_t+HA)^2}.
\]
For any pool of positive mass, \(E_{t,H}(q)\to\sigma^2\) as \(H\to\infty\), regardless of its composition. The sampling-noise benefit vanishes, as does the composition-dependent part of the heterogeneity term. Local learning still costs \(\mu_e/n_t\). So the limiting choice is essentially just local learning versus joining any nonempty pool: clients below the paper’s threshold prefer pooling, and those above it prefer local learning. The threshold remains, but the nontrivial interaction between small and large players that motivates the finite theorem disappears. The same collapse applies with more sample-count types under the paper’s common i.i.d. parameter law.
That scaling exposes a problem in the proposed utility \(E_t(q)\): with masses summing to one, it treats the pool as though it had order-one clients. It omits the population scale \(H\). Keeping that formula amounts to a fractional finite-cohort model, not the high-multiplicity limit of clients with fixed per-client sample counts. And if stability instead uses unilateral moves by atomless individuals, a mover cannot affect a pool’s aggregate; requiring positive-mass moves, as the proponent does, gives a reasonable but different move semantics.
One can preserve composition effects by giving observable client types different parameter distributions, or preserve aggregate sampling noise by changing how information scales with population. Either could motivate a new federation model. But the first departs from the paper’s shared i.i.d. parameter law and information assumptions; the second requires a different sampling regime, such as fixed total information split across an increasing number of clients. Those are plausible extensions, especially given the paper’s motivation, but they do not rescue the theorem’s direct high-multiplicity mirror.
So the best negative case is that the faithful limit loses the finite-sample externality on which the result’s coalition structure depends, while the proponent’s nondegenerate formula does not take that limit. This is a substantial objection to this anchor as a ChoCo project. It does not establish the universal claim: a type-heterogeneous extension could still be worthwhile, and the paper’s theorem is a real computational result. The honest negative case is therefore strong against the proposed direct mirror, but weak as a claim that no recognizable continuous variant is worth pursuing.
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.