Wednesday, November 18, 2009

An Indeterminate Two-Person Zero-Sum Game With Perfect Information

1.0 Introduction
I have stumbled upon some odd mathematics, some mathematics that I have not validated. Consider the claim that all two-person zero-sum games with perfect information have a value. Apparently, this claim is inconsistent with the Axiom of Choice, an axiom in set theory. This inconsistency is shown by the Banach-Mazur game and its variants. I guess it is essential to this demonstration that these games have a potentially countable infinite number of moves.

I don't know that this demonstration is as important for economics as, for instance, W. F. Lucas' example of a cooperative game without an equilibrium.

A game has perfect information if the results of all moves prior to any given move are known to all players. Simple examples of games with imperfect information are card games in which the deal gives a player a hand which only he knows. A two-person zero-sum game is determinate if one can prove either (1) the first player wins some definite amount, (2) the second player wins some definite amount, or (3) the game is a draw. Chess is a determinate game, although it is in practice impossible to expand the tree enough to determine its value.

2.0 A Game
I steal this example from a Usenet post by Herman Rubin.

The game is fully specified by the rules and by defining a set C, where C is a given subset of the real numbers between 0 and 1, inclusive. The two players alternatively select the successive binary digits of the base-two expansion of a number within the interval [0, 1].

In other words, consider the number:

(1/2) x1 + (1/4) x2 + (1/8) x3 + (1/16) x4 + ...
where, for all i, xi is in {0, 1}. The first player chooses the binary digits with the odd indices, and the second player chooses the binary digits with the even indices. But they take turns and go in order.

The game ends with the second player paying the first player a unit when it is guaranteed that any further expansion will result in a number within C. The game ends with the second player winning a unit payment from the first player when it is guaranteed that any further expansion will result in a number in the complement of C.

A simple example is C = [0.5, 1]. The first player wins in this case. A more complicated game arises when C is the set of all irrational numbers in the unit interval. I gather this game is determinate, but I don't see offhand who wins. Finally, consider a set C that does not have a Lebesque measure. (The Axiom of Choice is necessary for the definition of such a set.) I gather that in this case, the game is not determinate. Nobody can tell a priori who will win.

No comments: