Sparse Probabilistic Coalition Structure Generation: Bayesian Greedy Pursuit and $\ell_1$ Relaxations
This addresses coalition formation in multi-agent systems where values are uncertain, offering a probabilistic framework with theoretical guarantees, but it is incremental as it builds on existing sparse regression methods.
The paper tackles the problem of coalition structure generation when coalition values must be learned from episodic observations, modeling it as a sparse linear regression. It introduces Bayesian Greedy Coalition Pursuit and an ℓ₁-penalized estimator, showing that BGCP recovers profitable coalitions with high probability once T ≳ K log m and provides welfare-optimal structures.
We study coalition structure generation (CSG) when coalition values are not given but must be learned from episodic observations. We model each episode as a sparse linear regression problem, where the realised payoff \(Y_t\) is a noisy linear combination of a small number of coalition contributions. This yields a probabilistic CSG framework in which the planner first estimates a sparse value function from \(T\) episodes, then runs a CSG solver on the inferred coalition set. We analyse two estimation schemes. The first, Bayesian Greedy Coalition Pursuit (BGCP), is a greedy procedure that mimics orthogonal matching pursuit. Under a coherence condition and a minimum signal assumption, BGCP recovers the true set of profitable coalitions with high probability once \(T \gtrsim K \log m\), and hence yields welfare-optimal structures. The second scheme uses an \(\ell_1\)-penalised estimator; under a restricted eigenvalue condition, we derive \(\ell_1\) and prediction error bounds and translate them into welfare gap guarantees. We compare both methods to probabilistic baselines and identify regimes where sparse probabilistic CSG is superior, as well as dense regimes where classical least-squares approaches are competitive.