关于极小极大社会选择对应的反向偏差

，h}是个体的集合。N上的偏好关系是N上的线性序，即N上的完全、传递和反对称二元关系。N上的线性序集用L（N）表示。让q∈ L（N）固定。给定x，y∈ 我们通常写x≥qy代替（x，y）∈ q、 x>qy代替（x，y）∈ q和x6=y。函数rankq:N→ {1，…，n}定义为每x∈ N、 byrankq（x）={y∈ N:y>qx}|+1是双射的。我们用函数秩来表示q-1qa仍然用q表示。我们还用列向量[q（1），…，q（n）]T来标识q。此外，我们定义了L（n）中的元素qrast，这样，对于每个x，y∈ N、 （x，y）∈ qrif且仅当（y，x）∈ q、 当然，（qr）r=q。例如，设n=3和q∈ L（N）be使得2>q1>q3。然后q（1）=2，q（2）=1，q（3）=3，我们用[2,1,3]和[3,1,2]T来识别q。偏好文件是L（N）h的一个元素。集合L（N）his用P表示。让P∈ Pbe固定。考虑到我∈ H、 p的第i个组成部分用pian表示，代表个人i的偏好。偏好文件p可以自然地与第i列为[pi（1），…，pi（n）]T的矩阵识别。定义∈ P作为每个i的首选文件∈ H、 （pr）i=（pi）r.当然，（pr）r=p.我们将把prs的第i个分量写成pri，而不是（pr）i.给定u∈ N∩ （h/2，h]和x，y∈ N，如果|{i，我们写x>puy∈ H:x>piy}|≥ u. 注意x>puy当且仅当y>prux.N中的元素∩ （h/2，h]称为多数阈值。我们称最小多数阈值为整数u=h+1. 关于偏好关系和偏好偏好的更多细节，请参见Bubboloni和Gori（2015）。社会选择对应（scc）是从P到N的非空子集集的函数。SCC的集合用C表示∈ C

我们说，如果存在p，C会影响反转偏差（类型1）∈ P和x∈ N使得C（p）=C（pr）={x}；如果存在p，则t型2的逆转偏倚∈ 例如t | C（P）|=1和C（P）∩ C（pr）6=;如果存在p∈ 例如t | C（P）|<n和C（P）∩ C（pr）6=.显然如果C∈ C s影响类型1的反转偏差，那么C也影响类型2的反转偏差，如果C s影响类型2的反转偏差，那么C也影响类型3的反转偏差。我们为每一个j∈ {1,2,3}，setsCj={C∈ C:C对j型的反转偏倚免疫。注意C C C.3最小最大scc本节我们重点讨论每个p的最小最大scc，用M表示并定义∈ P、 byM（P）=一个rgminx∈Nmaxy∈N\\{x}{i∈ H:y>pix}|。根据上述定义，M（p）是那些最小化最大成对失败的备选方案集，与p描述的个人偏好相对应。然而，最小最大scc的结果允许在多数阈值方面的备选解释。给定u∈ N∩ （h/2，h），定义为每p∈ P、 setDu（P）={x∈ N:Y∈ N、 |{i∈ H:y>pix}|<u}。因此，替代品x属于Du（p），当且仅当至少u个个体无法找到另一个比x更偏好的替代品时，根据偏好文件p。请注意，setDu（p）对应于Gre e e nberg（1979）在更一般的设置中定义的与p相关的u-多数均衡集，其中个人偏好通过完整和传递关系表示。注意，如果≤ u′，然后是Du（p） Du′（p）表示所有p∈ P.此外，对于每一个μ，Gr eenberg（197 9）中的推论3的一个s animimediate推论及其证明∈ N∩ （h/2，h），我们有du（p）6= 尽管如此，p∈ P当且仅当u>n- 1nh。

（1） 自从h∈ N∩ （h/2，h]和h>n-1nh，很好地定义了由uG=min给出的格林伯格多数阈值M∈ N∩ （h/2，h）：m>n- 1nh.每p∈ P、 我们考虑整数u（P）=min{u∈ N∩ （h/2，h）：Du（p）6=}.注意，由于（1）表示DuG（p）6=, 我们发现u（p）的定义很明确，且u≤ u（p）≤ uG.我们现在可以证明以下命题。提议1。每p∈ P、 M（P）=Du（P）（P）。证据我们首先证明了M（p） Du（p）（p）提供N\\Du（p）（p） N\\M（p）。让x∈N\\Du（p）（p）。然后就有了前科∈ N\\{x}这样|{i∈ H:y>pix}|≥ u（p）。选择nowx∈ Du（p）（p），对于每个y∈ N\\{x}，|{i∈ H:y>pix}|≤ u（p）- 1.因此，maxy∈N\\{x}{i∈ H:y>pix}|≤ u（p）- 1<|{i∈ H:y>pix}|≤ 麦克西∈N\\{x}{i∈ H:y>pix}|，表示x/∈ M（p）。接下来我们证明Du（p）（p） M（p）。让x∈ Du（p）（p）。那么，我们有麦克西∈N\\{x}{i∈ H:y>pix}|≤ u（p）- 1.自相矛盾地假设存在x∈ 麦克斯∈N\\{x}{i∈ H:y>pix}|<maxy∈N\\{x}{i∈ H:y>pix}|。Fishburn（1977）提出了等效的定义m（p）=argmaxx∈n米尼∈N\\{x}{i∈ H:x>piy}|。然后x6=X，对于每个y∈ N\\{x}，我们有{i∈ H:y>pix}|<u（p）- 1.如果u（p）-1>h/2，即x∈ Du（p）-1（p）= 发现了矛盾。假设tu（p）- 1.≤ h/2。那么u（p）=u=h+1≤h+2和自|{i∈ H:x>pix}|≤ u- 2.我们得到|{i∈ H:x>pix}|≥ H- u+ 2. 现在我们观察到，由于≤h+2，我们有h- u+ 2 ≥ u，对x∈ Du（p）。定义setsT={（h，n）∈ N: H≤ 3} ∪ {（h，n）∈ N: N≤ 3} ∪ {（4,4）、（5,4）、（7,4）、（5,5）}，T={（h，n）∈ N: h=2}∪ {（h，n）∈ N: N≤ 3} ∪ {（4，4）}，T={（h，n）∈ N: n=2}∪ {(3, 3)}.注意T（T）（T）。我们现在可以陈述本文的主要结果。它的证明是技术性的，将在第5节中陈述。

我们强调它依赖于命题1和图论的语言和方法的使用（第5.1节和第5.2节）。定理2。让j∈ {1, 2, 3}. 然后，我∈ Cjif且仅当（h，n）∈ Tj。4 Borda和Copeland scc在本节中，我们表明，与Minimax scc的情况不同，Borda和Copeland scc易于分析普遍偏差。这些SCC分别用硼和Cop表示，并针对每个p进行定义∈ P、 asBor（P）=argmaxx∈NPhi=1N- rankpi（x）,Cop（p）=argmaxx∈N|{y∈ N:x>puy}|- |{y∈ N:y>pux}|.以下结果表明，他们对3型的逆转偏倚免疫。提议3。波尔，警察∈ C.证据。我们开始考虑博尔达scc。我们需要为每一个p∈ P、 博尔（P）∩博尔（pr）6= 意味着Bor（p）=N，然后修复p∈ P和x∈ N这样x∈ 博尔（p）∩ 博尔（公关）。设f、g和u为从N到R的函数，对于每个x∈ N，byf（x）=hXi=1N- rankpi（x）, g（x）=hXi=1N- 兰克里（x）, u（x）=hXi=1rankpi（x）。注意bor（p）=argmaxx∈Nf（x），Bor（pr）=argmaxx∈Ng（x），以及，对于每一个x∈ N，f（x）=hn- u（x）和g（x）=u（x）- h、 由于这个因素，rankpr（x）=n+1- rankp（x）。然后x求出u的最小值和最大值，使u为常数。因此，f也是常数，因此Bor（p）=N。对于Borda scc，我们指的是众所周知的Borda计数。科普兰scc的定义可以在Fishburn（1977）中找到。接下来我们考虑科普兰scc。我们需要证明，对于每一个p∈ P、 警察（P）∩警察（公关）6= 意味着Cop（p）=N。然后修复p∈ P和x∈ N这样x∈ 警察（p）∩ 警察（公关）。

设f和gbe函数从N到R定义，每x∈ N，byf（x）={y∈ N:x>puy}|-|{y∈ N:y>pux}|，g（x）=|{y∈ N:x>pruy}|-|{y∈ N:y>prux}|。注意cop（p）=argmaxx∈Nf（x），Cop（pr）=argmaxx∈Ng（x）。此外，对于所有x，y，sinc e x>priy相当于y>pix∈ N和我∈ H、 我们每个人都有∈ N，g（x）=-f（x）。然后X实现了f的最小值和最大值。由此可知f是常数，因此Cop（p）=N。下一个推论说明了如何利用关于M、Bor和Cop的反转偏差的结果，来建立关于个体数和替代数的条件，这些条件是必要的，并且足以使M=Bor和M=Cop相等。推论4。M=Bor当且仅当n=2。证据如果n=2，那么我们肯定有M=Bor。假设n≥ 3.如果（h，n）6∈ T、 然后，由提奥·雷姆2和命题3，M 6∈ 坎德博尔∈ Cso表示M 6=Bor。If（h，n）∈ T、 然后（h，n）=（3，3），我们仍然有m6=Bor，因为两个SCC在优先权上不同=1 1 22 2 33 3 1推论5。M=Cop当且仅当（h，n）∈ T.证明。如果n=2，那么我们肯定有M=Cop。假设n≥ 3.如果（h，n）6∈ T、 然后，由提奥·雷姆2和命题3，M 6∈ 坎德警察∈ Cso，M 6=警察。If（h，n）∈ T、 然后（h，n）=（3，3）。以p为例∈ P.由于M和Cop都是中性的，没有失去普遍性，我们可以假设P=[1,2,3]T。回顾M和Cop都满足Condorcet pr inc iple，当Condorcet赢家存在时，它们肯定是一致的。因此，我们可以假设，第一个备选方案之间是不同的。由于M和Cop都是匿名的，我们可以假设p（1）=2和p（1）=3。只剩下四个病例需要治疗。

通过逐案计算，最终可以证明M=Cop。5定理2的证明从命题1我们立即得到定理2由以下三个命题所隐含。第5.3节、第5.4节和第5节介绍了他们基于图论的棘手证明。5.提议6。存在p∈ P和x∈ N使得Du（p）（p）=Du（pr）（pr）={x}如果且仅限于（h，N）∈ N\\ T.提案7。存在p∈ P和x∈ N使得Du（p）（p）={x} Du（pr）（pr）if和onlyif（h，n）∈ N\\ T.提案8。这里有∈ 使得Du（P）（P）6=N和Du（P）（P）∩ Du（pr）（pr）6= 当且仅当（h，n）∈ N\\ T.5.1图表在本节中，我们回顾了图论中的一些基本事实和符号，我们将在续集中使用它们。所有考虑的图都是有向图。一个图是一对（V，A），其中V是一个称为顶点集的不完全集，A是{（x，y）的子集∈ V:x6=y}称为弧集。注意，如果Γ=（V，A）是一个图且|V |=1，那么A=. 给定两个gr-aphsΓ=（V，A）和Γ=（V，A），我们说Γ是Γif V的子图 范达 A.如果Γ是Γ的子图，我们写Γ≤ Γ.现在让Γ=（V，A）成为一个图。Γ是完全的，如果每x，y∈ V，x 6=y，我们有（x，y）∈ A或（y，x）∈ A.我们说x∈ 如果不存在y，V是rΓ的最大[最小]∈ V这类（y，x）∈ A[（x，y）∈ A] 。我们用max（Γ）[min（Γ）]表示Γ的最大[最小]垂直集。请注意，这些集合可能是空的。我们说x∈ V是Γif的最大值[最小值]，例如y∈ V\\{x}，我们有（x，y）∈ A[（y，x）∈ A] 。我们用Max（Γ）[Min（Γ）]表示Γ的最大值[最小值]的集合。我们说x∈ V在Γif中被隔离，对于每个y∈ V\\{x}，（x，y），（y，x）6∈ A.我们用I（Γ）表示Γ的孤立顶点的集。注意Max（Γ）是有用的∩ min（Γ）=I（Γ）。

（2） 注意，如果x∈ 麦克斯（Γ）∪ Min（Γ）和|V|≥ 2，然后是x6∈ Γ（I）。Γ被认为是连通的，如果，对于每个x，y∈ 当x 6=y时，存在k≥ 2和有序序列x，V的不同元素，使得x=x，xk=y，对于每个j∈ {1，…，k-1} ，（xj，xj+1）∈ 或（xj+1，xj）∈ A.注意，如果Γ是最大值[最小值]，那么Γ是连通的。众所周知，存在一个唯一确定的c∈ N与连通子图Γ=（V，A），Γc=（Vc，Ac）的∪ci=1Vi=V，∪ci=1Ai=A，对于每个i，j∈ {1，…，c}，其中i6=j，Vi∩ Vj=Ai∩ Aj=. 那些子图Γ，Γcare将连接的组件称为Γ。它们是Γ的连通子图的极大a，也就是如果Γ′≤ Γ是连通的，Γ′是连通的≥ Γ如果有人∈ {1，…，c}，然后Γ′=Γi。特别是，对于每一个i∈ {1，…，c}，x∈ 维安迪∈ V\\V暗示（x，y），（y，x）/∈ A.x、 y∈ 维兰德（x，y）∈ A（x，y）∈ 人工智能。注意，x∈ N在Γ中是孤立的，当且仅当包含x的连通分量o fΓ是（{x}），). 考虑到我≥ 2，如果| V |=l且存在有序序列x，…，则称Γ为l-环，在v的元素中，一旦定义了xl+1=x，我们得到A={（xj，xj+1）：1≤ J≤ l} 。Γ是一个循环，如果它是一些l的l-循环≥ 2.固定l≥ 2，如果存在一个l-循环，则称Γ为l-循环≤ Γ，否则为l-非环。Γ是无环的，如果它对所有l都是l-无环的≥ 2.注意，如果| V |=1，那么Γ是非循环的。5.2多数图及其性质let p∈ P和u∈ N∩ （h/2，h）.自然地，我们与∑u（p）={（x，y）给出的N上的关系有关∈ N×N:x>puy}，图Γu（p）=（N，∑u（p））称为p的u-多数图。注意，如果u，u′∈ N∩ （h/2，h]带u′的≤ u，然后Γu（p）≤ Γu′（p）。尤其是Γu（p）≤ Γu（p）适用于所有u∈ N∩ （h/2，h）。

当h为奇数且u=u=h+1时，多数图的概念基本上与ca se有关（例如，参见Miller（1977））。在我们的论文中，这个例子很有趣，因为Γh+1（p）是完整的（见引理12），但我们并不是只关注这个特殊的多数图。关系∑u（p）的性质很容易转化为Γu（p）的图论性质。此外，考虑Γu（p），我们获得了使用l-非环性和连通性等概念的优势，这些概念通常属于图论。这很快就能更好地理解集合Du（p）和Du（p）（p）=M（p）。所有无法解释的符号都是标准的。例如，参见Diestel（2010）。注意，如果x是Γ的最大值[最小值]，则不一定是Γ的最大值[最小值]。事实上，给定Γ=（{1，2}，{（1，2），（2，1）}），我们知道1和2都是最大值[最小值]，但它们都不是最大值[最小值]。引理9。让我们∈ N∩ （h/2，h]和p∈ P.然后Du（P）=max（P））=min（pr）。MoreoverDu（p）∩ Du（pr）=I（Γu（p））=I（Γu（pr））。证据等式Du（p）=max（p））=min（pr））遵循Du（p）和pr的定义。因此，由于（pr）r=p，我们也有Du（pr）=max（Γu（pr））=min（Γu（p）），所以t（2）完成了证明。引理10。让我们∈ N∩ （h/2，h]和p∈ 那么Γu（P）是2-无环的，Γu（P）最多有一个最大值。此外，如果Γu（p）具有最大x∈ N、 然后Du（p）=Max（Γu（p））={x}。证据2-酰基丰度紧接着从u>h/2开始。自相矛盾地假设存在不同的x，y∈ 最大值（μu（p））。然后（x，y）∈ ∑u（p）和（y，x）∈ ∑u（p），所以Γ=（{x，y}，{（x，y），（y，x）}）≤ Γu（p）。由于Γ是一个2-环，这与Γu（p）是2-非环的事实相矛盾。假设存在x∈ Max（μu（p））并显示x∈ 最大（Γu（p））=Du（p）。顺便提一下，le t x 6∈ 麦克斯（Γ）。

还有一个是y∈ N使得（y，x）∈ ∑u（p）。自也（x，y）∈∑u（p），2-圈Γ=（{x，y}，{（x，y），（y，x）}）是Γu（p）的一个子图，并发现了矛盾。我们完成证明时只需注意到，对于每个y，x的最大值为Γu（p）∈ N\\{x}，我们有（x，y）∈ ∑∑u（p）使y6∈ 最大值（μu（p））。引理11。让我们∈ N∩ （h/2，h）。那么Γu（p）对于所有p都是非循环的∈ P当且仅当u≥ uG.特别是Γh（p）对所有p都是无环的∈ P.证明。这是Bubboloni和Gori（2014）中6号和7号提案的直接结果。引理12。如果h是奇数，那么对于每一个p∈ P、 Γu（P）是完整的，I（Γu（P））=. 此外，如果Du（p）6= 那么u（p）=u，Γu（p）允许m最大值x∈ N和Du（p）={x}。证据让我们来看看∈ 注意，由于h奇数，我们有u=h+1。现在，通过矛盾假设存在x，y∈ N，其中x6>puy，y6>pux。然后，我们得到不可能的关系h={i∈ H:x>piy}|+|{i∈ H:y>pix}|≤ u- 1 + u- 1 = 2h+1- 2=h- 1.因此，Γu（p）是完整的，并且作为直接结果，I（Γu（p））=.为了证明第二部分，假设Du（p）6=. 然后u（p）≤ u和sou（p）=u。接下来，选择x∈ Du（p）。既然Γu（p）是完整的，那么对于所有y，x>puy∈ N\\{x}，也就是说，x是Γu（p）中的最大值。然后，通过引理10，Du（p）={x}。让我们用C（Γu（p））表示Γu（p）和定义a（Γu（p））的连接组件的集合∈ C（Γu（p））：Γ是无环的。我们准备好了一个关键的命题，给出了| Du（p）的下限，并导致了一些有趣的结果。提议13。让我们∈ N∩ （h/2，h]和p∈ P.然后du（P）=[Γ∈C（Γu（p））最大值（Γ）[Γ∈A（μu（p））最大值（μ） I（Γu（p））和|Du（p）|=XΓ∈C（u（p））|max（Γ）|≥ |A（Γu（p））|≥ |I（μu（p））|。证据设Γ=（V，A）∈ C（Γu（p））。然后呢≤ Γu（p），因此 N和A ∑u（p）。因为Γ是Γu（p）的连通分量，所以每x∈ V和y∈ N\\V，y 6>pux。

这会立即给出每个x∈ max（Γ）属于Du（p），所以Du（p）SΓ∈C（Γu（p））最大值（Γ）。另一种夹杂物很小，因此Du（p）=SΓ∈C（Γu（p））最大值（Γ）。自A（μu（p）） C（Γu（p））和外汇∈ I（Γu（p）），（{x}，) ∈ A（Γu（p）），我们也g et[Γ∈C（Γu（p））最大值（Γ）[Γ∈A（μu（p））最大值（μ） I（Γu（p））。特别是，由于不同连接组件的顶点之间没有重叠，我们得出| Du（p）|=pΓ∈C（μ（p））|max（μ）|。我们完成了证明，证明∈ A（Γu（p）），我们有max（Γ）6=. 选择x∈ 五、如果y 6>puX或所有y∈ V，那么我们有x∈ 麦克斯（Γ）和我们已经完成了。假设存在x∈ V的x>pux。显然，我们有x6=x。然后，重复x的参数。因为集合N是有限的，且Γ不包含循环，所以在有限的数字中≤ n步，我们得到一个元素xk∈ 马x（Γ）。推论14。让我们∈ N∩ （h/2，h]和p∈ P.如果Γu（P）允许至少一个非环连接成分，则u（P）≤ u.证据根据命题13，我们得到了| Du（p）|≥ 1，所以Du（p）6=.推论15。让我们∈ N∩ （h/2，h]和p∈ P.如果Γu（P）是非循环的，而Du（P）是单态，则Γu（P）是连接的。证据由于Γu（p）是无环的，我们有C（Γu（p））=A（Γu（p））。然后，使用命题13，我们得到1=|Du（p）|≥ |Γ（1245p）≥ 1.这意味着| C（Γu（p））|=1，也就是说，Γu（p）是连通的。引理16。让p∈ P使得u（pr）≤ u（p）。然后：（i）Du（p）（p）∩ Du（pr）（pr） I（Γu（p）（p））。特别是，如果Γu（p）（p）连接，则Du（p）（p）∩Du（pr）（pr）=.（ii）如果| Du（p）（p）|=1且Γu（p）（p）是非循环的，则Du（p）（p）∩ Du（pr）（pr）=.证据（i） 来自u（pr）≤ μ（p）我们得到Dμ（pr）（pr） Du（p）（pr），因此，通过引理9，我们推导出了u（p）（p）∩Du（pr）（pr） Du（p）（p）∩Du（p）（pr）=I（p）（p））。如果Γu（p）（p）被连接，那么I（Γu（p）（p））是空的，因此Du（p）（p）也是空的∩ Du（pr）（pr）=.（ii）根据推论15，（i）给出Du（p）（p）∩ Du（pr）（pr）=.推论17。让我们∈ N∩ （h/2，h]和p∈ P