It1 is the registrar’s job to oversee the assignment of classes2 to students. When at

least one class is oversubscribed, this problem becomes much more difficult, since the

registrar must decide who is allowed to enroll in the class, and who is rejected. This

problem, which we refer to as the student-class combinatorial assignment problem , is

a particular instance of a more general problem known as a combinatorial assignment

problem. “Combinatorial” refers to the fact that students are assigned a combination

of classes, namely a schedule, and that they have a preference over how the bundle

is composed.3

We call the structure that determines the assignment of students to classes a

mechanism. When a class is oversubscribed, typically the registrar relies on the

mechanism to determine which students get in and which don’t. Clearly the mech-

anism is central to arriving at a good assignment. But this gives rise to another

question— what is a good assignment? Is it an assignment that is efficient? Is

it an assignment that tells us something about what students want? How do we

determine what “efficiency” is in the first place? Mechanism design is the study

of mechanisms in general, and mechanism designers seek answers to questions like

these, in a general context. A mechanism designer tries to create new mechanisms

that solve design problems like the student-class assignment problem. We can think

of a mechanism designer as similar to an engineer, only they operate in an economic

domain. Mechanism design is a nascent science, and is considered a sub-discipline

´ a

1

I would like to thank my project advisor Ad´m Galambos. Thanks to Eric Budish, Marilda

Sotomayor, Anne Norman, and Brenda Jenike for their helpful conversations. Thanks also to the

honors committee judging my paper, consisting of Bruce Pourciau, Scott Corry, and Peter Gilbert.

2

We use class to mean a particular class section. That is, a particular class offered a particular

time, taught by a particular teacher. It may also be referred to as a course, and the two are

interchangeable.

3

If students do not care about how their bundle is composed, we call it a “multi-unit” assignment

problem instead.

2

problem that have been completely overlooked. We hope to broaden the conceptual

framework within which the student-class assignment problem is formulated, allowing

for a more complete modeling of the problem that allows us to include components

we feel have been ignored. This involves the introduction of matching theory, and

we offer a survey of the theory. We hope that in addition to finding merit in the

theory for its inherent interest, the reader is also convinced of its applicability to

the problem at hand. To the best of our knowledge, framing the student-classes

assignment problem as a matching problem is novel. We also introduce student

uncertainty over schedule preferences. We believe this feature is novel.5

We operate in an inchoate theoretical realm— matching theory is far from com-

plete, and the student-classes assignment problem is just beginning to be tackled as

a mechanism design problem. We hope to formulate specific questions that would

be of particular relevance to the problem. Finally, we hope to leave the reader with

a sense of how the Lawrence registration process can be improved, by discussing

potential changes to the mechanism.

The structure of this paper

The structure of this paper is as follows. We begin with a description of the criteria

we find desirable in a student-class assignment mechanism in section 1.2. In 1.3, we

offer a short discussion about the difficulties associated with actually realizing all of

these criteria, and some of the difficulties associated with modeling the problem in

general. In section 2, we survey two matching mechanisms currently in use, discussing

some of their difficulties. In sections 3-5, we model and analyze the current Lawrence

registration mechanism. The student-class combinatorial assignment problem is then

reframed a student-class matching problem in section 6. Here we offer a survey of

the relevant ideas in matching theory, as well as an example of applied matching

theory. Section 7 offers a survey of specific matching models. In section 8, we

construct a new model to discuss the student-class matching problem. Using this

model, we point out additional difficulties with the Lawrence mechanism, and offer

some potential solutions.

1.2

Evaluation criteria

In order to evaluate various assignment mechanisms, we need to first establish the

criteria by which we will evaluate them. The following basic criteria are of cen-

tral importance, and will be the primary considerations when we evaluate various

5

Eric Budish informed us that this was his opinion as well.

4

1.3

What makes the student-class assignment problem dif-

ficult?

Preferences

Leading market designer and matching theorist Alvin Roth summarizes the difficulty

with the student-class assignment problem as follows.

The problem of allocating classes to students is a famously hard problem

of market design. The reasons include the fact that, in most applica-

tions, it isn’t acceptable to sell the most desirable class places at higher

prices to richer students. Also, students take multiple classes, and may

have preferences for how their bundle is composed. So the problem is

substantially more difficult than how to auction multiple goods, or how

to allocate each student a single place, as comes up e.g. in assigning

students to schools.7

Roth notes that “students may have preferences for how their bundle is com-

posed.” That is, students may care not only about the individual classes they take,

but also about the way those classes are combined. The most basic approach to

modeling the student-class assignment problem has been to assume that students

have a preference relation over classes, and from this infer the way a student feels

about various schedules— essentially ignoring this “bundle” preference. While this

approach may simplify the problem considerably, it is problematic for many reasons.

For instance, consider a student who chooses their schedule by first determining

which classes they need to take for their major, and then filling in the holes with

electives. This is a realistic reflection of many students’ true process, roughly. Let

us suspend disbelief and suppose that the student does have a preference relation

over classes. After having determined which classes they must take for their major,

what if the student finds out that his “most preferred” elective is offered at the same

time as one of his required classes? Perhaps the student responds by finding his most

preferred elective from those that do not conflict with his required classes. Surely he

prefers the schedule with the non-conflicting elective to the one with the conflicting

elective, but how can we deduce this simply from a preference order over individual

classes? Clearly the worth of a particular class is contingent on the other classes

taken in conjunction with it.

Complementarities exist in many other forms, too. Perhaps a math student would

be eager to take any of three upper-level math classes, yet would recoil in horror at

7

Taken from Al Roth’s maket design blog: http://marketdesigner.blogspot.com/2009/04/course-

allocation-by-eric-budish.html.

6

each class.

Table 1: Utilities

Beer Tutorial

Wine Tutorial Calculus Topology

s1

70

25

3

s2

52

40

5

They are college students, so they prefer beer to wine, and they are lazy, so they

prefer calculus to topology. They each must be assigned two classes. Consider an

assignment mechanism that randomly allows one of them to choose his schedule first,

and then allows the other to choose. Whoever goes first will opt to take the wine

and beer tutorials, leaving the second with the two math classes. Hence, one student

envies the other’s schedule of wine and beer tutorials. This assignment does not

satisfy envy bounded by a single good, since one tutorial alone has a greater utility

than the two math classes together.

On the other hand, if we let students take turns picking individual classes, we end

up with an assignment of the beer tutorial and calculus to one student, say s1 , and

the wine tutorial and topology to the other. Then s2 envies s1 ’s schedule, but in this

case, the envy is bounded by a single good. By eliminating the beer tutorial from

s1 ’s schedule, s2 no longer envies s1 ’s schedule. This squares well with our natural

intuition that the second mechanism is fairer than the first.

This concept appears to be a nice adaptation of envy-freeness to this new domain.

The problem is that the concept makes no sense unless we assume that utilities for

classes and schedules behave nicely, namely that they are additive-separable. But,

as discussed, we believe this assumption on preferences is too strong for the student-

classes assignment problem. Consider a simple example of this; most students at

Lawrence wish to take 3 classes a term in order to meet a credit requirement needed

to graduate. In this case, most students would prefer almost any set of three classes

to any two, so practically any assignment mechanism will satisfy envy bounded by

a single good. We have tried to generalize this concept to our specific domain, but

feel a meaningful criterion is still out of reach. Hence, we omit a fairness criterion.

Fortunately, there is plenty to be said even in the absence of such a criterion.

Uncertainty

We believe that before a student has attended at least one day of each class, they

have some uncertainty about what their schedule preferences are. While this uncer-

8

only by their business or law schools. The most basic auction mechanisms work

in the following way. Students are each given an endowment of some sort of fake

currency, like “points.” The size of the endowment may be uniform for all students,

or a prioritization of students can be reflected in heterogeneous endowments, with

size corresponding to priority. The students then spend points of their endowment

on bids for seats in various classes. Then, by some means, the clearing price for

each class is determined, and all students who submitted a bid for a particular class

greater than the clearing price win a spot in the class. Variations include iterating

the auction procedure. While auctions seem to offer appealing solutions to some

aspects of the assignment problem, they too have a host of unique difficulties.

To get a true sense of the virtues and drawbacks of these various types of mech-

anisms, we need to look at particular cases of each in detail. The University of

Michigan Business School uses an auction mechanism, and the Harvard Business

School uses a clearinghouse. We summarize both, and describe some of the problems

with each. The Lawrence registration mechanism serves as an example of a serial

dictatorship.

2.1

UMBS course-bidding system

Assigning class seats via an auction is a relatively recent phenomenon which first

became popular during the eighties. Today, several universities use some form of a

class auction, including Columbia Business School, Haas School of Business at UC

Berkeley, Kellogg School of Management at Northwestern University, Princeton Uni-

versity, Yale School of Management, Wharton, and of course, University of Michigan

Business School. We outline the UMBS course-bidding system below.

At the beginning of each semester, students are each given an equal endowment

of points B > 0. They then place bids on the various classes, by submitting a bid

vector bs over the entire set of classes. For student s, let bs = (bs1 , bs2 , ...bsn ) denote

∑

his bid vector, where bsc is s’s bid on class c. Naturally,

c∈C bic ⩽ B, though

it wouldn’t make sense for each student not to bid all of their points since the

endowment is worthless except to bid ∑ classes, and saved points don’t carry over

on

10

into later terms. Hence, we expect c∈C bsc = B. Students also make it known

how many classes they are willing to take, and we call this their quota. Similarly,

classes have a quota that indicates how many students may enroll in it. We write qi

to indicate i’s quota.

10

Some auction mechanisms, like the one at Wharton, allow points to be saved. At Wharton,

they even allow the resale of class seats for points (since the auction is iterated there), allowing

shrewd students to increase their pool of points!

10

¨

S¨nmez and Unver review this mechanism in detail in [27]. They find that the

o

system is flawed because the optimal bids may not be those that accurately reflect the

preferences of a participant, yet the mechanism operates from the point of view that

they are. The paper is written largely from the point of view that preferences over

schedules can be inferred from preferences over specific classes. Our paper does not

make such strong assumptions, but for the sake of the following example, we discuss

utility over classes instead of schedules. We demonstrate the difficulty associated

with this bidding mechanism, and why it is subject to strategic manipulation, in the

following example.

Example 2.2. Suppose each student is given an endowment of 1000. Suppose some

student s finds six classes acceptable, intends to take only three of those six, and has

a cardinal utility11 for each class as follows (where the cardinal utilities have been

normalized so they can be expressed as a bid vector).

Table 3: Utility

c1

c2

c3

c4

c5 c6

s

400 250 100 100 100 50

If s is truthful, she will submit exactly this bid vector. S¨nmez and Unver [27]

o

consider the scenario where students have some prior knowledge allowing them to

predict the approximate clearing price of each class. This is an accurate reflection of

reality, since most schools do offer a price history. But in this circumstance, s will

naturally want to alter her bid vector depending on what she expects clearing prices

to be. For instance, if c1 is actually an unpopular class, and typically has a clearing

price around 100, s has no need to bid 400 for it, since she may be confident that a

bid of 200 will ensure her a spot in the class. Similarly, if all the classes s is bidding

on are very popular, it’s possible that none of her bids may be honored. In this case,

she would be well advised to take the points she has spent on c4 , c5 , c6 and distribute

them among c1 , c2 , c3 , in order to avoid spreading her points too thin.

From this it is clear that if students react to expected clearing prices, we cannot

treat bid vectors as dependable indications of true preferences. In fact, despite

implicitly relying on bid vectors as a means of inferring preferences, strategic bidding

11

Cardinal utility is an arbitrary numerical representation of utility that indicates the intensity

of a preference by the relative magnitude of the cardinal utility for a particular good, in addition

to implying a preference order.

12

During the course of writing this paper, we were fortunate that [4] became avail-

able. In [4], Budish considers the virtues and shortcomings of the HBS draft mech-

anism in detail. In particular, Budish finds that the HBS is vulnerable to a specific

strategic manipulation where students “downgrade” classes that are unpopular, by

lowering the rank they are given on the submitted lists. Against a fixed set of rank

order lists, Budish finds that for a particular student, submitting a rank order list

with true preferences is not as good as one where unpopular classes have been down-

graded in most cases.

When a student submits a rank order list with strategic downgrading, it isn’t

clear that the student will not end up forfeiting spots in other classes on their list.

This is because by strategically downgrading, it may be that the student successfully

takes the spot of some other student in a full class. The risk is that this may cause

what Budish refers to as an “overflow chain,” where students keep replacing other

students in full classes, potentially causing some class to fill up that would have

otherwise been open. If the strategic student would rather be in the newly full class,

then strategic downgrading was a bad strategy. Budish shows that there is little risk

of this happening in the HBS mechanism, and that as the market gets large, this

strategy becomes increasingly viable.

To test his hypothesis that students actually engage in strategic downgrading,

Budish collected data about students’ true preferences simply by giving them a

survey. The survey data was then compared with the rank order lists students

submitted to the HBS draft during actual registration. The results were found to

largely support his hypothesis that students engage in this strategic manipulation in

practice. The HBS draft mechanism operates on the assumption that students are

submitting truthful preferences, so this strategic manipulation results in efficiency

loss. This also makes class demand difficult to gauge.

Remarks

In both of these mechanisms, the assignments they produce are efficient in most cases,

if true preferences are submitted. The key problem is that for both mechanisms,

they fail to elicit true preferences from students. They fail this even when the more

convenient assumptions the mechanisms make about students’ preferences are in fact

true. In both cases, this vulnerability has led to problems in the real world, causing

efficiency loss and potentially obstructing the registrar from making good decisions.

We will see that the Lawrence assignment mechanism is also plagued by the same

problems.

14

“Term Registration” takes place during the first two weeks of each term. All

students are given the opportunity to register for classes they wish to take, or are

currently taking, that term. Students are not split up into priority groups for term

registration, allowing all students the ability to register at any time during the two

weeks. After the two weeks have elapsed, students must submit an academic petition

to register for any class that term. During term registration, students alter their

schedules in the following way.

• If a class c is full on the first day, then

– If a student s was enrolled in c, and s attended, s remains enrolled

– If s was on the waiting list and s attended, then s is either enrolled or

remains on the waiting list

– If s was enrolled or on the waiting list, and s did not attend, s is dropped

from c

• If c is not full on the first day, then s can enroll or drop independent of his

attendance

• In general, s may choose to drop any class at any time.

Midway through the fall term, advance registration is offered for the winter and

spring terms of the same academic year. This registration period is also unprioritized,

and lasts two weeks. Midway through the winter term, there is a similar two week

advance registration period, where students can register for classes offered during

the spring term of the same academic year. We find the names of these registration

periods ambiguous, and rename them in the model for clarity’s sake.

Waitlisting, Credit Registration Limit

The waitlisting policy has been recently revised. Previously, if a student attempted

to register for a limited enrollment class that had already been filled, they were

automatically given the option to be added to the bottom of that course’s waiting

list, regardless of the registration period. For the sake of subsequent discussion,

this old procedure is relevant. Now the policy allows students to join a waiting list

for a full class only if that class is offered during the following term. Students are

prioritized on a waiting list in the order they joined the list. Before the beginning

of a term, students are given the option to enroll in classes from the waiting list as

soon as spots become available, in order of priority. If, on the first day of a term, a