The Tao of Gaming

I don't know if I've linked to Overcoming Bias before or not. It doesn't deal with gaming, but is interesting and sometimes deals with tangential items of interest (especially to game theory).

Today they are talking about Newcomb's Paradox (which I first encountered in a math class in middle-school. Thanks, Martin.)

And the following jumped out:

Nonetheless, I would like to present some of my motivations on Newcomb's Problem - the reasons I felt impelled to seek a new theory - because they illustrate my source-attitudes toward rationality. Even if I can't present the theory that these motivations motivate...

First, foremost, fundamentally, above all else:

Rational agents should WIN.

Don't mistake me, and think that I'm talking about the Hollywood Rationality stereotype that rationalists should be selfish or shortsighted. If your utility function has a term in it for others, then win their happiness. If your utility function has a term in it for a million years hence, then win the eon.

But at any rate, WIN. Don't lose reasonably, WIN.

{I'm adding them to the blogroll and cleaning up some old URLs).

I Love Math, a site for math teachers, has an interesting page on probability & statistics. The Game of Greed is a precursor to Diamant — although I don't know which came first. You have five rounds. In each round, you start with some point (they use 2d6). Each student can sit (and score) or risk. Once everyone's decided, the teacher rolls a die. One number 'craps out.' Any other number adds to the current score.

They have a lesson on statistics with that, but lets ignore that.

(Interesting aside — the break even point (the score at which sitting or standing shows the same Expected Value) doesn't depend type of die, assuming only one side "craps out", and is just equal to the total of the other sides. Proof is left as an exercise for the reader.)

Assume you were playing for extra credit, but for the winner only. It's the first round, simultaneous decisions. The score is at 14. Expected Value says to risk. (We'll assume the sides are 1,2,3,4,5,Bust.

Suppose you sit. The ideal outcome has everyone else craps out. You are up 14 points with four rounds remaining. More likely, you'll be down ~3 on everyone. Presumably (given EV) most people will now sit. Some may push on and be 6-10 ahead of you. Let's assume someone gets to 10 ahead. Not good, an almost certain loss. But with 25 students, losing is expected. Being +14 gives you good odds of winning (and a 1/6th shot). So others should also sit out.

In Bridge, this is like matchpoints tournament strategy. A solid 60% game is good, but won't win. If you add risk to your game (bringing your average score down but increasing volatility), you stand a better chance of winning. [I remember an article in Bridge World about this].

The more I ponder this, the more intrigued I get. As the number of players increases, you can either risk by pushing past everyone, or by dropping out and hoping for a bust. An early drop mirrors a late push. [Of course, here the payoffs or the same, which isn't true for Diamant, and the odds change with tile draws in the real game.]

Consider the final round. Abby leads, with Betty one point back and Carla eleven points back. Everyone else is hopeless. Opening roll is a twelve. Who do you like in that situation?

You know, Carla has a shot. She passes and the roll survives. Can Abby and Betty pass now? if either one does the other just needs to survive one roll (5/6). [Technically Betty may need to survive two rolls to win outright, but lets assume that the numbers preclude a tie ... make it 2,3,4,5,6,Bust]. So both risk and survive. Do they have to keep going? Either one stopping gives it to another. At three rolls the score should be ~22, but they've only got a 50/50 shot of making it there. Great odds for Carla, because the leaders won't stop.

If both Abby and Betty keep rolling forever, they lose. Who should give ground first? Suppose they keep going for three more rolls, then Betty (being in the inferior position) stands down and takes the 1/6 shot of the next roll crapping out.

Under this scenario: Carla wins 131/256 (~50%) of the time (Crap out in the middle) [51.1%] Betty wins 1/6 * (125/256) [8.1%] Abby wins 5/6 * (125/256) [40.7%]

Not bad for Carla at all.

But Betty can improve. Suppose that Betty stands down the round after Carla. Carla's got a 1/6 chance. Betty has a 5/36 shot (makes the roll, sits down, Abby busts) and Abby gets 25/36. Carla has better odds than Betty, but not obscenely better.

Another finesse. Betty, knowing that Carla will sit, sits at the same time. Carla can't win, Betty gains 1/36th, and Abby pockets the rest. But Abby, figuring the same thing, may sit at the same time. Abby wins automatically.

Remove Carla, and the situation is simple -- Abby pushes. If Betty pushes, then Abby wins 1/6th of the time and we're back to start, so Betty just has to sit and give Abby the 5/6th shot. Carla confuses the issue.

I'm not even sure how to handle this (assuming Carla sits and we're down to two decision makers). It's not a zero sum game, it's a negative sum game (the excess value going to Carla). There's a recursive entry (both risking gives Carla a 1/6th shot, removing value from the Abby/Betty matrix).

So if Carla sits, what do you do as Betty. You sit most of the time, but you have to risk sometimes, to prevent Abby from sitting at the same time.

Putting it all together -- how many people (out of the class of 25) should take wild risks in the first round? This splits the pack into two groups, one of which is probably 15 points ahead of the other. Then how many of that group should take a high risk strategy? Meanwhile, the losing group has to go riskier, since they are behind ... should some of them play for a minor gain, let the rest of the group (probably) fail, and then try again next round. I wonder if these questions have been answered in the literature?

I'm terrible at Diamant, by the way. But I think that I may try my "Drop out slightly early and pray for disaster" idea. [Of course, Diamant lets you score extra depending on when you drop out, complicating the issue]

Little Princess Tao wanted to play Ubongo. So we played. (She finished most puzzles in time, and often beat me).

This got me to thinking about polyominoes. I can look at a basic grid arrangement and a set of -ominoes and tell if it's impossible by counting squares, and some arrangements because of parity issues. But I suspect that with some thought I could knock out more possibilities. Are there other tricks? Is there a good reference for the theory behind this that doesn't involve massive math?

The fact that Wikipedia had nothing leads me to believe I'm spelling this wrong, or missing a technical term.

A local gamer strongly resisted Air Baron, claiming it took forever. But we played 6 players in the typical 90 minutes. (w/ advanced rules). Most players followed what I call the 'typical' strategy.

1. Get a single hub in several spokes (to earn the $3 bonus when that spoke is drawn). Usually get ones that are valuable (to have more of your money invested), but save a few bucks for next turn.
2. Once you've got a reasonable base, try to control a hub. Some prepatory moves (jumbos, foreign spokes) may help if you plan on doing this via a fare war.
3. Now that you have market share (and income) start attacking adjacent hubs.

Let's call this strategy "Expansive" since it spreads out quickly.

The old group would start attacking players who split up in phase 1. (They call it wimpy play). So they attack! I'm not sure on the details ... but this strikes me as a non-stable strategy, on the other hand, it poisons the environment.

If we assume five opponents who will attack people who split up ("Punishers") then an Expansive player is doomed. He expands, and then punishers attack. Even if they fail often, and cost themselves dearly, odds are that one of them will knock me out. And while they incur a large cost (paying twice as much for ~60% shot at kicking out the expander), the expander losses the whole investment as well. So in a spoke valued Y, several punishers lose 2Y (paying and failing), one looses 2Y (paying and succeeding) but has potential future income. And the expander loses all that future income. [I'm making a lot of simplifications].

Now, this clearly does suck the amount of money out of the system. In a game with all punishers, they'll start grouped out (for safety and too avoid triggering punishment) and so will earn money at a slower rate, and increase market share quickly. That will toss in the 'event' chits into the bag, and those suck money out of the game too. 9 Hours seems excessive, but I could imagine three.

But put one "Mellow Defender" into the mix. Mellow won't provoke an attack (like the expander), but won't attack him either (unless it's genuinely a good play). In essence, he'll let the punishers deal with him. Given that the punishers overpay (to punish), he should win more than his fair share. Other players notice, and switch from Punishers to Mellow. If there's only a single punisher, he'll rarely win.

This doesn't help the poor expanders, who were driven extinct (in that play group) long ago. Ah, group think and evolution. To complicate things, Punishers may retaliate against the 'parasitic' mellow player. Evolution worries about free-riders.

Via Newmark's Door, I skimmed an interesting book available online: Markets, Games, and Strategic Behavior: Recipes for Interactive Learning, an economics text on game theory and the like. I just skimmed it, but there were some interesting experiments on market bubbles. As usual, the games are theory, not fun. But I now think that someone could make a great game about stag hunting.

The Fury of Dracula showed up this week. I've never played the original, so the release didn't excite me, but I did glance at the rules. The basic mechanism reminds me of Scotland Yard, and then I read the combat section.

Oooh, it's a decision matrix. Chock full of game theory. But it gets better. The matrix is actually done with cards, and each player has a base number of cards. The hunters have 3, and Dracula has 3 during the day, but 8 at night. But the hunters (and possibly Drac, I'm not sure) may have some cards beyond what the started with, which means that your opponent may or may not be able to make some choices.

I think this is an innovation; it's certainly new to me. You also have a one-turn delay. Once you pick a tactic, you can't use it during the next round. Combat keeps going until one side escapes, dies or a certain number of stalemates occur in a row.

Unfortunately, Fury of Dracula adds dice as well. Each entry in the matrix has two outcomes depending on who wins the die roll, but ties are not re-rolled (the cards have an initiative number to break ties). There's also multiple combat if several hunters corner Drac ... they each play a card and Dracula picks his opponent. If Dracula wins, you resolve his card against his opponent. If the hunters win, they pick which card to use.

So you have a reasonable "find the villian" game, and then a decision matrix with hidden information.

Interesting, in theory. No idea if it works in practice ... but I hope to find out.

And yes, I realize the title plays on the Exorcist. I couldn't think of a good vampy quote.

As I was driving home, the news was discussing an immigration speech the President gave. Given recent discussions about the utility of game theory, I was reminded about some thoughts I had on this a while back. Warning — very little to do with games. Feel free to skip.

The problem with the current situation is that the incentives all align to do nothing. The employer doesn't want to rat out the workers — he wants cheap labor. The workers don't want to get deported. Fortunately, game theory has a solution — turn this into a prisoner's dilemma. But how?

Say that the current fine is $10,000 per illegal employee. (I don't know what it is, but it's a nice round number). The solution is to give half that amount to the person who fingers the employer, including the illegal employee. Suddenly the two sides aren't so cozy. Remember, that unlike many of the cases in nature, etc, this is a single shot game. If the employee defects (calls the Feds), then the employer can't retaliate. Also, as the number of employees grows, each has to be concerned that another employee is willing to sell them all out for a large payday. (Sure, you may not rat yourself out for $5k, but would you rat yourself out for $50k? That's a large chunk of change to have in Latin/South America ... more than you'll earn in several years).

As an added incentive, give the illegal employee a guest worker permit (in addition to the money) and employers would have to be fools to hire illegals (that weren't relatives or some such).

[I'd personally combine this with immigration reform, but that's not a game-theoretic issue].

Update: The rest of the money can go into the general gov't coffers (or wherever it goes now), but allocating some as a pool for hiring new enforcers or paying bonuses would give the responsible agency (DHS now, I guess) some incentive, too.

I know that everyone's made the pilgrimage to Mecca Essen (or eagerly casting their gaze towards the Messe), but a bit further north the Nobel prize for Economics went to Schelling and Aumann for Game Theory. Schelling's work is actually very approachable (after he won the Nobel I read up a bit). In any case, this has kicked off a discussion in the economics (and political) blogosphere on the utility of Game Theory.

Slate posted an anti-Schelling article, Daniel Drezner defends him here.

There's discussion on just how useful game theory is. Check out this post on Marginal Revolution and follow the trackbacks.

Mark Kleiman has a nice roundup of links, and a great quote: "If you doubt the utility of game theory, just ask an evolutionary biologist."

Or anyone whose been to Mordor or had to convert a point after attempt.

Mahalanobis references a few papers on Evolutionary Game Theory. You know you care.

I played Power Grid and Around the World in 80 Days with a new group. (And it's nice to find another new group in San Antonio).

Power Grid has an evaluation problem: How much to bid on a plant? For example, in the early game there's only one reasonable plant available. The next plant (on the future market) is great. But the replacement plant (top card of the deck) may be terrible and show up instead of the great plant. Or it could be a plant that is good, but not great.

This probabilistic evaluation showed up several times last night. But I've noticed ... even if you can set a value that completely encompasses the risk of the future, the actual future will often be quite far away from the evaluation. [This issue shows up quite a bit in my work, too, and I want to explain it with technical terms like "Strongly Bimodal"]

To make this easier to explain, let's take the reverse. One good plant available, two players, and the next plant to fall into the market will be bad. However, there's a plant (or two) in the deck that are great and will go into the the market. [The rest of the plants wont, or are terrible].

The good plant will be bid up, of course. But each player will have to weigh the fact that they could get a great plant (cheaply) if they drop out. That lowers the premium that should be paid. So if you are willing to pay 45 (say), that's because you'd normally be willing to pay 50 (if the next plant was guaranteed to be terrible), but factor in a chance of something good happening. That's valued at five. (All numbers made up).

Here's the thing. I place the value of 'a good plant may show up' at five (or whatever). But once the card flips, I'll usually get zero (bad plant) or some high value (good plant bought at face value, instead of bid up). Call it forty. So the risk premium is five, but the actual value is never five.

This is like having an auction game where one item you can bid on is worth a zero, unless you roll 11+ on 2d6, then it's worth sixty. I don't think I'd look too kindly on such a game.

Power Grid has lots going on, but as we move up the learning curve, I expect more games to be won or lost on the turn of a card. [My last BSW game was a runaway when I got a good plant for face value on turn 3 or 4]. And this will be true even if everyone values the risk correctly. If the "turn of the card" premium is correctly evaluated and followed, some number of games are going to have one player jackpot or crap out. [The 'crap out' option leaves the other n-1 players all fighting evenly].

I've been thinking of Power Grid as a "Top Ten" game. (I've played 50 times on BSW, and probably 30+ face to face). But this fact has been gnawing at the back of my mind for a while.

While thinking about football, I noticed that the geek has the alternate game matrices used for the official WBC tournament.

You are on the one yard line, you need a TD, the clocks about to run out. What play to call (Pro-style offense). What defense? For simplicity, ignore offenses 13-20. [You can't use them inside the 10 yard line anyway]. Let's look at the coach's sheet....

I've flipped the chart around to make offenses run down the side. This is basically taking each chart and answering the game theory question ... does this win me the game? (1,-1) means that the offense (me) wins while (-1,1) means I'm the goat. Note that 5D is (0,0). That's because it's a defensive penalty, and we'll get another play (at the one yard line). Those zeroes should be equal to the value of the rest of the game, but I'm not about to figure that out.

Anything jump out at you?

For this situation, there are some strategies that are Dominated. If you win with Power Tackle, you would have won if you picked Power Middle ... and Power Middle wins a few time that Power Tackle doesn't. With a lot of math (or a computer program) you can solve this exactly. (I did this, but then the file got corrupted and I'm not typing that matrix in again. Maybe I need a better tool). The optimal strategy involves picking three offenses 1/7th of the time, and two others 2/7ths. Ditto for the defenses. (The symmetry of the answer surprised me, which is why I remember it).

Football Strategy is solvable in these "DoOrDie" situations, the real issue is "What do you do on 1st & 10 at your 20 or 25, with the game tied and plenty of time on the clock." How do you value each yard? I could use some ideas that football sabermetricians are using. In fact, I may.

Yes, I have a side project. Right now I'm working on the framework, but I'm also doing this to learn about MFC (which stands for Microsoft's Effin Classes, I believe). Don't expect anything soon, but if anyone has any thoughts about how to place a value on yardage in a "long distance" situation, I'd like to hear it.

Oh, and a good repository of Linear Algebra algorithms would be nice.

Brad Delong posts a seminar notice:

Clock Games: Theory and Experiments

Markus Brunnermeier (Princeton) and John Morgan (Haas)

December 4, 2004

Abstract: Timing is crucial in situations ranging from currency attacks, to product introductions, to starting a revolution. These settings share the feature that payoffs depend critically on the timing of a few other key players--and that their moves are uncertain. To capture this, we introduce the notion of clock games and experimentally test them. Each player's clock starts on receiving a signal about a payoff-relevant state variable. Since the timing of signals is random, clocks are de-synchronized. A player must decide how long, if at all, to delay his move after receiving the signal.

Still, I don't think I'll be travelling to attend. Too bad. Quick! To the Googlemobile!

The paper contains 56 pages. The hoary math starts around page 8. I particularly like the equation on the bottom of page 9, which shrinks the font size (so that it fits on one line), and has taus, several integrals, lots of famous numbers and yes! even a summation. The next line starts "This unwieldy integral expression is greatly simplified using Kummer functions..."

I used to be good at math...