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.

— Manipulability —

I start with Sandroni’s paper (pdf). The following definition formalises the idea that the true expert is unlikely to fail the test

Definition 1 The test {T} does not reject the truth with probability {1-\epsilon} if {\mu(T(\mu))<\epsilon} for every {\mu\in \Delta(X)}.

If a test does not reject the truth with probability {1-\epsilon} then a true expert, who knows how nature randomizes the realization, is unlikely to fail the test. Alas, a charlatan who acts strategically is also unlikely to fail

Theorem 2 (Sandroni (2003)) Let {X} be finite. If {T:\Delta(X)\rightarrow 2^X} is a test that does not reject the true expert with probability {1-\epsilon} then there exists {\zeta\in\Delta\bigl(\Delta(X)\bigr)} such that {\zeta\bigl(\{\mu|x\in T(\mu)\}\bigr)<\epsilon} for every {x\in X}.

So, a charlatan who knows nothing about how Nature chooses {x} can randomize a forecast {\mu} according to {\zeta}, and is unlikely to fail, regardless of the realization. We say that the test is manipulable.

For Sandroni’s Theorem we do not need to assume any structure on {X}. However the situation we have in mind is that {X=S^n} for some finite set {S} of outcome. So at every day {0\leq k<n} Nature randomizes an outcome of {s_k\in S} and the Expert claims to know the stochastic process that governs Nature’s choices.

Proof: Let {Y\subseteq \Delta(X)} be a finite set such that {T(Y)=T(\Delta(X))}.

Consider the following two-player zero-sum game with the players called Nature and Expert. Nature is the maximizer with pure strategies set {X}, and Expert is the minimizer, with pure strategies set {Y}. If Nature plays {x\in X} and Expert plays {y\in Y} then Expert pays Nature {1} if {x\in T(y)} and {0} otherwise.

By von-Neumann’s Minimax Theorem the game admits a value {v} in mixed strategies, so that the maximin equals the minimax. We claim that {v<\epsilon}. Indeed, let {\mu\in\Delta(X)} be a mixed strategy of Nature and let {y\in Y} be such that {T(y)=T(\mu)}. Then the expected payoff that Expert pays Nature if Nature plays {\mu} and Expert plays {y} is {\mu(T(y))=\mu(T(\mu)<\epsilon} since the game does not reject the true expert with probability {1-\epsilon}.

Now let {\zeta\in\Delta(Y)} be a mixed optimal strategy of the Expert in the game. Then

\displaystyle \zeta\bigl(\{\mu\in Y|x\in T(\mu)\}\bigr)\leq v<\epsilon

for every pure strategy {x} of Nature, since the left hand side is the expected payoff that the Expert pays Nature if he plays {\zeta} and Nature plays {x}. \Box

The argument in the proof of Sandroni’s Theorem captures the essence of all the manipulability theorems we will see. We define a zero-sum game between two players, Nature and Expert. The minimax theorem is the core of the proof: The fact that the maximin is smaller than {\epsilon} follows from the assumption that the test is unlikely to reject the true expert. The fact that minimax is smaller than {\epsilon} implies that the test is manipulable. In the middle, we use the most wonderful miracle that the minimax and maximin are equal.

— Fan’s Theorem —

Here is the more general minimax theorem which we will use later: In a zero-sum game, if one of the players have a compact set of pure strategies, and the payoff to that player is u.s.c. in his own strategy then the game admits a value in mixed strategies.

Proposition 3 (Ky Fan)Consider a two-player zero-sum game in normal form with pure strategy sets {X,Y} and payoff function {h:X\times Y\rightarrow [0,1]}. If {X} is a compact metrizable space and {h(\cdot,y)} is upper-semi continuous for every {y\in Y} then the game has a value in mixed strategies, i.e.

\displaystyle \sup_{\mu\in \Delta(X)}\inf_{y\in Y}\int h(x,y) \mu(\text{d} x)=\inf_{\zeta\in\Delta_f(Y)}\sup_{x\in X}\int h(x,y)\zeta(\text{d} y).

and all suprema are attained.

The set {Y} is not topologized and {\Delta_f(Y)} is the set of distributions over {Y} with finite support, so the integral on the right side is just a summation. The challenge in using Fan’s Theorem is to find a topology over {X} which is sufficiently weak to make {X} compact and sufficiently strong to make the functions {h(\cdot,y)} upper semi-continuous.

— Non-manipulability —

Sandroni’s Theorem does not hold when {X} is infinite, precisely because the game we defined in the proof will have no value. We now take a game without a value and translate it to a non-manipulable test for an infinite set {X} of realizations. I only know about one game without a value (`I know a larger such game’ quipped Sergiu when I said it in the talk): Two players pick simultaneously and independently natural numbers and the player that chose the largest number wins. Here is the translation of the game to a test:

Example 1 Let {X=\mathbb{N}}. Let {T:\Delta(X)\rightarrow 2^X} be the test that is given by

\displaystyle T(\mu)=\{x\in{\mathbb N} | \mu([x,\infty))<\epsilon\}.

Then {T} does not reject the true expert with probability {1-\epsilon}, and for every {\zeta\in\Delta(\Delta(X))} there exists a realization {x\in X} such that

\displaystyle \zeta\bigl(\{\mu\in\Delta(X)|x\in T(\mu)\}\bigr)>1-\epsilon.

Not only the test is not manipulable, also for every {\zeta\in \Delta(\Delta(X))} that a charlatan might employs to randomize his worthless forecast {\mu}, there is some realization {x} under which he fails with high probability.

Proof: For every {\mu\in\Delta(X)} let {t(\mu)} ({t} for tail) be given by {t(\mu)=\min\{t\in {\mathbb N}|\mu\left([t,\infty)\right)<\epsilon\}}. Then {T} can be equivalently written as {T(\mu)=[t(\mu),\infty)}.

We first show that the test has small probability to reject a true expert. Indeed,

\displaystyle \mu\left(T(\mu)\right)=\mu\left([t(\mu),\infty)\right)<\epsilon

for every {\mu\in\Delta(X)}, where the first equality follows from the definition of {T} and the second from the definition of {t}.

Now let {\zeta\in\Delta(\Delta(X))}. Let {\bar\zeta\in\Delta(\mathbb{N})} be the push-forward of {\zeta} under {t} and let {x\geq t(\bar\zeta)}. Then

\displaystyle \begin{array}{rcl} \lefteqn{\zeta\bigl(\{\mu\in\Delta(X)|x\in T(\mu)\}\bigr)=}\\&&\zeta\bigl(\{\mu\in\Delta(X)|x\geq t(\mu)\}\bigr)=\bar\zeta\left([0,x]\right)\geq 1-\epsilon.\end{array}

The first equality follows from the definition of {T}, the second from the definition of {\bar\zeta} and the inequality from the choice of {x}. \Box

— Sequential Tests —

So, Sandroni’s Theorem only holds for finite sets {X}. We are now aiming at proving a manipulability theorem for infinite set {X} by adding some structure on the set {X} and some restrictions on the test. From now on we assume that {X=\{0,1\}^{\mathbb N}}. The set {S=\{0,1\}} is the set of outcomes. Everything works for arbitrary finite set of outcomes but I stick with two outcomes for notational convenience. Note that {X} a compact metrizable space in the product topology.

There is an almost equivalent representation of and element {\mu\in\Delta(X)} as the conditional probability that {s_n=1} given {s_0,\dots,s_{n-1}} for a {\mu}-randomly chosen {x=(s_0,s_1,\dots)}. Let {\mathcal{F}} be the set of functions {f:\{0,1\}^{<{\mathbb N}}\rightarrow [0,1]}, then this gives rise to natural map {f\in\mathcal{F}\mapsto\mu_f\Delta(X)}, which is surjective and continuous when the domain is equipped with the product topology and the range with the weak{^\ast} topology. It will be useful to identify {\mathcal{F}} with {\Delta(X)}, so I will think of a test as a function {T:\mathcal{F}\rightarrow 2^X}.

For every {f\in\mathcal{F}} and every realization {x=(s_0,s_1,\dots)}, the sequence of forecasts of {f} along {x} is given by {(p_0,p_1,\dots)} where {p_k=f(s_0,\dots,s_{k-1})}.

Definition 4 A test {T:\mathcal{F}\rightarrow 2^X} is sequential if {x\in T(f_1)} implies {x\in T(f_2)} for every {f_1,f_2\in\mathcal{F}} and every realization {x} such that the forecasts made by {f_1} and {f_2} along {x} are the same.

Equivalently, a sequential test is given by a subset {R\subseteq ([0,1]\times \{0,1\})^{\mathbb N}} ({R} for rejection): {x\in T(f)} iff {(p_0,s_0,p_1,s_1,\dots)\in R} for every realization {x=(s_0,s_1,\dots)} and every forecast {f\in\mathcal{F}}, where {(p_0,p_1,\dots)} is the sequence of predictions of {f} along {x}.

— Next Episode (Thursday 12:00) —

I will talk about Olszewski and Sandroni’s paper `The manipulability of future independent tests’ and my paper `Many inspections are manipulable’ . Main goal is to prove that sequential tests are always manipulable.