You are currently browsing the tag archive for the ‘zero-sum games’ tag.

Department of self-promotion: sequential tests, Blackwell games and the axiom of determinacy.

Read the rest of this entry »

I am visiting the rationality center in the Hebrew University, and I am presenting some papers from the expert testing literature. Here are the lecture notes for the first talk. If you read this and find typos please let me know. The next paragraph contains the background story, and can be safely skipped.

A self-proclaimed expert opens a shop with a sign at the door that says `Here you can buy probabilities’. So the expert is a kind of a fortune-teller, he provides a service, or a product, and the product that the expert provides is a real number: the probability of some event or more generally the distribution of some random variable. You can ask for the probability of rain tomorrow, give the expert some green papers with a picture of George Washington and receive in return a paper with a real number between 0 and 1. The testing literature asks whether you can, after the fact, check the quality of the product you got from the expert, i.e. whether the expert gave you the correct probability or whether he just emptied your pocket for a worthless number.

So, let {X} be a set of realizations. Nature randomizes an element from {X} according to some distribution and an expert claims to know Nature’s distribution. A test is given by a function {T:\Delta(X)\rightarrow 2^X}: the expert delivers a forecast {\mu\in\Delta(X)} and fails if the realization {x} turned out to be in {T(\mu)}. A good test will be such that only `true’ experts, i.e. those who deliver the correct {\mu}, will not fail. Read the rest of this entry »

I wrote some time ago about Michael Rabin’s example of how a backward induction argument is killed when you require players’ plans to be computable. Since Rabin’s paper is not available online, I intended to post the proof at some point, but never actually got to do it. Richard Lipton’s post about Emil Post is a good inspiration to pay that debt since the concept of simple set, which was introduced by Post, has a role in Rabin’s example.

A set {S\subseteq\mathbb{N}} is simple if {S} is recursively enumerable and its complement {S^c} is infinite and contains no infinite recursively enumerable subset.

For Rabin’s purpose, what matters is that Post proved the existence of such a set. So Post provides us with a code of a computer program that enumerates over all the elements of {S} and such that no computer program can produce infinitely many elements that are not in {S}. By the way, Post introduces the concept of simple set while working on his eponymous problem which Richard mentions. In fact, if {S} is simple set then {S} is not many-one equivalent to a universal recursively enumerable set.

Now let {S} be a simple set and consider the following three-round game with perfect information. At each round a player announces a natural number (an action): First Alice announces {n}. Then Bob announces {m} and then Alice announces {t}. After the game is played, a winner is determined as follows: Bob wins if {m>n} and {m} is not the {t}-th element in the enumeration of {S}. Otherwise, Alice wins. Therefore, determining the winner is a task that can be effectively done using the code provided by Post.

Does any of the players have a strategy that guarantee winning regardless of how the opponent play ? The answer to this question depends on which mathematical creature you use to model the intuitive notion of `strategy’.

If by a strategy you mean just a function from histories to current action then Bob has a winning strategy: for every {n} that Alice might chose in the first round there exists some {m>n} such that {m\notin S}, since the complement of {S} is infinite.

But if you think of a strategy as a complete set of instructions, that is a plan or an algorithm that will tell you how to produce your next action given the past, then you want to model a strategy as a computable function. Now, for every computable function {f:\mathbb{N}\rightarrow\mathbb{N}} that Bob can chose, there exists some {m} such that either {f(m)\leq m} or {f(m)\in S} since otherwise {f(0),f(f(0)),f(f(f(0))),\dots} would have been a recursive enumeration of infinitely many elements of {S^c}. In particular, there exists some {t} such that if Alice plays {m} in the first stage and {t} in the third stage she wins against {f}. So, Bob has no winning strategy.

Since in the near future I will have to start advocating a computability argument, and since this position is somewhat in contrast to what was my view a couple of years ago when I first came across algorithmic game theory, I thought I should try to clarify my thoughts about the issue in a couple of posts.

The most beautiful example I know for the surprising outcomes we get when taking computability into account in game theory is Michael Rabin’s paper from 1957. Rabin considers a finite win-loss game with perfect information between two players, Alice and Bob. The game is played in three rounds, at each round a player announces a natural number (an action): First Alice announces {n}. Then Bob announces {m} and then Alice announces {t}. After these declaration are made, the game coordinator determines the winner: If {(n,m,t)\in W} Alice wins. If {(n,m,t)\notin W} Bob wins. The set W, Alice’s winning set, is part of the description of the games. This is a finite game, which can be solved by a background induction. By the so called Zermelo’s Theorem, the game is determined: One of the player has a winning strategy. The identity of the winner depends of course on {W}.

Rabin gives an example for a game with the following propertie:

  1. {W} is a decidable set: this means that there is an effective way to decide, for every triple {(n,m,t)} whether or not {(n,m,t)\in W}. So the job of the game coordinator in this game can be performed by a computer program. Games with effectively computable payoff are called actual games: These are the games that can actually be played.
  2. Bob has a winning strategy {f:\mathbb{N}\rightarrow\mathbb{N}}: whatever actions {n} and {t} Alice chooses in the first and third stages, Bob will win the game if in the second stage he chooses {f(n)}: so that (n,f(n),t)\notin W for any n,t\in \mathbb{N}
  3. Bob has no computable winning strategy: For every function {f:\mathbb{N}\rightarrow\mathbb{N}} that can be computed by a computer program there exist some actions {n,t} for Alice such that {(n,f(n),t)\in W}.

Feel the blow ? Bob finds himself in a strange predicament. On the one hand, after observing Alice’s action {n} from the first round, Bob knows that there is some action {m} he can choose that beats any possible response of Alice. However, if Bob tries to `plan ahead’ which action to take after every possible choice of {n}, he cannot produce such a plan. Bob can beat all Alice’s strategies and Alice can beat all Bob’s (computable) strategies. von-Neumann and Morgenstern’s least controversial idea, solving a zero-sum game with perfect information by backward induction, trembles. The argument that in finite zero-sum games with perfect information a player doesn’t care if the opponent finds out his strategy falls apart.

(To be continued…)

Join 102 other followers

Follow

Get every new post delivered to your Inbox.

Join 102 other followers

%d bloggers like this: