| paper | Welfare Approximation in Additively Separable Hedonic Games |
| authors | — |
| venue | AAMAS 2025 |
| filed under | coalition · hedonic |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 4.7
statement extracted from the paper’s text layer
Given a finite type set \(T\), rational masses \(\mu \in \mathbb{Q}_{\ge 0}^{\tau}\) summing to \(1\), and a symmetric rational valuation matrix \(W=(w_{ts})\) satisfying \(V_\mu:=\sum_{t,s}\mu_t\mu_s w_{ts}\ge 0\), output in randomized time polynomial in \(\tau\) and encoding length \(L\) a finite mass partition \(\Pi=(x^\ell)_{\ell=1}^{r}\) with \(x^\ell\in\mathbb{R}_{\ge 0}^{\tau}\) and \(\sum_{\ell}x^\ell_t\le\mu_t\), such that \(\operatorname{OPT}_\mu\le O(\log(\tau+1))\,\mathbb{E}[\operatorname{SW}_\mu(\Pi)]\), where \(\operatorname{SW}_\mu(\Pi)=\sum_{\ell}\sum_{t,s}w_{ts}x^\ell_t x^\ell_s\).
An atomless high-multiplicity ASHG society with finitely many complete valuation types, type masses \(\mu\), divisible mass assignments to coalitions, and quadratic within-coalition welfare \(\sum_{\ell,t,s}w_{ts}x^\ell_t x^\ell_s\), restricted to \(V_\mu\ge 0\).
The paper does not establish that Charikar–Wirth's \(O(\log n)\) guarantee survives the type-splittable box domain in time polynomial in \(\tau\), so the claimed algorithmic transfer remains open.
fatal: False
The mirror covers Theorem 4.7's welfare approximation result under \(V_\mu \ge 0\), while leaving Theorem 4.1 and the stochastic results in Theorems 5.8 and 5.11 unmirrored.
I think this paper has a credible continuous mirror, but I would anchor it on one result only: Theorem 4.7. The other results are less safe to continuize, especially the clique-based hardness gadget in Theorem 4.1.
My lead problem is:
\[ \textsc{Continuum-ASHG-Welfare}_{+}. \]
An instance consists of a finite set of types \(T=\{1,\ldots,\tau\}\), a rational mass vector \(\mu\in\mathbb{Q}_{\ge 0}^{\tau}\) with \(\sum_t\mu_t=1\), and a symmetric rational valuation matrix \(W=(w_{ts})\). A type is a complete valuation profile: every agent of type \(t\) values an agent of type \(s\) at \(w_{ts}\). The instance is restricted by
\[ V_\mu:=\sum_{t,s\in T}\mu_t\mu_s w_{ts}\ge 0. \]
A solution is a partition of the atomless population into coalitions. Equivalently, each positive-mass coalition \(\ell\) is represented by a vector \(x^\ell\in\mathbb{R}_{\ge0}^{\tau}\), where \(x^\ell_t\) is the mass of type \(t\) in that coalition, and
\[ \sum_\ell x^\ell_t\le \mu_t. \]
Any residual mass may be placed into singleton “dust” and contributes no welfare. The objective is normalized social welfare
\[ \operatorname{SW}_\mu(\Pi) = \sum_\ell\sum_{t,s\in T}w_{ts}x^\ell_t x^\ell_s. \]
The computational question is to output a coalition mass partition \(\Pi\) such that, in expectation,
\[ \operatorname{OPT}_\mu \le O(\log(\tau+1))\,\mathbb{E}[\operatorname{SW}_\mu(\Pi)], \]
in time polynomial in \(\tau\) and the encoding length \(L\) of \((\mu,W)\).
This is a genuine population continuization. Consider a large labour market or recurring project-allocation system with millions of workers but only a moderate number of complete role-and-preference profiles: for example, workers who have identical valuations for collaborating with every other role. The mass \(\mu_t\) is the fraction of workers of profile \(t\); the decision variable is how much of each profile is assigned to each team. No individual is fractionally assigned: only the population of a type is divisible because it is atomless.
The finite high-multiplicity bridge is direct. If there are \(N\mu_t\) named agents of type \(t\), a discrete coalition with \(n^\ell_t\) members corresponds to \(x^\ell_t=n^\ell_t/N\). After normalization by \(N^2\), the discrete welfare converges to the displayed quadratic objective, up to the usual \(O(1/N)\) correction for self-pairs. Conversely, rational coalition masses can be rounded to a sufficiently large finite population. Thus this is not merely fractional coalition formation; it is the high-multiplicity limit of the paper’s ASHG welfare problem.
The anchor is Theorem 4.7, proved in this paper: “There exists a randomized \(O(\log n)\)-approximation algorithm for maximizing social welfare in ASHGs with nonnegative total value.” The continuous version replaces \(n\) by \(\tau\), the number of distinct valuation types. That replacement is necessary: duplicating every type changes \(n\) but leaves the continuous instance unchanged, so \(n\) is not an intrinsic parameter of the mirror.
The proof architecture is unusually well suited to this translation. The paper’s identity
\[ \operatorname{CW}(\Pi)+\frac12V=\operatorname{SW}(\Pi) \]
is purely algebraic and remains valid for mass partitions. The argument that an unrestricted partition is within a factor of two of a two-coalition partition also extends by randomly cutting coalition mass. The resulting two-coalition problem is a weighted finite-dimensional quadratic optimization problem over the \(\tau\) type variables. The Charikar–Wirth randomized MaxQP machinery cited by the paper should therefore yield an \(O(\log \tau)\) approximation, with the continuous algorithm depending on \(\tau\) and \(L\), not on the enormous number \(N\) of repeated agents. I would classify this mirror as expected Class A.
The further questions are meaningful rather than cosmetic: can the \(O(\log \tau)\) factor be improved to a constant; can the optimum be computed exactly for fixed \(\tau\); when does allowing arbitrary coalitions improve on two coalitions; and what happens when \(V_\mu<0\)? A finite-population rounding theorem would also turn the result into an additive approximation for high-multiplicity discrete ASHGs.
The weakest point is that atomlessness permits a type to be split across many coalitions, including infinitesimal singleton coalitions. That can change the optimum substantially when same-type valuations are negative, so the continuous problem is not simply the discrete problem with large numbers substituted for small ones. For this anchor, however, the paper’s own two-coalition comparison controls precisely that extra freedom under \(V_\mu\ge0\). The weakness becomes more serious for Theorem 4.1: its reduction relies on one special agent \(z\), and in a continuum the mass of type \(z\) can be split among many coalitions, destroying the clique gadget. I therefore do not use Theorem 4.1 as a second anchor.
I am also not claiming a mirror for Theorems 5.8 or 5.11. Their randomness is attached independently to individual edges; collapsing agents into finitely many types would change that stochastic model unless one introduces a separate random graphon or type-pair model. Theorem 4.7 alone gives a strong, recognisable continuous population version of a named computational result in the paper.
The negative case is weaker here than the proponent’s case, because Theorem 4.7 is a genuine named computational result and ASHGs do admit a plausible high-multiplicity regime: repeated workers or machines with identical valuation profiles. There is no identity obstruction, and the normalized clone limit does converge to
\[ \operatorname{SW}_\mu(\Pi)=\sum_\ell\sum_{t,s}w_{ts}x_t^\ell x_s^\ell. \]
The strongest objection is instead that the proponent has not actually transferred the theorem’s algorithm.
The paper’s proof combines the two-coalition reduction with Charikar–Wirth’s algorithm for a binary quadratic program. After aggregating clones, a two-coalition partition is represented by \(z_t\in[-1,1]\), where \(z_t\) records the imbalance of type \(t\) between the two coalitions. Its objective is
\[ \operatorname{CW}_\mu(z) = \frac12\sum_{t,s}\mu_t\mu_s w_{ts}z_tz_s. \]
This is a box-constrained quadratic program, not the \(\{\pm1\}^{\tau}\) MaxQP to which the cited result directly applies. The distinction matters: if \(w_{tt}<0\), an optimum may split one type between the two coalitions, so restricting \(z_t\) to \(\pm1\) changes the high-multiplicity problem. Running the original algorithm on all \(N\) clones is polynomial in \(N\), but does not establish a polynomial algorithm in \(\tau\) and the encoding length. Thus “replace \(n\) by \(\tau\)” is the central unproved step, not a consequence of the paper.
One can repair this in either direction, but both repairs weaken the mirroring claim. If types are kept indivisible, Charikar–Wirth applies more directly, but the model is no longer the clone limit whenever identical agents optimally divide across coalitions. If type splitting is retained, one must solve or approximate a new box-quadratic or configuration problem. That may be worthwhile, but it is a new continuous coalition-formation problem rather than an established continuization of Theorem 4.7.
This still does not support a strong universal “no mirror” verdict. The finite clone correspondence is recognizable, the welfare does not collapse, and the paper’s two-coalition argument plausibly survives. I could therefore reject the proponent’s claimed \(O(\log(\tau+1))\) algorithm as unsupported, but I could not honestly defeat the underlying anchor: a meaningful continuous high-multiplicity question remains. The fairest negative classification is “credible mirror, unresolved algorithmic transfer,” not “no worthwhile mirror.”
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.