Saturday, October 25, 2008

First mover advantage

You and I play a game where we take turns rolling a die. I win if I roll a 4. You win if you roll a 5. If I go first, what’s the probability that I win? There are several answer options but I find the one below most intuitive:
This dice problem is mentally tricky because many rounds end without a winner. It would seem necessary to keep track of an infinite series to arrive at an answer. But that’s not the case. The trick is seeing that each round is really an independent sub-game. The fact that the previous round ended without a winner does not affect the winner of the current round or any future round. This means we can safely ignore outcomes without winners.

The probability of winning depends only on the features of a single round. This simplifies the problem to a more tractable one. So now, assume that one of the players did win in a round, and then calculate the relative winning percentages. In other words, calculate the probability the first player wins given the round definitely produced a winner. To do that, we look at the distribution of outcomes. In any given round, the first player can roll six outcomes, as can the second player. How many of those thirty-six outcomes produce a winner, and how many are from the first player?

This diagram illustrates the answer:

There are exactly 11 outcomes where somebody wins, of which 6 belong to the first player. Therefore, the first player wins with a 6/11 chance, or about 54.5 percent of the time. This is the same numerical answer as Monte Carlo, but we get an explanation why it works. The first-mover advantage is caused by the fact the first player wins even if both were to roll winning numbers.

Source: http://mindyourdecisions.com

No comments: