Szabó László: Stable Marriage Problems I+II

Place

room G202 & A112, FIT VUT v Brně, Božetěchova 2,, Božetěchova 2, 612 00 Brno, CZ

Organiser

Department of Information Systems FIT BUT

Type

seminar

Access

free

Description

The seminar is organized by the Formal Model Research Group at the Department of Information Systems, Faculty of Information Technology, Brno University of Technology. As its central scientific topic, it discusses formal models and their applications. Recent presentations are to be found at http://www.fit.vutbr.cz/~meduna/work/doku.php?id=talks:seminar.

Author: Dr. Szabó László (Faculty of Informatics, Eötvös Loránd University, Budapest, Hungary)
Title: Stable Marriage Problems I+II
Part I: Thursday, October 5, 2017, 8:00-11:00, room G202
Part II: Friday, October 6, 2017, 10:00-12:00, room A112

Abstract: Matching problems arise in numerous applications. Dating services want to pair up compatible couples. Students need to be matched to universities. Other assignment problems involving resource allocation arise frequently, including balancing the traffic load among servers on the Internet. In the following version of the problem suppose we have an equal number of boys and girls. Every boy lists the girls in order of his preference, and every girl lists the boys in order of her preference.

We would like to arrange marriages between the boys and girls so that there is not a boy and a girl who prefer one another to their spouses. In their 1962 paper, Gale and Shapely demonstrated that, given a set of preferences for every boy and girl, there is always such a stable matching; even better, they showed how to find one by applying an elegant algorithm. It is relatively straightforward to extend this algorithm to situations where there are an unequal number of boys and girls and we allow polygamous matchings in which parties in one group may be matched with more than one party from the other group, which applies when, e.g., universities accept more than one student.