Springe direkt zu Inhalt

Colloquium by Klaus Heeger (Technische Universität Berlin): Stable Matchings Beyond Stable Marriage

Jan 31, 2022 | 04:00 PM s.t.

Stable matchings are well-studied from computer science, mathematics, and economics. In the most basic setting, called Stable Marriage, there are two sets of agents. Each agent from one set has preferences over the agents from the other set. A matching assigns the agents into groups of two agents. A matching is called stable if there are no two agents preferring each other to the partners assigned to them. In this talk, we will review important parts of my forthcoming PhD thesis concerning the computational complexity of two extensions of this basic model: First, we assume that an instance of Stable Marriage is given, and the aim is to modify the instance (using as few "modifications" as possible) such that a given edge is part of some stable matching. Second, we assume that agents have preferences over sets of d-1 other agents (for some d>2). In this case, a matching matches agents into groups of size d, and a matching is stable if there are no d agents preferring to be matched together to being unmatched. While since 1991 this problem is known to be NP-complete, we study the case that the preferences of all agents are "similar".

Time & Location

Jan 31, 2022 | 04:00 PM s.t.

Online via Zoom.

Freie Universität Berlin
Technische Universität Berlin
Humboldt-Universität zu Berlin
Deutsche Forschungsgemeinschaft (DFG)