基于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 函数无法确保相同参与者分在一组的情况只出现一次的缺点.回溯算法的时间复杂度以及空间复杂度并不适用于参与者人数过大的实验，在下一步的工作中将尝试设计能够大幅降低复杂度的算法.