Minority Game project

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

      • 2M combination of outcome

    • Each 2M outcome, two possible decisions: go or stay.

      • 22M possible strategies

  • Genetic algorithm within NA

    • Each agent hold N out of 22M 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

• • strong negative correlation between score and loyalty.

  • About 20% of the Team agents who are the most disloyal perform above the zero mark

• • TA with 50% loyalty do not lose or gain anything

  • Positive / negative correspondence between loyalty and score for members of the same team

  • High loyalty maybe not too bad !

• • the score distribution of teams following type 2 is more balanced

Discussion and conclusion

Discussion

• • wealth distribution in the real world (in the U.S.)

    • top 25 % of households owned 87 % of the wealth in the country

    • bottom 25% of households owned nothing

    • (Zhu Xiao Di, 2007)

  • In our simulation

    • if you are a NA, you will likely live an average life.

    • if you are a TA (prone to be positively or negatively influenced by others), life could be extreme in either way.

  • What we learned

    • Betraying others is the only way to win the game? No

    • If honest ppl. are the minority, they win against the tricksters

  • Like in the real world, any organization could be extremely successful either by being honest or dishonest depending on its environment.

Summary

• • Because of the characteristics of the game

    • the genetic algorithm produced a normal distribution.

    • simple statistics as well as genetic algorithm

    • If all Team agents are honest, they perform worse than NAs.

    • If TAs lies at the voting for team decision, they always perform well.

    • If TAs disobey the team decision, result depends on the rate of honest people in group.

    • If TA have 50% loyalty to obey, he will neither win nor lose.

  • In a team, if only you somehow know the rate of other people to disobey, you would likely to find out the way to win the game.

Data / Documents

• • Program development report [View Download]

  • Program [Download]

Publication

• 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]