I finally found a use for my graduate degree in Game Theory!
Courtesy of New Scientist Magazine, Graham Lawton. Magazine Issue 2792, 25 December 2010, pages 58-59. I should probably put some legal disclaimer here, since I am just using copy and paste. I think everyone should get a subscription to their magazine. Please don’t sue.
Win big at the office party with game theory as your guide
WHEN it comes to Christmas presents, do you give as good as you get? Most people think they do. Even President Barack Obama is on record saying he goes one better. “Here’s the general rule: I give nicer stuff than I get,” he told Oprah Winfrey in a hard-hitting pre-Christmas interview last year.
That may seem ungrateful, but consider the implications. Most people believe that the gifts they get are not as good as the ones they give. No wonder Christmas is so often a crushing disappointment. There is a better way: abandon the ritual of mutual gift-giving in favour of a much more rational system called secret Santa. The beauty of this is that you only have to buy one present for each social circle you belong to, rather than one for everyone you know.
In the original version of secret Santa each member of a group – colleagues, say – is anonymously assigned to buy a gift for another and give it to them at the Christmas party. How sweet. Thankfully, that game has evolved into something more Machiavellian: thieving Santa, also known as dirty Santa or the Grinch game. As its name suggest, this revolves around theft and dirty tricks.
In its simplest version, everybody buys a present costing between, say, £10 and £20. They then secretly deposit it, gift-wrapped, into a sack. To start the game, numbers are drawn out of a hat to decide the order of play. Now the horse-trading begins. The first player must take a present from the sack and open it. The second player then has a choice – open a new present, or steal the already opened one. If they choose to steal, player 1 gets to open another present, but they are not allowed to steal their present straight back. Player 3 now enters the fray, either opening a new present or stealing an opened one, whereupon the victim gets to play again, either stealing a different present or opening another new one. And so it goes on until everybody has had a turn and there are no more unopened presents.
The system is not without its flaws, however. For example, if the first player opens a poor present they are likely to be stuck with it, while the player picked to go last has a good chance of getting a really good present, perhaps the best. For that reason there are many variants designed to spread the pain. One is to allow dispossessed players to steal a present back, although this tends to lead to endless rounds of tit-for-tat larceny. Another is to set a limit on how many times an individual present can be stolen.
If you have never played thieving Santa, give it a go. It’s fun. Fun, though, can be overrated. What you really want is to win – and that means ending up with the best possible present.
So how should you go about getting it? Intuitively it is hard to say. Imagine you are playing a game in which a present can only be stolen once (see diagram) and it is your turn. There are three opened presents on the table and four in the sack. One of the opened ones is not bad, and if you steal it you can keep it. But there may be even better ones in the sack, so why not gamble? Then again, if you open a really good present somebody is certain to steal it from you, and you risk ending up with something really terrible. What to do?
Here is where a strategy developed by game theorists Arpita Ghosh and Mohammad Mahdian of Yahoo Research in Santa Clara, California, can help (Lecture Notes in Computer Science, vol 6099, p 228). “I heard about this game at a New Year’s party, from somebody who had just been playing it at Christmas,” says Ghosh. “I thought it would be fun to analyse.”
Ghosh and Mahdian decided to play a simplified version of the game. Assuming certain things – that the players are sober, for example, and that everybody puts the same value on the same presents – they wanted to work out how to “maximise the expected utility”. Or, in English, to work out what you theoretically expect to get out of a transaction before it has happened.
They started by thinking about the game’s final round, where all but one of the players has had a turn and there is just one unopened present left in the sack. In this case the strategy is pretty obvious.
If all the presents are worth somewhere between £10 and £20, the expected value of the final unopened present is £15. The rational strategy, therefore, is to look around the table and steal any present worth more than that. But remember, if the top present has been unwrapped it is likely to have been stolen already so you won’t be able to have it. So if there isn’t a present worth more than £15 that hasn’t already been stolen, open the one in the sack. This means that the final player has an expected utility of at least £15, which is about as good as it gets.
Expected utility, of course, is not the same as what you actually get. You might think that the final present is trash, in which case the strategy wasn’t much help. But at least you can console yourself that it was correct in theory.
Ghosh and Mahdian then started to work backwards through each player’s turn – a process known as backward induction – to derive a general strategy.
Their next stop was the last-but-one player, where there are two unopened presents. This is a bit more complicated than before, as you have to take into account the possibility of opening a really good present which is immediately stolen. This possibility means that the last-but-one player must have a lower steal threshold than the final player. Ghosh and Mahdian’s calculations show that a player in this position should steal any present worth £13.75 or more. If there is no such present available, they should open a new one.
This “threshold strategy” turns out to work for all players, except the first, who has no choice but to open an unopened gift. The steal threshold itself rises as each player takes their turn because the fewer people left to pick a present, the fewer opportunities there are for someone to steal yours.
What this means is the steal threshold starts low; in an 8-player game it is approximately £11.56 for the second player. But, surprisingly, it delivers an expected utility of slightly more than £15 for all players – except poor old player 1, of course, who is more or less guaranteed to “take one for the team” and get something pretty lousy.
“When your turn arrives, have a look at the gifts that you can possibly steal,” says Ghosh. “If the best of those is good enough, where ‘good enough’ depends on how many unopened gifts remain, steal it. If the best of those is not good enough, open a new gift.”
Which is all very well and good, but a theoretical utility in excess of £15 can’t magically transform the contents of the sack. There are still good presents and bad ones, and somebody is going to end up with the dross.
Ghosh acknowledges this. “What this is really all about is making sure you get the best of the rubbish.” This should perhaps be known as “minimising your futility”.
So what of the first player, who seems doomed to pick the short straw? This is an acknowledged problem in real-world thieving Santa, and is usually solved by giving the first player a chance to steal right at the end. In this case all the players have an expected utility of exactly £15.
With all this strategy at her fingertips, you would expect Ghosh to be arranging secret Santa games every year. “Actually no,” she says. “I’ve never played it.” Typical theorist.
Graham Lawton ignored the advice in this feature and won a truly lousy present in the New Scientist secret Santa
# # #
bloomfield knoble creates marketing plans, strategy, creative design, collateral, Power Point presentations, email templates, videos, audio, music videos, television commercials, letterhead, identity, gift cards, SWOT analyses, brochures, letter templates, software applications, web applications, multimedia productions, Flash content, streaming videos, logo designs, widgets, technical consulting.