0 概述

计算社会选择理论作为近年来出现的一个交叉学科, 在经济学、社会学和管理学等领域有着广阔的应用前景。计算社会选择理论的研究主要集中在2个方面^[1]:一方面是对社会选择问题的研究, 如设计公正的投票方法; 另一方面是在计算技术方面的研究, 包括使用人工智能方法对已有的社会选择理论成果进行证明, 进而为找到更多类似结论提供一种新的方法^[2]。此外, 逻辑学也被引入了计算社会选择的研究之中^[3]。选举(或投票)理论是计算社会选择领域里研究的一个重要方向, 它主要研究各种选举方式可能带来的不同结果^[4]。其中, Slater选举的求解复杂度为NP-hard^[5], 与之同为基于距离的偏好聚合策略的Kemeny选举求解复杂度为P_‖^NP-complete^[6-7]。

回答集程序设计(Answer Set Programming, ASP)是一种基于逻辑编程、非单调推理而非函数的声明式推理范式, 是一种描述性问题求解的新范例^[8-10], 即用回答集程序描述所需要求解的问题, 该程序的回答集对应问题的解。随着ASP面向应用的基准测试不断增加^[11], 其被广泛应用于知识表示和推理领域中涉及不完整、不一致和不断变化的信息建模问题^[12]。目前回答集求解器已经实现了高效的求解, 例如clasp、DLV等。正因为ASP是一种描述性的程序设计语言, 所以其编写出的程序具有较高的可读性和可扩展性。

文献[13]提出一种使用ASP来求解Slater选举问题的方法。由于在该方法中ASP编码方式与候选人数量有关, 难以进行扩展, 本文在此基础上, 改进选举的描述方式, 优化回答集程序求解的计算时间复杂度。同时通过同样的思路, 对Kemeny选举进行有效求解。

本文介绍Slater与Kemeny选举策略以及ASP的语法语义, 阐述ASP求解Slater选举的方法及具体的程序编码, 并分析其正确性。

1 基本知识 1.1 Slater及Kemeny选举的描述

Slater选举是一种基于锦标赛的选举方式。一个锦标赛T=(X, A)是一个反对称的完全有向简单图, 其中, X是T中顶点的集合, A是T中的二元关系。对于X中2个不同的顶点x∈X和y∈X, 有且仅有一条边(x, y)∈A或(y, x)∈A, 在投票理论中这种结构会产生一个成对比较的结果。从直观上理解, 锦标赛T包含了所有候选人的集合X和这些候选人之间的二元关系, (x, y)表示候选人x优于候选人y, 反之(y, x)表示候选人y优于x。一个定义在X中的线性序列O为从X集合中选取合适的n个元素x_j(1≤j≤n), 表示为x₁>x₂>…>x_n的形式, 其中x₁是线性序列O的第1个顶点, O表示了所有候选人的排名。

虽然锦标赛上的二元关系可能无法形成严格的线性序列, 但它可以通过逆转这个反对称的完全有向简单图上的边来线性序列化。Slater选举的规则是, 通过逆转最少的边形成线性序列, 线性序列上的最优者即为获胜者^[14]。

假设有9个选民给4个候选人a、b、c、d投票, 得到投票描述(profile)R如下:

有3个人的投票序列为:a>b>c>d;

有2个人的投票序列为:d>b>c>a;

有1个人的投票序列为:c>a>d>b;

有1个人的投票序列为:d>a>c>b;

有1个人的投票序列为:c>d>b>a;

有1个人的投票序列为:d>b>a>c。

根据投票序列可得:m_{(a, b)}=5, m_{(b, a)}=4;m_{(a, c)}=5, m_{(c, a)}=4;m_{(a, d)}=4, m_{(d, a)}=5;m_{(b, c)}=6, m_{(c, b)}=3;m_{(b, d)}=3, m_{(d, b)}=6;m_{(c, d)}=5, m_{(d, c)}=4, 这就构成了一个锦标赛, 但不能构成一个线性序列。

Kemeny选举也是一种基于锦标赛的选举方式。假设有候选人集合A={1, 2, …, m}, 选民集合N={1, 2, …, n}和偏好关系$ \succ $_i∈L(A), i∈N, 候选人x到y的多数边m_R(x, y)的定义是偏向x优于y的选民数与偏向y优于x的选民数之差, 即:

$ {m_R}(x,y) = \left| {\left\{ {i \in N:x{ > _i}y} \right\}} \right| - \left| {\left\{ {i \in N:y{ > _i}x} \right\}} \right| $

加权锦标赛(Weighted Tournament)可以表示为(A, M_R), M_R是m×m的反对称矩阵。当x, y∈A且x≠y时, (M_R)_xy=m_R(x, y)且(M_R)_xx=0。加权锦标赛中的顶点表示候选人, 边的权值即m_R(x, y), 根据投票描述R可得加权锦标赛如图 1所示。

Kemeny选举通常是通过最小化分歧来定义的, 定义一个根据描述R所得排列$ \succ $的Kemeny分数(Score)为$\sum\limits_{i \in N} \tau \left({{ \succ _i}, \succ } \right)$, 其中:

$ \tau \left( {{ \succ _i}, \succ } \right) = \sum\limits_{{\rm{\{ }}x,y{\rm{\} }} \subseteq A} {{d_{x,y}}} \left( {{ \succ _i}, \succ } \right) $

$ {d_{x,y}}\left( {{ \succ _i}, \succ } \right) = \left\{ {\begin{array}{*{20}{l}} {1,x{ \succ _i}y,y \succ x{\rm{ }}\;或\;{\rm{ }}y{ \succ _i}x,x \succ y}\\ {0,其他} \end{array}} \right. $

则Kemeny分数为:

$ \sum\limits_{i \in N} \tau \left( {{ \succ _i}, \succ } \right) = \mathop {\sum\limits_{x,y \in A} {\left| {\left\{ {i \in N:y{ \succ _i}x} \right\}} \right|} }\limits_{x \succ y} = \mathop {\sum\limits_{x,y \in A} {\frac{{{m_R}(y,x) + n}}{2}} }\limits_{x \succ y} $

Kemeny选举就是找出使得分数最小的排列。

1.2 ASP的基本语法和语义

ASP的基本思想是:对一组规则描述给定的问题, 采用ASP求解器计算出回答集, 该回答集即问题的解^[15]。ASP程序的语法与Prolog类似, 是一组在Horn子句基础上构造的逻辑程序^[16]。假设一个命题语言L:

定义1 (正规逻辑程序)  一个正规逻辑程序是如下形式的正规规则的集合^[17-18]:

$ H \leftarrow {a_1},{a_2}, \cdots ,{a_m},{\rm{ not}}\;{\rm{ }}{a_{m + 1}}, \cdots ,{\rm{ not}}\;{\rm{ }}{a_n}. $

其中, 0≤m≤n, a₁, a₂, …, a_n是原子, not表示失败即否定, H是单元素原子集, 若为空, 则此规则称为约束。若一个正规逻辑程序中的所有规则都不含有not, 则称为正程序。

定义2 (正程序的回答集)  给定不含约束和not的正规逻辑程序P, P的回答集S为P的最小Herbrand模型, 且这个回答集模型是唯一的^[19]。

定义3 (不含约束程序回答集)  给定不含约束的正规逻辑程序P和一个原子集S, S是程序P的回答集当且仅当S是P^S的回答集, P^S是P基于S的G-L归约, 它是由P经过如下变换而得^[20]:

1) 如果某规则体中有not q且q∈S, 则删除该规则, 其中q是原子。

2) 删除剩下规则体中的所有not q, 其中q是原子。

2 Slater与Kemeny选举的ASP编码 2.1 Slater选举求解 2.1.1 Slater选举的ASP描述与分析

在Slater选举问题求解中, 将用到以下谓词:ver(X)表示顶点集合, ver_num(X)表示顶点的总数, arc(X, Y)表示有向边的集合, 在锦标赛中表示X优先于Y, arc_num(X)表示有向边的总数。假设有n个候选人, 选民总数为奇数。

对于Slater选举问题, 问题的实例是一个锦标赛, 其编码是描述Slater选举的ASP程序, 包括描述逆转锦标赛的边以形成有向无环图, 描述Slater的获胜者以及描述输出等的规则。Slater选举的求解过程可划分为以下步骤:

步骤1  在给定的锦标赛T中任意逆转一定数量的边得到锦标赛T′, 使T′中不存在回路(即锦标赛T′可以线性序列化), 记这部分ASP规则集为P_normal。

步骤2  求出所有逆转边后得到的锦标赛T′中逆转边数量最少的一个, 得到这个锦标赛的Slater获胜者, 记这部分ASP规则集为P_optimal。

文献[13]方法为先枚举出所有候选人的所有排名序列, 再构造出相应的新锦标赛与原来的对比, 其时间复杂度为O(n!), 并包含规则如下:

$ \begin{array}{*{20}{l}} {{{\rm{c}}_ - }{\rm{d}}\left( {I,{K_1}} \right) \vee \cdots \vee {{\rm{c}}_ - }{\rm{d}}\left( {I,{K_n}} \right) \vee {{\rm{v}}_ - }{\rm{d}}(I,J)}\\ {: ver (I), ver (J)} \end{array} $

因为K₁≠K₂≠…≠K_n, K_i≠J, K_i∈{1, 2, …, n}, 所以在针对不同数量候选人时需要重新编码, 候选人数越多, 编码越冗长。而改进后的回答集程序无需如此。

本文对Slater选举进行回答集求解的技术框架如图 2所示。

2.1.2 P_normal规则集

在给定的锦标赛T中任意逆转一定数量的边得到锦标赛T′, 使T′中不存在回路, P_normal规则集表示如下:

规则1   {re_arc(A, B):arc(B, A), ver(A; B)}H:-arc_num(C), H=C/2.

规则2   slater(A, B):-arc(A, B), not re_arc(B, A), ver(A; B).

规则3   slater(A, B):-re_arc(A, B), ver(A; B).

规则4   :-slater(A, B), slater(B, A).

规则5   reach(A, B):-slater(A, B), ver(A; B).

规则6   reach(A, B):-slater(A, C), reach(C, B), ver(A; B;C).

规则7   :-reach(A, A), ver(A).

规则1中的谓词re_arc(A, B)表示逆转一条(B, A)的边为(A, B)。规则1限定了最多需要逆转H条边, 下文将在2.3节对H进行分析。规则2的语义是将没有被逆转的边arc(A, B)加入到新构造的锦标赛T′中。规则3的语义是将逆转后的边re_arc(A, B)加入到新构造的锦标赛T′中。规则4表示新构造的锦标赛T′是反对称的。这样规则2~规则4就构造出了锦标赛T′, slater(A, B)表示T′的有向边。规则5中的谓词reach(A, B)表示存在一条从A到B的通路, 规则5的语义表示如果锦标赛中存在有向边(A, B), 则就有一条从A到B的通路。规则6的语义表示如果锦标赛中存在有向边(A, C), 且存在从C到B的通路, 则存在一条从A到B的通路。规则7的语义表示如果锦标赛中存在从A到A的回路, 则这个锦标赛是无效的。这样规则5~规则7的语义就限制了锦标赛T′中不能有回路, reach(A, A)表示产生了回路。

2.1.3 P_optimal规则集

在逆转一定数量的边得到锦标赛T′后, 要求出其中逆转边数最少的一个, 并得到T′的胜者, P_optimal规则集表示如下:

规则8  diff(Z):-Z=#count{A, B:re_arc(A, B)}.

规则9   #minimize{Z:diff(Z)}.

规则10   winner(A):-not reach(_, A), ver(A).

规则11   #show re_arc/2.

规则12   #show winner/1.

规则8的语义表示求出锦标赛T′逆转边的数量, 其中diff(X)表示逆转的边数。规则9的语义表示求出T′中逆转边数最少的一个。规则10表示得到对应T′的Slater胜者, 即如果T′中没有任何一个顶点指向A, 则A就是Slater胜者。规则11和规则12的语义表示输出逆转的边以及Slater胜者。

2.2 Kemeny选举求解 2.2.1 Kemeny选举的ASP描述与分析

在Kemeny选举问题求解中, 将用到以下谓词:candidate(X)表示候选人集合, ver_num(X)表示候选人的总数, votes(X, Y, J, K)表示投票描述的集合, 在锦标赛中表示第K种情形有X位选民认为第Y名候选人排名为J, vote(X)表示选民的总人数。对于Kemeny选举问题, 可以把求解过程划分为以下步骤:

步骤1  从给定的投票描述中得到候选人之间的偏好关系, 即可构造出加权锦标赛T_w, 记这部分ASP规则集为P_prefer。

步骤2  在得到的加权锦标赛T_w中任意逆转一定数量的边得到锦标赛T_w′, 使T_w′中不存在回路(即锦标赛T_w′可以线性序列化), 记这部分ASP规则集为P_wnormal。

步骤3  求出所有逆转边后得到的加权锦标赛T_w′中Kemeny分数最小的一个, 得到这个加权锦标赛的Kemeny获胜者, 记这部分ASP规则集为P_woptimal。

本文对Kemeny选举进行回答集求解的技术框架与Slater选举求解相同。

2.2.2 P_prefer规则集

从给定的投票描述中, 得到候选人之间的偏好关系并构造出加权锦标赛T_w, P_prefer规则集表示如下:

规则13  pwt(C, D, G):-G=#sum{X, C, D, K:votes(X, C, P1, K), votes(X, D, P2, K), P1 < P2}, candidate(C; D), C < D.

规则14   pwt(C, D, A-X):-pwt(D, C, X), vote(A), C>D.

规则15   arc(A, B, C):-pwt(A, B, C), pwt(B, A, D), C>D.

规则16   arc(B, A, D):-pwt(A, B, C), pwt(B, A, D), C < D.

规则13中的谓词pwt(C, D, G)表示有G个人认为第C个候选人优于第D个候选人。规则13的语义表示在第K种情形时, 若有X位选民认为第C个候选人的排名为P1且第D个候选人的排名为P2, 当P1 < P2时, 则得出有G位选民认为第C个候选人优于第D个候选人且C < D。规则14的语义表示若有G位选民认为第C个候选人优于第D个候选人且C < D, 选民总数为A, 则有A-X位选民认为第C个候选人优于第D个候选人且C>D。这样规则13和规则14就根据投票描述得到了候选人之间的偏好关系。规则15中的谓词arc(A, B, C)表示在加权锦标赛中, 改变(A, B)这条边的Kemeny分数为C。规则16中的谓词arc(B, A, D)表示在加权锦标赛中, 改变(B, A)这条边的Kemeny分数为D, 下文将在2.3节对C和D进行分析。规则15和规则16的语义表示构造出加权锦标赛T_w, 并得到相应的Kemeny分数。

2.2.3 P_wnormal规则集

在得到的加权锦标赛T_w中任意逆转一定数量的边得到锦标赛T_w′, 使T_w′中不存在回路, P_wnormal规则集表示如下:

规则17  {re_arc(A, B, X):arc(B, A, X), candidate(A; B)}H:-ver_num(C), D=C-1, E=D×C, H=E/4.

规则18   kemeny(A, B):-arc(A, B, X), not re_arc(B, A, X), candidate(A; B).

规则19   kemeny(A, B):-re_arc(A, B, X), candidate(A; B).

规则20   :-kemeny(A, B), kemeny(B, A).

规则21   reach(A, B):-kemeny(A, B), candidate(A; B).

规则22   reach(A, B):-kemeny(A, C), reach(C, B), candidate(A; B;C).

规则23   :-reach(A, A), candidate(A).

规则17中的谓词re_arc(A, B, X)表示逆转一条(B, A)边为(A, B)的Kemeny分数为X。规则17限定了最多需要逆转H条边, 下文将在2.3节对H进行分析。规则18的语义是将没有被逆转的边arc(A, B, X)加入到新构造的锦标赛T_w′中。规则19的语义是将逆转后的边re_arc(A, B, X)加入到新构造的锦标赛T_w′中。规则20表示新构造的锦标赛T_w′是反对称的。这样规则18~规则20就构造出了锦标赛T_w′, kemeny(A, B)表示T_w′的有向边。规则21中的谓词reach(A, B)表示存在一条从A到B的通路。规则21的语义表示如果T_w′中存在有向边(A, B), 则有一条从A到B的通路。规则22的语义表示如果T_w′中存在有向边(A, C), 且存在从C到B的通路, 则存在一条从A到B的通路。规则23的语义表示如果T_w′中存在从A到A的回路, 则T_w′是无效的。这样规则21~规则23的语义就限制了锦标赛T_w′中不能有回路, reach(A, A)表示产生了回路。

2.2.4 P_woptimal规则集

在逆转一定数量的边得到锦标赛T_w′后, 要求出其中Kemeny分数最小的一个, 并得到T_w′的胜者, P_woptimal规则集表示如下:

规则24  diff(Z):-Z=#sum{X, A, B:re_arc(A, B, X)}.

规则25   #minimize{Z:diff(Z)}.

规则26   winner(A):-not reach(_, A), candidate(A).

规则27   #show re_arc/3.

规则28   #show winner/1.

规则24的语义表示求出锦标赛T_w′的Kemeny分数Z, Z为所有逆转的边Kemeny分数的累加。规则25的语义表示求出T_w′中Kemeny分数最小的一个。规则26表示得到对应T_w′的Kemeny胜者, 即如果T_w′中没有任何一个顶点指向A, 则A就是Kemeny胜者。规则27和规则28的语义表示输出逆转的边以及Kemeny胜者。

2.3 正确性分析

在ASP的源代码中, Slater选举的求解要用到规则1~规则12, Kemeny选举的求解要用到规则13~规则28, 下面进行具体分析:

1) 在规则1中, 限定了顶点数为n的锦标赛最多只需逆转的边数为n(n-1)/4, 即总边数的一半, 就可使逆转后的锦标赛中不存在回路。因为一个锦标赛的边数为n(n-1)/2, 给锦标赛中的顶点顺序编号, 若任意2个顶点x、y, 都有x>y或x < y, 则锦标赛中是无环的, 所以至多只需要逆转其中一半的边就可以得到一个有向无环图, 符合锦标赛的定义, 故规则1正确。

2) 在规则2~规则4中, 分别将逆转后的边和没有经过逆转的边选出来构造新的锦标赛, 并规定其中不会出现一对反向的边, 符合锦标赛的定义, 故规则2~规则4正确。

3) 在规则5~规则7中, 限定了逆转后的锦标赛一定不存在回路, 即可以线性序列化并进一步求出获胜者, 符合Slater选举的定义, 故规则5~规则7正确。

4) 在规则8~规则12中, 使用minimize聚集函数计算出与锦标赛T中不同方向边总数最小的锦标赛T′, 再从T′中找到了入度为0的顶点作为Slater获胜者, 符合Slater选举的定义, 故规则8~规则12正确。

5) 在规则13~规则16中, 得到候选人中的偏好关系, 构造出加权锦标赛并得到相应的Kemeny分数。其中, 当有pwt(A, B, C)和pwt(B, A, D)且C>D时, M_R(A, B)=C-D, 若选民总数为n, (M_R(A, B)+n)/2是逆转边(A, B)的Kemeny分数, 带入可得(M_R(A, B)+n)/2=C, 所以arc(A, B, C)符合Kemeny选举的定义, 故规则13~规则16正确。

6) 在规则17中, 限定了顶点数为n的加权锦标赛最多只需逆转的边数为n(n-1)/4, 就可使逆转后的加权锦标赛中不存在回路。在加权锦标赛中, 选民总数为n时, 逆转每一条边的Kemeny分数大于n/2, 故不存在同样情况下逆转2条边的Kemeny分数小于逆转1条边的Kemeny分数的情形, 因此与不带权锦标赛同理, 规则17正确。

7) 规则18~规则28与规则2~规则12同理, 符合加权锦标赛和Kemeny选举的定义, 是正确的。

综上可得, 规则1~规则12将Slater问题映射成ASP问题是正确的; 规则13~规则28将Kemeny问题映射成ASP问题是正确的。

3 实验结果与分析

本文实验在Fedora release 21、32 GB内存、Intel(R) i7-4770K环境下采用clasp回答集求解器进行, 分别在不同候选人数的情况下随机生成100组事实与文献[13]方法进行对比。该问题的ASP编码及其实验数据, 请参见github.com/Shadowdre am1234 56/Slater-ASP。文献[13]方法采用的数据是与Slater选举相关的事实与常量的值, 其中基本谓词包括:ver(X)表示候选人顶点, arc(X, Y)表示有向边, ver_num(X)表示顶点的总数, arc_num(X)表示有向边的总数。

由于选民给出的投票序列不确定, 因此任意2个候选人之间的偏序关系具有随机性, 因此arc(X, Y)由程序随机产生。

将规则1~规则12保存在slater文件中, 分别在候选人数为4、5、6、8和13的情形随机生成的100组投票命名为ver1, ver2, …, ver100, 调用回答集求解器运行, 记录下各自平均运行时间, 并以60 s作为求解时间上限, 结果如表 1所示。

在表 1中, 规则数表示求解过程中实例化的规则数, 平均时长表示每100组实验平均消耗的时间, “—”表示需要消耗的时间超出限定。实验结果表明, 与文献[13]方法相比, 本文方法效率提升显著, 并且在候选人数不同时, 不需要重新设计编码。在Slater选举的计算中, 本文方法的时间耗费主要与规则1~规则7相关, 其时间复杂度低于文献[13]方法的O(n!)。经过测试, 本文方法最多可在60 s内求解14位候选人的Slater选举。

在Kemeny选举求解实验中, 将规则13~规则28放入kemeny文件, 参照文献[21]的实验, 将选民总人数设定为5和35, 测试所用的数据是与Kemeny选举相关的事实与常量的值, 其中基本谓词包括:candidate (X)表示候选人, ver_num(X)表示候选人的总数, votes(X, Y, J, K)表示在锦标赛中第K种情形有X位选民认为第Y名候选人排名为J, vote(X)表示选民的总数。

由于选民给出的投票序列不确定, 每个序列的票数也不确定, 任意2个候选人之间的偏序关系和权值具有随机性, 因此votes(X, Y, J, K)由程序随机生成。分别在候选人数为6、10、15、20, 选民总数为5、35、65的情况随机生成100组投票, 调用回答集求解器运行, 记录下各自平均运行时间, 并以60 s作为求解时间上限, 结果如表 2所示。

在表 2中, “—”表示需要消耗的时间超出限定。实验结果表明, 在候选人数相同时消耗的时间随着选民总数的增加而增长, 候选人数与选民总数相同的情况下也有部分用例需要较长时间求解。经过测试, 在选民总数为35时, 该回答集程序最多可在60 s内求解17位候选人的Kemeny选举。这表明使用描述性方法求解Kemeny选举问题切实可行。

4 结束语

本文对Slater及Kemeny选举问题进行分析, 以ASP方法求解选举结果, 并证明了该方法的正确性。通过回答集求解器进行实验, 结果表明, ASP方法对Slater选举的计算效率显著优于文献[13]方法, 且适用于Kemeny选举。但本文方法时间复杂度仍然较大, 下一步将对其优化并用于计算其他选举策略的获胜者。