二分偏好下的多单元分配

我想| RNk |≥ qk对于每个对象k。根据我们想到的应用程序，也可以理解R以表示其分配或物理约束。如果对某个对象的需求不足，则可以始终保留其他副本。如果我们消除了这一假设，那么我们需要考虑非个体理性的赋值，其中代理接收他们不想要的对象。映射（R，q）的随机分配矩阵（RAM）是满足以下条件的m×n矩阵我∈ N、 k级∈ M可行性（0≤ 齐克≤ 1件∈Mzik公司≤ qk（1）只有当rik=1时，个体理性（Rationalitynzik）>0（2）RAM的条目表明每个代理获得每个对象的一个单位的概率。可行性条件确保任何代理都不能获得每个对象超过一个单元，并且每个对象分配的单元总数小于其容量。同样，IndividualRational保证每个代理人只从可接受的对象获得股份。在整个论文中，我只考虑满足这两个性质的作业。如前所述，符号ZiM（分别为ZNk）表示Z的第i行（分别为第k列）和zik=1的对象集（分别为玩家）。F（R，q）表示映射（R，q）的所有RAM的集合。匹配大小ν（R，q）=Pk∈Mqkof映射表示可以分配的最大对象单元数。多个随机分配可以具有相同的对应RAM。Budish et al.（20 13）中的定理1暗示了引理1。任何RAM都可以分解为二进制RAM的凸组合，因此可以实现。我假设代理在他们认为可以接受的对象之间是不同的，并且他们希望最大化他们获得的可接受对象的数量。代表这些首选项的规范效用函数是ui（Z）=Xk∈Mzik（3）表示仲裁代理i。

此函数显然不是唯一的，但使用起来很方便。该函数表示的偏好关系r是所有RAM上的一个完整顺序，这意味着RAM Z对于MAP（r，q）是Paretooptimal当且仅当ifPi∈NPk公司∈Mzik=ν（R，q）。由于可行性约束集是一个层次结构，因此允许使用该集合的含义。引理1是著名的Birkho fff-von Neumann de c composition定理的扩展。效用函数U（R，q）可以用asU（R，q）={U来描述∈ Rn | Z∈ F（R，q）：Ui=Xk∈Mzik，我∈ N} （4）我不区分事前效率和事后效率，因为在二分法偏好域中，它们是一致的。之所以出现这种等价性，是因为在所有有效赋值中，效用之和都是常数。在我们的设置中，效率只是要求不浪费任何对象。福利主义解决方案是将Φ从（R，q）映射到U（R，q）中的一组效率文件，因此，它只关注代理接收的预期对象数量，而不关注确定性分配上的确切概率分布。每当一个解是单值的，就使用符号φ。2.1。完美对象和完美扩展我们可以将相应的对象集M划分为两个子集TSP（R，q）和O（R，q），分别称为完美和超需求。完美对象集定义为asP（R，q）={k∈ M：| RNk |=qk}（5）向量qP（R，q）和qO（R，q）分别表示完美和过度需求商品的容量。给定一个映射（R，q），agent i的完美扩展表示添加agent i认为可以接受的任意完美对象k′。通常，映射（r，q）中主体i的完整扩展是一对（[r RNk′），q），其中[r RNk′]表示两个矩阵的n×（m+1）并置，q=（q，…，qm，| RNk′）。3、三个有效解决方案3.1。

平等主义解决方案一个直观的解决方案在效率和个人理性方面尽可能平衡了代理人的效用：这是众所周知的leximinEx事前和事后效率在具有二分法偏好的分配问题中的重新等效（BM04，Roth et al.，2005）。解决方案我将其称为平等主义解决方案（ES），由BM04从理论上提出，并应用于byRoth et al.（2005）和Yilmaz（2011）的活体供肾移植交换。为了规范地定义它，让lbe是著名的词典顺序。Foreach U公司∈ Rn，letγ（U）∈ Rnbe包含与Ubut相同元素的向量，按升序排序，即γ（U）≤ . . . ≤ γn（U）。leximin订单由U定义的LMILMU′当且仅当γ（U）lγ（U′）。ES由φES（R，q）=arg max定义LMU（R，q）（6）ES满足了一种称为洛伦兹优势的强大的公平性概念，定义如下。确定订单ldon Rnso，对于任意两个向量U和U′，UldU′仅当PTI=1Ui时≥Pti=1U′it型≤ n、 对于某些t，具有严格的不等式。我们说，U Lorenz支配U′，U写道LDU′，如果γ（U）ldγ（U′）。A矢量U∈ 如果n映射（R，q）的U（R，q）的Lorenz支配U（R，q）中的任何其他向量，则U（R，q）是Lorenz支配的。洛伦兹优势是U（R，q）中的偏序，因此不需要存在洛伦兹优势效用函数。然而，ES解决方案在新西兰占主导地位。定理1。ES解决方案是一组高效实用程序中的Lorenz domin ant。我使用Dutta和Ray（1989）中的定理3证明了定理1，该定理指出每个超模合作对策的核心都是Lorenzdominant元素。相应的合作游戏的构建可以在附录中找到。3.2。

具有同等IncomesA第二解决方案的受限竞争均衡实质上更为复杂，要求在代理商拥有同等预算的情况下平衡go ods的供需。这些相等的预算经常被标准化为一个货币单位，我也使用这种标准化。这种解决方案被称为具有同等收入的竞争均衡（CEE I）（瓦里安，1974；HylandZeckhauser，1979）。在映射中，每个代理最多可以消耗一个单位，因此对于任意两个向量U，U′∈ Rn，U仅当某些整数的Ut>U′t时为lU′≤ n、 对于每个对象的任何正整数p<t，Up=U′p，因此对其消耗集有特定的约束。从现在起，我使用约束竞争均衡（CCE，仍然具有同等收入）一词来明确这一区别。CCE解决方案不同于inHylland和Zeckhauser（197-9）定义的CEEI，因为在我们的案例中，代理从不部分消费具有不同价格的对象（见他们论文中的表1）。这一区别正是CCE的不同之处。定义1。MAP（R，q）的CCE是一对RAM Z*和一个非负的价格向量p*因此，我∈ N、 代理最大化其效用z*即时消息∈ arg maxZiM∈βi（p*)ui（ZiM）（7），其中βi（p）是定义为βi（p）={ZiM | Pk的预算集∈Mzik公司≤|轮辋|：p·ZiM≤ 1} ，市场清仓，所以*∈ F（R，q）（8）正如我们将在定理2中看到的那样，CCE集永远不会为空，但可能会变大。CCE-implyk的最优性条件/∈ P（R，q）==> p*k> 0（9）z*ik，z*ik′型∈ （0，1）==> p*k=p*k′（10）[p*k<p*k′]∧ [0<z*ik′]==> z*ik=1（11）Xkz*ik<|边缘|==>Xkp公司*k·z*ik=1（12）这些是我们模型中Fisher方程的等价物，参见Brainard和Scarf（2005）。

条件（9）只允许完美对象的价格为零，而表达式（10）则要求代理人获得的每个对象都具有相同的边际收益。CCE通常是多值的。给定一张地图，我表示这一组，若一个苹果派的价格比一个梨派高，并且代理对它们的价值相等，代理要么完全吃掉梨派并吃掉部分或全部苹果派，要么代理只吃掉部分梨派而不吃掉苹果派。CCE中永远不会发生的情况是，代理会吃掉一些（但不是全部）梨馅饼和一些（但不是全部）苹果馅饼。成对（Z*, p*) 作为C（R，q）。CCE解由ΦCCE（R，q）={u（Z′）|定义 p′：（Z′，p′）∈ C（R，q）}（13）3.3。每个对象都是天真的平等主义者最后，一个天真且非常直观的解决方案（我仅将其用作基准）将分配问题分解为m个子问题，即将对象k的qkunits分配给RNk，在所有认为可以接受的人中分配对象k的同等份额。我将此解决方案称为每对象平等（Equalitarian Per Object，EPO）。给定一个映射（R，q），EPO解决方案分配给每个代理φEP Oi（R，q）=Xk∈Mrik·qk | RNk |（14）在二分法偏好域中，EPO相当于众所周知的随机优先级机制，也称为随机序列专政。我不认为EPO是MAPS的合适解决方案，因为它忽略了对应于每个对象的m分配问题之间的相互作用。EPO还使以下基本公平性属性失败：如果n-1个代理接收至少一个对象，第n个代理还接收至少一个对象；请参见示例1以获取说明。还可以考虑文献中讨论的其他解决方案，特别是Bogomolnaia和Moulin（2001）定义的概率序列规则。我不考虑这个解决方案，原因有二。

首先，概率论规则在不同的效率概念不一致的情况下很有吸引力。地图的情况并非如此。其次，它最初是针对具有严格偏好的分配问题定义的。尽管Katta和Sethuraman（2006）扩展了概率序列规则以允许f或差异，但他们的扩展仅适用于单机组分配问题。3.4。两个示例表明，所有解都是不相交的示例1（来自EPO的多值CCE differs）。表1显示了我们的三种解决方案对子表1a中给出的n=6、m=3和（R，q）的问题产生的不同结果。CCE实用程序写在子表1b的框架中，因为有支持实用程序的CCE，而EPO在更常见的首选项中并不有效。具有随机优先级的等效EWI也将消失。介于（2.4，1.4，1）和（2.25，2，1）之间，0≤ pγ≤. 这种多样性很有趣：在Fisher markets相应的实用性文件中，竞争解决方案总是独一无二的（Jain和Vazirani，2010年，第87页）。这也是一个问题，因为CCE没有明显的选择。表1：CCE是多值的。N\\Mαβγ总计：与R矩阵相对应的d 1 1 1 E 1 0 2f 1 0 1总计6 4（a）。不适用于CCE EPOa：d 2.25[2.25-2.4]2.47e 2[1.4-2]1.47f 1 1 0.67（b）每个解决方案的实用程序。示例1中的任何CCE都将对象α的一个单位提供给代理f。这意味着不存在支持EPO结果的CCE价格，这是反对这种解决方案的有力论据，因为竞争均衡被视为“本质上是对完美正义的描述”（Arnsperger，1994），也是德沃金“资源平等”的基础（德沃金，1981）。因此，EPO解决方案并不理想。

但有趣的是，ESsolution也可以产生作为CCE无法支持的结果。示例2（与CCE不同）。我使用子表2a中给出的n=9、m=6和（R，q）的映射来显示这一点。请注意，在单台机组的情况下（BM04中的定理1），ES始终由具有竞争力的价格支持。如果ES溶液n（2，2.5，2.5，3.25）可以作为CCE来支持，那么pα=pγ=pδ=p=pζ，因为试剂f：i获得了具有正可能性的对象，但不会耗尽它们。代理商d：我必须花掉他们的全部预算，这意味着价格pα=和pβ=。然而，在这样的价格下，代理a:c的ES实用程序是不可用的（>1）。ES和CCE不一致的事实很有意思：在非约束的情况下，竞争解决方案可以通过最大化Nash乘积来计算，求解所谓的Eisenberg-Gale progr am（Eisenberg，1961；Eisenberg和Gale，19 59；Chipman，1974，参见第7章inMoulin，2003的教科书处理）。通过求解艾森伯格-盖尔过程，无法计算出竞争解，这意味着我们缺乏表2：ES和CCE是不相交的。N\\Mαβγ，δ，ζTotala:c 1 0 2d 0 1 0 3e 0 1 0 1 3f:i 1 0 1 1 5 total 7 5 q4 4（a）对应于R矩阵。αβγ，δ，ζ总计1 0.97 0 0 1.970 0.54 1 0 2.540 0.54 0 1 2.540.25 0 0 0.75 0.75 3.25（b）对应于Z*（CCE）。计算竞争均衡的算法。Eisenberg-Galeprogram在其他方面是一个相当稳健的结果，因为它扩展到了线性情况以外的一大类效用函数（Jain和Vazirani，2010），以及对象和BAD的混合划分（Bogomolnaia et al.，2017）。竞争解决方案的多样性及其与平等主义结果的不等价性证明了CCE的新术语的合理性。

对于任何映射，CCE集都是非空的，我在附录中使用标准固定点参数证明了这一结果。我在定理2中总结了这些发现。定理2。ES解决方案是定义良好的单值解决方案，并且存在CC解决方案。i r交叉点可以为空。3.5。EnvyIt很容易看出，ES和CCE解决方案都没有令人羡慕的地方。对于任何具有代理i和j的映射（R，q），如tha tRiM，解φ是无嫉妒的 RjM，φi（R，q）≤ φj（R，q）。对于多值CCE，envy Freeness适用于其中的任何选择。引理2。ES和CCE没有嫉妒。我推迟了一个简单的证明。请注意，没有一个有效的解决方案是完全没有嫉妒的，即对于任何带有代理i和j的MAP（R，q），如| RiM |<RjM |，φi（R，q）≤ φj（R，q），seeOrtega（2016）。4、群体操纵我在与每个解决方案相关的直接揭示机制中考虑代理的操纵。为此，我们需要确切地知道对象是如何分配的，而不仅仅是每个代理接收到的总效用。详细解ψ将每个映射（R，q）映射为RAM Z∈ F（R，q），指定每个对象的哪个共享分配给每个代理，而alfarist解决方案φ将每个映射映射到实用程序文件U∈ U（R，q）和只告诉我们每个代理接收的预期对象数。每个详细解ψ投影到福利解φ（R，q）=u（ψ（R，q））。与详细解决方案ψ相关的直接揭示机制是，所有代理都会揭示其偏好RiM，然后将ψ应用到相应的映射（R，q），实现RAMψ（R，q）=Z。我假设具有真实偏好RiM的代理I只能通过低估其认为可接受的对象数量来歪曲其偏好，即通过声明参考文件R’iM RiM（然后我们说R′iMis IR代表RiM）。我使用这个假设有两个原因。

第一个是理论上的：我没有具体说明不受欢迎对象的消费给代理带来的效用，我只关注个别理性设计。我需要指定这种效用，通过夸大可接受对象的集合来分析解决方案的操纵。第二个原因是，在对调度问题的研究中，已经有了这样的假设（例如Koutsoupias，2014）。在许多激励地图的计划问题中，取消消费可能会受到中央票据交换所的严厉惩罚，特别是当其他代理的消费依赖于其他代理完全耗尽他们的包袱时（只有4名球员中的3名才能进行网球双人赛）。11,12A详细解ψ对于每个映射（R，q）和每个联盟S是群策略证明的 N R′满足i）R′jM=RjMj/∈ S、 和ii）RSM的R′SMis IR，因此我∈ S、 ui（ψ（R′，q））≥ u（ψ（R，q））（15）中至少有一个代理具有严格不等式。如果每个详细解ψ都是群策略证明的，则福利主义解φ是egy证明的群str。如果允许代理将不需要的对象报告为需要的对象，则组（优先级较高的代理请求她不想要的对象，并将其提供给操纵联盟的成员）可以操纵平等主义者甚至优先权的解决方案。BM04引入了一个等效的假设：它们要求每个映射的RAM必须根据代理的真实偏好分别是合理的。BM04表明，当代理最多可以获得一个对象时，没有确定的解决方案是防组策略的。确定性解决方案包括优先级解决方案，即代理根据预先指定的顺序依次选择其最喜欢的可用捆绑包。

为什么团体可以使用最终解决方案，是因为具有最高优先级的代理可以更改其报告，并且仍然可以收到一份可接受的替代报告，使其效用保持不变，同时使优先级较低的代理受益：这是一种被称为专横的属性。此参数不适用于贴图。由于代理可以获得多个对象，因此具有较高优先级的代理只能通过声明较少的对象而属于一个操作联盟。但由于她拥有最高的优先权，这种操纵总是会给她带来极低的效用，因此她不能加入联盟。同样的论点适用于所有剩余的代理，因此也适用于引理3。任何确定性优先级解决方案都是集团策略证明。前面的引理表明，对于二分法do-ma-in中的映射，组策略证明相对容易实现。事实上，我在下面展示了ES解决方案也是组策略证明。CCE是否也是集团战略证明？我们的组策略证明定义有两个扩展到集值解。第一个要求，对于每个映射（R，q），操纵映射（R′，q）的竞争平衡不存在弱于原始问题（R，q）的所有竞争平衡的竞争平衡，对于操纵联盟S的每个成员，一个更强的推广是，（R，q）至少有一个竞争均衡，其产生的效用弱于（R′，q）的某些竞争均衡，对于偏离联盟S的至少一个成员，具有严格的不等式。事实证明，CCE违反了这两个条件。这样做的原因是，一个团队可以协调使多个对象完美，从而使这些对象的价格为零。定理3。