Minimizing Class Conflicts through Game Theory and Matching
As prelim season starts up, you may notice that there exist a decent amount of prelims and final exams that exist concurrently; these are time conflicts, and you may have had to deal with them personally before. These conflicts and, specifically, the methods in which we avoid them, provide an interesting application of the matching markets that we have been learning about. The goal of the exam coordinators is to achieve perfect matching; if we make matchings for, say, every individual 30 minutes, there should be a bijective relationship between students and their exams, such that no student is ever connected to more than one exam.
As we all know, however, that does not always pan out; inevitably, because of how many students are in so many diverse courses, there will be conflicts, this is where valuations begin to come into play. So far, our discussion on valuations in matching market has been to maximize the total—what if, instead, we attempted to minimize total valuation? In this scenario, the minimization of total valuations is equivalent to minimizing total conflicts, and this is the basis on which all exam conflict scheduling algorithms are built on. Actually doing this is quite challenging, and for a class the size of cornell, the algorithms involved are probably quite out of the scope of this course, but the high level view of what is considered in these algorithms and how they connect to our networks class is very interesting!
Source: https://cuongdo.math.uconn.edu/exam-scheduling-conflict-optimization/