Also in the spirit of the holiday season, I present a new math problem relating to Christmas gift-giving. This doesn't have anything to do with gaming, but it's still too good to pass up.
Bonus Problem: Divvying Up the Loot, Modern-Day Edition
The "white elephant gift exchange" protocol, featured in an episode of NBC's "The Office", is a procedure used for distributing Christmas gifts at large gatherings. In the protocol, each of the N participants brings a gift, for a total of N gifts, which are all placed into a central pile. The participants are numbered from 1 to N. The protocol consists of N rounds.
In the I'th round of the protocol, the following steps take place:
1. Player I selects a gift and places it in front of him. He can select a gift either from the central pile or any of the gifts in front of other players.
2. If he selects a gift from the central pile, the round ends. If he selects a gift from another player, then that player (who just had his gift taken) now has the option of choosing a gift, again either from the central pile or from another player. If he takes a gift from another player, then that player also has the option of choosing a gift as described. This process continues until someone chooses a gift from the central pile, at which point the round ends.
3. Once a gift has been selected, it cannot be selected again until the beginning of the next round.
After all N rounds have been completed, each player gets to keep the gift that is in front of them.
Is it possible that after this protocol is completed, there will be two people (A and B) who each prefer the gift that the other one ended up with to the one he ended up with? (Assume that each participant has a strict preference ordering over the available gifts, and that each time a participant makes a selection, that he chooses the gift he most prefers out of those that are available for selection.)
Subscribe to:
Post Comments (Atom)
3 comments:
Alex,
I must be missing something. I would think that play would go like this...
Round 1, Player 1 picks the gift that they like the most. No reason to take from somebody else. Nobody has a gift yet. Round over.
Round 2; Player 2 picks the gift from the pile that they like most. They would not take the gift from player 1 as that isn't their favorite gift. They would pick their favorite from the pile. Round over.
And so on...
Nobody would ever take a gift from someone else as the gift that they want is still remaining in the pile.
And, everyone would wind up with their favorite gift.
Uncle Sam is assuming that Player I's favorite gift is no one else's favorite gift. But you haven't assumed that, right? I mean, it is possible for two players to actually have identical gift rankings, right?
I would start from the Nth player. The Nth player absolutely gets his or her favorite gift. If it was from the pile that means the (N-1)th player keeps his or her favorite gift -- she didn't like the one remaining in the pile as much or she would have taken it.
If Player N takes it from Player N-1 then player N-1 will get her second favorite gift.
If Player N takes it from a different player, then player N-1 might get her favorite gift taken from her, so she will end up with her second or third favorite gift.
Going backwards like this, I think that we end up with a Pareto Optimal situation. But I don't have the patience to think this through completely. But I'm guessing that I'm missing something or you wouldn't have posed this problem. Where is the flaw in my reasoning?
It is correct that Uncle Sam assumed that everyone has a different favorite gift, which is not necessarily true.
I don't really understand Dan's reasoning, but here is my solution:
---
Suppose that two people, X and Y, ended up with gifts that the other one liked better. Suppose that X selected his gift in the Ith round, while Y selected his in the Jth round. (These round numbers mean the last time that the players in question selected a gift, so they selected the gift they ended up with.) Suppose I < J. Then during the Jth round, when it is Y's turn to select a gift, X's gift will be available (since it was last selected in a previous round) so he would have selected that gift over his one. The same argument applies the other way around if I > J. Thus we must have I = J. Assume that in that round, X selected before Y. Then when X selected, both X's and Y's gifts were available, so he would have selected Y's gift because that's the one he prefers. Of course if Y was the first to select in that round, the he would have selected X's gift instead. Thus there is a contradiction.
Post a Comment