Kemeny社會選擇函數(shù)的0-1規(guī)劃算法

吳祥標(biāo)

(遵義師范學(xué)院數(shù)學(xué)與計(jì)算科學(xué)學(xué)院，貴州遵義563002)

Kemeny社會選擇函數(shù)的0-1規(guī)劃算法

吳祥標(biāo)

(遵義師范學(xué)院數(shù)學(xué)與計(jì)算科學(xué)學(xué)院，貴州遵義563002)

Kemeny函數(shù)是群決策中的一種社會選擇函數(shù)，作者將Kemeny函數(shù)的計(jì)算過程轉(zhuǎn)化成整數(shù)規(guī)劃模型的求解，并提出了一種有效的算法。

Kemeny函數(shù)；社會選擇函數(shù)；群決策；整數(shù)規(guī)劃

群決策中的Kemeny函數(shù)是J GKemeny（1972）提出的一種社會選擇函數(shù)，這種社會選擇函數(shù)要使社會的排序與投票人對各方案的偏好序有最大的一致性。Kemeny函數(shù)為所有方案的每一個(gè)可能的排序賦予一個(gè)函數(shù)值來表示該排序與投票人的個(gè)體排序之間的一致性，并將最大的函數(shù)值所對應(yīng)的排序作為群的排序。

當(dāng)方案的比較多時(shí)，用窮舉法計(jì)算量太大。窮舉法不是一種有效的算法，因此提出了計(jì)算Kemeny函數(shù)的0-1規(guī)劃算法。

1 Kemeny函數(shù)

為了方便表述，先引入如下符號：

N＝｛1,2,…,n｝表示群，即投票人的集合；

A＝｛a1,a2,…,am｝表示備選方案（候選人）集合；

njk或表示群中認(rèn)為aj優(yōu)于ak的成員數(shù)。

采用上述標(biāo)記，過半數(shù)規(guī)則可以表示為：對aj,ak∈A，若njk＞nkj，則；若njk＝nkj，則ajGak。

Kemeny函數(shù)的計(jì)算過程分為以下幾個(gè)步驟：

社會選擇的排序矩陣L＝｛ljk｝,j,k=1,2…m,其中上的線性序都有相應(yīng)的矩陣。

（3）計(jì)算Kemeny函數(shù)

2 Kemeny函數(shù)算法的分析

表1 m=3～7時(shí)L的數(shù)目

從上表可以看出，利用Kemeny函數(shù)進(jìn)行群決策最大的困難是計(jì)算量較大。因此，有必要對Kemeny函數(shù)的算法進(jìn)行一些改進(jìn)。

定理1一定存在一個(gè)傳遞的強(qiáng)序，使得Kemeny函數(shù)取得極大值。

按照步驟一，得到新的排序的Kemeny函數(shù)值fk=〈E·L〉+ejk，因而有〈E·L〉≤〈E·L0〉。

所有傳遞的強(qiáng)序矩陣中的Kemeny函數(shù)的值最大的排序矩陣，則這個(gè)排序可以使得Kemeny函數(shù)取得最大值。證畢。

由定理1可以知道，我們只需要對傳遞的強(qiáng)排序進(jìn)行比較，就能找出最優(yōu)的排序。對于存在無差異關(guān)系的情況，會在本文的后面進(jìn)行討論。

3 整數(shù)規(guī)劃算法

(1)ljk∈{-1,1}, j≠k

(2)ljk=-lkj,j,k

(3)-1≤lhj+ljk+lkh≤1,h≠j≠k

條件(1)和(2)很清楚，條件(3)可以保證傳遞性的需要。若ah,aj,ak非傳遞，必有l(wèi)hj,ljk,lkh同號，則lhj+ ljk+lkh=-3或lhj+ljk+lkh=3。ah,aj,ak滿足傳遞性，則lhj+ljk+lkh=-1或lhj+ljk+lkh=1，由于lhj,ljk,lkh都為奇數(shù)，所以約束條件(3)能保證滿足傳遞性。

(1)ljk∈{-1,1}, j≠k

(2)-1≤lhj+ljk－lhk≤1h＜j＜k

Kemeny函數(shù)可用如下整數(shù)模型求解：

令L=ljk,其中

(1)ljk∈{0,1},≠

(2)ljk+lkj=1,j,k

(3)lhj+ljk+lkh≤2,h,j,k

4 關(guān)于無差異的分析

在群決策中，如果只存在兩個(gè)方案，而支持這兩個(gè)的相同，我們認(rèn)為這兩個(gè)方案是無差異的。那么，在存在多個(gè)方案時(shí)，會不會存在這種無差異的情況呢？

比如某個(gè)群對三個(gè)備選方案a，b，c進(jìn)行排序，群中成員可能會有如下6種觀點(diǎn)：

假設(shè)群中有六個(gè)成員，分別支持以上6種觀點(diǎn)，或者2個(gè)支持觀點(diǎn)（1）、2個(gè)支持觀點(diǎn)（2）、2個(gè)支持觀點(diǎn)（3）。群中各成員的權(quán)力相同，因此很難確定方案a，b，c的優(yōu)劣次序，在這兩種情形下，我們有理由認(rèn)為方案a，b，c是無差異的。

同樣，用Kemeny社會選擇函數(shù)得出的社會總體排序也會出現(xiàn)這樣的無差異關(guān)系。在前文中，為了減少計(jì)算量，我們忽略了含有無差異關(guān)系的社會排序，但是無差異關(guān)系是存在的。例如，在某個(gè)群決策中，排序矩陣使得Kemeny函數(shù)取得極大值。假設(shè)在這個(gè)排序中，排在第 位和第 +1位的方案分別為ai和ai+1，且兩兩比較的結(jié)果是ai≈Gai+1。則將排序矩陣L中aiGai+1變成ai≈Gai+1其它排序保持不變的得到的新的排序矩陣L0。排序矩陣0也使得Kemeny函數(shù)取得極大值，因此我們認(rèn)為方案 和 是無差異的。

用整數(shù)規(guī)劃算法求解時(shí)，如果最優(yōu)解不唯一，說明社會排序存在無差異關(guān)系。若排序和排序…(i＜j)都能使得Kemeny函數(shù)取得極大值，則可以認(rèn)為方案ai,ai+1,…, aj-1,aj是無差異的，因?yàn)榕判蛞材苁沟肒emeny函數(shù)取得極大值。

5 示例

示例1參考文獻(xiàn)[1]中的例11.6

投票矩陣為：

受約束于：

用整數(shù)規(guī)劃法求得最優(yōu)解為： l12=l13=0,l23=1，社會選擇的排序是

實(shí)例2參考文獻(xiàn)[1]中的例11.7

投票矩陣為：

受約束于：

最優(yōu)解為：l12=l14=l15=l25=l34=l35=l45=1,l13= l23=l24=0，max〈E·L〉社會選擇的排序是

[1]岳超源.決策理論與方法[M].北京：科學(xué)出版社,2004.

[2]胡運(yùn)權(quán).運(yùn)籌學(xué)教程[M].北京：清華大學(xué)出版社,1998.

[3]徐小湛.Kemeny社會選擇函數(shù)的一種改進(jìn)算法[J].西南民族大學(xué)學(xué)報(bào)（自然科學(xué)版），2003，29（6）：655-659.

0-1 programming algorithm of Kemeny social choice function

WU Xiang-biao

(School of Mathematics and Computation Science,Zunyi Nomal College,Zunyi 563002，China)

Kemeny is a function of a social choice function in group decision making,and this paper will calculate the Kemeny function into solving integer programming model,and proposes an effective algorithm.

Kemeny function;social choice function;group decision making;integer programming

C934

A

1009-3583（2014）01-0081-03

2013-11-05

吳祥標(biāo)，男，湖北仙桃人，遵義師范學(xué)院數(shù)學(xué)與計(jì)算科學(xué)學(xué)院講師，碩士。

朱 彬）