Expressible inspections
Abstract
EconStor is a publication server for scholarly economic literature, provided as a non-commercial public service by the ZBW.
Full text
Hu, Tai Wei; Shmaya, Eran Article Expressible inspections Theoretical Economics Provided in Cooperation with: The Econometric Society Suggested Citation: Hu, Tai Wei; Shmaya, Eran (2013) : Expressible inspections, Theoretical Economics, ISSN 1555-7561, The Econometric Society, New Haven, CT, Vol. 8, Iss. 2, pp. 263-280, https://doi.org/10.3982/TE992 This Version is available at: https://hdl.handle.net/10419/150191 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. https://creativecommons.org/licenses/by-nc/3.0/
Theoretical Economics 8 (2013), 263–280 1555-7561/20130263 Expressible inspections Tai Wei Hu Kellogg School of Management, Northwestern University Eran Shmaya Kellogg School of Management, Northwestern University A decision maker needs predictions about the realization of a repeated experiment in each period. An expert provides a theory that, conditional on each finite history of outcomes, supplies a probabilistic prediction about the next outcome. However, there may be false experts who have no knowledge of the datagenerating process and who deliver theories strategically. Hence, empirical tests for predictions are necessary. A test is manipulable if a false expert can pass the test with a high probability. Like contracts, tests have to be computable to be implemented. Considering only computable tests, we show that there is a test that passes true experts with a high probability yet is not manipulable by any computable strategy. In particular, the constructed test is both prequential and futureindependent. Alternatively, any computable test is manipulable by a strategy that is computable relative to the halting problem. Our conclusion overturns earlier results that prequential or future-independent tests are manipulable, and shows that computability considerations have significant effects in these problems. Keywords. Computability, expert testing, calibration tests, zero-sum games. JEL classification. C44, D81, D83. 1. Introduction Forecasting is crucial for economic planning. In many cases, such as weather or macroeconomic variables, the underlying data-generating process is stochastic instead of deterministic. Indeed, probabilistic predictions have been widely adopted in forecasting precipitation and economic variables. Although it is easy to test deterministic forecasts empirically, it is less obvious whether a stochastic forecast is useful or even meaningful. There is a literature that frames this problem in the context of testing experts: does there exist a test, which specifies situations where the expert is rejected, such that a true expert who knows the underlying process is not rejected by the test while a false expert who has no such knowledge but can make predictions strategically is rejected? The answer to this question depends on the nature of the test. In the most general setup, the expert is required, before any outcome is realized, to provide predictions for Tai Wei Hu: [email protected] Eran Shmaya: [email protected] We are grateful to Lance Fortnow, Sergiu Hart, Ehud Lehrer, and Rakesh Vohra for very helpful comments. Copyright ©2013 Tai Wei Hu and Eran Shmaya. Licensed under the Creative Commons AttributionNonCommercial License 3.0. Available at http://econtheory.org. DOI: 10.3982/TE992
264 Hu and Shmaya Theoretical Economics 8 (2013) each period contingent on all possible histories before that period, and the test makes a decision based on these predictions and the realized sequence of outcomes. In this general setup, without imposing other requirements, there exist tests that accept the true expert but reject strategic false experts (Dekel and Feinberg 2006,Shmaya 2008, Olszewski and Sandroni 2009a). However, this result does not hold if some natural requirements are imposed on the test. One such requirement is that a decision to reject the expert can be made only at a finite time. Another requirement is to ask the expert to provide prediction only along the actual sequence of outcomes without giving counterfactual predictions. In the literature, tests that satisfy the first requirement are referred to as rejection tests (Olszewski and Sandroni 2009a); and the second requirement is called prequentiality (Dawid 1985).1The general finding (Olszewski and Sandroni 2008,Shmaya 2008)isthat, against any rejection test satisfying prequentiality, a false expert has a strategy that allows him to pass it with a high probability against every realization of outcomes. The literature refers to such tests as manipulable, meaning that they are vulnerable to manipulation of predictions from a false expert. Here we propose a new property, expressibility, that a test should satisfy, along with the rejection-test requirement and prequentiality. As discussed in Olszewski and Sandroni (2008, Section 4), a test can be regarded as a contract between the expert and those who make use of his predictions. In the corresponding contract, the principal of the forecasting service keeps the right to charge the expert with contract violation during the entire service. To implement such a contract, there should be a finite procedure that determines whether the expert fails the test for any finite history of predictions and outcomes. However, a precise definition of expressible tests is lacking in the extant literature despite the fact that many tests in the literature are expressible. We formalize this notion by Turing computability: a test is expressible if there is a Turing machine that implements the test. A Turing machine is a finite sequence of instructions that corresponds to an algorithm: hence, for each expressible test there is a well defined procedure that determines whether the expert has failed the test for any given finite history of predictions and realizations. Moreover, it is widely believed, according to the Church–Turing thesis, that any procedure that can be expressed in words and can be implemented mechanically corresponds to a Turing machine. Thus, any contract that can be written as finitely many instructions and has a well defined procedure to implement it corresponds to an expressible test according to our definition. Indeed, all practical tests considered in the literature are expressible, including all tests proposed in the calibration literature (Foster and Vohra 1998,Lehrer 2001,Sandroni et al. 2003). The goal of this paper is to study manipulability of expressible tests (assuming the rejection-test requirement and prequentiality). Our main results pin down the exact complexity requirements on forecasting strategies to make expressible tests manipulable. The extant literature already gives some hints about our findings. The abstract 1Another property, future independence in Olszewski and Sandroni (2008), is implied by these two properties.
Theoretical Economics 8 (2013) Expressible inspections 265 manipulability results cited previously already imply a negative result: any expressible test is manipulable. However, it does not give any information about the complexity of the manipulating strategies. We find some answers to this problem from the calibration literature: for each calibration test, an algorithm of the polynomial-time class has been devised to implement a forecasting strategy that manipulates the test. Nevertheless, because the class of all calibration tests is only a subclass of all expressible tests, it is not clear whether forecasting strategies of the polynomial-time class can manipulate any expressible test. Alternatively, Fortnow and Vohra (2009) obtain positive results by considering the computational complexity of forecasting strategies, where tests of the polynomial-time class are constructed to be nonmanipulable against forecasting strategies with timeor space-complexity constraints. Their results suggest that some expressible tests are not subject to manipulation if the expert has limited computational power, but the exact requirement on such power has not been pinned down for expressible tests. A natural starting point is to consider the set of computable forecasting strategies, that is, strategies that can be implemented with Turing machines without restrictions on computation resources or time. We answer this issue with two results. In the first result, we devise an expressible test that is not manipulable by any computable forecasting strategies; in the second result, we show that if the expert has more computational power than Turing computability to implement forecasting strategies, then any expressible test is manipulable. The first result overturns the negative results in the calibration literature and shows that some expressible tests are immune to manipulability against computable forecasting strategies. In fact, we show that there are such tests that can be implemented with algorithms of the polynomial-time class. Our result then generalizes those in Fortnow and Vohra (2009) in that we consider a larger class of forecasting strategies.2This result is also related to another strand of literature (Olszewski and Sandroni 2009b,Al-Najjar et al. 2010), which obtains nonmanipulability results by imposing restrictions on the class of data-generating processes: a true expert passes the test only for processes in that class and the false expert fails on some process in that class. In our setup, a true expert always passes the test as long as the conditional distributions of the underlying processes admit rational probability values (but the process may not be computable) and the false expert is rejected on some computable process. Wenowturntooursecondresult.Herewetaketheviewthatthefalseexpert,when implementing the forecasting strategies, does not have to be constrained by Turing computability, while the test, which has to be written down as a contract, has to be expressible. Then we look for the exact complexity class of forecasting strategies against which the nonmanipulability result holds for expressible tests. To this end, we use oracle machines to model the complexity of forecasting strategies, and we classify forecasting strategies according to the arithmetic hierarchy {0 n}∞ n=1. The lowest class, 0 1, consists of all computable strategies, while the next class, 0 2, consists of strategies that can be implemented by an oracle machine with the halting problem as the oracle. Our second result states that, for any expressible test, there exists a forecasting strategy of class 2In fact, as in Fortnow and Vohra (2009), our test can be modified to run in linear time.
266 Hu and Shmaya Theoretical Economics 8 (2013) 0 2that manipulates it. Therefore, within the arithmetic hierarchy, expressible tests can avoid the manipulation result only against forecasting strategies in the lowest class. Those two results give the exact computational power requirement on the expert for expressible tests to be nonmanipulable: it corresponds to the class of computable strategies. This shows that expressible tests are more powerful than what one may infer from the previous literature: there are expressible tests that can handle Turing-computable forecasting strategies. It also shows that Turing-computability captures the full strength of expressible tests—false experts with computational power that is one layer higher than computability within the arithmetic hierarchy can manipulate any expressible test. 2. Tests and forecasting strategies At each period n,anoutcomesnfrom a finite set Sis observed. Before the observation, the principal asks the expert to deliver a probabilistic prediction, pn∈(S).Theexpert may use the partial history σ=(p0s0pn−1sn−1)of predictions and outcomes before period nto determine his prediction. The set of all such partial histories is given by ((S) ×S)<N=∞ n=0((S) ×S)n,where((S) ×S)0={e}and eis the empty sequence. Similarly, elements in S<N=∞ n=0Snare called partial realizations. Aforecasting strategy is then a function f:((S) ×S)<N→((S)) with the interpretation that f(p0s0pn−1sn−1)is the distribution according to which the expert randomizes his prediction at period n,wherepkand skare the prediction and outcome of period kfor 0≤k<n. The contract between the expert and the principal is written as a test, which is a Borel subset Tof ((S) ×S)<N.3The expert fails the test Tif (p0s0pnsn)∈Tfor some period n. The data-generating process is governed by an S-valued stochastic process X= (X0X1).GiventheprocessX, a forecasting strategy f:((S)×S)<N→((S)),and atestT⊆((S) ×S)<N, we can compute the probability that the expert fails Tover X. That probability, denoted by R(TfX),isgivenby R(TfX)=P((P0X0PnXn)∈Tfor some n) where Pn,thepredictions generated by f over X,are(S)-valued random variables such that the conditional distribution of Pngiven P0Pn−1and Xis f(P0X0Pn−1 Xn−1). A natural requirement on a test is not to fail the true expert, who knows the datagenerating process and makes predictions accordingly, with high probability. For an S-valued stochastic process X=(X0X1),letfXbe the forecasting strategy that predicts according to X, i.e., fX(p0s0pn−1sn−1)is the dirac atomic distribution on 3Our definition of test is more restrictive than what is used in some other papers because it implicitly assumes the rejection-test property and prequentiality. More general definitions allow the outcome of the test to depend on the infinite sequence of predictions and outcomes or on counterfactual predictions (that is, predictions conditional on unrealized histories).
Theoretical Economics 8 (2013) Expressible inspections 267 the element pXx ∈(S) that represents the conditional distribution of the process given the partial realization x=(s0sn−1), i.e., pXx[s]=P(Xn=s|X0=s0Xn−1=sn−1) (1) Then R(TfXX)is the probability that Trejects the true expert when the truth is X. We say that a test does not reject truth with probability 1−if R(T fXX)<for every stochastic process X. Here we give an example of a test that does not reject truth with probability 1−. Example 1 (Passing the true expert). Let S={01}, so that elements of (S) can be identified with elements pof [01],wherepis the probability for the outcome 1.LetTNα be the test that rejects the expert on all histories (p0s0pn−1sn−1)∈((S) ×S)<Nsuch that n>Nand 1 n· k<npk<1/2 (−1)sk+1+ k<npk≥1/2 (−1)sk>α for some parameters N∈Nand α>0.♦ The test TNα works as follows. The expert gets a penalty point whenever the outcome is far from his prediction (i.e., when pk<1/2but sk=1or pk≥1/2but sk=0) and gets credit otherwise. The test TNα rejects the expert if, in the long run, the penalty points exceed the credit points by a specific amount (normalized by the number of periods). The parameter αdetermines how strict the test is. For any α,ifNis large enough, then the test TNα does not reject truth with probability 1−. The test TNα is manipulable: a forecasting strategy f-manipulates atestTif a false expert, by implementing f, can ignorantly pass the test Twith probability greater than 1−regardless of the true data-generating process, that is, R(T fX)<for every stochastic process X. We give an example of a forecasting strategy that manipulates TNα. Example 2 (Manipulating strategy). Let S={01}as in Example 1 and let fbe the strategy given by f(p0s0pn−1sn−1)=⎧ ⎨ ⎩ R0 R0+R1 δ1/4+R1 R0+R1 δ3/4if R0>0 δ3/4otherwise; where R0=max|{k<n|pk≥1/2sk=0}|−|{k<n|pk≥1/2sk=1}|0 R1=max|{k<n|pk<1/2sk=1}|−|{k<n|pk<1/2sk=0}|0 and δpis the dirac atomic distribution on p. For every α>0and >0, the strategy f- manipulates the test TNα in Example 1 for sufficiently large N,thatis,R(TNαfX)< for every stochastic process X.♦
268 Hu and Shmaya Theoretical Economics 8 (2013) Remark 1. The fact that the strategy in Example 2 manipulates the test follows from the standard no-regret argument using Blackwell’s approachability theorem. See Lehrer (2003) for a substantially more general result using that argument. It is desirable for the test not to be manipulable by a false expert. However, the previous literature, which studies a more general class of tests, shows that if it is a rejection test and if it does not use counterfactual predictions, then it is manipulable. Because our definition of tests already includes these two assumptions, we have the following manipulability result, which follows from Olszewski and Sandroni (2008) and Shmaya (2008). Proposition 1. Every test that does not reject truth with probability 1−is +δmanipulable for every δ>0. 3. Expressible tests Here we propose another requirement for tests: the contract (written as a test) between the principal and the expert should be implementable with an algorithm. We call such tests expressible tests and formalize this notion by Turing computability. In Section 4,we study manipulability of expressible tests. We begin this section with some preliminaries on computability and then formulate expressible tests formally. 3.1 Preliminaries on computability Afunctionfwith natural arguments and values is computable if there exists an algorithm that computes f, i.e., if nis in the domain of f, then the algorithm halts on input n and produces output f(n), and if nis not in the domain of f, then the algorithm does not halt on input nand runs forever. An algorithm corresponds to a computer program in any programming language (say, the language C), running on a machine without memory or time restrictions. The formal definition is based on a model of computations using Turing machines (see Odifreddi 1989 for details). The celebrated Church–Turing hypothesis states that Turing computability captures our intuition of a finite procedure or an algorithm, that is, a function can be computed by an algorithm if and only if it can be computed by a Turing machine. Here we make two remarks on computable functions. First, the domain of a computable function can be a strict subset of N. We sometimes write f:⊂ N→Nto emphasize that the domain of fis a subset of N. This is because an algorithm may run into an infinite loop and never produce an output for some inputs. When the domain is N, i.e., when f(n) is defined for every natural number n, we say that fis total.S econd, the notion of computability can be extended to functions with several variables, corresponding to computer programs that get several natural numbers as input. In fact, the generalization goes further. Many sets of mathematical objects, such as Nk,Q,andN<N,canbeeffectively identified with N. There are ways to encode elements of these sets as natural numbers, i.e., there exist computable one-to-one correspondences, called codings, between these sets and the set N. Consider the set N2
Theoretical Economics 8 (2013) Expressible inspections 269 as an example. Every pair (mn) of natural numbers can be encoded as the number (n +m)(n +m+1)/2+n, which is a computable function. Similarly, every rational number can be encoded as a pair of natural numbers, and therefore, as a natural number. Given the coding, we can speak about computable functions to and from these sets. In what follows, we apply the notion of computability to any set Zthat can be effectively identified with N, assuming a fixed coding but without constructing the specific codes (which can be found in Odifreddi 1989). The notion of computability can be applied to subsets of natural numbers as well. Let Zbe a set that can be effectively identified with Nand let Abe a subset of Z.We say that Ais computable, or decidable, if its characteristic function χAis computable. By the Church–Turing thesis, a set Ais decidable if and only if there is an algorithm that determines the membership of the set A. Later we formulate a test as a subset of a set that is effectively identified with Nand formalize the notion of expressibility by decidability. Most sets and functions that one comes across are computable. Take, for example, the function r:N2→Nsuch that r(nm) =1if mdivides nand r(nm) =0otherwise. Long division gives an algorithm for this function. A more complicated example is the set of prime numbers. A number nis prime if and only if there exists no 1<m<nsuch that mdivides n. The definition already gives rise to an algorithm to check whether a number is prime: go over all those numbers mand check whether mdivides n, i.e., for each such mcheck whether r(nm) =1; this is a computable operation because ris computable. In what follows, we take the computability of a function for granted when our definition of the function gives rise to an algorithm that computes the function. The two examples above exhibit an important property of computability: if fis computable and gcan be computed by an algorithm that calls fat some points, then gis also computable. In the above algorithm, checking whether a number is prime calls to the algorithm that computes divisibility. Indeed, most programming languages support such a construction by allowing the programmer to call existing functions to define new ones. We return to this point later when we define oracle computation. The existence of uncomputable functions can be easily shown by a counting argument. Because the set of computable functions, which has the same cardinality as the set of computer programs (which are, after all, finite sequences of symbols), is countable, most functions are not computable. Related to this counting argument is the celebrated result in computability theory, the enumeration theorem (Odifreddi 1989,Theorem II.1.5), which is used in our proofs. That theorem states the existence of a binary computable function U:⊂N2→Nsuch that, for every computable function f,thereis an msuch that f=U(m·), i.e., such that f(n)is defined if and only if U(mn)is defined, and if either is defined, we have f(n)=U(mn). The main insight from the enumeration theorem is that there exists an effective encoding of all computer programs, say mbeing the code for the program pm,andthe function Ucorresponds to an algorithm that takes the codes as input and simulates the behavior of each program pmwhen given input m. Indeed, the development of operating systems is based on this insight that the master program can manage all application
270 Hu and Shmaya Theoretical Economics 8 (2013) programs (cf. Davis 2001). The function Uis called a universal machine and the sequence φ0=U(0·) φ1=U(1·)is called a computable enumeration of computable functions. The enumeration theorem also gives rise to an example of a undecidable set: the set H=dom(U), which consists of all pairs (m n) such that U(mn) is defined (i.e., such that the program pmhalts on input n), is undecidable. The set His usually called the halting problem. In a more colloquial language, the halting problem cannot be solved by a Turing machine. Finally, we introduce the notion of a oracle machine, which is a Turing machine that has access to a black box, called an oracle. In the previous example of the program that decides whether a number is a prime number, the program calls to the function r,which acts as an oracle in the sense that whenever the program calls to r, it returns values that are used by the program but are not directly computed by the program. Oracle machines generalize this idea and allow the oracle to be the characteristic function of an arbitrary subset of natural numbers (see Odifreddi 1989 for details). As such, each oracle can be identified with a subset of natural numbers. If a function fcan be computed with an oracle machine with set Aas the oracle, then we say that the function fis computable from A.IfAis decidable, then the set of functions computable from Ais the set of Turing-computable functions. However, the function χH, as well as any Turingcomputable function, is computable from H. In fact, many other uncomputable functions are computable from H. Nevertheless, because an oracle machine consists only of finitely many instructions, the set of functions computable from a fixed oracle is still a countable set. In the literature, there are various ways to classify the oracles, or, equivalently, subsets of natural numbers, into different complexity classes. Here we adopt the arithmetical hierarchy, described by 0 nsets (see Odifreddi 1989, Section IV). This classification is based on the complexity structure of quantifiers necessary to describe each subset of natural numbers as a predicate. This hierarchy respects the strength of oracles in terms of functions computable from them; more precisely, if fis computable from Afor some A∈0 n, then fis computable from any set B∈0 n+1.Theset0 1consists of all decidable sets. A set A∈0 2if and only if χAis computable from the halting problem H(Odifreddi 1989, Proposition IV.1.16). In this sense, the halting problem is among the least uncomputable functions. 3.2 Expressible tests Here we formalize the notion of expressible tests via computability. A test is expressible if and only if it can be implemented by a Turing machine or, by the Church–Turing thesis, if and only if there is an algorithm to implement the test. This definition, however, requires modifications of previous definitions of tests and forecasting strategies, because computability applies only to functions over natural numbers or subsets of natural numbers, while tests, as defined in Section 2, involve real numbers from the expert’s predictions. For this modification, we assume that the predictions made by the experts are always in rational numbers. We can relax this restriction to allow computable real numbers (which may be more natural in our context), but that requires more notation and
Theoretical Economics 8 (2013) Expressible inspections 277 such τ, checks whether (τmn)∈˜ Tby calling the algorithm that decides the membership of ˜ T.Moreover,τ∈Tif and only if σ∈T∗for some extension σof τ. Therefore, Tand T∗are equivalent in the sense that they reject the expert over the same infinite histories (p0s0p1s1). Remark 4. For comparison with Fortnow and Vohra (2009), we note that the argument in the last paragraph in the proof of Theorem 1 can be modified to make the test run in polynomial time. The test Tis polynomial if there exist a polynomial function ρ:N→N and an algorithm Asuch that, for every σ=(p0s0pnsn)∈(S ×(S))<N,Atakes at most ρ(n) steps over the input σand decides whether σ∈T.LetTbe an expressible test, that is, there is an algorithm Athat outputs 1 on σif σ∈Tand that outputs 0 on σotherwise. Consider the test T∗such that σ=(p0s0pnsn)∈T∗if and only if A outputs 1on (p0s0pksk)after at most lsteps for some k l ≤√n.ThetestT∗can be implemented with the following algorithm A. Given input σ=(p0s0pnsn), run algorithm Aon σk=(p0s0pksk)for k≤√nsequentially; if Ahalts on some σkwith output 1within lsteps for some l≤√n,thenAhalts immediately and outputs 1; otherwise Aoutputs 0. This ensures that Aruns in polynomial time with ρ(n) =Cn for some constant C.Moreover,Tand T∗are equivalent in the sense that they reject the expert over the same infinite histories (p0s0p1s1). 5.2 Proof of Theorem 2 Fix, once and for all, a test Tas in Theorem 2 and δ>0. For every n,letTnbe the nperiods restriction of T, i.e., the test that is given by all sequences (p0s0pksk)∈T such that k<n. Since Tn⊆T, it follows that Tnalso does not reject admissible truth with probability 1−. Since T=nTn, it follows that R(TnfX)−−−−→ n→∞ R(TfX)(5) for every S-valued stochastic process X=X0X1 and every strategy f: ((S) ×S)<N→((S)). We first give a lemma that shows that a manipulation strategy can be modified to have probability values over a finite grid, which in turn is a distribution over predictions over a finite grid. Let Zbe a finite set. For every natural number M>0, we denote by M(Z) the set of distributions μover Zsuch that μ[z]∈{01/M2/M1}for every z. Lemma 2. Let MK:N→Nbe given by M(k) =|S|·2k/δand K(k) =|S|M(k)+1·2k/δ. Then for every n, there exists a strategy fthat +δ-manipulates Tnsuch that f(σ) ∈ K(k)(M(k)(S)) for every kand every sequence σ=(p0s0pk−1sk−1)of past predictions and outcomes. To prove Lemma 2, we use three claims. The first claim states that every distribution over a finite set Zcan be approximated by a distribution with probability values on a finite grid. We use the L1metric: for any μν ∈(Z),μ−ν1=z∈Z|μ[z]−ν[z]|.The proof of the claim is easy and is omitted.
278 Hu and Shmaya Theoretical Economics 8 (2013) Claim 1. Let Zbe a finite set. Then for every μ∈(Z) and every M,thereexistsμ∈ M(Z) such that μ−μ1<|Z|/M. The proofs of Claims 2and 3below are omitted as well, since similar arguments have already appeared in previous papers (Olszewski and Sandroni 2008,Shmaya 2008, Lemma 1). Claim 2 states that if the expert gives prediction that are close enough to the truth, he still passes a test that does not reject a true expert. Claim 3 states that a slight perturbation of a strategy does not greatly change the probability of failing a particular test. Claim 2. Let δ>0,letX=X0X1be an S-valued stochastic process, and let fbe a forecasting strategy such that, for every sequence σ=(p0s0pk−1sk−1),f(σ)is the dirac atomic distribution on an element p∈(S) such that p−pXx1<δ/2k,where x=(s0sk−1)and pXx is given by (1). Then R(TfX)<+δ. Claim 3. Let δ>0and let f ˜ f:(a(S) ×S)<N→(a(S))5be two strategies such that f(σ)−˜ f(σ)1<δ/2kfor every k∈Nand every sequence σ=(p0s0pk−1sk−1) of predictions and outcomes. Then |R(T fX)−R(T ˜ fX)|<δfor every S-valued stochastic process X. Proof of Lemma 2(Sketch). Fix n. Then for every stochastic process X,thereexistsby Claim 1 astrategyfsuch that, for every sequence σ=(p0s0pk−1sk−1)of predictions and outcomes, f(σ) is the dirac atomic distribution on an element p∈M(k)(S) such that p−pXx1<δ/2k(notice that for Claim 1 to be applicable, M(k)must satisfy |S|/M(k) ≤δ/2k), where x=(s0sk−1)and pXx is given by (1). By Claim 2, it follows that R(TnfX)<+δ. By a minmax argument as in Sandroni (2003), it follows from the last observation that there is a prediction strategy fthat +δ-manipulates the test Tnand such that f(σ)∈(M(k)(S)) for every σ=(p0s0pk−1sk−1). Notice that the minmax argument works because Tncan be used to construct a zero-sum game with a finite set of strategies for each player. By Claim 1,fcan be approximated by a strategy ˜ fsuch that ˜ f(σ)∈K(k)(M(k)(S)) (notice that K(k) satisfies |S|M(k)+1/K(k) ≤δ/2k)and|˜ f(σ)−f(σ)|<δ/2kfor every σ= (p0s0pk−1sk−1),andbyClaim 3,˜ fis a strategy that ( +2δ)-manipulates Tn. Proof of Theorem 2.LetRn=M(0)(S) ×S×···×M(n−1)(S) ×Sbe the set of all possible sequences σ=(p0s0pn−1sn−1)of the n-stage past predictions and outcomes if the expert uses the strategy fas in Lemma 2,andletFn=(K(n)(M(n)(S)))Rn be the set of contingent mixtures in day ngivenpasthistorywhenthekth day’s mixture is restricted to K(k)(M(k)(S)).LetT⊆n≥0F0×···×Fnbe the finitely splitting tree of all elements fn=(f0fn−1)∈F0×···×Fn−1such that the following condition is satisfied: If gis an admissible strategy for which g(σ) =fk(σ) for every sequence σ∈Rk, 5Notice that here we assume that both strategies are mixtures over rational predictions, but not necessarily admissible.
Theoretical Economics 8 (2013) Expressible inspections 279 then g(+δ)-manipulates Tn.Wecallsuchastrategygan extension of fn. Notice that fndoes not define an admissible forecasting strategy—it does not define predictions for many partial histories; however, it is also true that for any realization, one extension of fnfails on Tnif and only if any other extension fails on Tn. The set Tis a tree, that is, if fn=(f0fn−1)∈T,thenfk=(f0fk−1)∈Tfor any k<n. This result follows from the fact that Tk⊆Tnand hence if any admissible strategy gthat extends fn( +δ)-manipulates Tn, then any admissible strategy gthat extends fk( +δ)-manipulates Tk. Note that to check whether an extension gof fn manipulates Tn, it is sufficient to check that the probability that an expert who uses fk to predict in day k(k=0n−1) will be rejected by day nis less than ( +δ) for every partial realization x=(s0sn). Since the number of such partial realizations is finite, it follows that Tis a decidable set. By Lemma 2, for every n,thetreeThas a node of length n. Therefore, by the Kreisel basis lemma, Tadmits an infinite branch (f0f1) that is computable relative to the halting problem. If gis the corresponding admissible strategy such that g(σ) =fk(σ) for every sequence σ∈Rkand g(σ) is the atomic dirac measure on the uniform distribution for other σ’s, then gis a strategy that ( +δ)-manipulates Tnfor every n.By(5), it follows that galso ( +δ)-manipulates T.Also,gis computable relative to the halting problem because the infinite branch (f0f1)is. References Al-Najjar, Nabil I., Alvaro Sandroni, Rann Smorodinsky, and Jonathan Weinstein (2010), “Testing theories with learnable and predictive representations.” Journal of Economic Theory, 145, 2203–2217. [265] Davis, Martin (2001), Engines of Logic. Norton, New York. [270] Dawid, A. Philip (1985), “The impossibility of inductive inference.” Journal of the American Statistical Association, 80, 340–341. [264,272] Dekel, Eddie and Yossi Feinberg (2006), “Non-Bayesian testing of a stochastic prediction.” Review of Economic Studies, 73, 893–906. [264] Fortnow, Lance and Rakesh V. Vohra (2009), “The complexity of forecast testing.” Econometrica, 77, 93–105. [265,272,277] Foster, Dean P. and Rakesh V. Vohra (1998), “Asymptotic calibration.” Biometrika, 85, 379–390. [264] Lehrer, Ehud (2001), “Any inspection is manipulable.” Econometrica, 69, 1333–1347. [264] Lehrer, Ehud (2003), “A wide range no-regret theorem.” Games and Economic Behavior, 42, 101–115. [268] Odifreddi, Piergiorgio (1989), Classical Recursion Theory, volume 125 of Studies in Logic and the Foundations of Mathematics. Elsevier, Amsterdam. [268,269,270,274]
280 Hu and Shmaya Theoretical Economics 8 (2013) Olszewski, Wojciech and Alvaro Sandroni (2008), “Manipulability of future-independent tests.” Econometrica, 76, 1437–1466. [264,268,274,278] Olszewski, Wojciech and Alvaro Sandroni (2009a), “A nonmanipulable test.” The Annals of Statistics, 37, 1013–1039. [264] Olszewski, Wojciech and Alvaro Sandroni (2009b), “Strategic manipulation of empirical tests.” Mathematics of Operations Research, 34, 57–70. [265] Sandroni, Alvaro (2003), “The reproducible properties of correct forecasts.” International Journal of Game Theory, 32, 151–159. [274,278] Sandroni, Alvaro, Rann Smorodinsky, and Rakesh V. Vohra (2003), “Calibration with many checking rules.” Mathematics of Operations Research, 28, 141–153. [264] Shmaya, Eran (2008), “Many inspections are manipulable.” Theoretical Economics,3, 367–382. [264,268,278] Submitted 2011-4-26. Final version accepted 2012-4-6. Available online 2012-4-6.