Mini-course on The Stable Marriage Problem

Time: 10:00 đến 12:00 ngày 15/02/2016, 09:00 đến 11:00 ngày 16/02/2016,

Venue/Location: Lecture Hall C2-714, VIASM, 7th floor, Ta Quang Buu Library

Content:

Time: 10:00-12:00 Monday Feb 15, 2016 and 9:00-11:00 Tuesday Feb 16, 2016.

Location: Lecture Hall C2-714, VIASM, 7th floor, Ta Quang Buu Library

Lecturer: Prof. Vu Ha Van – Yale University

Abstract: In this series of talks, we are going to discuss the stable marriage problem, which is of fundamental importance in economy. As well known, the elegant solution of Gale and Shapley later earned Shapley a Nobel prize. Furthermore, the Gale-Shapley algorithm has a wide range of applications which may be of today interest. (Recently, there have been suggestions that it could even be used to aid the selection process to universities in VN.)

We will present Gale-Shapley’s algorithm in details, its analysis, advantages and disadvantages. Next, we will also look at the performance of the algorithm with respect to random inputs, and also in the situation when some of the participants decide to cheat.

Program:

(1) Introduction of the problem and the fundamental (Gale-Shapley) algorithm.

(2) Analysis of Gale-Shapley algorithm

(3) Getting married with random lists

(4) What if one cheats?