Following up on <A href=http://tar.weatherson.org/2008/01/01/signalling-and-job-markets/>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=http://en.wikipedia.org/wiki/Marriage_theorem>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=http://en.wikipedia.org/wiki/Stable_marriage_problem>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=http://en.wikipedia.org/wiki/Arrow%27s_impossibility_theorem>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.