Minority Game Simulation

2011

Abstract

Minority game is a simulation of a zero-sum game, which has a similar structure to that of a real world market like a currency exchange market. We discuss a way to implement the game and provide a simulation environment with agents that can use various types of strategies to make decisions including genetic algorithms, statistics, and cooperative strategies. The goal of this simulation study is to find the effective strategies for winning the zero-sum game. Results show that both honesty and dishonesty can lead to player success depending on the characteristics of the majority of players.

About the project

• Implementation
• Minority game
• simplified version of a real world market
• multi-types of agents:
• genetic algorithms
• Statistics
• cooperative strategies
• Simulation
• Analysis the results with various settings
• find interesting features of the game

Background

THE El Farol Bar problem (W. Brian Arthur, 1994)

• Whether you would be better going to a bar or not?
• Satisfaction changes based on the rules:
• More ppl go ⇒ bar becomes clouded ⇒ ppl stayed win
• More ppl stay⇒ bar becomes quiet ⇒ ppl went win
• Use inductive reasoning based on previous histories
• Real-world example
• agents buying or selling a certain stock every day.
• the price of the stock is changed based on the rules:
• more buyers ⇒price become higher⇒seller wins
• more sellers⇒ price become lower⇒buyer wins
• Have to analyze the history of the market

Minority Game

• A variant of the El Farol Bar problem
• Minority always win
• Odd total number of players
• Always be winner or looser
• zero-sum game
• Σ(degree of enjoyability) = 0
• decision of each agent influences how well other people enjoy

Implementation

Minority game with multi-agent system

• Scoring method
• Agents store the last M game outcomes in their memory.
• Each agent accumulates “capital” reflecting his/her overall score.
• Scoring method:
• Agent won:     score = score + nMajority
• Agent lost:     score = score - nMinority
• sum of all agents’ scores stay stable
• distribution changes

Various types of agents

• Four different types of agents:
• Normal agent
• genetic algorithm
• Team agent
• cooperate with others
• Super agent
• use simple statistics
• Human agent
• controlled by human

(1) Normal agent (NA)

• Idea of strategies in this model
• Each M history, two possible outcomes: won or lost
• 2^M combination of outcome
• Each 2^M outcome, two possible decisions: go or stay.
• ₂2^M possible strategies

• Genetic algorithm within NA
• Each agent hold N out of ₂2^M possible strategies
• randomly generated at first
• All strategies keeps virtual score agent would have been given if the strategy was used.
• strategies with poor virtual score are replaced by new randomly generated strategies

(2)Team agent (TA)

• Normal agent who belongs to a team
• share their strategies to make a team decision
• agents with the higher scores have more weight for their votes
• 2 types of TA based on loyalty to the team
1. loyalty to vote honestly based on their highest-ranked strategy.
2. loyalty to act according to the team decision

(3) Super Agent (SA)

• makes decisions based on market results
• predict the probability of other agents to go to the bar in the next turn
  
• based on the assumption that the number of agents that go and the number that stay will converge in the long run.

Memory consumption and speed

• converted Boolean array into integer array
• Optimized speed 32 times
• Decreased memory size 8 times

Simulation

Normal Agents

• 
  Configuration
• 1001 Normal agents (Genetic algorithm)
• memory size of 6
• 3650 turns
• Graphs
• red: best score of all agents
• blue: absolute value of the worst.
• bar graph: score distribution
• Observation / Analysis
• Winning agent and losing agent grows at the same rate
• normal distribution
• characteristics of zero-sum game
• Not all can agents can win

NAs and SAs

• Configuration
• 3650 turns
• 501 Normal agents
• 500 Super agents
• Graphs
• light blue: score distributions of each type of agent
  
• Observation / Analysis
• normal distribution
• Similar distribution of each type of agent
  =>simple statistics technique works as good as genetic algorithms.

NAs and Loyal TA (100% loyal)

• Configuration
• 500 team agents
• 100% loyalty
• 100 members x 5
• 501 Normal agents
• Observation / Analysis
• TA perform far more poorly than NA
• 100 TAs do exactly the same thing
• Best decision becomes the worst
• detrimental to minority game

NAs, SAs, and TAs (type 1)

• Configuration
• 501 Normal agents
• 500 Team agents
• 100 agents * 5
• Type 1 (disloyal TAs lie about their intentions)
• Randomly assigned loyalty
• 500 Super agents
• 3650 turns.
• Observation / Analysis
• bell curve on the right
• Mostly the sum of NAs and SAs
• TAs' scores are scattered
• Avg. of TAs is the worst
  

• Akihiro Eguchi, Hung Nguyen. “Minority Game: the Battle of Adaptation, Intelligence, Cooperation and Power,” 5th IEEE International Workshop on Multi-Agent Systems and Simulation (MAS&S), Szczecin, Poland, September 18-21, 2011. pp.631-634. [View Download]