F’NF-MixGen

1 collaborator

Cosimo Leuci (Author)

Flibs'NFarol

Darwin goes to El Farol Bar: Self-Organized Efficiency and Fairness in an Evolutive Game

WHAT IS IT?

The El Farol Bar (EFB) problem was introduced by W. Brian Arthur [1] to illustrate the dynamics of decision-making under conditions of bounded rationality where no solution can be derived in advance. Over time, it has evolved into an archetypal model of a complex adaptive system [2].

The main aim of this problem is to understand how individuals make choices when they are uncertain about the behavior of others. The problem is named after a bar in Santa Fe, New Mexico, which is famous for its weekly Irish music gatherings but has limited capacity. Every week, several independent agents have to decide whether to go to the bar or not. Their decision depends on their perception of how crowded the bar will be based on past attendance patterns and their personal forecasting strategies. If an agent thinks that the bar will be crowded, they will not go, otherwise, they will attend. Paradoxically, if all the agents expect only a few people to show up, they all end up going, leading to overcrowding, which is contrary to their predictions. Conversely, if they expect a lot of attendees, no one goes, once again defying their expectations.

To study this phenomenon, Arthur employed computer simulations to demonstrate that bar attendance fluctuates and eventually converges asymptotically around the bar’s capacity threshold.

The problem remains inherently ambiguous and lacks a deducible rational solution due to the impossibility of achieving perfect prediction. Nevertheless, the entire population can reach a Nash equilibrium, resulting in an optimal utilization of available resources. Consequently, the population tends to segregate into two distinct groups: frequent bar-goers and those who refrain from attendance. This raises the question of the circumstances under which the resource of “bar attendance” can be equitably distributed. To assess the game’s fairness, a procedure was integrated into the model to calculate the Gini index, a widely-used measure of inequality [3].

The Flibs’NFarol model endeavours to address the EFB problem by employing the genetic algorithm technique within an agent-based framework.

HOW IT WORKS

There have been various attempts to “solve” the El Farol Bar problem using genetic algorithms [4, 5]. While the problem cannot be solved deductively, a genetic algorithm allows for an inductive approach, even if this technique is designed to solve well-defined problems.

The present model is an implementation of the EFB problem within the NetLogo programming environment [6], building upon the earlier Flibs’NLogo model [7]. In this implementation, the agents are represented as flibs (finite automata or more fancifully “Finite LIving Blobs”), and their prediction strategies are determined by a transition table encoded as a string, essentially representing the chromosome. The genetic algorithm adjusts the behaviour of the flibs by assessing their fitness and rearranging their chromosomes through random mutations and selective reproduction as described by Dewdney, A.K. [8] with the modifications introduced by Leuci [7].

The primary distinction between Flibs’NFarol and Flibs’NLogo lies in their respective environmental background. In Flibs’NLogo, the environment is given by a cyclic input of binary digits sequence. The genetic algorithm selects flibs, based on their ability to predict the subsequent environmental input until the most proficient predictor emerges. Conversely, in Flibs’NFarol, the environment is characterized by the states of the bar (crowded or not crowded) determined by the cumulative choices made by the flibs based on their strategies. The most successful flib is the one capable of making appropriate decisions (i.e., whether to attend the bar or not) based on its internal state and the previous state of the bar.

Flibs’NLogo differs from Arthur's original model in a significant way: the agents do not carry strategies baggage. Instead, each agent has a single strategy represented by its transition table encoded within its chromosome. The transition table considers the state of the bar in the preceding evening, which means that the memory length of recent bar outcomes is limited to the last one. On the other hand, the flibs can exhibit various status numbers, which results in a range of potential chromosomes within the population. This diversity in status numbers affects the overall complexity of the system.

At the heart of Flibs’NFarol is the evaluation of flibs’ fitness, which is conducted through a 100-cycle tournament. Each cycle represents an evening at EFB, and flibs are rewarded for attending the bar when it is not crowded or abstaining from visiting when it is crowded. At the end of the tournament (equivalent to one EFB season, i.e., one NetLogo’s tick), the results are displayed, and standard genetic algorithm operators, such as recombination and mutation, are executed.

HOW TO USE IT

The user interface provides tools to execute experiments and comprises input controls (sliders and buttons) and output devices (monitors, plots, and the world window).

Input controls

SLIDERS

NUM-FLIBS determines the number of flibs in the simulation, set at 100 by default, following the standard Arthur's model.
THRESHOLD sets the fraction of the flibs' population that can comfortably attend the EFB, with a default value of 0.6, consistent with the standard Arthur's model.

BUTTONS

SETUP resets the system and prepares the model for execution.
TO GO ... executes only one season at EFB
OR NOT TO GO? continuously runs the model until it is turned off.

Output devices

MONITORS

RUN. AVG. ATTENDANCE shows the updated running average of attendance.
RUN. AVG. GINI INDEX shows the updated running average of the Gini index.
RUN. AVG. DIVERSITY shows the updated running average of diversity.
RUN. AVG. GENE-MASTER show the updated running average of gene-masters values
WORST FT. shows the current worst fitness.
AVERAGE FT shows the current average fitness.
BEST FT. shows the current best fitness.

PLOTS

ATTENDANCE HISTORY displays the value of the threshold (brown line), the mean fraction of flibs attending the bar (orange line) and its running average (green line) over time (ticks).
FITNESS DISTRIBUTION displays the current distribution of fitness values in the flibs population.
CHROMOSOME DIVERSITY: displays the chromosome diversity inside the Flibs population (purple line) and the running average of the chromosome diversity (red line) vs. time (ticks).
LORENZ CURVE: displays the current fairness distribution in the access to EFB.
GINI INDEX displays the flibs' Gini index (yellow line) and the running average of the Gini index (green line) over time (ticks). The Gini index is a measure of the inequality degree within the flibs' population. A Gini index of 0 is related to perfect equality, while a Gini coefficient of 1 is related to maximal inequality among fitness values.
GENE-MASTERS DISTRIBUTION displays the current distribution of the current gene-master classes distribution in the flibs population.
AVERAGE OF GENE-MASTERS VALUES displays the average of gene-masters values inside the Flibs population (purple line) and their running average (red line) vs. time (ticks).

THE WORLD

The World is a dynamic pictogram where a number of flibs move between two distinct areas: 'El Farol' Bar (yellow) and 'Elsewhere' (blue). The coordinates of a flib are not relevant; the only important thing is whether it is in the area of the bar or not. The colour of the flibs reflects their fitness level: white stands for 0%, black for 100% and red shades stand for intermediate fitness values.

THINGS TO TRY

During a run, you can change the threshold and observe how quickly the flibs population self-organises to approach the new limit.
A quantitative study can clarify the influence of the parameters on the time needed to reach the equilibrium point represented by the threshold attractor.
Test the model under different settings in order to evaluate the proximity of the attendance average to the capacity threshold. Simultaneously analyze the Gini index and other parameters as the chromosome variability or the accomodation of gene-masters values.

THINGS TO NOTICE

This version of the Flibs'NFarol model [9] produces populations characterized by varying quantities of internal states within the flibs. Indeed, all chromosomes possess an identical length, with the "coding" region representing a distinct segment dictated by a master gene. The numerical value assigned to this gene-master corresponds to the count of internal states that a flib can express. The gene-master constitutes an intrinsic component of the flib's genetic makeup and is consequently susceptible to both recombination and mutation processes.
Arthur’s original model employed a fixed set of strategies assigned to each agent for making predictions, resulting in deterministic dynamics. However, in reality, individuals do not adhere to a fixed set of models deterministically over time. Thus, a more suitable approach involves utilizing a genetic algorithm, which incorporates both stochastic elements, generating new models by randomly varying existing ones, and a selective process that eliminates ineffective models. This enables individuals to enhance their predictive models, akin to the scientific method and evolutionary processes [4].
Genetic algorithms evolve through a top-down process akin to artificial selection employed by breeders. In this process, a fitness value is assigned to each individual, and preferential reproduction is imposed based on this fitness value. Conversely, natural selection operates as a bottom-up process, where an individual’s fitness value is determined by downstream reproductive success. By employing a genetic algorithm to investigate adaptation, the underlying assumption is that adaptation predominantly occurs through the selection of the fittest individuals.
Dewdney highlights certain limitations to the efficiency of genetic algorithms, such as the case of Flibs’NLogo. These algorithms cannot develop a perfect predictor if the environmental period is entirely random, but they could successfully predict a repeating sequence if the period is no longer than twice their state number. Although each flib acts independently, the best flib can share part of its chromosome, encoding its successful strategy. As a flib attains superior predictive ability, its genome diffuses into the population, leading to stability in Flibs’NLogo. However, in Flibs’NFarol, no strategy can be deemed ultimate due to the dynamic nature of the environment. Nonetheless, a dynamical equilibrium can be approached and must be shared by the entire population.

EXTENDING THE MODEL

Method of selection. In order to test Darwinism, it may be insightful to vary the selection method of mating flibs in the reproduction operator.
Mutation and Mating Rates. These rates currently occur once every EFB season. It may be advantageous to vary these frequencies introducing new sliders in the user interface.
Reward Asymmetry. Currently, flibs are equally rewarded regardless of whether they choose to attend EFB or not. It may be worthwhile to introduce an asymmetric reward system for flibs attending different locations. If attendance at EFB confers a benefit to its customers, it should also confer an evolutionary advantage.
Diagram of the chromosome spectrum It may be insightful to provide the user interface with a diagram showing the spectrum of the different chromosomes (as could be their electrophoretic profile submitted to densitometry).

CREDITS AND REFERENCES

Arthur, W. B. (1994) "Inductive reasoning and Bounded Rationality (The El Farol Problem)" Amer.Econ. Review (Papers and Proceedings) 84: 406 - 411 http://tuvalu.santafe.edu/~wbarthur/Papers/El_Farol.pdf
Casti, J. (1996) "Seeing the light at El Farol" Complexity Vol. 1, Issue 5: 7-10 https://onlinelibrary.wiley.com/doi/abs/10.1002/cplx.6130010503
Ponsiglione, C., Roma, V., Zampella, F., Zollo, G. (2015). The Fairness/Efficiency Issue Explored Through El Farol Bar Model. In: Gil-Aluja, J., Terceño-Gómez, A., Ferrer-Comalat, J., Merigó-Lindahl, J., Linares-Mustarós, S. (eds) Scientific Methods for the Treatment of Uncertainty in Social Sciences. Advances in Intelligent Systems and Computing, vol 377. Springer, Cham. https://doi.org/10.1007/978-3-319-19704-3_26
Fogel, D.B. Chellapilla, K. Angeline, P.J. (1999) "Inductive reasoning and bounded rationality reconsidered" IEEE Transactions on Evolutionary Computation Vol. 3, Issue 2: 142 - 146 https://www.academia.edu/7005543/Inductive_reasoning_and_bounded_rationality_reconsidered
Rand, W. Sondahl, F. (2007) "The El Farol Bar Problem and computational effort: why people fail to use bars efficiently". In: Agent 2007, November 15-17, Evanston, IL, USA
Wilensky, U. (1999). NetLogo. http://ccl.northwestern.edu/netlogo/. Center for Connected Learning and Computer-Based Modeling, Northwestern University, Evanston, IL.
Leuci, C (2020). “Flibs’NLogo - An elementary form of evolutionary cognition” (Version 1.0.0). CoMSES Computational Model Library. Retrieved from: https://doi.org/10.25937/f932-8y73
Dewdney, A. K. (1985) “Exploring the field of genetic algorithms in a primordial computer see full of flibs” Scientific American 253 (5): 21-33. https://www.jstor.org/stable/24967834
Leuci, C. (2023) “Flibs’NFarol: Self-Organized Efficiency and Fairness Emergence in an Evolutive Game” (Version 1.0.0). CoMSES Computational Model Library. Retrieved from: https://doi.org/10.25937/fdxs-2479

OTHER RELATED MODELS

Rand, W., Wilensky, U. (2007). NetLogo El Farol Extension 3 model. http://ccl.northwestern.edu/netlogo/models/ElFarolExtension3. Center for Connected Learning and Computer-Based Modeling, Northwestern Institute on Complex Systems, Northwestern University, Evanston, IL.
Garofalo, M., 2006. Modeling the El Farol bar problem in NetLogo. PRELIMINARY DRAFT, Dexia Bank Belgium. http://ccl.northwestern.edu/2006/ElFarol.pdf and http://ccl.northwestern.edu/netlogo/models/community/ElFarolBarProblem
Wilensky, U. (1998). NetLogo Wealth Distribution model. http://ccl.northwestern.edu/netlogo/models/WealthDistribution. Center for Connected Learning and Computer-Based Modeling, Northwestern University, Evanston, IL.

COPYRIGHT AND LICENSE

CC BY-NC-SA 4.0

This work is licensed under the Creative Commons Attribution-NonCommercial-ShareAlike 4.0 License. To view a copy of this license, visit https://creativecommons.org/licenses/by-nc-sa/4.0/ or send a letter to Creative Commons, 559 Nathan Abbott Way, Stanford, California 94305, USA.

Comments and Questions

Please start the discussion about this model! (You'll first need to log in.)

Click to Run Model

;;  _________________________________________________________________________________________________________________
;;
;;  --------------------   FlibsN'Farol   ---------------------------------------------------------   FlibsN'Farol
;;  FlibsN'Farol   ---------------------------------------------------------   FlibsN'Farol   -----------------------
;;  _________________________________________________________________________________________________________________



breed     [flibs flib]     ;; FLiBs (finite living blobs) are the agents of the model: they are structured as
                           ;; finite automata. They have "a finite number of states; an input signal
                           ;; causes it to change automatically from one state to another. The kind of automaton
                           ;; used in a flib also generates signals. Incoming and outgoing signals are represented
                           ;; within the automaton by symbols. When a signal is received, the automaton changes
                           ;; state and emits a second signal" (A. K. Dewdney, 1985)


flibs-own [chromosome      ;; every flib owns a chromosome, that is a string codifying its state transitions schema
           gene-master     ;; define the states number of the flib
           state           ;; the current inner state of the flib
           choice          ;; choice/prevision expressed by the flib regarding to go or not to go to the bar
           fitness         ;; a measure of flibs' prevision ability to forestall if the bar will be crowded or not
           ]


globals  [tot_attend        ;; total of attendances during one season to "El Farol" bar (i.e. 100 cycles tournement)
          sigma_attend      ;; an accumulator for the previous variable
          crowded           ;; a switch recording the state of the bar: 1 if overcrowded, 0 if not
          lorenz-points     ;; list of the Lorenz curve ordinates
          gini-index-reserve;; counter functional to the calculation of the Gini index
          sigma-gini        ;; an accumulator for the previous variable
          diversity         ;; the number of the different chromosomes in the flibs population
          sigma_divers      ;; an accumulator for the previous variable
          gm-average        ;; average of gene-master values
          sigma_gm.avg      ;; an accumulator for the previous variable
          best              ;; the best flibs fitness value
          worst             ;; the worst flibs fitness value
          donor             ;; one of best-performing flibs sharing part of its genes
          recipient         ;; one flib acquiring genes from the donor flib
          a-split           ;; the first cut in the recipient's chromosome
          b-split           ;; the second cut in the recipient's chromosome
          locus             ;; pointer/counter of chromosome loci
          ]


;;  ----------   SETUP PROCEDURES   ----------------------------------------------------------------------------------
;;  ------------------------------------------------------------------------------------------------------------------

to setup           ;; initializing the model
  clear-all
  ;; create the bar area (yellow) and an elsewhere (blue)
  ask patches  [set pcolor blue - 3]
  ask patches with [abs pxcor < 10 and abs pycor < 7] [set pcolor yellow]
  ask patches with [pxcor = 9 and pycor = 7] [set plabel ["El Farol Bar"]]
  ask patches with [pxcor = 21 and pycor = -21] [set plabel ["Elsewhere"]]

  ;; create the flibs and give them a random chromosome
  ask n-of num-flibs patches [sprout-flibs 1 [
    set shape "flib"
    set color white
    set size 2
    set chromosome ""
    ]
  ]
  set locus 0
  ask flibs [chromosome-genesis]
  reset-ticks
end 

;; Chromosomes are strings randomly built through an iterative procedure. The content of even string positions
;; are 1 or 0: they are the flib's outgoing signals representing respectively the intention to go or not to go
;; to the bar. Odd string positions are occupied by the numerical code of one state.

to chromosome-genesis
  set chromosome word chromosome (word (random 2) (random 10))
  set locus locus + 1
  if locus < 10 * 2 [chromosome-genesis]
  ;; the gene-masters can acquire values between 1 and 10
  set gene-master 1 + random 10
  set locus 0
end 


;;  ----------   RUNTIME PROCEDURES   --------------------------------------------------------------------------------
;;  ------------------------------------------------------------------------------------------------------------------

to go
  set tot_attend 0
  ask flibs [set fitness 0 set state 0]

  repeat 100 [el-farol] ;; a 100 cycles tournament could be seen as a season to "El Farol" bar (i.e. 100 evenings)

  if sum [fitness] of flibs = 0 [  ;; no fitness no progress
    show "fitness null for every flibs"
    stop
  ]
  analyse   ;; some relevant "El Farol" seasonal results are picked and processed
  ask flibs [move] ;; the world displays a snapshot of the bar after the last evening of the season

  conjugation  ;; after every season, one breeding and one mutational event occurs
  ask one-of flibs [mutate]

  tick
end 


;; Operator 1: ONE SEASON TO EL FAROL BAR
;; -------------------------------------------------------------------------------------------------------------------

to el-farol
  let attendance 0    ;; the variable records the fraction of agents attending the bar during one evening
  flibs-behaviour
  ;; bar attendance is the sum of every flibs' choices
  set attendance sum [choice] of flibs / num-flibs
  ;; comparing the attendance and the threshold value, the (over)crowded state of the bar is determined
  if attendance >= threshold [set crowded 1    ;; if the bar is crowded, reward the flibs that are elsewhere
    ask flibs with [choice = 0] [set fitness fitness + 1] ]
  if attendance < threshold [set crowded 0  ;; if the bar is not crowded, reward the flibs that are attending
    ask flibs with [choice = 1] [set fitness fitness + 1] ]
  set tot_attend tot_attend + attendance ;; the results of every evening of a season is added up
end 

to flibs-behaviour
  ask flibs [
    ;; the flibs state is updated
    set state read-from-string item (4 * state + 2 * crowded + 1) chromosome
    ;; flibs express only a part of their chromosome and the lenght of this
    ;; codifying part is set by gene-master value
    if state != 0 [set state state mod gene-master]
    ;; each flib processes its choice (to go or not to go)
    set choice read-from-string item (4 * state + 2 * crowded) chromosome
  ]
end 

to analyse
  set best max [fitness] of flibs
  set worst min [fitness] of flibs
  ask flibs [set color scale-color red fitness 100 0]
  set sigma_attend sigma_attend + tot_attend / 100
  update-lorenz-and-gini
  diversity-assessment
  set sigma_divers sigma_divers + diversity
  set gm-average mean [gene-master] of flibs
  set sigma_gm.avg sigma_gm.avg + gm-average
end 

to update-lorenz-and-gini  ;; borrowed from Wilensky's model "Wealth Distribution"
  let sorted-comfort sort [fitness] of flibs
  let total-comfort sum sorted-comfort
  let comfort-sum-so-far 0
  let index 0
  set gini-index-reserve 0
  set lorenz-points []
  repeat num-flibs [
    set comfort-sum-so-far (comfort-sum-so-far + item index sorted-comfort)
    set lorenz-points lput ((comfort-sum-so-far / total-comfort) * 100) lorenz-points
    set index (index + 1)
    set gini-index-reserve
      gini-index-reserve +
      (index / num-flibs) -
      (comfort-sum-so-far / total-comfort)
    ]
  set sigma-gini sigma-gini + ((gini-index-reserve / num-flibs) * 2)
end 

to diversity-assessment
  ;; the value of genomic diversity inside the flibs population is evaluated as the number of different chromosomes
  let sort-chrom sort [chromosome] of flibs
  let index 1
  set diversity 1
  repeat num-flibs - 1 [
    if item index sort-chrom != item (index - 1) sort-chrom [set diversity diversity + 1]
    set index (index + 1)
  ]
  set diversity diversity * 100 / num-flibs
end 

to move
  ifelse choice = 0
      [move-to one-of patches with [pcolor = blue - 3]]
    [move-to one-of patches with [pcolor = yellow]]
end 


;; Operator 2: REPRODUCTION
;; -------------------------------------------------------------------------------------------------------------------

to conjugation
  ;; the conjugation process requires two flibs' chromosomes: the donor and the recipient:
  ;; just the second one will undergo to hybridization
  ifelse best > worst [select-flibs] [stop]
  ask flib recipient [genetic-shuffling]
end 

to select-flibs
  set donor [who] of one-of flibs with [fitness = best]
  set recipient [who] of one-of flibs
  if donor = recipient [select-flibs]
end 

to genetic-shuffling
  ;; a sequence included between two restriction sites (named a-split and b-split) is randomly chosen
  set a-split random (10 * 4)
  set b-split random (10 * 4)
  set locus 0
  hybridization
  ;; often the gene master of the flib donor is cloned into the genome of the flib recipient
  if random-float 1 < 0.7 [set gene-master [gene-master] of flib donor]
  set fitness 0
end 

to hybridization
 ;; the chromosome's sequence included between a-split and b-split restriction sites on a random
 ;; flib is replaced by the corresponding sequence on one of the most performing flibs;
 ;; chromosomes are treated as circular
 if a-split < b-split [
    set chromosome replace-item (a-split + locus)
      chromosome (item (a-split + locus) [chromosome] of flib donor)
    set locus (locus + 1) if locus < b-split - a-split
      [hybridization]
  ]
 if a-split > b-split [
    set chromosome replace-item ((a-split + locus) mod (10 * 4))
      chromosome (item ((a-split + locus) mod (10 * 4)) [chromosome] of flib donor)
    set locus (locus + 1) if locus < (10 * 4) - (a-split - b-split)
      [hybridization]
  ]
  set locus 0
end 


;; Operator 3: MUTAGENESIS
;; -------------------------------------------------------------------------------------------------------------------

to mutate
  ;; mutations occur randomly at a given frequency on one locus only
  let dice random length chromosome
  let muton read-from-string item dice chromosome
  ifelse dice mod 2 = 0
    [set chromosome replace-item dice chromosome word ((muton + 1) mod 2) ""]
  [set chromosome replace-item dice chromosome word ((muton + 1) mod 10) ""]
  ;; sometimes gene-masters mutate, as well
  if random-float 1 < 0.5 [set gene-master 1 + random 10]
  set fitness 0
end 




; Copyright 2023 Cosimo Leuci.
; See Info tab for full copyright and license.

There are 3 versions of this model.

Uploaded by	When	Description	Download
Cosimo Leuci	almost 2 years ago	ver. 0.1	Download this version
Cosimo Leuci	almost 2 years ago	ver. 0.1	Download this version
Cosimo Leuci	almost 2 years ago	ver. 0.1	Download this version

Attached files

File	Type	Description	Last updated
F’NF-MixGen.png	preview	preview_image	almost 2 years ago, by Cosimo Leuci	Download

Parent: Flibs'NFarol

This model does not have any descendants.

Graph of models related to 'F’NF-MixGen'

NetLogo