The White Elephant problem
It's that time of year for holiday parties. Everyone pulls out the one item of bright red clothing from their wardrobe, hams fly off of Christmas shelves, and someone from work drinks a bit too much and embarrasses themselves in front of their coworkers by falling prey to loneliness and the holiday blues and hitting on someone from another department. Fun!
A popular instantiation of the holiday party is the White Elephant party. Everyone brings a gift of roughly the same monetary value, wrapped and concealed from curious eyes. Everyone draws a number to determine the gift selection order. When your turn comes up, you have the choice of selecting one of the unopened gifts or stealing an opened gift from one of the previous participants. A gift can be stolen a maximum of three times, and when someone steals a gift from you, you can either steal a gift from someone else or choose one of the unopened gifts. The only limitation is that you can't steal a gift back from someone who stole it from you during the same turn. You can steal it back in a subsequent turn, however, if you get the opportunity to choose a gift again. A turn ends when everyone an unopened gift is chosen.
While playing earlier this evening at Eric and Christina's White Elephant party, I wondered what position was the optimal position for maximizing one's chance of ending up with the best gift. Maybe someone has worked this out, but I haven't heard of a solution. Let's call it the White Elephant problem.
Assume N particpants, each bringing one gift so we have N total gifts. If all gifts were exactly equal in desirability, then the problem would be uninteresting. Anyone who's been to such a party knows this is never true. Assume that each of the gifts varies in desirability, from most to least desirable, in linear fashion. The most desirable gift is N times as desirable as the least desirable gift, and the second most desirable gift is (N-1) times as desirable as the least desirable gift, the third most desirable gift is (N-2) times as desirable as the least desirable gift, etc. (this might seem unrealistic, but tell that to the person who brings the beautiful chrome martini shaker and ice bucket set only to walk home with a free AOL 9.0 CD-ROM or an avocado). To simplify the problem, we'll also assume that every person can compute exactly how the ratio of desirability of any two gifts if they those two gifts have been opened and that everyone judges the desirability of each gift the same exact way (this generally holds true at the White Elephant parties I've been to; if someone ends up with
Everyone draws a number from 1 through N. The person selecting number 1 chooses a gift first, and so on until the person drawing N has chosen, and then the game is over. Assume that when a person's turn comes up, they are statistical geniuses and can compute whether stealing a gift from another person or choosing from the unopened pile will maximize their chances of selecting the most desirable product possible. Based on all the previous assumptions I've stated, in some games, a participant whose turn comes up near the end will be able to tell even with a few unopened presents if one of the opened presents is the best gift from the group.
Express as a function of N what position is the most desirable position to be in if you want to maximize your chances of selecting the most desirable gift from among all N gifts at a White Elephant party. To remove the simple edge cases when there are only a few participants and to imitate reality, assume N is at least 10 or greater.
If someone can solve this, leave the answer in the comments or e-mail me the answer and I'll send you a stainless steel cocktail shaker or a mystery gift. I haven't had time to work out the problem myself, but I suspect there's an intuitive answer. You probably don't want to go first since you can't steal any gifts. Going last isn't necessarily the most desirable position, either, because the best gift may be selected early and stolen 3 times before the last participant's turn.
I myself was pleased to make out with a Dakine Metal Scraper and base wax combo at tonight's party. It was certainly a better bounty than Audrey's take of an anatomically incorrect blowup John doll, though in a place like L.A., dressing up John and getting to use the HOV lane might pay someone back in spades.
[There's also the Major League Baseball White Elephant Party, where the two partygoers named The Yankees and The Red Sox get to watch everyone else open their gifts and play with them for a while, and then the two of them steal all the most fun and desirable gifts. Okay, that's not entirely accurate, but I'm feeling quite bitter about MLB right now. Seriously, if you're Tampa Bay, holding one property, Baltic Place, and everyone else has built hotels on every other property on the Monopoly board, why even bother?]
A popular instantiation of the holiday party is the White Elephant party. Everyone brings a gift of roughly the same monetary value, wrapped and concealed from curious eyes. Everyone draws a number to determine the gift selection order. When your turn comes up, you have the choice of selecting one of the unopened gifts or stealing an opened gift from one of the previous participants. A gift can be stolen a maximum of three times, and when someone steals a gift from you, you can either steal a gift from someone else or choose one of the unopened gifts. The only limitation is that you can't steal a gift back from someone who stole it from you during the same turn. You can steal it back in a subsequent turn, however, if you get the opportunity to choose a gift again. A turn ends when everyone an unopened gift is chosen.
While playing earlier this evening at Eric and Christina's White Elephant party, I wondered what position was the optimal position for maximizing one's chance of ending up with the best gift. Maybe someone has worked this out, but I haven't heard of a solution. Let's call it the White Elephant problem.
Assume N particpants, each bringing one gift so we have N total gifts. If all gifts were exactly equal in desirability, then the problem would be uninteresting. Anyone who's been to such a party knows this is never true. Assume that each of the gifts varies in desirability, from most to least desirable, in linear fashion. The most desirable gift is N times as desirable as the least desirable gift, and the second most desirable gift is (N-1) times as desirable as the least desirable gift, the third most desirable gift is (N-2) times as desirable as the least desirable gift, etc. (this might seem unrealistic, but tell that to the person who brings the beautiful chrome martini shaker and ice bucket set only to walk home with a free AOL 9.0 CD-ROM or an avocado). To simplify the problem, we'll also assume that every person can compute exactly how the ratio of desirability of any two gifts if they those two gifts have been opened and that everyone judges the desirability of each gift the same exact way (this generally holds true at the White Elephant parties I've been to; if someone ends up with
Everyone draws a number from 1 through N. The person selecting number 1 chooses a gift first, and so on until the person drawing N has chosen, and then the game is over. Assume that when a person's turn comes up, they are statistical geniuses and can compute whether stealing a gift from another person or choosing from the unopened pile will maximize their chances of selecting the most desirable product possible. Based on all the previous assumptions I've stated, in some games, a participant whose turn comes up near the end will be able to tell even with a few unopened presents if one of the opened presents is the best gift from the group.
Express as a function of N what position is the most desirable position to be in if you want to maximize your chances of selecting the most desirable gift from among all N gifts at a White Elephant party. To remove the simple edge cases when there are only a few participants and to imitate reality, assume N is at least 10 or greater.
If someone can solve this, leave the answer in the comments or e-mail me the answer and I'll send you a stainless steel cocktail shaker or a mystery gift. I haven't had time to work out the problem myself, but I suspect there's an intuitive answer. You probably don't want to go first since you can't steal any gifts. Going last isn't necessarily the most desirable position, either, because the best gift may be selected early and stolen 3 times before the last participant's turn.
I myself was pleased to make out with a Dakine Metal Scraper and base wax combo at tonight's party. It was certainly a better bounty than Audrey's take of an anatomically incorrect blowup John doll, though in a place like L.A., dressing up John and getting to use the HOV lane might pay someone back in spades.
[There's also the Major League Baseball White Elephant Party, where the two partygoers named The Yankees and The Red Sox get to watch everyone else open their gifts and play with them for a while, and then the two of them steal all the most fun and desirable gifts. Okay, that's not entirely accurate, but I'm feeling quite bitter about MLB right now. Seriously, if you're Tampa Bay, holding one property, Baltic Place, and everyone else has built hotels on every other property on the Monopoly board, why even bother?]