Booth Id:
MATH005
Category:
Mathematics
Year:
2022
Finalist Names:
Baskaran, Niranjan (School: Gateway International School)
Abstract:
Consider assigning students to a set of classes, and classes to a set of students. Each student will attend more than one class, and each class will have more than one student (many-to-many matching). Students will have preferences over classes and vice versa, oftentimes with ties (indifferences). Our research question is this: How can we match students and classes so that all students have the best possible assignment when there are ties in their preferences over choice of classes? More and more, people are giving multiple choices the same rank in their preferences (E.g: Internet quizzes, opinion polls and college choices), creating ties and making the consideration of these indifferences increasingly important. In our research, we extend previous results in many-to-one markets to many-to-many. To this end, we define "stable worker improvement cycles" in many-to-many matchings, that when carried out, leave workers/students better off without breaching stability. We show that only the absence of these cycles implies worker-optimality. This result helps us create an efficient worker-optimal matching algorithm for many-to-many markets with indifferences that systematically looks for and carries out such cycles. We also note possibilities to explore both the efficiency of our algorithm and systems of tie-breaking in many-to-many matchings. The implications are plentiful. Our algorithm allows for effective matchings in a variety of many-to-many markets like education (student-class), employment (consultant-firm), and supply chains (buyer-producer) when the need of one agent is prioritized. These results contribute to the under-researched fields of many-to-many matchings and matchings with ties.
Awards Won:
Mu Alpha Theta, National High School and Two-Year College Mathematics Honor Society: First Award of $ 1,500