# Presentation: 134962

## Biology helps you to win a game

**Biology helps you to win a game**

- M. Sysi-Aho, _A. Chakraborti_ and K. Kaski
*Laboratory of Computational Engineering**,*
*Helsinki University of Technology**,*
*P.O. Box 9203, FIN-02015 HUT, Finland*

- UASP 2003, Kolkata.

## Outline

- Motivation
- Introduction to Game theory
- Basic Minority Game
- Adaptation and Evolution in Biology
- Adaptive game
- Results
- Conclusion
**     **

## Motivation

## Motivation

- complex systems studies
- out-of-equilibrium economics studies

## I. Complex Systems

- The behaviour of most complex systems can be characterized by the ***competition*** among the interacting agents for ***scarce*** resources and their ***adaptation*** to the environment.
- 	The agents could be diverse in form and in capability.
- 	The nature of agents and their manners differ.
- 	The interactions of the large number of agents depend on the capabilities of the individual agents.

## Behaviour and Strategies

- An agent’s **behaviour** is a collection of rules governing “responses” to “stimuli”.
- The rules of action describe an agent’s **strategies**.
- 	 a sequence of	IF ... THEN ...
- 	The behaviour and strategies of the agents are determined by the selection and representation of the stimuli and responses.

## Adaptation and Timescales

- “Adaptation’’ is described in biology as a process by which an organism tries to fit itself into its environment.
- 	The organism’s experience guides it to change its structure so that as time passes, the organism makes better use of the environment for its own benefit.
- The ***timescales*** over which the agents adapt vary from one system to another.

## II.  Out-of-equilibrium Economics

- Human beings react with intelligence and foresight – “rational actions”
- 	game theory is used in economics.
- 	Game theory and other conventional theories in Economics, study patterns in behavioural **equilibrium** that induce no further interaction!
- In complex adaptive systems, major part of the environment of a particular agent includes other adaptive agents.
- 	A considerable amount of an agent’s effort goes  in adaptation to the other agents.
- 	Interesting temporal patterns are observed.
**     **

## Introduction to Game Theory

- Introduction to Game Theory

## What is a game?

- A ***game*** is a competition or conflict between two or more members, where each opponent acts in a ***rational*** manner, trying to resolve the conflict in its own favour.
- 	The competitors in the game are usually referred to as ***players***.

## What is game theory?

- The theory that deals with decision making of a number of rational opponents under conditions of conflict and competition.
- 	The number of players is finite.
- 	There is a conflict of interests between the players.
- 	The players act rationally and intelligently.
- 	The rules governing the choices are specified and  known to all the players.
- 	Each player has a finite set of possible courses of action.
- 	The players make individual decisions without communicating directly and simultaneously select their respective courses of action.
- 	The payoff (outcome) is fixed and determined in advance.

## What is a strategy?

- A ***strategy*** is a set of rules or alternative course of action available to a player in advance, by which it decides the course of action to adopt.
- 	If the players select the same strategy each time, then it is referred to as ***pure*** strategy.
- 	A ***m******ixed*** strategy is a selection among pure strategies with fixed probabilities.

## Concepts in game theory

- Thus there is a probabilistic situation and the objective of the player is to maximise expected gains or to minimise losses.

- Concepts in game theory

## What is an optimum strategy?

- A course of action or play which puts the player in the most preferred position, irrespective of the strategy of its competitors is called an ***optimum strategy***.
- 	Any deviation from this strategy results in a decreased payoff for the player. It is the expected payoff of the play when all the players of the game follow their optimum strategies.

## Types of games I

- When the number of competitors are *N* (where *N>2*), it is called ***N ******person game***.
- When the sum of the amounts won by all winners is equal to the sum of the amounts lost by all losers, it is called a ***zero sum game***.
- When the sum of gains or losses is non-zero, it is a ***non-zero sum game***.

## Types of games II

- If a game is played repeatedly then it is called a ***repeated game***, otherwise it is called a ***non-repeated game***.
- Depending on the number of times it is repeated it can be a ***finite game*** or an ***infinite game***.

- Types of games II

## What is a Pay-off matrix?

- The matrix which shows the outcome of the game as the players select their particular strategies, is known as the ***payoff matrix***.
- 	It is important to assume that each player knows not only his own list of possible courses of action, but also of his opponent.

## Example of a pay-off matrix

- A two-person zero-sum game is represented below

|  |  |  |  |
| --- | --- | --- | --- |
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |

- Player B

- Player  B

- Player  A

|  |  |  |  |
| --- | --- | --- | --- |
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |

- Player  A

**A’s pay-off matrix**

**B’s pay-off matrix**

**...**

**...**

**...**

**...**

**...**

**...**

**...**

**...**

**...**

**...**

**...**

**...**

**...**

**...**

**...**

**...**

**...**

**...**

## What is a Nash equilibrium?

- A pair of strategies is in ***Nash equilibrium*** if *A*’s choice is optimum, given *B*’s choice, and *B*’s choice is optimum given *A*’s choice.
- 	Neither of them know what the other person will do when it has to make its own choice of strategy. But, each has an expectation of what the other’s choice would be.
- 	It may be interpreted as a pair of expectations about each person’s choice such that, when the other person’s choice is revealed, neither individual wants to change its behaviour.

## Examples

- Player B

- Player  B

- Player  A

- Player  A

|  |  |
| --- | --- |
|  |  |

|  |
| --- |

|  |  |
| --- | --- |
|  |  |

*L*

*R*

*R*

*L*

*T*

*T*

*B*

*B*

*2, 1*

*0, 0*

*0, 0*

*0, 0*

*0,-1*

*1, 0*

*-1,-3*

*1, 2*

## Examples

- Player B

- Player  B

- Player  A

- Player  A

**Nash equilibrium**

|  |  |
| --- | --- |
|  |  |

|  |
| --- |

|  |  |
| --- | --- |
|  |  |

*L*

*R*

*R*

*L*

*T*

*T*

*B*

*B*

*2, 1*

*0, 0*

*0, 0*

*0, 0*

*0,-1*

*1, 0*

*-1,-3*

*1, 2*

## Examples

- Player B

- Player  B

- Player  A

- Player  A

**Nash equilibria**

|  |  |
| --- | --- |
|  |  |

|  |
| --- |

|  |  |
| --- | --- |
|  |  |

*L*

*R*

*R*

*L*

*T*

*T*

*B*

*B*

*2, 1*

*0, 0*

*0, 0*

*0, 0*

*0,-1*

*1, 0*

*-1,-3*

*1, 2*

## Examples

- Player B

- Player  B

- Player  A

- Player  A

**Nash equilibria**

**No Nash equilibrium**

|  |  |
| --- | --- |
|  |  |

|  |
| --- |

|  |  |
| --- | --- |
|  |  |

*L*

*R*

*R*

*L*

*T*

*T*

*B*

*B*

*2, 1*

*0, 0*

*0, 0*

*0, 0*

*0,-1*

*1, 0*

*-1,-3*

*1, 2*

## Bounded rationality

- Agents
- do not have perfect information about their environment, in general they will only acquire information through interaction with the dynamically changing environment
- do not have a perfect model of their environment
- have limited computational power, so they cannot work out all the logical consequences of their knowledge
- have other resource limitations (e.g. memory).

## Basic Minority Game

## Basic Minority Game Model I

**  ***N*** *****odd*** number of players
-   at a given time *t*,  they perform any of the    two possible ***actions***, denoted by 0 or 1
-   player wins if it is in the ***minority*** group
-   all players share ***finite*** amount of ***public information***
-   common bit-string of the *M* most recent outcomes called “***memory***”
-  bounded rationality

- This model was inspired by the **El Farol Bar** problem, created by
- Brian Arthur, in which a population of agents have to decide whether
- to go to the bar (they **attend** if it is not too crowded) on each Thursday.

## Basic Minority Game Model II

- public information

## Basic Minority Game Model II

- public information
- memory

## Basic Minority Game Model II

- public information
- memory

- history

## Basic Minority Game Model II

- public information
- memory

- history

- strategy #

## Basic Minority Game Model II

- public information
- memory

- history

- possible strategies

## Basic Minority Game Model II

- public information
- memory

- history

- strategies

- signal

## Basic Minority Game Model II

- public information
- memory

- history

- strategy #

- strategies

## Basic Minority Game Model II

- public information
- memory

- history

- strategy #

- strategies

## Basic Minority Game Model II

- Suppose there are *N=3* players.
- Each of them have *k=2* strategies **fixed **initially **randomly** out of the total *S=16* strategies.

## Basic Minority Game Model II

- Suppose there are *N=3* players.
- Each of them have *k=2* strategies fixed initially randomly out of the total *S=16* strategies.

- player 1

## Basic Minority Game Model II

- Suppose there are *N=3* players.
- Each of them have *k=2* strategies fixed initially randomly out of the total *S=16* strategies.

- player 1

- player 2

## Basic Minority Game Model II

- Suppose there are *N=3* players.
- Each of them have *k=2* strategies fixed initially randomly out of the total *S=16* strategies.

- player 1

- player 2

- player 3

## Basic Minority Game Model II

- history signal
- memory

- Each player **initially** selects one strategy
**randomly** from its pool of *k=2 *strategies.

## Basic Minority Game Model II

- player 1

- history signal
- memory

## Basic Minority Game Model II

- player 1

- player 2

- history signal
- memory

## Basic Minority Game Model II

- player 1

- player 2

- player 3

- history signal
- memory

## Basic Minority Game Model II

- player 1

- player 2

- player 3

- history signal
- memory

- Players 1 & 3 choose 0 and player 2 chooses 1
- *** ******minority*** player 2 with choice 1 ***wins***

## Basic Minority Game Model II

- player 1

- player 2

- player 3

- history signal
- memory

-  Strategy of player 2 gets a ***real point*** and the
- 	strategies of players 1 & 3 get no real points

## Basic Minority Game Model II

- player 1

- player 2

- player 3

- Since choice 1 wins

-  strategies which have more ***virtual points ***are
- 	better

-  strategies which predicted a correct win, i.e. 1,
- 	get a ***virtual point***

## Basic Minority Game Model II

- history signal changes from
- memory

## Basic Minority Game Model II

- history signal changes to
- memory

## Basic Minority Game Model II

- 	The *N=3* players continue playing the game with their *k=2* strategies fixed initially randomly out of the total *S=16* strategies with *M=2* and updated history

- player 1

- player 2

- player 3

- and the ***best strategy***, i.e. the strategy with the highest
- virtual points (randomly when there are more than one).

## Basic Minority Game Results

-           as the “attendance”.

- The number of times a player wins shows his ***performance*** in the game which is plotted as a function of time.
- The number of agents who choose a particular action, say 1, is denoted by          and it varies with time.

## Basic Minority Game Results

- A typical simulation with *N=801*, *M=6*, *S=10*, *T=5000*.

## Adaptation and Evolution in Biology

## Adaptation and Evolution

_*Biology*_
- 	Adaptation: An alteration or adjustment in structure or habits, often hereditary, by which a species or individual improves its condition in relationship to its environment.
- 	Evolution: Change in the genetic composition of a population during successive generations, as a result of natural selection acting on the genetic variation among individuals, and resulting in the development of new species.
- The principle of “Natural selection” survival of the fittest
- Means of adaptation and evolution:**	****Genetic crossover & Mutation**

## Human chromosomes

## Structure of a chromosome

## Genetic crossover

## Introduction to Adaptive Game

- Introduction to Adaptive Game

## Adaptive Game Model I

**  ***N*** *****odd*** number of players
-   at a given time *t*,  they perform any of the    two possible ***actions***, denoted by 0 or 1
-   player wins if it is in the ***minority*** group
-   all players share ***finite*** amount of ***public information***
-   common bit-string of the *M* most recent outcomes called “***memory***”
-   the players adapt periodically

## Adaptive Game Model II

-   A player examines its performance after every time interval
-   if it finds that it is among the fraction *n* (where 0*<n<*1) who are the worst performing players then it modifies its strategies
-   a player modifies its strategies using ***genetic crossover*** mechanism

## Genetic crossover mechanism

- Parents are random strategies ***one-point genetic crossover***
- Parents are the best strategies ***hybridized genetic crossover***

## Adaptive Game Model III

- Four possibilities are considered:
- 	(a)** **One-point genetic crossover with the parents being replaced by the children
- 	(b) One-point genetic crossover with the parents being saved and two worst strategies being replaced by the children
- 	(c) Hybridized genetic crossover with the parents being replaced by the children
- 	(d) Hybridized genetic crossover with the parents being saved and two worst strategies being replaced by the children

## Results

## Comparison with Basic Minority Game I

## Comparison with Basic Minority Game II

## Test I

## Attendances comparison

## Utility

- The total utility of the system is the number of people in the minority group. Mathematically, the scaled utility (total/maximum) can be defined as
- where
- and

- or

- when

- when

## Utilities comparison

## Hamming distance

- The Hamming distance between two bit-strings is defined as the ratio of the number of uncommon bits to the total length of the bit-string.

- correlated

- uncorrelated

- anti-correlated

## Hamming distance evolution I

## Hybridized genetic crossover

## Utilities as functions of parameters

## Hamming distance evolution II

## Test II

## Test III

## Conclusion

## Conclusions

- Adaptation improves the individual’s performance.
- Adaptation improves the system’s total utility.
** **Hybridized genetic crossover produces better results than one-point genetic crossover.
- Saving the parents and replacing the worst ones, produces better results.
- The mechanism presented here is extremely simple yet very powerful with potenetial applications in various fields such as modelling of biological evolution of species.
- In a way, “Biology helps you to win a game”.

## References

- [1] D. Challet and Y.-C. Zhang, *Physica A ***246***, *407 (1997).
- [2] M. Sysi-Aho, A. Chakraborti and K. Kaski, “*Intelligent Minority Game with genetic crossover**”*, preprint available at cond-mat/0209525 (2002).
- [3] M. Sysi-Aho, A. Chakraborti and K. Kaski, “*Adaptation with hybridized genetic crossover**”*, *Physica A*, in press (2002).
- [4] M. Sysi-Aho, A. Chakraborti and K. Kaski, “Biology helps you to win a game”, preprint available at cond-mat/0303221 (2003).
- [5] A. Chakraborti, K. Kaski and J. Kertesz, “*Econophysics: Basic concepts, analyses & modelling*” (2003).
- [6] R. Myerson, *Game theory: Analysis of Conflict* (Harvard University Press, Cambridge, Massachusetts, 1991).