| paper | Computing Stable Coalitions: Approximation Algorithms for Reward Sharing |
| authors | Elliot Anshelevich, Shreyas Sekar |
| venue | WINE 2015 |
| filed under | coalition · hedonic |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Yes: a \((2\beta,2\beta)\)-solution can be computed using polynomially many value queries and bit operations in \((m,\tau,L)\). · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given finitely many projects \(P\), complete agent types \(T\), rational masses \(\mu_t\) with \(\sum_t\mu_t=1\), and monotone positively homogeneous subadditive valuations \(V_k:\mathbb{R}_{\ge 0}^{\tau}\to\mathbb{R}_{\ge 0}\), choose assignment masses \(x_{k,t}\) satisfying \(\sum_k x_{k,t}=\mu_t\) and reward densities \(p_{k,t}\). For every project \(k\), every feasible deviating mass \(y_{\ell k t}\le x_{\ell,t}\) from projects \(\ell\ne k\) must satisfy \(V_k(x_k+y_k)\le \rho\left(\sum_t p_{k,t}x_{k,t}+\sum_{\ell\ne k,t}p_{\ell,t}y_{\ell k t}\right)\). Compute a welfare-maximizing approximate-core solution, in particular a \((2\beta,2\beta)\)-solution from a supplied \(\beta\)-approximate typed welfare allocation and dual certificate.
A finite-type, high-multiplicity cooperative allocation model: mass \(x_{k,t}\) is assigned to project \(k\), project value is \(V_k(x_k)\), rewards are type-project densities \(p_{k,t}\), welfare is \(\sum_k V_k(x_k)\), and stability quantifies over all feasible mass coalitions.
The proposed \(V_k\) functions and type-level reward densities are additional symmetry assumptions, and the paper’s individual reserve-price, singleton-value, and dummy-agent arguments do not directly establish the claimed \(2\beta\) guarantee for mass coalitions.
fatal: False
The mirror covers Theorem 2’s black-box welfare-to-stability construction and its typed XoS or subadditive instantiations; it leaves the paper’s lower bounds, anonymous-function results, auction equivalence, and auction-specific equilibrium guarantees unaddressed.
The cleanest positive case is a high-multiplicity version of the paper’s own finite-project reward-sharing problem. I would use only one anchor, because the paper contains no named NP-hardness theorem: its remarks that welfare maximization is NP-hard are not themselves eligible computational anchors.
My lead anchor is Theorem 2, proved in this paper. It states that, for subadditive project valuations, given an \( \alpha \)-approximate solution to the welfare-allocation LP together with the relevant optimal dual information, one can construct in polynomial time a \( (2\alpha,2\alpha) \)-core-stable solution. In the paper’s convention, this means a solution whose welfare is within a factor \(2\alpha\) of optimum and whose payments are either fully budget-balanced with \(2\alpha\)-stability, or fully stable with total payments at most \(2\alpha\) times welfare.
I would mirror it with Typed Continuous Approximate Core for Finite Projects.
An instance consists of:
\[ V_k:\mathbb{R}_{\ge 0}^{\tau}\to\mathbb{R}_{\ge 0}. \]
Here \(x_{k,t}\) is the mass of type \(t\) assigned to project \(k\), subject to
\[
\sum_{k\in P}x_{k,t}=\mu_t.
\]
The project receives the type-mass vector \(x_k=(x_{k,1},\ldots,x_{k,\tau})\) and generates value \(V_k(x_k)\). The welfare is
\[
W(x)=\sum_{k\in P}V_k(x_k).
\]
A concrete finite representation is an XoS-type valuation
\[
V_k(z)=\max_{q\in Q_k}\sum_{t\in T}a_{kqt}z_t,
\]
although the more general oracle model used by the paper can also be adopted.
This is genuinely a population mirror, not divisible project output. Each infinitesimal agent is assigned wholly to one project; only the mass of repeated agents is divisible. A finite realization with \(n\mu_t\) agents of type \(t\) is obtained by clearing denominators. Conversely, a finite typed instance becomes a rational mass profile after normalization. The functions \(V_k\) are the consistent per-capita limits of the finite project valuations.
The decision also includes nonnegative reward densities \(p_{k,t}\): an agent of type \(t\) assigned to project \(k\) receives reward \(p_{k,t}\). For every project \(k\), consider a possible deviating coalition represented by masses \(y_{\ell k t}\), where \(y_{\ell k t}\) is type-\(t\) mass currently on project \(\ell\neq k\) that joins \(k\). Let
\[
y_{k,t}=\sum_{\ell\neq k}y_{\ell k t},
\qquad
0\le y_{k,t}\le \mu_t-x_{k,t}.
\]
The coalition-stability requirement is
\[
V_k(x_k+y_k)
\le
\sum_t p_{k,t}x_{k,t}
+
\sum_{\ell\neq k}\sum_t p_{\ell,t}y_{\ell k t},
\]
for every \(k\) and every feasible deviation. Thus the project’s incumbents and the deviators’ existing rewards must together cover the value that the enlarged coalition could create. One may relax this inequality by a factor \(\rho\), exactly as in the paper’s \(\rho\)-stability notion.
The continuous problem is:
Given \((m,T,\mu,(V_k)_k)\), compute an allocation \(x\) and rewards \(p\) that maximize welfare subject to approximate core stability and approximate budget balance. In particular, given a \(\beta\)-approximate solution to the typed welfare LP and its dual certificate, compute a \( (2\beta,2\beta) \)-core-stable solution.
This is recognisably the authors’ problem. It retains finite, non-identical projects; project-dependent subadditive value; assignment of agents to projects; coalition deviations; reward sharing; budget balance; and welfare maximization. The only change is that repeated workers are represented by mass rather than by names. A large research agency assigning thousands of recurring researchers, engineers, or grant applicants to a small number of projects is a credible regime: \(n\) is large, while \(\tau\), the number of skill/preference profiles, is modest. The type includes all exogenous attributes relevant to valuations and outside options. Rewards are endogenous outcomes of the solution, not idiosyncratic input prices.
I would expect the restricted XoS or demand-oracle version to be Class A. The paper’s LP machinery becomes a typed configuration LP, with type-mass configurations replacing subsets of named agents. Its reserve-price matching routine should become a mass-transfer routine: “heavy” and “light” users become heavy and light portions of types, while the finite set of type coordinates keeps the pricing problem finite-dimensional. The natural target is polynomial time in \(m\), \(\tau\), and the encoding length of \(\mu\) and the valuation data, rather than in the denominator-cleared population size \(n\).
The unrestricted version may have a harder boundary. If type-level demand or pricing is itself difficult, the continuum does not magically remove project-assignment combinatorics; hardness could transfer through the number of projects or valuation clauses. That is a useful follow-up rather than a defect:
The weakest point is that Theorem 2 is a black-box theorem: its polynomial-time statement assumes an approximate welfare allocation and optimal dual information. The paper does not prove that the raw continuous typed instance supplies those objects, and the extension from set functions on named agents to homogeneous functions of type mass requires a carefully specified valuation model. Thus I would not claim that the paper already proves the continuous theorem. The honest claim is narrower: it supplies a named, proved algorithmic anchor whose central mechanism has a natural high-multiplicity analogue, and the resulting problem is a serious computational question rather than a cosmetic replacement of \(N\) by a distribution.
The only eligible anchor is Theorem 2, and the strongest negative case is that the proposed mirror does not actually transfer that theorem’s computational content.
Theorem 2 is not merely a statement about an allocation LP. Its algorithm uses atomistic identities throughout: individual dual prices \(p_i^*\), singleton values \(v_k(\{i\})\), moving one whole agent into an empty project, and the cardinality argument that a bad project retains more than half its agents. The dummy-agent construction and the payment redistribution also depend on named agents being individually assigned and paid.
Collapsing agents into types creates a trilemma. If valuations remain arbitrary set functions, then two agents with the same advertised type can still have different effects in coalitions; preserving those effects requires treating them as different types. Then \(\tau\) grows with \(N\), and normalizing the electorate into masses is only a change of units. There is no high-multiplicity compression.
If instead agents of one type are genuinely interchangeable, the primitive \(v_k:2^N\to\mathbb{R}_+\) has been replaced by a new mass valuation \(V_k:\mathbb{R}^{\tau}_{\ge 0}\to\mathbb{R}_+\). That may be a sensible cooperative game, but it is not supplied by the paper. The proof of Theorem 2 does not survive by notation: an infinitesimal mass has no singleton value, mass can be split between projects, and the one-agent reserve-price routine, half-cardinality lemma, and dummy-agent argument all disappear. A new atomless-core theorem would be required.
The proponent’s positively homogeneous XoS restriction makes the gap sharper. For rational masses, it can be lifted to a specially symmetric finite instance by setting
\[
v_k(S)=n\,V_k\!\left(\frac{\#_t(S)}{n}\right).
\]
But this is only a narrow, type-symmetric subclass of the paper’s valuation model. Applying Theorem 2 to the expanded instance does not yield an algorithm polynomial in \(\tau\); obtaining such compression is precisely the new theorem that remains unproved. Moreover, the finite paper’s important examples use population-size effects and exceptional coalitions—such as a project whose value jumps when the grand coalition forms. Positive homogeneity erases that distinction.
The payment model introduces another unacknowledged change. The paper may pay two otherwise identical agents differently because their project assignments and outside options differ. Requiring a common density \(p_{k,t}\) is an additional symmetry constraint. Allowing arbitrary within-type payment variation preserves the finite theorem but destroys the compressed representation; forbidding it produces a different stability concept.
One can rescue the idea by defining a bounded-simplex, possibly nonhomogeneous mass valuation and by proving a genuinely new measure-valued core theorem. That could be worthwhile research, but it would be a new atomless coalition-formation model, not a continuous form of Theorem 2 established by the paper. Thus the proponent has shown plausibility, not a valid mirror: the claimed \((2\alpha,2\alpha)\) transfer is unsupported, and every faithful route either retains \(N\) identities or replaces the theorem’s central problem.
The negative case is not airtight. A carefully chosen type-symmetric XoS regime may well support a valuable high-multiplicity result. But the honest conclusion is that the paper itself does not provide the bridge, and the universal claim that no worthwhile mirror exists is stronger than the evidence permits.
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.