The Hiring (Im?)possibility Theorem

Following up on <A href=>Brian’s recent post</a> about candidates having to signal to departments that they’re actually interested, I’ll mention some ideas that my friend and colleague Mike Titelbaum and I were discussing one evening at the APA.

One thing that would remove the need for people to signal like this would be by putting the decisions of who is hired where in the hands of some sort of benevolent third-party (perhaps like the APA or something). Candidates could submit a ranked list of their preferences for which department they’d like to be at, and departments could submit a ranked list of their preferences for candidates (after having seen the files and conducted interviews and such), and hopefully some sort of matching between candidates and departments could be arranged from this information. (We might also want to allow some sort of cut-off where a candidate or department could specify that they’d rather just remain unmatched this year and repeat the search next year, rather than take anything further down on their list.) If this could be centralized, it would eliminate the inefficiencies each year where a position goes unfilled, because a department’s first few choices take other jobs, by which point their later choices have already settled for something else. These situations hurt both candidates and departments, because there are fewer actual jobs to go around, and some departments end up having to repeat the whole search process.

The important question to answer (ignoring temporarily the question of whether such a process would have negative consequences as well as positive ones) is whether such a process is even possible. Of course, one could just randomly assign candidates to jobs, but that would be no good – we’d want the assignment process to satisfy certain criteria.

1. The process should be able to take any set of rankings of departments and candidates and produce an assignment, with exceptions only if it’s impossible to construct a matching meeting the minimum acceptability cutoffs.

2. The matching should be “stable” in the sense that if C1 is matched with D1 and C2 is matched with D2, then it should not be the case that C1 prefers D2 to D1 and D2 prefers C1 to C2. (This condition guarantees that no department and candidate have an incentive to defect from the centralized assignment. Perhaps this condition can be dropped if the overall system is important enough to people’s long-term careers that there are already strong incentives not to defect.)

3. If one particular list of preferences produces a match between candidate C and department D, then keeping the same lists of preferences while raising C’s position on D’s list, or D’s position on C’s list should also result in C and D being matched matched. (This is the condition that guarantees there is no incentive to falsely list one’s preferences. We might want to further require that these changes in preferences make <i>no</i> change in the overall matching, because these changes should be irrelevant to anyone else’s matching.)

4. Maybe there should be other conditions too – the only potential one that comes to mind is that changing your preferences among candidates or departments that are lower on your list than the one you were matched to shouldn’t change anything, though perhaps this criterion is more arguable.

Once we’ve got a list of criteria like this, it should be possible either to construct an algorithm that meets these criteria, or to prove that no such algorithm exists. By <A href=>Hall’s Marriage Theorem</a>, criterion 1 is always possible as long as there is no set of m departments that find only the same n candidates acceptable, or m candidates that only find the same n departments acceptable, with m>n. By the <A href=>Stable Marriage Theorem</a>, there is in fact an algorithm that satisfies criterion 2. The question is whether these two can be combined with criteria 3 and 4.

Now, since criteria 3 and 4 were inspired by <A href=>Arrow’s Impossibility Theorem</a>, it might seem that such an algorithm is impossible. However, I have hope in this case, because the construction is not as involved in this case. In Arrow’s theorem, the problem is that given a bunch of rankings, no group ranking can be found that is positively influenced by all of them. In this case, we start with a bunch of rankings, but don’t need to produce a ranking – instead we just need to produce a pairing. And in this case, differences in rankings seem like they should only make things easier (because if the two of us have different first choices, you can make both of us happy in this case, while you can’t in Arrow’s situation).

In fact, if we don’t have minimum acceptability cutoffs, and all the candidates agree on the ranking of the departments (or vice versa), I can construct an algorithm that satisfies all these criteria. Just have the departments draft candidates one at a time, with the departments picking from most preferred to least preferred. (Or vice versa, if the departments all agree on a ranking for the candidates.) Since disagreements in ranking look like they should intuitively make things easier, hopefully this means that there’s an algorithm that will work in general, though actually coming up with this algorithm looks much harder.

Anyway, someone working on social choice theory should find the right set of criteria here and publish the proof of the possibility (or impossibility) theorem, and then the APA (and other professional societies) can have the discussion about whether or not to adopt the procedure. One thing that can be said for the current system is that it gives candidates and departments many chances to adjust their rankings of one another – this might be a way to help get around impossibility theorems, which will assume that the ranking is fixed.

14 Replies to “The Hiring (Im?)possibility Theorem”

  1. Psychology, too, has something similar for their internship programs (my wife is currently applying). My understanding is that their matching process is managed through a third-party agency, the NMS (, which also handles the matching process for internship/residency programs in dentistry, neuropsychology, osteopathy, pharmacy, and medicine. I’m not sure how exactly the NMS’s matching algorithm(s) works, but it seems to do a reasonably good job at least in psychology.

    Using an independent matching agency such as the NMS for the philosophy job market would seem to require no major resources on the part of the APA (other than money, of course).

  2. The original post didn’t address whether this is a good idea. I don’t think it is. In fact I think it would be disastrous. Note that it is quite different from the case of internship programs since here we are talking in many cases about positions which will be permanent.

    Here’s one problem I see with this: candidates are supposed to submit a ranked list of where they’d want to be — on what basis? They are to choose in advance without being able to visit the departments amongst which they’re choosing or the cities in which those departments are located. That is, they are to rank in a way that reflects little knowledge and sometimes much prejudice.

  3. I suppose that’s true – you can’t make informed rankings about places without having visited a bunch of them, but if people have to visit every place in order to get this information, then it’s even more expensive and time-consuming than the current system.

    But perhaps there’s room for a first round of matching, where several people are chosen to fly out to each place and a second round of matching where all jobs are assigned? Of course, it’s not clear at all what sorts of constraints are important for flying people out – there’s effectively no limit to the number of places one person can fly out to, but there’s good reason for the departments not to want to all fly out the same people.

    This sort of system would ease problems of hiring taking too long and being too stressful on both ends, but it would make it harder to see how to effectively gather the information that one gets at interviews and campus visits.

  4. While I concede Michael’s point to some extent, I’m not so sure things are as bleak as he suggests. First, most people don’t stay at their first job forever (in fact, I think this almost never happens anymore). Second, some schools (Princeton?) think that personal interviews or contact actually undermine the accuracy (predictive or otherwise) of the process. So, some would reject the presupposition of Michael’s remarks. I’m not sympathetic with the Princetonian line on this, but it’s worth mentioning. Why not a compromise: use a matching system for the fly-out selections. That would avoid Michael’s worry, no? And, it would also put the dreaded APA Eastern out of business.

  5. It would be great to put an end to the Eastern job market gauntlet. I expect the APA’d fight it tooth and nail though, since they make a huge amount of money on it (all those registration fees). The thing that bothers me the most is that job candidates have to bear the costs of APA interviews (they have to pay for their own flights and hotel stays, unlike with campus interviews).

  6. My wife is a doctor, and has gone through the medical match system twice, once for residency and just recently for fellowship. It results in surprising and unpredictable spur of the moment life changes. I know people who put money down on a house where they thought they would end up, only to find out that they were going somewhere else. The psychology governing the match system is very different than the psychology governing non-match systems, in ways that are difficult to explain. My impression is that it is retained in medicine because it takes all bargaining power out of the hands of the candidate, and therefore keeps costs lower for hospitals. Residency salaries are criminally low, since no one has bargaining power. As a result, there is a class-action lawsuit challenging the system wending its way up to the Supreme Court. Fortunately, I don’t think there is any danger of our community switching to this system, because we lack the cash incentives; by and large universities are far more likely to be financially solvent than hospitals.

  7. The a capella groups at Brown used to use a system like this. I don’t know if they still do. Each person trying out for more than one group would submit an ordered preference list, and each group auditioning would submit an ordered preference list of people they would be prepared to take. They need not list anyone. I never heard about any problems with it, and I knew a lot of people in several groups.

    I don’t know they ended up with situations that required someone uninvolved to make a choice to resolve cases that couldn’t be handled merely by the numbers, one way to do that is simply to have someone uninvolved make a decision. It could be by coin flip if there’s a need to make it non-subjective (not that a coin flip makes it objective in any important sense, but it’s not exactly subjective either).

    For the philosophy job market, this would indeed need to be in several stages, to leave room for APA interviews then campus interviews and then finally offers. But one problem that might appear is how to sort out schools that use a different system (e.g. phone or televideo interviews instead of APA, phone interviews after the APA with a larger committee in order to sift further down to campus interviews, campus interviews without any prior interviews). There’s also the problem of schools who might want to revisit lower candidates on their list with phone interviews after they don’t end up with anyone out of their choices the first time through but who didn’t know enough about those candidates to put them on the list the first time. There’s also the problem of how to coordinate this with non-APA departments who wouldn’t be using the system.

    But if those problems can be solved, this might work. It would certainly removed a number of problems with the way things are done at this time.

  8. I agree with Jason competely on this issue. The sort of psychology that governs match-up systems doesn’t seem to me to be one that would really work to everyone’s advantage with respect to tenure-track jobs in philosophy. First and foremost, it seems (falsely) to assume that people are quantifiable entities who could, all things considered, fit just as well in place A as in place B, and to assume that departments can be quantified neatly, too. Esp. with tenure-track jobs, though, the non-quantifiable stuff (like personality fit, collegiality, etc.) is also terribly important—and it becomes even more important for small departments that don’t get a chance to hire very often, or for departments at liberal arts colleges that place a huge emphasis on teaching (which obviously can be judged a heck of a lot better on the basis of personal experience than from old student evals).

    I can’t be the only person who’s gone into an interview thinking, “This place is #1 on my list” and walked out thinking, “Huh. Now #17”, or—better—who’s walked into an interview she’s not particularly excited about and walked out really impressed with the department. Sure, the Eastern APA sucks…but in-person interviews still seem to me the best way to go, for both job candidates and departments.

  9. In principle, there’s nothing about a system like this that prevents it from being implemented only after interviews and campus visits and the like, since those are important factors in forming one’s preference rankings. Though of course, those also form much of the problematic aspect of current systems.

    I suppose the main things this sort of solution are supposed to fix are things like people not getting a job because some places think they’ll be getting better jobs than theirs; and some places not getting hires because everyone they fly out gets a job they prefer over it.

    Of course, this does lead to the problem Jason mentions of reduced leverage for job applicants. Since there’s no real organization of labor among job applicants, this is the one point of leverage candidates really have. (Of course, since the hiring committees are made up of people who once were candidates, and perhaps will be again in the future, the pressures aren’t the same as in factory work, but I would have imagined the situation with residencies in medicine would be similar too, so some of these pressures do seem necessary.)

  10. And in response to Laurie Paul’s comment about paying for one’s own trip to the APA, I wonder if a suggestion something like the following might work. For campus visits it makes sense for the department to pay, because it’s clear which department ought to. For the APA interview there may not be any one department who can collect receipts. Instead, we might have candidates submit their receipts to the APA itself for reimbursement. As for where the APA gets the money from, they can just see which departments each person got interviews at, and split the costs for that person among those departments. Now, this particular system will create weird incentives, where a department can more cheaply interview someone who’s also being interviewed by other places, so it would mean that the people with many interviews would get more, and the people with few interviews would get less, which is not something to encourage.

    Perhaps instead, the APA could just calculate its total expenses on this project, and say that each department has to pay an amount proportional to the number of interviews they conducted. This might put a downward pressure on the number of interviews conducted there, but this might be a good thing if it means that departments do the real work of looking at all the candidates closely and cutting the list down to strong contenders before interviewing, rather than waiting until afterwards to sort through 24 candidates as I hear some places did.

  11. Michael and Christina-

    The residency match is conducted after a round of preliminary application, and a round of interviews, which address a number of your complaints. Presumably any sensibly designed philosophy match would work the same.

    Of course, the unpredictability side of things can’t be really be gotten rid of, but that’s somewhat true of the usual application process.

  12. It’s obvious that we’re never going to do this, so it’s not really worth making this point. But I’m procrastinating, so I’ll make it anyway. The residency match system, for the reasons I gave above, is in violation of federal anti-trust laws. The lawsuit against the residency match system was ultimately dismissed, because the AMA hired a bunch of lobbyists who got a bill through Congress signed by President Bush specifically exempting the medical match from federal anti-trust law. Below I’ve linked to the New York Times article explaining this; there is lots more information available elsewhere. So unless the APA has a lot more money than I’ve realized, we’re stuck with our current system. Which is not a bad thing.

Leave a Reply