基于CSP 方法的經濟學實驗分組問題的設計與實現

陳丹琳

（牛津大學納菲爾德學院社會科學實驗中心中國分部，天津 300071）

經濟學的許多實驗中都會涉及排列組合的分組問題，比如獨裁者博弈[1]、公共物品實驗[2]以及眾多經典的博弈類實驗.在這些實驗中，設計者需要將參與者按照一定數量進行分組，在每輪中會多組同時實驗，并進行多輪[3]，一些實驗還要求幾個參與者被分入同一組的情況只出現一次.

oTree 框架是進行實驗編寫的常用工具，它是使用Python 編寫的行為研究開源平臺框架[4].使用oTree框架編寫實驗時，大部分會使用group_randomly 函數將參與者進行隨機分組，對于N 個參與者P1，P2，…，PN，此函數調用Constants 類中的play_per_group 變量，即每組人數G，然后將參與者隨機排序后進行分組，最終返回一個（N/G）× G 的矩陣作為分組結果. 此函數每次只能完成一輪分組，如果需要進行多輪實驗，則需要重新調用此函數.根據group_randomly 的運行機制，幾個參與者被分入同一組的情況可能會出現多次，而在某些實驗中，這是不允許的. 如，將參與者P1、P2、P3、P4兩兩組合，進行 2 輪，設在第 1 輪使用group_randomly 函數后，分組情況為[[P1，P2]，[P3，P4]]，根據實驗要求，相同2 個參與者再次分入一組的概率應為零，但是在第2 輪調用group_randomly 函數進行分組時，P1、P2分入一組的概率為1/16. 因此利用group_randomly 函數分組不能滿足幾個參與者分在一組只出現一次的要求.為解決這一問題，本研究基于約束滿足類型問題（Constraint satisfaction problem，CSP）的分析方法[5]對此類分組實驗進行分析規制，將分組形式拆解，對任意輪次的任意組中的每個空位構造相對應的值域（可填入此位置的參與者范圍）以及限制條件，然后使用回溯算法[6]解決問題.

1 CSP 和回溯算法模型

1.1 CSP

CSP 廣泛應用于運籌學和人工智能等領域[7]，它通常需要將狀態進行要素化描述，即對每個變量設定相應的值域，當所有變量都被賦值，且其值同時滿足所有約束條件時，問題便得以解決.CSP 通常表現出較高的時間復雜度，因此需要結合啟發式搜索和聯合搜索等方法進行優化.經典的CSP 問題有八皇后問題[8]、地圖著色問題、 數獨問題等，這些問題可以分為二元問題和多元問題，本研究解決的為多元問題.

CSP 主要由 3 個集合組成：V={V1，V2，…，Vm}為變量集，包含所有需要被賦值的變量；D={D1，D2，…，Dn}為值域集，包含每個變量所對應的值域； C = {C1，C2，…，Cp}為限制條件集，包含每個變量的賦值需要同時滿足的所有限制條件.基于這3 個集合，可以定義CSP 問題的狀態空間和問題的解.

1.2 回溯算法

回溯算法是一種十分常用的基本優化搜索方法，通常用于解決CSP 問題[9]. 回溯算法是暴力枚舉的一種改進，通過使用CSP 中的約束條件減少無用的枚舉步驟.

回溯算法的基本思想為：首先對第1 個變量賦值x1，使其滿足所有限制條件，然后對第2 個變量從剩下的可能解中選擇一個滿足所有限制條件的值x2，直到所有變量都已賦值，最終形成完整的解；在賦值過程中，設前 k 個變量依次賦值為 x1，x2，…，xk，如果第k +1 個變量找不到滿足所有限制條件的值，則進行回溯，將第 k 個變量的值 xk刪除，回溯到 x1，x2，…，xk-1的狀態，并對第k 個變量重新賦值，再判斷第k+1個變量是否存在滿足條件的值.回溯算法流程類似于遞歸樹，通常使用深度優先搜索（Deep first search，DFS）的方法實現.

2 算法分析

設有 N 個參與者 P1，P2，…，PN，每 G 個分為一組.分組完成后，得到k=N/G 個組，將這樣的分組重復A 輪，總計得到A·k 個組，在這A·k 個組中，要求相同G 個參與者分入同一組（不論以何種順序排列）的情況只能出現一次.為方便，在下面的算法分析和代碼實現中設 N=20，G=2，A=10.

2.1 CSP 分析

（1）變量集V.變量集V 為一個10×10×2 的矩陣，

其中：Vi，j，k表示第 i 輪中第 j 個組的第 k 個參與者，1≤i≤10，1≤j≤10，k=1、2.

（2）值域集D.值域集D 中的量應與變量集V 中的變量一一對應，因此D 為一個10×10×2×20 的矩陣，

其中：若參與者Pl在第i 輪中被分入第j 個組的第k個位置，則 Di，j，k，l=1，否則 Di，j，k，l=0，1≤i≤10，1≤j≤10，k=1、2，1≤l≤20.

（3）限制條件集C.限制條件集C 為一個20×20的矩陣，

其中 Ci，j的值為分組過程中[Pi，Pj]出現的次數. 參與者Pi、Pj組合的順序會影響 Ci，j和 Cj，i的賦值.

2.2 回溯算法代碼實現

定義{V，D，C}后，使用回溯算法解決 CSP 問題.在問題求解過程中，每一步只討論一個變量的賦值，即每一步只在值域集D 中根據限制條件集C 尋找某個 Vi，j，k的賦值.當 V 中所有變量都已被賦值，則問題解決.變量集 V 中所有 Vi，j，k的初始賦值為-1，當第 i行的所有 Vi，j，k都已被賦除-1 以外的值時，則代表第 i輪分組完成.值域集 D 中所有 Di，j，k，l的初始賦值為 0.限制條件集 C 中所有 Ci，j的初始賦值為 0，且 Ci，j=0或1.

算法程序使用 Python 語言進行編譯，使用Numpy 庫存儲多維數據集{V，D，C}.回溯算法中主要使用了 5 個函數：recursive_wrap，recursive，select_unsigned_var，order_domain_value 和 value_consistent.回溯算法流程圖如圖1 所示.

（1）recursive_wrap 函數. 此函數主要用于對recursive 函數進行包裝，并返回一個長度為2 的表.表中第 1 個元素為 boolean 變量，其值為 True 或False，若為True，則表明分組問題存在完整的合法解，若為False，則表明不存在合法解.當第1 個元素值為True 時，則第2 個元素為完全賦值的數據集V，當第1 個元素值為False 時，則第2 個元素為未完全賦值的數據集V.其偽代碼如下：

圖1 回溯算法流程Fig.1 Process of backtracking algorithm

（2）recursive 函數. 此函數的返回內容與函數recursive_wrap 相同.recursive 函數的詳細步驟為：

①檢查V 中是否存在未賦值的組.若V 中所有的變量都已經被賦值，則recursive 函數返回[True，V]；若V 中還有未被賦值的組，則使用select_unsigned_var 函數得到集合[i，j，k]，選定 Vi，j，k進行賦值.

②運行 order_domain_values 函數，帶入 Vi，j，k，得到可被放入 Vi，j，k的值域集合[a，…，b]，這個集合表示參與者[Pa，…，Pb]在第 i 輪中未被分組，關于[a，…，b]的排列順序，請見后文.

③在循環過程中，根據[a，…，b]將 Pa，…，Pb依次賦值到 Vi，j，k，使用 value_consistent 函數，根據限制集C 判斷 Px是否為 Vi，j，k的合理賦值.如果 Px不能滿足限制集 C 對 Vi，j，k的限制條件，則 value_consistent 會返回-1，即 if_consistent 等于-1，此時在 Pa，…，Pb中重新尋找 Vi，j，k的賦值； 如果 Pa，…，Pb中不存在 Vi，j，k的合法賦值，則recursive 函數返回False.

④如果value_consistent 返回的結果不是-1，則更新{V，D，C}，然后定義變量 result，將更新后的{V，D，C}代入resursive 函數進行賦值，其結果賦給result.如果 result 的第 1 個元素為 False，則將{V，D，C}的更新撤銷，并返回步驟③.

recursive 函數的偽代碼如下：

Def recursive（{V，D，C}）：

If ?Vi，j，k∈V，Vi，j，k≠-1 do：

return[True，V]

end if

Vi，j，k=select_unsigned_var（V）

[a，…，b]=order_domain_values（Vi，j，k，{D，C}）

For ?x，x ∈[a，…，b]do：

if_consistent=value_consistent（Vi，j，k，Px，{V，D，C}）

if if_consistent≠-1，即 Px是 Vi，j，k的合理解：Vi，j，k=Px

更新值域集D

if if_consistent==2 do：

更新限制集C

end if

result=recursive（{V，D，C}）

if result 的第1 個元素不是False，

return result

end if

else：

Vi，j，k=-1

取消值域集的更新

if if_consistent==2：

撤銷限制集C 的更新

end if

end for

return[False，V]

（3）select_unsigned_var 函數.此函數用于尋找數據集 V 中還未被賦值的變量 Vi，j，k，函數返回一個長度為 3 的數據集[i，j，k]，表示 Vi，j，k還未被賦值. select_unsigned_var 函數的偽代碼如下：

Def select_unsigned_var（V）：

for i= 第 1 輪到第 10 輪 do：

for j= 第 1 組到第 10 組 do：

for k=Vi，j，1，Vi，j，2：

if Vi，j，k==-1：

return[i，j，k]

end if

end for

end for

end for

return-1

（4）order_domain_values 函數.此函數根據select_unsigned_var 函數中得到的[i，j，k]，在 D 中尋找第 i輪中還未出現過的所有參與者，即返回D 的第i 行j 列第 k 個集合里所有等于 0 的 Di，j，k，l.若此輪所有參與者已經都完成分組，函數則返回一個空的表. order_domain_values 函數的偽代碼如下：

def order_domain_values（[i，j，k]，D，C）：

player_list=[]

for j=Di，j，k，1，…，Di，j，k，20do：

if Di，j，k，l=0：

player_list.append（l）

end if

end for

根據限制集C，將player_list 中的l 按限制條件由多到少排列.

return player_list

這里使用了最小剩余值（Minimum-remaining-values，MRV）技巧，以改變player_list 中元素的排列順序，從而對合法值的選擇進行優化. 集合[a，…，b]表示參與者[Pa，…，Pb]在第 i 輪中未被分組，通過檢查限制集C，可得[Pa，…，Pb]中的 Px還能與多少參與者進行組合，可與Px組合的參與者越多則受到的限制越少.因此將[a，…，b]按照限制由多至少的順序進行排列可提高賦值的成功率，從而降低程序的時間復雜度.

（5）value_consistent 函數. 此函數用于判斷 Px是否為 Vi，j，k的合法賦值，如果是，則返回 1 或 2，如果不是，則返回-1.value_consistent 函數的偽代碼如下：

def value_consistent（{V，D，C}，[i，j，k]，Px）：

if 與 Vi，j，k同組的成員還未確定：

return 1

else：

match= 與 Vi，j，k同組的參與者為 Px

if y≠x 且 Cx，y+Cy，x==0：

return 2

end if

end if

return-1

3 仿真實驗

使用Python 分別編寫了關于分組問題回溯算法的程序和包含MRV 技巧的程序，在CPU 為1.6 GHz Intel Core i5、 操作系統為macOS Sierra10.12.6 的 Mac air 計算機上運行. 設定參與者 N = 16、18、20、22，每組人數G = 2，共進行10 輪分組，利用程序進行測試，程序運行時間見表1，以N=20 為例，10 輪的分組結果見表2.由表1 和表2 可知，本文基于CSP 的分組問題的回溯算法是有效的，且利用MRV 優化的回溯算法可有效降低算法的時間復雜度.

表1 仿真實驗運行時間Tab.1 Run time of simulation experiments

表2 N=20 的分組結果Tab.2 Grouped results when N=20

4 結語

將經濟學經典實驗中分組問題歸類為CSP，并將問題拆解成變量集、 值域集以及約束條件集的形式，并使用回溯算法實現分組. 本文算法有效彌補了oTree 中group_randomly 函數無法確保相同參與者分在一組的情況只出現一次的缺點.回溯算法的時間復雜度以及空間復雜度并不適用于參與者人數過大的實驗，在下一步的工作中將嘗試設計能夠大幅降低復雜度的算法.