Optimal Partitions in Additively Separable Hedonic Games

The strongest positive case is a qualified one: the paper supports a genuine Class A mirror for its egalitarian-hardness result, and a complementary Class B mirror for its utilitarian-hardness result. The first is my lead.

My lead anchor is Theorem 2 in Section 3: “Computing a maximum egalitarian partition is NP-hard in the strong sense.” The paper proves this result. Its reduction is from the cited problem \({\sc MaxMinMachineCompletionTime}\): there are machine players and job players; a machine values job \(j\) by its processing time \(p_j\), machine–machine valuations are strongly negative, and job–machine valuations are a large positive constant. In an optimal partition, machines occupy separate coalitions and jobs are assigned to machines, so a machine’s utility is exactly the total processing time of its assigned jobs. Maximizing the minimum player utility therefore encodes maximizing the minimum machine load.

The continuous mirror I would hand to a prover is Continuous Maximum-Egalitarian Machine–Job ASHG. An instance has one machine type \(M\) of mass \(\mu_M>0\), job types \(J_1,\ldots,J_r\) with masses \(\mu_1,\ldots,\mu_r\), rational processing values \(p_1,\ldots,p_r>0\), and a large rational job-side utility \(B\). Types are complete: all machines have the same valuation row, and two jobs have the same type exactly when they have the same processing value and the same valuation behaviour.

A feasible partition assigns every unit of job mass to a machine coalition. A coalition pattern is described by \(q=(q_1,\ldots,q_r)\), where \(q_j\) is the amount of job type \(J_j\) attached per unit of machine mass in that coalition. If \(\lambda\) is the distribution of machine mass over coalition patterns, feasibility requires \(\mathbb{E}_{\lambda}[q_j]=\mu_j/\mu_M\) for every \(j\). Each unit of machine mass in pattern \(q\) receives utility \(\ell(q)=\sum_j p_jq_j\); each matched job unit receives utility \(B\). The question is to output a feasible \(\lambda\) maximizing the egalitarian value \(\min\{B,\operatorname*{ess\,inf}_{q\sim\lambda}\ell(q)\}\).

This is a genuine population continuization. Individual job units still belong to one coalition; only a large cohort of identical jobs can be distributed across many machine coalitions. The fractional \(q_j\) is a type-level average, not a fractional bundle received by an individual. The per-capita utility normalization is the necessary co-modification: without it, raw integrals over atomless mass would make the finite utilities collapse to zero.

For this regime the answer is exact and elementary. Every feasible solution has egalitarian machine utility at most the average workload \(\sum_jp_j\mu_j/\mu_M\), while the constant pattern \(q_j=\mu_j/\mu_M\) for every machine attains it. Hence the optimum is \(\sum_jp_j\mu_j/\mu_M\), computable in polynomial time in \(r\) and the encoding length. The discrete scheduling hardness has disappeared because the source of difficulty was the indivisibility of individually named jobs. A large production system with many interchangeable jobs in finitely many processing classes and many interchangeable machines is a credible high-multiplicity regime: the number of agents can be enormous while \(r+1\) remains small.

This is not merely replacing an integer objective by a fractional objective. It preserves the paper’s machine/job roles, additive coalition utilities, egalitarian welfare, and the fact that each population unit receives one integral coalition assignment. It asks exactly what happens to the scheduling obstruction when repeated job cohorts become mass. I would expect this mirror to be Class A. Further questions are whether one can obtain finite-population rounding guarantees, how the answer changes under machine capacities or forbidden machine–job pairs, and whether a fixed number of processing classes yields denominator-independent algorithms for the original discrete problem.

My secondary anchor is Theorem 1 in Section 3: “Computing a maximum utilitarian partition is NP-hard in the strong sense even with symmetric and strict preferences.” This theorem is proved in the paper, using a reduction from MaxCut; the surrounding discussion also connects the problem to correlation clustering. The underlying objective is \(u_{ut}(\pi)=\sum_i u_\pi(i)\), where each player’s utility is the sum of their pairwise valuations inside their coalition. The theorem says that even when \(v_i(j)=v_j(i)\) and every pairwise valuation is nonzero, finding a welfare-maximizing partition is strongly NP-hard.

The corresponding problem is Continuous Maximum-Utilitarian Typed Partition. The input is a finite type set \(T\), rational mass vector \(\mu\in\mathbb{Q}_{\ge0}^{T}\), and rational valuation kernel \(V:T\times T\to\mathbb{Q}\). A type includes the complete valuation information relevant to the game. A solution is a finite rational configuration decomposition \((\lambda_k,q^k)_k\), with \(\lambda_k\ge0\), \(q^k\in\mathbb{Q}_{\ge0}^{T}\), and \(\sum_k\lambda_kq^k=\mu\). Here \(\lambda_kq_t^k\) is the mass of type \(t\) assigned to coalitions of composition \(q^k\); no individual mass unit is assigned to two coalitions. A type-\(t\) unit in configuration \(q^k\) gets \(u_t(q^k)=\sum_{t'}V(t,t')q_{t'}^k\). The task is to output a decomposition maximizing \(\sum_k\lambda_k\sum_tq_t^ku_t(q^k)\). The symmetric-strict version requires \(V(t,t')=V(t',t)\) and nonzero values for distinct types.

I would expect this second mirror to be Class B. The paper’s MaxCut gadget can be populated by large cohorts of each vertex type and two large anchor types. The large positive anchor valuations and strongly negative anchor–anchor valuation force the mass into two principal coalition blocks. Although a vertex type may split its mass between the two blocks, the resulting objective is affine in each split coordinate, so an optimum should have an unsplit representative and recover a discrete cut. Establishing that saturation lemma would be the main proof obligation, but the combinatorics live in the interaction graph, not in the number of named voters. Thus this is precisely the kind of hardness that should survive continuization.

The utilitarian mirror is plausible in applications such as repeated team formation: a large organization has many agents drawn from a finite set of symmetric affinity profiles, and coalitions are teams. It also gives the programme a useful boundary result. The egalitarian scheduling obstruction dissolves under mass, while the MaxCut obstruction remains. That is a more informative mirror than claiming that all ASHG hardness either disappears or survives.

The weakest point is the lead construction’s restriction to the machine–job regime and its explicit per-capita normalization. A referee could say that it mirrors the hard family used in Theorem 2 rather than the unrestricted maximum-egalitarian ASHG problem. I would concede that. The claim is not that every continuous ASHG partition problem is easy; it is that the paper’s own central NP-hardness mechanism has a natural high-multiplicity population interpretation in which it becomes an exact balancing problem. The unrestricted typed coalition model remains a separate question, likely requiring configuration-LP or nonconvex optimization tools. This case therefore covers Theorems 2 and 1, with Theorem 2 as the lead, and deliberately does not stretch to the paper’s Pareto, envy-freeness, or Nash-stability results.