Comprehensive Survey On Automata Based Game Theory Computer Science Essay

Published:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Abstract- in recent years, Game Theory and Decision Theory were tightly related to the field of Artificial Intelligence through the use of intelligent agents. In Game Theory, the interactions between several agents, who may be individuals, groups, firms are interdependent. These interdependent interactions are controlled by the available strategies and payoff to participants. Finite Automata is one way for representing players' strategies in Game Theory. In this paper we study and analyze the representations of games' strategies in the field of game theory and show how games can adapt several strategies using finite automata and its variances.

Keywords: Game Theory; Prisoner's Dilemma; Evolutionary Algorithms; Finite Automata; Adaptive Automata.

Introduction

Game Theory is a mathematical tool that can analyze interactions between individuals strategically. In recent years, Game Theory and Decision Theory were tightly related to the field of Artificial Intelligence through the use of intelligent agents. The interdependent interactions between several agents are controlled by the available strategies and payoff to participants. Prisoner's Dilemma is the best known example of social Dilemmas. It has various applications where individual's defections at the expense of others lead to overall less desirable outcomes. Examples of its application includes

arms races, litigation instead of settlement, environmental pollution, or cut-price marketing. Prisoner's Dilemma is a symmetric game with a transparent payoff matrix, where both players can act simultaneously without knowing the other's action. Finite Automata is one way of representing players' strategies in Game Theory. A Finite automaton has a set of states, variables (control variables) and one or more external stimulus (inputs). There are two types of Finite Automata, Deterministic and Non-Deterministic. In this paper we aim to show that by using the combination of finite automata and evolutionary algorithms (EAs), flexible and powerful negotiating agents can be obtained. In this regards, the finite automata permit the negotiating agents to have different behaviors against each others. By using EAs the agents' negotiating strategies which have finite automata can be adapted continuously in order to produce efficient strategies during the time.

Game Theory

The expression 'Game Theory' was created by Von Neumann and Morgenstern in 1944. Since then, the applications of Game Theory are found in economics, politics, biology, computer science, psychology and sociology. Game Theory provides a language to formulate structure, analyze, and understand strategic scenarios [5]. In Game Theory, the actions of several agents are interdependent. These agents may be individuals, groups, firms, or any combination of these. Generally, the game consists of the following entities [6]:

Agents (players): where one side of the game tries to maximize the gain (payoff) while the other side tries to minimize the opponent's score.

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.

Objective (terminal test): the terminal test specifies when the game is over and the terminal states.

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

The study of game theory concepts provides a useful example of a perspective on mathematics from which mathematical frameworks, as well as associated concepts, are seen as being value-laden [p1]. Game theory has been applied several applications in economics; it has been used in studying competition for markets, advertising, and planning under uncertainty [p1]. Also the game theory is now finding its applications in computer science. It has been used in interface design; discourage understanding, network routing, load sharing, resource allocation in distributed systems and information and service transactions on internet. So because all these applications in that the best reason to study games is that games can be used to model many real-life situations. And achieve the individual goals and maximize the individual payoffs.

PRISONER'S DILEMMA

Prisoner's Dilemma models the story of two prisoners held suspect of a serious crime. If one of the prisoners testifies, or becomes a witness, against the other, he will be rewarded, or goes free (a payoff of 5), whereas the other will serve a long prison sentence, or ten years (payoff 0). On the other hand, if both testify, their punishment will be relatively less, five years each (payoff 1 for each). However, if they both "cooperate" with each other by not testifying at all, they will only be imprisoned for a short term. For example for illegal weapons possession (the payoff will be 3 for each) as shown in Figure 1.

Figure1. Prisoner's Dilemma game[18]

The game-theoretic justification of Prisoner's Dilemma on individual sides is sometimes taken as a case for treaties and laws, which impose cooperation. However, there is some "inefficiency" of the outcome of the Prisoner's Dilemma game. For example, the game is fundamentally changed by playing it more than once and the payoffs matrix can be a subject to change.

Anyway we particularly focused on models that can be used for simulation of Prisoner's Dilemma, and we showed how existing models and algorithms can be used with automata for representing the behaviors of players.

The benefit of surveying on the Prisoner's Dilemma is that it models situations where there is competition between the advantage of each player and the advantage of the group. It, also, makes a useful framework for manifesting the significance of decision-making in ethical way by social environment.[4]

The Prisoner's Dilemma is a situation that is best identified as a problem in Game Theory which goes to show that two people or groups of people may not choose to cooperate even though it would be the good situation or best benefit to do so.

It is Important to say that our purpose is to make available the environment and data to permit readers to lead researches into the newest developments about the prisoner's dilemma [موقع].

Evolutionary Computation(EC) and Evolutionary Algorithms(EAs)

Evolutionary Computation has been applied in several games. The utilization of EC could lead to better game playing and reducing development costs, and hence it could help finding or exploring better game strategies [30]. Games are still a tremendously active area of research in diverse areas such as biology, economics and bargaining, as well as evolutionary computation. Recently, EC methods have been applied to evolve all kinds of game-players, including real-time games and console games. The latest approach of EC is to generate opponents that are more interesting and fun to play against, rather than being necessarily superior [5].

Evolutionary Algorithms are a kind of stochastic search and optimization heuristics [40]. Today, EAs successfully used for solving numeric problems, such as optimization, automatic programming, and so on [41]. There are several EAs techniques, but we found that the Evolutionary Programming, Evolution Strategies, Genetic Algorithm and Genetic Programming have a conceptual base for simulating the evolution of individual structures by the well-known processes such as selection, mutation and reproduction. Their importance is coming from their abilities in optimizing complex function. However, the use of EAs will enable agents to choose the best actions in order to achieve the highest payoffs, which in turn will lead to the optimal strategy.

There are various applications of Evolution Algorithms in Game Theory that appeared in the literature. Periaux et al. presented two works on applying GA-based approaches to solve different optimization problems. In their first work [51], Periaux applied GA approach on DDM-nozzle optimization problems (Domain Decomposition Method-nozzle).

More interesting GA-approaches in Game Theory were presented by Macy [56] and Phelps [57]. Macy has used evolutionary Game Theory to study the viability of cooperation in a predatory world. The work is differentiating the selection and learning processes whether hard-wired or soft-wired based on the organism that carries them. However, the differentiation was operationalized by using artificial neural network. Phelps has considered the use of evolutionary optimization with a principled game-theoretic analysis for automatic double-auction strategies acquirement. His approach relies on utilizing GA for searching for a hitherto-unknown best response.

AUTOMATA

An automaton (plural: automata or automatons) is a self-operating machine. Where the output behavior is a combination between the consequence of the current input with the history of the machine's previous input. There are many types of well known automata, such as Finite automata, Turing machines, Push-down automata, Linear-bounded automata as well as other variations such as random access machines, parallel random access machines, arrays automata.

Although the automata theory has an old history in computer science, there is a re-establish attention in this subject in today world. two main aspects of automata theory are considerably under investigation: nonstandard models and descriptional complexity. Nonstandard models of automata such as, self-verifying [2], probabilistic [18], Las Vegas [7], and quantum [12, 16], which are different from classical models evolution rules and/or in the accepting situations. In descriptional complexity formal systems are compared concerning their conciseness. There are several kinds of finite automata in the literature such as, one-way or two-way, deterministic or nondeterministic, and so on [24].

Finite automaton is one of the oldest and well studied computation models in theoretical computer science. [L5]

[ppt02]Finite automata have finite memory which is fixed beforehand. According to the input series which may be long or short, complex or simple, the finite automata must take its decision by using the same fixed and finite memory.[ppt02] The basic model is called the deterministic finite automaton (DFA). However in deterministic automaton cannot be in more than one state in any time. But in one non-Deterministic Automaton the machine can be in two or more states at any time. From the other perspective, DFA can be NFA (with restrictions) but the converse is not true. The DFA can be shown in special two ways: Graph-based representation scheme which is often called the Transition Diagram and this way is good for construction and for visualizing behavior. And another way called Table-based transition-listing scheme known as the 'Transition Table'. This way is good for computer simulation and for applying certain of algorithms. The main difference between the NFA and DFA is in the 'type of the value' which is returned by the Transition Function in case of NFA.

So we can describe importance of Automata during the game by players. They should be able to deal against different agents with different strategies in a successful way. And, also they should be capable of adapting their strategies to negotiate with various agents who have various attitudes.

Applications of Automata

Many of classical techniques can be replaced by Artificial Intelligence techniques in order to model environmental systems. Some of these processes and their environmental applicability are reviewed with examples and a reference list in this paper. The intelligence techniques consist of some techniques such as, cellular automata, multi-agent systems, Evolutionary Algorithms [L6]. So there are a lot of applications illustrating how to use automata to represent the strategies for agents.

Applications of finite automata.

We will display the works of some researchers have making models to represent the players and their behavior by showing the integration between EAs and Automata can facilitate the negotiation between different gents (with different behaviors) within the same environment. Such as [Inacio and Jaime] they work presents the results of experiments made with a spatial evolutionary model of agents playing the N-Players Prisoner's Dilemma, by using two different ways to represent the agent's strategies finite automata and adaptive automata. Finite automata can represent simple strategies, the components of finite automata to represent set of states, initial state, transitions function. On the other hand, they used the adaptive automata to represent complex strategies by using adaptive functions, it associated to some transitions of the automata. These functions can add or remove states and transitions to the automata while it is used. Also it includes the one of finite automata, because when removing adaptive functions of them we get finite automata. This is an important characteristic that makes possible to use them naturally where the finite automata are used. So, the comparison of their results obtained in both simulations showed that there was a fast convergence for a situation of broad cooperation between the agents, obtained in both cases through strategies of revengeful behavior: the cooperation is kept while all the participants cooperate.

Also, we can see in [L5] the problems of learning and organizing the strategies in infinitely repeated games, such as prisoner's dilemma, Matching Pennies, and so on. Their introduced dynamic system where agents can begin the game with any possible strategies with are represented by finite state automata and are allowed to clearly change their strategies during their playing [L5].

[Lindgren and Nordahl 1994] use the genetic algorithms and strategies with changeable memory size inside their model where the agents play Prisoner's Dilemma. Finite State Machines (FSMs), which have easy structure and maintenance, are widely used in video games to complement Artificial Intelligence. In any problem which requires finite number of solutions, FSMs are definitely an easy method to be approached.

On the other hand, after we examined some of the models used the finite automata in known environment , but now we observed that recent researchers have used unknown environments for their models,, because they have used a new expression called "learning finite automata". As an instance, the aim of [3] of their model was to show the benefit of the finite learning automata which help to agents to find the action that minimizes the expected number of penalties received, or maximizes the expected number of payoffs received.

Applications of Cellular Automata

On the other hand, we found many researchers using other type of automata called Cellular Automata (CA) are dynamic models. A cellular automaton is ''an array of identically programmed automata, or cells which interact with one another in a neighbourhood and have definite state". They can be complex systems themselves, and offer good ways of studying the behavior of such systems [10]. So we will give an overview of existing models and algorithm that are useful for analyzing or achieved desired dynamics of a complex system, e.g., cellular automata, evolutionary algorithm and so forth, Such as [N8] they used the cellular automata to simulate agents with different strategies. And they had been shown the ability of co-evolutionary learning that is using to evolve cooperative strategies in structured populations using the N-player Iterated Prisoner's Dilemma (NIPD). Also they examined the effects of both fixed and random neighbourhood structures on the evolution of cooperative behavior in a lattice-based NIPD model. [sally and et.al,] defined a cellular automaton as a collection of cells arranged in a grid where each cell inside changes state as a function of time according to a defined set of rules that includes the states of neighboring cells. Also each of those cells contains an "automaton", a finite state machine. The resulting construct is a space filled with cells, each of those cells containing a finite state machine. They said "a cell has a state", meaning the state where the cell finite state machine is in the grid. It has been used for studying the evolution of cooperation between the players in the games by means of computer modeling. Cellular automata occur in various natural systems.

In [a2] they also simulated their own method by using cellular automata with some approaches for agents programming, such as artificial intelligence, automata modeling, distributed computing, swarm intelligence and genetic algorithms to solve complex systems. Also they developed their own method, based on agent-based modeling for complex systems using automata with multiplicities.

We can conclude the benefit from representation the environments for N-players prisoner's dilemma models by cellular automata, because most of the researchers need it for distinguishing the effects of neighbourhood structure on the evolution of cooperative behavior for N-players models. Such as [N6] they simulated the N-Player Iterated Prisoner's Dilemma as a bidding game by using cellular automata to prove why cooperation emerges in the triangular neighborhood structure but not in the rectangular and the random pairing neighbourhood structures. And in [ss11] they investigated how the evolution of cooperation is influenced in Prisoner's Dilemma model by using cellular automata. Also in [13] they examined how the spatial structure of environment loss affects the eco-epidemic. They simulated the heterogeneous lattice landscape by defining two environment states, i.e. suitable and unsuitable.

On the other hand, there is a difference between the environments for representation the players such as lattice, tree, or graph by using EAs techniques such as Genetic Algorithms, Genetic Programming, and so forth, depending on many other factors that in turn affect back the outcome of the evolution of strategies, some of these factors such as number of players, technique of evolutionary computation, type of automata, neighbourhood structures and so forth. We can see this is clear in [N7] they reported in their paper that they build their model of three players by using a genetic programming technique to discover high-quality negotiation policies, with implemented the behavior of the players by finite automata.

In [a1] they used the other technique of EAs is genetic algorithms to generate adaptive behaviors and it can be applied for modeling an adaptive strategy for the prisoner dilemma. They used automata-based model for the agent behavior description.

Applications of Turing machines

There is an extension of finite automata called Turing machines "Alan Turing". [F8] The above definition of a finite state machine is intuitively the simplest.

There are many types of this main model that differ in the way of defining the environment of the machines, and in the defining the conditions and impacts of the transition rules. For a true finite state system, we should have finite environment state. If there isn't any finite environment state, Turing Machine model is largely used in theoretical computer science as the model of choice. The Turing machine can be observed as a generalization of the finite state machine model [F8].

Although Turing machines are simple modification of finite automata, they are computing devices much more powerful than finite automata. In fact Turing machines are as powerful as computers and it is generally believed, but not proved, that any computation by human beings, with or without computers, can be performed by Turing machines.

Applications of Adaptive Automata

In order to Adaptive automata do self-modification, adaptive acts adhered to their state-transition rules are activated whenever the transition is used. And adaptive mechanism can be defined as Adaptive actions which change the behavior of adaptive automata by modifying the set of rules defining it [L2].

In their opinion the simple notation for representing adaptive automata should have some features such as, being, at least, "compact, simple, expressive, unambiguous, readable, and easy to learn, understand and maintain" [L2].

[L3] they paid their attention to the iterated prisoner dilemma and they created an original evaluative probabilistic automaton for strategy modeling. They showed that genetic automata are well-adapted to model adaptive strategies. So here in their paper we can understand easily that the modelization of a player behavior needs some adaptive attributes. The computable models related to genetic automata are good tools to modelize such an adaptive strategy.

[L7] In their paper the collection of automata is formed in a tree-like structure, and the modification of action possibility continued at different levels according to the reward signs provided for all hierarchical levels.

[a1] they particularly focused on the models that can be used for simulation of Prisoner's Dilemma, and, this way, they showed how existing models and algorithms can be used with automata for representing the behaviors of players. They showed that the Dynamical and adaptive properties can be described in term of specific operators based on genetic algorithms. Also they described the genetic operators on probabilistic automata which enable the t adaptive behavior to be modeled for prisoner dilemma strategies.

VII. CONCLUSION

In this survey, an overview for using Automata in Game Theory for finding absolutely optimal strategy and the evolution algorithms are based on adaptive properties that can be useful for managing and modeling adaptive strategies in Game Theory.

We explored the applications and study the utilization of Automata applications in Game Theory. Fig. 2 illustrates the process of utilizing evolution algorithms for searching and automata for representing in Game Theory to solve problems and get the optimal solution.

It is generally agreed that finite automata are a natural medium to describe dynamic behaviors of reactive systems. Finite automata are formal and rigorous and computer programs can be easily written to simulate their behaviors.

To model a reactive system with finite automaton, first the states the system goes in or the modes of its operation are identified. These become the states of the finite automaton that models it. Then the transitions between the states triggered by events and conditions, external or internal to the system, are identified and they become arcs in the transition diagram of the finite automaton. In addition actions that may take place in those states can also be added to the model.[موقع]

We also concluded that the cellular automata can be well represented the evolutionary games, where the players are located on the sites of a lattice. For example, in the model proposed by Nowak and May (1992), each player takes the strategy of those neighbors (including himself) who obtain the extreme rewards in the last round, and a cellular automaton rule describes the new strategy for every player as a function of the strategy distribution in his neighborhood[L1].

Figure 2:-------

Acknowledgment

The authors would like to thank the School of Computer Sciences, USM for organizing the writing workshop under the APEX incentive grant that provides the platform to produce this paper.

Writing Services

Essay Writing
Service

Find out how the very best essay writing service can help you accomplish more and achieve higher marks today.

Assignment Writing Service

From complicated assignments to tricky tasks, our experts can tackle virtually any question thrown at them.

Dissertation Writing Service

A dissertation (also known as a thesis or research project) is probably the most important piece of work for any student! From full dissertations to individual chapters, we’re on hand to support you.

Coursework Writing Service

Our expert qualified writers can help you get your coursework right first time, every time.

Dissertation Proposal Service

The first step to completing a dissertation is to create a proposal that talks about what you wish to do. Our experts can design suitable methodologies - perfect to help you get started with a dissertation.

Report Writing
Service

Reports for any audience. Perfectly structured, professionally written, and tailored to suit your exact requirements.

Essay Skeleton Answer Service

If you’re just looking for some help to get started on an essay, our outline service provides you with a perfect essay plan.

Marking & Proofreading Service

Not sure if your work is hitting the mark? Struggling to get feedback from your lecturer? Our premium marking service was created just for you - get the feedback you deserve now.

Exam Revision
Service

Exams can be one of the most stressful experiences you’ll ever have! Revision is key, and we’re here to help. With custom created revision notes and exam answers, you’ll never feel underprepared again.