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

855

收藏 2022-04-16

摘要翻译：
研究了在任意线性约束条件下，当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)

马上下载

扫码加我拉你入群

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

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

全部回复

kedemingshi

2022-4-16 11:17:05

完整优先级上的约束串行规则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)。在随机分配机制的背景下，这与代理报告每个对象的基本效用的基本原则形成了鲜明的对比。

扫码加我拉你入群

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

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

mingdashike22

2022-4-16 11:17:11

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)。

扫码加我拉你入群

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

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

何人来此

2022-4-16 11:17:18

我们的约束序列规则对文献进行了总结，给出了这些机制的一个通用的推广，并对全偏好域进行了扩展。我们证明了即使在一般的约束条件下，约束序列规则仍然保持了概率序列机制的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)∈.

扫码加我拉你入群

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

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

何人来此

2022-4-16 11:17:24

设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（同类型代理人之间的无嫉妒）。

扫码加我拉你入群

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

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

mingdashike22

2022-4-16 11:17:30

如果对于每一对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的总概率份额。

扫码加我拉你入群

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

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

点击查看更多内容…

nandehutu2022

2022-4-16 11:17:36

图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的单例集都可能是瓶颈集。

扫码加我拉你入群

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

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

mingdashike22

2022-4-16 11:17:42

这是因为约束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,所以该机制是可行的。然后我们继续展示两个技术引理。

扫码加我拉你入群

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

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

大多数88

2022-4-16 11:17:48

引理表明，即使我们允许任意的线性约束对随机的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\'，)∈.

扫码加我拉你入群

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

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

mingdashike22

2022-4-16 11:17:54

然而，我们有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是一个可行的结果。

扫码加我拉你入群

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

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

mingdashike22

2022-4-16 11:18:00

此外，通过我们对对象的选择，我们对所有(，0，0)∈F有((0))≥((0))≥(0，0))，对所有∈F也有((0))≥((0))。然而，由于((8))>((8))≥，这与Lemm A3.3相矛盾。3.3计算复杂性如命题3.1所示，该机制在最多的回合中终止，并分别表示不同的主体和对象的nu mber。在每一轮中，该算法解决了一个线性prog ram的实例来计算。进一步，该算法利用eeds对瓶颈Agent集合进行筛选。我们现在证明了在多项式时间内，通过求解至多线性规划的非齐次，可以找到它。我们回想起，任何一个极小的主体集，其（,，(0)∈)的目标值等于。算法2提供了一个简单的程序来筛选这样的氨基集合。我们将初始化为所有代理的集合。在每一步中，算法都考虑从。如果去掉这样一个agent使线性规划获得更高的目标值，那么很明显agent一定属于瓶颈。另一方面，如果线性规划obtai ns的ob jective值仅为，那么agent可以安全地从考虑si中删除，因为它是一个较小的候选集。input：,..,do（{},，(0)∈)的目标值；如果==then（{}）endendReturn算法2：寻找瓶颈集的过程算法M2至多以迭代结束，因此总的来说，约束规则的每一轮最多需要求解(+1)个线性p个rograms。因此，算法1可以在约束的大小、代理和对象的数量为多项式的时间内执行。3.4可实现性对象分配机制中的随机化经常被用作从预先的角度结合公平的工具。随机分配机制的结果被视为确定性结果之上的概率分布，从这种分布中得出的结果是在实践中得到实现的。根据Birkho-von Neumann定理，每个双随机的随机分配都可以实现为对可实现的确定性分配的抽签，即每个agent都是一个对象，每个对象都被分配给一个agent的deter ministic分配。然而，在存在任意约束条件的情况下，这样的对满足这些约束条件的deterministic赋值的抽奖分解可能不存在。下面的例子说明了这种情况。考虑一个简单的例子，一个主体={1}，三个对象={，,}，在存在约束1，+1，≤2/3，1，+1，≤2/3和1，+1，≤2/3的情况下，随机问题的一个潜在的可行解是设置1，=1，=1，=1/3。然而，可以很容易地看出，并不存在满足这三个约束的确定性分配，仍然存在Ns1,+1,+1,=1。在许多实际应用中，人们可以表明，满足这些约束的任意随机分配都可以表示为对Deter-ministic分配的抽奖。例如，Nguyen等人对于具有有限补点的组合ass对齐问题。（2016）证明人们总是可以将一个可行的分配分解为一个对determi nistic分配的抽奖，这里每个对象的容量被至多加法所侵犯，其中表示最大外滩的大小。

扫码加我拉你入群

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

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

mingdashike22

2022-4-16 11:18:07

在第4节的具体应用中，我们对d和ai进行了具体的实现。另一方面，我们对随机分配解施加约束的模型，广义上是对后确定性结果施加约束的方法。正如Balbuzanov(2019)所指出的，任何一组关于后置任务的树状约束都可以用随机赋值上的一组l线性不等式来表示。虽然这样的约简总是存在的，但它不是计算上的。4应用本节，我们讨论了如何将约束序列规则应用于约束对象分配的几个具体应用。4.1无约束对象分配我们可以将我们的模型应用于无约束对象分配问题，只要对所有的在这种情况下，约束条件下的随机分配输出与Katta和Sethuraman(2006)的扩展概率串行算法所给出的随机分配输出一致，本文讨论了扩展概率串行算法。在每一轮中，扩展的概率算法构造了一个Generow n et工作，其中Agent在该轮中的对象集合中选择他们最喜欢的红色对象。在参数最大-最小-最小-最小-最小-最小-最小-最小-最小-最小-最小-最小-最小-最小-最小-最小-最小-最小-最小-最小-最小-最小-最小-最小-最小-最小-最小-最小-最小-最小-最小-最小-最小-最小-最小-最小-最小-最小-最小-最小-最小-我们注意到，这个agent集合恰恰是这个roun d中最受约束的集合，即agent能从她的偏好对象中得到恰好是λ()（而不是更多）的概率共享。在constrainedseri al r ule算法中，由于没有其他约束限制t h e随机作为签名，因此同一组智能体将被选为t he bott Renekk集。4.2双层次约束Budish et al.（2013）考虑了具有一般配额约束的对象分配问题，提出了一大类普遍可实现的约束，称为“双层次约束”，即满足这些约束的任意随机分配都可以在满足相同约束的确定性分配上实现。它们的约束形式为≤p(，)∈，≤，其中×是一组agent-object对，x是确定性分配，并且都是整数。constraintstructure H=(，)由这些约束的集合组成。onH的一个附加要求是它必须包括所有的sin gleton集。一个约束结构H是一个层次结构，如果对于每一个，\'∈H，\'or\'或\'orTM\'=.最后，H是一个b I-层次结构，如果它是H,那么H=HühandHüH=.是一个b I-层次结构，那么H是一个b I-层次结构，如果H是H,则H是b I-层次结构。布迪什等人。（201 3）提出了两层次配额约束下的对象分配的广义概率串行机制。然而，它们的机制只对上限配额起作用，并假定所有的下限=0。相反，我们可以直接使用我们的约束序列rul e算法m中的约束结构H中的不等式（即使在偏好关系中存在间接关系的情况下），通过对所有的(，)∈R的ΔC(Ⅵ)={x∈ΔD≤x(，)∈H}进行推导，从而推广了Budish等人的方法。即使对于下限配额限制，我们也能做到这一点的关键技术创新在于，我们的算法在任何时间都向前看，以确保在任何时间得到的部分会导致一个可行的随机分配。4.3类型依赖的分布限制Sashlagi等人。（2020）不符合ABI-层次结构的学习类型依赖的d Istribute约束。在这种设置中，每个agent与一个type age相关联，其中表示一组类型。Let表示一组任意的agent类型，Let更是表示一个任意的对象。

扫码加我拉你入群

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

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

大多数88

2022-4-16 11:18:13

一个单一的con strint是t-h-e形式，≤pε，≤，即该机制对一个给定对象上属于特定agent类型集合的所有agent的总分配量施加限制和上限配额。如前所述，可以很容易地看出，这种分布约束可以很容易地在我们的框架中表示。由于约束不符合一个双层次结构，我们的机制的结果不能总是作为对可行的决定性分配的抽签来实现。然而，正如Ashlagi等人所表明的那样。（2020）将满足这些约束的随机分配分解为一个几乎可行的确定性结果上的分布，其中每个约束和上限约束都是由at mo st.4.4显式的事后约束Balbuzanov(2019)考虑了当我们是givenan显式的事后可行分配列表，并且t h e随机分配必须作为对t h es e分配的抽奖而隐含时的随机obj ect分配问题。对于一个偏好，设(th)是所有允许确定性赋值的集合，ΔC(th)是集合C的凸壳。他证明了对于每个(th)，存在一个由矩阵参数化的极小约束集，对于所有(，)∈×和约束，≥0,且向量≥0使得ΔC(th)={x∈ΔD x≤}。Hegenerali利用概率SERIAL机制将这些不等式结合到Agent具有严格偏好的情况下。4.5组合赋值是另一类p roblems，其中ou r机制可以应用于当偏好表现出复合性时，将不可分对象的包分配给Agent的问题（Budish（2011）；Budish和Cantillon(2012)；Nguyen et al.(2016))。形式上，设为一组底层对象，其中每个对象都是副本。一个物体的bun可以用avector表示，在N+中，这个向量的第1个坐标对应于该物体的拷贝数，并且N+=Nü0}。设={∈N+P∈≤}最多是所有大小束的集合。我们假设每个包在单个副本中可用。每个agent都有兴趣In从集合中消耗一个bundle，并且在集合上有一个Compleet e和传递偏好。这类问题中的一个常见应用程序是课程分配问题。每个学生最多只能被分配一个课程表，其中每门课都有一定的座位数。这个可行的随机分配集合可以用下面的一组con-straints来描述，该集合使任一物体的分配总量至多等于它的供应量。在每个偏好条件下，我们有:ΔC(t)=ΔC={∈ΔDx∈X∈·,≤，Δ∈}。从定义2.2中可以看出，所有的智能体在能力约束条件下都是相同类型的。在此之前，受约束的seria l ru le保证了通常受约束和无嫉妒的结果。此外，正如Nguyen等人所指出的那样。

扫码加我拉你入群

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

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

nandehutu2022

2022-4-16 11:18:20

（2016年），该机制的任何结果都可以作为对违反供应限制的确定性分配的抽签来实现。参考abdulkadirooglu，阿蒂拉和泰芬·桑梅斯，“学校选择：一种机制设计方法，“美国经济评论，2003年，93(3)，72 9-747.阿克巴普尔，穆罕默德和阿夫申·尼克扎德，“近似随机分配机制”，2014.阿什拉吉，伊泰，阿明·萨贝尔一世，还有阿里·沙梅利，“分布约束下的分配机制”，OperationsResearch,2020年，68(2)，467-479.巴尔布扎诺夫，伊万，“约束随机匹配”技术报告，工作文件2019.Biró，佩特，塔马斯·弗莱纳，罗伯特·W·欧文，和大卫·F·曼洛夫，“大学招生申请低配额和普通配额”，“理论计算机科学，2010年，411(34-36)，3136-3153.博戈莫尔纳亚，安娜，“随机分配：修改系列规则，“经济理论杂志，2015年，158,308-318。和埃尔韦·穆林，“随机分配问题的新解法”，经济理论杂志，2001年，100(2)，295-328.布迪什，埃里克，“c ombinatorial指派问题：收入相等的近似共--复合均衡“,《政治经济学杂志》,2011年，119(6)，1061-1103。埃斯特尔·坎蒂隆，“多单位分配问题：课程分配的理论和证据，“美国经济评论，2012年，102(5)，2237-71，车延九，小岛富仁、保罗·米尔格罗姆，设计随机分配机制：《美国经济评论》，2013年，103(2)，585-623.陈，颜和Tayfun S"onmez，“改善校园住房的安全性：一项外周研究，“美利加经济评论，2002年，92(5)，1669-1686.德拉克雷塔兹，大卫，斯科特·杜克·科米纳斯，亚历山大·泰特尔博伊姆，“难民安置”，牛津郡大学经济系工作文件，2016.埃切尼克，费德里科和M Bumin Yenmez，“如何控制受控学校选择”，《美国经济评论》，2015年，105(8)，2679-94。，安东尼奥·米拉莱斯，而张俊，《受约束的伪市场均衡》，arXiv预印本arXiv:1909.05986，2019年。埃勒斯，拉斯，伊萨·哈法利尔，M Bumin Yenmez，穆罕默德·耶尔德勒姆，“有控制的cho冰约束的学校选择：硬边界与软边界，“经济组学理论杂志，2014年，15 3,648-683.埃尔迪尔，Aytek和Haluk Ergin，经济理论杂志，2017,17,268-292。Fleiner，Tamás和Naoyuki Kamiyama，《用较低的配额稳定并购交易的拟阵分析》，《数学运筹学》，2016年，41(2)，734-744。Foley，Duncan K,《资源分配和产业部门》，《耶鲁生态经济学论文集》，1967年。Fragiada kis，Daniel和Peter Troyan，《在硬分配约束下改进匹配》，Theo reticalEconomics，2017，12(2)，863-908。Goto，Masahiro，Ryoji Kurat a，Naoto Hamada，Atsushi Iwasaki和Makoto Yokoo，《用等级制度改进非浪费匹配的《最低配额》，载于“2015年自治代理和多代理系统国际会议的Pro ceedings”，第2页。

扫码加我拉你入群

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

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

可人4

2022-4-16 11:18:21

1887-1888.哈法利尔，伊萨·埃，M Bumin Yenmez，穆罕默德·耶尔德勒姆，“择校中的消极作用”，理论经济学，2013年，8(2)，325-363.滨田，科基，岩山一夫、而宫崎修一，“低配额的hosp itals/resident问题，”算法，2016年，74(1)，440-465.Hylland，Aanund和Richard Zeckhauser，《个人对职位的公平分配》，政治经济杂志，1979年，87(2)，293-314.镰田，雄一郎与小岛富仁、“分配约束下的e？cient ma tching：理论与应用，“美国经济评论，2015年，105(1)，67-99.卡塔，Akshay-Kumar和Jay Sethuraman，“在完全优先度上的ran dom a signment问题的解决方案”，《经济理论杂志》，2006年，131(1)，231-250.小岛，Fuhito，“多个不可分割对象的随机分配”，2009年，57(1)，134-142，“学校选择：“游戏和经济omic行为”的不可能性，2012年，75(2)，685-693.Kominers，斯科特·杜克和泰芬·桑梅斯，“为匹配中的多样性设计”，在“欧共体”2013年，第603-604页，Nguyen,Thanh，艾哈迈德·佩瓦·恩迪，和拉凯什·沃赫拉，经济理论杂志，2016年，165，20 9-241.阴道，Marek和M·乌特库·翁弗，“分解随机机制”，《数理经济学杂志》，2015年，61，21-33。罗伯逊，杰克和威廉·韦伯，《切蛋糕算法：如果可以，就要公平》，AK彼得斯/CRC出版社，1998年。罗斯，Alv in E，Tayfun S"onmez和M Utkuünver，《两两肾脏Exchange》，经济理论杂志，2005年，125(2)，151-188。苏，弗朗西斯·爱德华，《出租和谐：公平分工中的斯佩纳引理》，美国数学月刊，1999年，106(10)，930-942。韦斯特卡议员，亚历山大，《德国大学adm issions系统的分析》，经济理论，2013年，53(3)，561-589.ylmaz，zz.具私人捐赠的概率序列机制，“博弈与经济行为，2010,69（2）,475-491。

扫码加我拉你入群

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

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

扫码加我 拉你入群

扫码加我 拉你入群

扫码加我 拉你入群

扫码加我 拉你入群

扫码加我 拉你入群

扫码加我 拉你入群

扫码加我 拉你入群

扫码加我 拉你入群

扫码加我 拉你入群

扫码加我 拉你入群

扫码加我 拉你入群

扫码加我 拉你入群

扫码加我 拉你入群

扫码加我 拉你入群

扫码加我 拉你入群

分享

扫码加好友，拉您进群

扫码加我拉你入群

扫码加我拉你入群

扫码加我拉你入群

扫码加我拉你入群

扫码加我拉你入群

扫码加我拉你入群

扫码加我拉你入群

扫码加我拉你入群

扫码加我拉你入群

扫码加我拉你入群

扫码加我拉你入群

扫码加我拉你入群

扫码加我拉你入群

扫码加我拉你入群

扫码加我拉你入群