没有合适的资源?快使用搜索试试~ 我知道了~
+v:mala2277获取更多论文在Voters'B e h a v i or中通过多个PatePaterns执行扩展Sonja Kraiczy1, Edith Elkind11牛津大学计算机科学系Sonja. merton.ox.ac.uk,eelkind@cs.ox.ac.uk摘要在一些偏好聚合场景中,选民的偏好是高度结构化的:例如,候选者集合可以具有一维结构(使得投票者然而,有时单个轴或决策树不足以捕获投票者 树木)。 在这项工作中,我们研究的复杂性,决定是否可以用这种方式来解释消费者的偏好。对于k =2,我们得到一个多项式时间算法-rithm为几个域:单峰首选-”(《明史》卷102)“问其故,问其故,问其故。 2017)、可变约束偏好、组可分离偏好以及组可分离偏好的自然子域,即,卡特彼勒组可分离偏好。对于k≥3,已知该问题对于单峰偏好;我们表明,这也是价值限制和组可分离的偏好的情况下。我们的积极结果k=2利用禁止-den各自的小特征主要的,特别是,我们建立的域的毛毛虫组可分离的偏好承认一个禁止未成年人的特征。1介绍某国即将举行大选。X中的每一个政党都可以在从左到右的政治光谱中找到一个位置。此外,各方亦就疫苗要求、学校关闭及口罩规定等事宜制定COVID-19政策。这些政策为各方提供了一种可供选择的排序,从支持严格措施的各方到反对任何限制的各方。这两种排序非常不同:例如,其中一个左翼政党认为限制措施对其选民有害,而另一个左翼政党则支持极端的病毒控制措施。艾丽斯、鲍勃、卡罗尔和戴夫计划在这次选举中投票。Alice和Bob然而,Alice和Bob都完全忽略了双方相比之下,卡罗尔和戴夫认为,无论如何,大流行很快就会结束,并根据他们的社会和经济政策对各方进行排名。因此,在这种情况下,集体偏好由候选日期集合上的两个轴驱动,每个投票者现在,假设我们期望集体偏好具有这种一般形状(可能具有k≥2个轴),但我们不知道潜在的k排序:我们能在多项式时间内识别它们以及投票者集合的相关划分吗?这个问题同样适用于另一个结构概念:虽然偏好与轴一致的想法被单峰偏好的数学概念所捕获[Black,1948],但我们也可以考虑单交叉偏好[Mirrlees,1971; Roberts,1977]或组可分离偏好[Inada,1964]。后一种方法在计算社会选择文献中受到的关注相对较少(参见Faliszewski et al.[2021]),由可以用二叉决策树解释的偏好配置文件组成:每个备选方案由一组二叉属性表征,每个投票者对每个属性都有一个偏好值,并且有一个二叉树,其顶点标记有引导投票者决策过程的属性将输入轮廓划分为k个单点轮廓的问题已经由Erdell等人讨论过。 [2017],他对k ≥ 3得到了NP-硬度结果,但对k =2打开。这个开放的问题是高-由Jaeckle等人[2018]点燃,他们也研究了类似物的单交叉偏好,并获得一个多项式时间算法k=2。然而,它的变量组可分离的偏好(其中我们寻求k个二叉决策树,我们的贡献我们解决了Er d'lyietal的开放问题。 [2017],通过我们如何能确定一个政策-arXiv:2201.11195v1 [cs.GT] 2022年1月+v:mala2277获取更多论文通常,输入轮廓P是否可以被划分为两个子轮廓P1和P2,使得这些轮廓中的每一个都是单峰。我们的证明是基于单 峰 偏 好 在 禁 止 子 项 方 面 的 特 征 : 如 Ballester 和Haeringer[2011]所示,存在一个小的恒定大小的偏好配置文件集,使得配置文件是单峰的,当且仅当它不包含与此集中的配置文件同构的子配置文件。我们的方法的优点是,它扩展到其他几个领域,承认一个禁止的次要特征,包括,特别是,群体可分离的偏好。此外,我们考虑组可分离偏好的自然子域,即毛虫组可分离域:它由底层二叉树是毛虫形的轮廓组成每个二元判决将单个候选与所有其它候选进行比较。我们提供了一个表征这个域的禁止未成年人,从而表明我们的算法也适用于这个域。为了补充这些结果,我们表明,划分问题是NP-难的组可分离的偏好(和其他几相关域),对于每个k≥3的值。我们认为我们的结果很有趣有两个原因。首先,识别单峰轮廓的轴或组可分离轮廓的二叉决策树有助于我们理解替代空间的结构;这仍然是轮廓由两个第二,从更实际的角度来看,存在对于一般偏好计算困难的投票问题,但是对于结构化偏好允许多项式时间算法;一个突出的例子是用于单峰偏好的Chamberlin-Courant规则的al-tax m [ Betzler etal. [2013],它依赖于知道轴。虽然我们还不知道对于可以被划分为少量结构化简档的简档是否可以获得类似的结果(参见Misra等人的工作)。 [2017]在这种精神的一些贡献),我们的结果提供了一个有希望的起点和必要的成分,这样的算法。相关工作我们的工作属于对识别近结构化轮廓(即,可以制成单峰/单交叉/组可分离等的曲线。小小的修饰,阳离子),这是由Brederecket al. [2016年] a n d他也是。[2017];see阿斯奥THE工作^Jaeckleet al.[2018]和Lakhaniet al. [2019],以及Elkindet al.的调查。[2017年]。几个结构化域可以通过一小组禁止子项来表征:这是单峰和组可分离偏好[Ballester和Haeringer,2011]和单交叉偏好[Brederecket al. ,2013]。此外,一些域直接根据非 负 子 项 来 定 义 最 佳 / 中 等 / 最 差 / 值 受 限 域 [Sen ,1966]) 。我 们的 基于 minor 的 方法 在概 念上 类 似于Elkind和Lackner[2014]的工作,他们为所有可以通过恒定大小的禁止minors来表征的域提供了投票者/候选人删除结构化偏好的近似算法。Karpov[2019]和Faliszewski等人 [2021]启动了算法分析的群体可分离的偏好。特别是,据我们所知,Faliszewski等人。 [2021]是第一个讨论卡特彼勒集团可分离偏好的域;然而,他们的主要焦点是这种偏好的投票问题的复杂性,而不是这个域本身的结构。2预赛假设C是候选人的有限集合。对C的投票是对C的线性序。给定C上的投票v和两个候选人a,b∈C,我们写一个vb来表示a的排名高于b在v. 我们将这个符号扩展到集合:AvB意味着v将A的所有元素排在B的所有元素之上。的偏好候选集C上的简档P是C上的投票列表。给定对C的投票v和候选人的子集A≠C,v对A的限制是投票v|A在A上,使得对于所有的a,b∈A,v成立|A使A高于B当且仅当v把a排在b的上面。 给定分布P =(v1,. . . ,v n)和候选者的子集A ∈ C , 则P 对A 的限制是简档P|A=(u1,. . .,u n),使得u i= v i|对于每个i ∈ [n]。A上的轮廓P ′是C上的轮廓P的子轮廓,如果A≠C,并且P′是通过从P中移除零个或更多个投票而获得的|A.我们将考虑几种特殊的偏好类别定义2.1(单峰偏好)。设k是候选集C上的线性序。C上的投票v是单峰的,如果对于每个三元组a,b,c∈C,使得a<$b<$c,它保持b<$va或b<$vc。如果P中的每个投票都是单峰的,则P在C上的轮廓是单峰的。一个剖面P是单峰的,如果在C上存在一个阶,使得P在C上是单峰的;这个阶被称为轴。单峰偏好模型设置,其中所有候选人可以在从左到右的轴上排序,并且每个投票者在该轴上具有最喜欢的点,并且按照与该点的距离增加的顺序将候选人排名在他们最喜欢的点的任一侧:例如,如果投票是关于税率的,一个最喜欢税率为22%的选民更喜欢20%,而不是15%和27%。到40%(但可能更喜欢27%而不是20%)。定义2.2(可分组偏好)。候选集C上的轮廓P是群可分的,如果每个候选集A<$C有一个真子集B<$A,使得对于每个投票v∈P,我们有B<$v(A\B)或(A\B)<$vB。等价的、组可分离的简档可以用二元决策树定义如下。有序二叉树是一个根树,每个内部节点有两个孩子,其中一个孩子被指定为左孩子,另一个被指定为右孩子。给定一个有序二叉树T,其叶子被标记为C的元素,我们说C上的投票v是T-相容的,如果对于T的每个内部节点x,它保持v将x的左子树中的所有候选者排在x的右子树中的所有候选者之上,或者反之亦然。我们说一个轮廓P是T-相容的,如果P中的每一票都是T-相容的.以下命题隐含在先前的工作中(参见[Karpov,2019]);为了完整性,我们在附录A中提供了证明。提案1. 一个剖面P是群可分的当且仅当它对某个有序二叉树T是T-相容的。+v:mala2277获取更多论文T,xT,aT,aT、c3T,aT、c我们可以把T的内部节点看作二元属性:x的左子树中的所有候选者都拥有与x相关的属性,而x的右子树中的所有候选者都不拥有它。每个投票者认为每个属性是可取的或不可取的,并通过从树的根开始向下移动来相应地形成它们的排名。因此,树T在群可分偏好在单峰偏好的定义中扮演着类似于轴的角色受限域是偏好简档的集合;例如,我们将谈到所有单峰轮廓的域限制域X是遗传的,如果对于每个剖面P∈X,它保持P的每个子剖面在X中。从定义中可以直接看出,SP和GS都是遗传的。如果两个配置文件可以通过重新命名候选人和/或重新排序投票而彼此获得,则称它们是同构的。p×qminor是一个包含p票和q候选人的配置文件。我们说一个剖面P包含一个子剖面Q,如果有一个P的子剖面同构于Q。一个受限域X可以由一组禁止子式来表征,如果存在一组子式Q,使得一个简档P属于X当且仅当它不包含Q中的子式;我们将集合Q称为X的禁止子式集合。2号提案[Lackner and Lackner,2017]一个受限的域可以由一组(可能是无限的)非线性子式来表征,当且仅当它是遗传的。有一些研究得很好的限制域,它们是根据禁止的子项来明确定义的。定义2.3. 对于j=1,2,3,我们说一个3乘3的子式Q是一个j-子式,如果在Q中每个候选者在第j个位置出现一次(注意,对于每个j=1,2,3,有几个j-子式不是成对同构的)。一个配置文件P是最佳/中等/最差限制,如果它不包含任何1-(分别为2-,3-)未成年人。我们说侧写是X VOTERK-PARTITION:输入:轮廓P。问:可以 P 被 分割成 k剖面P1,. . . ,Pk,使得对于每个i∈ [k],Pi在X中?3将选民分为两组本节的主要结果是下面的定理。定理3. 设X是一个限制整环,使得对于某个常数n ∈N,X可以由一个有限的禁止子式集Q来刻画,其中Q中的每个子式要么是2 × n-子式,要么是j-子式,其中j=1,2,3.然后X V OTER2-P ARTITION允许多项式时间算法。注意,定理3中的条件被第2节中定义的所有限制域所满足。因此,我们得到以下推论。推论1. 问题X V OTER2-P ARTITION在P中,对于X∈{SP,GS,BR,MR,WR,VR}。对于SP域,推论1回答了Er d'ly ietal的一个开放性问题。[2017]和J aeckl eetal. [2018]。素描证明。考虑一个满足定理陈述中的条件的域X,设Q是相应的禁止子式集。修正一个配置文件P。请注意,如果P包含投票v的多个副本,我们可以删除除一个副本之外的所有副本而不改变答案。因此,我们可以假设,P不包含两个相同的投票。此外,P中的投票顺序无关紧要。因此,从现在开始,我们将把P视为一组票。因此 , 我 们 的 目 标 是 决 定 我 们 是 否 可 以 将 P 划 分 为P=U<$V,使得U,V∈X。我们首先解释了i-子式,i=1,2,3,如何诱导一个par-将P分为三个子集。修复候选三元组T={a,b,c} ∈C且i∈ {1,2,3}。对于每个x∈T,设Pi是投票v∈P的集合,使得x出现在v中的第i个位置|T.我们说T对P是i危险的,如果Q包含值受限,如果它同时是最佳,中等,i小调和Pi我T、b我T、c- 是的我们的分析依赖于限制最严 我们将表示限制域,分别由BR、MR、WR和VR的最佳/中等/最差/值限制曲线组成。根据定义,域BR、MR、WR和VR中的每一个都可以由有限的禁用子式集来表征它有下面的lemma引理1. 设Q包含i-子式,i∈ [3].假设我们可以将P划分为P=U<$V,使得U,V∈X。那么对于每一个i-危险的三重T ={a,b,c}C,在最多一个候选者a∈T使得两个U∈P i兰蒂昂已经证明,域SP和GS也承认这样的特征;我们在下面给出它们,因为它们对于VP i/=保持。T,a我们的艰难和我们的安逸的结果。定理1. [Ballester和Haeringer,2011]剖面P是当且仅当它是最差限制且不包含证据 假设对于某个i-危险三元组T={a,b,c}有两个候选者a,b∈T使得Pi和Pi都与每个U有非空交集aB四个2 ×4未成年人中的任何一个,和V.存在一个集合W ∈ {U,V},其中Pi<$W- 是的但{a,d} ub uc,{c,d} vbva.定理2. [Ballester和Haeringer,2011]配置文件P在GS中,当且仅当它是中等限制的,并且不符合那么W包含一个禁止的i-子式,所以它不在X中。我们 开始 通过 检查, 为 每个 . m重三倍T={a,b,c}<$C,对于Q中的每个i-子式,保留2×4minor,集合Pi我T、bPi在X中。 注意,由于X可以是aubuc ud,b v dvavc.对于每个限制域X和正整数k,我们定义以下决策问题。特征在于一个有限的禁止子集合,并且Q中每个子的大小由一个常数限制,我们可以在多项式时间内检查给定的轮廓是否在X中。如果对于某个i-危险的三重T,且Q中的禁止i-小调至少有两个得双曲余切值.得双曲余切值.得双曲余切值.+v:mala2277获取更多论文T,xT,aT、bT,aT、bT、cT,aT、cT、bT、bT,xT、b∗T,xT,aT、bT,aT、bvT,aT、bvT、bT、cT、cT,aT、bT、cT,aT、bT、bT,a对于集合Pi,,x∈T,(比如,PiPi)不在X中,使得P是乌乌峰由Lemma1. 我们主张然后我们报告P是一个无实例;这个决定是正确的Lemma1. 在以后的日子里,每一个人,在三元组T={a,b,c}上的i-子式Q ∈ Q,我们假设a,b是可以满足的。实际上,对于每个v∈Pi,如果v ∈U,则设x v=T,如果v ∈ V,则设x v=F。考虑一个形式为xv的从句。如果不满足此条款,则必须是至多有一个集合Pi我T、bPi不在X中。我们如果v∈V。 但是我a,b只能包含此子句现在把我们的分析分成两种情况。如果存在u∈Pi使得u,v诱导2 ×π情形1:对任意i-危险三元组T∈A和X的任意禁止i-子式,Pi,x∈T中的恰有一个不在X. 在这种情况下,我们构造一个图G,P使得G是二部的当且仅当P是我们问题的是-实例。 我们定义图G的边集E如下。 给定两票u,v,使得(u,v)诱导a2× n禁止子式,我们把边{u,v}加到E上;我们把这种类型的边称为2×n-边。对于X的每个禁止i-子式和每个i-危险三元组T={a,b,c},如果如果存在u,w∈Pi<$V,使得u,v,w在Q中诱导一个j-子式,则无论哪种情况,我们都得到了与V∈X的矛盾.同样,对于以下形式如果不满足<$xv,则必须满足v∈U且U包含禁止子式。此外,对于不满足的子句(xuxv),必须是u,v∈U并且U包含禁止子式的情况。 事实上,上面描述的满足Ia,b.我T、c不属于X,则对于每对投票(u,v),相反,假设有一对{a,b} ≠T,iT,a,v∈Pi我们将边{u,v}添加到E;我们引用设(xv)v∈Pi,是一个令人满意的分配-将这种类型的边作为i-边。不难看出,G是二部的当且仅当P是我们问题的是实例;T、c然后,我们通过设置U=Pi,{v ∈ Pi:x∈=T},V=Pi{v∈Pi:x∈F}.我们详见附录B。T、c和vT、bT、c和v情形2:存在i-危险三元组T={a,b,c}<$C使得对于每个x∈T,集合Pi在X中。U和V在X中。实际上,考虑U,并假设它包含一个涉及投票u和v的2×n禁子式。因为Pi和Pi在X中,我们可以假设-在这种情况下,我们构建了三个2-SAT实例,并显示失去了u∈Pi的一般性,v∈Pi. 但在那个其中至少有一个是可满足的当且仅当P是肯定的我们的问题的例子。 回想一下,2-SAT的实例是由一组布尔变量给出的,这些布尔变量的值为情形Ia,b包含子句<$xv,所以我们必须有x<$=F,这是一个与v放在U中的矛盾。现在,假设U包含Q中的j-子式,j∈[3],涉及投票u,v和{T,F}和形式为xy的子句的集合,其中W. 由于PiPi在X中,我们可以假设没有x和y是(不一定不同的)文字(即,变量失去一般性,即(1)u,w∈Pi,v∈Pi或或变量的否定)。它是可满足的,如果我们可以分配i iT,aT、c值到所有变量以使得满足每个子句中的至少一个文字(即,取值T)。我们可以在多项式时间内决定给定的2-SAT实例是否可满足[Sipser,2013]。(2)w∈PT,a,u,v∈PT,c. 但在情况(1)中,Ia,b包含子句<$xv,所以我们必须有x<$=F,并且在情形(2)中,实例Ia,b包含子句<$xu<$xv,所以我们必须有x=F或x=F。在任何一种情况下,我们得到对于每一对候选者{a,b},我们构造一个2-u vSAT实例Ia,b可满足当且仅当P可为分割为V =U<$V使得U和V在X中,与U的构造方式相矛盾。我们的结论是U不包含被禁止的未成年人,因此它在X中;iT,a U和Pi1995年。为此,我们使用引理1。根据同样的论证,S2也在X中总结一下,我们的算法需要考虑O(m3)的配置文件,检查是否对于每个v∈P i,我们创建一个布尔变量x v;我们将xv=T解释为v∈U,将x v=F解释为v∈ V。我们创建以下子句:它们中的每一个都在X中,然后构造一个图并确定它是否是二分的,或者求解3个2-SAT实例因此,我们的算法在多项式时间内运行。• 对于每个v∈Pi,若存在u∈Pi使得u,v诱导出一个2×10的禁止小调,我们添加以下子句:第十节 类似地,如果存在u∈Pi,使得u,v诱导一个2×10的禁止小调,我们增加了第XV条。• 对于每个v∈P i ,如果存在u,w∈Pi使得第四,将选民分成至少三部分组他也是。 [2017]在SPVOTERk-PARTITION处的h它的减少是从k-u,v,w在Q中诱导出一个j-子式,对于j∈[3],我们把划分加入到CLIQUES中. 这个问题,这是众所周知的,子句<$xv;如果有u,w∈Pi使得u、v、w是NP完全的[Karp,1972],定义如下。引入一个被禁止的j-小调,我们增加了第XV条。• 对于每对投票u,v∈Pi如果有一个投票w∈T、c我使得u,v,w在Q中诱导j-子式,我们添加子句(xv),如果有投票w∈Pi等u,v,w在Q中诱导j-子式,我们添加子句(xuxv).k-P关节 进入CLIQUES:输入:图G=(VG,EG)。问题:我们能否将VG划分为k个集合,使得每个顶点集合在(VG,EG)上导出一个团。得双曲余切值.Pu∈PP+v:mala2277获取更多论文假设P可以划分为U<$V,使得U,V∈X. 我们知道T是i-危险的,存在a,b∈T下面我们证明VR VOTER k-PARTITION和GS VOTER k-PARTITION 也 是 NP 完 全 的 。 虽 然 我 们 的 证 明 也 从 k-PARTITION+v:mala2277获取更多论文我1ki在CLIQUES中,我们的论点完全不同:我们使用3×3m inor s,其中有Er de′ly ietal。 [2017]I'mnotsure. 我们的方法的优点是它也适用于VR域,其禁止的次要特征不使用2×4未成年人。我们首先考虑域BR、MR、WR和VR。然后我们解释为什么我们的证明方法也适用于GS域。对于我们考虑的每个域X,XVOTER k-PARTITION都是NP的,这是直接的,所以在下面的内容中,我们专注于NP-困难证明。定理4. 对于X∈ {BR,MR,WR,对于每个k ≥ 3,VR}是NP-完全的。证据给定一个图G=(V,E),我们首先创建一个图G′,使得G′包含k个大小为k+2的团,并且G′是k-CLIQUE PARTITION的是-实例当且仅当G是.对于每个i∈[k],设H i是一个具有顶点集U i的团,|U i|=k +2。为了构造图G′,我们将所有这些团的顶点连接到G的所有顶点。 也就是说,G′是顶点集V ′= V的图。. . K与边集E′=E<${{u,v}:u∈V,v∈i∈[k]U i}.如果V′,. . .,V′是G′划分为k个团,则每个首先观察到,如果我们有u r,us∈ V <$,对于某个ε∈ [k]且{u r,us}/∈E′,则V <$={u r,us}。实际上,如果V包含另一个顶点ut,其中tr,s,则v t将Tr,s中的备选项排列为cr,s a r,s b r,s,因此v r,v s,v t和Tr,s对于每个j = 1,2,3形成j -子式。因此,每个集合V要么是G′中的一个团,要么是一对顶点,它们之间没有边。我们现在将使用计数论证来排除后一种可能性。回想一下,每个不相交的集团H1,. . . ,Hk的大小为k +2。因此,根据鸽子洞原理,对于每个j∈[k]t,x都是这样的: |V (j )Hj|≥2。更具体地说,ifj/=j′then(j)=/(j′)。我发现,这是一个(j)=j′,且dc在满足V∈(j)的情况下。它包含至少四个不同的顶点,但它不是一个集团,因为Hj和Hj′之间没有任何区别,我们已经确定这是不可能的。因此,映射j<$→n(j)是一个双射。也就是说,每个集合V∈[k]包含来自同一团的两个顶点因此,没有这样的集合由两个顶点组成,这两个顶点是不一致的。连接,我们认为,在这种情况下,V必须是一个集团。这证明了我们的主张。现在我们将解释如何将定理4的证明扩展到群可分偏好。1KV′,i∈[k],限制到G是团或空集.相反,如果V1,. . .,Vk是G的一个划分为k个团的划分,则V ′,. . . ,V ′,其中V ′= Vi <$U i,是G′的k个划分.现在我们准备创建一个VRVOTERk的实例。分区 为方便起见,将G′的顶点重新编号为:定理5. GS VOTERk-PARTITION是NP-完全的,对每个k≥3。证据我们使用与证明Theo-rem4相同的归约。假设所得到的简档P可以被划分为k个简档Pi。. .,P,使得每个P是可分组的。 1千吨u1,. . . ,联合国。在我们的例子中,对于不形成G′的边的每对顶点,有三个候选,即,为每个{ui,uj}∈(V′×V′)\E′设Ti,j={ai,j,bi,j,ci,j}andd那么,特别地,每个Pt都在MR中,因此对应于G′中的团。相反,假设图G′可以划分为k个集团V,. . .,V,且令P,. . .得双曲余切值. 成为各自的1k1k让[C={ui,uj}∈(V′×V′)\E′Ti,J。P的分割 定理4的证明表明,每个 Pt不包含2-子式。因此,根据定理2,仍然需要论证每个Pt不包含2×4子式设P =(v,. . . 得双曲余切值.),其中n=|V′|. 每次投票,aubucud,bv 德乌夫 阿吉夫 C. 想对于1为了矛盾,对于某些t∈[k],轮廓Pt候选项的三元组根据其索引排序:如果i≠i=j且j i或R=i且r > j。ci,j和vjd被称为bi,jjci,jjai,j。假设V1,. . . ,Vk是G′的团划分. 我们主张,对于每个k∈[k],轮廓(vi) ui∈Vk在VR中(因此也在BR、MR和WR中),即,它不包含j-子式,其中j=1,2,3。事实上,对于三倍的选票u,v,w和三倍的候选人a,b,c,对于某些人来说,j=1,2,3,则对于某些{ur,us}∈(V′×V′)\E′且vr,vs∈ {u,v,w},{a,b,c}=Tr,s,这与V∈形成团是矛盾的.反之,设P1,. . . ,Pk是P到k个值受限的简档的划分(如果这些简档中的每一个在BR中,或者如果它们中的每一个在MR中,或者在WR中,则相同的论点起作用)。注意,对于每个k∈[k]和每个j=1,2,3,轮廓Pk不包含j-子式。我们将证明每个顶点集V∈={ui:vi∈P∈}在G′中形成一个团。+v:mala2277获取更多论文但是,P中的所有其他选民,包括v,都将a排在d之上,这是矛盾的。5毛毛虫的群可分性在这一节中,我们考虑了在卡特彼勒图上可分组的轮廓。毛毛虫是一棵二叉树,其中每个内部节点至少有一个子节点是叶子。 让 E是一条有m片叶子的毛虫,注意它有2m-1片叶子。顶点。 对于每个i = 1,. . . ,m-2,则树E恰好有一个叶子在深度i;我们将这个叶子记为ci,两个叶子在深度m−1记为cm−1和cm。 我们将通过(c1,. . . ,c m)。在下文中,给定这种形式的毛毛虫,将方便地表示候选集{c,. . . ,c j},其中1 ≤ i≤ j ≤ m,通过C[i,j]。+v:mala2277获取更多论文使用这个符号,我们可以说V在毛毛虫(c1,..上是群可 分 的 。 . . , c m ) 如 果 对 每 一 个 v∈V 和 每 一 个i∈[m−1],它保持c i<$vC[i+1 ,m]或C[i+1 ,m]<$vc i。 设CAT-GS表示所有群的轮廓的域,在毛毛虫上可以分开。下面两个命题的证明见附录C。3号提案轮廓P在履带(c1,c2,. . . ,c m)当且仅当对于每个v ∈ P,存在子集C′<$C使得C′<$vC\C′,且v对C ′中的候选项按指数的递增顺序排列,对C\C′中的候选项按指数的递减顺序排列.4号提案。C AT-GS在候选删除下关闭。回想一下,候选删除下的闭包对于域允许被禁止的未成年人的特征化(提案2)。识别算法CAT-GS域允许一个简单的识别算法.假设一个候选人在v中排名第一或最后,那么她正在为投票v进行极化;让π(v)表示投票v的极化候选集。给定一个轮廓P,该算法以m-2步进行。在每一步,它都在寻找一个对所有选票都两极分化的候选人如果找到这样的候选者,则将其从所有投票中移除如果没有找到这样的候选人,则算法报告P不属于CAT-GS。现在,假设算法成功了。重新标记候选项,使得在第j步识别的候选项被标记为cj,并且在算法终止后剩余的两个候选项被标记为cm-1和cm。则轮廓P在(c1,. . .,cm)。的该算法的正确性直接来自命题4。我们现在准备提出我们的小为基础的characterza- tion的CAT-GS。定理6. 一个轮廓P在毛毛虫上是可分组的,当且仅当(1)它是中等限制的,并且(2)它不包含由下式给出的四个2× 4禁止子式中的任何一个:au{b,c} ud和bv{a,d} vc。证据很容易看出,如果一个轮廓在履带上是可分组的,它满足条件(1)和(2);关于形式证明,见附录C。对于相反的方向,我们证明了如果我们的识别算法在P上失败,则P包含由条件(2)给出的禁止的2×4子式或 2- 子 式 。 假 设 我 们 的 识 别 算 法 在 第 j 步 失 败 ,j≤m−2,即,没有候选人在这一步是两极分化的所有选票。从现在开始我们考虑将P限制于其余候选人。考虑一个投票u,设a和b是该投票的两个极化候选人,因此π(u)={a,b}。我们知道存在某个投票v使得a/∈π(v)。如果b/∈π(v),即,π(v)={c,d}且{a,b}<${c,d}=π,则投票u,v和候选人a,b,c,d形成满足条件(2)的禁止2×4子式,我们完成了。因此,仍然需要考虑π(v)={b,c}的情况,对于某个c/∈{a,b}。在这种情况下,b对u和v都是极化的;因此,必须存在一个投票w使得b/∈π(w)。现在,如果π(w)={a,c},则投票u、v、w和候选a、b、c形成证明简档不是中等限制的并且因此不属于C_AT_GS的2因此存在一个候选d/∈{a,b,c}使得d∈π(w)。因此,它必须是这样的情况:(i)a/∈π(w)或(ii)c/∈π(w)。但是由于b/∈π(w),在情形(i)中我们有π(u)<$π(w)=<$,并且投票u,w和候选人π(u)<$π(w)形成禁止的2×4子式。类似地,在情形(ii)中,我们有π(v)<$π(w)=<$$>,并且投票v,w和候选人π(v)<$π(w)形成禁止的2×4子式。比较GS整环(定理2)和CAT-GS整环(定理6)的禁子集是很有趣的:当前者包含一个2×4mi-也不是,后者包含四个2×4的未成年人,每个都是通过在0、1或2原始未成年人给定这个基于minor的特征,我们可以应用定理3。推论2. C AT-GS V OTER2-P ARTITION在P中。然而,我们不能在证明中使用该参数-Orem4表明CAT-GS VOTER3-PARTITION是硬的对于k≥3。这是因为对应于输入图中的团的一组投票可能包含CAT-GS的2×4禁止子式我们提供了一个明确的例子,附录C(实施例1)。一个类似的问题出现,如果我们试图一个dthhhar dne spr ooofEr de'ly ietal. [2017]将SP结构域(其基于2×4子式)转化为C AT-GS结构域。事实上,我们不能排除GS-CAT VOTER k-PARTITION对于k >2是多项式时间可解的可能性;然而,似乎不可能使用定理3的证明技术来证明这一点。6结论和今后的方向我们的工作有助于结构化和近结构化偏好的研究。我们解决了一个悬而未决的问题。 [2017]通过示出在SPVOTER2-P ARTITION处的h在P中,并且提供了针对GS V OTE k-P ARTITION的复杂度分类。对于域CAT-GS,我们描述了一个简单的识别算法和特征这是算法的自然结果。这一特征意味着CAT-GS VOTER2-PARTITION也在P中.我们的工作提出的最直接的开放问题是 的 复杂CAT-GS V OTER k-PARTITION fork≥3。我们注意到,对于k ≥ 3,SC V OTER k-P ARTITION的复杂性也是开放的[Jaeckleet al. ,2018]。我们还可以探索其他关于群体亲密度的概念可 分 离 性 和 履 带 组 可 分 离 性 : 例 如 , 使 输 入 简 档(catcatering)组可分离所需的候选交换的最小数量;GS域的该问题的变体是NP完全的,其中接近度测量基于投票者/候选者删除[Brederecket al. ,2016]。稍微不同的方向是询问给定的简档P是否可以被分成两个子简档P1和P2,使得P1和P2属于两个不同的域:例如,因此P1是单峰的,而P2是可分组的;解决这种类型的问题可能需要新的证明技术。+v:mala2277获取更多论文引用[Ballester and Haeringer , 2011] Miguel A Ballester andGuillaume Haeringer.单峰域的一个特征. 社会选择与福利,36(2):305[Betzler et al. Nadja Betzler , Arkadii Slinko , and Jo-hannes Uhlmann.关于全比例表示的计算。Journal ofArtificial Intelligence Research,47:475[布莱克,1948]邓肯·布莱克。论群体决策的基本原理。Journal of Political Economy,56(1):23[Bredereck et al. Robert Bredereck , Jiehua Chen , andGerhard J Woeginger.单交叉域的一个刻画. 社会选择与福利,41(4):989[Bredereck et al. Robert Bredereck , Jiehua Chen , andGerhard J Woeginger.附近有没有结构很好的数学社会科学,79:61[Elkind和Lackner,2014] Edith Elkind和Martin Lackner。关于检测几乎结构化的偏好配置文件。在AAAI'14的会议记录[Elkind et al. ,2017] E. Elkind,M. Lackner,和D.彼得斯结构性优惠。 在us Endriss,《计算社会选择趋势》编辑。AI Access Foundation,2017年。[Er de'ly ietal. ,2017]G a'bo rEr de'lyi,MartinLac kn e r,and d Andreas Pfandler. 计算方面的近单峰选民。人工智能研究杂志,58:297[Faliszewski et al. Piotr Faliszewski , Alexander Kar-pov,and Svetlana Obraztsova.具有群体可分离偏好的选举问题的复杂性在IJCAI'21的论文集中,第203-209页,2021年[Inada,1964] Ken-ichi Inada.关于简单多数决定规则的一个注记。Econometrica,pages 525[Jaeckle et al. Florian Jaeckle , Dominik Peters 和 EdithElkind。关于识别几乎是单交叉的染色体。在AAAI'18会议记录[Karp,1972] Richard M Karp.组合问题的归约。计算机计算的复杂性,第85-103页。斯普林格,1972年。[Karpov,2019] Alexander Karpov.可分组偏好的数量。Group Decision and Negotiation,28(3):501[Lackner and Lackner , 2017] Marie-Louise Lackner andMartin Lackner.关于单峰偏好的可能性。社会选择与福利,48(4):717,2017。[Lakhani et al. Foram Lakhani , Dominik Peters 和 EdithElkind。相关的偏好和属性:几乎单一交叉的配置文件。在IJCAI[1971]詹姆斯·莫里斯。最优所得税理论探讨The Reviewof Economic Studies,38(2):175[Misra et al. Neeldhara Misra , Chinmay Sonar 和 PRVaidyanathan。关于几乎结构化轮廓的张伯伦-柯朗的复杂性。在ADT'17会议记录[Roberts,1977] Kevin Roberts.对所得税表进行表决。Journal of Public Economics , 8 ( 3 ) : 329- 340 ,1977.[1966] Amartya K Sen. A possibility theorem on majoritydecisions. Econometrica,pages 491[Sipser,2013] Michael Sipser. 计算理论导论。国际汤姆森出版社,2013年。+v:mala2277获取更多论文T、cT,aT、b T、cT、cT,xT,aT,aT、bT,x第2节省略的材料T={a,
下载后可阅读完整内容,剩余1页未读,立即下载
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/default.jpg!1)
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
我的内容管理 收起
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
会员权益专享
最新资源
- 藏经阁-应用多活技术白皮书-40.pdf
- 藏经阁-阿里云计算巢加速器:让优秀的软件生于云、长于云-90.pdf
- 藏经阁-玩转AIGC与应用部署-92.pdf
- 藏经阁-程序员面试宝典-193.pdf
- 藏经阁-Hologres 一站式实时数仓客户案例集-223.pdf
- 藏经阁-一站式结构化数据存储Tablestore实战手册-206.pdf
- 藏经阁-阿里云产品九月刊-223.pdf
- 藏经阁-2023云原生实战案例集-179.pdf
- 藏经阁-Nacos架构&原理-326.pdf
- ZTE电联中频一张网配置指导书
- 企业级数据治理之数据安全追溯
- MISRA-C 2012-中文翻译版.pdf
- 藏经阁-《多媒体行业质量成本优化及容灾方案白皮书》-37.pdf
- 藏经阁-浅谈阿里云通用产品线Serverless的小小演化史-23.pdf
- 藏经阁-冬季实战营第一期:从零到一上手玩转云服务器-44.pdf
- 藏经阁-云上自动化运维宝典-248.pdf
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)