全偏好域上的约束序列规则

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

摘要翻译：
研究了在任意线性约束条件下，当Agent允许对象之间不受影响时，将对象分配给Agent的问题。我们的主要贡献是通过一种称为约束串行规则的新机制来推广（扩展的）概率串行机制。该机制具有计算效率和公平性，即约束有序效率和同类型Agent之间的无嫉妒性。我们的机制基于线性规划方法，它考虑了所有的约束，并提供了对构成扩展概率串行机制关键部分的代理瓶颈集的重新解释。
---
英文标题：
《Constrained Serial Rule on the Full Preference Domain》
---
作者：
Priyanka Shende
---
最新提交年份：
2020
---
分类信息：

一级分类：Economics        经济学
二级分类：Theoretical Economics        理论经济学
分类描述：Includes theoretical contributions to Contract Theory, Decision Theory, Game Theory, General Equilibrium, Growth, Learning and Evolution, Macroeconomics, Market and Mechanism Design, and Social Choice.
包括对契约理论、决策理论、博弈论、一般均衡、增长、学习与进化、宏观经济学、市场与机制设计、社会选择的理论贡献。
--

---
英文摘要：
  We study the problem of assigning objects to agents in the presence of arbitrary linear constraints when agents are allowed to be indifferent between objects. Our main contribution is the generalization of the (Extended) Probabilistic Serial mechanism via a new mechanism called the Constrained Serial Rule. This mechanism is computationally efficient and maintains desirable efficiency and fairness properties namely constrained ordinal efficiency and envy-freeness among agents of the same type. Our mechanism is based on a linear programming approach that accounts for all constraints and provides a re-interpretation of the bottleneck set of agents that form a crucial part of the Extended Probabilistic Serial mechanism.
---
PDF下载：
--> English_Paper.pdf (233.2 KB)

2022-4-16 11:16:59 上传

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏0 回帖

关键词：序列规则 Contribution Constrained Constraints Theoretical

完整优先级上的约束串行规则domainpriyanka Shende*日期：2020年11月3日摘要我们研究了在任意线性约束条件下，允许Agent在对象之间交互时将对象分配给Agent的问题。我们的主要贡献是通过一种称为约束序列规则的新机制来推广（扩展的）概率序列机制。该机制在计算上是e-cient的，并保持了理想的e-cient和公平性，即同类型代理之间的约束序数e-cient和无嫉妒性。我们的机制基于线性规划方法，它考虑了所有的约束条件，并提供了对“瓶颈”代理集的重新解释，这些代理集构成了扩展的概率序列机制的关键部分。关键词：随机分配；概率串行机制；约束序数E-ciency；加州大学伯克利分校；电子邮件:priyanka.s@berkeley.edu1介绍在一组代理之间公平地分配一组不可分割的对象是应用和理论电子商务中最基本的问题之一。经典的对象分配模型，如房屋分配模型（Hylland and Zeckhauser(1979))，现在已经被很好地理解，沿着公平、平等和激励的模糊扩展，保证可获得属性的任何最大子集的机制也是众所周知的。然而，在实践中，许多应用都施加了额外的限制，在这样的限制条件下设计分配机制仍然是一个巨大的挑战。本文提出了一种新的约束序列规则机制，该机制在一个大的一般约束条件下，总是能获得公平合理的分配结果。在一般的对象分配模型中，一组不可分的对象必须根据agents对这些对象的偏好来匹配一组agents。在本文中，我们将注意力限制在代理只报告相对于目标的偏好排序的序号机制1上。这种设置模拟了大量现实世界中的应用，如公立学校的学生安置（Abdulkadiro-lu和S"onmez,20 0 3）,cours e分配（Budish,2011）,organdonation（Roth et al.，2005)和校园住房分配（Chen and S"onm ez，2002)amon Gothers。在许多这样的应用中，非常希望机制是fai r的，即没有agentis被歧视，也有e-cient的，即没有Allagents更喜欢的其他结果。不幸的是，由于对象是不可分割的，所以很容易发现没有一种机制可以被认为是公平的事后机制。因此，随机化常常被我们认为是从事前的角度恢复的一种工具。在住房分配的背景下，Bogomo lnaia和Moul在（2001）中提出了no tion ofordin a l e-ciency。一个随机赋值被称为序数赋值，如果不存在任何其他赋值来随机支配它。事实上，他们表明，经过充分研究的随机优先级机制，即以一致的随机顺序对代理进行排序，然后从剩余对象集合中分配每个代理最喜欢的红色对象，并不是有序的，而只是满足了一个较弱的后序的概念。要求每个代理人更喜欢自己的分配而不是其他人的分配的嫉妒自由的概念经常被认为是manydi anthe erent sett ings中的旧的公平标准，如资源分配(Foley，1967)、切蛋糕（Robertson and Webb，1998)和租金分工（Edward Su，1999)。在随机分配机制的背景下，这与代理报告每个对象的基本效用的基本原则形成了鲜明的对比。

Bogomolnaia和Moulin(2001)在他们的扫描电镜工作中引入了概率序列机制，该机制总是产生有序的和无嫉妒的结果。概率串行机制可以如下所示。在tim e zero，每个代理开始“吃”她最喜欢的对象。当代理吃掉一个对象的总时间s p结束等于1时，该对象就变得不可用。一旦一个对象变得不可用，所有正在吃它的代理，就会切换到吃仍然可用的对象中最喜欢的对象。最后，一个agent接收某个对象的概率是该agent吃掉该对象所花费的时间。不幸的是，概率服务机制假设agent对对象有严格的偏好，这在实践中是一个相当严格的限制。事实上，正如discus sedbyKatta和Sethuraman(2006)和Erdil和Ergin(2017)，偏好中的领带在许多实际应用中是广泛存在的。例如，代理可能将so me对象视为i Dentic对象。即使对象都是d型的，对所有对象进行评估和排序可能是计算上的困难，而智能体可能只能通过间接的结果显示粗略的排序。Katta和Sethuraman(2006)在论文中提出了扩展的概率序列机制，将概率序列机制推广到全偏好域，并保留了ordin和Envy-freeness的理想性质。这些机制的广泛应用受到了这些机制假设每个随机分配都是可行的这一事实的阻碍。在大量的实际应用程序中，法律和政策的要求要求研究在某种程度上限制行为的机制。例如，在课程所有定位问题中，通常要求分配给一门课程的最小（和最大）学生人数。类似地，在择校申请中，要求收集保持多样性水平的作业（Ehlers et al.(2014))。在住院医师匹配中，通常需要将医生分配到医院以满足地理限制（Kamada and Kojima(2015))。在Refugeeresethentity问题中，对象代表安置设施，一个可行的分配必须确保被分配到一个设施的所有代理人的总需求由该设施的资源供应来满足(Delacrétaz et al.(2016))。类似地，在肾脏匹配app lications（Roth et al.(2005))中，血液-T型兼容性对可行的匹配施加了限制。本文研究了在可行概率分配的s et上具有任意线性约束的目标分配问题。在Balbuzanov(2019)的基础上，本文将随机序列机制推广到完全偏好域，并在可行随机分配集合上支持任意线性约束。我们的机制是计算，只需要一个多项式的运行时间，即约束、代理和对象。对于完全偏好域上的经典无约束住房分配机制，我们的机制与Katta和Sethuraman(2006)的扩展概率序列机制相一致。概率串行机制的各种推广已经被提出，公式--单需求（Kojima(2009))、特定类型的约束，如双层次约束（Budish et al.，2013)、依赖类型的di stributional con约束（Ashlagi et al.，2020)、组合需求（Nguyen et al.，2016)、具有ind ividual rational itity的财产权(Yülmaz，2010)和对后所有o阳离子的任意约束（Balbuzanov，2019)。

我们的约束序列规则对文献进行了总结，给出了这些机制的一个通用的推广，并对全偏好域进行了扩展。我们证明了即使在一般的约束条件下，约束序列规则仍然保持了概率序列机制的desi rabl e e e ciency和fairnesss性质。在p关节，我们的机制通常受到限制。虽然很容易观察到任意约束排除了无嫉妒机制的存在，但我们证明了约束序列规则保持了公平的概念。直观地说，如果constraintstructure不区分两个agents之间，我们就说agents和是sam e类型的。我们证明了约束序列规则机制保证了任意一对相同类型的agent的无嫉妒性。然而，我们的机制不是战略证明，甚至不是弱战略证明。这是不足为奇的，因为即使在无约束的环境中，弱策略证明性也与完全偏好域上的序数e-ciency和嫉妒自由有关（Katta和Sethuraman，2006)。1.2其他相关工作有越来越多的文献研究约束下的分配和匹配机制。几项研究在学校选择、大学入学和反反行动的背景下考虑了限制和上限（Ashlagi et al.，2020年；Biróet al.，2010年；Echenique and Yenmez，2015年；Ehlers et al.，2014年；Fleiner and Kamiyama，2016年；Fragiadakis and Troyan，2017年；Goto et al.，2015年；Hafalir et al.，2013年；Hamada et al.，2016；Kojima，2012年；Kominers and S"onmez，2013年；Westkamp，2013)。埃切尼克等人。（2019）将任意的事后约束考虑为inBalbuzanov(2019)，并提供了一个受约束的伪市场均衡解。Akbarpour和Nikzad(2014)；布迪什等人。（201 3）；Pycia和ünver(2015)研究了rando m匹配机制的可实现性，Budish et al.（2013）将双层次约束结构确定为使用弱赋值抽签实现随机赋值的必要条件。它们提供了在无约束条件下的（扩展ed）概率序列机制的一般化。事实上，我们的机制能够在存在n个零约束的情况下容纳双约束不等式。Akbarpour和Nikzad(2014)提出了超越双层次结构的更一般约束，并展示了如何近似地实现可行的随机分配。Pycia和ünver(2015)提供了关于随机机制的性质的条件，当随机机制被分解为对这些决定性机制的抽奖时，这些条件继续满足于确定性机制。我们的论文的重点是noton可实现性，我们在3.4.2节模型中对此进行了一个小的讨论，我们首先考虑了一组代理和一组对象。设=为不同主体s的nu mber,且=为不同对象的数目。每个agent都有一个单位2的需求，其中的对象是供给量是供给量是供给量是供给量是供给量是供给量。当对象稀少时，我们可以把e的nullobject,在th e集合中，以一定的数量供应以满足所有参与者的需求，即:θ≥.因此，在不丧失一般性的情况下，我们可以假定atp∈≥.Eachagent在in的对象集合上具有偏好关系。偏爱是屁股，是完整的和传递性的。特别是，我们允许代理在任何一对ofobjects之间交互。设（jing）是在preference them内的in d i change Erence类的个数。对于任一个π≤(eMb)，设(π)是首选项jeMy的n个类中的所有对象集。所有主体的个体偏好的Aset构成偏好profection=(t)∈.

设R是所有可传递关系和可传递关系的集合，而R是所有可能优先关系的集合。对象对agent的随机分配由向量x=(，)∈，∈[0,结果还推广到所有agent都需要≥1个对象的情形，当x∈，=1‰‰x∈，≤‰‰x时，每个agent的分配是由子向量x=(，)∈，其中t是agent分配对象的能力。设()=p∈，是agent对集合中对象集合的累积分配。赋值是永恒的，当存在于{0,1}时，即每个agent被赋值为一个概率为1的对象。L et D表示所有确定性分配s的集合，ΔD表示所有随机分配s et。一个随机分配机制是一个映射:R→ΔD，它将Eachpreferency proferency proferency proferency proferency proferency proferency proferency proferency proferency proferency proferency proferency proferency proferency proference给定两个随机分配s x和y，分配x随机支配分配y关于t o。，用x（.）y表示，当且仅当p′，′≥p′，′，对于所有∈.如果不等式对s ome是严格的，那么X严格随机支配Y，在这种情况下我们用X（）Y来表示它。在任意给定的条件下，我们假定可行随机分配的集合可以描述为凸多面体。形式上，在偏好点上，可行随机赋值集ΔC(Ⅵ)由一个矩阵=[，]1≤≤，{，}∈×∈R×和一个向量=[]1≤≤∈R参数化，其中是一个泛型约束，是约束的个数，定义为:ΔC(Ⅵ)={x∈ΔD x≤}。我们假定在每个偏好点上，可行随机赋值集是非空的。即ΔC(to)≠。这样的约束形式使我们能够将我们的模型应用于我们在第4节中描述的许多di-whited erent specific应用程序。设ΔC={Δ(.)}∈R为所有偏好点的约束多边形集合。给定一组约束ΔC，如果在每一个偏好profire.(ut)∈ΔC(ut)，则一个机制是可行的。我们接下来在存在约束的情况下对e-ciency和公平性的规范性质进行了分析。定义2.1（约束序数e-ciency）。如果不存在另一个随机赋值x′∈ΔC(ρ)，使得x′(ρ)x对所有的均如此，x′()x对至少一个如此，x′()x对任意一个均如此，则随机赋值x在一个偏好点和约束集ΔC(ρ)上被有序约束。如果对于每一个偏好，公平原则通常都受到约束，那么公平原则通常都受到约束。公平原则的概念要求任何一个代理人都不应该嫉妒其他代理人所得到的分配。当面对限制时，很容易看出一个人不能保证没有嫉妒的任务的存在。因此，我们将自己限制在属于同一类型的代理之间的公平比较。对于rix中给定的约束m，我们说agents and属于相同的ty pe，如果对于每个对象，变量，and,在.definition2.2（Agent类型）中的每个约束中都有samecoe-cients。设ΔC(Ⅵ)={x∈ΔDx≤},其中=[,]1≤≤,{,}∈×表示t h e约束集一个优先级。如果对于每一个约束条件1≤≤，并且对于每一个对象，我们有，=，.认知2。3（同类型代理人之间的无嫉妒）。

如果对于每一对agent s，则同一类型的agent之间的随机分配x是无嫉妒的，如果对于每一对agent s，则同一类型的agent之间的随机分配x是无嫉妒的，如果对于每一对agent的偏好，则同一类型的agent之间的机制是无嫉妒的。3序列规则的构造给出了简单房屋分配模型中的经典概率序列机制（Bogomolnaia和Moulin，2001)的一个简短直观的描述。该机制最好用连续时间过程来描述：在每一个小的时间间隔[,+)，每个agent在当前可用的一组对象中消耗她的m o个首选对象的量。当这个过程结束时，一个agent分配一个对象的概率由agent消耗的对象的分数给出。当试图将概率串行机制扩展到我们在完全偏好域上的一般模型时，在最终随机分配的条件下，面临着两个关键的挑战。首先，当agent具有stri ct偏好时，每个agent在任何时间点都有一个唯一的最偏好对象，因此机制可以简单地将该对象分配给agent。另一方面，当Agent在两个或多个对象之间交互时，其机制不再能够唯一地标识要分配的对象。Katta和Sethuraman(2006)通过构造一个Vireow图来解决这个问题，其中每个agent指向她的集合的最多agent对对象有严格的偏好，并且对分配没有额外的约束。首选红色对象，然后通过参数化的Vireow公式来筛选瓶颈agent和对象。从直观上看，瓶颈代理集是竞争最激烈的代理集，而瓶颈代理集则是b-奥特领代理所期望的代理集。扩展的概率串行机制将瓶颈对象统一分配到这些代理中。与经典的概率序列规则一样，该机制由每个瓶颈代理指向下一个最优对象进行。一个关键的观察是（扩展的）概率序列机制尽力为每个agent分配她最喜欢的对象。事实上，正如Bogomolnaia(2015)所观察到的那样，我们可以为Prob abilistic序列规则提供如下的福利主义解释：对于任何一个代理，设(0)是该代理为其顶级类接收的对象的总概率份额；然后，概率串行机制leximin最大化所有这类共享的向量(((du))∈，≤(ob)。我们在我们的con-stracted串行规则机制中关键地使用了这一观察。第二个挑战是由于在可行空间上存在任意的约束而产生的。我们观察到，在该机制的任何一个步骤中，概率机制总是为每个agent分配她当时最喜欢的对象。然而，在现有的约束条件下，如果这样的分配导致不可行，那么不允许代理获得他们最喜欢的对象是至关重要的。更确切地说，该机制需要在建立部分分配时向前看，以确保至少有一种方法将部分分配扩展到可行的分配。我们的con stracted serial规则机制使用一个l线性程序，它明确地说明了所有约束条件，并且在每一步都保持一个可行的解。我们现在描述了该机制所使用的关键线性规划。设deno teany是agents的ubset，并设对每个agent∈d表示indi erencethreshold{1,2,....,(qo)}。设一个表示pri或PROMISED赋值的三元组集。形式上，triple(，0，0)∈，表示agent必须从其最大的indi-indi-erence类中获得at l east的总概率份额。

图1所示的线性规划(，，(^)∈)构造了一个随机赋值x∈R+，该赋值满足除强加的可行约束外的所有约束，并使每个agent从h个顶级类中获得的总概率份额最大化。每一个的变量表示Agent为她的顶级Indi和Erence类中的对象接收的总p可劫性份额。约束条件（1）和（2）加强了线性规划使mi n∈.约束（3）和（4）使得到的随机ass排列是可行的，约束（5）要求赋值与三元组中指定的要求一致。(，，(0)∈)=maximizex,h,s。t.≥±[1]x∈(8]，≥±[2]x≤(3)x∈Δd(4)x∈(8)，≥±[2](4)x∈(5)h，≥0.图1：约束串行规则3.1机制所用的线性规划我们现在可以正式地描述约束串行规则机制。机械在多个回合中进行。我们对每个agent进行初始化=，并且对每个agent进行初始化的时候，我们对每个agent进行初始化的时候，我们对每个agent进行初始化的时候，初始化的时候，初始化的时候，初始化的时候，初始化的时候，初始化的时候，初始化的时候，初始化的时候，初始化的时候，初始化的时候，初始化换句话说，在内部，我们考虑了分配给agent的对象的总p可劫性份额。让denote表示分配给agent的顶级indi类中对象的总概率份额。我们使用图1中描述的li near程序来构造一个可行的随机赋值ent，使得最小值最大化。该机制包含一组瓶颈代理。从本质上来说，这些都是这一轮目标的代理人。由于我们处理的是任意的线性约束，所以对瓶颈代理的认识需要比Kat ta和Sethuraman(2006)更微妙。我们将其定义为一个极小的Agent集，这样，在求解线性规划时，只试图最大化该集中Agent的效用，也会产生相同的目标值。我们对瓶颈代理的认识是该机制有效性及其e-ciency和fai rness性质的核心。最后，一旦发现了代理的瓶颈集，我们就会更新，以保证在以后的几轮中，每个代理从其最大的类中获得他承诺的概率份额最少，然后增加所有这些代理的阈值。然后，该机制进入下一轮，该过程继续进行，直到每个agent收到的总概率份额为1。Algorith m1给出了算法的完全形式化描述，我们给出了一个简单的例子，在一个有约束的分配问题上，Algorith m1初始化为：（1,2,）：（1,2,）：（1,？）：（1,？）：（1,？）：（1,？）：（1,）：（1,）：（1,）：（1,）：（1,）..do(x，h，)à(，，(0)∈)；if=1thenxèx；终止；Elsex找到一个小马尔集，使得(，，(0)∈)有obj ecti ve值；update+1={(，0，，)∈}；update+1=8+1‰∈OtherwiseEndendAlgorithment1：约束串行规则说明了我们的约束串行规则。示例3.1。一个具有三个代理={1,2,3}和三个对象={,,}的分配问题。我们的目标是得到一个满足通常的双随机约束的赋值，即p∈，=1‰，和p∈，=1‰.在addit中，有两个附加约束:1，+2，≤0.5和1，+2，≥0.5。代理的首选项如下所示。：：{，}：我们通过这个例子来说明我们的机制是如何工作的。在这一轮中，我们初始化了一个最大值=min{1,2,+2,3,}的可行解th，并求解了一个线性p rogram，得到了一个最大值=min{1,2,+2,3,}的可行解th。在gi ven约束条件下，一个pot o p timum soluti on分配1，=2，=3，=0.5以得到=0.5。在这个例子中，具有代理1或代理3的单例集都可能是瓶颈集。

这是因为约束1，+2，≤0.5阻止代理1接收更大的ob ject概率共享。类似地，约束1，+2，≥0.5阻止代理3接收对象的大概率共享。假设我们选择代理1作为瓶颈代理。然后，weincrement@=2和maintein@@=@=1。我们还设置=(1,1,0.5）来表示agent 1必须继续获得其最优选择的0.5个。在第二轮中，我们再次求解线性规划，以找到一个可行解t，它现在最大化=min{1,+1,2,+2,3,}。如前所述，在任何可行的解决方案中，agent3不能接收到超过0.5量的对象，因此我们得到=0.5。在这种情况下，代理3是唯一的瓶颈代理，正如前面我们在创造她的Indi和Erence阈值，并将三重（3,1,0.5）添加到。同样地，在第三轮中，我们求解线性规划，得到一个最大值=min{1,+1,2,+2,3,+3,}的可行解。然而，1，+2，≤0.5和1，+2，+3，=1这两个约束条件一起意味着3，≥0.5，因此3，+3，≤0.5。因此，我们有=0.5，代理3是机器人的高领代理，我们增加她的indi-erence阈值，并将三重（3,2,0.5）添加到。在第四轮，线性规划试图找到一个可行的解决方案，该解决方案尊重所有约束，并最大化=min{1,+1,2,+2,3,+3,+3,}。在这种情况下，一个锅的op timum溶质离子分配1，=0。5,1,=0.25,2,=0.75,3,=0。5,3,=0。25得到=0.75。由于约束1，+2，=0.5已经很紧，而对象h也完全相同，代理1和代理2都在th是roun D的瓶颈集内。通过增加agents b的Indi-erence阈值，使其分别为：3,2,0.75）和（2,1,0.75）。最后，在第4轮中，我们再次求解线性规划，得到一个既满足所有约束条件，又使=min∈{,+,+,}最大化的可行解。对于任何可行的解决方案，+，+，=1，我们得到=1和机制项。该机制的结果是满足所有约束条件的任何可行解决方案。对于本例，这种唯一的解是由下面的随机赋值给出的。a b c1 0.5 0.25 0.252 0 0.75 0.253 0.5 0 0.55.2性质证明了Al gorithm 1中提出的约束Serial规则是好的，并且总是产生一个可行的随机赋值。命题3.1。Algori thm1终止并总是产生一个可行的随机赋值。我们观察到，在任何一个步骤中，总是有一个可行的解决方案。这是因为，对于任何>1，来自前一个迭代的s olution（-1,-1,-1）继续是一个可行的olution；而对于=1，由于赋值约束是可满足的，所以保证了可行解的存在。在任何步骤中，通过观察所有Agent的集合都满足了所需的约束，很容易看出Agent的瓶颈集是保证存在的。此外，我们还观察到，任何一个诸如son*=(tor*)这样的中介物*∈，都不会在套头毛衣中应用ear。这是因为，对于任何这样的agent*∈，l线性程序(，，(\\\\\\\\}，，(\\\\\\\\\\}因此，在任何一个步骤中，我们都增加了至少一个试剂的临界值。最后，通过对feasibl e赋值的认识，当π=(ef),(ef)时，我们可以设置=p∈，=1,从而得到=1,算法终止。最后，由于图1中的线性规划显式地主要考虑约束x≤、ΔD,所以该机制是可行的。然后我们继续展示两个技术引理。

引理表明，即使我们允许任意的线性约束对随机的ass排列，可行的litypolitope在h和变量上的投影也具有理想的单调性。具体而言，h变量上的t个约束可以表示为一组线性上限约束，其中只有一个非负约束。引理3.2。修正算法的任何步骤。设为多面体，由（,，(0)∈)中的约束条件所修饰，且设={（h,）}（x,h,）∈}为多面体的投影。则存在非负的mat RIX~和非负向量~，使得=≥，λ∈~h≤~h，≥0证明。通过Fourier-Motzkin定理，我们知道用Fourier-Motzkin消元法也可以得到多面体t帽。由于只涉及到的约束不包含任何x变量，这些约束在多面体中保持不变。设～=[～]和～=[～]表示在傅里叶-莫特基消元后确定的变量h上的最小线性约束。我们现在需要证明that～和～是非负的。我们观察到多面体在h变量上是向下闭合的，即对于任何h′≤h，如果(h，)∈，则存在一个\'≤，使得(h′，\')∈.这是因为，根据我们的认识，如果(h，)∈，那么存在一个x，使得(x，h，)∈.进一步，观察th e多面体（参考文献1）可知(x，h\'，\')al so属于w h ere\'=mi n∈\'，因而(h\'，\')∈.现在，为了矛盾，假定存在一个约束，使得某一多面体的entr y～<0。由于thi s约束i不是冗余的，所以存在一个向量～h∈R+，使得thi s约束是唯一的bi n ding约束，即p～=～，并且对于所有的将\'∈R+定义为\'=～,(ε)\\\\{}和\'=0。最后，如果矩阵~是非负的，向量~有一个负项，那么polyt ope一定是空的。Sin ce保证为非EM pty，我们必须知道~不是n-负的。下面的引理说明了瓶颈agent的重要性。非正式地说，如果在算法的某一步是b个Ottreneck agent的集合，那么在没有其他agent的情况下，任何agent都可以为她的顶级类分配更高的总分配。这个引理对于证明约束序列rul e ProducesConducted Ordinal e cient outcom e以及证明它的公平性是至关重要的。引理3.3。求出a的任一步，并设(x，h，)表示(，，(0)∈)的最优解。那么y=(，)∈，∈R+这样1。y≤，y∈ΔD2。((8))≥，ABER(，0，)∈3。具有至少一个严格不等式。证明。设为多面体，由(，，(^)∈)中的约束所修饰。设={（h,）}（x,h,）∈)}是h与变量上的投影n。由Lemma3.2,存在非负矩阵~=[~]和一个非负向量~，使得=≥，λ∈~h≤~h，≥0By,(x，h，)是(，，(0)∈)的最优解。设~H被定义为~=for all,且~=0 for all。我们现在有(x，~h，)也是一个最优的solutionto(，，(0)∈)。因此，(～h，)不位于多面体的内部。因此，在这一点上，约束中至少有一个～h≤～必须是t轻的，即，存在s这样的约束:p∈～～=～。我们现在考虑两种情况。情况1:～>0对所有的特例。针对引理存在的矛盾，对引理的前提进行了修正。对于任何一个agent,设\'=((8)),所以我们对于所有的autler至少有一个严格不等式。因此，由于(y，h′，)是(，，(0)∈)的可行解，我们有(y，h′，)∈.通过了解，我们有(h\'，)∈.

然而，我们有x∈~′>x∈~=x∈~=~=~，这与(h′，)∈.情形2:~=0对于某一点来说是矛盾的。考虑集合\'=\\{}。我们现在有p∈\'～=～，设‘是由(\',，(0)∈)中的约束所限定的多面体，而’是它的投影。由于是最小瓶颈集，所以存在一个(Y\',‘,\')∈\'使得\'>和\'=\',(+)∈\'。因此，我们有x∈\'～\'>x∈\'～=x∈\'～=～，因此(\'，\')\'。但是，这与(y\'，\'，\')∈\'的事实相矛盾。我们现在准备证明约束序列规则具有约束序号的e-cient赋值。定理3.4。对于任何偏好方案和约束集ΔC(t),算法的结果通常受约束。证明。设x是该算法对任意偏好项和约束集ΔC(.)的解。为了证明x是受约束的，它表明如果在x\'(.)x处存在XSX\'∈ΔC(.)这样的t h,则\'((0))=((0))，对于all∈，对于all∈(1，2，...，(eum)}。我们用矛盾来证明th。对于任何一个圆，设(，，)表示(，，(^)∈)的最优解。对于瓶颈集中的任何agent，该机制将为其顶级Indi和Erence类收集agent收到的累积分配。因此我们有((8))=((8))=。对于一个矛盾，设为算法中的最后一步，使得对于某个agent来说，\'((0))≠((0)).由于x\'(.）x对于al l∈，它一定是\'((0))>((0))=((0))=。另外，对于所有的主体，我们有\'((8))≥((8))=。此外，由于X\'是一个可行的随机赋值，我们有X\'∈ΔD和X\'≤.最后，s ince round是从x开始的时间x′dihile ers，′((0))=((0))≥，λ(，^，)∈.这与Lem MA3.3是直接矛盾的。因此，x通常是受约束的。在任意约束条件下，如果一个主体的约束比另一个主体的约束更大，那么多个主体之间可能不可避免地存在嫉妒。然而，正如下一个定理所表明的，我们可以保证任何一对相同类型的代理之间没有嫉妒。定理3.5。在任何偏好上，约束序列规则保证s ame类型的代理之间没有嫉妒。设x表示算法的结果。Cons ider任何一对相同类型的代理。对于agent所嫉妒的矛盾，假设t在这里存在一个indiantic的Erence类，这样((th))<(th))。让我们来表示当在瓶颈中存在时算法的步骤。设(x，h，)表示(，，(0)∈)的最优解。由于agent处于瓶颈集中，所以该机制是agent对其顶级类的累计分配。因此，我们有((8))=((8))=.让我们考虑两种情况：情况1：假定agent是我们有((8))=((8))=。但是，当((0))>时，一定存在一些obj ect来使得，>0。情况2：假定agent。通过构造n,对于任意三元组(，0\'，)∈，我们有0\'≤0-1，(0\')=≤.在任何一种情况下，由于((8))=<1，都存在一个对象(0)，其中，>0。在任何一种情况下，由于((0))=<1，所以存在一个对象(0)。Let0<<min{,,,}是一些固定的常量。我们现在可以得出一个新的结果y如下。让\'，\'=\'，\'对于所有的ob jects\'∈and代理‘{，}。对于agents\'∈{，}，let\'，\'=\'，\'forall对象‘{，}。让，=，+，=，-和，=，-，=，+。Sinceagents和是相同类型的，我们有，+，=，+，，对于所有的对象，wemust有y=x≤b。另外，通过构造我们有y∈ΔD，即y是一个可行的结果。