As you might expect from the title, this post is motivated by gift exchanges common during this holiday season. In particular, the “Yankee swap,” or “white elephant,” gift exchange involves some interesting mathematics that remind me of the classical secretary problem.
First, the secretary problem: suppose that you must interview each of candidates for a job, and after each interview you must decide whether to accept the candiate, or reject him/her and continue with the next interview. You cannot return to a previously interviewed candidate. What should your strategy be in order to maximize the probability of selecting the best candidate?
This problem is interesting in part because the performance of the optimal strategy does not depend (much) on ; you can select the best applicant with probability approximately by interviewing– and rejecting– about candidates, then accepting the next candidate that is the best so far (or the last candidate if a “new best” is not found).
The Wikipedia link above provides plenty of information about the problem and its solution, which I won’t rehash here. But the reference at the bottom of this post has a lot of additional interesting information about generalizations of the problem. For example, rather than maximizing the probability of selecting the best candidate, what if you want to maximize the expected rank of the selected candidate? This frankly seems like a more realistic objective, at least in this particular context. One fascinating result is that, similar to the original problem, the optimal expected rank is also (nearly) independent of , about 3.8695.
What does this have to do with exchanging gifts? The Yankee swap gift exchange may be viewed as a more hostile variant of the secretary problem. Suppose that you represent one of companies (participants) each hiring a secretary from a pool of candidates (gifts). The first company interviews a randomly selected candidate, and is initially stuck with that candidate. Each subsequent company may either interview a randomly selected new candidate, or “steal” a candidate previously interviewed by another company, in which case that company must interview a new randomly selected candidate. Depending on your position in the selection order, should you choose to “steal” a previously interviewed candidate or interview a new candidate, and what is the probability that you will end up with the best candidate?
(Note that we have made several simplifying assumptions in this problem. First, this is the “standard” Yankee swap with rules as described above. There are a lot of variations, including longer series of stealing, “freezing” gifts that have been stolen a number of times, etc. Also, as with the original secretary problem, the goal is to get the single best secretary, or gift, or whatever, as opposed to the one with the best expected rank. Finally, and least realistically, let us assume that everyone ranks the candidates/gifts in the same order.)
It turns out that, as expected, the last person to make a selection has the largest advantage, getting the best gift with probability . More generally, the probability that the person in position ends up with the best gift is
Slightly less obvious is the fact that the optimal strategy does not have the “cutoff” property as in the secretary problem: everyone (except the first) should always steal the best gift seen so far… except that for the second person, their strategy does not matter. That is, their performance is not affected by whether they steal the first person’s gift or select a new one. Can you see why?
- M. Ajtai, N. Megiddo, and O. Waarts, Improved Algorithms and Analysis for Secretary Problems and Generalizations, SIAM Journal of Discrete Mathematics, 14:1 (2000) 1-27.