優(yōu)化計(jì)算slater投票獲勝者的Picat方法

摘要：slater投票規(guī)則是基于錦標(biāo)賽的投票規(guī)則，主要是通過構(gòu)造無(wú)環(huán)錦標(biāo)賽，找到與原錦標(biāo)賽差異最小的一個(gè)，從中選出獲勝者。針對(duì)求解難度為NP難的slater投票算法，提出了一種基于相似候選項(xiàng)集的優(yōu)化求解slater問題的Picat方法。相比于非優(yōu)化求解slater問題的方法，該方法縮小了slater算法的解空間，有效地減少了求解slater獲勝者的計(jì)算量，提高了計(jì)算速度。實(shí)驗(yàn)結(jié)果表明，優(yōu)化求解slater問題的Picat方法的計(jì)算速度優(yōu)于非優(yōu)化的Picat方法；當(dāng)候選項(xiàng)人數(shù)少于20時(shí)，求解slater問題的回答集程序（ASP）方法的計(jì)算速度和計(jì)算能力優(yōu)于優(yōu)化的Picat方法，但當(dāng)候選項(xiàng)人數(shù)超過30時(shí)，優(yōu)化的Picat方法（用可滿足問題求解器）的計(jì)算速度和計(jì)算能力優(yōu)于ASP方法。

關(guān)鍵詞：slater投票問題；NP難問題；約束滿足問題；Picat程序設(shè)計(jì)；錦標(biāo)賽；線性序列

中圖分類號(hào)：TP305文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695（2022）08-004-2268-05

doi：10.19734/j.issn.1001-3695.2022.01.0013

Optimizing Picat method for calculating slater voting winners

Ao Huan1a，1b，Wang Yisong1a，1b，F(xiàn)eng Renyan1a，1b，Deng Zhouhui2，Tong Tianle3

（1.a.School of Computer Science amp; Technology，b.Institute of Artificial Intelligence，Guizhou University，Guiyang 550025，China；2.Kechuang Industrial Development Co.Ltd.，Guiyang 550025，China；3.Guizhou Donkey Technologies Co.Ltd.，Guiyang 550025，China）

Abstract：The slater voting rule is a tournament-based voting rule.It mainly constructs a ringless tournament，finds the one with the smallest difference from the original tournament，and selects the winner from it.Aiming at the NP-hard slater voting algorithm，this paper proposed a Picat method to solve the slater problem based on the optimization of similar candidate item sets.Compared with the non-optimized Picat method for solving the slater problem，this method reduced the solution space of the slater algorithm，effectively reduced the amount of calculation for solving the slater winner，and improved the calculation speed.The experimental results show that the computational speed of the optimized Picat method for solving the slater problem is better than that of the non-optimized.When the number of candidates is less than 20，the computational speed and computing power of the answer set program（ASP） method for solving the slater problem are better than those of the optimized Picat method，but when the number of candidates exceeds 30，the optimized Picat method（with a satisfiable problem solver） outperforms the ASP method in terms of computational speed and computational power.

Key words：slater voting；NP-hard problem；constraint satisfaction problem；Picat programming；tournament；linear sequence

可計(jì)算社會(huì)選擇理論（computational social choice，COMSOC）是社會(huì)選擇理論和計(jì)算機(jī)科學(xué)融合而成的一個(gè)交叉學(xué)科，在人工智能、經(jīng)濟(jì)和計(jì)算性理論等領(lǐng)域有著廣闊的應(yīng)用前景[1～3]。社會(huì)選擇研究各種社會(huì)決策能否尊重個(gè)體偏好和平衡利益分配，投票是最普遍的社會(huì)決策方式，其作用是將個(gè)人偏好轉(zhuǎn)換為社會(huì)偏好，因此投票理論是可計(jì)算社會(huì)選擇理論的主要研究?jī)?nèi)容之一。研究者先后提出了各種投票投票算法規(guī)則：Kemeny[4]、slater[5]、banks[6]，其中slater投票算法的求解復(fù)雜度為Θp2-完全的[7]，該算法求解的slater問題是約束滿足問題。

Picat程序設(shè)計(jì)是一種描述性問題求解的新范例。Picat程序設(shè)計(jì)針對(duì)約束滿足問題的設(shè)計(jì)思想是：用一組規(guī)則描述所需要求解的問題，然后用相應(yīng)的求解器計(jì)算出問題的解[8]。Picat融合了聲明式語(yǔ)言特性和命令式語(yǔ)言特性，既有類似Prolog的聲明式語(yǔ)言特性，又具有數(shù)組、函數(shù)等命令式語(yǔ)言的特性，因此用Picat對(duì)組合優(yōu)化問題進(jìn)行建模非常方便[9]。文獻(xiàn)[10～12]提出使用回答集程序設(shè)計(jì)（ASP）求解slater問題的方法。用ASP求解slater問題，雖然可以計(jì)算出至少一種解決方案，但當(dāng)求解問題規(guī)模較大時(shí)，計(jì)算時(shí)間過長(zhǎng)。鑒于在求解多人尋路問題（multi-agent pathfinding problem）的實(shí)驗(yàn)中，當(dāng)問題規(guī)模較大時(shí)，Picat的求解時(shí)間少于ASP的[13]，此外，slater問題是約束滿足問題，而Picat支持約束編程，內(nèi)置了三種求解器，都可以用來(lái)求解約束滿足問題，所以本文用Picat求解slater問題。此外，文獻(xiàn)[14]提出了優(yōu)化求解slater問題的方法，本文會(huì)用Picat實(shí)現(xiàn)優(yōu)化的方法，以此求解slater問題。

1背景知識(shí)

1.1問題描述

投票活動(dòng)中，當(dāng)候選人數(shù)達(dá)到三個(gè)或三個(gè)以上，在成對(duì)候選項(xiàng)的選擇結(jié)果中可能會(huì)出現(xiàn)“投票悖論”問題，即循環(huán)的選擇結(jié)果[15]。例如，假設(shè)有三個(gè)候選項(xiàng)A、B、C，三個(gè)人的投票分別為Agt;Bgt;C，Bgt;Cgt;A 和Cgt;Agt;B（xgt;y 表示x比y好）。按照少數(shù)服從多數(shù)原則，這樣無(wú)法確定獲勝者（或者A、B、C都可能是獲勝者）。針對(duì)投票悖論問題，研究者們提出了各種投票算法。slater投票算法就是其中之一。

1.2slater投票

slater投票是基于錦標(biāo)賽的一種投票方式。錦標(biāo)賽T=（C，P），C是候選項(xiàng)集，P是集C上的完全二元關(guān)系，表示兩兩候選項(xiàng)之間的集體偏好關(guān)系，集體偏好關(guān)系反映的是兩個(gè)候選項(xiàng)之間支持票數(shù)的多少。設(shè)x和y為任意兩個(gè)候選項(xiàng)，（x，y）∈P（記為xgt;y），表示支持x的票數(shù)多于支持y的。因此，錦標(biāo)賽是個(gè)反對(duì)稱的有向完全簡(jiǎn)單圖。對(duì)于具有 n個(gè)元素的集合 C和C中的元素xi（1≤i≤n），稱l=x1gt;…gt;xn（xi∈C，1≤i≤n）為集合C上的任一嚴(yán)格線性序列，也記l={（xi，xj）|1≤ilt;j≤n}。錦標(biāo)賽可能不能形成一個(gè)嚴(yán)格的線性序列。

定義1slater分?jǐn)?shù)。給定錦標(biāo)賽T=（C，P），C上的一嚴(yán)格線性序列l(wèi)關(guān)于T的slater分?jǐn)?shù)定義為：|{（x，y）|（x，y）∈l且（y，x）∈P}|。

具有最小slater分?jǐn)?shù)的任何C上的線性序列，被稱為slater序列，slater獲勝者即slater序列的首項(xiàng)。slater問題即求解錦標(biāo)賽T的slater獲勝者。

研究者們認(rèn)為slater問題至少是NP難問題，對(duì)slater問題的計(jì)算復(fù)雜度的最新研究表明slater問題是Θp2類問題[5，16]。Lampis[7]證明slater問題是Θp2-完全問題。slater問題的研究目標(biāo)是研究在多項(xiàng)式時(shí)間之內(nèi)計(jì)算出任何錦標(biāo)賽的slater序列的方法。該方法可以用于求解回饋弧集問題（feedback arc set problem），該問題是錦標(biāo)賽研究中的NP完全問題[14，17～19]。

在2019年，Bachmeier等人[20]指出即使只有七名選民的情況下，求解slater問題的計(jì)算復(fù)雜度仍是NP難的。2021年，Lampis[7]指出即使只有七名選民的情況下，求解slater問題的計(jì)算復(fù)雜度是Θp2-完全的。因此slater問題是難計(jì)算的。

用Picat求解slater問題的難點(diǎn)，首先是如何構(gòu)造可以描述投票描述的謂詞，根據(jù)投票描述的謂詞構(gòu)造錦標(biāo)賽。2019年，徐珩僭等人[11，12]提出了一種基于回答集程序（ASP）的計(jì)算slater問題的方法。本文借鑒了其中定義投票描述的謂詞構(gòu)造錦標(biāo)賽。

再者，設(shè)計(jì)優(yōu)化求解的算法是又一難點(diǎn)。構(gòu)造完錦標(biāo)賽之后，非優(yōu)化求解slater問題的方法是利用求解器枚舉所有的線性序列，與錦標(biāo)賽比較，找出其中差異最小的，即slater分?jǐn)?shù)最小的，從而求出獲勝者，其時(shí)間復(fù)雜度是O（n！）。這樣隨著問題規(guī)模的增大，用非優(yōu)化方法求解slater獲勝者的計(jì)算時(shí)間過長(zhǎng)。

2006年Conitzer[14]提出優(yōu)化求解slater問題的新方法，為候選項(xiàng)引入相似性概念，即相似的項(xiàng)與任何其他項(xiàng)具有相同的偏好關(guān)系。通過搜尋原錦標(biāo)賽中的相似項(xiàng)集構(gòu)造加權(quán)錦標(biāo)賽，該加權(quán)錦標(biāo)賽的每一個(gè)頂點(diǎn)是一個(gè)相似項(xiàng)集，先計(jì)算加權(quán)錦標(biāo)賽的slater獲勝者，該獲勝者是一個(gè)相似項(xiàng)集，該相似項(xiàng)集中有一個(gè)候選項(xiàng)是原錦標(biāo)賽的獲勝者。然后遞歸求解由該相似項(xiàng)集構(gòu)成的子錦標(biāo)賽的slater獲勝者，該slater獲勝者即為原錦標(biāo)賽的slater獲勝者。下面詳細(xì)介紹其基本概念。

定義2極大相似項(xiàng)集。給定錦標(biāo)賽T=（C，P），若SC，且對(duì)于任意兩個(gè)候選項(xiàng)x，y∈S，對(duì)于任意z∈C-S，xgt;z當(dāng)且僅當(dāng)ygt;z，或者zgt;x當(dāng)且僅當(dāng)zgt;y，則稱S為極大相似項(xiàng)集，稱S中的候選項(xiàng)為相似項(xiàng)。

極大相似項(xiàng)集分為非平凡相似項(xiàng)集和平凡相似項(xiàng)集兩種。單個(gè)候選項(xiàng)和全體候選項(xiàng)都能構(gòu)成一個(gè)相似項(xiàng)集，即若|S|=1或者|S|=|C|則稱S為平凡相似項(xiàng)集。若錦標(biāo)賽中只存在平凡相似項(xiàng)集，則不能用優(yōu)化方法求解slater獲勝者。若1lt;|S|lt;|C|，則稱S為非平凡相似項(xiàng)集。優(yōu)化算法的關(guān)鍵步驟是找出錦標(biāo)賽中存在的非平凡相似項(xiàng)集。

定義3加權(quán)錦標(biāo)賽。給定錦標(biāo)賽T=（C，P），其加權(quán)錦標(biāo)賽為Tw=（Cw，Pw），其中Cw={S1，…，Sk}是C的極大相似項(xiàng)集的集合，即每個(gè)Si（1≤i≤k）都是C上的一個(gè)極大相似集，其中k=|Cw|，而且每個(gè)Si都自帶權(quán)重，權(quán)重值為|Si|。

給定加權(quán)錦標(biāo)賽Tw=（Cw，Pw），Cw上的一個(gè)嚴(yán)格線性序列wl的加權(quán)slater分?jǐn)?shù)定義為

∑（Sm，Sj）∈wlΔPw|Sm|×|Sj|（1）

加權(quán)錦標(biāo)賽Tw的slater獲勝者是具有最小加權(quán)slater分?jǐn)?shù)的任何Cw上的線性序列的首項(xiàng)。

1.3Picat程序設(shè)計(jì)

Picat是通用目的編程語(yǔ)言（http：//picat-lang.org/index.html），它結(jié)合了邏輯程序設(shè)計(jì)、函數(shù)式程序設(shè)計(jì)、約束程序設(shè)計(jì)和腳本語(yǔ)言等的特征；支持邏輯的合一、非確定選擇、查表（tabling）等計(jì)算特征，也支持循環(huán)、數(shù)組、列表等控制和多種數(shù)據(jù)結(jié)構(gòu)，基于高效的Prolog引擎B-Prolog；目前結(jié)合了可滿足問題（SAT）求解器、約束問題（CP）求解器和混合整數(shù)規(guī)劃（MIP）求解器，被廣泛應(yīng)用在組合優(yōu)化、圖搜索和大量邏輯難題[8，9]。

2計(jì)算slater獲勝者算法

2.1構(gòu)造相似項(xiàng)集

給定錦標(biāo)賽T=（C，P），優(yōu)化求解slater投票獲勝者的第一步是找出錦標(biāo)賽中存在的非平凡相似項(xiàng)集。

設(shè)S為T中的一個(gè)極大相似項(xiàng)集，因?yàn)閷ふ业氖欠瞧椒蚕嗨祈?xiàng)集，所以S中至少有兩個(gè)元素，所以任取兩個(gè)不同的候選項(xiàng)x，y∈C作為S的初始值，即S：={x，y}。如算法1中步驟a）所示。根據(jù)定義2可知，對(duì)于任意的非平凡相似項(xiàng)集S，滿足性質(zhì)1。

性質(zhì)1不存在s1，s2∈S，c∈C-S使得s1gt;cgt;s2（或者s2gt;cgt;s1），即不存在s1，s2∈S，c∈C-S使得（s1，c）∈P并且（c，s2）∈P。性質(zhì)1在第3章正確性分析中，將給出證明。

為了確保x，y滿足性質(zhì)1，因此令S1：={c∈C|xgt;cgt;y}，S2：={c∈C|ygt;cgt;x}，S1和S2都是S的子集，如算法1中步驟b）～d）所示。因?yàn)镾1，S2S，所以對(duì)于任意c∈S1∪S2，也要滿足性質(zhì)1，故若存在{u，v}S，a∈C-S，使得（u，a）∈P，（a，v）∈P，則a∈S。令S3={a∈C-S|ugt;agt;v，{u，v}S}，S3也是S的子集。如算法1中步驟e）～g）所示。

最后，輸出相似項(xiàng)集S={x，y}∪S1∪S2∪S3，如算法1中步驟h）所示。

給定錦標(biāo)賽T=（C，P）及任選兩個(gè)不同候選項(xiàng)x，y∈C，計(jì)算包含x，y的非平凡相似項(xiàng)集的方法MST（x，y，T）如下：

算法1MST（T=（C，P），{x，y}C）

輸入：T=（C，P），{x，y}C。

輸出：包含x，y的單個(gè)極大相似項(xiàng)集S。

a） S：={x，y}；

b） S1：={c∈C|xgt;cgt;y}；

c） S2：={c∈C|ygt;cgt;x}；

d） S：=S∪S1∪S2；

e） E：=C-S；

f） while （a∈E，{u，v}S使得（u，a）∈P，（a，v）∈P）

g） S：=S∪{a}；E：=E-{a}

h） return S

2.2構(gòu)造加權(quán)錦標(biāo)賽

給定錦標(biāo)賽T=（C，P），優(yōu)化求解slater投票獲勝者的第二步是根據(jù)錦標(biāo)賽T構(gòu)造其加權(quán)錦標(biāo)賽Tw=（Cw，Pw），主要是構(gòu)造Cw和Pw，且初始值都為空集，TL表示可能存在新的相似項(xiàng)集的集合，其初始值為C，fail表示不在同一個(gè)相似項(xiàng)集中的兩個(gè)候選項(xiàng)的集合，其初始值為空值。如算法2中步驟a）所示。

Cw是錦標(biāo)賽T中的所有極大相似項(xiàng)集的集合。換句話說(shuō)，加權(quán)錦標(biāo)賽中每個(gè)頂點(diǎn)都是一個(gè)極大相似項(xiàng)集，無(wú)論平凡的還是非平凡的。而利用算法1計(jì)算出T中的極大相似項(xiàng)集的條件是，任取的兩個(gè)候選項(xiàng)x，y可能互為相似項(xiàng) ，即（x，y）fail并且x，y不能是別的非平凡相似項(xiàng)集中的候選項(xiàng)，即{x，y}TL。此外，TL中至少要有兩個(gè)候選項(xiàng)待選，即|TL|gt;2，如算法2中步驟b）所示。

算法1的計(jì)算出來(lái)的極大相似項(xiàng)集S分為兩種：若是非平凡相似項(xiàng)集，則S是Cw中的元素；若是平凡相似項(xiàng)集，則說(shuō)明x，y不是同一個(gè)相似項(xiàng)集中的元素。因此{(lán)（x，y），（y，x）}是fail的子集，如算法2中步驟b）～g）所示。

任取兩個(gè)相似項(xiàng)集S1，S2∈Cw，ci∈S1，cj∈S2，因?yàn)镾1，S2由相似項(xiàng)構(gòu)成，相似項(xiàng)在錦標(biāo)賽T中具有相同的偏好關(guān)系，所以，下面兩種情況必然可以滿足一個(gè)：a）對(duì)于每一個(gè)ci，cj，都存在ci→cj；b）對(duì)于每一個(gè)ci，cj，都存在cj→ci。

因此在加權(quán)錦標(biāo)賽Tw=（Cw，Pw）中，若（ci，cj）∈P，則（S1，S2）∈Pw；反之，（cj，ci）∈P，則（S2，S1）∈Pw如算法2中步驟j）～l）所示。

給定錦標(biāo)賽T=（C，P），計(jì)算其加權(quán)錦標(biāo)賽的方法MST（T）如下：

算法2MST（T=（C，P））

輸入：錦標(biāo)賽T。

輸出：由T的所有極大相似項(xiàng)集的集合Cw構(gòu)成的加權(quán)錦標(biāo)賽Tw。

a） Cw：=；TL：=C；fail：=；Pw：=

b） while（|TL| ≥ 2并且{x，y}TL并且（x，y）fail）

c） S：=MST（x，y，TL）；

d） if（1lt;|S|lt;|C|） then

e） Cw：=Cw∪{S} ；TL：=TL-S；

f） else

g） fail：=fail∪{（x，y），（y，x）}

h） foreach（a∈TL）

i）Cw：=Cw∪{{a}}；

j） foreach（{x，y}Cw）

k） if（u∈x，v∈y使得（u，v）∈P） then

l）Pw：=Pw∪{（x，y）}

m） return Tw=（Cw，Pw）

2.3計(jì)算出加權(quán)錦標(biāo)賽的一個(gè)slater獲勝者

給定錦標(biāo)賽T=（C，P），優(yōu)化求解slater投票獲勝者的第三步是計(jì)算出加權(quán)錦標(biāo)賽Tw=（Cw，Pw）的一個(gè)slater獲勝者。

給定一個(gè)加權(quán)錦標(biāo)賽Tw=（Cw，Pw），wl為任意Cw上的嚴(yán)格線性序列，Cw上具有最小加權(quán)slater分?jǐn)?shù)的嚴(yán)格線性序列為Tw的slater序列，其首項(xiàng)為Tw的一個(gè)slater獲勝者。所以主要分為兩步：a）描述Cw上的嚴(yán)格線性序列wl；b）求解出Cw上具有最小加權(quán)slater分?jǐn)?shù)的嚴(yán)格線性序列。

對(duì)具有k個(gè)元素的Cw和Cw中的元素Si（1≤i≤k），稱wl=S1gt;…gt;Sk為Cw上的任意嚴(yán)格線性序列，又記作wl={（Si，Sj）|1≤ilt;j≤k}，即每個(gè)嚴(yán)格線性序列可以看做一個(gè)有序二元組集合。

任意兩個(gè)Cw上的嚴(yán)格線性序列之間的區(qū)別在于各個(gè)Si的排列順序。因此描述wl的關(guān)鍵在于描述wl中各個(gè)Si的排列順序。

設(shè)c：={si|1≤i≤k}，其中k=|Cw|，si∈{1，..，k}，si的取值表示任意wl中Si的排列位置，而且si的取值為1～k。例如，Cw={S1，S2，S3}，c={3，1，2}，可以表示Cw上的一個(gè)線性序列S2gt;S3gt;S1。

集合c還有一個(gè)必要的約束條件，即c中k個(gè)元素的取值各不相同，all_different（c）可以確保c中的各個(gè)元素各不相等。all_different（FVar）是Picat內(nèi)置的約束謂詞，它的作用是確保集合FVar中任意兩個(gè)元素各不相等。對(duì)于任意V1，V2∈FVar，編譯之后，all_different（FVar）會(huì)生成不等約束，即V1≠V2。所以，對(duì)于任意si，sj∈c，編譯之后all_different（c）會(huì)生成si≠sj的約束，以確保c中的元素各不相同。例如，|c|=3，實(shí)例化c時(shí)，{1，1，1}或者{2，1，2}都不會(huì)是c。

所以令Cw：={S1，…，Sk}，c：={s1，…，sk}，其中si∈{1，…，k}，1≤i≤k并且c滿足all_different（c），則c可以描述Cw上任意嚴(yán)格線性序列。如算法3所示。

約束minimize∑1≤ilt;j≤k，silt;sj（Ssj，Ssi）∈Pw|Si|×|Sj|可以求解出Cw上具有最小加權(quán)slater分?jǐn)?shù)的嚴(yán)格線性序列。如算法3步驟b）所示。后文在第3章正確性分析中證明。

計(jì)算出加權(quán)錦標(biāo)賽Tw的一個(gè)slater序列之后，該slater序列的首項(xiàng)即加權(quán)錦標(biāo)賽Tw的一個(gè)slater獲勝者。如算法3中步驟c）所示。

給定一個(gè)加權(quán)錦標(biāo)賽Tw=（Cw，Pw），計(jì)算出加權(quán)錦標(biāo)賽Tw的一個(gè)slater獲勝者方法slater_winner_w（Tw=（Cw，Pw））如下：

算法3slater_winner_w（Tw=（Cw，Pw））

輸入：加權(quán)錦標(biāo)賽Tw。

輸出：Tw的一個(gè)slater勝者Smin（c）。

a） 令Cw：={S1，…，Sk}，c：={s1，…，sk}/*si 的取值表示Si在一個(gè)嚴(yán)格線性序列中的排序*/

b） minimize∑1≤ilt;j≤k，silt;sj（Ssj，Ssi）∈Pw|Si|×|Sj|

s.t.1≤i≤k，si∈{1，…，k}，all_different（c）

//all_different（c）表示c中的各個(gè)變量的取值不同

//可用SAT、CP、MIP等求解器計(jì)算上述優(yōu)化minimize問題

c） return Smin（c）

注意，算法slater_winner_w也可用于計(jì)算非加權(quán)錦標(biāo)賽T=（C，P）的slater獲勝者，此時(shí)C中每一個(gè)候選項(xiàng)ci（1≤i≤n）都可以看做一個(gè)平凡相似項(xiàng)集{ci}。下面采用Conitzer 方法計(jì)算錦標(biāo)賽的slater獲勝者。即Cw中每個(gè)相似項(xiàng)集恰好都只有1個(gè)候選項(xiàng)（權(quán)重都為1）時(shí)，Cw={{c1}，…，{cn}}，則該加權(quán)錦標(biāo)賽Tw=（Cw，Pw）就是一個(gè)錦標(biāo)賽T=（C，P），其獲勝者就是slater獲勝者，故該方法slater_winner_w稱為計(jì)算slater獲勝者的非優(yōu)化方法。

2.4計(jì)算錦標(biāo)賽T的slater算法

給定錦標(biāo)賽T=（C，P），構(gòu)造加權(quán)錦標(biāo)賽Tw=（Cw，Pw），計(jì)算出加權(quán)錦標(biāo)賽Tw的一個(gè)slater獲勝者為Sw。而Sw是一個(gè)極大相似項(xiàng)集，優(yōu)化求解slater投票獲勝者的前三步如算法4中步驟a）～c）所示。

優(yōu)化求解slater投票獲勝者的第四步是遞歸求解由H構(gòu)成的子錦標(biāo)賽Tsub=（Sw，P|Sw）的slater獲勝者，其中（P|Sw）P，（P|Sw）表示{（x，y）|（x，y）∈S2w ∩P}，即由極大相似項(xiàng)集Sw中每一個(gè)候選項(xiàng)之間相連的邊構(gòu)成的邊集。子錦標(biāo)賽Tsub 的slater獲勝者即錦標(biāo)賽T=（C，P）的slater獲勝者。如算法4中步驟d）～e）所示。

給定錦標(biāo)賽T=（C，P），計(jì)算錦標(biāo)賽T的slater獲勝者的算法如下：

算法4slater_winner（T=（C，P））

輸入：錦標(biāo)賽T=（C，P）。

輸出：錦標(biāo)賽的一個(gè)slater獲勝者。

a） 計(jì)算C的極大相似項(xiàng)集的集合Cw：={S1，…，Sk}

b） 由Cw和T構(gòu)造出加權(quán)錦標(biāo)賽Tw=（Cw，Pw）

c） 計(jì)算出加權(quán)錦標(biāo)賽Tw的一個(gè)slater獲勝者Sw：=slater_winner_w（Tw）

d） 遞歸求解子錦標(biāo)賽Tsub=（Sw，P|Sw）的slater獲勝者w：=slater_winner_w（Tsub=（Sw，P|Sw））

e） 返回w

3正確性分析

算法4即優(yōu)化求解slater問題方法。現(xiàn)在分析四個(gè)步驟的正確性，以此證明優(yōu)化求解slater問題的方法的正確性。

定理1若S為相似項(xiàng)集，則存在一個(gè)原錦標(biāo)賽T上的slater序列，S中的候選項(xiàng)能夠構(gòu)成該slater序列中連續(xù)的一塊子序列（因此，不存在s1，s2∈S，c∈C-S使得（s1，c）∈P并且（c，s2）∈P）。

證明設(shè)有兩個(gè)C上的嚴(yán)格線性序列1，2， S中的候選項(xiàng)在1上被分割成m（mgt;1）塊；而S中的候選項(xiàng)在2上被分割成m-1塊。下面將闡述如何將1轉(zhuǎn)換成2，而且1和2的slater分?jǐn)?shù)相同。

設(shè)1由三塊組成：{s1i}，{s2i}S和{ci}C-S，S中的候選項(xiàng)被{ci}分割成兩塊：s111s121…1s1l11c11c21…1cl1s211s221…1s2l2。因?yàn)镾是相似項(xiàng)集，則給定一個(gè)ci，其在錦標(biāo)賽T中與每一個(gè)sji具有相同的偏好關(guān)系，要么是ci→sji，要么是sji→ci。因此，下面兩種情況，{ci}必然能滿足其中一種：

a）{ci}中至少有一半ci使得ci→sji；

b）{ci}中至少有一半ci使得sji→ci。

如果是情況a），則可以將1轉(zhuǎn)換c12c22…2cl2s212s222…2s2l22s112s122…2s1l1。設(shè){s1i}上的slater分?jǐn)?shù)為A1，{s2i}上的slater分?jǐn)?shù)為A2，因?yàn)閘=|{ci}|，假設(shè){ci}中有p個(gè)ci使得ci→sji，q個(gè)ci使得sji→ci，而且p+q=l。那么2和1的slater分?jǐn)?shù)都是l+A1+A2。同理，如果是情況b） 則可以將1轉(zhuǎn)換為s212s222…2s2l22s112s122…2s1l12c12c22…2cl，2的slater分?jǐn)?shù)也是l+A1+A2。換句話說(shuō)，1等價(jià)于2。

上述轉(zhuǎn)換在S被分割成m（mgt;2）時(shí)，同樣適用，重復(fù)多次這種轉(zhuǎn)換，可以將原來(lái)的線性序列轉(zhuǎn)換成新的線性序列，原來(lái)的線性序列中同一相似項(xiàng)集S中的元素被分割成多塊，新的線性序列中同一相似項(xiàng)集S中的候選項(xiàng)是一塊的。而且兩個(gè)線性序列的slater分?jǐn)?shù)是一樣的。定理1得證。

算法1構(gòu)造相似項(xiàng)集的方法是正確的，且每個(gè)相似項(xiàng)集都是極大的。分析如下。

設(shè)SC且|S|≥2，根據(jù)投票悖論的定義可知，|C|≥3，下面分情況分析構(gòu)造相似項(xiàng)集S的過程：

a）當(dāng)|S|=2，|C|≥3時(shí)，s1，s2∈S，因?yàn)閟i（i=1，2）是相似項(xiàng)，故對(duì)于任意t∈C-S，每一個(gè)si，存在tgt;si或者sigt;t，不存在s1gt;tgt;s2。

b）當(dāng)|S|=|C|=3時(shí)，則S為平凡相似項(xiàng)集，S=C，因?yàn)閠∈S，故不存在s1gt;tgt;s2。

c）當(dāng)|S|=3，|C|gt;3時(shí)，設(shè)有一嚴(yán)格序列3中，C被分成三塊{c1i}，{c2j}，{t}：c113c123…3c1l33s13t3s23c213c223…3c2l4。其中，對(duì)于每一個(gè)cji，對(duì)于任意r∈{s1，s2，t}，存在cjigt;r或者rgt;cji。根據(jù)極大相似項(xiàng)集的定義以及定理1可知，因?yàn)閟1，s2∈S，故t∈S。因此不存在s1gt;tgt;s2。

d）當(dāng)|S|gt;3，|C|gt;3時(shí)，根據(jù)情況b）c）的分析，同理可知，對(duì)于任意s1，s2∈S，t∈C-S，不存在s1gt;tgt;s2，因?yàn)槿魋1gt;tgt;s2，則t∈S。

綜上所述，在錦標(biāo)賽T=（C，P）中，任意s1，s2∈S，t∈C-S，若s1gt;tgt;s2，則t∈S。因此算法1構(gòu)造相似項(xiàng)集的方法是符合相似項(xiàng)集定義的，是正確的。

算法2中構(gòu)造加權(quán)錦標(biāo)賽的方法是正確的，分析如下：給定錦標(biāo)賽T=（C，P），構(gòu)造加權(quán)錦標(biāo)賽Tw=（Cw，Pw），加權(quán)錦標(biāo)賽中每個(gè)頂點(diǎn)都是一個(gè)相似項(xiàng)集，無(wú)論是非平凡相似項(xiàng)集還是平凡相似項(xiàng)集。Tw中一個(gè)頂點(diǎn)（相似項(xiàng)集）與其他頂點(diǎn)之間的邊的指向性取決于該相似項(xiàng)集中候選項(xiàng)的偏好關(guān)系。算法2的算法描述和形式化說(shuō)明，符合加權(quán)錦標(biāo)賽的定義，故算法2正確。

算法3計(jì)算出加權(quán)錦標(biāo)賽Tw=（Cw，Pw）的一個(gè)slater獲勝者的方法是正確的，分析如下：Tw上的嚴(yán)格線性序列wl的slater分?jǐn)?shù)為∑（Sm，Sj）∈wlΔPw|Sm|×|Sj|，其中wlΔPw=（wl∪Pw）-（wl∩Pw），wl={（Sm，Sj）|1≤mlt;j≤k，k=|Cw|}，wlΔPw表示wl和Pw中存在差異的邊的集合。其中，若（Sm，Sj）∈wlΔPw，則（Sj，Sm）∈wlΔPw。算法3的描述和形式化說(shuō)明可知∑1≤ilt;j≤k，silt;sj（Ssj，Ssi）∈Pw|Si|×|Sj|和∑（Sm，Sj）∈wlΔPw|Sm|×|Sj|是等價(jià)的。所以算法3中的minimize約束求出加權(quán)錦標(biāo)賽上加權(quán)slater分?jǐn)?shù)最小的嚴(yán)格線性序列，并返回其首項(xiàng)。符合加權(quán)錦標(biāo)賽的slater獲勝者的定義。故算法3正確。

算法4中步驟d）遞歸求解子錦標(biāo)賽Tsub=（Sw，P|Sw）的slater獲勝者是正確的。分析如下：

給定錦標(biāo)賽T=（C，P），構(gòu)造出加權(quán)錦標(biāo)賽Tw=（Cw，Pw），在找出T中所有的極大相似項(xiàng)集之后，當(dāng)需要計(jì)算出一個(gè)T的slater序列時(shí)，根據(jù)定理1，可以將每一個(gè)相似項(xiàng)集Si（1≤i≤k，k=|Cw|）看做一個(gè)超級(jí)候選項(xiàng)，而且其權(quán)重為|Si|。先計(jì)算出由超級(jí)候選項(xiàng)構(gòu)成的slater序列，而因?yàn)橐粋€(gè)Si內(nèi)部的slater序列和超級(jí)候選項(xiàng)構(gòu)成的slater序列以及其他極大相似項(xiàng)集內(nèi)部的slater序列無(wú)關(guān)，所以再遞歸求出每個(gè)Si內(nèi)部的候選項(xiàng)構(gòu)成的slater序列。這樣就可以計(jì)算出錦標(biāo)賽T的一個(gè)slater序列。

綜合上述，算法4計(jì)算slater獲勝者是符合文獻(xiàn)[11]提出的求解slater問題的定義。故算法4是正確的。

4實(shí)驗(yàn)與分析

4.1舉例說(shuō)明

給定錦標(biāo)賽T=（C，P） 如圖1所示。根據(jù)算法2計(jì)算出T中的所有的極大相似項(xiàng)集：S1={a，b，d}、S2={c}和S3={e，f}，因此Cw={S1，S2，S3}，因?yàn)閍∈S1，c∈S2，e∈S3，又因?yàn)椋╟，a），（c，e），（a，e）∈P，所以，Pw={（S2，S1），（S2，S3），（S1，S3）}。由此，構(gòu)造出加權(quán)錦標(biāo)賽Tw=（Cw，Pw），如圖2所示。

根據(jù)算法3計(jì)算出Cw上加權(quán)slater分?jǐn)?shù)最小的嚴(yán)格線性系列，顯然，S3gt;S1gt;S2的加權(quán)slater分?jǐn)?shù)為2，最小，故S3即加權(quán)錦標(biāo)賽Tw的一個(gè)slater獲勝者。

根據(jù)算法4的步驟d）遞歸求解子錦標(biāo)賽Tsub=（S3，P|S3），其中S3={e，f}，P|S3={（e，f）}，則子錦標(biāo)賽Tsub的slater獲勝者為e，因此，錦標(biāo)賽T的一個(gè)slater勝者為e。

4.2實(shí)驗(yàn)與結(jié)果分析

本文實(shí)驗(yàn)是在Debian 9.2、內(nèi)存257.288 GB、Intel Xeon Gold 6132 CPU @ 2.60 GHz 環(huán)境下進(jìn)行，分別在不同候選項(xiàng)人數(shù)的情況下隨機(jī)生成100組測(cè)試用例。每組測(cè)試用例其實(shí)是一些基礎(chǔ)謂詞，其中包括votes（M，X，O，N），表示在第N種投票描述中，有M個(gè)選民支持X排在第O位；candidate（1，…，L），表示總共有L名候選項(xiàng)；voters（X）表示一共有X位選民參與投票。與文獻(xiàn)[8]中的回答集程序進(jìn)行對(duì)比實(shí)驗(yàn)，比較Picat程序和ASP程序的平均計(jì)算時(shí)間，時(shí)間單位為秒（s）。所有實(shí)驗(yàn)代碼及實(shí)驗(yàn)數(shù)據(jù)已上傳至GitHub（https：//github.com/Barnette-ao/picat）。

在第一組實(shí)驗(yàn)中，候選項(xiàng)數(shù)量分別為 5、10、15、20，單個(gè)測(cè)試用例的計(jì)算時(shí)間限制為60 s。因?yàn)镻icat內(nèi)置了多種求解器：混合整數(shù)規(guī)劃（MIP）、命題可滿足性（SAT）和約束可滿足性（CP），本文分別用ASP方法、Picat三種求解器的優(yōu)化和非優(yōu)化方法來(lái)計(jì)算slater獲勝者。優(yōu)化方法即本文介紹的方法，給定錦標(biāo)賽T=（C，P），構(gòu)造加權(quán)錦標(biāo)賽Tw=（Cw，Pw），先求解加權(quán)錦標(biāo)賽的slater獲勝者，然后再遞歸求解由加權(quán)錦標(biāo)賽的slater獲勝者構(gòu)成的子錦標(biāo)賽的slater獲勝者，該slater獲勝者即錦標(biāo)賽的slater獲勝者；非優(yōu)化方法則是，給定錦標(biāo)賽T=（C，P），求出與錦標(biāo)賽差異最小的一個(gè)C上的嚴(yán)格線性序列，其首項(xiàng)即為錦標(biāo)賽T的slater獲勝者。

實(shí)驗(yàn)結(jié)果如表1、2所示，求解方法名的后綴為0表示優(yōu)化方法slater_winner（算法4），后綴為1表示非優(yōu)化方法slater_winner_w（算法3）。表中“-”表示計(jì)算時(shí)間超出時(shí)間限制。結(jié)果表明：使用Picat計(jì)算slater獲勝者的優(yōu)化方法比非優(yōu)化的方法更有效（更少的平均時(shí)間和更少的超時(shí)實(shí)例數(shù)）；Picat的三種方法中，SAT方法優(yōu)于CP方法，CP方法優(yōu)于MIP；另外，ASP（clingo 5.2.2，https：// github.com/ potassco /clingo/releases）方法仍然是這些方法中最有效的。

第二組實(shí)驗(yàn)，進(jìn)一步探索比較ASP（clingo）和Picat的SAT 優(yōu)化方法以求解更多的候選項(xiàng)25、30、35、40、45和50，每個(gè)實(shí)例的求解時(shí)間限制為600 s，這兩種方法的平均計(jì)算時(shí)間如圖3所示，超出時(shí)間限制的實(shí)例的數(shù)量如圖4所示。

由圖3可知，當(dāng)候選項(xiàng)個(gè)數(shù)等于或者大于25時(shí)，ASP方法的平均計(jì)算時(shí)間多于Picat方法的平均計(jì)算時(shí)間。隨著候選項(xiàng)個(gè)數(shù)的增多，ASP方法的平均計(jì)算時(shí)間也越來(lái)越長(zhǎng)。而隨著候選項(xiàng)個(gè)數(shù)的增加，Picat方法的平均計(jì)算時(shí)間始終在50 s以下。由圖4可知，當(dāng)候選項(xiàng)的個(gè)數(shù)少于20時(shí)，ASP能夠計(jì)算出更多的實(shí)例，當(dāng)候選項(xiàng)的個(gè)數(shù)多于30時(shí)，Picat能計(jì)算出更多實(shí)例。

5結(jié)束語(yǔ)

本文對(duì)slater投票問題進(jìn)行了分析，以Picat方法實(shí)現(xiàn)文獻(xiàn)[14]提出的優(yōu)化求解slater問題的算法，并證明了Picat方法的正確性。實(shí)驗(yàn)結(jié)果表明，當(dāng)候選項(xiàng)少于20時(shí)，ASP方法的計(jì)算效率和計(jì)算能力優(yōu)于Picat方法，當(dāng)候選項(xiàng)多于30時(shí)，Picat的SAT方法計(jì)算效率和計(jì)算能力優(yōu)于ASP方法。但本文方法的時(shí)間復(fù)雜度仍然較大，下一步將對(duì)其優(yōu)化并計(jì)算其他投票策略的獲勝者。

參考文獻(xiàn)：

［1］Mattei N.Closing the loop：bringing humans into empirical computational social choice and preference reasoning[C]//Proc of the 29th International Conference on International Joint Conferences on Artificial Intelligence.San Francisco：Morgan Kaufmann Publishers，2021：5169-5173.

[2]Brandt F，Conitzer V，Endriss U，et al.Handbook of computational social choice[M].Cambridge：Cambridge University Press，2016：1-20.

[3]Nardi O，Boixel A，Endriss U.A graph-based algorithm for the automated justification of collective decisions[D].Amsterdam：University of Amsterdam，Institute for Logic，Language and Computation，2021.

[4]Hamm T，Lackner M，Rapberger A.Computing kemeny rankings from d-Euclidean preferences[C]//Proc of the 7th International Conference on Algorithmic Decision Theory.Berlin：Springer，2021：147-161.

[5]Boussari A，Chachaa A，Chergui B，et al.Spectral slater index of tournaments[J].The Electronic Journal of Linear Algebra，2022，38：170-178.

[6]Brill M，Schmidt-Kraepelin U，Suksompong W.Margin of victory for tournament solutions[J].Artificial Intelligence，2022，302：103600.

[7]Lampis M.Determining a slater winner is complete for parallel access to NP[EB/OL].（2021-04-07）[2022-02-27].https：//arxiv.org/pdf/2103.16416.pdf.

[8]Zhou Nengfa，Hkan K，Jonathan F.Constraint solving and planning with Picat[M].Berlin：Springer，2015：1-33.

[9]Zhou Nengfa.Modeling and solving graph synthesis problems using SAT-encoded reachability constraints in Picat[C]//Proc of the 37th International Conference on Logic Programming.2021：165-178.

[10]De Haan R，Slavkovik M.Answer set programming for judgment aggregation[C]//Proc of the 28th International Joint Conference on Artificial Intelligence.Palo Alto，CA：AAAI Press，2019：1668-1674.

[11]徐珩僭，王以松，馮仁艷.一種用于slater與Kemeny投票求解的ASP方法[J].計(jì)算機(jī)工程，2019，45（9）：198-203.（Xu Hengjian，Wang Yisong，F(xiàn)eng Renyan.An A-SP method for calculating slater and Kemeny voting[J].Computer Engineering，2019，45（9）：198-203.）

[12]徐珩僭.計(jì)算社會(huì)選擇選舉問題及其變形的描述性求解[D].貴州：貴州大學(xué)，2019.（Xu Hengjian.An descriptive solution of computational social choice election problem and its variants[D].Guizhou：Guizhou University，2019.）

[13]Barták R，Zhou Nengfa，Stern R，et al.Modeling and solving the multi-agent pathfinding problem in Picat[C]//Proc of the 29th Internatio-nal Conference on Tools with Artificial Intelligence.Piscataway，NJ：IEEE Press，2017：959-966.

[14]Conitzer V.Computing slater rankings using similarities among candidates[C]//Proc of the 21st International Conference on Artificial Intelligence and Soft Computing.Palo Alto，CA：AAAI Press，2006：613-619.

[15]Nurmi H，Kacprzyk J，Zadrony S.Collective decisions：theory，algorithms and decision support systems[M].Berlin：Springer，2022：3-16.

[16]Govc D，Levi R，Smith J P.Complexes of tournaments，directionality filtrations and persistent homology[J].Journal of Applied and Computational Topology，2021，5（2）：313-337.

[17]Lemus J，Marshall G.Dynamic tournament design：evidence from prediction contests[J].Journal of Political Economy，2021，129（2）：383-420.

[18]Beretta L，Nardini F M，Trani R，et al.An optimal algorithm to find champions of tournament graphs[C]//Proc of the 26th International Symposium on String Processing and Information Retrieval.Berlin：Springer，2019：267-273.

[19]Baharev A，Schichl H，Neumaier A，et al.An exact method for the minimum feedback arc set problem[J].ACM Journal of Experimental Algorithmics，2021，26：article No.1.4.

[20]Bachmeier G，Brandt F，Geist C，et al.k-majority digraphs and the hardness of voting with a constant number of voters[J].Journal of Computer and System Sciences，2019，105：130-157.

收稿日期：2022-01-13；修回日期：2022-03-01基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目（61976065，U1836205）

作者簡(jiǎn)介：敖歡（1997-），男，湖南衡陽(yáng)人，碩士，主要研究方向?yàn)镻icat程序設(shè)計(jì)；王以松（1975-），男（通信作者），教授，博士，主要研究方向?yàn)橹R(shí)表示與推理、機(jī)器學(xué)習(xí)（yswang@gzu.edu.cn）；馮仁艷（1990-），貴州黔西人，博士，主要研究方向?yàn)橹R(shí)表示與推理；鄧周灰（1978-），男，貴州貴陽(yáng)人，碩士，主要研究方向?yàn)闄C(jī)器學(xué)習(xí)、統(tǒng)計(jì)分析、算法分析與優(yōu)化；仝天樂（1990-），男，貴州貴陽(yáng)人，碩士，主要研究方向?yàn)樵朴?jì)算、移動(dòng)互聯(lián)網(wǎng)、虛擬現(xiàn)實(shí)．