| paper | Coalition Formation with Bounded Coalition Size |
| authors | — |
| venue | AAMAS 2024 |
| 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
statement extracted from the paper’s text layer
Given an integer \(k\ge2\), rational type masses \(\mu\in\mathbb{Q}_{\ge0}^{\tau}\) with \(\sum_a\mu_a=1\), and a rational symmetric interaction matrix \(w\in\mathbb{Q}_{\ge0}^{\tau\times\tau}\), choose nonnegative rational masses \(y_r\) for integral coalition patterns \(r\in\mathbb{Z}_{\ge0}^{\tau}\) satisfying \(1\le\lVert r\rVert_1\le k\) and \(\sum_r r_a y_r=\mu_a\) for every type \(a\), maximizing \(\sum_r F_w(r)y_r\), where \(F_w(r)=\sum_a r_a(r_a-1)w_{aa}+2\sum_{a<b}r_ar_bw_{ab}\). Compute a feasible allocation with welfare at least \(1/k\) of optimum for odd \(k\), or at least \(1/(k-1)\) for even \(k\).
A society is a distribution \(\mu\) over \(\tau\) exchangeable complete agent types with symmetric values \(w_{ab}\). Decision variables are masses \(y_r\) of ordinary integral coalitions of size at most \(k\), subject to type-balance constraints, with normalized utilitarian welfare \(\sum_r F_w(r)y_r\). The approximation is obtained by a capacitated fractional matching over type pairs plus singleton mass.
It covers Theorem 4 and, as a specialization, the unweighted MaxUtil approximation in Theorem 3 on block-constant high-multiplicity instances. It leaves the core, Strict Core, Contractual Strict Core, and their existence or hardness results untouched, as well as arbitrary non-repeated friendship graphs.
The strongest honest case is a single anchor: the paper’s Theorem 4. It is proved in this paper and states that Algorithm 1 gives a \(1/k\)-approximation for weighted MaxUtil when \(k\) is odd, and a \(1/(k-1)\)-approximation when \(k\) is even. Theorem 3 is the unweighted special case, so I would not count it as a separate anchor.
My mirror is a high-multiplicity version of weighted MaxUtil, which I would call \(\textsc{Typed-MaxUtil}_{\infty}\). Consider a large recurring team-formation market: a corporation assigns thousands of employees to project teams, or a large transport service assigns many travelers to vehicles. There are only \(\tau\) complete agent types, determined by role, location, shift, skill profile, and every interaction-relevant preference. Agents of type \(a\) form mass \(\mu_a\), with \(\sum_a\mu_a=1\). Two agents of types \(a\) and \(b\) contribute the same symmetric friendship value \(w_{ab}=w_{ba}\ge 0\), including a within-type value \(w_{aa}\). Thus the finite graph is a weighted blow-up of a \(\tau\)-vertex type graph.
This is a genuine high-multiplicity regime: \(N\) may be tens of thousands or millions, while \(\tau\) is perhaps a few dozen recurring role-location cohorts. The type assumption is not that named people have identical personalities; it is that the model treats agents with the same complete role and interaction profile as interchangeable, exactly as high multiplicity requires.
The continuous instance consists of \(k\), rational masses \(\mu_a\), and a rational symmetric interaction matrix \(w\). A coalition pattern is an integral vector \(r\in\mathbb Z_{\ge0}^{\tau}\) with \(1\le \lVert r\rVert_1\le k\), where \(r_a\) is the number of type-\(a\) agents in that coalition. Its social welfare is \(F(r)=\sum_a r_a(r_a-1)w_{aa}+2\sum_{a<b}r_ar_bw_{ab}\).
The decision variable is \(y_r\ge0\), the mass of coalitions having pattern \(r\). It must satisfy \(\sum_r r_a y_r=\mu_a\) for every type \(a\). The objective is to maximize the normalized utilitarian welfare \(\mathrm{SW}(y)=\sum_r F(r)y_r\). A solution to \(\textsc{Typed-MaxUtil}_{\infty}\) is a feasible rational vector \(y\) whose welfare is at least \(1/k\) of the optimum for odd \(k\), or at least \(1/(k-1)\) for even \(k\).
This is not fractional coalition membership. Every configuration \(r\) is an ordinary integral coalition of at most \(k\) agents; only the population mass of such coalitions is continuous. If all input numbers are rational, clearing denominators turns \(y\) into a finite population of cloned agents partitioned into integral coalitions. Conversely, every finite typed blow-up of the paper’s graph induces such a \(y\). The objective and capacity constraint are therefore exactly the paper’s objective and constraint after normalization by population size.
Theorem 4’s approximation proof has a direct mass version. Introduce \(x_{ab}\) for the mass of type-\(a\), type-\(b\) pairs, including \(x_{aa}\) for same-type pairs. The constraints are \(2x_{aa}+\sum_{b\ne a}x_{\min(a,b),\max(a,b)}\le\mu_a\). Maximizing \(2\sum_a w_{aa}x_{aa}+2\sum_{a<b}w_{ab}x_{ab}\) is a compact linear program with \(O(\tau^2)\) variables. Pair the matched mass and leave the remainder in singleton coalitions.
For every coalition pattern \(r\) of size \(s\), the induced weighted complete graph has an edge coloring with \(s\) colors when \(s\) is odd and \(s-1\) colors when \(s\) is even. Hence one matching inside that coalition captures at least a \(1/k\) fraction of its welfare when \(k\) is odd, and a \(1/(k-1)\) fraction when \(k\) is even. Applying this argument to every configuration in an optimal mass allocation and integrating over \(y\) gives exactly the Theorem 4 ratio. The resulting pair-and-singleton allocation is thus a Class A continuous problem: its stated approximation task is solvable by a polynomial-size LP, independent of the number of cloned agents.
The authors should recognize this as their problem in a high-multiplicity regime. The mirror preserves their weighted symmetric ASHG utility, their bounded coalition size, their partition decision, and their utilitarian objective. It changes only the population representation, from named vertices to repeated exchangeable types. It does not replace the paper’s problem by divisible outcomes or by a mean-field utility over an infinite-sized coalition.
The main further questions are whether exact \(\textsc{Typed-MaxUtil}_{\infty}\) is tractable beyond fixed \(k\), whether its configuration LP admits efficient pricing when \(k\) is part of the input, and how closely a continuous optimum can be rounded for a prescribed finite population \(N\). For fixed \(k\), the configuration LP has \(O(\tau^k)\) columns; for variable \(k\), pricing becomes a nontrivial quadratic selection problem and may itself be hard. That is a useful boundary question rather than a defect in the mirror.
My weakest point is the type regime. An arbitrary friendship graph from the paper may have almost no repeated rows, in which case \(\tau\) is essentially \(N\) and the continuous representation provides no compression. The positive case therefore covers the weighted MaxUtil result on structured, genuinely high-multiplicity populations—role- or cohort-based social relations—not every graph instance studied by the paper. I think that restriction is defensible because the programme asks whether some sensible scenario admits a continuous mirror, not whether every named-agent graph does.
The strongest negative case is that Theorem 4 does not actually expose a population-continuous phenomenon. Its proof is an edge-colouring argument followed by a maximum-weight matching. In the proposed model, the \(O(\tau^2)\)-variable LP is simply maximum-weight matching on the quotient graph of types, with capacity \(\mu_a\). The resulting pair allocation is the first matching round of Algorithm 1 performed after identifying cloned vertices. Thus the continuum contributes compression, but no new structural or computational question: it is a compact restatement of the paper’s matching proof.
The exact high-multiplicity problem is different. Its natural formulation has a variable \(y_r\) for every integral coalition pattern \(r\) with \(\lVert r\rVert_1\le k\). The number of such patterns is potentially exponential, and the pair LP does not solve that exact configuration problem; it only supplies the same approximation guarantee. The proponent’s stronger suggestions about exact optimization and pricing are worthwhile new problems, but they are not mirrors of Theorem 4 itself. They extend the paper beyond its stated result.
There is also a genuine modelling thinness. The mirror applies only to block-constant graphs in which every agent of type \(a\) has exactly the same value for every agent of type \(b\). An arbitrary friendship instance has \(\tau\) essentially equal to the number of agents, at which point the supposed continuous representation has lost its compression. The proposed employment or transport examples are plausible compatibility markets, but they replace individualized friendship with role-level complementarity. That is a defensible new model, not an obviously canonical high-multiplicity version of the paper’s social-network model.
Still, this negative case does not defeat the anchor under the programme’s rules. Theorem 4 is a named computational result, and the weighted blow-up regime is a legitimate high-multiplicity instance regime. Rational \(y_r\) can be denominator-cleared into a finite population of cloned agents, while every finite typed blow-up induces such a \(y\). The coalition size remains an integral local constraint; the construction is not illicit fractional coalition membership. The pair LP is therefore a valid polynomial-time continuous approximation algorithm for a recognizable version of the paper’s problem.
One might object that coalitions of bounded size have measure zero in an atomless population, but the configuration-mass formulation correctly preserves finite coalition indivisibility. That objection would reject the programme’s own high-multiplicity interpretation rather than this mirror.
So the honest negative conclusion is limited: the proposed mirror is probably incremental and does not continuize the paper’s full stability theory. But I cannot honestly claim that no worthwhile mirror exists. Theorem 4 survives: it gives a clean, faithful Class A high-multiplicity approximation problem, and the stronger exact configuration/pricing version supplies a natural boundary question.
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.