Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Programming Complexity

Programming Complexity

Modeling Complex Systems with Go and React

Sau Sheong Chang

February 20, 2016
Tweet

More Decks by Sau Sheong Chang

Other Decks in Programming

Transcript

  1. Complexity The  behavior  that  emerges  from  a  group  of  interacting

      parts,  that  is  not  directly  the  result  of  interactions   between  individual  parts
  2. Algorithm •At  every  tick,  randomly  pick  n  cells •Compare  features

     of  the  culture  with  each  of  its   neighbours •If  the  trait  difference  for  the  same  feature  between  2   cultures  are  <  t,  randomly  select  either  culture  and   copy  the  trait  of  the  feature  to  the  other  culture
  3. A 0 5 5 F 6 F A D 2

    D 0 culture  B culture  A Difference  between  2  cultures  =  34 5 A 8 3 2 6 + + + + + = 34
  4. F F F F F F 0 0 0 0

    0 0 culture  B culture  A 100%  different  =  96 F F F F F F + + + + + = 96
  5. A 0 5 5 F 6 culture  B culture  A

    Difference  between  2  cultures  that  are  100%  similar  =  0 0 0 0 0 0 0 + + + + + = 0 A 0 5 5 F 6
  6. The  more  similar  2  cultures  are,  the  more  likely  

    there  will  be  cultural  exchange Probability  of  cultural  exchange  =  1  -­‐ difference   between  2  cultures  ÷ 96
  7. culture  B culture  A Randomly  choose  to  copy  one  of

     culture  A’s   features  to  culture  B  or  vice  versa A 0 5 5 F 6 F A 5 2 D 0 When  interaction  happens
  8. What  do  we  want  to  measure? •Average feature  distance  tells

     us  how  far  apart   (different)  the  cultures  are •Uniques tells  us  the  number  of  unique  cultures  at  any   given  point  in  time •Changes tells  us  how  vibrant  the  cultural  exchanges   are
  9. Observations •Eventual  equilibrium  is  only  a  few  dominant  cultures •Dominant

     cultures  can  be  quite  different  from  each   other •Smaller  areas  results  in  faster  equilibrium  and  smaller   number  of  dominant  cultures •A  culture  that  is  more  dominant  at  a  point  in  time   doesn’t  mean  it  will  be  dominant  in  the  end
  10. Algorithm •At  every  tick,  check  every  cell •If  at  least

     n  number  of  its  neighbours are  of  the  same   ‘race’,  do  nothing •Otherwise,  randomly  pick  an  empty  cell  and  move   there
  11. Parameters •Acceptable number  of  neighbours (n) •Number of  ‘races’  in

     the  grid  (r) •Percentage  of  vacant  cells  (v) •Policy  limitation – cannot  have  more  than  (l)  number   of  neighbours of  the  same  race
  12. Observations • Segregation  happens  even  if  there  is  weak  preference

     for  neighbours of  same  type • The  weaker  the  preference,  the  less  segregated  (smaller  clusters) • The  stronger  the  preference,  the  more  segregated  (larger  clusters) • At  a  threshold,  stronger  preference  results  in  an  unstable  but  non-­‐ segregated  state  (occupants  always  moving  to  another  cell) • Number  of  races  have  no  impact  of  segregation • Number  of  vacant  cells  have  no  impact  on  segregation • Policy  enforcement  has  limited  impact  on  segregation  (stronger   policies  result  in  unstable  state)
  13. The  study  of  mathematical  models  of  conflict  and   cooperation,

     often  used  in  economics  and  political   science
  14. V  =  value  gained  if  at  least  1  person  volunteers

    C  =  individual  cost  of  volunteering A =  overall  cost  if  no  one  volunteers
  15. You volunteer You  don’t   volunteer I volunteer I  don’t

     volunteer V  -­ C V  -­ C V  -­ C V V  -­ C V V  -­ A V  -­ A Payoff  matrix  for  a  2-­‐player  game
  16. You  volunteer You don’t   volunteer I volunteer I  don’t

     volunteer V  -­ C V  -­ C V  -­ C V V  -­ C V V  -­ A V  -­ A If  I  volunteer
  17. You  volunteer You  don’t   volunteer I volunteer I  don’t

     volunteer V  -­ C V  -­ C V  -­ C V V  -­ C V V  -­ A V  -­ A If  I  don’t volunteer
  18. Mixed  strategy  Nash  equilibrium V  – C  =  pV +

     (1  – p)(V  – A)   where  p  =  probability  of  volunteering  
  19. For  an  N-­‐player  game Probability  of  volunteering  =  p  x

     p  x  …  x  p =  pN-­‐1 N  – 1  times
  20. V  =  value  if  at  least  1  volunteer C  =

     individual   cost  of  volunteering A  =  overall  cost  if  no  volunteers N  =  number  of  people  involved p  =  probability  of  getting  at  least  1  volunteer 1-­‐ p  =  probability  of  getting  no  volunteers V  – C  =  (pN-­‐1)V  +  (1  – p) N-­‐1(V  – A)  
  21. V  =  value  if  at  least  1  volunteer C  =

     individual   cost  of  volunteering A  =  overall  cost  if  no  volunteers N  =  number  of  people  involved p  =  probability  of  getting  at  least  1  volunteer 1-­‐ p  =  probability  of  getting  no  volunteers p =1− C A " # $ % & ' 1 N−1
  22. Observations •Decrease  individual  cost  of  volunteering •Increase  the  overall  costs/impact

     of  not  volunteering   (??) •Increase  difference  between  individual  cost  and   overall  costs •Reduce  number  of  ‘players’ •Increasing  number  of  players  have  negative  or  no   impact