The Applications of Automata in Game Theory

Introduction

Any problem with interacted participants and actions can be treated as a game. When car drivers put a plan to drive in heavy traffic, they are actually playing a driving game. When users bid on bidding-based Websites, they are actually playing an auctioning game. In election, choosing the platform is a political game. The owner of a factory deciding the price of his product is an economic game. Obviously, game theory can be presented in wide range of applications.

Game theory is a mathematical tool that can analyze the interactions between individuals strategically. The interactions between agents, who may be individuals, groups, firms are interdependent. These interdependent interactions are controlled by the available strategies and their corresponding payoffs to participants. However, game theory studies the rational behavior in situations involving interdependency (McMillan, 1992). Therefore, game theory will only work when people play games rationally and it will not work on games with cooperational behavior.

Generally, the game consists of the following entities:

• •

  Players: Where one side of the game tries to maximize the gain (payoff), while the other side tries to minimize the opponent’s score. However, these players can be humans, computer applications or any other entities.

• •

  Environment: This includes board position and the possible moves for the players.

• •

  Successor Function: The successor function includes actions and returns a list of (move, state) pairs, where each pair indicates a legal move and the resulting state.

• •

  Terminal Test: The terminal test specifies when the game is over and the terminal state is reached.

• •

  Utility Function: The utility function is the numeric value for the terminal states.

The scientists of inter-disciplinary community believe that the time has come to extend game theory beyond the boundaries of full rationality, common-knowledge of rationality, consistently aligned beliefs, static equilibrium, and long-term convergence (Izquierdo, 2007). These concerns have led various researchers to develop formal models of social interactions within the framework of game theory.

The first formal study of games was done by Antoine Cournot in 1838. A mathematician, Emile Borel suggested a formal theory of games in 1921, which was extended by another mathematician John von Neumann in 1928. Game theory was established as a field in its own right after the 1944 publication of the monumental volume Theory of Games and Economic Behavior by von Neumann and other economists. In 1950, John Nash proved that finite games have always have an equilibrium point, at which all players choose actions which are best for them given their opponents’ choices. This concept has been a basic point of analysis since then. In the 1950s and 1960s, game theory was extended and developed theoretically and applied to problems of war and politics. Since the 1970s, it has created a revolution in economic theory. Moreover, it has found applications in sociology and psychology, and found links with evolution and biology. Game theory received special attention in 1994 with the awarding of the Nobel Prize in economics to Nash (Almanasra, 2007).

The attractive point in studying games is that models used in games are applicable to be used in real-life situations. Because of this, game theory has been broadly used in economics, biology, politics, low, and also in computer sciences. Examples on the use of game theory in computer science include interface design, network routing, load sharing and allocate resources in distributed systems and information and service transactions on Internet (Platkowski & Siwak, 2008).

One of the crucial factors which affect the performance of players in a given game is the behavior (strategy) representation. We found that different techniques are used to represent players' behavior in different games. One of the successful techniques is the use of automata-based model to represent and control participated agents. In the next sections, we will discuss different types of automata and their affect on games.