Game Theory: No Winning Strategies

[ehrenfest]

http://en.wikipedia.org/wiki/Game_theory

It can be proven, using the axiom of choice, that there are games—even with perfect information, and where the only outcomes are "win" or "lose"—for which neither player has a winning strategy.) The existence of such strategies, for cleverly designed games, has important consequences in descriptive set theory.

I am confused about this. Can someone give me an example of a game with perfect information in which neither player has a winning strategy?

 

[DaveC426913]

Well, tic-tac-toe comes to mind.

 

[Hurkyl]

I assume ehrenfest was asking for an example that satisfied the hypotheses in the quoted passage -- specifically, the only outcomes are "win" and "lose".

Alas, the page doesn't give a precise definition of "game" and "winning strategy"; without that, I couldn't really speculate. But since the article suggests the axiom of choice is needed, such games probably aren't explicitly constructible.

 

[ehrenfest]

What kind of a game is not explicitly constructible?

Does that mean that if I get asked a question about a specific game on a test, I can assume that one player has a winning strategy? Can one prove that for explicitly constructable games?

 

[EnumaElish]

A strategy is winning if the player following it must necessarily win, no matter what his opponent plays. (http://en.wikipedia.org/wiki/Determinacy#Winning_strategies)

Example 1: Rock, paper, scissors.

Example 2:
___________Column player__
___________Left ____ Right__
Row player:
Up.....(1, 0)...(0, 1)
Down...(0, 1)...(1, 0)

If CP plays L, RP wins by playing U, but if CP plays R, RP wins by D.
If RP plays U, CP wins by playing R, but if RP plays D, CP wins by L.

 

[ehrenfest]

I don't think rock paper scissers is a game in the game theory sense.

 

[EnumaElish]

I don't think rock paper scissers is a game in the game theory sense.

Why not?

 

[ehrenfest]

Okay, I guess its an example of a simultaneous game.