The end of the graduate-industrial complex

The philosophy department of Columbia has, in their wisdom, waitlisted me.  (I knew it was a bad idea to use an essay that criticized one of their emeritus faculty as my writing sample.)  Apparently the logistics of waitlisting and acceptance are as follows: since all philosophy departments require notice as of April 15th as to whether or not one will be attending in the following fall, on the morning of the 15th the departments get in touch with those from whom they have not yet heard and demand said intelligence.  Thus armed they contact those on their waitlist (who have, presumably, been fending off calls from the schools that have accepted them) and tell them if they've been accepted and on what terms, &c., these then deciding what they will do in the span of a few hours and then calling back.

This scheme, while clunky, seems as if it probably works pretty well, but what about the case of cyclic acceptances and waitlistings, as in the following?

A is accepted by X and waitlisted at Y, the first choice.
The same relationship holds for B, Y and Z, and C, Z, and X

Comes the morning of the 15th, and X calls A and wants to know, are you coming?  A says, "I'm waiting to hear from Y".  But A will never hear from Y, because Y needs to know the disposition of B, who's waiting to hear from Z, which needs to know what's the story with C, who still carries a torch for X, which is waiting on A.

Of course, if they were all aware of the total acceptance situation, the problem would be easily soluble.  But they aren't.

I bet this kind of problem comes up in poorly-designed multithreaded or parallel processing programs pretty frequently.

[Post title shamelessly taken from a conversation with <a href="http://www.adamkotsko.com">Kotsko</a>.]

Comments

[Matt Weiner]

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.

[ben wolfson]

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.

[Matt Weiner]

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.

[eb]

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.

[bitchphd]

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.

[Adam Kotsko]

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.

[ben wolfson]

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

[James Liu]

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

[austro]

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.

[tweedledopey]

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.

[tweedledopey]

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.

[tweedledopey]

I am tweedledopey, killer of comments.

[ben wolfson]

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!

[Matt Weiner]

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.

[Matt Weiner]

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.

[tweedledopey]

Ben,
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.

[ben wolfson]

That is what I was thinking of.

[Adam Kotsko]

RIGOR!

[joe o]

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.

[ben wolfson]

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.