美國洛杉磯航警局運用賽局理論建置巡查系統

911事件後美國洛杉磯航警局為因應未來恐怖攻擊的威脅，希望能建一個符合巡查人員的檢查點電腦配置系統
這系統不只能改善現行系統的不足，還能提昇破案率，預防犯罪事件的發生。由於巡查人力的不足，很難全面性的監控所有重要進出點(checkpoints)，加上犯罪者能透視機場每日巡查的時間與地點。不定點巡查是現行系統主要預防犯罪的方法。所以洛杉磯航警局的電腦系統工程師利用賽局理論的貝斯史塔博格賽局（Bayesian Stackelberg game）建置隨機監控或巡點派遣軟體(ARMOR: Assistant for Randomized Monitoring over Routes)，以提供巡查人員有效的監控機場安全，並介由巡查，即時地破獲非法行為。
我們假設這賽局有兩個玩家：巡警 (police agent)及犯罪者(adversaries)，警員巡邏可選擇兩檢查點(check points)：A 和B點。犯罪者同樣也有兩個選擇：選擇A 和B點進入LAX航站，根據以往巡警的破獲率及得到的報酬，以及犯罪者作案成功率及獲得的報酬，將兩者玩家的互動報酬製作如下矩陣表：

我們先說明什麼是Stackelberg game?在一個資訊不完全的賽局中,有一個先行者(leader)及一個後行者(follower)，先行者會先選定一個策略，後行者根據先行者所選的策略，選定自已利潤最大化的策略。
我們回到以上的賽局，先看犯罪者，在圖1中，如果是靜態資訊完全賽局，只有一個純粹Nash均衡為(2, 1)，也就是(臨檢A, 進入B)，巡警臨檢“A”點，而犯罪者由“B”點進入。我們假設雙方的行為策略運用會有先後順序 ，以史坦伯格Stackelberg模型來分析這賽局，我們假定巡警是先行者(leader)，犯罪者是後行者(follower)，巡警先給定臨檢“A”點的混合策略機率μ和臨檢“B”點的混合策略機率1-μ，犯罪者看到這兩個巡邏點的機率後，就會選擇自已利潤最佳化的策略。我們給定巡警臨檢“A”點機率μ=0.5及臨檢“B”點機率1-μ=0.5，犯罪者看到這機率後比較選擇A和B的報酬(payoff) ，選擇由A進入的報酬為0.5×0+0.5×2=1，選擇由B進入的報酬為0.5×1+0.5×0=0.5，因此考量報酬最大化後，犯罪者會選擇由A點進入的策略。而巡警用混合策略得到的期望payoff為0.5×4+0.5×3=3.5。這值比純粹Nash均衡的2還要高。
我們考量資訊不完全的情況，假設犯罪者有兩種偏好類型(Types)，第一種類型是恐怖份子(犯罪者類型1)，另一種類型是運毒者(犯罪者類型2)。巡警只有一種類型－希望能抓到犯罪者。同樣地，根據以往巡警的破獲率及可得到的報酬，以及犯罪者兩種類型作案成功率及可獲得的報酬，將兩者玩家的互動報酬製作如下兩類型的矩陣表：

第一，我們假定犯罪者的類型1機率為q, 類型2機率為1-q，只有上帝知道q有多大,，我們用Nature來表示，將以上兩類型的Matrix合併成一個有先後順序的樹狀賽局圖，如下圖：

我們也可用漢撒意轉換(Harsanyi transformation)，將以上兩個表格合併為下圖，從不完全訊息賽局轉為不完美訊息賽局(imperfect information)。

第二，經由漢撒意轉換後找出不完美訊息賽局的納許均衡，這均衡就是在不完全訊息賽局中的貝斯納許均衡。
1.在賽局中，我們可以知道犯罪者的純粹策有兩個：(A, B)。
2.犯罪者選擇A的混合策略的機率為λ，選擇B 的混合策略的機率為1-λ。
3.犯罪者的Type1機率為q, Type2機率為1-q。
4.巡警在犯罪者的Type1中，Patrol A的混合策略機率為μ₁，Patrol B的混合策略機率為1-μ₁，在犯罪者的Type2中，Patrol A的混合策略機率為μ₂，Patrol B的混合策略機率為1-μ₂。
5.我們用比較巡警和犯罪者的payoff來決定純粹貝斯納許均衡：
給定巡警選擇臨檢A，由表中可知犯罪者的優勢策略是RB- R’B。
給定巡警選擇臨檢B，由表中可知犯罪者的優勢策略是RA- R’A。
反過來看，
給定犯罪者選擇RA- R’A，如果2+2q > 3，q>1/2由表中可知巡警的優勢策略是臨檢A，如果q＜1/2，巡警的優勢策略是臨檢B。
給定犯罪者選擇RA- R’B，巡警的優勢策略是臨檢A。
給定犯罪者選擇RB- R’A，如果2 > 3-2q，q>1/2由表中可知巡警的優勢策略是臨檢A，如果q＜1/2，巡警的優勢策略是臨檢B。
給定犯罪者選擇RB- R’B，巡警的優勢策略是臨檢B。
由以上兩者的共同優勢策略，我們可知純粹貝斯納許均衡有兩個：1.當q>1/2（犯罪者的類型偏向恐怖份子），巡警的均衡策略是臨檢B，而犯罪者選擇RA- R’A。2.當q<1/2（犯罪者的類型偏向運毒者），巡警的均衡策略是臨檢A，而犯罪者選擇RB- R’B。
接著計算混合策略貝斯納許均衡(Mixed-strategy Bayes-Nash Equilibria)
首先考量巡警在類型1的情況下, 選A的期望報酬(expected payoff):與選B的期望報酬(expected payoff)相等
考量犯罪者的最佳選擇：
1.如果巡警在犯罪者類型1下的混合策略機率為μ₁，如果巡警在犯罪者類型2下的混合策略機率為μ₂，犯罪者選A的期望報酬(expected payoff)為:
在類型1選A為q[1×μ₁+2×(1-μ₁)]加上在類型2選A (1-q)[0×μ₂+2×(1-μ₂)]為
2q(1-μ₁)＋2(1-q)×(1-μ₂)
2.犯罪者選B的期望報酬(expected payoff)為:
在類型1選B為q[1×μ₁+0×(1-μ₁)]加上在類型2選B (1-q)[1×μ₂+0×(1-μ₂)]為
qμ₁＋(1-q)×μ₂
犯罪者選A的期望報酬等於選A的期望報酬
qμ₁＋(1-q)×μ₂＝2q(1-μ₁)＋2(1-q)×(1-μ₂)
q(4μ₁-2)＝(1-q)×(2-3μ₂)
當q=1時犯罪者為恐怖份子，μ₁=1/2，當q=0時犯罪者為運毒者，μ₂=2/3
所以混合策略貝斯納許均衡為(μ₁,μ₂)=(1/2, 2/3)
分析類型1的犯罪者（恐怖份子）：
我們運用史坦伯格Stackelberg模型來分析這賽局，我們假定巡警是先行者(leader)，犯罪者是後行者(follower)，巡警先給定臨檢“A”點的混合策略機率μ₁和臨檢“B”點的混合策略機率1-μ₁，犯罪者看到這兩個巡邏點的機率後，就會選擇自已利潤最佳化的策略。我們給定巡警臨檢“A”點機率μ₁=0.5及臨檢“B”點機率1-μ₁=0.5，犯罪者看到這機率後最大化她的報酬(payoff) ，巡警用混合策略得到的期望payoff為0.5×4+0.5×3=3.5。這值比純粹Nash均衡的2還要高。所以選擇臨檢A的機率為50%，而選擇臨檢B的機率為50%。
分析類型2的犯罪者（運毒者）：
我們運用史坦伯格Stackelberg模型來分析這賽局，我們假定巡警是先行者(leader)，犯罪者是後行者(follower)，巡警先給定臨檢“A”點的混合策略機率μ₂和臨檢“B”點的混合策略機率1-μ₂，犯罪者看到這兩個巡邏點的機率後，就會選擇自已利潤最佳化的策略。我們給定巡警臨檢“A”點機率μ=2/3及臨檢“B”點機率1-μ=1/3，犯罪者看到這機率後比較選擇A和B的報酬(payoff) ，選擇由A進入的報酬為2/3×0+1/3×2=2/3，選擇由B進入的報酬為2/3×1+1/3×0=2/3，因此考量報酬最大化後，犯罪者會選擇由A點進入的策略。而巡警用混合策略得到的期望payoff為2/3×2+1/3×3=7/3≒2.33。這值比純粹Nash均衡的3還要小。她會選擇純粹Nash均衡：(臨檢B, 進入A),μ₂=1，所以選擇臨檢B的機率為100%，而選擇臨檢A的機率為0%。

美國洛杉磯航警局利用賽局理論建置隨機巡點派遣軟體(ARMOR: Assistant for　Randomized Monitoring over Routes)，這軟體先請使用人員及專家（巡警）輸入檢查點的需要次數，並結合以往的查獲資訊，將這些資訊建構貝斯史坦伯格賽局報酬矩陣表，解出混合策略貝斯賽局的最適解（均衡），以得到各檢查點的混合策略機率值，最後輸出巡警可能會疏忽的檢查點，並提供每日巡查點的行程表(Suggested schedule)。 

這電腦軟體系統，得到洛杉磯航警局的巡警們的許多正面回應，例如這軟體可以減輕巡警們的工作負荷，提昇破獲率，以及有效地維護機場內入出境旅客的安全。
 參考來源:James Pita, Manish Jain, Fernando Ordonez, Christopher Portway, Milind Tambe, Craig Western, Praveen Paruchuri, Sarit Kraus Using Game Theory for Los Angeles Airport Security, AI Magazine 30(1):43‐57 2009.