加权选举系统

离散数学结构加权选举系统实验一第1页加权选举系统——快速算出每个人的权力一、加权选举系统如果一个企业有2个人合资，一个人股份为70%，一个人的股份为30%,若记分配方式为[55：70,30]，其中55称为定额，或者说表决权，那么显然，第一个人拥有70%，远超55%，那么他有决定权，称为独裁者。但是，如果有3个人，他们的分配方式[55:30,34,36]，没有了独裁者，是否说这3个人就没有权力呢。从另一方面看，其中任意2个以上的组合，就会超过55，那么我们称这样的方法是联盟，而若超过定额数的联盟则称为优胜联盟。而没有超过定额的联盟叫做劣势联盟。若果遇到这种分配方式[55:30,30,30,10]，对于最后一个人，和前面3个人所组成的联盟均为劣势联盟，那么最后一个人还会有权力吗？因此我们就要讨论一下，加权选举系统在各种情况下每个人的权力。像以上的例子，都是一个加权系统，从这些例子可以看出，个人的影响未必只由他所拥有的票数决定，有时候还会与定额，全体票数，每个人的分配所决定。定义：有n个选举者的加权选举系统可以表示为:[12:,,,nq]，其中q是定额，12,,,n是选举人的权力。每个选举系统中，最多只能有一名独裁者，而不能有两位，因为独裁者是一个集权者，不能允许有人影响他的决定。那么要保证独裁者只能有1位，定额就必须有限制：12...2n关于联盟：以S为全体选民所构成的集合，赢家联盟就是S的一个子集W，满足：ii而劣势联盟就是S的一个子集Q，满足：iiQQQq。离散数学结构加权选举系统实验一第2页二、Banzhaf当一个加权选举系统中没有独裁者，我们是不能就断定那么候选人有没有权力，所以我们Banzhaf提出的联盟的方法。例如[8:5,3,2,1],可以找到优胜联盟{5,3}，{5,2,1}，{5,3,2,1}总共有6次机会使联盟变为劣势联盟，拥有权力5的选举人3次，分别拥有权力3，2,1的选人各1次。那么对于这4个人的Banzhaf权力指数分别为：3/6,1/6,1/6,1/6,而Banzhaf权力分布为：3/6,1/6,1/6,1/6。当权力指数大于等于0.5时，那么他就有否决权。如果Banzhaf权力分布为：2/6,2/6,1/6,1/6，那么就说明没有人有否决权？既然有优胜联盟，我们就会有否决联盟。当选举人的Banzhaf权力指数相加不小于0.5时，他们就是一个否决联盟。对于存在独裁者的一个加权选举系统[q:v1,v2,v3,v4],其中v1为独裁者，即1wq,那么权力指数分布为[1,0,0,0]，可见，独裁者只有一个，而其他候选人没有权力。对于[8:5,3,1]权力指数分布是2/3,1/3,0，也就是说最后一人没有权力。对于[7:3,4,5]权力指数分布是1/3,1/3,1/3,说明每个人的权力一样。那么可以总结出,当有1个选举人的权不小于定额时，便有一个独裁者，其他人都是无权力的。当没有独裁者的时候，任意2个候选人的权和不小于定额时，他们的权力是一样的。当一个候选人与任意的一个候选人的权和都不能达到定额的时候，那么他就是没有权力。如果针对4个或4个选举人以上的系统呢？现在引入一个说法：极小赢家联盟。即当一个联盟中任意一个候选人退出，那么这个联盟就会变为劣势联盟。我们可以将以上的结论推广到n人的加权选举系统：若1个候选人不能和其他候选人组成1个极小赢家联盟，那么他就是无权力的。说明一个事实：票数多的不一定权力多，有票数不一定有权力。下面来研究一下否决权。对于[8:5,3,1]权力指数分布是2/3,1/3,0.可以作出猜测：权大于定额如果1个候选人不在，那么其离散数学结构加权选举系统实验一第3页他候选人的权和都达不到定额，那么他们就没有否则权了。若候选人iv有否则权，则满足：1211......iinq（*）这样视乎有点不公平，我有权力，但却权力不足以达到否决权，如果我们把权力不够的一群人看成一个联盟，那么组合起或许就会拥有否则权力了，我们称为否决联盟。由（*）可知道，右边的权和均小于定额，那么他们是一个劣势联盟，如果把他们看成一个集合W，那么他们的补集w中的每个元素都是一个否决联盟。从以上总结的结果，我们很容易就可以应用于要求指定定额的加权选举系统。例如[q:6,3,1].若q=6，则，w1是独裁者。若q=7，则，w1，拥有否决权。若q=8，则，w1，w2拥有否决权。而w3没有权力。三、加权选举系统与matlab。有时候，当一个加权选举系统有大量的候选人的时候，计算他们的权力就会非常复杂。所以，我们把这个系统运用到matlab上。那么我们首先要用matlab帮助我们求出每个候选人的Banzhaf指数。步骤一：打开matlab步骤二：在M文件编辑器中输入：function[ANSWER]=dybzf(q,X)%q是定额。%X是候选人，多个候选人为[v1v2v3…]B=sort(X,'descend');%sort函数用于排序，descend表示降序long=length(B);XX=zeros(2^long,long);%XX矩阵用来初步存放数据yszs=0;%yszs表示优胜联盟的总数fora=1:longziji=nchoosek(B,a);%nchoosek(B,a)列出所有含a个元素的矩阵，元素来自B[m,n]=size(ziji);forb=1:mzijih=0;%表示每个组合的元素的和离散数学结构加权选举系统实验一第4页forc=1:nzijih=ziji(b,c)+zijih;endifzijihq|zijih==q%挑选出优胜联盟yszs=yszs+1;ford=1:length(ziji(b,:))fore=1:longifziji(b,d)==B(e)ifXX(yszs,e)==0XX(yszs,e)=B(e);break;endendendendendendendYY=zeros(yszs,long+1);fori=1:yszsforj=1:longYY(i,j)=XX(i,j);endendfori=1:yszsforj=1:longYY(i,long+1)=YY(i,j)+YY(i,long+1);endendZZ=zeros(3,long);fori=1:longZZ(1,i)=B(i);endfori=1:yszsforj=1:longifYY(i,long+1)-YY(i,j)qZZ(2,j)=ZZ(2,j)+1;endendendfenmu=0;fori=1:longfenmu=fenmu+ZZ(2,i);end离散数学结构加权选举系统实验一第5页fori=1:longforj=(i+1):longifZZ(1,i)==ZZ(1,j)ZZ(2,i)=ZZ(2,j)+ZZ(2,i);ZZ(2,j)=0;endendendVV=zeros(2,long);fori=1:longforj=(i+1):longifZZ(1,i)==ZZ(1,j)VV(1,i)=VV(1,i)+1;endendendfori=1:longifVV(1,i)~=0forj=1:VV(1,i)VV(1,i+j)=0;endendendfori=1:longVV(2,i)=ZZ(2,i)/(VV(1,i)+1);endfori=1:longifVV(1,i)0a=VV(2,i);forj=0:VV(1,i)ZZ(2,i+j)=a;endendendfori=1:longZZ(3,i)=ZZ(2,i)/fenmu;endANSWER=zeros(2,long);ANSWER([12],:)=ZZ([13],:);步骤三：测试与验证。在命令窗口输入dybzf(7,[5,4,3])得到结果:离散数学结构加权选举系统实验一第6页但是，实际上存在着买票的存在，那么应该怎么买才是最好呢？以下是matlab中的过程：步骤一：打开matlab步骤二：在M文件编辑窗口输入：functiony=yhbzf(q,num,buy,X)%q是定额。%num是第几个候选人有买票权力。%buy是可以买票的数量。%X是候选人。disp('初始banzhaf指数分布为');disp(dybzf(q,X));ZZ=dybzf(q,X);a=ZZ(2,num);num1=0;fori=1:length(X)UU=X;UU(i)=UU(i)-buy;UU(num)=UU(num)+buy;TT=dybzf(q,UU);fori=1:length(X)if(TT(1,i)==UU(num))&&(TT(2,i)a)a=TT(2,i);endendendb=zeros(1,length(X));c=1;fori=1:length(X)UU=X;UU(i)=UU(i)-buy;UU(num)=UU(num)+buy;TT=dybzf(q,UU);d=0;forj=1:length(X)if(TT(1,j)==UU(num))&(TT(2,j)==a)离散数学结构加权选举系统实验一第7页d=d+1;endendifd~=0b(c)=i;c=c+1;endenddisp('以下为最优选择方案：');disp('');fori=1:(c-1)UU=X;UU(b(i))=UU(b(i))-buy;UU(num)=UU(num)+buy;disp(['购买'num2str(b(i))'号选举人得选票，banzhaf指数分布将变为']);disp(dybzf(q,UU));end步骤三：测试与验证，在命令窗口输入：yhbzf(8,4,1,[5,3,2,1])得到结果：四、总结通过以上的结论，我们可以很快的算出一个加权选举系统的定额，banzhaf指数，是否拥有否则权，以及买票情况。如果把这些结论运用在实际的加权选举系统上，那么在大量候选人存在的情况下，我们依然能很快的算出想要的结果，这大大的节省时间，以及提高准确度。