Winter Mug

I have now finished my third semester at SNU, which marks my last semester of coursework. In my final semester, I will focus on my thesis research into college admissions markets and continue to help with our lab’s ongoing project on game-theoretic models of urban transit congestion.

I took two courses this semester. The first was graduate microeconomics, with a special focus on engineering applications of economic concepts such as tax design and price discrimination. The latter synergizes nicely with a course I took last winter on revenue management, aka how airlines get away with charging each customer a different price for equivalent seats. We used Hal Varian’s Microeconomic Analysis, a textbook that strikes a nice balance between verbal explanation, mathematical exposition, and numerical examples.

The second course was combinatorial optimization, taught my by advisor, equal parts challenge and reward. The final unit of this class concerned randomized linear programming algorithms for solving hard problems such as the minimum-cost set cover. I had encountered such algorithms in seminar presentations before and assumed that they were simply an effective heuristic for typical problem instances. However, in many cases, we can formally prove (probabilistic) performance guarantees for randomized-rounding algorithms, which marks them as an reliable tool in industrial applications and a promising area of future theoretical research.

I was also involved this semester in the design of an interactive display for self-driving vehicles, a project associated with our department’s Human Interface Systems lab. I created a variety of musical sounds for an experimental interface.

I’ve updated the sidebar with a photo of my winter mug.

Administrative vs. Allocative Efficiency

This fall marks my final semester of coursework, and penultimate semester overall, of the master’s course in industrial engineering here at Seoul National University. I’m taking courses in combinatorial optimization and advanced microeconomics, as well as continuing my study of college admissions markets as a research assistant in the Management Science/Optimization Lab.

Recently, I have been focusing on risk-averse behavior in college applications. In an ideal universe, college applications are completely standardized and there are no constraints on students’ ability to apply to many schools or on schools’ ability to assess a large number of applicants. In reality, many highly qualified students fail to apply to top schools because they doubt their ability to get in or receive a sufficient financial-aid package. For these students, the time and money required to submit an additional application to a so-called reach school takes away from time that could be spent refining an application to a target school. This opportunity cost is not trivial, because modern admissions offices strongly prefer students who tailor their personal statement to the characteristics and interests of the target school or program.

In Korea, such strategic behavior is baked into the college admissions process at the policy level: No student may apply to more than six colleges in a given year, and colleges are allowed to adopt more generous admissions standards for students who list the college as their first choice. A student who wishes to apply to a top university therefore needs more than just confidence in her academic talent; she must also be willing to accept the risk of being rejected and ending up at the bottom of the pile at her second choice.

We know, however, that risk aversion is not homogeneous across the population. Some of the variance is just temperamental: There are people who will continue working at an unsatisfying job because they fear that whatever job they switch to will be even worse, and there are other people who happily take the leap (paywall). But some of the variance in risk aversion is correlated with demographic traits. For example, all other things being equal, women are less likely than men to guess randomly on a hard multiple-choice test like the SAT that penalizes wrong answers (paywall). And we know that kids from low-income backgrounds tend to fail the marshmellow test; perhaps it is not stunted patience, but deliberate, risk-mitigating behavior that makes them favor the sure bet.

In college admissions, administrative efficiency requires any practical admissions procedure to put up some minimal barriers to application; otherwise, truly underqualified students will spam top universities with vain applications, wasting everyone’s time. However, if the application barriers are too high, they may force marginally admissible students—that is, qualified students—to engage in strategic behavior that does not reflect their actual preferences or abilities. A highly qualified, risk-averse student may list her second choice as her first, or neglect to apply early decision to her dream school (early decision increases admissions likelihood but arguably entails financial risk). And as a result, a less qualified but more cocksure student can step into her place.

The scenario above—which, to be clear, is speculative—suggests that market features designed to produce administrative efficiency, like requiring students to express a specific interest in their target school or indicate whether the school is their top pick, trade off with allocative efficiency in the composition of top universities’ entering classes. Moreover, if the psychological findings above on risk-averse decisionmaking also hold with respect to applicant behavior, then it is possible that the social cost falls most heavily on precisely the marginal groups whom we are trying hardest to recruit.

JuliaCon Presentation

In a poster presentation at JuliaCon last month, I introduced DeferredAcceptance, a Julia package I created that solves both discrete and nonatomic school-choice problems using a variety of modern algorithms.

College Scorecard API Tutorial

Many researchers studying American higher education want to work with the College Scorecard dataset, which was created under the Obama administration and contains detailed information about college quality, affordability, and student outcomes.

It is possible to download the entire dataset, but the file is large and difficult to navigate, and for most researchers, a more efficient strategy is to learn how to query the database for just the data that you are interested in.

In the video below, I explain how to use Python to submit an API query to the server that hosts the College Scorecard data, and show how to convert the JSON output into a Pandas dataframe or Excel spreadsheet. I also demonstrate a few data analysis and visualization tasks.

The video assumes a very basic understanding of Python.

A New Notion of Equilibrium

My previous posts about admissions markets have considered a notion of equilibrium called market clearing or Walrasian equilibrium. This means that each school picks a target number of students to recruit, and adjust its admissions standards until the number of enrollees equals the target. Deferred acceptance mechanisms, which are used in public school districts like Boston and New York City to assign students to middle and high schools, are essentially algorithms for the Walrasian equilibrium. I expand this argument in “Characterizing Nonatomic Admissions Markets,” a preprint I posted on arXiv last week, and develop a parametric market that enables easy computation of market-clearing score cutoffs from school preferability parameters and vice-versa.

However, in college admissions markets, schools care about not just the size of the entering class, but also how qualified the students are. Characterizing a college’s preference of one entering class relative to another is a difficult problem. For one thing, while it is somewhat reasonable to assume that schools can make a partial ordinal ranking of their applicants (student A is better than student B), the ranking is typically not cardinal (student A is twice as good as student B). For another, even if we have a cardinal ranking, it is unclear how utility aggregates across students. If student A is twice as good as student B, then is recruiting student A equivalent to recruiting two students like B?

Nonetheless, colleges must have preferences over sets of students, because there are many liberal-arts colleges that desperately need tuition dollars, but still reject some applicants. This behavior can only be explained if adding the underqualified students to the entering class would compromise its overall quality. In turn, this suggests rather than Walrasian equilibrium, a more realistic notion of equilibrium for decentralized admissions markets is the Nash equilibrium. The Nash equilibrium means that each school has tuned its admissions standards such that changing them could only yield lower utility according to some utility function that rates the quality of the entering class. Finding the Nash equilibrium can be difficult, because each school can control only its own actions, but its utility depends on the collective actions of all the schools in the market.

Recently, I have been experimenting with modeling each school’s utility as a linear combination of the log of the size of the entering class and the log of the percentile score of its least-qualified student. We can find some interesting computational results by applying this utility function to the parametric market developed in the arXiv paper.

For example, when the number of colleges in the market is large, their utility functions approach concavity, and we can expect the market to reach a Nash equilibrium in schools’ admissions standards under light assumptions on its dynamics. However, when there are just a few schools, then the utility functions are neither concave nor necessarily unimodal. Instead, they take the cloudlike shape shown in gold in the figure below. In this animation, each school follows the gradient of its utility function to update its cutoff at each iteration, and the market converges to a local equilibrium. School 2, in the top right, could achieve higher overall utility by reducing its cutoff to around 0.17, but it never gets that far.

By picking a different update rule, such as having each school update its cutoff to its global “best response” at each iteration, the market may cycle or behave chaotically instead of converging.

An Economic View of the Korean College Admissions Market

Existing computational models of admissions markets tend to fall at one of two extremes: Either they envision a centralized admissions process in which the school board runs an algorithm that says which students go where, or a decentralized process in which colleges compete for the best students. But the Korean college admissions process cannot be adequately described in either of these terms.

The Korean admissions process is decentralized in the sense that students ultimately can choose which college to attend from the subset to which they are admitted. However, the application procedure is facilitated by the government, which enforces a limit on how many schools each student can apply to (currently six) and requires a certain distribution of applications across three tiers of selectivity. This means that the Ivy League sweep is theoretically impossible in Korea.

In addition, the government assigns each college a quota, meaning the maximum number of students it can “recruit” in each academic major. In smaller universities, the quota for a given program may be as small as a single-digit number. To ensure that no college exceeds its quota, students are admitted over the course of several rounds of acceptances, with different scoring criteria and cutoffs in each round. Because colleges are not allowed to use empty seats in one major to admit extra students in another, this creates endless possibilities for strategic application. As an applicant, if you can identify an underdemanded program at your target school, you will be guaranteed admission in the final round as long as you meet the minimum application requirements.

And, as many have probably heard, a signature feature of the Korean admissions process is a big test called the Seneung or CSAT. Whereas American universities have begun to discount standardized test scores, a typical Korean university determines about 80 percent of applicants’ composite score using the Suneung; the remainder comes from high school grades, an interview, and/or an admissions test specific to the program the student is applying to. It is from this weighted average that the college defines its final ordering of the applicants and sets its score cutoff. As a result, students’ admissions probabilities are highly correlated across universities.

The argument for this design is twofold: First, it is cost-efficient, because it caps the total number of applications and therefore reduces the number of applications that each college has to read. (However, we ought to question the amount of reading actually involved, since very few universities require anything as textually substantial as the American “college essay.”) Second, it is fair in the sense that it evaluates all students on the same, quantitative metrics.

The most obvious and common argument against the semicentralized admissions procedure used in Korea is that it is actually unfair, because evaluating students in approximately the same way at every college means that winners take all. A student with low test scores but a high degree of motivation does not have the chance to prove herself by actually taking college courses alongside high-achieving peers. You have to get smart by the end of high school, or it’s game over. A related argument says that the Suneung is unfair because wealthy students receive private tutoring in order to increase their score. However, I find these arguments to mistargeted, because (to my knowledge) the high priority colleges give to the Seneung in their admissions decisions is not mandated by the government. In theory, if a college wants to admit students purely on the basis of high school grades or tennis ability, it can, but colleges stick to the Suneung because they like it. It’s a legible (if unreliable) indicator of academic ability, it avoids the appearance of corruptibility, and it’s easy for the college to track year over year as it tweaks its admissions standards in response to market conditions.

However, even if we set aside the Suneung and the attendant debate about fairness, I argue that the Korean admissions process is economically inefficient because of the limits it imposes on students’ application strategies. If an outstanding student from a rural area knows that she can only apply to two schools ranked within the top fifty, she may be inclined to hedge her bets by applying to schools ranked in the thirties and forties rather than wasting an application on (what Americans would call) a “reach” school in the top ten. Because of situations like this, in any admissions process that circumscribes students’ ability to consider a broad range of colleges produces, the outcome is highly sensitive to students’ ability to intuit their rank in the broader distribution of academic talent.

I hypothesize that students who don’t have role models who attended top universities will tend to adopt a minimax strategy, and end up attending a university that’s worse than where they could theoretically get in under an efficient allocation. On the other hand, students who have the financial means to take a gap year can afford to apply to reach schools, and reapply to a more conservative set of schools next year if they don’t get in. With the right computational model, we can attach numbers to these hypotheses; for example, if the number of allowed applications increases from six to seven, we can try to predict the change in the number of students who decide to take a gap year.

Why study the Korean college admissions market from an economic perspective? Anyone familiar with the computational models typically used to study admissions markets should have raised an eyebrow at the monolithic notion of better and worse schools implied by the previous two paragraphs. In fact, the very thing that makes the classical school-choice problem interesting is the possibility that students have diverse preferences (based on individual variations in geography, academic interest, family alumni, and so on). Thus, in the canonical problem, there is not necessarily a global ordering of better and worse schools. Nor is there a global ordering of students, like the one that arises when all universities grade students based on standardized test scores. Korea is exceptional on both of these points. Most schools rank students in a similar way, and because of the high degree of vertical differentiation, most students have a similar preference order over the 300ish universities in the market.

Loosely speaking, when the preference orders are more or less random, the set of possible stable assignments is relatively large, and we can start to “play” with other distributional goals, like trying to obtain gender parity at each university while preserving overall stability. This is what a lot of current papers in stable assignment are doing now. However, in a stylized Korean admissions market in which most students have a similar preference order over the schools and all schools assess students in the same way, there is only one stable assignment (as I can show mathematically). Although we don’t get to play with distributional goals, because the stable assignment is unique, we can examine it in greater detail, and compute comparative statics such as the marginal effect of a change in student population on the selectivity of each university.

Another reason to take a closer look at correlated admissions procedures like the one used in Korea is that such market designs are common around the world, not just in Asia, but also in many European countries and in local school-choice markets in places like New York City. It’s cool, if you know how to program, that we have a simple algorithm for computing stable assignments in arbitrary discrete admissions markets given lists of student and school preferences. But by narrowing our focus to the case of correlated admissions, we can make more ambitious quantitative predictions about the long-run behavior of the market, including, hopefully, computing the efficiency cost of admissions quotas and limits on the number of applications each student has.

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.