Least Unstable Above Stable Cardinality Matchings in the Stable Marriage Problem with Ties and Incomplete Lists

6^th February 2019, 13:00
Duncan Adamson
University of Liverpool

Abstract

When we consider matching problems we often look to find matchings that are stable, however in many variants such as the stable marraige problem with ties and incomplete lists such a matching may not include the maximum possible number of agents. While finding a maximum cardinality matching can be done in polynomial time, we often want to find one which is ``almost stable'', containing either as few blocking agents or pairs as possible, with the problem of finding a matching satisfying one of these conditions being NP-hard. In this work we will provide theoretical results for the these matchings, providing bounds on the numbers of both blocking agents or pairs, depending on what we are looking to minimise.

This is work from the project of Duncan's MSci at the University of Glasgow, supervised by Prof. David Manlove.