宝宝的Arrow不可能定理_女孩萌一点的糖果小名

 

1.宝宝的第一个生日禁忌

有的宝宝喜欢吃胡萝卜,有的宝宝喜欢喝奶,那么这就是一种偏好;如果一个宝宝在选 xx 和 yy 的时候偏向于选择 xx ,那么我们就记为 x≻yx\succ y .设备选集合为 XX ,则我们往往要求宝宝们的偏好满足如下两个条件.

2.宝宝的奶粉

完备性: ∀x,y∈X\forall x,y\in X , x≻yx\succ y 和 y≻xy\succ x 必居其一.传递性:若已有 x≻yx\succ y 和 y≻zy\succ z ,则必有 x

3.宝宝的生长发育标准表

≻zx\succ z .设这里有 |I||I| 只宝宝,对于每个宝宝 ii ,对于 |X||X| 种选项给出自己满足如上条件的偏好 [≻i][\succ_i] ,经过某个映射(规则)F:([≻i])i∈

4.宝宝的英文

I↦[≻]\[F:([\succ_i])_{i\in I}\mapsto[\succ]\]合成出一种总偏好,这个偏好就叫社会偏好.而这样的 FF 就称为社会福利泛函数.宝宝们就想研究在不具体指定 FF 长什么样的时候,能得到

5.宝宝的拼音

FF 的多少信息.有一些自然的想法:FF 具有全域定义域,简单来说,就是所有满足完备性和传递性的偏好都在 FF 的定义域中.总是允许有些宝宝喜欢喝奶,也总是允许有些宝宝不喜欢吃葱花.FF 具有社会偏好理性,也就是最后从

6.宝宝的乳牙一共有几颗

FF 得到的社会偏好也具有传递性和完备性;这当然是相当自然的要求.接下来有一些不是很平凡,但是有必要说清楚的事情,也就是我们讨论的前提,两个比较具体的条件:Pareto效率是指x,y∈X,(∀i∈I,x

7.宝宝的囟门什么时候闭合

≻iy)⇒x≻y\[x,y\in X,(\forall i\in I, x\succ_i y)\Rightarrow x\succ y\]简单来说就是所有宝宝都觉得 xx 好于 yy ,最后结果应该也是

8.宝宝的体温多少度正常范围

xx 好于 yy ,这就是一致同意.配对独立性条件要求([≻i])i∈I,([≻i′])i∈I,x,y∈X,(∀i∈I,x≻iy⇔x≻i′y)⇒(x≻y⇔x≻′y)\[([\succ_i])_{i\in I},([\succ_i])_{i\in I},x,y\in X,(\forall i\in I,x\succ_i y\Leftrightarrow x\succ_i y)\Rightarrow (x\succ y\Leftrightarrow x\succ y)\]

9.宝宝的头型几个月定型

简单来说就是有两组偏好,每组偏好中都保持了 xx 和 yy 的偏好关系(注意所谓等价号其实就是两边同时成立或两边同时不成立),则最后结果应该也要保持.这也就是,其它参选者不应该影响结果.最后还要定义一个叫独裁的概念,即

10.宝宝的最萌小名

∃h∈I,∀x,y∈X,x≻hy⇔x≻y\[\exists h\in I,\forall x,y\in X,x\succ_h y\Leftrightarrow x\succ y\]就是存在一个人,使得其可以完全决定结果,宝宝们自然不希望这样的事情发生.比如,起码喜欢吃香菜的宝宝肯定不希望不吃香菜的宝宝完全左右社会偏好.

那么,所谓Arrow不可能定理指出了如下事实:|X|≥3|X|\geq3 ,那么所有具有全域的定义域,满足Pareto效率和配对独立性条件的社会福利泛函数都是独裁的.为了证明这个定理,需要补充一些定义,一旦补充完定义,聪明的宝宝已经自明其证明了.预设

S⊂IS\subset I .我们说 SS 决定了 xx 比 yy 好,若当 SS 中每个人都认可 x≻yx\succ y 但是 SS 外每个人都认可 y≻xy\succ x 时,社会偏好认可 x≻yx\succ y

.我们说 SS 是决定性的,当对于任何一对选项 (x,y)∈X2(x,y)\in X^2 ,都有 SS 决定了 xx 比 yy 好.我们说 SS 完全决定了 xx 比 yy 好,若当 SS 中每个人都认可

x≻yx\succ y 时即刻有社会偏好认可 x≻yx\succ y .稍加注意的是,虽然说 SS 决定了如何,但是不代表实际上就是如何,这应当理解为一种假定性,也就是当给定好一组偏好时,如果满足上述关于

SS 的条件,那么总是有陈述的结果.为了更清楚认清这种假定性的感觉,给出如下命题:命题1. ∀(x,y)∈X2,∀S⊂I\forall (x,y)\in X^2,\forall S\subset I ,那么要么

SS ,要么 I∖SI\backslash S ,决定了 xx 比 yy 好,或者 yy 比 xx 好.证明几乎是自明的,不妨假设 ∀i∈S,x≻iy\forall i\in S,x\succ_i y ,同时假设

∀i∈I−S,y≻ix\forall i\in I-S,y\succ_i x .此时社会偏好有两种可能, x≻yx\succ y 抑或是 y≻xy\succ x ;前者得到了 SS 决定了 xx 比 y

y 好,后者得到了 I∖SI\backslash S 决定了 yy 比 xx 好.互换 SS 和 I∖SI\backslash S 的情况在此不表了.这样我们可以把Pareto效率的要求换成了 II 是决定性的.

我们这么定义的目的自然是为了证明服务.我们首先给定了能够决定一对选项的集合,然后我们希望通过推理,使得这个集合能够决定更多的选项,从而最终决定全部选项,也就是决定性的;另一方面,我们还需要可以缩小这个集合,使得这个集合最后只剩一个人,这几乎构造出了独裁者.但是这还是不够的,最后还需要说明决定性的集合基本上是完全决定的,那么就彻底完成了整个定理的证明.为了开始这个证明,首先给出一个引理:

引理1.若 SS 决定了 xx 比 yy 好,那么对于任意一个 z≠xz\not=x , SS 决定了 xx 比 zz 好;类似的,对于任意一个 z≠yz\not=y , SS 决定了 zz 比 yy 好.

初见这个引理,感觉这个引理是十分夸张的,因为我们根本没有 zz 的信息,居然就能断言 zz 和 xx 的关系.为了证明,我们按照定义写出我们要证明的事情,即∀i∈S,x≻iz,∀i∈I∖S,z≻ix⇒x

≻z\[\forall i\in S,x\succ_i z,\forall i\in I\backslash S,z\succ_i x\Rightarrow x\succ z\]当然,我们要使用已经有的条件,也就是

SS 决定了 xx 比 yy 好,也就是为了使用这个条件,我们需要假设地把 yy 插入这个偏好列中.我们不妨假设∀i∈S,x≻iy≻iz;∀i∈I∖S,y≻iz≻ix\[\forall i\in S,x\succ_i y\succ_i z;\forall i\in I\backslash S,y\succ_i z\succ_i x\]

由于 FF 具有全域定义域,所以这么取总是还在定义域中的,于是由 SS 决定了 xx 比 yy 好的定义, x≻yx\succ y ,由Pareto效率, y≻zy\succ z ,由传递性 x≻zx\succ z

.在说辞上去掉 yy 的干扰是本证明的最后一步,因为另一半是同理的.这里就要使用配对独立性条件了, xx 和 zz 之间的比较不应该和 yy 有关,所以 yy 实际上怎么插入的结果都是一样的,而我们现在通过一种特定的插入法得到了这个结果,所以结果就是这样;检查定义,我们知道了

SS 决定了 xx 比 zz 好.值得注意的是,基本上配对独立性条件就是这么用的.我们立即得到如下推论推论1.若 SS 决定了 xx 比 yy 好, zz 是第三个选项,对于任何一个非 zz 的选项 w

w , SS 决定了 zz 比 ww 好和 ww 比 zz 好.由引理1,我们已经知道了 SS 决定了 xx 比 zz 好和 zz 比 yy 好,从而对 (x,z)(x,z) 和 ww 使用,就知道 S

S 决定了 ww 比 zz 好;对 (z,y)(z,y) 和 ww 使用,就知道 SS 决定了 zz 比 ww 好.可见我们基本上已经可以决定了任意两个选项互相的比较了,立刻得到如下推论推论2.若 SS

决定了 xx 比 yy 好,则 SS 是决定性的.这里唯一不平凡的一步是 zz 的存在性,由 |X|≥3|X|\geq3 保证了,所以就没有问题了.到此为止,一个集合若能决定一对,则我们知道直接具有绝对的决定性了.而这样集合的存在性其实已经由命题1保证了,所以这样的

SS 的存在性也不用慌.我们下一步的工作是想办法把 SS 变小,我们给出第二个引理引理2.若 SS 和 TT 是决定性的,则 S∩TS\cap T 是决定性的.只要取一对,证明可以决定之就行.看如下的构造

z≻iy≻ix,∀i∈S∖(S∩T)\[z\succ_i y\succ_i x,\forall i\in S\backslash(S\cap T)\]x≻iz≻iy,∀i∈S∩T\[x\succ_i z\succ_i y,\forall i\in S\cap T\]

y≻ix≻iz,∀i∈T∖(S∩T)\[y\succ_i x\succ_i z,\forall i\in T\backslash(S\cap T)\]y≻iz≻ix,∀i∈I∖(S∪T)\[y\succ_i z\succ_i x,\forall i\in I\backslash(S\cup T)\]

SS 是决定性的,所以 z≻yz\succ y ; TT 是决定性的,所以 x≻zx\succ z ;由于传递性 x≻yx\succ y ,于是 S∩TS\cap T 决定了 xx 比 yy 好,于是

S∩TS\cap T 是决定性的.有了交集,我们就可以造小集合了;一种具体的办法由如下两步推论给出,也就是先扩大一点,然后一交就变得很小.推论3. SS 是决定性的, S⊂TS\subset T ,则

TT 也是决定性的.首先由Pareto效率,空集必然不可能是决定性.(没有人觉得 x≻yx\succ y ,所有人都觉得 y≻xy\succ x ,那么最后结果怎么可能是 x≻yx\succ y 呢?)因此

I∖TI\backslash T 必然不可能是决定性的,否则 ∅=S∩(I∖T)\varnothing=S\cap(I\backslash T) 是决定性的,矛盾.则 TT 就是决定性的,由命题1.从而我们有办法进一步利用缩小性和自己与补必有一决定集的性质缩小决定集了.有如下推论

推论4.若 1">|S|>1|S|>1 是决定性的,则存在一个严格子集 S0S_0 ,使得 S0S_0 是决定性的.任取 h∈Sh\in S ,如果 S∖{h}S\backslash\{h\} 是决定性的则已经结束,否则

S∖{h}S\backslash\{h\} 不是决定性的,则 I∖(S∖{h})=(I∖S)∪{h}I\backslash(S\backslash\{h\})=(I\backslash S)\cup\{h\}

是决定性的,则 {h}=S∩((I∖S)∪{h})\{h\}=S\cap((I\backslash S)\cup\{h\}) 是决定性的,同样找到了严格变小的子集.我们再利用 |I|<+∞|I|<+\infty

和归纳法直接得到如下推论推论5.存在 h∈Ih\in I , {h}\{h\} 是决定性的.从 II 开始用归纳法和推论4往下走就行,走不动说明已经到了 |S|=1|S|=1 ,正是所求.这里的 hh

已经几乎是要找的独裁者了.这里需要最后一个引理,如下陈述引理3.如果 SS 是决定性的,那么对于任意一对 (x,y)(x,y) , SS 完全决定了 xx 比 yy 好.我们要证的是,对于任意一个 T

⊂I∖ST\subset I\backslash S , SS 和 TT 中都认为 x≻yx\succ y ,除此之外认为 y≻xy\succ x ,则最后结果要求 x≻yx\succ y .为此,我们引入第三个选项

zz 来处理,如下构造偏好:x≻iz≻iy,i∈S\[x\succ_i z\succ_i y,i\in S\]x≻iy≻iz,i∈T\[x\succ_i y\succ_i z,i\in T\]y≻iz≻

ix,i∈I∖(S∪T)\[y\succ_i z\succ_i x,i\in I\backslash(S\cup T)\]由推论3, S∪TS\cup T 是决定性的,所以 x≻zx\succ z ;由

SS 的决定性,所以有 z≻yz\succ y ;由传递性, x≻yx\succ y ,这就得证了.于是最终结论呼之欲出,我们作为推论写出推论6. {h}\{h\} 是决定性的,则 hh 是独裁者.因为由引理3,

{h}\{h\} 完全决定了任何 xx 比任何 yy 好,即对于任意一对选项 (x,y)(x,y) ,若有 x≻hyx\succ_h y 必有 x≻yx\succ y ,满足独裁者的定义.至此,Arrow不可能定理就被证明出来了.