Two Six-Packs of Beer on a Game Theory Wager

[Jeff W]

I have a wager with my friend on a point of game theory. Can someone verify my claim below? If you have a link to a credible source, I would appreciate it.

JeffW Okay, my wager is
JeffW In a two person zero sum game
JeffW The player who is second to act
JeffW Always wins or ties under the following conditions:
JeffW 1. He has perfect information about the game.
JeffW 2. He plays perfectly under all contingencies.
JeffW okay, 2 six packs of beer valued at no more than $15 total.

[xCEO]

if he allways wins or ties, is this a zero-sum game?

[MCS]

[ QUOTE ]
if he allways wins or ties, is this a zero-sum game?

[/ QUOTE ]

Sure. Let's say the game is: you pick an integer between zero and five, then I pick an integer between zero and five. Then, I receive 10 points and you receive -10 points. That's a zero-sum game I always win.

Which actually leads me to the question of whether you can have the same trivial case serve as a counterexample to your claim (where the result is always 10 for player one and -10 for player two).

[Jeff W]

I think I am missing an assumption somewhere. The basic argument was that in Chess, according to game theory, black must either win or tie if he plays perfectly. He cannot lose.

[MCS]

Hmmmm. I would think that white should always win or tie, not black.

In tic-tac-toe on a 4x4 board where you still only need three in a row, the first player always wins.

And yeah, chess is a game of complete information and thus theoretically "solvable."

[WhiteWolf]

I do not think this follows from game theory. I'll make up a trivial game: Put four beans in a jar. Two players alternate moves. For each move, you can take out either one or two beans. The player who removes the last bean wins. In this game, the smart first player will remove one bean, leaving three beans in the jar. No matter what move the second player makes (removing one bean to leave two, or two beans to leave one), the first player will be able to win, thus disproving the hypothesis that moving second is always an advantage....

[bobbyi]

You are definitely missing some part of the description of what you are trying to say, because as it stands now it is trivial to come up with games under your conditions that do not have first mover advantage. Suppose we play iterative roshambo. You say "rock", "paper" or "scissors". Then I do. Obviously, this game is a win for the second player.

[Iceman]

[ QUOTE ]
I have a wager with my friend on a point of game theory. Can someone verify my claim below? If you have a link to a credible source, I would appreciate it.

JeffW Okay, my wager is
JeffW In a two person zero sum game
JeffW The player who is second to act
JeffW Always wins or ties under the following conditions:
JeffW 1. He has perfect information about the game.
JeffW 2. He plays perfectly under all contingencies.
JeffW okay, 2 six packs of beer valued at no more than $15 total.

[/ QUOTE ]

In Connect Four, if both players play perfectly the first player always wins. The game Hex is also a first player win with perfect play.

John Nash, the subject of "A Beautiful Mind", proved that Hex is a win for the first player:

http://maarup.net/thomas/hex/
(scroll down to "first player wins")

[marv]

Just because the game has perfect information and is zero sum still allows lots of flexibility since the game is necessarily asymmetric.

Silly example:

We flip a coin.
Both players are told the result.
Player 1 chooses heads or tails.
Player 2 has no actions.
If player 1 guesses correctly he wins USD 1 from player 2.
If player 1 guesses incorrectly he gives USD 1 to player 2.

This is zero sum but under optimal play the second player always loses.

Similarly we can construct second-player advantage games.

Marv

[pzhon]

[ QUOTE ]
I think I am missing an assumption somewhere.

[/ QUOTE ]
Yes. You lose the bet.

[ QUOTE ]
The basic argument was that in Chess, according to game theory, black must either win or tie if he plays perfectly. He cannot lose.

[/ QUOTE ]
That is not known. It is not a simple consequence of basic principles of game theory. It is conceivable that the opening position could be an instance of zugzwang (http://home.comcast.net/~joyner.david/wdj/chess/Elkies04.html).

Some games like hex or chomp have a structure that allows you to do at least as well as the first player as you could as the second player. In those games, the first player has a strategy that at least ties. However, not all games have this property, and it has not been proven that White can at least draw in chess.

[OrangeKing]

[ QUOTE ]
However, not all games have this property, and it has not been proven that White can at least draw in chess.

[/ QUOTE ]

However, there is overwhelming anecdotal evidence, from every level of play and from every computer chess program ever built, that it is White that has the advantage, not Black - and thus the question is almost certainly: is the opening position a win for White (probably not) or a draw?

The difference is the complete information that white has; in poker, acting last allows you to have more information. In chess, acting first allows you to improve your position, forcing the second player to play catchup until white makes an inaccurate move.

It is theoretically possible that white is lost, but it seems incredibly unlikely. World class players nearly never lose with the white pieces, and it is pretty simple for the top players in the world to force a drawish position if they have white.

[pzhon]

[ QUOTE ]

However, there is overwhelming anecdotal evidence... that it is White that has the advantage, not Black

[/ QUOTE ]
That isn't news.

I try to point out things that are not obvious, particularly when they contradict things that people have just said. In particular, game theory does not say that White can at least draw. That is what is relevant to this thread, and it contradicts a statement made by the original poster.

[J_V]

[ QUOTE ]
That is not known. It is not a simple consequence of basic principles of game theory. It is conceivable that the opening position could be an instance of zugzwang.

[/ QUOTE ]

Fat [censored] chance.

[Jeff W]

[ QUOTE ]

In particular, game theory does not say that White can at least draw. That is what is relevant to this thread, and it contradicts a statement made by the original poster.

[/ QUOTE ]

This does not contradict my statement. I stated that game theory predicts that black will either win or tie given perfect knowledge and perfect play, even if white plays perfectly as well.

[Jeff W]

I am missing something in my original stipulations. However, it seems that you and several other posters misread my original wager. I claimed that the 2nd player has the advantage.

Anyway, let us simply apply my wager to chess instead of a broader continuum of games. Will black always win or tie in chess given perfect play(I am aware of anecdotal evidence to the contrary)?

[J_V]

No, white is at a distinct advantage. Anyone trying to argue otherwise is insane.

[Jeff W]

Nevermind guys. Thanks for the help.

[TStoneMBD]

if youve ever played uno or crazy eight, you should know that the player who goes first has a distinct advantage.

if you removed games with a random element then your arguement would be a bit more valid, however, it would still be wrong.

for instance, lets play darts;

rule: whoever hits the bullseye on a dartboard first wins.

player 1 is obviously at an advantage.

[FNG]

In chess, white moves first so he has a 1 tempo advantage. With perfect play by both sides he cannot lose, except in the special case that the starting position is zugzwang for both sides, which I assume can be constructed.

I don't think there's a generalization for this, it must be game specific, since you can construct a game such that a given side will win. Chess is just one constructed so that who moves first wins.

[ACW]

Really trivial example of first player always winning :

Put $1 each on the table. Players take it in turns to pick up as much money as they like until there's none left.

99.99999% of player 1's win the whole $2.

[Orpheus]

I think you unconsciously included a cheating proposition in your mental depiction of the scenario. You say Player 2 (with perfect knowledge and execution) cannot be beaten by Player 1. I say: that may be true if Player 1 is a mere mortal, but a Player 1 with perfect knowledge and execution would have a pretty nice advantage over a 'mortal' Player 2, too.

I can think of *many* counterexamples to your premise if BOTH players have perfect knowledge and play perfectly.

How about a 'perfect duel'? The first person to shoot wins. [literally a perfect -ahem- 'execution']. You can be Player 2; tell me how perfect knowledge gets you a tie. The perfect strategy would consist of NOT letting yourself be Player 2!

It's quite common for the party that acts first to have a distinct advantage in games, in business, etc.

Also, if both parties have perfect knowledge and execution, many common games can go either way.

Take, for example: Texas Hold'Em. If both have perfect knowledge and execution, Player 2 will still lose if s/he doesn't have the hands. In fact, because there will be no bluffing or uncertainty, every hand will be folded, and the outcome will be a simple addition of how many winning hands each player will be dealt on the BB (net: 1 SB from SB) vs. SB (net: 2 Sb from BB) vs any other position (net: 3 SB from SB and BB).

"Perfect knowledge" is NOT inconsistent with randomness. Randomness means that the exact distribution of (cards, dice, cute willing babes) is beyond your control. You can still have perfect knowledge of the random outcome is still possible in two distinct forms: a) each player may know all that can be known (i.e. both know the hands dealt, but not undealt hands); or b) both have perfect knowledge of the entire sequence of hands -- dealt and undealt. Either way, "Perfect Knowledge plus Perfect Execution" do not equal "perfect control over the outcome" in TX HE.

There's another issue: If player 2 cannot lose, than either the game is biased against player 1 (who can lose) or it is moot (because Player 1 ALSO cannot lose) We cannot judge if this is true unless WE have perfect knowledge of the game. Mathematicians have been debating for centuries whether chess, for example, might be solvable -- possesing a perfect strategy for black or white. WE do not have perfect knowledge or play, so we cannot decide.

Or imagine, for example, a game where players take turns playing pieces on a N-grid (for the sake of simplicity, imagine they place their token on the intersections, as in Go or Pente, rather than the squares defined by the intersections, as in Chess). After placing each token, the player gets a score that is equal to the the sum of the distances to every remaining empty intersection (i.e. the final score will be the number of remaining empty squares x the average distance)

Our perfect (algebraic) knowledge of this game tells us that, if N is odd, the first player always wins, because placing his first token in the center spot represents an insuperable advantage. Player 2 must make an inferior 2nd move, and every later spot s/he chooses will already have been passed over as "known inferior, or at best equal) by Player 1 [Also, Player 1 will have one more empty square on each turn to gain points with: each of his/her tokens fills a square, preventing player 2 from getting points for its distance)

You could say that this is a biased game, because Player 1 has a guaranteed winning strategy, but in YOUR example, you presumed that Player 2 had a never-lose strategy. Isn't THAT either biased (if he always wins) or moot (if he always ties)? However, to players with bad math skills (inperfect knowledge), many such games seem reasonable. We can't prove there is no universal winning strategy for black ore white, so we continue to play. Someday a computer may "solve the game" and it'll be as meaningless as tic-tac-toe to anyone who can memorize the solution.

Therefore: there exist zero sum games with an insurmountable first player advantage, if both players are otherwise equal (e.g. a duel or the token game above); and games where the outcome can be perfectly known and played, but either player may win (e.g with a random element, as in TXHE). The chess example disproves your believe that your postulate is a known premise of game theory: mathematicians have argued if there is a "solution" to chess for centuries, yet if you postulate were a known truth, any math grad student could prove "if there is a universal winning strategy to chess, it must mean a victory for Black (Player 2)" However, the general belief is tbat it would more likely be a victory for White (Player 1) because chess is a game where the first move is a significant advantage (like the duel or disk game)

You owe someone some beer.

[laja]

he owes me some beer ;]

luckily I had complete information before I made the bet and consulted my game theory teacher^^;;