-
Notifications
You must be signed in to change notification settings - Fork 12
Home
Welcome to the CourseMatch.jl wiki!
Our current strategy breaks down the problem into two steps and defines a subset of issues within each step. A brief sketch:
- Preferences
- Allocation problem
-
Translation of pseudo code to Julia
- Stage 1: Price vector search (Neighbouring price vectors)
- Stage 2: Eliminate over-subscription
- Stage 3: Reduce under-subscription
- Demand function
- Course constraints
- Clearing error function
The following section provides further details and specifies our approach.
In the first step, students insert their preferences over schedules of courses by assigning values from 0-100 to each course. Students can if applicable, define complementary course bundles. In an important respect, the class registration problem can be broken down into smaller self-contained problems (Tronc Commun, electives etc.). Problems of intersectionality, as in the case of Core Curriculum and concentration classes, might be solved by allocating additional tokens to the budget of the more important 'stakeholder' (i.e. 2nd-year students and primacy of students who need a given course as core curriculum). We might want to limit the maximum number of course bundles to a reasonable
The question arises how do we get student's preferences into the application? Our approach so far is to define a matrix for each student. Rows and columns represent courses, the values in the diagonal will represent individual utility for each course. Elements outside diagonal represent substitutes (if the value is negative) and complements (if the value is positive) The diagonal elements will represent the individual utility derived from taking that course, whereas elements outside the diagonal will indicate whether the two courses are substitutes and complements (as well as how strong is the complementarity/substitutability). Think on the following matrix for 3 courses: [80 10 -50; 10 90 0; -50 0 60].So each course will report 80, 90 and 60 utility units respectively. Courses 1 and 2 together will report 20 points of additional utility (I write 10 but it'll make sense later). On the contrary, course 1 and 3 are substitutes, so together that will mean minus 100 points of utility. Course 2 and 3 together report no additional utility for the sake of the example. We can easily tune the additional values of utility to achieve the +200 and -200 from the paper. With this matrix form, the computation of the utility becomes as follows: X is a row vector of 0s or 1s. Say the utility Matrix is U. The final utility will be X'UX. This matrix form is the reason why outside the diagonal we report the bonus utility divided by 2. A problem with this approach is that our objective becomes nonlinear. Also, this approach might be too complicated for the user and we have to think about how we scale the preference input for course bundle: plausibly, we could translate an ordinal scale (strong compelements = +100, complements = +50, substitute = -50, strong substitutes = -100).
We have to store the student input somehow. This issue is not resolved yet, see issue page for further discussion.
This section relates to the implementation of the algorithm. Budish et. al (2015) provide the pseudo-code for the algorithm (p. 14, 17, 19). We translate the generic expressions into Julia code, functions within the code such as the search for neighboring price vectors, the demand function, and clearing error function are considered separately below. The general algorithm is structured into three stages. We have not translated the pseudo-code for stages 2 and 3 yet. Nor do we have completed the function that returns neighboring vectors.
Stage 1, finds a price vector p⇤ that is an approximate competitive equilibrium. In this stage, we define a function for neighboring price vectors. This function follows a hybrid neighborhood approach that combines two different, independent ways of generating neighbors. The first way to generate new neighbors is to move along the gradient of error, raising prices of classes that are oversubscribed and lowering the prices of classes that are undersubscribed proportionally (i.e. Gradient Neighbors). The second way to generate new neighbors is to raise/reduce the price of a small set of courses that are over-/under-subscribed such that it reduces demand by exactly one student in the case of over-subscription and lowers its price to zero in the case of under-subscription (i.e. Individual Adjustment Neighbors). As soon as these neighborhoods are generated, the algorithm should drop all the price vectors that generate an allocation that is identical to the one generated by the current price vector. The final neighbors are defined as the union of the output of these two approaches, after the vectors generating the same allocation are removed. Because of the way that the neighborhood is designed, it is expected that the clearing error will drop dramatically in the first few search rounds, and then proceed to dropping more slowly after a while. This is due to the fact that in the first rounds we expect the search to pick vectors from the gradient neighborhood, which are considerably different than the current candidate vector. After a few rounds the search should reach an allocation that is close to a local minimum, and as such we expect that the vectors picked come from the individual neighborhood, in which vectors are very similar to the current candidate. In order to avoid spending a lot of time searching around a local minimum, a limit of searches should be defined so that after reaching it the search will re-start from a different point. The allocation obtained in this step may have both over-subscription and under-subscription errors.
Stage 2, Eliminate Over-subscription, modifies the prices from Stage 1 so as to eliminate all over-subscription errors that cause violations of the strict capacity constraints (the qˆ capacities); at this stage, the solution is feasible.
Stage 3, Reduce Under-subscription, then attempts to reduce, to the extent possible, any under-subscription errors, without too much compromise of fairness considerations.
So far, we set up a function which given a set of prices, preferences, budget and capacity, returns a demand vector for each course. We also added a couple of tests. However, we have not included the possibility of cross-preferences yet.
Two constraints arise. First, courses cannot be at the same time. To account for this constraint, we should develop a feasibility matrix F, where each row and column represent a course. Indicate simultaneous feasibility by 0, infeasibility by 1. Then, we could add to the optimizer the constraint that x'Fx = 0. For an example look at the issue page. Second, we need to have constraints on electives/mandatory courses. For an example look at the issue page.
If the course is assigned a positive price, then the clearing error is the difference between the number of students assigned to the course (i.e., total demand) and the course’s capacity. A course is over-subscribed if its demand exceeds its capacity and it is under-subscribed if it is over-subscribed if its demand exceeds its capacity, and it is under-subscribed if its demand is less than its capacity and its price is strictly positive. This issue is not resolved yet, see issue page for a draft and a test.