El Farol Bar problem

※此筆記可能會有一些錯誤, 歡迎大家指正:)※
前一陣子看了一本科普書, 書名是大科學[1], 對書裡面某一個章節的內容蠻有興趣的 (在另一本書隱藏的邏輯[2]中也有提及相同的內容), 因為看著看著就覺得應該可以試寫一個程式來跑跑看. 於是最近就用個幾天時間, 找了文獻及參考資料等之後, 就著手來做做看囉!! 結果還蠻順利的寫完了程式及做了一些簡單的實驗!! :D

I. Introduction
又到星期五啦~!! 想必大家一定都想在今天晚上要不要跟朋友去看一場電影?!還是要去吃頓大餐?! 又或者是去那裡喝一杯呢?! :D 有時候會覺得要決定去那個地方似乎是一件很困難的事!! 誰知道選擇去看一場電影, 到時候會不會人很多, 排隊買票要排很久, 卻有點後悔當初應該去吃頓大餐或喝一杯的!! :s 關於人們如何做決定這件事, 有沒有什麼方法可以幫助我們了解, 人們到底是如何做決定, 而且可不可做出預測? 至少, 可以讓我們想去看電影, 吃大餐或者是喝一杯時, 希望目的地的人數不要太多, 這樣子的一個小願望, 總是是被大家期待的!! :)

在 1994 年亞瑟(Brian Arthur)提出了一個艾法洛(El Farol)酒吧模型[3][4], 用一個簡單的模型來模擬人們如何做出決定. 至於為什麼會提出這個模型呢?! 科科…,原因跟大家一樣囉!! 那個時候亞瑟在新墨西哥州的聖塔菲研究院工作, 在同一條街上, 有一間名叫艾法洛的酒吧, 在每個星期二晚上都會有現場的音樂表演, 因此, 可以喝一杯並且同時欣賞現場表演, 應該是很高興的一件事!!

但是, 問題來了!! 這是一間小酒吧, 酒吧內的座位有限(假設為L). 若當亞瑟去的時候, 酒吧內的人數小於L, 那想必亞瑟當天晚上一定會過的相當愉快 (酒吧的座位未滿, 即酒吧不擁擠, 加上又有現場音樂表演, 而且應該還能夠喝上好幾杯!!). 反之, 若當亞瑟去的時候, 酒吧內的人數大於L, 亞瑟當天晚上會覺很失望, 因為酒吧太擠了!!!

在亞瑟提出酒吧模型之後, 後續就有其他的研究人員以這個模型為基礎, 加以修改並且應用在其他的問題上. 我們也可以稍為想一下, 如果就一開始提到的, 我們想去看電影, 吃大餐或喝一杯, 在這樣的情況下就包含了三種做決定的對象, 而且我們只能選擇其中的一個. 以酒吧模型來做模擬的話就會有三個酒吧, 分別代表不同決定 (看電影, 吃大餐及喝一杯). 當然, 這個情況一定會比單一酒吧的問題更來的複雜了 (若大家有興趣就再自行研究吧!!).

II. Agent-based simulation
在看過一些文獻及參考資料[5][6][7][8] 之後, 稍為整理一下前人在利用agent-based model (以代理人為基礎的模型) 做電腦模擬的時候, 使用了那些相關的設定. 在agent-based model 中, 用一個agent (代理人) 來表示一個人, 並且這個代理人會依照我們給它的設定做一些事情, 因此我們就可以用代理人來模擬一個人. 例如: 用一個代理人來模擬一隻羊, 我們設定牠在一個星期7 天中,每天都會做不同的事, 像是星期一小羊穿新衣, 星期二小羊肚子餓, 星期三小羊去爬山…等等 (猴子表示: 應該是我吧!!).

小羊版的酒吧模型之相關參數設定:
(1)程式的部份
S: 執行模擬(simulation)的次數:

(2)酒吧的部份
L: 酒吧座位的上限.
K: 僅關心過去K 個星期.
B[K]: 過去K 個星期, 去酒吧的人是否超過上限的歷史資訊 (0:沒有超過, 所以應該去酒吧; 1:超過, 所以不應該去酒吧).
例如: L=60, 表示酒吧只有60 個座位. K=3, 只關心過去3 個星期. B[]的大小為3,所以有B[0], B[1]及B[2]. 若過去3 個星期的模式(pattern)為101, 則表示B[0]=1為上上上星期不應該去酒吧, B[1]=0 為上上星期應該去酒吧, B[2]=1 為上星期不應該去酒吧.

(3)代理人的部份
N: 有多少人(代理人)會去酒吧.
P[i]: 代理人i 的決策機率, 例如: P[1]=0.9, 表示代理人1 有90%機率會做出跟上一次相同的決定.
A[i][K]: 過去K 個星期, 代理人i 所做的決定(0: 不去酒吧; 1:去酒吧).
Win[i]: 代理人i 贏的次數.
Lose[i]: 代理人i 輸的次數.
D: 代理人輸的次數超過贏的次數D 次, 則更換決策機率P[i].
H[i][j]: 代理人i 的策略, 其中有j 個歷史模式. 例如: 當K=3 時, 則j=2^3=8 個歷史模式, 即000~111 共8 個.

代理人決定輸贏的方法:
(1)代理人決定不去酒吧, 且酒吧人數未到上限, 則輸.
(2)代理人決定不去酒吧, 且酒吧人數超過上限, 則贏.
(3)代理人決定去酒吧, 且酒吧人數未到上限, 則贏.
(4)代理人決定去酒吧, 且酒吧人數超過上限, 則輸.

小羊版的模擬演算法:
1. 讀取參數設定
2. 初始化程式變數
3. 執行模擬S 次
3.1 每個代理人根據自己的歷史模式做出決策, 或更改舊有決策.
3.2 統計去酒吧的人數及給出是否該去酒吧的資訊.
3.3 判斷每個代理人的輸贏.
3.4 判斷每個代理人是否更換決策機率; 若要更換, 則隨機選取新的機率, 但不可跟舊的機率相同.
3.5 重設相關變數
4. 輸出結果

(以下為小羊之不負責任解說)

在小羊版的酒吧模型做了一些簡化, 像是每一個代理人只有一種策略, 及一種決定方式, 就是”僅根據上次遇到的歷史模式來做決定”. 例如: 這次遇到了模式(K=3) 001, 則代理人會根據從自己的策略中找到歷史模式 001 -> 1 (去酒吧) 這個模式, 再根據自己的決策機率P[i]來做決定並且加以修改.

但是, 在文獻中每一個代理人應會有多個方法來預測這次去酒吧人數, 像是方法1: 跟上星期的人數相同, 方法2: 過去K 個星期的平均人數, 方法3: 跟上上上(K=3)週的人數一樣, 方法4: 在過去6 個(2K)星期中最大的人數等, 藉此來判斷這週是否要去酒吧. 再者, 每一個方法都有一個分數, 來得知該種方法預測能力的好壞, 並且會有加減分數的判斷方式, 每一次只選分數最好的方法來預測.

最後, 在文獻中每一個代理人的策略在K=3 時, 會有000~111 共8 個歷史模式,其中以000 為例, 會對應到一個決定, 即000 -> 0 or 1. 因此, 8 個歷史模式還會有2^8=256 種策略組合. 在初始化時, 每一個代理人會從256 種策略中取S 種策略作為自己的策略, 每一種策略還會有一個分數及加減分數的判斷方式, 每一次只選分數最好的策略來使用.

(以上為小羊之不負責任解說)

III. Experiment
基於好奇心會殺死一隻羊的原因, 小羊實在是很想親自做出跟科普書[1]中提到的結果, 即:

“群眾最終會朝向兩極化 (就是群眾跟反群眾, 又或者去跟不去).”

最後在決定輸贏關鍵會落在少數人 (猶豫不決的人) 的身上. 有趣的是, 這些猶豫不決的人在輸的次數上, 會比處在兩個極端的人來的多!! (科科…, 真可憐 :p)在文獻中有研究人員將酒吧模型修改成更為簡化的模型, 稱為”少數者賽局(minority game)” (即少數者贏).

實驗1 (L=60, N=100, K=3, D=20, S=1000):
在實驗1 中, 想初步的了解科普書中所說的現象, 去酒吧的人數會在一個數值(L=60)上上下下的變化(如圖1 所示). 再者, 就是會出現最重要的兩極化 (群眾跟反群眾) 現象 (如圖2 所示). 在初始化時, 代理人的決策機率會是均勻分佈(uniform distribution), 即在第0 次模擬時. 隨著時間變化, 在第1000 次模擬時,似乎是有出現兩極化的現象, 即曲線的兩端往上升.




實驗2 (L=600, N=1000, K=5, D=20, S=100000):
在做完實驗1 之後, 總覺得圖2 的曲線不是很漂亮, 就在想是不是應做一些調整.在實驗2 中, 小羊把酒吧的座位改成600, 總共有1000 個代理人, 並且做了10萬次的模擬, 還有一些分析.

首先, 在圖3 中, 酒吧人數的平均都維持在600 人, 原因在於酒吧的座位是600個. :p 在圖4 中, 酒吧人數的標準差有逐漸下降, 我們也許可以想成是群眾越朝向兩極化, 猶豫不決的人就越來越少, 所以在圖5 中, 酒吧人數上下變化的幅度會變小.




再者, 也許是個有趣的地方, 在大約30000 次, 57500 次, 70000 次, 85000 次的附近有一種相同的模式, 當酒吧人數變化的幅度逐漸變小時, 突然間又劇烈的變化後再逐漸變小. 也許是跟代理人變更決策機率的設定方式有關, 先前有提到代理人更換新的機率時是隨機選取的.




在圖 6 中, 相較於圖2 可以發現, 曲線的變化相當明顯. 決策機率從第0 次的模擬的均勻分佈, 在第10000 次模擬時呈現兩極化的現象, 在第20000 次及100000次時則更加極端.



在圖 7 中, 以圓餅圖的方式來觀察兩極化的現像, 在圖中決策機率為0 及1 的部份 (群眾及反群眾), 會隨著時間越來越大, 其他位於中間的部份則越來越小.




--
參考文獻及資料
[1] 詹森 (N. Johnson), 大科學: 解析群眾行為、金融風暴、流行病毒、戰爭衝突背後的共通脈絡 (林俊宏譯), 天下文化.
[2] 布侃南 (M. Buchanan), 隱藏的邏輯：掌握群眾行為的不敗公式 (葉偉文譯), 天下文化.
[3] W. B. Arthur, "Inductive Reasoning and Bounded Rationality", The American Economic Review, Vol. 84, No. 2, pp. 406-411, 1994.
[4] W. B. Arthur, "Complexity and the Economy", Science, Vol. 284, pp. 107-109, 1999.
[5] S. Russell & P. Norvig, Artificial Intelligence: A Modern Approach, 2nd, Prentice Hall International, 2002.
[6] Lecture - El Farol Bar Problem and the Minority Game,
http://www.ece.rutgers.edu/~marsic/books/SE/projects/MinorityGame/
[7] M. Nekovee, The El Farol Bar Problem on Complex Networks,
http://www.richardclegg.org/mon/meeting5/Nekovee.ppt
[8] Wikipedia - El Farol Bar problem,
http://en.wikipedia.org/wiki/El_Farol_Bar_problem