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.

Accidental Signals

It is a well-known result in psychology that measures of intelligence correlate across domains. If you are good at math, you are probably also good at verbal reasoning, and vice versa. Therefore, if a company is hiring for a position that requires a variety of skills (as most jobs do), it should pick a candidate who has demonstrated impressive skill in one domain over someone who has demonstrated middling proficiency in a number of different domains.*

Hiring managers’ preference for specialists is widely known. So, smart people, who tend to be good at estimating job-market incentives (thanks to the correlation between domains of intelligence), gravitate toward programs that award narrow, in-demand credentials—even when the credentials are nominally equivalent (a BA in linguistics vs. a BA in English). This can create a feedback loop in which fields that are perceived as “challenging,” like computer science, attract challenge-seeking entrants, raising the standards of proficiency within the field and making it more difficult for a newcomer to rise above average. On the other hand, majors that are perceived as relatively easy, like sociology, may attract less-ambitious students, leading to deflated expectations and dissuading hard workers. (I have met a few people who told me that they majored in the liberal arts because they were “bad at math.” I have never met a STEM major who chose their field because they were “bad at writing.”)

(National Center for Education Statistics, Undergraduate Degree Fields)

Nothing in this argument depends on the skills actually conferred by a given degree program or the skills actually required by an employer. A tech company needs managers and product designers just as much as it needs engineers, but positions in management and product design are typically reserved as rewards for distinguished engineers rather than handed out to people who majored in management or design. This is because a coder’s science degree(s), plus a few years of demonstrated commitment to the company, signals greater potential for success in the new role than some stranger’s design credential, which may relate more to the job but is also easier to obtain.

The problem comes when we confuse these signals of potential with the thing itself. To depart from credentials for a moment, one such signal is “grit” (tenacity, work ethic, passion), which Angela Duckworth argues is the best predictor of career success. This conclusion is obvious if taken as a prescription for moneymaking. But the book (Grit: The Power of Passion and Perseverance, 2016) becomes more interesting if we read it as a diagnosis: an attempt to organize American capitalism’s scattered, ever-changing incentives under a handy label. It is this explanatory power that makes grit conceptually coherent. Successful people come from a range of economic and educational backgrounds, but what they all have in common is—see book title.

However, grit’s conceptual strength comes at the cost of moral clarity. In a later chapter, Duckworth begins to caution that grit is morally neutral: good and bad people (she mentions Hitler) alike can be possessed of grit, so we should not regard someone as morally virtuous just because they are gritty. This is correct, but Duckworth fails to take the further step of disclaiming the converse: she assumes that moral people will see value in grit and pursue it for its own sake. On the contrary, we (moral people, presumably) ought to question the value of grit, because the positive traits by which Duckworth defines it can be easily reframed as negatives: Where does tenacity end and stubbornness begin? What about work ethic and workaholism, or passion and temper? We can think of a few geniuses whose “passion” had disastrous consequences for their personal and professional lives.

While you may cultivate success through grit (and leverage your success for moral good), will you, in your power, recognize the worth of someone who is highly intelligent and hardworking but has not developed grit as a signal of this potential? Under a different incentive structure—an unstable family environment, for example—an effective learner might develop, in place of tenacity, the ability to recognize a losing battle; in place of discipline, flexibility; in place of passion, consideration of communal needs. These latter traits are not incompatible with grit’s essence, but they may interfere with grit’s signal when it is measured by prompts like, “I finish whatever I begin” (to which the respondent answers on a scale from “not like me at all” to “very much like me”). Grit is an abstract concept that attempts to unify many disjoint values under one label. It may reliably indicate career potential—it may even be the most reliable such indicator available—but it does so only “by accident”: it signals the presence of a collection of traits that employers value, not the merit that undergirds the traits themselves.

So it goes with credentials. Achieving a high level of expertise in any field is hard. But the accidental arrangement of the job market at a particular moment in time has stiffened competition in some fields and weakened it in others. Today, it is relatively easy to parlay a STEM degree into a number of careers. That is not because everyone “needs” to know differential equations, but because knowing that someone passed a differential equations (MATH 235) tells us more about their overall intelligence than knowing that they can speak intermediate French (FREN 235). A STEM degree is a proximate signal of being good at following directions, which is in turn a proximate signal of career success.

Ideally, employers, grad schools, and other such gatekeepers would shun such imperfect signals. Instead, they ought to evaluate each candidate on an individual basis, combing through their background in search of desirable traits. But this is cost-intensive, so gatekeepers bet on the reliability of cheap signals like credentials and test scores instead. They do not work perfectly, but they work well enough, most of the time.

* You may have heard that the instruments we use to measure “intelligence” are biased toward people from dominant cultural backgrounds and people of financial means. This is a good argument against the use of standardized testing in college admissions, but it does not contradict the claim that I am using here, namely, that intelligence between domains (and within an individual) is correlated.