社会选择函数集结中的对影判别和性质

高晓波，卢美华

(1.江西农业大学计算机与信息工程学院，江西 南昌 330045；2.江西科技学院理科部，江西 南昌 330022)

1 引言与研究背景

著名的Arrow不可能性定理冲击了整个社会科学的基础，从技术层面上，Arrow不可能性定理指向了偏好集结、加总等问题，是典型的群决策问题。虽然自上世纪50年代以来，Arrow不可能性定理及其指向的社会选择函数存在性问题的研究历史已有70余年，权威文献提供了数十个具体证明，近期提供了形式更为规范研究的证明[1-10]，不过各种证明都具有瑕疵[11]。撇开诸多修订证明的文献，如文献[2-10]等等，在管理理论和决策理论中，社会选择函数研究还具有广泛的空间。罗云峰的文献[1]对社会选择函数及其存在性的研究和概括较为全面；特别是罗云峰文献[1]第13章全面概括选择函数的路径无关性；可以说，一方面选择函数的路径无关扩展了无关备择物的独立性公理(IIA公理)，另一方面选择函数的路径无关也是直接考察偏好集结方式和路径。另外一些重要文献给出了社会选择函数的框架性扩展或者方法的拓展。胡毓达的文献[12]利用可排方法简化并严格化了Arrow不可能性定理的证明，同时提出了一些新的解释。郭春香文献[13]、Cato文献[14]拓展了社会选择函数的框架，在格序、不完全序上构造了新的序决策结构，吴志彬文献[15]提出了共识概念和非公理化集结的方法。例如，具有完全的共识的群体，表现为偏好序完全是一致的，那社会偏好序也就自然确定了。不过这时社会选择函数也是一种冗余的概念。本质上，社会选择函数就是集结冲突的投票者的偏好。从而，直接考察集结更能在操作层面上形成对社会选择函数的判断。为此，本文集中考察社会选择函数集结中的对影判别和性质。

2 基本概念和符号说明

社会科学研究中有诸多运用标准数学工具研究现实背景中问题，但这些问题未必得到了严格和标准的刻画，从而产生理论文献中一些符号及其意义上的不一致。为此，这里给出基本概念和常用符号如下：

(1)集合、关系以及定向。对于一个集合X，称‖X‖为其范数，当X为有限集时为其元素个数。关系R是X×X上的一个子集，R⊂X×X。为方便，当x、y∈X具有关系R，即(x,y)∈R,也表示xRy，这里R是一般性泛指关系。如果是特定的关系R，还常直接用特定符号表示，例如某特定xRy表示为xy，这里xy是定向的，例如考虑定向关系，关系xy={x,{x,y}}。

(2)关系的属性。对于装载了关系R的集合X，简记为(X，R)。∀x、y∈X，称R是自反的，若总有xRx；称R是非自反的，若总有xRx；(2)称R是传递，若另∀z∈X，总能由xRy、yRz⟹xRz；称R是对称的，对于x≠y若xRy⟹yRx；称R是非对称的x≠y，若xRy⟹yRx；称是完全的，若x≠y，若xRy、yRx必有两者之一，或者说若xRy⟹yRx。

(3)偏序、全序和强序、弱序。称R为偏序，若X上的R是传递的；称R为全序，若X上的R是传递的和完全的；称R为强序，若S上的R是非对称、传递和完全的；称R为弱序，若S上的R是对称、传递和完全的；称R是等价关系，若X上的R是自反、传递和对称的。同时引入“～”表示等价关系；引入“≼”和“”表示弱序，“”和“≻”表示强序；另外，还引入其他一些记号，≼=，R=P∪I，=≻∪～。本文涉及的主要概念都将基于普适性符号。若xRy即为“xy”，也称R排x、y为xy，或R排为xy，或R：xy。这些符号在权威文献中广泛采用，并且本文中这些符号的具体含义依据上下文是自明的。

3 主要结论

SCF在现实意义上需要遵循约束公理，Arrow、Sen、May都提出了不同的约束公理。除出律例规范外，也确实考虑合理非公理配置以保障和SCF集结加总的存在，本文不直接研究合理公理配置，所以以AS代表一般的约束公理系统。在考虑直接的集结过程中，孔多塞循环受到多方面的研究，本质是孔多塞循环是排序轮换，其全轮换恰好构成一个完整的循环群。

定义1备择物集为A={α1,α2,…,αi}，称∇:A→A为轮换函数，若满足∇(α1)=α2,∇(α2)=α3…,∇(αk)=αk+1…∇(αi-1)=αi,∇(α)i=α1。

说明，这里A={α1,α2,…,αi}的标定是无序的；也就是说，本质上A={αk|k∈I}，并且其中的I为无向指标集。另外，考察各阶轮换幂n(α)=∇(…∇(∇(α))…)，1≤n≤i-1，从而在备择物集A={α1,α2,…,αi}定义了轮换或孔多塞循环后，也就构成轮换次序。本质上A={α1,∇(α1),2(α1)…,i-1(α1)}，就按照轮换幂级就构成了序向。

另外，为给出定义2，设R为备择物集A上的偏好序(弱序)，并记R=P∪I，其中的严格偏好P和偏好等价分别用“”和“～”刻画。

显然有如下定理：

定理1A={α1,α2,…,αi}，Δ:A→{1,2,…i}为标号映射，且Δ(αk)=k。∇:A→A为轮换映射，则∀αk∈A，Δ(∇αk)-Δ(αk)=1或者1-i。Δ(nαk)-Δ(αk)=n或者n-i,其中n

定义2对于备择物集A上的偏好序R(为弱序)，称序对为R在<α1、α2>两点上的有序分影，并记为φα1α2R=，若满足：

(1)当α1Rα2为α1～α2时，α1R+α2为α1α2，而α1R-α2为α1≻α2；并对其他全部的α～α1～α2，满足αR+α1为α～α1(α2)，规定αR-α1为α～α1(≻α2)。

(2)当α1Rα2为α1α2时，α1R+α2为α1α2且α1R-α2为α1α2；

为方便，简记R+=R+φα1α2，R-=R-φα1α2。考虑到定义2中有φα2α1R=，下文简记φα1α2R=(R+，R-)为R在(α1、α2)上的分影。另外考虑分影合成，若R中有α～β～γ，先φαβR，R+φαβ和R-φαβ都包含α～γ，再做φαγ(R+φαβ)=以及φαγ(R-φαβ)=，取称为α、β、γ的分影，记为φαβγR，也即φαβγR=。显然，对于偏好序R进行分影运算，总是把某两个等价备择物偏好严格化，通过分影合成最终能把R的所有等价备择物都对称的严格化，并记为φA/～R，也即如下定理成立。

定理2若R为备择物集A={α1,α2,…,αi}上的偏好序，则存在φA/～R=(R+，R-)为R的等价性分影，其中的R+、R-都是强序，是严格偏好。

证明若偏好序R本身为强序，按强序定义，∀α、β∈A,则αβ或者βα。那么按照分影定义，只需φαβR=中R+=R-=R。从而，遍历任何两个元素，也必有φA/～R=(R+，R-)中R+=R-=R；从而，存在φA/～R=(R+，R-)为R等价性分影，其中的R+、R-都是强序，是严格偏好。

若偏好序R本身不为强序，则R=P∪I包含无差异的备择物，为等价关系。为此可作A/～={Λ1、Λ2、…、Λk}，满足A=Λ1∪Λ2∪…∪Λk、Λs∩Λt=φ(s≠t)以及∀Λs、∀α、α′∈Λs⟹α～α′(αIα′)等条件；也即A/～形成A等价类划分。

对其中任何单点集Λk={α}，则∀β≠α、β∈A,规定“αR+β⟺αRβ”、“βR+α⟺βRα”、“αR-β⟺αRβ”、“βR-α⟺βRα”。对任何非单点集Λk，写出其全部元素并任意排列Λk={αs1,αs2,…,αsi},规定αs1R+αs2R+…R+αsi⟺αs1αs2…αsi；并规定αs1R-αs2R-…R-αsi⟺αs1≻αs2≻…≻αsi。

显然，可以验证R+和R-均为备择物集A={α1,α2,…,αi}上的严格偏好序，为强序。因为∀α、β∈A,若αβ或者βα，规定“αR+β⟺αRβ”、“βR+α⟺βRα”、“αR-β⟺αRβ”、“βR-α⟺βRα”保证了R+和R-对α、β序向和R相同。若α～β，则∃Λkα、β,则或者αR+β、βR-α同时为αβ，或者则βR+α、αR-β同时为βα。从而，R+、R-都是强序，保持了R的严格偏好关系。故(R+、R-)为R的分影。

综上所述各种情况，定理得证。

定理3对于(A,R)，φA/～R=(R+，R-)在A/～上保持了等价类序，同时对于等价类划分A/～中的一个划分子集Λs作轮换∇：Λs→Λs，延拓∇在AΛs上为恒等映射，则R+∇和R--1也构成R的分影。

证明为证明第一个结论，考虑(A,R)的等价类划分A/～={Λ1、Λ2、…、Λk}。按照φA/～R=(R+，R-)定义，∀α、β∈A,且α～β，为证明方便设R排序为αβ；则∃Λkα，对于此Λk，必然β∉Λk，于是α、β在R+、R-中不能序反向，并且α、β在R+、R-中序向都相同于R的序向；即R+排序为αβ，同时R-排序也为αβ；由于Λkα，β∉Λk，取Λhβ，在Λk、Λh上，∀α′∈Λk以及∀β′∈Λh，R中α′～α、β′～β⟹α′β′。从而按(R+，R-)定义，R+、R-中α′、β′序向都相同于R的序向。由于α′、β′的任意性，则R+、R-在A/～上保持了等价类序，也即可规定∀α∈Λs、α′∈Λt，ΛsΛt⟺α′。

第二个结论只需要证明对应于等价类上的序反向。考虑A/～={Λ1、Λ2、…、Λk}，其中∇在Λs上为轮换映射，在AΛs上为恒等映射。由恒等映射，∀α、β∈AΛs，α、β在R+∇、R--1的序向分别和R+、R-完全相同；并且由第一结论，即使∀α∈Λs、∀β∈AΛs，α、β在R+∇、R--1的序向分别和R+、R-完全相同；为此只需考虑Λs。∀α、β∈Λs,只需证明α、β在R+∇、R-∇中序反向即可。设∇α=α*，∇β=β*，若R+∇排α、β为αβ，即R+排α*、β*为α*β*。考虑R-∇对α、β的排序，由∇α=α*，∇β=β*，即R-对的α*、β*。R+排α*、β*为α*β*⟹R-排α*、β*为β*α*⟹R-∇排对α、β的排序为βα。由此，α、β在R+∇、R-∇中序反向。即R+∇和R--1也构成R的分影。

对上述定理做直接的推广，即可得如下一些更为深刻的结论：

对于(A,R)的等价类划分A/～={Λ1、Λ2、…、Λk}而言，对于1≤s≤k设s在上Λs是轮换映射,在AΛs上为恒等映射，若(R+，R-)为R的分影，则(R+s，R-s)也为R的分影。(R+s)n，R-(s)n)也为R的分影。对于1≤t≤k设t在上Λt是轮换映射,在AΛt上为恒等映射，(R+((∇t)m(s)n，R-(t)m(s)n)也为R的分影。

定理4R+、R-∈(A,R)，都为A的偏好强序，如果∀α、ξ、ζ∈A，∇：{α、ξ、ζ}→{α、ξ、ζ}为R+对α、ξ、ζ三者的排序轮换，R+∇、R+2、R+3对α、ξ、ζ的排序均不在R-对α、ξ、ζ三者的排序之中，则(R+、R-)为A上的对影偏好。

证明按定义和定理2，关键A合理的划分A=Λ1∪Λ2∪…∪Λk能保证不同的两个子集Λkα、Λhβ⟹R+、R-对α、β排序序向相同；以及能保证同一个子集Λkα、β⟹R+、R-对α、β排序序向反同。构造A的如下划分A=Λ1∪Λ2∪…∪Λk即可。

记A={α1,α2,…,αi}对于R+为A的偏好强序，为方便，不妨设R+排A为α1α2…αi。

考察R-对α1,α2的排序强序的两种情况。

情况1若R-排为α1α2，则不存在α∈A，使得R-排为αα1。否则R-排为αα1必产生矛盾；因为，一方面α≠α2(否则R-排为α1α=α2产生矛盾)于是R+排为α1α2α，另一方面，R-对α1、α2、α的排序为αα1α2。那么显然只要取轮换映射∇：{α1、α2、α}→{α1、α2、α}，那么R-排为αα1α2，即有R-=R+∇，产生矛盾。

于是，R-排为α1α2，则不存在α∈A，使得R-排为αα1。于是取Λ1={α1}。同时有∀β∈AΛ1，即β≠α1，并必然α1β。

情况2若R-排为α2α1，取Λ1={α1}∪{α∈A|R-:αα1}，并且‖Λ1‖≥2。(1)若‖Λ1‖=2，也即Λ1={α1、α2}，显然R-：α2α1，即R+、R-在Λ1={α1、α2}排序是反向的。并且∀β∈AΛ1，必有R-:α1β、R-:α2β；即R-排序中AΛ1中任何元素严格优于Λ1中的全部元素。(2)而若‖Λ1‖>2,则考察R-排序α2、α3,必然有R-:α3α2α1,也即必然有α3∈Λ1；否则，一方面α3∈Λ1时R-:α2α3α1会有矛盾，因为R+：α1α2α3以及R-:α2α3α1⟹R-=R+2，即为矛盾。另外一方面，α3∈AΛ1也将导致矛盾。因为‖Λ1‖>2，α1∈Λ1、α2∈Λ1、α3∈AΛ1，必存在α∈Λ1，并且R+:α1α2α3α。但既然α3∈AΛ1⟹R-:αα2α1α3或者α2αα1α3。但无论如何，对于α1、α3、α而言，R+:α1α3α，R-:αα1α3。显然有R-=R+∇，产生矛盾。(3)由归纳法，事实上可证，‖Λ1‖=k时，必然为Λ1={α1}∪{α∈A|R-:αα1}={α1,α2,…,αk},并且R-在Λ1上排序为R-:αk…α3α2α1。另外，Λ1={α1}∪{α∈A|R-:αα1}⟹∀β∈AΛ1以及∀α∈Λ1，必然R-:αβ。

以上构造了Λ1并分析了Λ1单点集、两点集、多点集情况下，R-在Λ1内部的排序正好与R+序紧链反向。以AΛ1={αk+1,αk+2,…,αi},考虑R-对αk+1,αk+2的排序进行以上过程构造Λ2，显然Λ2可能是单点集、两点集、多点集情况，但‖Λ2‖=s时必然有Λ2={αk+1,αk+2,…,αk+s}。并且有R+、R-在Λ2排序是反向的，Λ1Λ2；另外∀β∈AΛ1，∀α∈Λ1，必然R-:αβ。∀β∈A(Λ1∪Λ2)，∀α∈AΛ1，必然R-:αβ。

由归纳法知A=Λ1∪Λ2∪…∪Λk能保证不同的两个子集Λkα、Λhβ⟹R+、R-对α、β排序序向相同；以及能保证同一个子集Λkα、β⟹R+、R-对α、β排序序向反同。定理得证。

4 余论

以上考虑了社会选择函数集结中的对影判别和性质。通过严格形式化刻画，给出了弱序偏好的强序化，强序化为分影偏好，给出了分影偏好定义，分析了其基本性质，并考虑广为关注的孔多塞循环，联系孔多塞循环和轮换，给出了一般意义上的分影的判别。以上定理1、2、3、4形成了一个完整的框架。

同时，这里可考虑[0,1]或者是无界空间[0,+∞)连续空间上的对影，就是连续的空间上区间。另外，可考虑三元组不构成孔多塞循环时，添加一个元素形成整序，一个空间上的三元组，固定方向后添加一元，最多可能只有四种情况。

虽然，考虑社会选择函数约束公理系统的相容性是社会选择理论的理论基础，但从现实形式上直接考虑偏好集结仍然具有十分重要的实践意义。本质上，本文提出的社会选择函数集结中的对影就是一个十分重要的、可行的集结机制，从而发展了集结的机制设计，也提供了指示约束公理系统相容性的一种方法。