加权选举系统.docx

离散数学结构加权选举系统实验一加权选举系统快速算出每个人的权力一、加权选举系统如果一个企业有2个人合资，一个人股份为70%，一个人的股份为30%,若记分配方式为55：70,30，其中55称为定额，或者说表决权，那么显然，第一个人拥有70%，远超55%，那么他有决定权，称为独裁者。但是，如果有3个人，他们的分配方式55:30,34,36，没有了独裁者，是否说这3个人就没有权力呢。从另一方面看，其中任意2个以上的组合，就会超过55，那么我们称这样的方法是联盟，而若超过定额数的联盟则称为优胜联盟。而没有超过定额的联盟叫做劣势联盟。若果遇到这种分配方式55:30,30,30,10，对于最后一个人，和前面3个人所组成的联盟均为劣势联盟，那么最后一个人还会有权力吗？因此我们就要讨论一下，加权选举系统在各种情况下每个人的权力。像以上的例子，都是一个加权系统，从这些例子可以看出，个人的影响未必只由他所拥有的票数决定，有时候还会与定额，全体票数，每个人的分配所决定。定义：有n个选举者的加权选举系统可以表示为:，其中q是定额，是选举人的权力。每个选举系统中，最多只能有一名独裁者，而不能有两位，因为独裁者是一个集权者，不能允许有人影响他的决定。那么要保证独裁者只能有1位，定额就必须有限制：关于联盟：以S为全体选民所构成的集合，赢家联盟就是S的一个子集W，满足：而劣势联盟就是S的一个子集Q，满足：。二、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为独裁者，即,那么权力指数分布为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个候选人不在，那么其他候选人的权和都达不到定额，那么他们就没有否则权了。若候选人有否则权，则满足： （*）这样视乎有点不公平，我有权力，但却权力不足以达到否决权，如果我们把权力不够的一群人看成一个联盟，那么组合起或许就会拥有否则权力了，我们称为否决联盟。由（*）可知道，右边的权和均小于定额，那么他们是一个劣势联盟，如果把他们看成一个集合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是候选人，多个候选人为v1 v2 v3B=sort(X,descend); %sort函数用于排序，descend表示降序long=length(B);XX=zeros(2long,long); %XX矩阵用来初步存放数据yszs=0; %yszs表示优胜联盟的总数for a=1:long ziji=nchoosek(B,a); %nchoosek(B,a)列出所有含a个元素的矩阵，元素来自B m,n=size(ziji); for b=1:m zijih=0; %表示每个组合的元素的和 for c=1:n zijih=ziji(b,c)+zijih; end if zijihq|zijih=q %挑选出优胜联盟 yszs=yszs+1; for d=1:length(ziji(b,:) for e=1:long if ziji(b,d)=B(e) if XX(yszs,e)=0 XX(yszs,e)=B(e); break; end end end end end endendYY=zeros(yszs,long+1);for i=1:yszs for j=1:long YY(i,j)=XX(i,j); endendfor i=1:yszs for j=1:long YY(i,long+1)=YY(i,j)+YY(i,long+1); endendZZ=zeros(3,long);for i=1:long ZZ(1,i)=B(i);endfor i=1:yszs for j=1:long if YY(i,long+1)-YY(i,j)0 a=VV(2,i); for j=0:VV(1,i) ZZ(2,i+j)=a; end endendfor i=1:long ZZ(3,i)=ZZ(2,i)/fenmu;endANSWER=zeros(2,long);ANSWER(1 2,:)=ZZ(1 3,:);步骤三：测试与验证。在命令窗口输入dybzf(7,5,4,3)得到结果:但是，实际上存在着买票的存在，那么应该怎么买才是最好呢？以下是matlab中的过程：步骤一：打开matlab步骤二：在M文件编辑窗口输入：function y=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;for i=1:length(X) UU=X; UU(i)=UU(i)-buy; UU(num)=UU(num)+buy; TT=dybzf(q,UU); for i=1:length(X) if (TT(1,i)=UU(num)&(TT(2,i)a) a=TT(2,i); end endendb=zeros(1,length(X);c=1;for i=1:length(X) UU=X; UU(i)=UU(i)-buy; UU(num)=UU(num)+buy; TT=dybzf(q,UU); d=0; for j=1:length(X) if (TT(1,j)=UU(num)&(TT(2,j)=a) d=d+1; end end if d=0 b(c)=i; c=c+1; endenddisp(以下为最优选择方案：);disp( );for i=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,