在享乐多样性博弈(HDG)中，有两种类型的代理(红色和蓝色代理)需要形成不联合的联盟，即代理的子群体。每个主体对联盟的偏好取决于其联盟中相同类型主体的相对数量。在二分类享乐多样性博弈(DHDG)的特殊情况下，每个agent只区分批准和不批准的分数。我们的目标是稳定的结果，对抗代理人的偏差，以及最大化社会福利的结果。特别是，我们表明，即使在只有三个代理的情况下，DHDG的严格核心可能是空的，而每个具有两个代理的HDG都有一个非空的严格核心。我们还提供了dhdg关于每个试剂批准的分数数量的几个计算复杂性结果。例如，我们证明，即使每个代理最多批准三个分数，确定DHDG是否具有非空严格核心也是\( extsf {NP}\)完全的。此外，我们表明，即使在每个代理只有两个批准分数的限制设置中，确定DHDG是否承认纳什稳定结果也是\( extsf {NP}\)完全的，从而改进了文献中的结果。对于社会福利最大化的任务，我们应用了投票理论中的批准分数和博尔达分数。对于dhdg和批准分数，我们在多项式可解和\( extsf {NP}\)完备的情况下，相对于每个代理的批准分数的固定数量，画了一条明显的分隔线。我们用Borda分数下HDGs的\( extsf {NP}\)完备性结果来补充这些发现。
在享乐多样性博弈(HDG)中，有两种类型的代理(红色和蓝色代理)需要形成不联合的联盟，即代理的子群体。每个主体对联盟的偏好只取决于其联盟中相同类型主体的相对数量。快乐博弈的一个重要子类是所谓的面包师和米勒博弈(Aziz等人[3]和Bredereck等人[13])，其中每个红色代理(面包师)都希望所在的联盟中蓝色代理(磨坊主)的比例尽可能大，每个蓝色代理(磨坊主)都希望所在的联盟中红色代理(面包师)的比例尽可能大。对于HDG的另一个例子，考虑两个学术部门(比如R和B)合并为一个的情况:虽然R的一些成员(红色代理人)渴望与他们的新同事，即B的成员(蓝色代理人)密切合作，但其他人可能不愿意这样做，而更愿意与他们习惯合作的R的其他成员一起进行下一个项目;因此，一些红色特工可能更喜欢在他们的联盟中有高比例的蓝色特工，而另一些人则喜欢低比例的蓝色特工。类似地，在他们的联盟中，一些蓝色特工更喜欢红色特工的相对数量较多，而另一些则相反。类似的可持续发展目标应用也出现在学生群体的形成(例如，在本地和交换生之间)和国际合作中(见Bredereck等人[13])。
因此，我们关注的是一个联盟形成问题，其目标将是一个合理的结果，即将代理划分为不相交的联盟。在这方面，我们考虑到两种解决方案概念。一方面，我们考虑了处理代理偏离稳定性的概念:在这里，我们重点关注纳什稳定的概念，这是一个著名的关于个体偏离稳定性的概念，以及严格核心稳定的概念，这是关于群体偏离稳定性的概念。另一方面，通过调整投票理论中的得分，我们的目标是使诱导的社会福利最大化的结果(即得分总和)。在这项工作中，我们特别关注二分享乐多样性博弈(DHDG)的设置，这是DHDG的特殊情况，其中每个代理都以二元方式通过仅区分“好”部分(即她赞成的部分)和“坏”部分(即她不赞成的部分)来陈述她的偏好。
在本文中，我们证明了决定DHDG是否承认纳什稳定结果是不完全的，即使每个代理只批准两个分数(另见表1)。因此，我们改进了文献中的结果。此外，我们证明了对于具有两个代理的实例，hdg的严格核总是非空的，因此DHDG的严格核也总是非空的，而对于任何数目的DHDG，即使每个代理只批准一个分数，也存在一个具有n个代理的DHDG的严格核为空的实例。接下来，我们证明了即使每个代理只批准三个分数，DHDG是否允许非空严格核心的相应决策问题是不完全的。从投票理论中调整分数，然后我们的目标是最大化社会福利的结果(另见表2)。在这方面，对于批准分数，我们在每个代理的批准分数的固定数量的多项式可解和非完全情况之间划一条明确的分界线:当每个代理只批准一个分数时，通过对双约束背包问题的非琐细简化，我们表明可以在多项式时间内找到最大化社会福利的结果;一旦智能体可以批准更多的分数，相应的决策问题就会变得完全——更准确地说，我们证明了-完备性对于每个智能体批准的任何固定数量的分数都成立。最后，我们证明了在Borda分数下最大化社会福利在计算上是困难的。
享乐多样性游戏。关于享乐多样性游戏的文献是最近才出现的。由Bredereck等人[13]提出，可持续发展目标中考虑的主要解决方案概念是针对个体或群体偏差的稳定性，如纳什稳定性、个体稳定性和核心稳定性。对于单峰偏好的特殊情况，Bredereck等[13]表明纳什稳定的结果可能不存在，而个体稳定的结果总是存在的，并且可以在多项式时间内找到。他们还表明，即使每个代理的偏好都是单峰的，核心也可能是空的，并证明一般来说，决定HDG是否承认非空的核心是一个完全的问题。在后续的论文中，Boehmer和Elkind[9]通过考虑纳什稳定性和个体稳定性，重点研究了抗个体偏差的稳定性。他们推广了Bredereck等人[13]先前的结果，表明在任何HDG中都保证存在单个稳定的结果，并且可以在多项式时间内找到这样的结果。在消极方面，Boehmer和Elkind[9]表明，即使每种药物最多批准4个分数，它是否完全确实决定了dhdg -从而hdg -是否承认纳什稳定的结果。在这项工作中，我们锐化了这一结果，并朝着计算复杂度二分法的方向迈出了一步:我们表明，即使在每个代理最多批准2个分数的限制设置中，DHDG是否承认纳什稳定结果的决策问题也是不完整的。更一般地说，我们证明了对于任何固定的数字，即使每个智能体恰好(或最多)同意s个分数，相应的决策问题也是-完整的。
谈到对抗群体偏差的稳定性，我们知道，与hdg相比，每个DHDG都有一个非空的核心(这一观察结果来自于二分类享乐游戏的更一般结果(参见Aziz等人[2]和Peters [24]);Boehmer[8]随后提供了一个多项式时间算法来找到这样的结果。在本文中，我们证明了与上述核心发现相反，DHDG的严格核心可能是空的，即使在只有三种药物的情况下，每种药物只批准一个分数。从计算复杂性的角度来看，我们证明了DHDG是否允许非空严格核的相应决策问题是完全的，即使在每个代理只有(或最多)5个批准分数的限制设置中，对于任何固定数量。
快乐的游戏。hdg与快乐游戏密切相关(droulze和Greenberg[17])，人们从不同角度对其稳定性进行了深入研究(例如，Bogomolnaia和Jackson [10]， Bloch和Diamantoudi [7]， Karakaya和Klaus[19])。特别是，匿名享乐游戏(例如，Bogomolnaia和Jackson[10])和分数享乐游戏(例如，Aziz等[3])的子类与hdg接近。
享乐博弈是一种联盟形成博弈，其中每个主体对其联盟成员都有偏好(参见Aziz和Savani[1]等调查)。在匿名享乐博弈中，代理人只关心他们可能的联盟规模(而不关心联盟成员的身份)。对于不同的稳定性概念，如纳什稳定性、个体稳定性和(严格)核心稳定性，(匿名)快乐博弈中的稳定联盟形成已经从计算复杂性的角度进行了很好的研究，例如Bogomolnaia和Jackson[10]、Ballester[4]、Olsen[23]和Peters[24]。在分数享乐博弈中，每个代理将某个值与其他代理联系起来;一个主体的联盟价值由联盟中其他主体价值的平均值给出。对于分数阶享乐博弈，Bilò等人[6]、Brandl等人[12]、Aziz等人[3]等人也对寻找稳定结果或决定稳定结果是否存在的计算复杂度进行了研究。我们指出，贝克米勒博弈可以被理解为分数享乐博弈的一个特例(参见Bredereck等人[13]);在Bakers和miller对策中，可以在线性时间内确定严格核中的一个保证非空的最优分区(Aziz等[3])。请注意，与匿名享乐游戏和分数享乐游戏的设置不同，在我们论文中考虑的HDG问题中，我们关注的是两种类型的代理，它们对自己类型的可能部分代理具有偏好。
最后，我们注意到投票理论中的位置分数(参见Brams和Fishburn[11]的调查)，最初设计用于确定选举的获胜者，已经应用于其他几个设置，以评估结果。最突出的是，批准和Borda分数被用于组合优化问题，例如旅行销售人员问题(Klamler和Pferschy[22])，公平分割问题(参见Baumeister等人[5]，Darmann和Schauer [16]， Kilgour和Vetschera[21])，以及群体活动选择问题(Darmann[14])。
本文的结构如下。在第2节中，我们正式介绍了(二分)享乐多样性博弈的模型和所考虑的解决概念。在第3节和第4节中，我们考虑了二分享乐多样性博弈:在第3节中，我们展示了纳什稳定性和严格核心稳定性的结果，在第4节中，我们将重点关注通过批准总数衡量的社会福利最大化的结果。在第5节中，我们考虑了在具有严格偏好的享乐多样性博弈中使用Borda分数最大化社会福利的问题。本文的初步版本为[15]。
一个享乐多样性博弈由两个互不关联的集合R和B组成，R中的代理被称为红色代理，B中的代理被称为蓝色代理，我们设置。每个智能体在包含智能体i的N子集中的所有红色智能体的分数集合上指定一个弱顺序(具有无差异部分和严格偏好部分)。因此，对于红色智能体我们有，对于蓝色智能体我们有;观察红色和蓝色代理的基数是相同的。
一个子集称为联盟，表示包含agent的所有联盟的集合。我们把它解释为在包含它的某个联盟中，代理人i对所有可能的红色代理人的偏好。对于联盟C，我们用。表示C中红色药剂的比例。如果一个联盟同时含有蓝色和红色的药剂，那么它就是混合的，否则它就是纯的。一个纯粹的红(蓝)联盟只由红(蓝)代理人组成。其结果是分裂成互不相干的联盟。对于结果，令表示包含agent i的联盟;反过来说，对于某个代理i，我们写if保持。滥用符号，因为我们有iff保持;我们说，相对于联盟D，代理人i更倾向于联盟C。
在二分类享乐多样性博弈(DHDG)中，每个智能体i指定一组批准分数;Agent I对in的所有分数(即，因为我们有)都是无所谓的，严格地偏爱任何而不是任何，并且对不包含在的所有分数都是无所谓的。
我们将考虑两种解的概念:一方面，我们考虑到对个体和群体偏差的稳定性的博弈论概念，其中我们重点关注纳什稳定和严格核心稳定;另一方面，我们将投票理论中的认可分数和Borda分数应用到我们的设置中，以确定最大化(功利主义)社会福利的结果，即分数的总和。
纳什稳定的结果要求，没有一个行动者可以通过形成单一联盟或偏离其他联盟而使自己变得更好。形式上，如果不存在代理i，那么享乐多样性博弈的结果是纳什稳定的。因此，在DHDG中，如果除了某些因子外没有其它因子，则结果是纳什稳定的。
严格的核心稳定结果要求不存在这样一组agents，即通过形成一个偏离联盟，S中至少有一个成员变得更好，而S中没有任何成员变得更糟。这可以形式化如下。对于我们拥有的每一个代理人，以及我们拥有的一些代理人，联盟都弱地阻止了N if的结果。一个结果被称为严格核心稳定(或在严格核心)，如果不存在弱阻塞联盟。
代理i的结果得分，是赋给的非负整数。在给定分数下，结果的社会福利为所有主体的分数之和:。我们考虑以下两种分数。
在DHDG中，代理i的结果批准分为1，否则为0。在DHDG中，使用批准分数，结果的社会福利(或总批准分数)因此是持有的代理数量。
给定一个具有严格偏好的享乐多样性博弈，agent i的结果Borda得分为。
在以下带有和的DHDG实例中，每个代理只批准下面列出的一个分数。
让联盟来决定结果，然后。不是纳什稳定的，因为agent加入联盟会更好;是赞成而她不赞成的分数，即她被分配到的联盟的分数。另一方面，是严格的核心稳定。唯一有偏离动机的代理是代理和。注意(和分别)是唯一批准(响应)的代理。这将需要一个混合联盟。然而，在分数的联盟中，每个蓝色代理的情况会更糟。．
接下来，考虑联盟给出的结果，。结果是纳什稳定的:每个行动者都在一个她赞成的部分的联盟中，因此没有偏离的动机;Agent不赞成，1，或，所以她也没有偏离的动机;同样，(和分别)不赞成或不同意。，或0)，因此没有偏离的动机。另一方面，不是严格的核心稳定，因为联盟弱阻塞，因为通过形成偏离联盟，S代理的情况比分配的联盟更好，而不是更差。
最后观察到，结果的认可分为4分，而结果的认可分为5分。特别是，这是一种将认可分数最大化的结果。
在本节中，我们考虑在每个代理的批准数量固定的限制设置下的纳什稳定性和严格核心稳定性。在这种情况下，我们指出，即使在每个代理的批准数量很少的情况下，这种结果也可能不存在，然后转向DHDG是否分别承认纳什稳定结果和严格核心稳定结果的决策问题。
如[9]所示，即使在只有两种药物的小情况下，DHDG也可能不存在纳什稳定的结果。将他们的例子推广到大于或等于2的任意数量的智能体是很简单的;然而，为了完整起见，我们在下面的命题中说明这一点。
对于每一种情况，都存在一个二分类享乐多样性博弈的实例，其中每个主体只认可一个不承认纳什稳定结果的分数。
让,红色代理人批准分数1只和每个蓝色代理批准分数.Footnote 2任何结果都包含一个混合联合C不是纳什稳定,因为红色的代理,必须C的一员,更喜欢形成独立联盟只包含自己从事C。然而,任何结果,只有纯粹的联盟不是纳什稳定,因为每个的代理更愿意加入独特的纯红色联盟。
我们的第一个计算复杂性结果表明，决定DHDG是否承认纳什稳定的结果在计算上是难以处理的，即使限制在每个代理最多两个批准和一种类型的代理只批准混合联盟的情况下。
判定二分类享乐多样性博弈是否承认纳什稳定结果的问题是不完备的，即使(i)每个主体最多赞成两个分数，(ii)没有一个红色主体赞成纯红色联盟。
我们提供从scExact Cover减少3套(scX3C)。scX3C的实例是一对，其中和是X的3元素子集(3-set)的集合;它是一个“yes”实例，如果X可以被恰好q个集合所覆盖。我们假设X的每个元素恰好出现在三个集合中;即使在这种限制下，已知scX3C也是不完全的[18]。观察这个限制意味着，它允许我们忽略q。给定这样一个scX3C的限制实例，我们构建一个二分类享乐多样性博弈的实例如下。我们设置和。对于let表示包含的三个集合。我们用6个行动体和，集合用分数来表示。
代理商批准的分数如下对于每一个k，
蓝色试剂的认可分数集是，
Red agent的批准分数集是，
红剂的批准分数集为，和
红剂的核定分数为。
最后,
各红代理商独家批准。
观察到
每个分数——由3-set引起——恰好被三个蓝色试剂认可，因为对于每个元素，恰好有一个蓝色试剂认可;
每个部分都有6个红色试剂认可，因为每个元素都有2个红色试剂认可。
我们证明了从iff G中承认3组的精确覆盖具有纳什稳定的结果。
假设有一个确切的掩护，比方说，从3集开始。我们推导出G中agent的如下划分:
对于每一组，组成一个联盟，由三个赞成的蓝色特工和六个赞成的红色特工加上任意选择的红色特工组成。剩下的2p个蓝色个体组成纯蓝色的联盟s，剩下的红色个体各自组成单独的联盟。
观察到每个蓝色代理都赞成其联盟的分数，因此没有这样的代理有偏离的动机。没有红色特工赞成1或，因此没有红色特工想要偏离到一个纯粹的红色联盟或s。此外，我们有任何选择，因为否则是矛盾的。因此，没有一个红衫军有动机转向混合联盟。最后，对于任何分数型联盟，通过构造，该联盟包含了所有6个赞成的主体。因此，没有任何一个代理人有动机偏离到混合联盟。因此，分区是纳什稳定的。
另一方面，假设是纳什稳定的结果。设C为混合联盟。联盟C必须恰好包含三个赞成它的分数的蓝色智能体:C不能包含一个不赞成它的分数的蓝色智能体，否则她会希望形成一个单一的联盟。同样，每个混合联盟至少需要三个蓝色智能体，如果C包含超过三个蓝色智能体，则至少有一个希望形成单一联盟，因为对于每个分数，正好有三个蓝色智能体赞成。
现在，我们证明它不能包含一个纯蓝色的联盟。假设相反的情况，S是一个大小为的纯蓝色联盟。请注意，对于任何一种选择，都有确切的红色代理。因此，每个行动者都更倾向于当前的联盟，并因此有偏离的动机，除非她已经在一个分数联盟中。然而，这是不可能的，每个这样的代理是在一个联盟的分数，因为这将需要蓝色的代理。因此，不能包含一个纯蓝色联盟的规模。
因此，必须至少有p个蓝色的主体参与某种混合联盟。由于每个蓝色主体都需要认可她所在的混合联盟C的分数，因此C必须是某个k的分数。同样，回想一下，分数是由set in诱导的。联盟C因此由
正好是三个蓝色的人，也就是三个人选择，和
确切地说，红色特工包括6个红色特工，他们同意——比如说某些选择——因为否则就不是纳什稳定的。
请注意，任意两个混合联盟必须有不同的分数，因为每个混合联盟必须有恰好三个蓝色代理，所有这些代理都赞成它的分数，并且每个分数的构造恰好有三个这样的代理。
另外，请注意，由于第2点。在上面的混合联盟中，对于每一个u，最多只能包含一个:和包含在混合联盟C中，这意味着与谁赞成，不能包含在分数混合联盟中，因为(i)一个赞成，(ii) D需要包含所有六个赞成的红色代理。
因为至少有p个蓝色智能体需要参与到某个混合联盟中，所以对于每个u，只有一个智能体包含在某个混合联盟中。由于1。联盟C必须包含另外两个赞成它的蓝色特工。因此，集合Z的集合包含一个大小的联盟，在实例中形成3个集合的精确覆盖。
如下所示，相应的硬度结果适用于每个代理只批准5个分数的情况，对于任何选择。
对于任何固定的，决定二分类享乐多样性博弈是否承认纳什稳定结果的问题是不完全的，即使(i)每个代理都赞成正好5个分数，(ii)没有一个红色代理赞成纯红色联盟。
我们假设s是固定的。我们通过让
每个代理商也都同意，
每个代理商也都同意，
每个代理也都赞成。
" only if "部分类似于定理1的证明。
对于“如果”部分，让它是纳什稳定的。回想一下，每个蓝色代理都赞成分数为0。因此，纳什稳定性意味着每个蓝色个体都赞成她的联盟的分数，否则她就会倾向于形成一个单一的联盟。因此，每个混合联盟C必须要么是某个k的分数，要么是某个k的分数。注意后一种情况是不可能的:至少有一个红色的智能体必须在一个纯红色的联盟中，因为所有的蓝色智能体都在c中——因此，这样的智能体想要加入c。回想一下，对于，这个证明类似于定理1的证明。
与纳什稳定的情况类似，在DHDG中也可能不存在严格的核心稳定结果。然而，在只有两个智能体的情况下，严格核心保证在任何HDG中都是非空的，因此在任何DHDG中也是如此(命题3)。另一方面，我们表明，一旦出现第三个智能体(或更多智能体)，严格核心可能是空的(命题4)。此外，我们证明-从计算的角度来看-很难确定给定实例是否具有非空的严格核心。即使每个制剂的批准分数最多为三个，一种制剂只批准混合联合;我们通过表明硬度对任何固定的分数也恰好成立来结束本节。
带有两个代理的享乐多样性游戏的每个实例都有一个非空的严格核心。
令和分别表示红色剂和蓝色剂。对于agent，可能分数的集合是，对于agent，可能分数的集合是。如果两个代理人都排名靠前，那么组成大联盟的结果是严格的核心稳定。否则，由单一联盟组成的结果是严格的核心稳定的，因为至少有一个代理严格地倾向于她的单一联盟而不是大联盟。
的话。请注意，上述命题意味着，对于具有两个代理的实例，HDG的核心始终是非空的。
对于每一种游戏，都存在一种二分类的享乐多样性游戏实例，其中每个代理只认可一个部分，因此严格的核心是空的。
令和，其中代理同意分数，其余代理同意分数0。考虑一个结果。每一个赞成分数0的蓝色智能体都必须在一个纯蓝色联盟中，否则就不是严格意义上的核心稳定，因为各自的智能体更愿意形成一个单一的联盟。此外，每一个都必须在一个分数的联盟中:为了矛盾起见，假定相反，假定w.l.o.g.在一个有其他分数的联盟中;然后，(它有分数)弱阻塞，因为它变得更好，而不是更坏。然而，在分数联盟中的每一种都要求至少有一种不同于的蓝色药剂，这是不可能的，因为不同于的蓝色药剂必须在纯蓝色的联盟中。因此，不是严格意义上的核心稳定。
现在我们转向DHDG是否具有非空严格核心的决策问题，并证明即使在每个代理最多有三个批准分数的限制设置下，这个问题在计算上也是困难的。
决定二分类享乐多样性博弈是否承认一个严格的核心稳定结果的问题是完全的，即使(i)每个代理最多批准三个分数，(ii)没有一个蓝色代理批准一个纯蓝色联盟。
在定理1的证明中，我们用3-scSets (scX3C)给出了scExact Cover的限制完全版的约简。给定这样一个scX3C的实例，其中和是X的3元素子集的集合，使得X的每个元素恰好出现在三个集合中，我们构造了一个二分类享乐多样性对策的实例。回想一下。我们设置和。对于let表示包含的三个集合。我们用行列式表示，我们把集合和分数联系起来。代理商的批准如下:
对于每个k, agent和agent的认可分数集合为，和
对于每个k和j, agent的批准分数集合为。
观察到，通过构造，每个分数，恰好被三种蓝色试剂所认可。我们现在证明，如果G承认非空严格核，则它承认3集的精确覆盖。
假设在实例中有一个精确的覆盖Z比3集。我们构造N的划分如下。对每一个集合设一个联合，并设每一个集合形成一个单一的联合。单个联盟中的每个agent都赞成自己的分数。注意，里面正好有三种蓝色和红色药剂。联盟的比例是，因此，由于，被所有的代理人认可。注意，由于Z是一个确切的掩体每个agent都在一个混合联盟中。因此，每个代理都参与了一些联盟，并批准了它的分数。因此，分区是严格核稳定的。
另一方面，假设有一个严格的核心稳定结果。为了矛盾起见，假设至少有一个蓝色代理与她不赞成的部分组成联盟。表示包含元素的三个集合之一。如上所述，与所有成员都同意的分数组成联盟。由于成立，我们可以得出弱阻塞的结论，这与严格核心稳定的假设相矛盾。因此，每个蓝色特工必须与她认可的部分组成联盟。请注意，通过构造(对于每个蓝色代理，每个批准分数的分母超过分子3)，这要求所有批准的三个代理必须在同一个联盟中。因此，该套形成了一个精确的覆盖3套。
对于任何固定的，决定二分类享乐多样性博弈是否承认一个严格的核心稳定结果的问题是不完整的，即使(i)每个代理只同意5个分数，(ii)没有一个蓝色代理同意一个纯粹的蓝色联盟。
我们假设s是固定的。我们将定理2的证明改写如下:
每个代理和每个代理也认可，
每个代理也赞成和赞成。
" only if "部分类似于定理2的证明。
对于“如果”部分，类似于定理2的证明，在一个严格的核心稳定结果中，每个蓝色智能体必须处于一个她认可的分数的联盟中。请注意，对于某些人来说，具有分数联盟的结果并不是严格意义上的核心稳定，因为代理人会偏离到纯粹的红色联盟。因此一定对应于某对某。因此，这个证明类似于定理2的证明。
除了稳定性概念之外，从社会选择的角度来看，使社会福利最大化的结果是令人感兴趣的。在本节中，我们考虑dhdg，并使用认可分数来衡量结果引起的社会福利。我们首先表明，当每个代理只批准一个分数时，可以在多项式时间内找到最大化社会福利的结果，即总批准分数。然而，我们随后证明了相应的决策问题在智能体可能批准两个分数时就已经完成了。因此，我们在多项式可解的和不完全的情况下，就每一剂的核定分数的固定数量，划出了明确的分界线。
我们引入一些额外的符号。对于代理集和分数，令和分别表示批准的红色代理集和蓝色代理集。令和分别表示集合中红色和蓝色智能体的数量。
在具有认可分数的二分类享乐多样性博弈中，每个主体只认可一个分数，可以在多项式时间内找到最大化社会福利的结果。
我们将把一个具有单个代理批准的二分类享乐多样性博弈简化为一个双约束背包问题。双约束背包问题的一个实例由一组物品组成，其中每个物品与利润、重量和体积相关联;目标是选择总利润最大的项目子集，使总重量不超过给定的重量界限W，总体积不超过给定的体积界限V(即和)。通过动态规划，可以及时确定双约束背包问题实例中的最大利润，及时确定项目的最优利润和利润最大化集(参见[20]中的9.3.2章)。
给定一个二分类快乐多样性博弈，每个agent只有一个批准，我们构造了一个双约束背包问题的实例。w.l.o.g.，我们假设G中的分数不能再约了，即G中每个分数的分子和分母都是素数。
对于每一个至少被一个智能体认可的分数(带有和)，我们首先将认可的智能体集合划分为集合，并在这些集合的基础上引入例如项目。
为了构建集合，我们的想法是，虽然有红色或蓝色代理批准，但只要它包含的红色代理少于蓝色代理，就将它们添加到其中;然后继续等等。我们的程序如下:
；
对于每个分数构造包含和的代理的集合，，使得
每个这样的集合最多包含红色代理和蓝色代理，集合非空，和
对于红色药剂，我们有iff包含药剂(对于蓝色药剂b，我们有iff包含药剂)
我们说集合是满的，如果它恰好包含红色和蓝色试剂。
观察到每个N的智能体只包含在其中一个集合中(因此我们最多有N个这样的集合)，并且集合中的每个智能体都同意。
为了构造双约束背包问题的实例，我们对每个集合引入一个具有利润、重量和体积的物品，集合为。
为了说明这个证明，我们提供了以下运行的DHDG示例，每个代理只有一个批准的分数。设由6个红色代理和7个蓝色代理组成一组N，审批如下:
代理和批准的分数;
代理和批准;
代理人同意;
代理人同意。
然后，对于分数，我们得到and |;With和它紧随其后。因此，我们构造集合
类似地，我们构建集合
注意，在我们的示例中，完整集合是集合和。由此，我们通过设置构造了双约束背包问题的实例，并引入了以下项目:
项目利润，重量2，体积1，
项目利润，重量2，体积1，
项目利润，重量2，体积1，
利润3，重量1，体积2的项目，
利润2，重量1，体积2的项目
利润1，重量1，体积1的项目
利润为1，重量为1，体积为7。
现在，我们通过证明如果存在G的结果，则存在带利润的解来证明这个定理。
“”:总利润的一个解(=一组项目)在G中推导出如下的社会福利结果。考虑集合，即是与中的项相对应的集合的集合。我们分两步构建可持续发展目标的结果。
首先，对于所有已满的集合，定义联盟。接下来，对于非完整集，该集包含红色代理或蓝色代理;但是，相应物品的重量和体积分别为和。因此，对于每一个非完整的集合，重量的贡献超过红色药剂的数量，体积的贡献超过蓝色药剂的数量。与选择(和分别)一起可以得出，必须至少有
至少是红色特工
N中的蓝色代理不包含在某个集合中。因此，对于所有不满的集合，我们可以通过用红色和蓝色的主体“填充”来构造分数的联盟。，通过添加红色和蓝色代理来创建，直到它完全包含红色和蓝色代理。
现在让我们把结果设为包含所有剩余行为人的联盟+联盟D的结果。观察每一个至少赞成其分数的代理。另外，回想一下定义。因此，对于结果我们有。
在我们正在运行的示例中，让。Solution满足重量约束和体积约束(其产品的总重量和总体积分别为6和5)，利润为8。为了构建DHDG的结果，我们推导。既然是满的，我们得到。剩下的几组没有满;为了获得与关联的分数，我们任意地将这些集合“填充”为不包含在-即-中的集合中的代理。，有代理。例如，我们得到，，和。最后,。它是这样的。
“”:假设有一个结果。W.l.o.g.我们假设每个联盟不能被分成相同比例的小联盟，即对于每个联盟C，它成立。
设为所有主体都赞成其分数的联盟集合，设为至少有一个主体不赞成的联盟集合。让我们设为参与某种联盟的行为者的集合，设为赞成联盟部分的行为者的集合，设为反对联盟部分的行为者的集合。从这里，我们通过对agent的重新分组来构造一个新的分区:
对于所有被在中的智能体认可的集合，从在中的智能体构建集合，类似于在实例的构造中构建集合;
用代理填充集合如下(即，将红色和蓝色代理精确地添加到):
只要有一组就行。，和一个红色的(代表)。蓝色)的代理，将该代理添加到集合中索引j最小的集合中;
在那之后，只要有一套就行了。，添加一个任意的红色(响应)。蓝色)代理从到;
其余的代理人组成联盟。
观察到，与之比较，对于每一个这样的集合的数量不超过分数的联盟的数量。因此，为了达到所需的分数，添加到集合中的代理数量实际上是足够的，因为这是一个可行的分区。
因此，对于每一个这样的分区都有一个联盟C，分数in的联盟最多和in的联盟一样多。同时，观察到赞成联盟分数in的代理人也赞成联盟分数in的代理人。因此，在某些联盟中，赞同其联盟分数的参与人的数量至少为。然而，通过的构造，在的组合集与中的项子集之间存在一一对应关系。因此，对于每个联盟，在实例中必须有一个项目，其利润与赞成的代理数相对应。此外，通过选择物品的重量和体积，是一个可行的解决方案。由此，承认解决与利润。
在运行的示例中，考虑与，，，，的联盟给出的结果。因此，，由中所有其他的联盟组成。因此，参与某种联盟的一组行为人。此外，我们还有和。
因此，我们从for中的智能体构建集合，因为这些是被某个智能体认可的唯一分数。我们得到，和。在下一步中，我们用来自的代理“填充”这些集。首先，我们添加赞成各自分数的代理:我们添加to和to。然后，我们将剩余的代理加入到集合中，得到相应的联盟分数，即，和。最后，我们进行构建。因此，由联盟，，和组成。注意这一点。
由此，我们导出了双约束背包问题实例的解:因为，其中所有3个成员都同意其分数，我们在利润项3中包括;因为，如果它的两个成员赞成它的分数，我们就把利润项目2包括在内，等等;因此，……注意，满足重量和体积限制并产生10的利润。
最后，观察到双约束背包问题的最优利润可以及时确定，并且解的回溯也可以及时完成。
消极的一面是，一旦代理人同意两个分数，决定具有批准分数的DHDG是否承认社会福利超过某个给定整数的结果的问题就变得难以计算。
给定整数，决定具有认可分数的二分类享乐多样性博弈是否允许结果为-完全的问题，即使(i)每个代理最多认可两个分数，(ii)每个蓝色代理只认可一个分数。
再次，我们将scExact Cover的-完全变体简化为3- set (scX3C)，该3- set被限制为具有和的实例，使得X的每个元素恰好出现在中的三个集合中。假设这是scX3C的一个受限制的实例，记住这一点。我们构造一个二分类享乐多样性博弈的实例如下。我们设，和。对于三个包含的集合表示为。我们认同这六个代理，并将集合与分数联系起来。代理商的批准由:
蓝色药剂的批准分数为，，
Red agent的批准分数集是，
Red agent的批准分数集是，
红剂的批准分数集为，和
各红代理商独家批准。
观察到，由set诱导的每个分数都恰好被三个蓝色试剂和六个红色试剂所认可。我们现在认为，如果G承认一个结果，那么它承认一个确切的3局掩护。
假设有一个精确的封面Z，回想一下，Z包含精确的集合。观察到对于z中的任意一个，为了构造G中的分区，
对于每一组，由赞同的3个蓝6个红agent与任意选择的agent组成联盟C;
其余的代理人各自组成单独的联盟。
由于Z是3集的精确覆盖，划分是定义良好的。由于我们所关注的是完全混合的联盟，因此参与混合联盟的代理的数量最多是，因此划分是可行的。每个混合联盟包含9个赞成其分数的代理人，其总社会福利为。
另一方面，假设有一个结果为g，没有一个主体赞成处于纯联盟中，因此只有混合联盟才能对社会福利产生正价值。为了做到这一点，混合联盟C必须要么是分数的，要么是分数的。在前一种情况下，C包含了所有的蓝色agent，因此C必须是唯一的混合联盟，这与我们的假设相矛盾。在后一种情况下，C至少需要红色代理。如果G恰好包含红色特工，那么最多可以存在这样的联盟，否则至少需要红色特工。由于任何分数都恰好得到9个主体的认可，这意味着我们必须有这样的联盟，每个联盟必须包含所有9个主体认可其分数。对于每一个k，这意味着，对于最多一个-由于我们有这样的联盟这意味着，对于正好一个-有一个分数的联盟;因此，对于每k，只有一个人参与了这样一个联盟，这个联盟包含了所有三个赞成它的分数的蓝色代理。因此，集合形成一个精确的覆盖3套。
事实上，上述硬度结果转化为任何固定数量的分数批准每个剂。
对于任何固定的问题，即决定具有认可分数的二分类享乐多样性博弈是否允许某个给定整数的结果是-完整的，即使每个代理只认可5个分数。
注意，由于s是固定的，我们可以假设它保持不变。将定理4的证明改编为如下证明:
每种蓝色试剂也赞成分数;
如果每个红剂也赞成分数;
此外，代理商也认可分数。
“如果”部分类似于定理4的证明。对于“only if”部分，请遵守以下规定:
任何结果包含一个F的组合，对于某些分数包含g个蓝色药剂和所有红色药剂，因此任何其他的组合必须是纯蓝色的。F中的每一个蓝色药剂都赞成它的分数，但是没有一个红色药剂赞成。因此，由于没有代理人赞成纯联盟的部分，这样的结果最多实现社会福利。
任何包含组合分数D的结果都包含红色药剂和除一种以外的所有蓝色药剂。D中的每一种红色药剂可能都赞成自己的分数，但没有蓝色药剂赞成。此外，不在D中的每个agent要么在纯红色联盟中要么在只包含一个蓝色agent的联盟E中。没有代理人赞成一个纯粹的联盟。由于至少有一个红色代理参与了D，所以不能包含一个分数的联盟，所以也没有代理认可联盟E的分数。因此产生的社会福利最多为。
有了这些观察，“只有当”的部分类似于定理4的证明。
现在我们离开dhdg的设置，考虑这样一种情况，即每个主体的偏好是通过对可能的联盟分数的严格排序来给出的。事实证明，在这种情况下，在使用Borda分数下，最大化社会福利在计算上是困难的。
给定整数，在Borda分数下，决定一个具有严格顺序的享乐多样性游戏是否承认一个结果是-完整的问题。
我们将scExact Cover的-完全变体简化为3- set (scX3C)，该3- set被限制为具有和的实例，使得X的每个元素恰好出现在其中的三个集合中。假设是scX3C的这样一个受限制的实例(回忆一下)。从这里我们得到了一个享乐多样性游戏的实例，如下所述。代理集由集合和组成。同样，我们表示三个集合包含。Agent表示元素，我们将分数与集合联系起来。代理的排名——直到分数所处的位置——如表3所示。设T为单个智能体的最大可能Borda得分。
我们声称，如果G承认一个结果具有Borda总分，那么这就是scX3C的“是”实例。
“”:设Z为3集的精确覆盖。考虑分区
因为每个人都组成了一个联盟，由三个排名前三的蓝色特工和任意选择的红色特工组成，
并将剩下的代理人(由于Z是一个精确的掩护，因此必须全部是红色代理人)分配给单一联盟D。
由于Z是一个精确的3组掩护，每个蓝色特工都在一个联盟中，她排名第一，第二或第三。每个红色特工都在一个分数为1的联盟中。因此，我们有。
“”:让结果与。请注意，所有蓝色代理人参与同一联盟的任何结果都最多产生总Borda得分。因此，任何满足期望边界的结果都将蓝色代理集划分为至少两个联盟。
假设有一个蓝色的agent不在一个分数排名前三的联盟中。由于蓝色代理不属于单一联盟，因此该代理的最大可能Borda得分为。对于剩余的蓝色智能体，最大Borda得分为t。接下来，观察到任何联盟在前p个排名的智能体分数中的分数对应于一些，因此在这样一个联盟中所需的蓝色智能体数量是3的倍数。由于总共只有p个蓝色智能体，因此在某个k的分数联盟中，涉及的红色智能体少于红色智能体。因此，所有红色智能体贡献的最大可能的总Borda得分为。因此,
与我们的假设相矛盾。
因此，每个蓝色代理的联盟必须有一个分数排在她的前3个分数中。因为每个这样的分数都在正好三个蓝色代理的前3个分数中，所以每个相应的联盟都正好需要3个蓝色代理(因为这样的联盟需要3个代理的倍数)。因此，集合形成一个精确的覆盖3套。
享乐多样性博弈既可以理解为博弈论问题，也可以理解为社会选择问题;因此，我们考虑了两种解决概念:一种是源于博弈论的稳定性概念，另一种是源于社会选择理论的社会福利概念。对于后者，我们考虑了投票理论中两种最突出的分数类型，即批准分数和博尔达分数。
除了一些计算复杂性的结果，我们还表明——与核心相反，它总是非空的(见[2,24])——二分类享乐多样性博弈的严格核心可能是空的，即使在具有少量代理的情况下，每个代理只有一个批准的分数。然而，一些有趣的问题仍然悬而未决。例如，决定一个二分类的享乐多样性博弈是否会在每个agent只有一个被认可的分数的情况下产生纳什稳定结果的计算复杂度是多少?当每个主体只认可一个分数或最多两个分数时，决定二分类享乐多样性游戏是否承认一个严格的核心稳定结果有多难?
未来研究的一个有趣的方向是，当每个代理不被批准的分数的数量是固定的，而不是被批准的分数的数量时，研究所考虑问题的计算复杂性。例如，当每个主体只同意固定数量的分数时，我们能否为最大化社会福利的任务推导出类似的二分法?
更一般地说，未来可能的研究方向可能是研究哪些(额外的)合理的领域限制允许与计算稳定结果或最大化社会福利的结果相关的积极结果。
发表评论
暂时没有评论，来抢沙发吧~