« A Poem | Main | 900 miles from my home »

March 20, 2005


When deciding on your career, reflect on this: An analogous situation holds for departments that are deciding who to offer jobs, without the "April 15" part.

Med schools, I understand, have a system in which graduating students and teaching hospitals submit their preferences to a central computer, which decides who shall go where. I don't know how popular this is. Philosophy seems disinclined to adopt something similar at any level.

I think this problem (suitable recast as a decision problem) is NP-complete, actually (though considering the small numbers likely involved, that probably wouldn't be much of a constraint on processing time).

A wrinkle is that the person I was talking to maintained that, since the balance of an entering class is a factor in admissions, there isn't a strict rank on the wait list, so depending on who decides not to attend different people can get lifted off it. I wouldn't be surprised at all to learn that that's just a CYA procedure.

I know nothing of the actual deliberations, but that actually makes sense. You wouldn't want to admit five people with expressed interests in subfield X if you wouldn't be able to get them all advisors.

In my (not philosophy) admissions experience, waitlisted people don't often wait until the 15th to hear from the schools that may or may not accept them. They simply choose to go elsewhere and make the commitment before the 15th.

So when a school starts calling people on the waitlist on the 15th it can end up getting no one. In a particularly bad recruiting year, this can mean a very small cohort for the department.

A student of mine, caught in a similar situation, was trying to negotiate for more support with one program (her first choice) *and* get them to give her more time to decide, because if they couldn't come up with enough funding, she was going to have to go to choice #2, which hadn't notifed her yet.

At one point, she said to choice #1 that she couldn't accept them without more funding--which she saw as a negotiating tactic--and they said, ok, well, we're sorry you won't be coming and hung up the phone. She was stunned.

Luckily choice #2 did accept her, but it's a pity.

Yes, it does seem that "tough negotiation skills" can only take you so far in a situation in which you have virtually no power.

I don't recall being properly credited for your title, Mr. Wolfson.

Don't be such a hardass, Kotsko. The vagaries of your memory are none of my concern!

Nah, it isn't even like that. The waitlist schools just send you an e-mail. Eventually.

FWIW. The Brits used to have something called U.C.C.A (University Central Clearing for Admissions). While it was designed as a mass clearing system for undergrad applications to ALL universities and all courses, the room for manoeuvre was embedded in the rules. One applied for 5 programmes, could be rejected, provisionally offered or offered a place and could then reject, provisionally accept or accept the offers. The provisonals were obviously time dependent but it still made for good fun. As good an auctioning system as any I ve seen.

This isn't NP-complete. It's nowhere near NP-complete. It is quantum, however, as a qubit armed with the ability to make either decision could probably solve it. What this really is, however, it is a circular wait deadlock. A is waiting for B who is waiting for C who is in turn waiting for A. But it's not NP-complete. It's part of the deadlock conditions. But I have a feeling it doesn't take place on such a small scale, and so the deadlock isn't as serious as you think it may be (although it could be).

You philosophophiles may be more used to it as this.

NP-complete would be more like having a philosopher have to find a hamiltonian cycle from of all the walking paths at the school in order to gain acceptance.

I am tweedledopey, killer of comments.

Ok. I thought I had read somewhere that finding an optimal allocation of resources among people who rank their values differently is NP. I'm not sure why I then proceeded to think it's also NP-complete, but whatever.

NP-complete would be more like having a philosopher have to find a hamiltonian cycle from of all the walking paths at the school in order to gain acceptance.

That's not a decision problem!

I was going to remark that tweedle has it wrong, and then I realized that tweedle might have it right. Suppose you have a circular waitlist:

North Dakota-Hoople has accepted Chris and waitlisted Sam
New Mexico-Dead Lizard has accepted Sam and waitlisted Terry
Western Nebraska-North Platte has accepted Terry and waitlisted Chris
Chris prefers WN-NP to ND-H
Sam prefers ND-H to NM-DL
Terry prefers NM-DL to WN-NP

If one of the students turns down one of the schools, then each student gets accepted off the waitlist, and gets their first choice. But as the system stands, probably no one will turn down their schools, and every student will wind up with their second choice.

This also shows that in a way it's impossible to optimize outcomes in certain situations. The students get their first choice iff the schools get their second choice, and vice versa. Probably someone's proved an impossibility theorem about this.

Why did I reproduce the exact example Wolfson gave, except with funny school names? Because philosophy grad school SUCKS YOUR BRAINS OUT.

I should say that I did not mean to cast aspersions on universities with similar names to the ones I gave. I did mean to cast aspersions on the town of North Platte, NE.

I realize that Hamiltonian Cycles are not decision problems (except in deciding the cycle). What you may be thinking of is a situation where everyone has n choices, and everyone has a ranking of those choices. Finding the optimal solution to that may be NP.

That is what I was thinking of.


I think is called a "deadlock" for computers. Application programs typically request resourses from an operating system, and it is the operating system's job too make sure the deadlock doesn't happen.

Like Matt said, getting an optimal assignment is hard, but operating systems don't really care about an optimal assignment. The med school assignment algortihm is described here.

This is a description of how the algorithm works; joe's link is to a popup and doesn't come up right (it's in the next section down from the link I just gave). I assume that med students are basically fungible as far as their interests, and aren't matched with advisors or the like—at any rate that algorithm doesn't accomodate a balance for the overall class.

This also shows that in a way it's impossible to optimize outcomes in certain situations.

Yeah, but only in the same way that the situation where we both want the last slice of cake and neither of us will settle for less than one whole slice does.

The comments to this entry are closed.