人工智能268（2019）96计算一个小的可接受的不可分项集Pasin Manurangsia、Warut Suksompongba美国加州大学伯克利分校电气工程与计算机科学系b英国牛津大学计算机科学系Ar t i clei nf o ab st r a ct文章历史：2018年3月10日收到收到修订版，2018年8月12日接受，2018年在线发售2018年关键词：可分割不可分割项目资源配置社会选择我们研究的问题分配一个小子集的不可分项目的一组代理人因此，该子集对所有代理都是合意的，这意味着所有代理都将该子集视为至少和它的补充一样多。对于任意数量的代理商和项目，我们得出一个严格的最坏情况下的约束的项目，可能需要包括在这样一个集合的数量。然后，我们提出了多项式时间算法，找到一个合适的集，其大小匹配最坏情况下的界限时，有两个或三个代理。我们还表明，即使我们只能获得代理人对单个项目的偏好，也可以找到小的合意集。此外，我们调查的问题，有效地计算一个令人满意的集，其大小近似的最小令人满意的集的大小为任何给定的实例。 我们考虑两个著名的模型代表的代理商的偏好值的预言机模型和添加剂的实用程序，并建立紧边界的近似比，可以通过在多项式时间内运行的算法，在这些模型中的每一个。2018 Elsevier B.V.保留所有权利。1. 介绍典型的资源分配问题涉及在感兴趣的代理之间划分一组资源。 我们经常关注分配的效率，例如，实现高社会福利或确保没有其他分配会使每个代理人比当前分配更好。另一个重要问题是分配的公平性。为了考试-例如，我们可能希望最终的分配是没有嫉妒的，这意味着每个代理都认为她的包是最好的。分配中的所有包[23，55]，或成比例，这意味着每个代理至少获得她按比例公平的份额[51]。这类问题的一个共同特征是，一个代理人资源分配问题是人工智能研究的一个主要领域在这项工作中，我们研究的资源分配问题的一个变种，而不是对彼此的代理被坑，他们属于同一组。 我们将集体地将一个项目子集分配给这个组;我们的目标是使这个子集对所有代理都是“合意的”。 可接受性可以被认为是一个最小期望条件：虽然一个智能体可能能够找到她个人喜欢的其他项目子集，但当前子集仍然是她可以接受的，她可以同意将其分配给该组。换句话说，如果不满足某些条件，本文统一并扩展了第25届国际人工智能联合会议论文集[52]和第26届国际人工智能联合会议论文集[40]中出现的早期版本。特别地，定理5、10和11对于这个版本是新的，并且 定理4，6和7改进了早期版本中的相应结果这些增加导致3.3节和4.1节中的渐近紧界。电子邮件地址：warut. cs.ox.ac.uk（W.Suksompong）。https://doi.org/10.1016/j.artint.2018.10.0010004-3702/ 2018 Elsevier B. V.保留所有权利。目录可在ScienceDirect人工智能www.elsevier.com/locate/artintP. Manurangsi，W.Suksompong/人工智能268（2019）969722n≥ 3min， m+n，，m≠（定理1）m+©（log m），n为常数（定理4，5）22表1最小合意集的大小上界的总结，在第3节中给出。完全偏好顺序偏好n=2m]+1（定理1），m，+1（定理2）代理人，那么代理人将不满意，并试图离开集团。我们考虑一个基于无嫉妒的公平概念的同意概念：如果代理人喜欢它至少一样多，则项目的子集被称为对代理人是同意的。补集。在公平分配的背景下，考虑了竞争或其较小的变体，其中每个组由单个代理人组成[7，13，16]。例如，Brams等人[16]称该财产“价值至少50%”。一致性的一个吸引人的方面是，它可以定义为任意序数偏好，这构成了比加性基数效用函数表示的偏好大得多的偏好类别[5，15，17，39，53]。对于大多数人来说，在这项工作中，我们只假设智能体至少和它的任何子集一样多。由于在大多数资源分配设置中，代理可以简单地忽略项， 如果它们产生负值，则通常在不失一般性的情况下进行单调性假设作为我们的一致性概念的应用，可以想象，代理人一起去旅行，并达成一致或者从团队比赛中选择一部分物品作为奖品，一起赢。如果没有进一步的约束，到目前为止描述的问题将是微不足道的，因为我们可以简单地将整个项目集分配给代理。因此，我们施加一个约束，分配的子集应该尽可能小。这种对大小的限制在各种设置中是合理的，包括在两个给定的示例中。 事实上，在第一个例子中，行李箱的空间有限，而在第二个例子中，组织者可能希望将一些物品作为奖品留给失败的团队，也许这样分配对局外人来说似乎是公平的。 类似的基数约束已经在公平划分的上下文中考虑过[11]。在代理一起旅行的示例中，如果他们喜欢的东西不亚于家里留下的物品的补充子集，他们就可以接受。换句话说，根据选择了一套项目，每个代理人宁愿去旅行，而不是呆在家里。同样，对于将物品作为奖品的代理人，从团队竞争中，如果竞争是在两个团队之间进行的，并且某些项目的子集不符合某些代理的要求，获胜的团队，我们将有一个不希望的情况下，代理羡慕失败的团队，采取剩余的项目。虽然我们的研究是基于资源分配的框架，但同意也与社会选择理论和人工智能的其他领域有关。 特别是，人们可以考虑选择一组令人满意的项目，作为对从一组候选人中选出一个委员会，委员会的人数没有规定，但也许应该尽量减少。理论委员会选举提供了许多具体的方法来实例化同意的概念。例如，如果使用批准选举，其中每个代理都批准或不批准每个候选人，并且如果委员会包含至少有一个她认可的候选人，根据我们的概念，一个令人愉快的委员会对应于一个每个人都能接受的委员会。代理人在委员会中有一个批准的候选人。一般来说，代理人对各种委员会的偏好可以是相当复杂，委员会选举的几种变体在文献中进行了研究[6，50]。我们视工作作为一个起点，处理一个特别简单和自然的共识概念，我们希望这项工作将为研究可能适用于其他应用的不同概念奠定基础1.1. 我们的结果在这项工作中，我们开始研究资源分配的一致性。 首先，在第3节中，我们建立了最小合意集的大小的上界，无论是当算法可以访问代理的全部偏好时，还是当算法只能访问代理对单个项目的偏好时。此外，我们提出的算法，计算同意- 在这两种假设下，其大小与最坏情况界限相匹配的能力集。我们在本节中的结果总结在表1中。在3.1节中，我们推导出了一个严格的上限，即对于任何数量的主体和项目，可能需要包含在一个可接受的集合中的项目数量。值得注意的是，即使代理人可能有很大的不同，也许是冲突的偏好，我们可能需要选择的额外项目的数量，以适应所有这些是令人惊讶的小，即，每增加一个代理，就增加一半的物品（定理1）。我们的结果在一个非常弱的假设下成立，是单调的，这意味着一个代理人不会更糟，每当一个项目被添加到她的集合。有趣的是，这个结果我们利用Kneser在3.2节中，我们将注意力转向我们是否能够有效地计算出一个其大小与3.1节中给出的最坏情况界限相匹配的合意集的问题。 我们在两个和三个代理人的情况下回答了这个问题。为此，我们假设偏好是响应性的，这意味着当一个项目被添加到她的集合中或被另一个项目取代时，她不会更糟。虽然响应性强于单调性，但它仍然是可加性的推广，这是资源分配问题中关于偏好的一个非常常见的假设。我们提出了多项式时间算法，计算一个令人满意的子集，其大小匹配的上限时，有两个或三个代理（定理2和3）。98P. Manurangsi，W.Suksompong/人工智能268（2019）96++在3.3节中，我们假设算法只能访问智能体对单个项目而不是项目子集的顺序偏好。 这种类型的模型提供的优点是相关的算法通常易于实现并且代理人不需要放弃甚至确定他们的全部偏好;因此，这样的模型受到了广泛的关注[7，13，31]。然而，由于只有对单个项目的顺序偏好可供使用，在大多数情况下，该算法无法判断某个子集是否符合代理人的要求。然而，通过假设偏好响应，我们可以将对单个项目的偏好扩展到对子集的部分偏好。这使我们能够推断出，只要完全响应的偏好与对单个项目的排名一致，某些子集总是令人愉快的;我们称这样的子集为必然令人愉快的。用m表示项目的数量，我们使用离散的结果来显示，一个新的理论，对于任何常数数量的代理，存在一个大小为m/2O（ logm）的必然合意子集， 这样一个子集可以在多项式时间内找到（定理4）。此外，我们通过证明即使有三个代理人，也存在偏好，每个必然同意的子集的大小为m/2▲（ logm）（定理5）来建立这个界限的紧密性。接下来，在第4节中，我们研究了为任何给定实例计算近似最优大小的合意子集的问题，而不是其大小与具有相同数量的所有实例的最坏情况界限相匹配的子集代理人和物品。我们使用两个模型来解决这个问题，这些模型在文献中得到了很好的研究，并展示了计算效率高的算法，用于在每个模型中找到一个近似最优大小的一致集合。此外，在这两个模型中，我们证明了我们的近似比是渐近紧的。在第4.1节中，我们使用值预言模型来考虑一般偏好，其中代理的偏好由效用函数表示，并且允许算法查询任何代理对任何项目子集的效用。我们在此模型中给出了一个逼近比为O（ m/logm）的有效逼近算法（定理7）。 虽然这看起来并不令人印象深刻，特别是在观察到总是输出整个项目集的平凡算法已经达到了近似比O（ m）的情况下，我们表明我们的近似比实际上是我们所能希望的最好的。换句话说，不存在近似比为o（ m/logm）的多项式时间算法，即使只有一个代理（定理8）。在4.2节中，我们假设代理人的偏好由可加效用函数表示。可加性提供 简单性和表达性之间的合理权衡;在文献中，特别是在最近的工作中，通常假设[5，15，17，39，53]。我们证明了在加法赋值下，即使只有两个代理人，也很难判定是否存在一个包含恰好一半项目的合意集（定理9）。另一方面，使用覆盖整数规划的结果，我们证明了存在一个O（logn）-近似算法计算的最小尺寸的一致集（定理13）。此外，我们证明了这个近似因子是紧的：对于任何常数δ >0，将问题近似到（1−δ） lnn的因子内是NP-困难的（定理12）。1.2. 相关工作虽然资源分配和公平分配在人工智能文献中已经得到了广泛的研究[7，11，13 Skowron等人。[50]研究了一个类似的设置，其中一组代理人共同决定一组共同的项目。 在他们的工作中，可以选择的项目的数量是固定的，代理人努力在该约束下最大化其效用，而在我们的工作中，项目的数量是可变的，但应该最小化，并且对所选择的集合设置了一个一致的约束。最近受到关注的一个相关问题是将物品公平地分配给代理人组;该问题在不可分割物品[39，48，53，54]和可分割物品[46，47]的背景下进行了研究。就像我们的作品，被视为每个组内的公共物品--一个组的所有成员都从分配给该组的物品中获得充分的效用。然而，与我们的工作不同的是，上面提到的所有工作都假设有多个组，并且整个资源都应该分配给这些组。在我们的工作的早期版本出版后[40，52]，Gourvès [25] 研究的附加假设下，该集必须满足拟阵约束的合意集除了关于资源分配和公平分配的文献外，与我们相关的另一项工作是组合投票[1，34，56]。组合投票的一个典型例子是要求选民对某组问题做出决定，他们对各种问题结果的偏好是依赖的。例如，一个选民可能会单独支持每一项提议的政策，但认为如果所有的政策都是 有待落实。组合投票可以在我们的资源分配设置中框定，分配的项目对应于正在投票的问题。对组合投票的几个方面进行了研究，包括不同投票规则的通信和计算成本、实现方法以及投票者的策略行为。2. 预赛我们考虑n个代理，编号为1，2，.，n，将被共同分配集合S= {x1，x2，.，xm}个不可分项。用S表示S的所有子集的集合。每个智能体i被赋予一个偏好关系i，一个在S上自反的、完全的和传递的序。令>i表示关系i的严格部分，而i表示关系i的无差别部分。对于x和y项，我们有时会滥用符号，将x y写成{x}{y}。P. Manurangsi，W.Suksompong/人工智能268（2019）9699\S联系我们⊆∅=∪=+≥≤：S→S{\displaystyle{\ frac{}≥在本文中，我们假设偏好是单调的，即，当一个物品被添加到她身上时，集单调性在很多情况下都是一个自然的假设。特别是，它意味着免费处理项目-每 项被认为对每个代理具有非负值定义1. 的偏好S是单调的，如果T<${x}T代表所有的T。注意，如果xT，那么TxT总是成立，所以我们只需要检查当xS T.我们现在准备好定义本文的中心概念定义2. 一个子集TS被称为对代理i是合意的，如果TiS\T。当所考虑的主体的集合从上下文中看得很清楚时，我们有时会把所有主体都同意的集合简单地称为同意集合。由于偏好是单调的，所以整个集合S对每个代理都是合意的，所以对于任何数量的代理，合意的集合总是存在的。1对一个主体的偏好也意味着该主体并不严格偏好当前集合的任何子集也就是说，我们对任何U S T都有Ti U。我们将考虑的偏好的另一个属性是响应性，它说的是，当一个项目被添加到她的集合中或被另一个项目取代时，她不会变得更糟。 虽然比单调性更强，但在许多情况下，响应性仍然是一个合理的假设2定义3. 对S的偏好是响应性的，如果它满足以下两个条件：• 是单调的• （T\{y}）∈{x}T对于所有T∈S和x，y∈S，使得txy，x∈/T和y∈T.如果我们可以访问代理的完整偏好，我们可以简单地检查代理是否同意子集通过与它的互补物进行比较。然而，当我们只能访问智能体对单个项目的偏好时，大多数我们无法判断给定子集是否令人满意的时间。然而，如果我们假设代理人的偏好是响应性的，我们有时可以推断出某个子集是同意的，只有通过观察代理人对单个 项目.下面的定义抓住了这种直觉。一般来说，我们使用表示对…的偏爱和唱表示对S.定义4. 固定偏好唱 在S.一个子集TS被认为是必然符合关于如果T S\T对S的任何响应偏好与sing一致，则sing。为了简洁起见，我们说，一个子集的项目是必然同意的代理，如果它是必然同意关于代理商对单个项目的偏好我们现在建立一个与模型的连接，在这个模型中，每个智能体对每个项目子集都有一个基数效用。效用函数u是一个将任何项目子集映射到非负实数的函数。由于每个代理人S，我们有T1iT2当且仅当u i（T1）ui（T2）.此外，由于我们考虑单调偏好，我们有ui（T1）ui（T2）对于任何T1 T2.我们假设u i（）0为所有i。一个效用函数u被称为可加的，如果u（T1T2）u（T1）u（T2），如果u（T1T2）u（T1）u（T2），则对任意不相交子集T1，T2都是次可加的.任何单调可加函数也是次可加的。次可加效用函数在文献中得到了广泛的研究[10，21]。当代理人的偏好由次可加效用函数给出时，代理人认为是合意的子集。 也给代理人的效用至少一半的代理人的效用的确，对于任何合适的子集T，我们有f（S）=f（T（S\T））≤f（T）+f（S\T）≤2f（T），这意味着f（T）f（S）/2。因此，当代理人在本节的最后，我们给出了必然一致子集的特征，这将被多次使用 在报纸上。Aziz et al. [7]和Brams et al. [16]也有类似的说法，尽管我们在处理关系时的处理略有不同。1 如果偏好不是单调的，则可能不存在合意的集合，例如，如果有两个具有严格偏好的智能体，其中一个智能体2 对于一个全面的治疗属性有关的排名的对象集，我们指的是一项调查Barberà等人。[9]。100P. Manurangsi，W.Suksompong/人工智能268（2019）962提案1. 固定偏好唱S中的单个项目，X1唱x2唱···Singxm.设T为S，定义I k= {x1，x2，.，x k}，对于所有k= 1，2，.，M.如果|I kt |≥ k/2，对于所有k = 1，2，.，m，则T对于唱歌很严格。唱 . 如果偏好证据首先假设，|I kt|≥k/2，对于所有k= 1，2，.，M.以来|我很抱歉|≥m/2，我们有|不|≥|科技|.设TrT是由|科技|最小指数的T项。定义一个双射函数f：Tr→S\T如下：给定项xk∈T，其最小指数f（xk）不为然而，我们定义f（ xk）为S\T中具有最小索引的项，该索引未出现在 F 迄今以来|I kt|≥k/2，对于所有k= 1，2，.，m，函数f将每个项xk映射到另一项xl，其中l> k。反应性的定义意味着，对于任何与sing一致的对S的反应性偏好，它认为TrS\T。因为任何 反应偏好也是单调的，我们有TS\T，这意味着T 就...而言，唱歌反之，假设偏好是 是严格的，|我不知道|0是一个小常数，并假设偏好由一个附加效用函数u给出，使得：• u（xi）=1+（l−i）<$，其中1≤i≤l;• u（xi）=（m-i）<$对于li≤m。<因为任何可以用加性效用函数表示的偏好都是响应性的，所以它是响应性的。而且我们 有u（ S\T）> l/2，而u（ T）l/2，当<$足够小时。由此可见，对S的反应偏好与sing一致，使得S\T>T。因此，T就歌唱而言不一定是令人愉快的。□最后，本文中任何无底对数都假定以2为3. 最坏情况界限在本节中，我们将建立最小合意集大小的上界，代理的全部偏好，以及当算法只能访问代理对单个项目的偏好时。此外，我们提出的算法，计算令人满意的集，其大小匹配的最坏情况下的边界在这两个假设。3.1. 一般最坏情况界我们开始我们的研究，通过推导出一个严格的最坏情况下的项目的数量，可能需要包括在这样的集合中，用于任意数量的项目和对项目具有任意偏好的任意数量的代理。即使使用单个代理，也已经存在一个偏好，我们需要包括至少一半的项目，例如， 一种偏好，由一个附加效用函数表示，它给每一个项目都提供了相同的正效用。 有鉴于此，当有几个代理人，可能有各种各样的偏好时，似乎没有希望获得一个小的令人满意的集合。尽管如此，我们表明，我们需要包括以适应额外的代理的额外项目的数量是令人惊讶的小，即使在最坏的情况下，这个数字是每个额外的代理只有半个项目定理1.对于任意数量的代理和项目，存在子集T∈S，使得|≤ min .，|≤ min., m + n，，m所有探员都能接受。更重要的是，对于我所拥有的一切来说，这是一个非常重要的问题。，m+2n，，m是紧的。定理1可以被看作是共识减半的离散版本，其目标是将蛋糕或土地等可分割的物品分成两部分，所有代理人都认为价值完全相同。有趣的是，一个共识减半分区可以找到任何数量的代理[2，49]。 由此可见，我们可以找到一部分物品，它最多是物品的一半，但所有代理人都认为它至少值物品的一半（特别是，我们选择共识减半分区中两部分中较小的一部分）。然而，当项目不可分割时，可能不再可能选择包含最多一半的项目，使所有代理人认为这一套是值得至少一样多，其补充。如果有，只有一个项目，并且所有代理都肯定地评价该项目，则该项目必须包括在集合中。 定理1给出了在最坏情况下需要包含多少附加项的精确界限我们首先给出了定理1的两个代理人的情况下的直接证明;我们的一般情况下的证明将依赖于一个组合的结果。P. Manurangsi，W.Suksompong/人工智能268（2019）96101□...{}.=联系我们\{}不{}不{ }\{}联系我们联系我们>\∈\∈{}\\{}\联系我们- -m+22=+当n=2时，定理1的直接证明。这两个词的第一和第二个词都是由一个词和一个词组成的。我们的桌子最多存在一组大小这是双方都同意的;结合的紧密性遵循相同的就像我们对定理1的证明一样，对于任何数量的代理人。假设m=2k+1是奇数。假设矛盾，没有一个子集的大小最多k+1是同意的两个代理。设T是这样的，|不|=k。我们首先证明以下主张。假设：如果T>1S\T，则（T<${x}）\{xr}>1（（S\T）\{x}）<${xr}对任意x∈S\T和xr∈T.假设T>1S\T，x∈S\T，且xr∈T。从单调性可以得出T∈{x}>1（S\T）\{x}。 由于没有一个大小为k +1的子集对两个智能体都是一致的，所以我们有（S\T）\{x}>2T\{x}。再次通过单调性，我们有（（S\T）\{x}）<${xr}>2（T<${x}）\{xr}.再次使用大小为k+1的子集对两个代理都不满意的假设，可以得出以下结论：（T<${x}）\{xr}>1（（S\T）\{x}）<${xr}，我们的主张得到了证实我们现在用我们的主张来获得所希望的矛盾。 在不失一般性的情况下，假设{x1，x2，...，x k}>1{x k+1，x k+2，...，x2k+1}。反复应用我们的主张，在两个集合之间移动项目，我们发现，{xk+1，x2，. ，xk}> 1{x1，xk+2，.， x2k+1}，{xk+1，xk+2，x3，. ，xk}> 1{x1，x2，xk+3，.， x2k+1}，直到最后，{xk+1，xk+2，...， x2 k}> 1{x1，x2，. ，xk，x2k +1}。通过单调性，我们有{x k+1，x k+2，...，x2 k+1}>1{x1，x2，.，x k}，这与我们的假设{x1，x2，...，x k}>1{x k+1，x k+2，...， x2 k+1}。现在假设m=2k是偶数。令Sr是S中除x1以外的所有项的集合。我们从m是奇数的例子中知道存在一个大小至多为k的子集T∈Sr，使得T1Sr\T和T2Sr\T。由于偏好是单调的，我们有T<${x1}1Sr\T和T<${x1}2Sr\T。这意味着大小至多为k + 1的集合T{x1}是我们想要的子集，完成了证明。 □这并不是说这种方法可以产生一种多正常时间的成本，以便更好地实现更大的规模m+22双方都同意的假设m2 K1是奇数;m是偶数的情况可以类似地处理。设TS是大小为k的任意子集。 如果S T1T和S T2T，我们完成了。否则，不失一般性地假设，不1S T，任意选择xS T和XRT. 如在索赔证明中，如果TX2（S T）x，或者如果（S T）x2不X和（（S T）（x）XR1（T x）xr，我们完成了。 因此，我们可以假设，在索赔的结论，（T x）xr1（（S T）（x）西河这意味着我们可以通过在两个元素之间反复移动元素来找到一个令人满意的子集。这两个集合是证明的延续。由于我们需要移动元素最多k次，因此我们的算法在多项式时间内运行。我们现在转到一般情况。如前所述，我们对定理的证明依赖于下面的组合结果，这是最有名的Kneser猜想。图的色数定义为给图的顶点着色所需的最小颜色数，使得没有两个相邻的顶点共享相同的颜色。引理1（Kneser猜想）。设G是具有集合1，2，.的所有k元子集的无向图，n作为顶点，使得两个顶点之间存在边当且仅当对应的集合不相交。G的色数由下式给出：χ（G） n−2k+ 2，若n≥ 2k;1否则。引理的陈述是由于Kneser [30]，他在1955年德国数学杂志的问题专栏中提出了它作为一个猜想。尽管陈述很简单，但直到1978年，这个猜想才首次得到解决。[37]用拓扑方法。这个证明后来由Bárány [8]和Greene [26]在Matoušek之前进行了简化[41]在2004年给出了第一个纯组合证明。Lovász的猜想证明，利用Borsuk-Ulam定理，标志着第一次从代数拓扑的方法被用来解决组合问题，并给出了上升到拓扑组合学领域有了引理1，我们就可以建立定理了。102P. Manurangsi，W.Suksompong/人工智能268（2019）96\\22...--\−⊆\==/==−=•联系我们{}−= ≥=22toagentnmustcontaina，tleasth，alf，oftheeit，ems，xn，x，n+1，. ，xm。让一个替代品对所有长时间记忆都是可接受的图1. 定理1证明中n = 2，m = 5时的图G，也称为Petersen图。具有标签{i，j}的顶点对应于集合{xi，xj}。Theorem 1. L etkm+2n -是的 如果km，则所有元素的集合S具有min（k，m）的大小，并且由于偏好是单调的，因此对于所有元素都是可接受的。从现在开始假设k iS\T1和T2>iS\T2.由于T1和T2是不相交的，我们有T1<$S\T2和T2<$S\T1。单调性意味着S\T 1i T 2>i S\T 2iT1>i S\ T1，矛盾这意味着我们总是可以找到一个大小为k的子集，它对所有代理都是合适的最后，我们证明了存在单调偏好，其中界min（k， m）是紧的。 事实上，我们甚至可以选择由附加效用函数表示的偏好我们考虑两种情况。n M. min（k，m）M. 因为我 一，二，n，让代理i的偏好由可加效用函数u给出，使得u（xmin（i，m））1和u（x j）0对于所有jmin（i，m）。那么任何对代理i有利的子集都必须包含项xmin（i，m）。因此，一个子集，是同意所有代理人必须包含所有m个项目。• <嗯。则min（k，m）=k。对于i= 1，2，...，n-1，让代理i的偏好由可加效用函数u使得u（xi）=1且u（xi）=0，对于所有ji =i。设代理人n的偏好由一个可加效用函数u给出使得对于j ∈ {n，n +1，.，m}，否则u（x，j）= 0。对于i = 1，2，...，n-1，任何同意代理i的 子 集 必须包含项目x i。此外，任何同意的子集大小至少为n−1+这就完成了证明。 □m−n+1 =m+n−1=m+2nk，如所愿。3.2. 匹配最坏情况界限定理1给了我们一个严格的最坏情况下的大小上的最小的同意集的任何数量的代理和项目。然而，它的证明并没有给出一个方法来获得一个这样大小的集合。 由于我们必须考虑的集合数量是项目数量的指数，因此即使对于中等数量的项目，暴力搜索也是不可行的。我们本节的目的是表明，当有两个或三个具有响应偏好的代理时，实际上可以计算出一个令人满意的集合，其大小在多项式时间内与最坏情况的界限相匹配。这意味着我们可以计算即使项目的数量很大，也可以这样设置P. Manurangsi，W.Suksompong/人工智能268（2019）96103...12−，...232 k2计算这样的子集T的算法。12122122当宇宙被认为是S时。12121112221对于sing和sing都必须一致的T_S必须至少包含m+2=k+1个项，因为1当我们讨论算法时，一个重要的问题是我们如何表示代理的偏好。 由于子集上的偏好与单个项目上的偏好不同，可能没有简洁的表示，因此不可能设计算法如果算法需要读取整个偏好，则其在项目数量中以时间多项式运行。规避对于这个问题，我们在本节中假设偏好是响应性的;这允许我们将对单个项目的偏好扩展到对子集的部分偏好。我们的算法，两个代理将只利用单一项目的偏好，并计算一个必然同意的子集。3另一方面，我们的三个代理的算法除了利用单个项目的偏好外，还将通过偏好预言机查询代理我们首先处理两个代理人的案件定理2. 假设有两个具有偏好的智能体唱歌和在S.存在一个子集T∈ S12使得|不|≤，m+2，并且T对于sing和sing都必然是一致的。此外，存在多项式时间此外，对于m + 2 2为紧边界的S中的单个项，其收敛性也很强.证据首先假设m = 2 k +1是奇数，并且不失一般性地假设x1singx2sing···singx2 k+1。我们我们选择T，m+2，2，=k+1，它如下：1. 选择x1。1 1 12. 在k对项目（x2，x3），（x4，x5），.，（x2 k，x2 k+1），根 据 下 列 条 件 选择首选项新新监狱2. 如果2在任何一对项目之间都是无关紧要的，从这对项目中选择任意一个项目对于任意j=1，2，.，m，我们的集合T至少包含j个项目x1，x2，.，xj;由命题1，T就sing而言必然是合意的。此外，由于我们选择的项目，是首选根据唱从每一个集合{x2，x3}，{x4，x5}，.，{x2 k，x2 k+1}和x1一起，命题1意味着T也必然与关于唱歌因此，T对于sing和sing都必然是合意的。现在假设m=2k是偶数。令Sr=S\{x1}。我们从m是奇数的情况下应用该算法来选择a一个大小为k的集合T∈Sr，它必然与唱 和唱 当所考虑的宇宙是Sr时。12因此，T{x1}是一个大小为m+2=k+1的子集，它必然与两个唱就唱此外，我们还表明，保留是对单个元素的保留，m+22很紧如果m=2k+1是奇数，且偏好sing是严格的，则根据命题1，任何子集，μstalreadycontainatleast，m+22，=k+1items.最后，假设m=2k是偶数，令唱 和唱 使得x1>singx2>sing···>singx2k且x2k>singx2 k−1>sing ···>唱歌 x1. 根据命题1，任何子集 TS 这是必然同意的，唱 必须独自包含至少k个项目，其中一个是x1。如果T正好包含k个元素，那么它正好包含k1项目之间X X x. 命题1意味着这样一个集合T不一定与sing一致。 因此，任何子集需要的话 □12 2在高层次上，定理2中的算法与Pruhs和Woeginger [ 44 ]提出的“特朗普规则”相似， 像我们的算法一样，特朗普规则 作为对两个代理的单个项目的偏好的输入。使用我们的术语，该规则是保证产生一个分配的属性，每个代理认为她的束是必要的同意，只要这样的分配存在。特朗普规则和我们的算法之间的区别在于，特朗普规则将项目划分为两个子集，每个代理都取一个子集，而我们的算法只产生两个代理共享的一个子集观察到在两个代理人的情况下，最小必然合意集的大小的上界（定理2）与最小合意集的大小的界（定理1）一致。这有点令人惊讶，因为必然合意集合的定义只涉及对单个项目的偏好，而即使我们可以获得全部偏好，最坏情况的界限也保持不变。下面的示例显示，同一语句不再当有三个代理人时，保持不变3 如果我们不假设响应性，仍然存在两个代理的多项式时间算法，该算法通过偏好预言发现代理104P. Manurangsi，W.Suksompong/人工智能268（2019）96...\...−·=•\−1•{}\\11112222233333m+23例1. 设m = 6，并假设三个代理人对单个项目的偏好如下：1. x1>唱x4>唱x5>唱x6>唱x2>唱x3;2. x2>singx5>singx6>singx4>singx3>singx1;3. x3>唱x6>唱x4>唱x5>唱x1>唱x2。在例1中，任何一个子集，只要是三个主体都同意的，就必须包含x1，x2，x3，因为它们中的每一个都被某个主体排在第一位。此外，只选择x4，x5，x6中的一个并不能为将该项目排在第四位的代理人产生一个必然令人满意的集合。因此，一个必然令人满意的集合必须包含至少五个项目。另一方面，如果我们能够访问任何一个参与者的全部资料，则理论1表明，我们可以确定大小6+23 =4，所有代理都可接受。因此，当有三个代理时，要计算一个大小与最坏情况界限匹配的合意集，只考虑单个项目的偏好是不够的。然而，如果算法可以访问代理的全部偏好，则可以在多项式时间内找到这样的子集。为了访问偏好，允许算法对偏好oracle进行多项式数量的查询。在每个查询中，该算法可以指定一个代理和两个子集的项目的偏好预言，和预言揭示了这两个子集之间的代理的偏好第三章. 假设R是S上的第三个代理，具有R，Sponsi，V，1，2和3。时间是多项式时间一种计算子集T ∈ S的算法，|不|≤而T对这三个代理人都很满意P roof. 假设m=2k的条件t是evenn。我们的目标是找到一个大小合适的子系统m+23=k+1，这对所有第三方代理都是可接受的。不失一般性地假设x2k-1是根据1的最优选项目，x2k是根据2的除x2k-1之外的最优选项目，并且在剩余的2k- 2个项目中，偏好1将它们排序为x11X21···1x2k−2。设A ={x1，x2，...， x2 k−2}，并考虑对（x1，x2），（x3，x4），.， （x2 k−3，x2 k−2）。设B是一个k-1个项目的集合，每个项目都包含一个项目，根据2，该项目对中的另一个项目不优选。如果2在任何一对项目之间是无关紧要的，我们可以任意选择。响应性意味着A\B2B。只要A\B2B，我们就从B中删除一个原来也在B中的元素，并将其对中的另一个元素插入B中。我们最终必须到达一个点，最迟在k-1移动之后，B2A\B我们考虑两种情况。• 我们还没有采取任何行动。通过定义B，我们有B2A\B和A\B2B，因此A\B=2B。由于偏好是单调的，因此（A\B）<${x2k}2B和B<${x2k}2A\B。• 我们至少走了一步。在不失一般性的情况下，假设在我们的最后一步中，我们将x2i-1插入B并从B中移除x2i。设C=（A\（B<${x2i}））<${x2i−1}且D=（B\{x2i−1}）<${x2i}，即，C和D分别是最后一步之前的集合A\B和B。我们有C>2D和B2A\B，从单调性可以得出C<${x2k}2D和B<${x2k}2A\B。我们认为D<${x2k}2C和（A\B）<${x2k}2B中至少有一个成立.假设C>2D<${x2k}和B>2（A\B）<${x2k}是矛盾的。响应性意味着，C>2D<${x2k}2B>2（A\B）<${x2k}2C，矛盾因此，如所要求的，D<${x2k}2C和（A\B）<${x2k}2B在这两种情况下，我们都可以在多项式时间内找到一个大小为k−1的子集EA，其中包含每个对中的一个项（x1，x2），（x3，x4），...，（x2 k−3，x2 k−2）使得E<${x2 k}2A\E和（A\E）<${x2k}2E.我们现在选择大小为k+1的合适集合如下：1. 同时选择x2k1和x2k。2. 选择E或A E根据该设定剂3优选。(If代理人3在两组之间是无差别的，选择其中一个是任意的）。我们声称我们所选择的集合T对所有三个主体都是合意的我们为每个代理人分别证明索赔对于任何j1，2，...，m，布景 不 含有至少 J/2 的 J 根据1.由于1是响应的，命题1意味着T必然同意主体1。由于Ex2 k2A E 且A Ex2k2E，且T包含E或A E以及x2k1和x2k，则T对代理2是合意的.由于我们选择了代理3更喜欢的集合E或AE，并且我们包括了剩余的项目x2k1和x2k，所以T对代理3来说是P. Manurangsi，W.Suksompong/人工智能268（2019）96105......++..I=pQ.Q因此，正如所声称的那样，T对所有三个主体都是合意的。这就结束了对m为偶数的情况的分析最后，假设m=2k+1是奇数。我们的目标是找到一个大小合适的子系统m+23=k+2，这是所有第三方代理都可接受的。令Sr=S\{x1}。 我们从m是偶数的情况应用该算法来选择大小为k + 1的集合T∈Sr，当所考虑的宇宙是Sr时，对所有三个代理人都是满意的。由
我的内容管理
展开
