Centralized matching market design is one of the success stories of algorithmic game theory. This project concerns two-sided matching that captures the setting where students have preferences over schools, schools have priorities over students, and the goal is to match the students to the schools in a stable manner. Although the Deferred Acceptance algorithm is a well-known solution for the problem, it need not work seamlessly when there are additional distributional constraints involved in the matching problem. For example, there may be diversity constraints that a school must accept a certain proportion of minority students. Another example of a distributional constraint is that a school in a certain region should get a minimum number of students. The goal of the project will be to examine challenging matching problems with distributional constraints and design algorithms for them.
The goal of the project will be to examine challenging matching problems with distributional constraints and design algorithms for them.
Expected outcomes include valuable learning of important algorithms for Expected Outcomes: proofs, implementation of algorithms, and an opportunity to get a real taste of doing research.