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.

The Optimal Stable Marriage

A one-to-one assignment problem involves a set of two groups, candidates and reviewers, each of whom has ranked the members of the other group on the basis of how much they would like to be paired together. A classic problem in game theory involves finding a stable assignment, or a way of pairing up candidates and reviewers such that no member of either group is incentivized to cheat on their partner. In a large problem, there may be more than one way to do this, but it isn’t necessarily easy to find all of the stable assignments or determine which one represents the best compromise between the candidates’ and reviewers’ interests. I have written some code that solves this latter problem. The algorithm it uses was developed in the 1980s, and I am currently working on improving its performance and extending it to many-to-one assignment problems. My code and further discussion are on Github here.

Three Creations

Python implementations of a two-phase simplex method and sparse LU matrix factorization.

An article about Korean SF in the Emory Journal of Asian Studies.

And an EP:

Day Seven of Fourteen

I’m trying to make everything last. But I already ate the chocolate. I had promised it to myself as a reward for getting halfway through isolation halfway intact, and I kept that promise this afternoon, most of the way between lunch and dinner. Otherwise, I’ve been spending most of my time on math, learning as many math words as I can in Korean and getting comfortable with the concepts I’ll need in my research group. I coded a simplex method.

One of the staff at the quarantine facility gave me his contact info and said we should stay in touch. I have my first friend, then, at SNU, and you could do some Bayesian stuff to argue it won’t be long before I have a couple others. This has me in high spirits. That, and that they are feeding us well.

It occurs to me that there will be a day at the end of this when I look back and say, I can’t believe how fast it went. Certainly it was like that with my time in Naju. I can still recall, if I look far enough inward, the feeling of my bed in my apartment by the river, the way the trees framed the window, the awkward hop between the bedroom and the shower … but I can also feel the memory fading, already, as irretrievable as every other mundane sensation.


They say that we perceive time by the accumulation of novel experiences, so that if you want to have a subjectively long life, you ought to do many spontaneous and hard-to-repeat things, but if you want to have a happy life, you ought to find one or two high pleasures that you can enjoy on a spiritual level and repeat the hell out of them, because they also say that on average, people derive more happiness from repeating a good experience than from trying something new.

You could write a linear program that targets your ideal mix of longevity and happiness and it would tell you exactly how many times to do this or that activity before moving onto something new. But what this calculus leaves out is the feelings of uncertainty that stain the transitions.

I am leaving Naju, after having grown accustomed to this routine, this commute, these faces, and I cannot say with any confidence that I have reached a joy plateau. Every week of teaching here has been better than the last: my skills have improved, my confidence has grown, and the teachers and students have become only more important to me. I could be happy like this for a long time. But.

But too much comfort has a way of smearing all the time together, so that the things that take place in a given day feel less like events and more like footnote references to proto-events hovering in the firmament of the distant past. I have already seen the river clog itself with duckweed; I have already looked down the street from all four of the intersection’s corners, trying to make the buildings line up with the trees. Upon inspection, a more sensitive man might look at these rhododendrons and see something more than last year’s blossoms in a different configuration, but I am a pattern-matcher by nature, too easily bored to remain a recluse. It is time for a new challenge.

As I wrap up my Fulbright grant, I am delighted to share that I have been accepted into the Government of Korea Scholarship program, through which I will be returning to Korea in the fall to pursue a fully funded master’s degree in industrial engineering at Seoul National University.

Thank you to all who have encouraged me.

A Parametric Curve Utility in Python

To run certain kinds of simulations, we need to generate random points that are evenly distributed along a certain curve (say, a circle) or over a surface (like a cube). If you have a formula for the length of the curve or the surface area, you can work backwards to find a procedure for generating the random points. But there are many mathematical curves, like ellipses, whose perimeter cannot be expressed using a formula. Instead, it must be computed numerically, by picking a large number of points along the curve and adding up the distance between them. The same applies to the surface area of many surfaces in three dimensions.

I have recently published param_tools, a small Python module that performs these numerical computations for a given curve or surface and generates random data in the desired region. The curve or surface can be given in either parametric coordinates or as a set of ordered points. And instead of generating random data, it can also map uniformly-spaced data or data from an arbitrary probability distribution to a specified curve.

This is the first standalone module I have posted to Github, so I welcome feedback on the implementation and documentation.

And here are some puppies who followed my students to school this week:

The Benefits of a Nonnative Teacher

In addition to the myth that it’s impossible for adults to “really” learn a foreign language, a widely held misconception about language learning is the notion that beginners must learn from native speakers. Many are willing to allow that a nonnative English speaker could make as good a teacher as a native speaker, but fewer recognize the pedagogical advantages offered by someone who has learned the target language as an adult and can understand what it looks like from the student’s perspective.

In the ELL classroom, we often encounter questions like: Why is it correct to say I am going to school but wrong to say I am going to home? A native speaker has to think about this: Is there a reason we drop the to before home, maybe something to do with the fact that you can attend, in theory, multiple schools but can have only one true home? Or is it because it just “sounds better”? Or maybe it’s just a random exception, but then, which one is the exception and which one is the rule?

Someone who learned English as an adult can tell you immediately that I am going home is a random exception, and that to is the rule when you are going to a specific, named place. The only reason I, a native English speaker, know this is that a similar exception exists in German: Ich bin zu Hause. When I asked my German teacher (a nonnative English speaker) about that sentence, she asked, rhetorically, “Why is it correct to say I am going to school but wrong to say I am going to home?”—having learned this very thing in school.

With some effort, you can generate sentence pairs that demonstrate the opposite case, where a native speaker feels inclined to call the difference a random exception when in fact there’s a grammatical rule in play. Here’s a test question that I’ve encountered in various forms:

I think dogs are awesome. I think cats are OK. Circle all correct sentences:

  1. I like dogs more than cats.
  2. I like dogs better than cats.
  3. I like more dogs than cats.
  4. I like cats less than dogs.
  5. I like cats fewer than dogs.

The answer is choices B and D. Most native speakers see nothing wrong with A, because it’s something that we actually do say, but according to a strict interpretation of the rules of English grammar, A is wrong for the same reason that C and E are wrong: more is for comparing quantities of things, but like expresses a binary preference. By an even stricter interpretation of the rules, you can argue that choice D should have worse instead of less, but the prescriptivists who write Korean standardized tests of English grammar have moved past that archaism even as they’ve resisted allowing choice A.

Native English speakers who teach in Korea are often given test questions like these, along with the answer key, and asked to explain the correct choice. Because the answer key disagrees with our intuition, we tend to grasp for an explanation and fail. On the other hand, a Korean teacher can reference the textbook page that discusses more than and better than and be done with it.

You might argue that memorizing these kinds of formalisms falls short of actual language acquisition, and you would be correct—language learners need also to engage with authentic texts and audio, experiment with the target language in roleplay scenarios, and practice speaking freely without worrying about errors. But teaching the more than/better than distinction, even if the student will eventually discard that rule as they encounter English in the wild, is useful because it primes the student’s awareness of the different kinds of comparisons available in the language.

Consider: You can allow choice A in the above question, but then students will ask why its parallel, choice E, is wrong, and you’ll teach them the fewer than/less than distinction, but then you’ll have to explain why there isn’t a more than/better than distinction as well. Yuck! It’s better (more?) to avail beginners of a consistent set of principles that mostly work, while maintaining a mental inventory of exceptions, and exceptions to the exceptions, in case a smart kid asks a good question.

Most native teachers long to do away with multiple-choice questions like the above. At best, they make for interesting illustrations of how English grammar is a moving target and there’s no universal set of rules obeyed by all English speakers everywhere forever. At worst, they make for frustrating illustrations of how English grammar is a moving target and there’s no universal set of rules obeyed by all English speakers everywhere forever. A nonnative speaker, who can detach herself from personal feelings about what constitutes “natural” English, can distinguish between language usage and test-taking strategy. A savvy test-taker, confronted with the above question, doesn’t have to know whether I like dogs more than cats is admissible in Korean Standard English; she merely recognizes that this question is “about” the more than/better than distinction and eliminates choice A because standardized examinations test rules, not exceptions.

Now, native speakers can learn to speak abstractly about grammar like nonnative speakers do, but it’s an acquired skill, just like algebra. While it’s theoretically possible for a native speaker to deduce the rules of his language’s grammar from first principles, a speaker who learned the language as an adult learned those rules at the same time, whereas native teachers like me have to scramble through Google to find answers or make up rules that seem right at first but collapse upon inspection.

I have learned a great deal of Korean from native speakers, but my foundation in the Korean language was established in a class at the UW taught by an American. After that, I had Korean professors and TAs who had invested considerable time in learning to speak about Korean, and they understood the utility of abstract grammar because they had relied on it themselves in learning English. To the extent that I’m good at Korean now, I attribute my success more to the many opportunities I’ve had to carefully examine Korean grammar and etymology than to my friendships with native speakers. That part’s just fun.