BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260417T073343Z
UID:Seminar-dept-1338@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Lutz Oettershagen:MAILTO:Lutz.Oettershagen@liverpool.ac.uk
DTSTART:20260421T130000
DTEND:20260421T140000
SUMMARY:School Seminar Series
DESCRIPTION:Martin Bullinger: The Power of Matching for Welfare Approximation in Coalition Formation\n\nThe 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.\n\nIn 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.\n\nWe 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:\n\n1.) The standard offline model, where all data is known upfront.\n\n2.) The standard online model, where decisions must be made as agents arrive.\n\n3.) An online model with recourse, where algorithms are permitted to dissolve existing coalitions.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1338
LOCATION:
END:VEVENT
END:VCALENDAR