The Power of Matching for Welfare Approximation in Coalition Formation

21^st April 2026, 13:00
Martin Bullinger
University of Bristol

Abstract

The matching problem asks how to pair a set of individuals with heterogeneous mutual compatibility to maximise total compatibility of all pairs. It is a cornerstone problem amongst others in algorithm design, discrete mathematics, and economics, with an abundance of applications ranging from school choice and ride-hailing to kidney exchange.
In this talk, I demonstrate that matching is a powerful tool when tackling the more general algorithmic question of coalition formation, where groups of larger sizes may form. In this context, the goal is to maximise total welfare, a measure that captures the aggregate compatibility within all formed groups. Coalition formation models can be applied to solve problems such as team formation, clustering, or community detection.
We will repeatedly see evidence for the paradigm that matching algorithms yield (asymptotically) optimal algorithms for approximating welfare. This will be illustrated in the prominent game classes of additively separable and fractional hedonic games and across three distinct algorithmic settings:
1.) The standard offline model, where all data is known upfront.
2.) The standard online model, where decisions must be made as agents arrive.
3.) An online model with recourse, where algorithms are permitted to dissolve existing coalitions.

Biography

Martin Bullinger is a Lecturer in Artificial Intelligence at the University of Bristol. Previously, he was a Postdoctoral Researcher at the University of Oxford. He obtained his PhD from the Technical University of Munich.
Martin has a particular interest in topics related to computational social choice, algorithmic game theory, combinatorial algorithms, and computational complexity. His research covers various scenarios in multiagent systems, including coalition formation, matching markets, the emergence of segregation, understanding polarisation, and voting theory.

Additional Materials

• https://arxiv.org/abs/2505.06163