Seminar Details
It's Hard to Find a Stable Marriage: Strategic Exploitation of the Gale-Shapley Algorithm
- Start Date: October 24, 2018
- Event Start Time: 12:15 PM
- Event End Time: 1:15 PM
- Seminar Series: Graduate Combinatorics Seminar
- Presenter(s): John Chiarelli - Rutgers University
- Event Location: Mathematics Graduate Student Lounge -- 7th Floor | Rutgers University | Hill Center | Mathematics Department
- Presentation Type: Stand Alone Presentation
- Abstract:
The stable marriage problem is a classic one in the library of discrete math. The best-known results on the problem stem from the work of David Gale and Lloyd Shapley, who in their 1962 paper not only showed that a stable matching exists for every possible instance of the problem, but also gave an algorithm for finding such a matching. However, in applications of finding stable matchings between agents, these agents may choose to be dishonest about their preferences. In this talk, I will discuss the circumstances under which agents in the Gale-Shapley algorithm can improve their outcome by lying about their order of preference