BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20261031T185821Z
UID:Seminar-ACS-1523@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Karteek Sreenivasaiah:MAILTO:Karteek.Sreenivasaiah@liverpool.ac.uk
DTSTART:20261104T130000
DTEND:20261104T140000
SUMMARY:Algorithms and Computing Systems Series
DESCRIPTION:Will Rosenbaum: Temporal Stable Matchings\n\nIn 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. \n\n\n\nIn 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.\n\n\n\nThis talk is based on ongoing collaboration with Duncan Adamson, George Mertzios, and Paul Spirakis\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1523
LOCATION:GH223
END:VEVENT
END:VCALENDAR