عقلانیت / شماره پذیری تجارت کردن در بازی های محدود

The computability of Nash equilibrium points of finite strategic form games is examined. When payoffs are computable there always exists an equilibrium in which all players use computable strategies, but there can be no algorithm that, given an arbitrary strategic form game, can compute its Nash equilibrium point. This is a consequence of the fact, established in this paper, that there is a computable sequence of games for which the equilibrium points do not constitute a computable sequence. Even for games with computable equilibrium points, best response functions of the players need not be computable. In contrast, approximate equilibria and error-prone responses are computable.

The notion of an algorithmically computable or recursive function was formalized in the 1930s, with important contributions being made by Church, Gödel, Kleene, Markov, Post, Rosser, Turing and others.1 A surprising implication of this formalization is that there are problems that are algorithmically unsolvable, a famous example being Matiyasevich’s resolution of Hilbert’s tenth problem (see Matiyasevich, 1993). A number of papers have recently sought to examine the computability of equilibrium in Economics and Game Theory (e.g. Lewis, 1988, Prasad, 1991, Prasad, 1997, Richter and Wong, 1999, Tsuji et al., 1998, Velupillai, 2000 and Velupillai, 2002). In this paper, I examine the computability of equilibrium for finite games, adopting a framework for computable analysis based on classical recursion theory. The key notion, for the results of this paper, is that of a computable real number. This is a number that can be approximated, to any desired degree of precision, using a finite set of instructions. It is well known that there are points of the classical real line that are not computable (Turing, 1936).2 However, all rational numbers and many irrational numbers (e.g. all algebraic numbers, and transcendental numbers such as e and ππ) are computable. In finite strategic form games, payoffs are given as real numbers and player strategies are typically real vectors. If payoffs are allowed to be uncomputable, it becomes quite easy to present games with uncomputable equilibrium points. The pertinent question is whether equilibrium strategies continue to be computable when payoffs are computable. Nash’s theorem states that any finite game will have at least one equilibrium point (Nash, 1951). This paper starts by showing that if payoffs are computable then there is at least one equilibrium in which each player uses computable strategies. In contrast, once we leave the framework of finite games, it is possible to construct examples of games (Specker, 1959) for which the only equilibrium strategies are uncomputable real numbers. The result gives us no indication that we will be able to compute an equilibrium using the information contained in the strategic form (viz. a list of players, their available strategies, and the real payoffs at each profile of strategies). As it turns out, there cannot exist an algorithm capable of computing an equilibrium point for every instance of a game, even when payoffs are computable. This negative result is a consequence of the fact that there exists a computable sequence of games for which the equilibrium points do not constitute a computable sequence. A logically separate question is how an equilibrium is reached. It is typically asserted that some form of evolution, learning, or introspection leads to an equilibrium being played. The computability literature argues that a minimal requirement for attainability of equilibrium is that there exist some algorithm that, given the complete description of a game, computes an equilibrium point, but it is not clear that computability would be sufficient for attainability. Some theories of learning in games, such as fictitious play, begin with past history of play as the informational basis for a conjecture about opponents’ play. Players then choose a best response to the historical frequency of actions of their opponents. In the same spirit, one may ask if players can choose a best response to computable conjectures about opponent play. The answer is in the negative. Proposition 3, on the failure of computability of best responses for sequences, shows that an individual’s strategy in equilibrium cannot be computed from equilibrium strategies of other players (even when the equilibrium itself is computable). This casts serious doubt on our ability to develop a general theory of learning to play Nash equilibrium strategies. On the positive side, there do exist algorithms that can compute approximate equilibrium points (strategy profiles in which deviation could be profitable, but the gains are bounded above by some View the MathML sourceɛ∈R). In fact, this is all that algorithms such as those of Scarf can be guaranteed to produce (although they will sometimes produce equilibrium points). One can also define classes of games (e.g. games with unique Nash equilibria), for which equilibrium is computable, but in this case, there is no effective procedure to determine whether an arbitrary game has a unique Nash equilibrium or not. This paper sorts through what we can and cannot compute, examining the implication of these ideas for economic behavior. If we require strategies to be computable from the strategic form of the game, these results present the following trade-off. One may either assume that agents are content with near-optimal decisions (and play an ɛɛ-equilibrium) or else assume they use procedures that produce equilibria for only a subset of the possible games they might encounter. In a somewhat different approach, individuals may be prone to error when making decisions. A number of bounded rationality models (e.g. Rosenthal, 1989 and McKelvey and Palfrey, 1995) proceed by assuming that players play suboptimal strategies with small probability. In contrast to best-response play, such error prone responses will often be computable in terms of the strategies of other players. 1.1. Related literature The first relevant result is a famous example by Specker, who shows that there are continuous (and computable) functions on [0,1][0,1] that have uncountably many maximum points, but do not attain a maximum at any computable point of [0,1][0,1]. Since a maximization problem is a one-player game, this is enough to establish that equilibria in games need not be computable. In a finite game where a player has two actions and can choose mixed strategies, the strategy space is [0,1][0,1], but payoffs are a linear function of strategies. In this case Specker’s construction does not apply, and we get a positive result; there is at least one computable maximum point. Proposition 1 proves the general case: any finite game has at least one computable equilibrium point. Much of the literature on computability has focused on failures of algorithmic solvability. Lewis demonstrates this for N-player games but, as best I can tell, allows arbitrary (and not just linear) payoff functions on the strategy space. 3 Tsuji et al. consider games with finite strategy sets. Sofronidis (2004) demonstrates undecidability of the existence of pure Nash equilibria. Prasad (2004) shows that Nash’s theorem fails in constructive frameworks, such as Bishop’s, that do not assume the law of the excluded middle (see Bridges and Richman, 1987). The present paper adopts an approach based on classical recursion theory (specifically, the framework of Pour-El and Richards), where the constructive failure of Nash’s theorem appears as an uncomputability result for sequences ( Proposition 2). 4 An advantage of the present approach lies in its being easily extensible to the best-response problem and to approximation. The result on quantal responses in Section 3 is, as far as I am aware, new. The papers by Richter and Wong (1999) and Velupillai (2002) are closest to mine in approach, but their focus is on the general equilibrium existence problem. The central point of this paper, the terms of the rationality/computability trade-off, appears not to have been made before.