| paper | Online Learning of Partitions in Additively Separable Hedonic Games |
| authors | Saar Cohen, Noa Agmon |
| venue | IJCAI 2024 |
| filed under | coalition · hedonic |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 1
statement extracted from the paper’s text layer
Given an atomless population \(\Omega\) partitioned into \(\tau\) homogeneous types \(A_a\) with masses \(\mu_a\), a horizon \(T\), and each round an active measurable subpopulation \(S^t\) of mass \(M_t\), the learner observes \(S^t\), chooses a measurable partition \(P^t_1,\ldots,P^t_k\) of \(S^t\) with each coalition having mass \(M_t/k\), and then receives a type-level disutility matrix \(D^t=(d^t_{ab})\). With \(x^t_{a\ell}=\lambda(S^t\cap P^t_\ell\cap A_a)\), \(y^t_{a\ell}(Q)=\lambda(S^t\cap Q_\ell\cap A_a)\) for one fixed whole-population \(k\)-partition \(Q\), and \(L_t(z,D^t)=\sum_{\ell,a,b}d^t_{ab}z_{a\ell}z_{b\ell}\), determine whether a learner running in time polynomial in the encoded input length can guarantee \(\sum_t L_t(x^t,D^t)\le c\min_Q\sum_t L_t(y^t(Q),D^t)+\operatorname{poly}(\tau,k,L)T^\delta\) for fixed \(c>0\) and some \(\delta<1\).
A high-multiplicity atomless population with finite behavioral or cohort types, mass-valued coalition decisions \(x^t\), type-level disutilities \(D^t\), and a fixed measurable comparator partition \(Q\); individuals remain integrally assigned, while type mass may be split across coalitions.
Theorem 1's reduction may rely on arbitrary named-agent edges and active-set/comparator intersections that a type-mass matrix does not retain; without an explicit cohort or arrival encoding, the proposed model could become the paper's fractional relaxation in disguise.
fatal: False
The mirror covers the population analogue of Theorem 1's integral online partition and no-static-regret problem. It does not directly transfer Lemma 1's exact reduction, the fractional and rounding results in Theorems 2–4, or their dynamic-regret guarantees.
The strongest honest mirror is a continuous, type-homogeneous version of the paper’s integral online partition problem, rather than its explicitly fractional \(k\)-FOP relaxation.
My lead anchor is Theorem 1, proved in this paper. It states that, when \(k\) is not constant, no polynomial-time learner for \((\alpha,k)\)-OP\(=\) achieves the stated approximation to no-static regret under ETH or Gap-ETH, even for simple games with disutilities in \(\{0,-1\}\). The proof uses this paper’s Lemma 1 together with Theorem 11 of Bilò et al. [2022], with an alternative reduction supplied in Appendix A. The paper also notes that the result remains valid when disutilities are fixed over time.
Here is the continuous problem I would mirror.
Call it Continuous Type-Homogeneous Online Partitioning, or CT-\(k\)-OP\(_\infty\). The population is an atomless probability space \(\Omega\), divided into finitely many types \(A=\{1,\ldots,\tau\}\). Type \(a\) has mass \(\mu_a\), where \(\mu_a\ge0\) and \(\sum_a\mu_a=1\). A type is a complete behavioural description: agents of type \(a\) have the same role, working style, and disutility toward every other type. Temporal preference changes are allowed, provided all copies of a type experience the same type-level change.
There are \(k\) equal-capacity coalitions. At round \(t\), before seeing the current disutilities, the learner partitions the entire population into measurable coalitions \(P^t_1,\ldots,P^t_k\), each of mass \(1/k\). Let \(x^t_{a\ell}\) be the mass of type \(a\) assigned to coalition \(\ell\). Thus \(x^t\) satisfies \(\sum_\ell x^t_{a\ell}=\mu_a\) and \(\sum_a x^t_{a\ell}=1/k\).
The matrix \(x^t\) is only an aggregate representation. Each individual \(\omega\in\Omega\) belongs to exactly one coalition; a type may be split across coalitions because it contains an atomless mass of distinct agents. This is therefore population continuization, not the paper’s fractional relaxation in which one named agent can belong fractionally to several coalitions.
After the learner acts, the adversary reveals a type-level disutility matrix \(D^t=(d^t_{ab})\). The normalized social cost is \(L_t(x^t,D^t)=\sum_{\ell=1}^k\sum_{a,b}d^t_{ab}x^t_{a\ell}x^t_{b\ell}\), using the paper’s ordered-pair convention. A static comparator is one fixed measurable partition \(y\) of the whole population, represented by the same type-mass constraints. The continuous no-\(c\)-regret question is whether a polynomial-time learner can guarantee \(\sum_{t=1}^T L_t(x^t,D^t)\le c\min_y\sum_{t=1}^T L_t(y,D^t)+\operatorname{poly}(\tau,k,L)T^\delta\), for every adaptively chosen sequence of revealed matrices, with \(\delta<1\). The case \(c=1\) is continuous no-regret.
This is a plausible high-multiplicity regime for the authors’ problem. Imagine a large organization repeatedly forming project teams from \(10^5\) or \(10^6\) employees, with perhaps \(20\)–\(100\) stable role or working-style types. Every employee still receives one actual team assignment, and team dissatisfaction is still additively separable over pairwise interactions. What changes is that the relevant object is the mass of analysts, designers, managers, and so on, rather than the identities of millions of interchangeable employees. A new project context can reveal the current type-to-type disutilities only after teams have been formed, exactly preserving the paper’s online-information structure.
The continuous formulation is also a genuine high-multiplicity limit. If every \(\mu_a\) is rational, multiplying by \(N\) gives a finite population with \(N\mu_a\) copies of type \(a\). Conversely, any finite type-homogeneous population maps to such a mass vector. Rational aggregate assignments can be implemented by actual finite partitions after sufficiently large replication, with rounding error that can be studied explicitly. The continuous problem therefore has a natural downward and upward dictionary rather than being merely an analogy.
My expectation is that the general CT-\(k\)-OP\(_\infty\) problem is probably Class B, with a tractable boundary in genuinely fixed-type regimes. Continuization removes dependence on the enormous population size, but arbitrary type-interaction matrices still contain a combinatorial interaction graph, and \(k\) may remain part of the input. If a reduction from the paper’s Densest-\(\beta\)-Subgraph route survives type splitting, the hardness lives in the number of types and coalition structure, not in population multiplicity; hardness should then transfer. When \(\tau\) and the interaction structure are fixed or strongly restricted, the problem becomes a finite-dimensional mass-allocation problem and configuration LPs, convexification, or fixed-dimensional optimization may plausibly yield Class A algorithms.
The key technical questions are whether the Theorem 1 reduction survives when many agents share each type, whether splitting a type across coalitions destroys the required gap, and whether the static comparator can be solved through a pricing problem over coalition type-compositions. The arrival version, in which only type-masses are active at each round, would provide the corresponding continuous analogue of the paper’s adversarial-subset model. Theorems 3 and 4 also suggest continuous dynamic-regret questions involving type-mass path length and an interaction term, though I would not count them as anchors here because their central object is the paper’s explicit fractional relaxation.
The weakest point is that arbitrary named-agent preferences are doing real work in the paper’s hardness proof. If the interesting hardness is entirely an arbitrary graph on individuals, then compressing that graph into a small number of homogeneous types may make the problem substantially easier. Also, a continuous type mass can be split, so a one-copy-per-vertex reduction does not automatically survive. I would not claim that Theorem 1’s exact ETH exponent transfers without a new reduction.
That weakness does not invalidate the mirror. It identifies precisely the question continuization is meant to answer: does the paper’s online partition problem remain hard when the society is a high-multiplicity distribution over behavioural types? If it becomes tractable, that is a meaningful Class A result; if the type-interaction graph preserves hardness, it is Class B. Either outcome is a legitimate computational continuation of the authors’ problem.
The proponent’s mirror does not preserve Theorem 1’s computational object. The theorem concerns indivisible partitions of named agents: an adversary selects a subset \(N^t\), the learner partitions those agents into exactly \(k\) coalitions of exactly \(\alpha\) agents, and the fixed comparator is a named-agent partition whose intersections with \(N^t\) are scored. The hardness comes from arbitrary pairwise relations between those identities.
CT-\(k\)-OP\(_\infty\) removes all three features. It partitions the whole population every round, replaces the individual capacity \(\alpha\) by a fixed mass capacity \(1/k\), and represents both decisions and comparators only by type-mass matrices. The proposed objective
\[ L_t(x,D^t)=\sum_{\ell,a,b}d^t_{ab}x^t_{a\ell}x^t_{b\ell} \]
depends solely on those masses. It therefore forgets the named partition that Theorem 1 compares against.
The claim that this is not the paper’s fractional relaxation because every atom is assigned integrally does not repair the problem. In an atomless population, every feasible mass matrix \(x\) can be implemented by assigning different indistinguishable agents of a type to different coalitions. Since the cost is type-anonymous, no observable quantity distinguishes that implementation from fractional assignment. The action space has become a transportation polytope: the indivisibility responsible for the paper’s partition problem has disappeared. This is a population interpretation of a fractional or mean-field relaxation, not a mirror of the integral theorem.
The alternatives are no better. If types are forbidden from splitting, the model becomes a weighted finite partition problem; the atomless population is only notation. If one type is introduced for every original agent, arbitrary graphs can be retained, but then the type space carries all the original identities and the proposed continuum performs no meaningful population compression. With many clones of each such type, the limit is instead a fractional balanced graph-partition problem. That may be an interesting new problem, but it is not a faithful continuation of the named no-static-regret result.
The arrival version exposes a separate obstruction. A type-mass vector does not determine the intersection of an active subset with a fixed comparator partition. The same active mass of type \(a\) can come entirely from coalition \(1\), entirely from coalition \(2\), or from both, producing different comparator costs. Preserving this information requires tracking type-by-coalition history, which restores the hidden individual structure; assuming uniform random arrivals changes the adversarial model into a stochastic one.
Thus the proponent has identified a plausible new online quadratic allocation problem, not a continuous mirror of Theorem 1. The paper’s Theorems 2–4 do not rescue the proposal: they already study fractional assignments and their rounding, so the atomless reinterpretation adds modelling language rather than a distinct population-computational question. The negative case is not an impossibility proof—one could reasonably study the proposed blow-up or block-type model—but its status should be “substantive re-modelling,” not a worthwhile direct 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.