Temporal Stable Matchings

4^th November 2026, 13:00 GH223
Will Rosenbaum
University of Liverpool

Abstract

In the classical Stable Marriage Problem (SM), there are two sets of agents, A and B, and each agent in A has preferences in the form of a linear ranking of the agents in B, and symmetrically, each agent in B has preferences over A. The goal in is to find a matching between A and B that is stable: there is no pair of agents a in A and b in B that are not matched with each other but prefer each other to their partners in the matching.

In this talk, I will introduce a generalization of the stable marriage problem to temporal graphs: the Temporal Stable Matching Problem (TSM). While SM is classically treated as a 1-shot problem, a TSM instance models changes in the agents' availability to match over time. I will define two notions of stability in the TSM model: Temporal Stability and Myopic Stability. Temporal Stability models a notion of stability appropriate for agents that are aware of future matches and are willing to wait for a better match in the future. Myopic Stability requires stability at every time t given only the previous and current state of the agent without knowledge of future matches. For both types of stability, I will present both hardness results and efficient algorithms for special cases.

This talk is based on ongoing collaboration with Duncan Adamson, George Mertzios, and Paul Spirakis