第10讲-群体决策模型

第10讲群体决策模型

【本节简介】

机制设计(Mechanismdesign)、社会选择(Socialchoice)和博弈论(Gametheory)是现代社会科学家们研究“民主问题”的标准工具。

本节介绍社会选择理论中的选举问题数学模型——阿罗不可能定理，其中的公理化建模方法具有典型意义。

群体决策模型

群体决策：根据群体中每个成员的决策结果，综合得出群体的决策结果。两个关键因素：公平性标准、规则。

n个选民:I={1,2,…,n

}

m个候选人:A={ａ1

,ａ2,

…,ａｍ}

Ｐi:选民i对候选人的一个排序；

P

：根据排序分布{Ｐ1

,Ｐ2,

…,Ｐn}及选举规则确定的

对A中元素的群体排序结果。{Ｐ1,Ｐ2,

…,Ｐn}选举规则P

对A的任何一个排序应有如下性质：＊三岐性：对一切x,y∈A，必有下列关系之一成立：

x<yx=yx>y＊传递性：对于x,y,z∈A

，若x≥y,y≥z，则有

x≥z.约定：（x>y）i—在

P

i中

x>y

（x>y）—在

P

中

x>y

1.简单多数规则（x>y）

使（x>y）i成立的i的个数大于n/2.

例1按简单多数规则将得到（x>y）

（y>z）

（z>x）.

——"投票悖论"（paradoxofvoting）

p1p2p3xyzyzxzxy

2.Borda数规则

记Bi

(x)为

Ｐi中劣于

x的元素的数目，定义

称B(x)为

x的Borda数。

Borda数规则

（x>y）B(x)>B(y)

例2由于B(x)＝12<B(y)＝13，按Borda数规则应有（y

>x）?p1p2p3p4xxxyyyyzzzzuuuuvvvvx

例3

（策略选举与Borda数规则）

设有15个选民与3个候选人x、y、z，有意向表7人x>y>z；7人y>x>z；1人z>x>y

则B(x)=22，B(y)=21，B(z)=2，所以依据Borda数规则,最后投票结果为x>y>z.

以上称为真诚选举或非策略选举。如果支持y的7个选民采用策略选举，不按照他们的真实意向投票，而改为y>z>x.

则B(x)=15，B(y)=21，B(z)=9，于是结果为y>x>z.

例4某学科排名榜，共四项指标。甲校排名为：1，1，1，2；乙校排名为：2，2，3，1．综合排名如何呢？乙校第一，甲校第二！按总分排名！规则的合理与否，会因解读的角度不同而不同。

肯尼斯·阿罗（KennethJ.Arrow,1921-）●

美国著名数理经济学家。●

1951年出版著名著作《社会选择和个人价值》。●最著名的工作：“阿罗不可能定理”。●1972年荣获诺贝尔经济学奖。

Arrow公理

公理1

（选举的完全性）选民对候选人的任何一种排序都是允许的。

公理2（个体选择与群体选择的正相关性）如果对所有选民i，都有（x＞y）i

，那么，应当有（x＞y）。

此性质又称为Pareto效应。

公理3

（无关候选人的独立性，Independentofirreletivealternatives）设x，y是任意两个候选人，若在两次投票中，每个选民对x，y的相对排序都不变，那么在两次选举结果中，x，y的相对排序也应不变。

公理4

（非独裁性，

Non-dictatorial）

不存在这样的选民i，使得

Arrow定理对于至少有三名候选人和两名选民的投票，不存在满足Arrow公理的选举规则。

Arrow定理证明梗概。

引理1

若候选人y位于每一个Pi的首位或末位，则y

一定位于P的首位或末位。

引理2

对任一候选人y，存在关于y

的极端关键选民k，在改变Pk时，可以将y从排序的末位改变成首位。

引理3

设k是关于候选人y

的极端关键选民，则对于任一不含y

的候选人对子x、z，k是个独裁者，即

（x>z）k

（x>z）.

引理4

对任一候选人x（≠y），上述关于y的极端关键选民k也是关于x与y的独裁者。参见《选举几何学》，胡卫群、盛立人等著，2011，科学出版社

引理1

若候选人y位于每一个Pi的首位或末位，则y一定位于P的首位或末位。

证明：设在一次投票P中，y位于每一个Pi的首位或末位，但在P中，y不在首位与末位，则存在候选人x，z，使得（x>y>z）

考虑另一次投票P*，在P*中，对每一选民i有

（z>x)i*,而关于其他候选人的位置与P相同。依Pareto效应（公理2）有（z>x)*.

再比较P与P*，由于对于每一个选民i，y不是位于首位，就是位于末位，所以选民i关于x与y，以及z与y的相对顺序在两次投票中是相同的，故依据无关候选人的独立性（公理3）应有结论：

x与y，以及z与y在两次投票中的相对顺序是不变的。

而在P中有（x>y>z），所以，在P*中也应有（x>y>z）*，从而（x>z）*，此与（z>x)*矛盾。所以原假设不真，即y一定位于P的首位或末位。

证毕阿罗的结论是：根本不存在一种能保证效率、尊重个人意向、并且不依赖程序的多数规则的投票方案。或者说，不可能通过一定的程序准确地表达社会全体成员的个人意向来达到合意的公共决策。完美无缺的程序民主不存在！一个社会不可能有完全的每个个人的自由——否则将导致独裁；一个社会也不可能实现完全的自由经济——否则将导致垄断。人们对社会的认识由此达到一个新的高度!

对社会学他给出了一个普世价值，对经济学他给出了一个理想平衡态，在数学上他给出了一个精美的应用。

“人们一直以来都在谋求理想的民主制度，即完美的选举制度……但Arrow却证明要想寻找这样一个完美的理想选举方案是不可能的，历史上不知有多少伟大的人物都在寻找这种完美民主，并留下记录，但他们实际上都是在寻找一个逻辑上自相矛盾的怪物……。从Arrow以后关于民主的理论将完全改写。”

——美国经济学家萨缪尔森

阿马蒂亚·森（AmartyaSen）——印度裔英国经济学家，1998年诺贝尔经济学奖获得者，解决“投票悖论”。

如果选举满足以下条件之一：（1）所有人同意某一项不是最佳；（2）所有人同意某一项不是次佳；（3）所有人同意某一项不是最差。则简单多数规则就是“最公平”的选举规则。

萨利（Sarri）——芬兰裔美国数学家，选举几何学

齐齐尔尼斯基（Chichilnisky）——阿根廷裔美国数学家，选举拓扑理论关于排序，介绍一本2012年出版的著作：作者：AmyN.LangvilleandCarlD.Meyer《Who’s#1?——TheScienceofRatingandRanking》Arrow不可能定理Massey方法Colley方法Keener方法Elo方法Markov方法

……

如何排序，是科学，也是一种妥协。

本节小结：1.规则的合理性解读可以有不同角度。2.选举公平性的公理化描述。3.公理化建模方法的应用。4.阿罗不可能定理：“绝对公平的选举规则不存在”的社会学与经济学意义。

体育科学的研究中，也有大量的数学建模问题，例如：棒球的最佳击球点问题，滑板滑雪赛道的设计，划艇比赛中运动员的体力分配，NBA赛程的科学性评价，体操团体赛出场队员的最佳组合等等，本讲重点介绍一个案例：越野长跑团体赛的排名规则，通过对排名规则的公平性的不同度量，可以得到不同的结果。【本节简介】

越野长跑团体赛竞赛规则的公平性

越野长跑团体赛竞赛规则的公平性

越野长跑团体赛的竞赛规则如下：每个参赛团体由7名队员组成，取该团体跑在前面的5个队员在所有参赛选手中的排名顺序之和为该团体的得分，然后根据各参赛队得分（由小到大）的顺序决定比赛排名（简称5-2规则）。试讨论该竞赛规则的合理性并提出改进方案。

一、比赛公平性的几个判断准则

A与B两个队的相对顺序不应当依赖于任何其他队的表现。

一个队如果在与任一个队的两两对决中获胜，则这个队应当是整个比赛的优胜者。准则一：二元独立性（binaryindependence）准则二：孔多塞准则（CondorcetCriterion）

如果A队是一次竞赛的获胜者。假如在另一次竞赛中所有的参赛队与选手都不变，A队的一个选手a提高了名次，而除a之外的其他所有参赛选手之间的相对顺序都不变，则A队仍应是获胜者。如果A、B两队各有m个队员参赛，且有ai<bi（i=1,2，…m），则A队排名应优于B队。准则三：单调性（MonotonicityCriterion）准则四：帕累托条件（ParetoCondition）

孔多塞

（MarieJeanAntoineNicolasdeCaritat,marquisdeCondorcet，

1743年－1794年）●

数学家、哲学家。●1782年当选法兰西科学院院士。●在生命最后时刻，完成了自己的思想绝唱——《人类精神进步史表纲要》。

二、（5,2）规则的公平性判断

我们按照上述准则来判断（5，2）规则的公平性。

例1

设一次越野团体赛有33个队231名队员参加，其中3个队的队员成绩如下：

风队：1，2，3，8，27，36，45（41）

越野者队：4，12，15，24，35，49，55（90）

酷跑队：10，11，13，28，30，43，69（92）

不算风队1，8，11，20，30，43，48（70）6，7，9，23，25，37，62（70）

仅算两队1，4，6，7，10，12，13（28）2，3，5，8，9，11，14（27）

结论1（5,2）规则不满足二元独立性。

例2

设一次比赛有A、B、C、D4支队伍参加，成绩如下：A：12325262728（57）B：491114161820（54）C：571213192122（56）D：681015172324（56）

B队第一，A队垫底！

但在与A队两两对决中，A队前5名名次为：1231112，得分29，而其他队名次都是4~10，得分30,

A队胜！

结论2（5,2）规则不满足孔多塞准则。

结论3（5,2）规则满足单调性。

结论4（5,2）规则满足帕累托条件。

三、其他几种竞赛规则评价

考虑以下几种其他规则：

1、名次加权（m，l）规则；

名次差异非均匀化。2、迭代（m，0）规则；每次淘汰最后一名，然后重新计算名次。

3、顺序孔多赛规则；

按任意顺序，前两队对决，胜者与下一队对决，如此进行下去，最后留下的队就是获胜队。

4、非团体规则

存在i，使得A<Bai<bi

结论5名次加权（m，l）规则不满足二元独立性与孔多塞准则，但满足单调性与帕累托条件。

结论6

迭代（m，0）规则满足孔多塞准则与帕累托条件，但不满足单调性，也不满足二元独立性。

例3

考虑3个队参加的一次比赛，采用迭代（5,0）规则。比赛进行到一半时，成绩如下：三队目前得分为：38,40,42.淘汰Ｃ队后成绩如下：第二轮得分为：25,30，故最终Ａ队将夺冠。123456789101112131415C1C2A1A2A3B1B2B3B4B5A4C3C4C5A512345678910A1A2A3B1B2B3B4B5A4A5在A队教练的督促下，A4从第11名前进到了第6名。

此时得分为：33,45,42，Ｂ队被淘汰。

第二轮得分为：A:28,C:27。

A队被淘汰！Ｃ队夺冠！

故迭代（5,0）规则不满足单调性。123456789101112131415C1C2A1A2A3B1B2B3B4B5A4C3C4C5A5123456789101112131415C1C2A1A2A3A4B1B2B3B4B5C3C4C5A5123456７８９10C1C2A1A2A3A4C3C4C5A5

结论7

顺序孔多塞规则满足孔多塞准则和单调性，但不满足二元独立性与帕累托条件。

例4

考虑4个队参加的一次比赛，采用顺序孔多赛规则，两两对决时采用（3,0）规则。比赛结果为：设两两对决顺序为ABCD。首先A：B—11:10—B胜；

然后B：C—11:10—C胜；最后C：D—12:9—D胜！

但是有：ai<di，i=1~3，所以不满足帕累托条件。

更有甚者，a3<d1!C15

6D234A245B136B236C145123456789101112C1B1A1B2A2A3D1D2D3C2C3B3

例5

（非团体规则的例子）考虑2个队的比赛，每个队派两名队员，共有6种可能结果：1.A1A2B1B24.B1B2A1A2

2.A1B1A2B25.B1A1B2A2

3.A1B1B2A26.B1A1A2B2

假设帕累托条件满足，则A赢得1.2.，B赢得4.5.。

如果A赢得3.，则对称地，B赢得6.，这时的胜负实际上由各队的第一人决定，因此是非团体规则。

反过来，如果A赢得6.，则B赢得3.，这时的胜负由各队的第二人决定，仍是非团体规则。

越野团体赛计分规则的Arrow定理

以名次为排序依据，那么，在有至少三个队参加的越野团体赛中，如果一个规则同时满足二元独立性与帕累托条件，则