Finite Automata Games: Basic Concepts

Finite Automata Games: Basic Concepts

Fernando S. Oliveira (ESSEC Business School, Singapore)
Copyright: © 2014 |Pages: 9
DOI: 10.4018/978-1-4666-5202-6.ch088

Chapter Preview



Automata based systems have been used extensively in complex business modeling, for example, to represent Markov systems (e.g., Stewart et al., 1995; Uysal & Dayar, 1998; Gusak et al., 2003; Fuh & Yeh, 2001; Sbeity et al., 2008), in the development of classification systems (Gérard et al., 2005), in the analysis of commuters behavior (van Ackere & Larsen, 2004), to design electricity markets (Bunn & Oliveira, 2007, 2008), in the planning of real-options (Oliveira, 2010a), to study human-computer interaction (Gmytrasiewicz & Lisetti, 2002; Altuntas et al., 2007; Kim et al., 2010; Muller et al., 2013), to represent the relationship between emotions and reason (Oliveira, 2010c), in devising product differentiation strategies (Oliveira, 2010b), and in forecasting and production control (Liu et al., 2011).

The analysis of the behavior of such systems is very often based on the concepts of game theory, such as Nash equilibrium (e.g., Fudenberg & Tirole, 1991). The Nash equilibrium is a powerful tool for analyzing industries where there are strategic interdependences between players. However, it does not explain the process by which decision makers acquire equilibrium beliefs, failing to determine a unique equilibrium solution in many games, and, therefore, failing to predict, or prescribe, rational behavior (e.g., van Huyck et al., 1990; Samuelson, 1997; Fudenberg & Levine, 1998).

In games with multiple equilibria the Nash equilibrium fails to predict the players’ behaviors. In this case, empirical studies (e.g., Roth & Erev, 1995) have shown that models of bounded rationality predict better than the Nash equilibrium does how people, organizations and markets behave (at least in the short run). A first attempt from the game theory literature to address this issue was to refine the concept of Nash equilibrium by including additional criteria. First, a player does not choose dominated strategies (Fudenberg & Tirole, 1991, p. 8). Second, choices in information sets not in the equilibrium path must be optimal choices (in order to avoid non-credible threats). This is called the rationalizability criterion (Bernheim, 1984; Pearce, 1984). However, the problem with equilibria selection still exists as different refinements select different equilibria. Furthermore, rationalizable strategies may be too demanding as they assume common knowledge of rationality.

Therefore, in order to model complex games, possibly with multiple equilibria, computer models which incorporate boundedly rational players are used as a mechanism for inductive equilibrium selection, and to test the validity of the perfect-rationality predictions. This methodological jump from perfect-rationality to bounded rationality has theoretical and philosophical implications. It corresponds to a switch from a “normative theory” to a “positive theory.” The normative theory prescribes what each player in a game should do in order to promote his interests optimally (von Neumann & Morgenstern, 1953; van Damme, 1991, p. 1), whereas the positive theory describes how agents actually decide, as this line of research tries to understand how people and institutions behave (e.g., Samuelson, 1997, p. 3).

Key Terms in this Chapter

Automaton: It is a decision rule, or a strategy, consisting of a finite set of states, a transition function (that defines the rules of transition between states) and a behavioral function (defining an agent’s behavior in each state of the automaton).

Automata Inference: The player attempts to learn the automata that can better describe the rules of behavior used by the process he interacts with or employed by a given opponent or set of opponents. Automata learning includes the observation of the inputs and outputs produced by a given system and, from these data, the estimation of the states in the automaton and respective behavioral and transition functions. There are two types of inference processes, active and passive learning, depending on how much control the player has on the inputs to the system (or opponent) he is observing.

Passive Learning: It is the process used by an agent to learn the automaton representing the behavior of a different system when he has no control over the inputs supplied to an automaton. In this case the agent is a passive observer of the behavior of the system without interacting with it.

Automata Game: It is a game in which the players’ strategies are rules of behavior encapsulated in an automaton that describes how the agent behaves in each state and how he reacts to changes in his environment. The automata employed by the agents may have been the result of an optimization procedure at the start of the game or have evolved through learning over time.

Nash Equilibrium of the Automata Game: It is a state of the automata game in which the choice of automaton by each player is such that no player can increase his payoff by unilaterally changing his automaton.

Best Response Automaton: It is the rule of behavior (composed by the internal states and by the behavior and transition functions) that maximizes the expected utility received by the automaton when employed against a given opponent’s automaton.

Active Learning: During the process of automata inference the player needs to estimate the internal states of the process observed (together with the respective behavioral and transition functions) by observing the sequence of inputs and outputs. If the player has control over the inputs provided to the automaton generating the data we have an active learning process.

Complete Chapter List

Search this Book: