d4-conf-aaai-2016-0373

My lead, and only anchor, is Theorem 5, proved in this paper: the decision version of maximizing social welfare is NP-complete even when each agent approves at most one coalition. Given a graph \(G=(V,E)\) and target \(k\), the reduction creates an agent for every vertex and edge. A vertex agent \(v\) approves only \(A_v=\{v\}\cup\{e\in E:v\in e\}\); edge agents approve nothing. A partition with at least \(k\) satisfied agents exists exactly when \(G\) has an independent set of size at least \(k\).

I would mirror the underlying welfare problem with Type-List Welfare\(_\infty\). An instance has a finite set \(T\) of agent types, rational masses \(\mu_t\geq 0\) summing to \(1\), and, for each type \(t\), either no approved coalition profile or one profile \(a^t\in\mathbb{Z}_{\geq 0}^{T}\) with \(a^t_t\geq 1\). A type-\(t\) agent approves a coalition exactly when its vector of type counts is \(a^t\). An outcome divides the population into finite coalitions, each with an integral type-count vector \(q\); mass may be split among different coalition profiles. Let \(x_q\geq0\) be the number of coalitions of profile \(q\) per unit of population. Feasibility requires \(\sum_q q_t x_q=\mu_t\) for every \(t\). The task is to return a feasible allocation maximizing \(\sum_q x_q\sum_{t:a^t=q}q_t\), the mass of agents in approved coalitions.

This question keeps coalition formation and approval as the paper studies them; it makes the population continuous while leaving each coalition’s membership integral. For this one-profile-per-type restriction, it is an LP: it suffices to use the profiles \(a^t\) and singleton profiles \(e_t\). Any other coalition profile pleases nobody, and replacing it by singletons cannot reduce welfare. There are at most \(2\tau\) columns, so the mirror is solvable in polynomial time in the number of types and the input bit length. I expect Class A: the discrete hardness can disappear when agents of each type may be divided fractionally among coalition configurations.

The regime is a large organization or repeated project system with many participants in each role, where everyone in a role has the same ideal team composition. For example, principal-role agents may approve a team containing one principal and one representative of each required liaison role. The number of people can be \(K\tau\) for large \(K\), with only \(\tau\) distinct role profiles. In the paper’s reduction, make each vertex a principal type and each edge a liaison type. A principal type approves a profile containing one principal and one liaison for each incident edge; liaison types approve no team. With equal type masses, the variables \(x_v\) for principal teams satisfy \(x_u+x_v\leq\mu_e\) for every edge \(e=\{u,v\}\), and the welfare objective is to maximize \(\sum_v x_v\). The independent-set conflict remains visible in these capacity constraints, but the continuous problem optimizes their fractional version.

The weakest point is that Theorem 5’s approved coalitions name particular agents, whereas my mirror specifies approved type compositions. Its reduction has one agent per role, so it does not itself exhibit the high-multiplicity regime. The mirror is the natural type-based version of the same welfare question, not a claim that the theorem already solves or directly implies anything about that version. That change is defensible under the programme’s definition of a type as a complete preference profile, though an author or referee could reasonably ask whether composition-based approval captures the intended application.

This mirror covers Theorem 5’s welfare-maximization result, not the paper’s stability results. It also suggests asking how the picture changes with several approved profiles per type, what guarantees rounding a continuous optimum back to a finite replicated population, and whether stability concepts admit useful mass-based counterparts.