نظریه بازی استقراء: سناریوی اصلی

The aim of this paper is to present the new theory called “inductive game theory”. A paper, published by one of the present authors with A. Matsui, discussed some part of inductive game theory in a specific game. Here, we present a more entire picture of the theory moving from the individual raw experiences, through the inductive derivation of a view, to the implications for future behavior. Our developments generate an experiential foundation for game theory and for Nash equilibrium.

1.1. General motivations In game theory and economics it is customary to assume, often implicitly and sometimes explicitly, that each player has well formed beliefs/knowledge of the game he plays. Various frameworks have been prepared for explicit analyses of this subject. However, the more basic question of where a personal understanding of the game comes from is left unexplored. In some situations such as parlour games, it might not be important to ask the source of a player’s understanding. The rules of parlour games are often described clearly in a rule book. However, in social and economic situations, which are main target areas for game theory, the rules of the game are not clearly specified anywhere. In those cases, players need some other sources for their beliefs/knowledge. One ultimate source for a player’s understanding is his individual experiences of playing the game. The purpose of this paper is to develop and to present a theory about the origin and emergence of individual beliefs/knowledge from the individual experiences of players with bounded cognitive abilities. People often behave naturally and effectively without much conscious effort to understand the world in which they live. For example, we may work, socialize, exercise, eat, sleep, without consciously thinking about the structure of our social situation. Nevertheless, experiences of these activities may influence our understanding and thoughts about society. We regard these experiences as important sources for the formation of individual understanding of society. Treating particular experiences as the ultimate source of general beliefs/knowledge is an inductive process. Induction is differentiated from deduction in the way that induction is a process of deriving a general statement from a finite number of observations, while deduction is a process of deriving conclusions with the same or less logical content with well-formed inference rules from given premises. Formation of beliefs/knowledge about social games from individual experiences is typically an inductive process. Thus, we will call our theory inductive game theory, as was done in Kaneko and Matsui (1999). In fact, economic theory has had a long tradition of using arguments about learning by experiences to explain how players come to know the structure of their economy. Even in introductory microeconomics textbooks, the scientific method of analysis is discussed: collecting data, formulating hypotheses, predicting, behaving, checking, and updating. Strictly speaking, these steps are applied to economics as a science, but also sometimes, less scientifically, to ordinary peoples’ activities. Our theory formalizes some part of an inductive process of an individual decision maker. In particular, we describe how a player might use his experiences to form a hypothesis about the rules and structure of the game. In the starting point of our theory, a player has little a priori beliefs/knowledge about the structure of the particular game. Almost all beliefs/knowledge about the structure of the particular game are derived from his experiences and memories. A player is assumed to follow some regular behavior, but he occasionally experiments by taking some trials in order to learn about the game he plays. It may be wondered how a player can act regularly or conduct experiments initially without any beliefs or knowledge. As mentioned above, many of our activities do not involve high brow analytical thoughts; we simply act. In our theory, some well defined default action is known to a player, and whenever he faces a situation he has not thought about, he chooses this action. Initially, the default action describes his regular behavior, which may interpreted as a norm in society. The experimental trials are not well developed experiments, but rather trials taken to see what happens. By taking these trials and observing resulting outcomes from them, a player will start to learn more about the other possibilities and the game overall. The theory we propose has three main stages illustrated in Fig. 1: the (early) experimentation stage; the inductive derivation stage; and the analysis stage. This division is made for conceptual clarity and should not be confused with the rules of the dynamics. In the experimentation stage, a player accumulates experiences by choosing his regular behavior and occasionally some alternatives. This stage may take quite some time and involve many repetitions before a player moves on to the inductive stage. In the inductive derivation stage he constructs a view of the game based on the accumulated experiences. In the analysis stage, he uses his derived view to analyze and optimize his behavior. If a player successfully passes through these three stages, then he brings back his optimizing behavior to the objective situation in the form of a strategy and behaves accordingly.In this paper, we should stop at various points to discuss some details of each of the above stages. Since, however, our intention is to give an entire scenario, we will move on to each stage sacrificing a detailed study of such a point. After passing through all three stages, the player may start to experiment again with other behaviors and the experimentation stage starts again. Experimentation is no longer early since the player now has some beliefs about the game being played. Having his beliefs, a player may now potentially learn more from his experiments. Thus, the end of our entire scenario is connected to its start. While we will take one player through all the stages in our theory, we emphasize that other players will experiment and move through the stages also at different times or even at the same time. The precise timing of this movement is not given rigorously. In Section 7.2 we give an example of how this process of moving through these stages might occur. We emphasize that experiments are still infrequent occurrences, and the regular behavior is crucial for a player to gain some information from his experiments. Indeed, if all players experiment too frequently, little would be learned. We should distinguish our theory from some approaches in the extant game theory literature. First, we take up the type-space approach of Harsanyi (1967), which has been further developed by Mertens and Zamir (1985) and Brandenburger and Dekel (1993). In this approach, one starts with a set of parameter values describing the possible games and a description of each player’s “probabilistic” beliefs about those parameters. In contrast, we do not express beliefs/knowledge either by parameters or by probabilities on them. In our approach, players’ beliefs/knowledge are taken as structural expressions. Our main question is how a player derives such structural expressions from his accumulated experiences. In this sense, our approach is very different. Our theory is also distinguished from the behavioral game theories that fall under the terms of evolution/learning/experiment (cf., Weibull, 1995, Fudenberg and Levine, 1993 and Kalai and Lehrer, 1993; and more generally, Camerer, 2003) and the case-based decision theory of Gilboa and Schmeidler (1995). The behavioral game theories are typically interested in adjustment/convergence of actions to some equilibrium. They do not address questions on how a player learns the rules/structure of the game. Behavioral game theorists focus on the “rules of behavior”, i.e., “strategies”. Case-based decision theory looks more similar to ours. This theory focuses on how a player uses his past experiences to predict the consequences of an action in similar games. Unlike our theory, it does not discuss the emergence of beliefs/knowledge on social structures. Rather than the above mentioned literature, our theory is reminiscent of some philosophical tradition on induction. Both Bacon (1589) and Hume (1759) regard individual experience as the ultimate source of our understanding nature, rather than society. Our theory is closer to Bacon than Hume in that the target of understanding is a structure of nature in Bacon, while Hume focussed on similarity. In this sense, the case- based decision theory of Gilboa and Schmeidler (1995) is closer to Hume. Another point relevant to the philosophy literature is that in our theory, some falsities are inevitably involved in a view constructed by a player from experiences and each of them may be difficult to be removed. Thus, our discourse does not give a simple progressive view for induction. This is close to Kuhn’s (1964) discourse of scientific revolution (cf. also Harper and Schulte, 2005 for a concise survey of related works). 1.2. Treatments of memories and inductive processes Here, we discuss our treatment of memory and induction in more detail. A player may, from time to time, construct a personal view to better understand the structure of some objective game. His view depends on his past interactions. The entire dynamics of a player’s interactions in various objective games is conceptually illustrated in the upper figure of Fig. 2. Here, each particular game is assumed to be described by a pair View the MathML source(Γ,m) of an n-person objective extensive game ΓΓ and objective memory functionsView the MathML sourcem=(m1,…,mn). Different superscripts here denote different objective games that a player might face, and the arrows represent the passing of time. This diagram expresses the fact that a player interacts in different games with different players and sometimes repeats the same games.We assume that a player focuses on a particular game situation such as View the MathML source(Γ1,m1), but he does not try to understand the entire dynamics depicted in the upper diagram of Fig. 2. The situation View the MathML source(Γ1,m1) occurs occasionally, and we assume that the player’ behavior depends only upon the situation and he notices its occurrence when it occurs. By these assumptions, the dynamics are effectively reduced into those of the lower diagram of Fig. 2. His target is the particular situation View the MathML source(Γ1,m1). In the remainder of the paper, we denote a particular situation View the MathML source(Γ1,m1) under our scrutiny by View the MathML source(Γo,mo), where the superscript “o” means “objective”. We use the superscript i to denote the inductively derived personal view View the MathML source(Γi,mi) of player i about the objective situation View the MathML source(Γo,mo). The objective memory function View the MathML sourcemio of player i describes how the raw experiences of playing ΓoΓo are perceived in his mind. We refer to these memories as short-term memories and presume that they are based on his observations of information pieces and actions while he repeatedly plays ΓoΓo. The “information pieces” here correspond to what in game theory are typically called “information sets”, and they convey information to the player about the set of available actions at the current move and perhaps some other details about the current environment. Our use of the term “piece” rather than “set” is crucial for inductive game theory and it is elaborated on in Section 2. An objective short-term memory View the MathML sourcemio(x) for player i at his node (move) x consists of sequences of pairs of information pieces and actions as depicted in Fig. 3. In this figure, a single short-term memory consists of three sequences and describes what, player i thinks, might have happened prior to the node x in the current play of ΓoΓo. In his mind, any of these sequences could have happened and the multiplicity may be due to forgetfulness. We will use the term memory thread for a single sequence, and memory yarn for the value (“set of memory threads”) of the memory function at a point of time.One role of each short-term memory value View the MathML sourcemio(x) is for player i to specify an action depending upon the value while playing ΓoΓo. The other role is the source for a l ong-term memory, which is used by player i to inductively derive a personal view View the MathML source(Γi,mi). The objective record of short-term memories for player i in the past is a long sequence of memory yarns. A player cannot keep such an entire record; instead, he keeps short-term memories only for some length of periods. If some occur frequently enough, they change into long-term memories; otherwise, they disappear from his mind. These long-term memories remain in his mind as accumulated memories, and become the source for an inductive derivation of a view on the game. This process will be discussed in Section 3. The induction process of player i starts with a memory kit, which consists of the set of accumulated threads and the set of accumulated yarns. The accumulated threads are used to inductively derive a subjective game ΓiΓi, and the yarns may be used to construct his subjective memory function View the MathML sourcemi. This inductive process of deriving a personal view is illustrated in Fig. 4.In this paper, we consider one specific procedure for the inductive process, which we call the initial-segment procedure. This procedure will be discussed in formally in Section 4. 1.3. The structure of the present paper This paper is divided into three parts: Part I: Background, and basic concepts of inductive game theory. Sections 1, 2 and 3. Section 1 is now describing the motivation, background, and a rough sketch of our new theory. We will attempt, in this paper, to give a basic scenario of our entire theory. The mathematical structure of our theory is based on extensive games. Section 2 gives the definition of an extensive game in two senses: strong and weak. This distinction will be used to separate the objective description of a game from a player’s subjective view, which is derived inductively from his experiences. Section 3 gives an informal theory of accumulating long-term memories, and a formal description of the long-term memories as a memory kit. Part II: Inductive derivation of a personal view. Sections 4, 5 and 6. In Section 4, we define an inductively derived personal view. We do not describe the induction process entirely. Rather, we give conditions that determine whether on not a personal view might be inductively derived from a memory kit. Because we have so many potential views, we define a direct view in Section 5, which turns out to be a representative of all the views a player might inductively derive (Section 6). Part III: Decision making using an inductively derived view. Section 7, 8 and 9. In this part, we consider each player’s use of his derived view for his decision making. We consider a specific memory kit which allows each player to formulate his decision problem as a 11-person game. Nevertheless, this situation serves as an experiential foundation of Nash equilibrium. This Nash equilibrium result, and more general issues of decision making, are discussed in Sections 7 and 8. Before proceeding to the formal theory in Section 2, we mention a brief history of this paper and the present state of inductive game theory. The original version was submitted to this journal in January 2006. We are writing the final version now two and a half years later in July 2008. During this period, we have made several advancements in inductive game theory, which have resulted in other papers. The results of the present paper stand alone as crucial developments in inductive game theory. Nevertheless, the connection between the newer developments and this paper need some attention. Rather than to interrupt the flow of this paper, we have chosen to give summaries and comments on the newer developments in a postscript presented as Section 9.3.

We have given a discourse of inductive game theory by confining ourselves to clear-cut cases. It would be, perhaps, appropriate to start this section with comments on our discourse. Then we will discuss some implications for extant game theory. 9.1. Comments on our discourse We have made particular choices of assumptions and definitions for our discourse. One important methodological choice is to adopt extensive games in the strong and weak senses for objective and subjective descriptions. First, we will give some comments on this choice, and then, we will discuss the definition of an inductively derived view given in Section 4 based on the initial segment procedure. As pointed out in Section 4, an extensive game contains observable and unobservable elements. The nodes with the successor relation are unobservable for the players and even for the outside observer, in which sense those are highly hypothetical. The components in a memory kit are all observables and actually observed. Thus, our definition of the inductive derivation of a personal view from a memory kit extends the observed observables by adding hypothetical elements. This may be interpreted as an “inductive” process of adding unobservable elements to observed data. However, this freedom of adding hypothetical elements leads us a proliferation of possible views. To prevent this proliferation, we need some criterion to choose a view from many possible ones. In this paper, we have used the concept of a g-morphism (game theoretical p-morphism) to choose a smallest one. Conceptually speaking, the choice of a personal view is supposed to be done by a player, rather than us. While the definition of an inductive derivation allows many views, a player cannot construct a large one because of his bounded cognitive ability. Thus, the criteria of smallness and constructiveness are important from this point of view. The direct view defined in Section 5 has a constructive nature as well as being a smallest one for a given memory kit. In this sense, the direct view has a special status among those possible views. Nevertheless, Definition 4.1 may admit no inductively derived views for a given memory kit, as characterized by Theorem 5.1. In fact, the initial segment procedure adopted in Definition 4.1 still gives a strong restriction on the addition of hypothetical elements. If we allow more freedom in using hypothetical elements in an inductive derivation, we could avoid the nonexistence result. For example, if we allow a player to add “nature nodes” to his personal view, we could even avoid the use of an extensive game in the weak sense. On the other hand, this creates vast arbitrariness in inductive derivations; and we expect serious difficulties in finding natural criteria to narrow down the use of “nature nodes”. Until we find natural criteria, we should refrain from the cheap use of “nature nodes”. The above conclusion may sound negative to any extension of our definition of an inductive derivation, but we have different opinions. We could actually have a more general procedure to construct a personal view than the initial segment procedure. Since this paper is intended to provide an entire scenario, we have chosen the initial segment procedure as a clear-cut case. In separate papers, we will discuss less restrictive definitions. See Section 9.3. Another comment should be given on the choice of extensive games. In fact, we can avoid the adoption of extensive games; instead, the present authors (Kaneko and Kline, in press-a) have developed a theory of information protocols, which avoids the use of nodes and describes game situations directly in terms of information pieces and actions together with a history–event relation. If we adopt this theory, then we could avoid a proliferation of personal views generated by the use of hypothetical nodes. In the theory of information protocols it may be easier to discuss extensions of inductive derivations. One reason for our adoption of extensive games here is their familiarity within our profession. The choice of extensive games makes the distinction between observables and unobservables explicit, which is another reason for our choice. We expect gradual developments of inductive game theory to come about by deeper analysis and alternative approaches to the various stages mentioned in the diagram of Fig. 1. By such gradual developments, we may find natural criteria for steps such as the use of nature nodes, and some experimental tests of inductive game theory. 9.2. Some implications to extant game theory It is a main implication of our discourse that a good individual view on society is difficult to construct from the experiential point of view: there are many places for a player to get stuck in his inductive process and analysis process. Nevertheless, we gave a characterization theorem of Nash equilibrium in Section 7. Here, we discuss some other implications to extant game theory and economics chiefly with respect to Nash equilibrium. There are various interpretations of Nash equilibrium (cf. Kaneko, 2004, Act 4). Nash (1951) himself described his concept from the viewpoint of purely ex ante decision making, but in economic applications, it is typically more natural to interpret Nash equilibrium as a strategically stable stationary state in a recurrent situation. The characterization given in Section 7 is along this line of interpretations, including also ex ante decision making in a player’s constructed personal view. To reach Nash equilibrium, which may not be the case, it takes a long time. Also, the process of trial and error may not allow all possible available actions. The Nash equilibrium reached should be regarded as a Nash equilibrium in the game with respect to the actually experienced domains. Thus, the characterization of Nash equilibrium in Section 7 should not merely be interpreted as a positive result. It means that the characterization would be obtained if all those processes go through well and if reservations about restrictions on trials are taken into account. From the same point of view, the subgame perfect equilibrium of Selten (1975) involves even deeper difficulties from our experiential point of view, which was already pointed out in Kaneko and Matsui (1999). The reason is that subgame perfection requires higher order experimentations. When one player deviates from his regular behavior, other players in turn need, again, to make experimentations from regular behavior. This second or higher order experimentation is already problematic and violates some principles discussed in the informal theory in Section 3.2. In fact, a similar criticism is applied to Nash equilibrium, as already stated. Nash equilibrium itself is regarded as one limit notion, and subgame perfection is a higher limit one. Taking the above criticism seriously, one important problem arises. The complexities, in a certain sense, of an inductively derived view as well as of experimentations are measured and restricted. In the epistemic logic context, Kaneko and Suzuki (2005) introduced the concept contentwise complexity, which measures “contentwise complexity” of a single instance of a game. This notion can be converted to our inductive game theory. Then, we will be able to give restrictions on individual views as well as experiments. In this manner, our inductive game theory will be developed in the direction of “bounded rationalities”. We have restricted our attention to the purely experiential sources. In our society, usually, we have different sources of beliefs/knowledge such as from other people or through education. These suggest that a player may get more beliefs/knowledge on the social structure, but do not suggest that he can guess other people’s thinking, which has usually been assumed in the standard game theory (cf., Harsanyi, 1967 for incomplete information game and Kaneko, 2002 for the epistemic logic approach). At least, the assumption of common knowledge is far beyond experiences. If we restrict interpersonal thinking to very shallow levels, deductive game theory may have some connections to inductive game theory (cf. Kaneko and Suzuki, 2002 for such a direction of deductive game theory). 9.3. Postscript By now, several new developments along the line of the scenario given in this paper have been made in Kaneko and Kline, 2007a, Kaneko and Kline, 2007b and Kaneko and Kline, 2008 and Akiyama et al. (in press). We use this postscript section to present some small summaries of those papers to help the reader catch up to the present state of inductive game theory. The main concern of Kaneko and Kline (2007) is the size of an inductively derived view for a player with bounded cognitive abilities. If the objective situation is too large, a player may have difficulty: (1) analyzing it strategically; and (2) accumulating enough experiences to have a rich view. The premise of that paper is that the number of experiences and the size of a view must be small for it to be managed by a player. The concept of “marking” some parts and actions as important was introduced in that paper and shown to be successful in allowing a player to obtain a manageable, though potentially biased, view. As already mentioned in Section 9.1, Kaneko and Kline (2007b) introduced a new construct called an “information protocol”, based on “actions” and “information pieces” as tangible elements for each player rather than hypothetical non-tangible concepts such as nodes. This approach gives a more direct and simpler description of a game situation from the perspective of a player. It has another merit to classify extensive games in a more clear-cut manner. With an appropriate choice of axioms, it fully characterizes an extensive game in the weak and strong senses. It also enables us to avoid g-morphisms, since we have no multiplicity in i.d.views caused by hypothetical nodes and branches. The theory of information protocols has been adopted in our more recent research including Kaneko and Kline (2008). Kaneko and Kline (2008) took up that task of constructing i.d.views with more partiality in a players memory. Accordingly, the definition of an i.d.view had to be weakened to admit a view. By these generalizations, the induction becomes less deterministic and we meet some multiplicity of consistent views with a given set of memories. The interactions between a player’s i.d.view, his future behavior, and future views become the topics of this paper and also serve as potential sources for resolving the multiplicity problem. Finally, Akiyama et al. (in press) took a computer simulation approach in order to look into the process of experiencing and memorizing experiences in a one-person problem called “Mike’s bike commuting”. That paper tries to clarify the informal theory of behavior and accumulation of memories discussed in Section 3.2 of this paper. The simulation approach is based on finite experiences and accumulations of memories. The use of “marking” introduced in Kaneko and Kline (2007a) was found to be crucial for obtaining a rich enough view. These developments are, more or less, consistent with the scenario spelled out in this paper and give more details into each step in the basic scenario. We are presently continuing our research along those lines making progress into experiential foundations of beliefs/knowledge on other players’ thinking.