You are currently browsing the tag archive for the ‘axiom of choice’ tag.

They say that when Alfred Tarski came up with his theorem that the axiom of choice is equivalent to the statement that, for every set , and have the same cardinality, he first tried to publish it in the French PNAS. Both venerable referees rejected the paper: Frechet argued there is no novelty in equivalence between two well known theorems; Lebesgue argued that there is no interest in equivalence between two false statments. I don’t know if this ever happened but it’s a cool story. I like to think about it everytime a paper of mine is rejected and the referees contradict each other.

Back to game theory, one often hears that the existence of Nash Equilibrium is equivalent to Brouwer’s fixed point theorem. Of course we all know that Brouwer implies Nash but the other direction is ~~more tricky~~ less known. I heard a satisfying argument for the first time a couple of months ago from Rida. I don’t know whether this is a folk theorem or somebody’s theorem but it is pretty awesome and should appear in every game theory textbook.

So, assume Nash’s Theorem and let be a compact convex set in and be a continuous function. We claim that has a fixed point. Indeed, consider the two-player normal-form game in which the set of pure strategies of every player is , and the payoffs under strategy profile is for player I and for player II. Since strategy sets are compact and the payoff function is continuous, the game has an equilibrium in mixed strategies. In fact, the equilibrium strategies must be pure. (Indeed, for every mixed strategy of player II, player 1 has a *unique* best response, the one concentrated on the barycenter of ). But if is a pure equilibrium then it is immediate that .

**Update** I should add that I believe that the transition from existence of mixed Nash Equilibrium in games with finite strategy sets to existence of mixed Nash Equilibrium in games with compact strategy sets and continuous payoffs is not hard. In the case of the game that I defined above, if is a dense subset of and is a mixed equilibrium profile in the finite game with the same payoff functions and in which both players are restricted to the pure strategy set , then an accumulation point of the sequence in the weak topology is a mixed strategy equilibrium in the original game.

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

**Recap: **At every day an outcome is realized (`‘ means a rainy day, `‘ a non-rainy day). An expert claims to know the distribution of the stochastic process that generates the sequence of outcomes. A sequential test is given by a Borel set of infinite sequences of predictions and outcomes. An expert who delivers forecast fails on a realization if where is the prediction made by about given the previous outcomes .

Let me remind you what I mean by `a test that does not reject the truth with probability ‘. I am going to write an equivalent definition to the one I used up to now, this time using the language of stochastic processes.

Definition 1The test does not reject the truth with probabality if for every -valued stochastic process one has

We are going to prove the following theorem:

Theorem 2Consider a sequential test that does not reject the true expert with probability . Then for every there exists a such that

So a charlatan, who doesn’t know anything about the true distribution of the process, can randomize a forecast according to and pass the test with high probability regardless of the actual distribution.

** — Discussion —**

Before we delve into the proof of the theorem, a couple of words about where we are. Recall that a forecast specifies the Expert’s prediction about rain tomorrow after every possible history . We denote by the set of all such forecasts. The most general tests are given by a function , and specify for every such the set of realizations over which the forecast fails. Since is infinite we know that there exist tests that passes a true expert and are not manipulable by a strategic charlatan.

Sequential tests have the additional property that the test’s verdict depends only on predictions made by along the realized path: When deciding whether a forecast passes or fails when the realization is the test only considers the predictions made by *along* x. We also say that the test does not depend on counter-factual predictions, i.e. predictions about the probability of rainy day after histories that never happen. It seems that counter-factual predictions would be irrelevant to testing anyway, but, as the theorem shows, if the test does not use counter-factual prediction then it is manipulable.

One situation in which sequential tests are the only available tests is when, instead of providing his entire forecast before any outcome is realized, at every day the expert only provides his prediction about the outcome of day just before it is realized. At infinity, all the information available to the tester is the sequence of predictions and realized outcomes.

** — Sketch of Proof —**

We can transform the expert’s story to a two-player normal form zero-sum game as we did before: Nature chooses a realization and Expert chooses a forecast . Then Expert pays Nature if fails on and otherwise. The fact that the test does not reject the true expert translates to the fact that the maximin of the game is small. If we knew that the minimax is also small then an optimal mixed strategy for the Expert will satisfy (3). We only need to prove the existence of value, or as game theorists say, that the game is *determined*.

Unfortunately, this time we cannot use Fan’s Theorem since we made no topological assumption about the set , so there is no hope to get semi-continuity of the payoff function. Indeed, as we shall see in a moment, the Normal form representation misses an important part of the expert’s story. Instead of using a normal form game, we are going to write the game in extensive form. I will call this game .

- The game is played in stages .
- At stage Nature chooses an outcome and Expert chooses a prediction simultaneously and independently.
- Nature does not monitor past actions of Expert.
- Expert monitors past actions of Nature.
- At infinity, Expert pays Nature if and otherwise.

Now I am going to assume that you are familiar with the concept of strategy in extensive form game, and are aware of Kuhn’s Theorem about the equivalence between behavioral strategies and mixtures of pure strategies (I will make implicit uses of both directions of Kuhn’s Theorem in what follows). We can then look at the normal form representation of this game, in which the players choose pure strategies. A moment’s thought will convince you that this is exactly the game from the previous paragraph: Nature’s set of pure strategies is , Expert’s set of pure strategies is and the payoff for a strategy profile is . So far no real gain. Extensive form games in which one of the players don’t monitor opponent’s actions need not be determined. In order to get a game with a value we are going to twist the game , and allow Nature to observe past actions of the Expert player. This makes life more difficult for the Expert. Up to a minor inaccuracy which I will comment about later, the resulting game is what’s called Blackwell game and it admits a value by (a seminal theorem of Donald Martin).

Here is the game after the twist. I call this game .

- The game is played in stages .
- At stage Nature chooses an outcome and Expert chooses a prediction simultaneously and independently.
- Each player monitors past actions of the opponent.
- At infinity, Expert pays Nature if and otherwise.

Now if you internalized the method of proving manipulability that I was advocating in the previous two episodes, you know what’s left to prove: that the maximin of is small, i.e. that, fore every strategy of Nature, Expert has a response that makes the payoff at most . We know this is true for the game but in Nature is more powerful.

Here is the most important insight of the proof: The fact that an expert who knows the distribution of the process can somehow pass the test implies that the maximin in is small, but this fact alone doesn’t say anything about the maximin of . To show that the maximin of is also small we will use the fact that the way such an expert passes the test is *by providing the correct forecast*. Until now the distinction was not really important to us. Now it comes into play.

Let be a behavioral strategy of Nature in , i.e. a contingent plan that specifies the probability that Nature play after every. Let be the pure strategy of Expert in that is given by

So the pure action taken by the Expert player at day is the mixed action that Nature is going to take at day according to her strategy . Now assume that Nature follows and Expert follows . Let and be the random variables representing the actions taken by Expert and Nature at day . Then the stochastic process satisfies (2). Therefore from (1) we get that the expected payoff when Nature plays and Expert plays is indeed smaller than .

Now for the minor inaccuracy that I mentioned: For Martin’s Theorem we need the set of actions at every stage to be finite. We can handle this obstacle by restricting Expert’s action at every stage to a grid and applying the coupling argument.

** — Non-Borel Tests —**

What about pathological sequential tests that are given by a non-Borel set ? Well, if, like me, you find it preposterously impossible to choose one sock from each of infinitely many pairs of socks, then perhaps you live in the AD paradise. Here every set is measurable, Blackwell Games are determined even when the payoff function is not Borel, and Theorem 2 is true without the assumption that is Borel. See, the AD universe is a paradise for charlatans, since they can do as well as the true experts.

If, on the other hand, you subscribe to the axiom of choice, then you have a non-manipulable test:

Theorem 3There exists a sequential test with a non-Borel set that does not reject the truth with probability and such that for every there exists some realization such that

** — Summary —**

If you plan to remember one conclusion from my last three posts, I suggest you pick this: There exist non-manipulable tests, but they must rely on counter-factual predictions, or be extremely pathological.

Muchas gracias to everyone who read to this point. Did I mention that I have a paper about this stuff ?

The economics profession has been for a long time divided into two camps — ADs and ACs.

On the AD camp, there is me, claiming that a bit of exciting bizarreness brought to game theory by the axiom of choice is not worth the headache of checking measurability of strategies and the embarrassment caused by undetermined gale-stewart games; The Axiom of Determinacy, on the other hand, offers a paradise in which Read the rest of this entry »

## Recent Comments