基于策略和无嫉妒的房屋分配机制

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

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

立即领取

感谢您参与论坛问题回答

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

+2 论坛币

摘要翻译：
考虑了当Agent对对象有严格偏好时，将不可分对象分配给Agent的问题。在分配机制中，效率、公平和激励等相互竞争的概念之间存在着内在的权衡。因此，当试图在第三维度上改进时，自然会考虑在它们最强的概念中满足这三个性质中的两个的机制。在本文中，我们的动机是以下问题：是否存在一个策略证明和无嫉妒的随机分配机制比等分更有效？我们在这篇论文中的贡献是双重的。首先，我们进一步探讨了策略证明机制中效率与无嫉妒之间的不相容性。我们定义了一个比事后效率弱的新的效率概念，并证明了任何策略证明和无嫉妒机制都必须牺牲效率，即使是在这个非常弱的意义上。接下来，我们引入了一个新的机制家族，称为两两交换机制，并做出了令人惊讶的观察，在这个类中，策略证明等同于嫉妒自由。我们刻画了这个家族中所有中立的和策略证明的（因此也是无嫉妒的）机制的集合，并表明它们承认一个非常简单的线性表示。
---
英文标题：
《Strategy-proof and Envy-free Mechanisms for House Allocation》
---
作者：
Priyanka Shende and Manish Purohit
---
最新提交年份：
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 consider the problem of allocating indivisible objects to agents when agents have strict preferences over objects. There are inherent trade-offs between competing notions of efficiency, fairness and incentives in assignment mechanisms. It is, therefore, natural to consider mechanisms that satisfy two of these three properties in their strongest notions, while trying to improve on the third dimension. In this paper, we are motivated by the following question: Is there a strategy-proof and envy-free random assignment mechanism more efficient than equal division?   Our contributions in this paper are twofold. First, we further explore the incompatibility between efficiency and envy-freeness in the class of strategy-proof mechanisms. We define a new notion of efficiency that is weaker than ex-post efficiency and prove that any strategy-proof and envy-free mechanism must sacrifice efficiency even in this very weak sense. Next, we introduce a new family of mechanisms called Pairwise Exchange mechanisms and make the surprising observation that strategy-proofness is equivalent to envy-freeness within this class. We characterize the set of all neutral and strategy-proof (and hence, also envy-free) mechanisms in this family and show that they admit a very simple linear representation.
---
PDF下载：
--> English_Paper.pdf (396.51 KB)

2022-4-16 10:48:10 上传

扫码加我 拉你入群

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

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

分享0 收藏0 回帖

关键词：分配机制 Contribution Presentation Theoretical equilibrium

房屋分配的策略证明和无嫉妒机制*Priyanka Shende*California University of California,BerkeleyManish Purohit of Google Research,Mountain ViewDate：2020年11月2日我们考虑了当Agent对对象有严格的偏好时，将不可分割的对象分配给Agent的问题。在分配机制中，在电子商务、公平和激励等相互竞争的概念之间存在固有的贸易关系。因此，在试图改进第三维度的同时，自然要考虑在它们最强的概念中满足这三个性质中的两个的机制。在本文中，我们的动机是这样一个问题：是否存在比等分更有效的策略证明和无嫉妒的随机分配机制？我们在本文中的贡献是双重的。首先，在策略证明机制类中，我们探讨了e-ciency和无嫉妒之间的不相容性。我们发现了一个新的概念，它比事后的e_ciency弱，并证明了任何s_trategy-free机制都必须对e_ciency进行修改，即使在这个非常弱的意义上也是如此。其次，我们引入了一个新的机制族，称为成对交换机制族，并在这类机制族中证明了无嫉妒机制与无嫉妒机制的等价性。我们刻画了这类机制族中所有中立和策略证明（因此也是无嫉妒机制）机制的集合，并表明它们承认一个非常简单的线性表示。JEL分类:C78，D61，D63，D71关键词：随机分配；序数的；策略证明；嫉妒--自由；平等分割*我们感谢Haluk Ergin、David Ahn、Yuichiro Kamada、Chris Shannon和Shachar Kariv提供的有益的commen tsand建议。\\email:priyanka.s@berkeley.edu\\email:mpurohit@google.com1介绍房屋分配问题是一个有趣的、令人讨厌的资源分配问题，它涉及在不使用货币转移的情况下将不可分割的e对象分配给代理人。在许多现实世界的应用中，金钱转移是不可取的，如将学生安置到publicschools（Abdulkadiro-lu and s"onmez，2003)、课程分配（Budish,201 1）、器官捐赠（Roth et al.，2005)和校园内housi ng allo cation（Chen and s"onmez，2002)。在classicalordinal设置中，每个agent报告一个严格的偏好排序，并向agent输出一个对象分配。一种理想的市场机制具有良好的品质；它必须是不可操纵的，公平和公正的。由于对象是不可分割的，任何向代理分配对象的行为都必然会被认为是不公平的，事后的。因此，Randomizati on通常被用作恢复公平的工具。也许最自然的随机化机制是随机的Seria ldoctorship(RSD)机制，也称为随机优先机制。在该机制中，agent被随机地统一排序，每个agent按照该顺序从可用对象集合中依次选择自己喜欢的对象。众所周知，RSD满足许多有吸引力的属性（Abdulkadiro奥卢和S"onmez，1998；Bogomolnaia和Moulin，2001)。它是策略证明的，这意味着揭示真实的偏好总是每个Agent的主导策略。它也是后电子商务，这意味着它总是导致电子商务最终的结果。然而，它只在平等对待平等人的弱意义上满足公平（在这种情况下，具有相同偏好的代理人面对相同的对象彩票）。公平的一个更强的概念是嫉妒自由。由Foley(1967)引入，嫉妒自由的经典认知要求每个代理人都应该更喜欢她的分配而不是其他人的分配。这一概念常常被视为公平的黄金标准，在许多直接的解决方案中，如资源分配(Foley，1967)、蛋糕切（Robertson and Webb，1998)和租金划分（Edward Su，1999)。

在随机分配机制的背景下，Bogomolnaia和Moulin(2001)利用有限阶随机占优关系对这一性质进行了研究。他们提出了概率序列(PS)m机制，该机制比RSD具有更强的e-ciency和公平性。PS是没有嫉妒的。然而，这种机制不是策略证明的。unfor tunately,越来越多的工作（Bogomolnaia and Moulin，2001；Martini，2016；Nesterov，2017；Zhou,1990）已经证明了e-cient之间的内在不相容性，1a机制通常是e-cient,如果它的结果不是由任何其他随机分配随机支配的。公平性和策略证明性。Bogomolnaia和Moulin(2001)证明，没有任何机制同时满足策略证明性、有序性和平等对待平等性。最近，Nesterov(2017)展示了策略证明、嫉妒自由和后验之间的不相容性。在有了这些交易条件的情况下，当人们希望将公平性、公平性和策略性这三个属性中的两个属性充分利用到它们的最强属性时，就很自然地考虑可以设计的机制，而这些属性的选择取决于应用，并试图在第三个维度上进行改进。由于住房分配机制中rando mization的主要动机是提供缺憾性保证，因此本文将重点放在满足嫉妒自由的策略性rando m分配机制上。事实上，近年来，在经济学和计算机科学的交汇点上，对公平的兴趣重新抬头。例如，参见Moulin(2019)和EC workshop2关于公平资源位置的最新调查，以获得一个出色的概述。据我们所知，在所有代理之间平等分配每个对象的equal divisi on(ED)机制是唯一已知的策略证明和嫉妒的机制。然而，由于th is机制完全忽略了代理的偏好，所以它几乎总是ine-cient。这就提出了一个问题：除了等分机制之外，还有其他策略证明和无嫉妒机制吗？1.1我们的贡献给出了一个强有力的结果，证明策略证明和嫉妒自由机制即使在很弱的意义上也必须要有策略证明和嫉妒机制。我们发现了一个比后置e_cience弱得多的无争用e_cience概念，并证明了没有一个策略证明机制可以满足嫉妒自由，是无争用e_cience。因此，我们的结果加强并包容了Bogomolnaia和Moulin(2001)和Nesterov(2017)关于后验、策略证明和无嫉妒不相容的硬度结果。为了设计新的策略证明和无嫉妒机制，我们在4.1节中认为，任何随机机制都可以认为是从等分机制出发，允许每对主体交换对象的概率份额。ese交换可以代表传递函数的优先权。接下来，我们将注意力限制在一个简单的转移函数类上，它只依赖于2019年ACM经济与计算会议上的公平问题对agents2研讨会的偏好:https://users.cs.duke.edu/~rupert/fair-division-ec19/index.html，它涉及到交换，并描述了允许这种转移的称为两两交换机制的机制家族。在第4.2节中，我们展示了在这类机制中策略证明和嫉妒自由之间惊人的等价性。我们给出了这个家族中中立的、策略证明的和无嫉妒的机制集的刻画i第4.3节。这些机制有一个简单的li近表示，其中任何对象在一对Agent中的转移由该对象在Agent的p引用顺序n GS中的相对秩决定。

最后在4.4节中，我们刻划了这类中所有Pareto-e-cient机制的s et。1.2其他相关工作本文补充了Hylland和Zeckhauser(1979)所开创的关于不可分e对象的随机赋值的广泛文献。他们采用了从平等收入中得到的竞争均衡(CEEI)解决方案来构造一个伪市场机制，该机制引起了代理人的von NeumannMorgenstern偏好而不是独立的，并给出了一个相对于效用函数而言是公平的解决方案（即事前公平和无嫉妒）。然而，i snot Strategy-prof.Zhou（1990）实际上表明（证明了Gale(1987)的一个猜想）不存在sati预先确定和平等对待平等的策略证明机制。当agent只报告对单个对象的顺序偏好时，最简单也是最广为人知的策略证明机制是串行独裁(SD)(Satterthwaite and Sonnenschein，1981；Svensson，1994)：使用agent的一个组合顺序，每个agent从剩余的obj集合中连续选择她最喜欢的对象。Abdulkadiro-lu和S"onmez(1998)表明这些只有Pareto e cient匹配机制。然而，尽管这些都是非常不公平的，但使用代理人的随机排序结果是在平等待遇的意义上恢复公平。Abdulkadirooglu和S"onmez(1998)也分析了由此产生的m机制RSD，并证明RSD等价于随机赋值机制的核心，其中每个Agents最初赋予一个随机一致选择的对象，然后该机制使用Gale的Top Trading Cycles(TTC)算法（Shapley and Scarf，1974)来获得随机赋值。在另一个成功的研究领域，有几篇论文侧重于描述满足某些期望性质的机制（族）。对于确定性机制，Svensson(1999)证明了串行独裁是唯一的群体策略证明和中立机制，Pápai(2000)引入了一种称为层次交换机制的机制，并证明了这些机制表征了群体策略证明、paretoe-cient和再分配证明机制。最近，Pycia和ünver(2017)展示了他们的交易周期机制表征了集团策略证明和Paretoe cient机制的全部类别。Bogomolnaia和Moulin(2001)表明，在随机机制中，当存在三个主体和三个对象时，RSD是满足策略证明性、事后e-ciency和平等对待平等的唯一机制，而PS是满足序数e-ciency、无evny和弱策略证明的唯一机制。Bogomolnaia和Heo(2012)；桥本等人。（2014年）；高级代表办公室(2014a、b)；Heo和Yülmaz(2015)提供了PS的其他公理特征。在大型常规市场中，Liu和Pycia(2016)表明，存在一种单一的行为，通常是嫉妒

.,我。所有主体的一组个人偏好构成一个偏好亲=()∈.让-=\\{}表示除agent以外的所有agent的首选项集。我们将使用=(=,=\',-{,}）来表示当agent的偏好是，agent的偏好是‘并且所有其他agent的偏好都由-{,}给出时的偏好。设R为所有个体偏好的集合，R为t h e为所有pos sible偏好的集合。a d永恒赋值是从to到b的集合，其中每个agent接收一个对象，并且y对象被恰好分配给一个agent。设D是所有确定性赋值的集合，随机赋值是确定性赋值上的p可劫性分布。随机分配=h，i∈，∈，可以表示为一个大小为×的dou b ly随机矩阵x，其中矩阵的每个元素表示agent被分配对象3的概率。设L(D)是所有可能的随机分配S的集合。矩阵的抛出表示agent在随机分配中收到的分配。这种分配仅仅是对象的概率分布。所有随机分配的集合用L（）表示，为了比较随机分配，我们将Agent对对象集合的偏好扩展到随机分配的集合L（）。设（,）={∈}为ofobjects th at根据偏好关系弱偏好对象的集合。例如，如果=h，，...,i,th en（,）={,....,}。当且仅当随机分配顺序根据Agent的偏好而随机支配时，Agent更喜欢一个随机分配序列来支配L()，而不是另一个随机分配序列来支配L()（表示为≥)。从形式上说，≥==x∈(，)，≥x∈(，)，，π∈IF≥，此外，还有一个对象，这样p∈(，)，>p∈(，)，，那么我们说agent严格地倾向于，它由>表示。最后，如果每个agent都更喜欢她所接受的随机分配而不是她所接受的随机分配，则随机分配占优势。一个随机赋值m机制是一个映射:R→L(D)，它将一个偏好profoile∈R与一个随机同化项∈L(D)相关联。为了便于说明，我们经常使用():=(())来表示机制中与偏好相关联的随机分配。设[]={1,2,...,}。设:→是一个permutati on,即a b ectio n自其自身。对于任意的偏好关系和置换，设（）表示按顺序对每一个对象应用t个置换得到的偏好关系。换句话说，obj ects是根据函数重新标记的。形式上，如果=h，，..，i and是一个permu式，那么()=h()，()，....,（）i.类似地，对于任何偏好Profile=()∈R，l et()=(())∈Be t他的偏好Profile=()=(())∈Be t是通过根据t o重新标记对象而得到的。设(，)根据偏好关系表示最多p个所指对象。最后，我们用(，)来表示对象的秩。3为了方便起见，我们常常把每一个对象看作是一个单位中的一个完全可分的好物，它将在各主体之间分配。将一个对象的分数单位分配给agent被解释为设置=.2.2机制的性质。我们现在正式地定义了我们在本文中所讨论的e-ciency、公平性和激励同胞性的概念。e-ciency。如果对于任何偏好，随机分配（）是Pareto-最优确定性分配S上的分布，则称随机机制是事后的。Bogomolnaia和Moulin(2001)提出了一个更强的e ciency概念。

如果在任何情况下，赋值（）不被任何其他随机赋值所省略，那么一个机制通常被称为e-cient。激励。如果报告真实的偏好是每个Agent的合适策略，那么一个机制就有助于策略证明(SP)。从形式上说，一个机制是策略证明的，如果对于每一个，对于每一个，R和\'∈R，≥(\',-)，where=()和(\',-)=(\',-）。如Mennle和Seuken(2014a,b）所示，策略证明等价于以下三个公理：交换单调性、上不变性和l ower-invariance。我们对这些公理进行了解释。对于任何一个偏好关系，我们将γ()的相邻关系定义为所有偏好的集合，这些偏好是通过交换该偏好中的任意两个连续排列的偏好而产生的。例如，假设={,,,}和:=h,,,i。一个机制是交换单调的，如果对于每一个主体，对于每一个偏好亲=(，-)∈R，和每一个带but的\'ε()，对于某一个，∈，T或者\'=OR\'，>，其中=()和\'=(\'，-)。换句话说，swap单调性要求机制要么忽略agent的mi s-报告，要么通过分配一个更高的概率来对她的错误报告做出反应。如果没有agent通过交换一个在她的偏好中不太优先的对象，可以为任何严格优先于对象的对象获得更多的分配，则机制是上不变的。形式上，是u pper-不变的，如果对每个agent来说，对于每=(，(-)∈R和每一个带but的\'ε(),对于某些，∈，我们有，=\'，(λ)\\\\{}，其中=()和\'=(\'，-).类似地，如果对于每个agent，对于每个=(，-)∈R和每一个带but的\'ε(),对于某些，∈，我们有，=\'，π(，)，其中=()和\'=(\'，-),一个机制是下不变的，如果对于每个agent，我们有，=\'，π(，)，则机制是下不变的。引理2.1（Mennle and Seuken(2014a，b))。一个机制是策略证明当且仅当它是交换单调的、上不变的、下不变的和公平的。公平的概念在文献中一直遭到反对。平等待遇ofequals是一种弱公平准则，它要求具有相同报告偏好的两个代理获得相同的随机分配。另一方面，嫉妒自由是一个公认的强公平性准则，它要求没有一个agent嫉妒其他agent的分配。在形式上，对于任何偏好profectionle=()∈，如果我们对所有人都有，∈，≥，那么一个随机赋值是无嫉妒的。一个机制是没有嫉妒的，如果它总是刺激你和我们没有嫉妒的任务。我们可以亲眼看到，嫉妒自由意味着平等对待平等。中立。在本文中，我们经常把注意力限制在中性机制上。中立性是一种自然的不对称性，它限制机制以相同的方式对待所有对象，即，该机制对任何对象的重命名都是不变的。在形式上，一个机制是中立的，如果对于任意偏好profirele∈R和置换:→,如果=()和=(())，th en对于所有的agent来说，我们有，=，().匿名性。这是我们在本文中研究的机制上的另一个休息。这是强加给机制的一个常见要求，要求它们对所有代理进行相同的处理，即该机制对代理的任何重命名都是不变的。让:→成为代理人的一个permu。如果=(，...，)，那么()=((1)，(2)，..，())是这样的优先级，其中agent现在报告agent（）报告的优先级，即，()。

一个机制是匿名的，如果对于任何p参考profirele∈R和permutation:→,如果=()和=(())，那么对于所有agent来说，我们有()，=，.3一个不可能的结果。在这一节中，我们给出了我们的主要结果，关于e-ciency、公平性和策略证明性这三个概念之间的内在贸易。我们的目标是证明任何策略证明和无嫉妒机制都必须以最弱的方式来实现e ciency。在陈述我们的定理之前，我们先引入一个非常弱的e ciency概念，它可以实现无争用e ciency。直觉上，这个概念抓住了这样一个结论：如果在独立的代理之间没有对对象的竞争，那么一个独立的机制必须给每个代理分配她最喜欢的对象4。我们将t h作为直观形式ly捕获如下。第3.1条（无争用规则）。如果每个代理都更喜欢一个不同的对象作为她而不是p选择，那么偏好选择就被称为con-tentio-n-free偏好选择。从形式上说，一个优先级函数∈R是无争用的当且仅当对于所有的优先级函数来说，∈，(，1)=(，1)=.设C TUR是所有无争用优先级函数的t h e集。一个机制被定义为争用自由当且仅当它为每个代理分配的每一个争用自由优先级都是她最喜欢的对象。也就是说，是无争用的e（？）cient？（？）cient？（？）C和？（？）？（？）=1,where=（）。这种概念对一个机制的e（？）ciency要求很低。实际上，它对任何不是无争用的程序都没有任何限制。此外，对于任何无争议的问题，唯一的Pareto最优d和erministic分配是分配给每个Agent她最喜欢的obj等的一个t。因此，任何事后的电子商务机制也必须是无争议的电子商务。此外，我们还证明了策略证明性、嫉妒自由性和内容自由性是不可分的。定理3.1。对于任何>=3，没有任何策略证明和嫉妒自由的机制可以是争用自由的。我们在下面的引理中证明=3的声明。定理3.1是引理3.2。对于=3，没有任何策略证明和无嫉妒机制可以是无争用的。设={1,2,3}和={,,}分别表示代理和代理的集合。为了矛盾，假设存在一个策略证明、无嫉妒和无竞争的机制。回想一下，我们对任何profirele（）都采用()=(())表示法。我们将继续考虑表1所示的六种首选方案。该机制给出的对应函数赋值在表2.4中为sh所拥有，该性质类似于社会选择文献（Muller和Satterth waite，1977)中规定的一致公理。1 a b c2 b a c3 c a b(a)profillele A1 a b c2 a b c2 a b c3 c a b(b)profillel B1 b a c2 a c b3 c a b(c)profillel C1 b a c2 a c b3 c a b(d)profilled D1 a b c2 a c b3 a c c a bb(f)profielle FTable 1：六个偏好profield来证明策略证明性、无嫉妒性和无争用性的不兼容性。profielle A（（））：考虑表1A中的偏好profield,其中代理1更喜欢()()，代理2更喜欢()()，而代理3更喜欢（）（）。由于该机制是无争用的，每个代理必须以1的概率获得她的首选。也就是说，()1,=()2,=()3,=1。profirele B（（））：接下来，假设代理1和代理3像profirele一样报告它们各自的首选项。但是代理2交换了她的两个选择并报告（）（）。首先，策略证明性意味着低方差，我们有()2,=()2,=0。第二，不嫉妒意味着平等对待平等的人。由于代理1和代理2具有s ame首选项，因此两者必须接收相同的对象随机分配。所以，()1，=()2，=0，因此()3，=1。

这意味着()1，=()2，=和()1，=()2，=.profirele C(()):相反，如果代理2报告()()，而代理1和3报告profirele B中的same首选项，则上不变性意味着她应该得到与她的顶部对象相同的概率。因此，()2,=()2,=。为了使代理1不嫉妒代理2，我们必须有()1,=()2,=。因此，()3,=0。对于agents 2和3之间的自由性，我们有()2,+()2,=()3,+()3,和()2,=()3,设()2,=()3,=。注意than[0,]。所以我们有，()2,=-和（）3,=1-。Profirele D（（））：考虑无争用Profire，代理2和代理3不改变Profirele的首选项，但代理1报告（）（）。通过假设它们的机制是不受影响的，每个代理获得他们的首选，概率为a b c1 1 0 02 0 1 03 0 0 1(a)profilterle Aa b c/2/2 0/2/2 03 0 0 1(b)profilterle Ba b c/2 1-2-/2/2/2-3 0 1-c）profilterle Ca b c1 0 1 02 1 0 0 0 0 1(d)profilterle Da b c/3/2/6/3/4/12/3/4/12(e)profiltere Ea b c1 1/62 03 0(f)profiltere FTable 2：表1.1中六个优先级profiltern的分配。为了使该机制具有策略性，代理1必须在Profireles中接收到相同的接收对象的概率。也就是说，()1,=()1,=yen2-=0=yen=。因此，对Profile in mechanism的结果ng分配如表3.1 a b c2 a c b3 c a a ba b c/2/2 0/2/4/43 0/4/4表3：Profile c及其分配Profile E（（））：假设代理3模仿Profile中的代理2，而代理1和代理2保持与Profile相同的偏好。为了使所有三个代理都不嫉妒另一个代理，该机制必须将对象平等地分配给所有代理。即()1，=()2，=()3，=。通过策略证明，()3,=()3,=。他的意思是（）3,=。由于代理2和代理3具有相同的偏好，它们得到相同的分配。所以（）2,=和（）2,=。代理2和代理3的分配完全阻止了代理1获得的分配。Profile F（（））：最后，反对代理1报告（）（）而代理2和代理3保持与Profile相同的首选项的做法。因为该机制是策略证明的，所以对于agent 3来说，在Profigures and中如实地报告她的偏好，()3,=()3,=3,=0。对于agent 2和3来说，不互相嫉妒，()2,=0,这在t urn中意味着()1,=1。然而，由于该机制是策略证明的，所以agent 1在Profigures and中必须得到相同的对象概率。也就是说，()1,=()1,=，这与分配的可行性相矛盾。为了证明>3的定理3.1，我们证明了任何策略证明、无嫉妒和无争用的e-cient机制都可以用来在=3的情况下构造一个等价的机制。我们将其推广到附录A。当存在三个代理和对象时，Bogomolnaia和Moulin(2001)提到策略证明和无嫉妒与后置e-cient是不相容的。这是Nesterov(2017)正式证明≥3的。由于后置e-ciency意味着自由e-ciency上的内容，他们的结果是定理3.1的直接推论（Bogomolnaia and Moulin(2001)；Nesterov(2017))。当≥3时，不存在策略证明、无嫉妒和后验的机制，当仅限于三个主体和对象时，我们可以进一步加强引理3.2，证明策略证明和无嫉妒是所有纯确定性分配的障碍。正如前面所讨论的，neutrali ty是一个对称的概念，它要求一个机制对对象的任何重命名都是不变的。当Lemma3.2表明确定性分配是无争用性的imposs时，下面的结论证明了策略证明性和无嫉妒性以及中性性是任何对象在任何条件下分配给任何agent的纯确定性分配。我们包括附录B中定理3.3的证明。

设==3。如果是中立的、无策略的和无嫉妒的，那么没有一个agent在任何偏好上被完全分配任何对象。定理3.1证明，在我们寻找无嫉妒和策略证明的机制时，n有时会偏离e-cient机制的（变体）。例如，反对认为RSD机制是策略证明和弱无嫉妒的，人们可以通过从RSD任务开始，然后依次试图从每个任务中消除嫉妒来获得策略证明和无嫉妒的机制。例如，Harless和Phan(2019)利用了一种类似的策略h，即RSD机制的一种变体，其中仅在三个相邻的agent位置上随机化（而不是所有的顺序）有助于恢复序数E ciency，而不需要修改策略证明。4配对交换机制对于任何随机分配机制来说，策略证明和嫉妒自由都是非常理想的性质，但在此之前已知的唯一的策略证明和嫉妒自由机制是等分(ED)机制，它简单地将所有对象平等地分配给所有Agent，完全不考虑agents的偏好。在一定意义上，等分机制可以看作是“Mo st ine-cient”策略证明机制。鉴于T Heorem3.1中提出的强烈的不可能性结果，自然会怀疑是否存在比同等的di视觉更具有策略性和无嫉妒性的机制。在这一节中，我们肯定地回答了这个问题，并设计了一个大的机制族t h在策略证明和无嫉妒的情况下，并控制了相等的d I vision机制。4.1传递函数表示法从相等的分配开始，然后允许agent根据他们的偏好交换他们的分配，从而获得更多的策略证明和无嫉妒机制。事实上，我们认为，从最一般的意义上说，这种设计机制的方法是从平等分配开始的，然后是对代理之间对象的转铁蛋白概率份额出发的，这种方法是不失一般性的。在下面的命题中，我们证明了任意的随机指派机制都可以用一组代理之间的转移函数来表示。命题4.1。对于每一个随机分配机制，都存在函数:××→[-，]，这样，=+x∈\\{}(，，)，(+x∈\\\\\\}然后，该命题断言，任何随机分配机制都可以被看作是所有的对象在agents上相等地分配，然后这些对象从一个agents到另一个agents之间的转铁蛋白g依赖于报告的偏好。一般说来，这些转让可能依赖于这对代理人的身份以及所有代理人的偏好，但当转让的部分股份的数量完全依赖于参与交易的pai rof代理人的偏好时，考虑这种情况是很自然的。这促使我们把注意力限制在承认一类转移乐趣的机制上。第4.1条（两两交换机制）。如果存在一个函数:R×R×→[-,],使得=+X∈\\{}（,,）,[=()∈R和[L,∈，∈WHERE=(),则称一个机制为两两交换机制。我们通过。

当上下文清楚时，我们也放弃了superscript，我们实施的关键限制是，它是与参与转移的两个代理的偏好有关的函数，特别是与代理身份和其他代理的偏好无关。为了证明随机分配的可行性，传递函数满足某些性质，我们在下面的提议中列出了这些性质。在双边交换中，这些因素吸引了自然的非离子，限制了非离子的存在。例如，no t ransfers属性指出，如果一对代理对对象有相同的偏好，那么他们永远不会参与任何对象的分数份额交换。第二个性质，平衡转移，确保一个代理转移给另一个代理的概率份额的数量必须等于她从同一个代理那里得到的数量。我们引用这些性质来证明本文的初步表征结果。该命题直接来自于对可行机制的认识，我们在附录D中得到了完备性的证明。命题4。2.考虑一个成对的迁移机制及其相关的迁移规律:R×R×→[-,]。然后满足以下属性1。无传输:(，，)=0？和？。2。平衡转移:p∈(，\'，)=0，对于任意一对偏好，\'∈R.3。反对称性:(，\'，)=-(\'，，)对于任意p，air的偏好，\'∈R和±∈4。有界范围:(，\'，)∈[-(-1)，(-1)]，对于任意一对偏好，\'∈R和(-1)]。正如我们在后面的章节中所示，成对交换机制形成了一个丰富的机制类别，并承认许多策略证明和嫉妒自由的机制。事实上，它们在资格上表现出公平性与激励报酬之间的不对等性。这使得我们能够只专注于证明这两个公理中的任何一个。这些机制中传递函数的约束形式使它们易于分析，并使我们能够准确地刻画这类中所有策略证明和中立机制的集合。除了它们吸引人的简单性之外，这些机制还抓住了对象分配中可分性的乌拉尔公理。Consi d er在profoungles=()∈and\'=(，\'-)中收到的分配byan agent。非正式地，我们称之为分离机制，如果两个分配中的di ited erence可以与来自每个代理的di ited erence ar ising（从to）改变她的偏好。一个机制是可分的，如果对于所有=()∈R，每个agent∈，每个\'-=(\')∈{}∈R-1和每个对象，我们有(，\'-)，-，=x∈{}H\'，-，I，其中\'=(\'，-)和~=(~)对于任意的~∈R，我们现在证明了匿名和可分机制的集合完全等于交换机制的类别。我们认为匿名性和可分离性都是这一特征的必要条件，因为成对交换机制是无名的，而可分离性并不意味着无名性5.定理4.3。一个机制是一个成对交换机制，如果它是匿名和分离的。证明。我们证明了容易的方向。设一个与t ransfer函数相关联的成对交换机制。由于转移函数独立于代理的身份，因此机制的匿名性来自于识别。为了了解可分性，我们观察x∈\\{}h\',-,i=x∈\\{}h+x∈\\{,}(，，)+(，，，)--x∈\\{}(，，)i=x∈\\{}(，，)-x∈\\{}(，，)=′-，-,来证明她的方向，假设是匿名的和可分的。设=()表示任意的∈R。对于任一，\'∈R，设任一偏好，这里（-1）代理有偏好，剩下的代理有偏好‘。设为（-1）剂中的一个，并为热剂。