二分偏好下的多单元分配

ES是集团战略证明，但CCE不是。在附录中可以找到ES是集团战略公关的证据，但我表明CCE可以由下面的集团毫不含糊地操纵。示例3（CCE不是集团战略证明）。设n=7，m=4，和（R，q）由表3给出。表3：示例3。N\\MαβγδΦCCEaaa 1 1 1 2.5bbb 1 1 1 1 2.5ccc 1 1 1 2.5d 1 0 1 2。5e 1 1 0 1 2。5f 1 1 0 2。5g 1 0 0 0 1总计7 5 5 5 5 Q 4 4 4（a）真实偏好R。αβγδΦCCE1 0 1[2.5-2.57]1 1 0 1[2.5-2.57]1 1 1 0 0[2.5-2.57]1 0 1[2.5-2.57]1 1 1 1[2.5-2.57]1 1 1 0[2.5-2.57]1 0 0 0 0[0.57-1]总计7 4 4 4 Q 4（b）S={a，b，c}的误报R′。考虑联盟S={a，b，c}。当代理提交其真实首选项时，存在一个支持ES解决方案的唯一CCE：代理a、代理b和代理c获得2.5个预期对象。通过对不同对象（如子表3B）的报告进行更改，他们使对象β、γ和δ变得完美，从而扩大了CCE解决方案集，其中包括始终弱于2.5 a和高达2.57的效用。通过虚假陈述和创造特定的完美对象，他们允许将这些对象定价为0，在（R′，q）的任何竞争均衡中微弱增加预期对象的数量，在这种情况下，以具有有限可接受对象的代理为代价。我不讨论战略计划（由个人在自己的岗位上操作），因为ES和CCE（以及EPO）是战略证明，这是直接的。对于CCE，我们可以构建一个战略证明的选择，因为减少一个对象的总需求或者降低其价格，相对增加其他对象的价格，或者保持其价格不变。效率、公平性和不可操作性是资源分配机制设计的标准目标。在结束之前，我将讨论一个新的目标，它自然会出现在地图上。5.

完美对象的独立性有些解决方案不依赖于代理所需的完美对象的数量。如果代理人发现一个新的完美对象是可以接受的，我们可以推断她总是会收到一个额外的预期单位。这是以下属性捕获的内容。如果对于everyMAP，每个i∈ 对于它的任何一个完美扩张（[R RNk′），q），φi（R，q）+1=φi（[R RNk′），q）（16），IPO是一个理想的性质，有两个原因。首先，完美的对象很大程度上属于那些认为可以接受的代理，因此他们可以争辩说，他们应该完全获得它们，而不管他们从过度需求的对象中获得的份额是多少。其次，如果票据交换所使用的解决方案不是首次公开募股，那么找到可接受的完美对象的一组代理可以避免报告他们对完美对象的需求，并完全在中央机制之外获得它们，这是安排应用程序的真正问题，在这种机制中，代理可以自己组织团队活动。CCE（部分）满足这一要求。引理4。虽然ES不是首次公开募股，但有一些CCE可以满足首次公开募股的要求。Lemma4强调了CCE总是可以为所有perfectobjects分配零价格：这就是我们如何构建满足IPO的CCE选择。但它也可能只为一些完美的对象指定零价格，或者根本没有完美的对象。设计师在选择均衡价格时具有高度灵活性。选择问题扩展到了Budish（2011）的CAP竞争机制，在该机制中，学生向中央票据交换所透露他们的偏好，中央票据交换所宣布了相应的均衡分配。布迪什认为，这种机制是透明的，这意味着学生可以验证分配是否平衡。

但这种机制可以“从内部操纵”，有选择地将零价格分配给手工挑选的课程，同时正确地辩称它会产生竞争性分配。如果必须实现首次公开募股（取决于背景和设计人的目标），我们希望有一个解决方案，同时避免CCE的多重性问题，同时避免嫉妒，并且IPO也能满足首次公开募股的要求。再一次，EPO在公平考虑方面表现得很差，因此我不作进一步分析。尽可能公平。存在这样一种解决方案：我们称之为重新定义的平等解决方案（ES*）。为了定义它，我们将M划分为P（R，q）和O（R，q），并将原始映射（R，q）划分为两个独立的问题（RNP（R，q），qP（R，q））和（RNO（R，q），qO（R，q）），分别对应于具有完全和超需求对象的独立映射。ES*由φES给出*i（R，q）=φES（RNO（R，q），qO（R，q））+Ri P（R，q）（17） ES*采用了只包含过度需求对象的地图的平等解决方案，并添加了玩家可用的完美对象的数量。ES*接近于Budish（2011）的建议。注意到一些课程可能供过于求，他建议只在需求过剩的课程集中运行分配机制：“如果已知某些课程供应不足，我们可以将该问题重新模拟为只分配潜在的课程”。将此建议正式化。它还提出了几个要求。引理5。ES*解决方案定义明确，单值、高效、首次公开募股、无妒忌，且洛伦兹主导问题（RNO（r，q），q）。ES*立即成为单值、高效和IPO。其余的性质是对引理1和2以及定理1的证明的直接修改。

不幸的是，Lemma5中的属性是有代价的：ES*不是群策略证明的。可以通过减少可用性来操作ES*，以使某些对象更加完美。因此，操纵联盟的成员完全获得了这些目标，同时也获得了剩余超额需求问题的一部分。集团战略证明和IPO是兼容的。EPO既能满足他们的需求，又能满足他们的嫉妒心理和帕累托效率。然而，正如第3.3.6小节所述，它在公平性方面表现不佳，不适合我在本文中考虑的问题。结论对于二分法偏好域中的多单元分配问题，平均主义解是Lorenz-do-minant、单值和群。例如，使用例3中所示的映射和操作r′。战略证明。出于这些原因，我建议使用它作为一种解决方案，而不是著名的收入相等的竞争均衡，因为它破坏了这三个可取的属性。如果市场设计师有兴趣满足完美对象的独立性，那么重新定义的平等主义解决方案将成为一种极具吸引力的替代方案。附录：证明定理1 ES解决方案在一组高效实用程序中是洛伦兹主导的。证据F ix a图（R，q）。考虑凹合作博弈（N，u），其中u：2N→ R是一个函数，它为代理的每个子集分配它们可以一起获得的最大数量的对象。为了将这种直观的功能形式化，给定一个联盟 N、 让我们将对象集M划分为M+（S）和M-（S） ，定义的asM+（S）={k∈ M：| RSk |<qk}（18）函数u由u（S）=Xk决定∈M+（S）Xi∈Srik+Xk∈M-（S） qk（19）该函数显然是子模块，即。

对于任意两个子集T，S Nu（S）+u（T）≥ u（S∪ T）+u（S∩ T）（20）“上述核心”定义为以下一组参数C（R，q）={x∈ Rn | Xi∈Nxi=ν（R，q）和 S N：Xi∈Sxi>u（S）}（21）从定理3 inDutta和Ray（1989）得出，集合C（R，q）具有Lorenz主导元素，是平等解。但通过构造“上方m的核心”，U（R，q） C（R，q），ES解在有效效用函数U（R，q）集中也是Lorenz占优的。定理2对于一般网球问题，ES解是定义良好的单值解，CCE解是有效的。他们的十字路口可能是空的。证据F ix a图（R，q）。让p∈ Rm+是任意的价格向量，使得p·c=n，并使用符号yi=rim表示代理i的最优消费束∈ N、 和yN=（| RN1 |，…，| RNm |）。请注意P·yN≥ p·q（22）将向量λ定义为λ（p）=（λ，…，λn）=UNIF{p·yi；n}（23），其中UNIF表示统一配给规则：一种映射，只要小于λ，就给每个代理提供购买其首选对象束所需的资金，其选择应确保p·~λ=n。定义满足和非满足代理的集合n（p）={i∈ N |λi=p·yi}（24）N+（p）={i∈ N |λi<p·yi}（25），因此λi=λ我∈ N+。确定需求对应关系di（p）asdi（p）=arg maxZiM∈I（RiM）{p·ZiM≤ λi}（26），其中i（RiM）表示RiM的单独有理赋值集。注意，对于每个i，di（p）={yi}f∈ N（p），而对于N+（p）中的代理，任何向量zi∈ di（p）满足p·zi=λ。根据Berge极大定理，需求对应为上半连续凸值。整个社会的超额需求对应关系继承了di的特性，通过（p）=dN（p）给出- q（27），其中dN（p）表示每个对象的总需求对应关系。使用Gale-Nikaido-Debreu定理（第7页定理7）。

在Debreu（1982）的716-718中，我们知道存在价格向量p*∈ R+和超额需求向量x*∈ e（p*) 满足以下两个条件*=~0（28）p*· x个*= 0（29），其中等式（29）中的Walras定律通过~λ和d的构造成立。最后，我∈ 新西兰*iM=di（p*) （30）使相应的Z*∈ F（R，q）通过方程（28），得出CCE存在的可能性。ES是单值的，这一点来自定理1。我已在示例3中显示，对于某些MAP，不存在支持ES作为CCE的价格。引理2 ES和CCE没有嫉妒。证据对于任意映射，设φES（R，q）=（U，…，Ui，Uj，…，Un），假设代理i嫉妒j，这意味着RjM RiMand存在一个Pigo u-Dalton转移函数，因此效用函数u′=（u，…，Ui+，Uj-，联合国）∈ U（R，q）。但U′Lorenz支配φES（R，q），因此φES（R，q）不是ES解，这是一个矛盾。由于标准论点，任何CCE解决方案的选择都是无嫉妒的：如果有任何代理嫉妒，她可以改变她嫉妒的代理的时间表。定理3 ES是群策略证明，但CCE不是。我已经证明，在正文中，CCE不是集团战略证明。为了证明ES是集团战略的证明，我从几个预备阶段开始。设Zdenote为所有支持平均主义解的可行ram集，即Z={Z∈ F（R，q）|我∈ 编号：Xk∈Mzik=φESi（R，q）}（31）如果没有一个代理可以在不改变自己效用的情况下影响其他人的分配，那么规则就是非专横的。也就是说，如果对于everyMAP（R，q），我∈ N、 以及任何操作R′，如That 1）j 6=i，RjM=R′jM，和2）R′iM（RiM，我们有φi（R，q）=φi（R′，q），只有当φ（R，q）=φ（R′，q）（32）我们证明了下面一个有用的辅助引理。引理6。ES是非boss y证明。我们以矛盾的方式前进。让R′与前一定义中的规定相同。

操作可能来自三种对象可用性的降低：1。k∈ O（R，q）和{k∈ M|Z∈ Z:zik=0}，因此即使代理我误报了，也有一种方法来实现ES解决方案，所以她的可用性变化无关紧要，所有实用程序都保持不变，所以代理不能专横。2.k∈ O（R，q）和{k∈ 米|Z∈ Z:zik>0}，所以很明显特工的能力发生了变化，所以她不能专横。31.k∈ P（R，q），但如果代理i减少了完美商品的数量，她总是减少她获得的效用（正如我在下面证明的那样），因此她的效用不是常数，她不能专横。现在，我证明了减少代理iis可用的完美对象的数量总是会严格降低她的效用。perfectobject的某些损失必须通过增加她从所有需求对象获得的份额来准确补偿，这在任何Z中都是恒定的∈ Z、 代理iwas没有获得这些对象的全部份额（否则我们会得到一个矛盾），因此另一个代理j必须获得这些对象的份额f，这意味着φESj（R，q）≤ φESi（R，q）（因为否则ES将把这些股份给代理i）。代理人j在φ（R，q）中获得的部分股份必须转让给代理人i在φ（R′，q）：这是一次庇古-达尔顿转让，因为如果代理人i在虚假陈述的问题中没有获得较低的效用，则他不会获得j的股份。此外，φESi（R，q）- 1<φESj（R，q）≤ φESi（R，q）（33），否则当i减少完美对象的数量时，j不会将任何份额转移给i。设γ为所需的从j到i的Pigo-u-Dalton变换，以使i的效用保持不变。

我们有φESi（R′，q）=φESi（R，q）- 1+γ=φESj（R，q）- γ<φESi（R，j）（34）表明，确实减少了完美对象的数量，这总是会降低效用，从而得出结论，ES是非专横的。我们现在已经准备好证明ES是集团战略项目。我们将通过证明没有人可以加入操纵联盟来实现这一点。证据通过矛盾的方式，假设存在一个映射（R，q），一个联盟（N），和一个操纵R′，这样，对于所有i∈ SφESi（R′，q）≥ φESi（R，q），对于某些j∈ SφESj（R′，q）>φESj（R，q）。设φES（R，q）=UE，并对代理进行排序，使UE≤ . . . ≤ UESn。我们将通过归纳法，按a-gents的顺序，展示以下性质i/∈ S（35）有两种情况下，代理人i可以在S中。情况1）要么她获得更多效用，φESi（R′，q）>φESi（R，q），要么情况2）她获得相同的效用，但她改变了自己报告的偏好以帮助S中的另一个成员。这被ES的非专横性所排除，因此我们只关注情况1）。我们首先证明了i=1，即效用最低的代理。代理1使用新的文件R′获得了更高数量的对象，这些对象必须来自一组对象K O（R，q），他没有从中获得全部股份（K={K∈ 米|Z∈ Z:0<zik<1}），其中代理2，t也可用，UES=UES=…=UESt公司。这些代理会耗尽qkentirely；i、 e。k∈ KZ∈ Z、 Ptzik=qk。设T={1，…，T}∩S、 对于任何对RT M具有独立性的首选项matr ix R′T mt，对象{k∈ K | RNk6=R′Nk}对代理{1，…，t}\\t的过度需求减少，因此t中的代理作为一个整体得到的对象较少。因此，T中必须至少有一个代理人表现最差，而这种合作是不可行的。因此1/∈ S、 现在我们假设我/∈ S表示代理i=h- 我们向h探员展示了它。我们必须有那个UESh。

我们假设φES（R，q）ES<φESh（R，q），否则我们对代理1的论证完全相同。如果代理h∈ S、 必须存在一个操纵R′，使得φh（R′，q）>φh（R，q）。她的效用的增加必须来自于比她没有完全获得的所需对象有更多的对象份额，即Kh={k∈ 米|Z∈ Z:0<zhk<1}。其中一些对象已被代理1、…、，h类- 因为{1，…，h，一个代理h不可能从这些对象中获得更多的共享- 1}∩ S= 通过我们的归纳步骤。因此，增加量必须来自未被{1，…，h耗尽的对象- 1} 。这些对象对{h，…，n}\\S的过度需求减少了，因此S中的元素得到的对象共享更少。因此，在S中必须有一个不太可靠的代理人，所以联盟S是不可行的。因此h/∈ S、 证据到此结束。引理4虽然ES i不是首次公开募股，但存在一系列满足首次公开募股要求的CCE。证据很明显，ES不是IPO。设n=5，M={α}，q=4，R= [1 1 1 1 1]。对于任何代理，φESi（R，q）=0.8，但对于任何代理i，用capa city 4添加一个完善的对象k′会改变φESi（[R RNk′，（4，4））=1.75 6=2。为了表明存在Φcce的选择，即IPO，让（Z*, p*) 求（R，q）且（[R RNk′），q）是（R，q）的完美推广。然后fixp*k′=0，且对于每个i∈ N让z*如果rik′=1，则ik′=1，否则为0。空气（[Z*Z*Nk′，（p*, . . . , p*n、 0）是完美扩展（[R RNk′），q）的CCE，因为每个对完美对象感兴趣的人都能提供它，而对k′的需求等于它的供给，因为新对象k′是完美的。ReferencesReferencesArnsperger，C.（1994）：“嫉妒自由和分配正义”，《经济调查杂志》，8155-186。Bogomolnaia，A.和H。

莫林（2001）：“随机分配问题的新解决方案”，《经济理论杂志》，100295-328（2004）：“二分法参考下的随机匹配”，《计量经济学》，72257–279。安第斯州Bogomolnaia，A.，H.Moulin，F.Sandomirskiy。Yanovskaya（2017）：“混合甘露的竞争划分”，《计量经济学》，第851847-1871页。Bogomolnaia，A.、H.Moulin和R.Stong（2005）：“二分法偏好下的集体选择”，《经济理论杂志》，122165-184。Bouveret，S.和J.Lang（200 8）：“不可分割商品公平划分中的效率和无嫉妒：逻辑表示和复杂性”，《艺术情报研究杂志》，32，525–564。Bouveret，S.和M.Lema^itre（2016）：“使用标准量表描述不可分割商品公平划分中的冲突”，自治代理和多代理系统，30259–290。Brainard，W.和H.Scarf（2005）：“1891年如何计算均衡价格”，《美国经济和社会学杂志》，64，57-83。Brams，S.和M.Kilgour（2001）：“竞争性足球部门”，Jo urnalof Political Economy，109，418–44 3。Budish，E.（2011）：“组合分配问题：来自平等收入的近似竞争均衡”，《政治经济学杂志》，1191061-1103。Budish，E.，G.Cachon，J.Kessler和A.Othman（2017）：“Coursematch：大规模实施组合分配的等收入近似竞争均衡”，运筹学，65314–336。Budish，E.和E.Cantillon（2012）：“多单元作业问题：哈佛大学课程分配的理论和证据”，《美国经济评论》，1022237-71。Budish，E.、Y.-K.Che、F.Kojima和P.Milgrom（201 3）：“设计随机分配机制：理论和应用”，《美国经济评论》，103，585–623。奇普曼，J。