Reverse Optimization and Admissions Markets

The hot topic in lab nowadays is reverse optimization. In normal optimization, we are given information about a system and try to figure out which inputs will make it do its thing at the lowest cost (or highest profit). In reverse optimization, we are given the inputs that we know produce optimal behavior, and we try to figure out the mechanics of the system.

If the system is a market and the optimal inputs are the quantities of supply and demand at equilibrium, then we can use reverse optimization to figure out the fundamental parameters of the market: How much value do people ascribe to each commodity? This is called econometrics.

Here are a few proof-of-concept examples of reverse optimization I have developed for the admissions market I am modeling. The first example concerns student preferences. Given information about the demand (entering class size) for each school and its admissions standards, I show how to derive the probability weight or preferability given to each university when it enters a student’s choice set. This exercise uses real data on SAT scores and admissions rates from a somewhat arbitrary set of 98 universities.

In general, the schools that top the list are popular overall. But it’s surprising to see that, for example, UW Madison has a higher preferability rating than Princeton, which means (by the definition of the preference parameters) that a student admitted to both schools is slightly more likely to choose UW Madison.

This is an artifact of the design of the model, which considers only SAT math scores. UW Madison has unusually high math scores. Perhaps this is because most UW Madison applicants take the ACT (which is more popular in the Midwest) rather than the SAT; hence, the subset of admits who submitted the SAT are out-of-state students who are atypically zealous about their college search.

But for the sake of argument, let’s take the results at face value and try to understand the economic relationship between cutoffs, demand, and what I am calling “true yield.” In the model, Princeton’s cutoff is 0.94, which means 6 percent or 5766 of the 96094 students in the market are able to get into Princeton. The number who chose to attend is 1285, for a true yield of 22 percent.

On the other hand, UW Madison’s cutoff is 0.81, so 19 percent of students can get into UW Madison, and of them 6279 choose to attend, for a true yield of 34 percent.

The inevitable conclusion, according to these results, is that UW Madison is more preferable overall. Consider it this way: UW Madison enrolls five times as many students as Princeton. And every student who is qualified for Princeton is also qualified for UW Madison. So, if every student who got into both schools chose Princeton, then UW Madison would have to admit six times as many students as Princeton to achieve this level of enrollment. But in reality, UW Madison admits about three times as many students as Princeton. This can only be explained by the fact that some (in fact, a plurality of) students who get into both schools choose UW Madison—again, according to this very limited model.

Clearly, it’s painfully unrealistic to suggest that all colleges have the same ranking of their applicants, let alone that all colleges perform this ranking using the SAT math score. So in a separate example, I consider how to express schools’ diverse (but positively correlated) preferences over the set of students. This is also a case of reverse optimization. Given real admissions outcomes for individual students at a certain university, I show how to extract the optimal weighting used in the college’s assessment function. The assessment function has a special form that is both compact enough to enable reverse optimization, and robust enough to express a range of school preferences, including schools’ desire to admit well-rounded students with a combination of strengths.

As you may have guessed, one of the things I’m working on now is a way put these two models together.

Nonlinear Dynamics in College Admissions

Even under the fairly restrictive market restrictions given in my previous post, we can generate instances of school-choice markets that exhibit chaotic dynamics. Here is an example. I let tâtonnement process run for 8000 iterations and plotted the final 7000 cutoffs. The blue and red points indicate even and odd iterations; the behavior is bounded and quasiperiodic but has no obvious symmetry. Here is the code.

Dynamic Admissions Markets

School-choice markets are like any economic market in that they are characterized by prices (score cutoffs), supply constraints (school capacity), and consumer demand (student interest). In general, a t√Ętonnement or price-adjustment process converges quite well for school-choice markets when students’ preferences follow a multinomial logit choice model and their scores at each school are independent or positively correlated.

A unique challenge in school-choice is how to model the preferences of schools over students and vice-versa. In this example, I use a standard model for student preferences known as the multinomial logit choice model. To express the fact that student preferability is imperfectly correlated between schools, I assume schools score students using a convex combination of orthogonal dimensions of student quality. For example, each student may have a language score and a math score, and the school’s decision is how much weight to place on each of these and what minimum score it should require for admission.

(In reality, if the language and math scores correlate, we can use principle component analysis to extract the orthogonal components of the score vector, so the only loss of generality here is that we have limited the score dimensions to two. The number of dimensions used can be increased, but at considerable computation cost.)

The first pane of the animation visualizes the possible sets of admitted schools and associated probabilities. A student who scores high on both tests will be admitted to both schools, while one who scores high on the math test but low on the language test may only get into the Antarctic Institute of Technology, and so on. Each school starts out with a random score cutoff and adjusts it over time to make the number of students who enroll agree with its capacity—when this occurs, we say the market is in equilibrium.

At equilibrium, the total percentage of students who receive no admissions offers (the white area of the graph) must equal 0.4, which is one minus the sum of the schools’ capacities (expressed as a fraction of the number of students).

The second pane shows the motion of the cutoff and demand vector over time. The gray pointers indicate the excess demand at those cutoffs; this graph thus shows that the equilibrium is stable, because all the integral curves lead to it. I configured the step parameter in this example so that it converges to the equilibrium gradually, but with better parameters we can use the t√Ętonnement process to find the equilibrium quite quickly, even in large markets with more schools and tests.

You can find this example in self-contained form here on GitHub. A collection of equilibrium-finding algorithms is part of my DeferredAcceptance Julia package.

Stable Matching on Planet Money

Planet Money, an NPR show about economics, recently ran an episode entitled “The Marriage Pact” that deals precisely with my research topic. It’s a great episode that discusses both the basic ideas behind stable assignment as well as its applications in organ donation, job placement, and (my area of focus) school choice.

The episode begins with an interview with a Stanford econ student who designed a marriage market for his peers and managed to get 4111 of them to sign up for it. What a cool project! The student makes a few minor misstatements about the Gale–Shapley proposal algorithm that Planet Money leaves uncorrected. In this post, I want to offer a few corrections, not just because I can, but because in my opinion these marginal details are what make stable assignment an interesting and profitable research topic.

The interviewee says that because the proposal algorithm produces a stable matching, it is guaranteed to provide participants with their “best” match. But it turns out that even when the participants in the proposal algorithm have strict preferences, there can actually be more than one set of stable matchings, and which stable matching you get depends on which form of the algorithm you use.

If you run the algorithm in the male-proposing form, you get a match that is simultaneously male-optimal and female-pessimal. This means that among all of the women Fido could be stably matched with, the male-proposing algorithm is guaranteed to pair Fido with his first choice, and to pair Fido’s mate with the male she likes least among the males she could stably match with.

Likewise, if you run the algorithm in the female-proposing form, you get a match that is female-optimal and male-pessimal.

In the episode, the hosts mention that the algorithm provides the participants with no incentive to lie about their preference order (notwithstanding misrepresenting basic facts about themselves like height). But an important corollary of the result above is that the male-proposing algorithm is actually not strategy-proof for the female participants—by lying, they may end up with a male better than their worst match.

I don’t know how the Stanford match works, but it’s likely that (for the straight participants) they used an extension of the Gale–Shapley algorithm developed in the 1980s that finds the “male–female optimal stable match”—a sort of compromise between the male- and female-proposing forms. This extended algorithm, while egalitarian, isn’t strategy proof for either group of participants, precisely because it gives both groups a slightly suboptimal match.

The good news it that in the one-to-one matching case with strict preferences, the differences between the male- and female-optimal matches are quite minimal (usually just a shuffling a few pairs around at the edges, if any), and the “strategy” you need to use to beat the market is not at all obvious.

But when we relax the assumption of strict preferences and start to work with many-to-one matching, as is the case in school choice, the set of stable matches becomes very large, and coming up with a good way to maximize participants’ outcomes while maintaining incentive compatibility is an interesting challenge. The dominant contenders in this space are randomized “tiebreaking” (lottery) mechanisms, including those used in school markets in New York, Boston, and elsewhere. I’ve run a bunch of computational experiments on these mechanisms, and you can see some fun graphs on the Github page for my Julia package DeferredAcceptance.

(I sent a version of this to the Planet Money team, but I’m not betting on a response.)

Slides and Registration

I”ve gotten little bit ahead of myself on my seminar slides, so here is a compilation of what I have created so far. For the most part, they should stand on their own, but some degree of familiarity with the Gale–Shapley assignment process wouldn’t hurt (it isn’t hard to grasp).

My DeferredAcceptance package, now at version 0.3.1, was also accepted into the general Julia package registry.

Winter Quarter Update

I have greatly expanded the functionality of DeferredAcceptance, my school-choice code library. New features include the nonatomic form of the DA algorithm, several new tiebreaking mechanisms, and further replications of recent experimental results from the literature on stable assignments. A couple of interesting research results of the past ten years include a tiebreaking mechanism that lets students name a “target school” where they will receive enhanced admissions priority, and a two-round dynamic reassignment mechanism that uses the spaced freed up by students who leave the market (e.g. to attend private school) to compensate for inequality in the primary assignment round.

I also coded a practice implementation of an interior-point method for solving linear programs. During winter break, our lab has been working through Jorge Nocedal and Stephen Wright’s Numerical Optimization textbook, and the section I was responsible for included the predictor-corrector algorithm given above.

During winter quarter, I completed a course in revenue management and pricing. For my final presentation in that class, I reviewed a paper that concerns which products should be presented to a customer in order to maximize revenue (assortment optimization):

One rewarding aspect of this class was the exposure to a wide range of models in choice theory, which allows us to express mathematically the processes consumers use when deciding which product to buy. So far, in my research in school choice, I have focused on the assignment aspect of the problem, which takes place after students’ preferences are revealed. But robust simulation of school-choice markets requires effective modeling of uncertainty and information asymmetry on the demand side.

First Steps in School Choice

Do you know what algorithm your district uses to assign students to public schools? A fair school-choice process is an essential part of a functioning democracy, and determining the “best” algorithm involves carefully weighing tradeoffs between student welfare, equity, and distributional goals like gender equality and racial diversity. Such considerations are the basis for my thesis research in the Management Science/Optimization lab here at SNU.

I coded a few commonly used algorithms in Julia, and this week I've been running computer simulations to reproduce a few well-known results in this area of the literature. Check out my implementation and a brief discussion on Github.