二分偏好下的多单元分配

相似文件 换一批

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

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

立即领取

感谢您参与论坛问题回答

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

+2 论坛币

英文标题：
《Multi-unit Assignment under Dichotomous Preferences》
---
作者：
Josue Ortega
---
最新提交年份：
2018
---
英文摘要：
  I study the problem of allocating objects among agents without using money. Agents can receive several objects and have dichotomous preferences, meaning that they either consider objects to be acceptable or not. In this setup, the egalitarian solution is more appealing than the competitive equilibrium with equal incomes because it is Lorenz dominant, unique in utilities, and group strategy-proof. Moreover, it can be adapted to satisfy a new fairness axiom that arises naturally in this context. Both solutions are disjoint.
---
中文摘要：
我研究了在不使用金钱的情况下在代理之间分配对象的问题。代理可以接收多个对象，并具有二分偏好，这意味着它们要么认为对象是可接受的，要么认为对象是不可接受的。在这种情况下，平等主义解决方案比同等收入的竞争均衡更具吸引力，因为它是洛伦兹主导的，在公用事业领域独树一帜，而且是集团战略的证明。此外，它可以进行调整，以满足在这种情况下自然产生的新公平公理。两种解决方案是不相交的。
---
分类信息：

一级分类：Quantitative Finance        数量金融学
二级分类：Economics        经济学
分类描述：q-fin.EC is an alias for econ.GN. Economics, including micro and macro economics, international economics, theory of the firm, labor economics, and other economic topics outside finance
q-fin.ec是econ.gn的别名。经济学，包括微观和宏观经济学、国际经济学、企业理论、劳动经济学和其他金融以外的经济专题
--
一级分类：Computer Science        计算机科学
二级分类：Computer Science and Game Theory        计算机科学与博弈论
分类描述：Covers all theoretical and applied aspects at the intersection of computer science and game theory, including work in mechanism design, learning in games (which may overlap with Learning), foundations of agent modeling in games (which may overlap with Multiagent systems), coordination, specification and formal methods for non-cooperative computational environments. The area also deals with applications of game theory to areas such as electronic commerce.
涵盖计算机科学和博弈论交叉的所有理论和应用方面，包括机制设计的工作，游戏中的学习（可能与学习重叠），游戏中的agent建模的基础（可能与多agent系统重叠），非合作计算环境的协调、规范和形式化方法。该领域还涉及博弈论在电子商务等领域的应用。
--

---
PDF下载：
--> Multi-unit_Assignment_under_Dichotomous_Preferences.pdf (285.3 KB)

2022-5-31 07:26:29 上传

扫码加我 拉你入群

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

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

分享0 收藏0 回帖

关键词：Quantitative Applications Environments Coordination Game Theory

二元优先权下的多单元分配英国科尔切斯特埃塞克斯大学奥尔特高大学。欧洲经济研究中心（ZEW），德国曼海姆。抽象我研究了在不使用金钱的情况下在代理之间分配对象的问题。代理可以接收多个对象并具有二分法偏好，这意味着他们要么认为对象是可接受的，要么认为对象不是。在这种情况下，平等主义解决方案比收入相等的竞争均衡更具吸引力，因为它是洛伦兹主导的，在效用方面是独特的，并且是集团战略证明。此外，它可以进行调整，以满足在这种情况下自然产生的新公平公理。两种解决方案是不相交的。关键词：多单位分配、二分偏好、洛伦兹优势、等收入竞争均衡。JEL代码：C78、D73。电子邮件地址：josue。ortega@essex.ac.ukThis这篇论文基于我博士论文的第二章，由埃尔夫·莫林（Herv’eMoulin）提供支持，我感谢他提出的宝贵建议。我还收到了来自安娜·博格·奥莫纳亚、杨古彻、布拉姆·德里森、乔治·诺德克、费多尔桑多米尔斯基、E rel Segal Halevi、Jay Sethuraman、Olivier Tercieux以及在巴塞罗纳举行的计量经济学会冬季会议和在约克举行的第十届经济设计大会上的观众的有益评论。特别感谢哥伦比亚大学的盛情款待。我感谢Erin和ChristinaLoennblad校对了这篇论文。错误只有我一个人。20211年11月12日。导言分配问题是一个分配问题，在这个问题中，稀缺的对象将被分配到多个ag中，而不使用货币转移。分配问题包括参议员分配给委员会、课程分配给学生或求职者面试。

在本文中，我研究了分配问题，其中每个代理可以接收多个对象，但每个对象最多只能接收一个单元，并且每个对象有几个相同的单元。这些被称为多单元分配问题。其中包括前面讨论的三个示例。一个美国参议员平均参加四个委员会，一个学生可以在一个学期内选修许多课程，一个求职者可以安排许多面试。然而，参议员在每个委员会中不能有一个以上的席位，学生不能通过课程获得学分，申请者不能就同一职位进行多次面试。对于这样的多单元分配问题，我们希望有一个系统的（概率）程序来公平地决定哪些代理应该获得哪些对象，同时，这不会刺激代理联盟隐瞒其真实偏好。我的贡献是为二分法偏好领域中的多单元分配问题提出一个平等的解决方案，实现这一目的，在这个领域中，对象被认为是可接受的还是不可接受的，代理在他们认为可接受的所有对象之间是不一样的。平等主义的解决方案基于众所周知的列克西明原则。在二分法偏好领域，它的表现优于著名的同等收入竞争均衡，这是一种在更大偏好领域的类似分配模型中使用的解决方案（Hyland a and Zeckhauser，1979；Budish，2011；Reny，2017），并已成功应用于商学院的课程分配（Budish et a l.，2017）。更好的是，我的意思是，与收入相等的竞争均衡不同，平等解决方案是洛伦兹主导的，在公用事业中是独特的，不可能被群体操纵。

与单单元分配问题（Bogomolnaia和Moulin，2004）相比，这两种解决方案是不相交的，这意味着在一般情况下，当管理者被赋予同等收入时，我们无法获得作为竞争均衡的平等解决方案。资料来源：“国会议员的多重角色”，印第安纳大学代议制政府中心。洛伦兹优势是“公认为不平等比较的明确标准的排名”（Foster和Ok，1999年），“被广泛接受为体现了应作出的一系列最低限度的道德判断”（Dutta和Ray，1989年）。给定两个大小为n的向量，如果按升序排列，则第一个洛伦兹支配第二个洛伦兹≤ 第一个元素的n个元素始终大于或等于第二个元素的k个元素之和。如果itLorenz主导任何其他可行的公用事业项目，则公用事业项目为洛伦兹主导。在我们的设置中，效用函数是洛伦兹占优的事实意味着它唯一地最大化了代表代理人偏好的任何严格凹效用函数，因此是一种很强的公平性。解决方案的唯一性（在获得的效用文件中）也是一个令人满意的特性，因为它明确建议了如何分割资源。多值解决方案让时间表设计者承担了一项复杂的任务，即在解决方案所建议的分配中选择一个特定的分配，从而提高了一些代理提出合理投诉的可能性，这些代理可能会辩称，解决方案也推荐了对他们有害的其他分配。同样有趣的是，平等主义的解决方案是集团战略证明，这意味着企业联盟永远不会歪曲其可用性。相反，竞争解决方案可以由此设置中的组进行操作，就像在许多其他设置中一样。

然而，值得注意的是，即使在我们的二分法偏好领域中，虚假陈述的可能性非常有限，伪市场解决方案仍然可以由代理联盟操纵。事实上，平等主义解决方案满足了这三个理想的特性，这有力地证明了当代理具有二分法偏好时，建议使用它，而不是使用平等竞争均衡。二分法偏好域是公认的简单，不适用于建模一些多单元作业问题，在这些问题中，代理可能会将对象视为补充，例如课程分配给学生。然而，这种设置有助于表示日程安排问题（例如，参见Inmar，2016年的网球分配问题），在这些问题中，代理要么与每个目标兼容，要么不兼容，并希望最大限度地增加他们获得的目标数量，或者解决上述问题，即为候选人分配工作面试，或为公众分配表演席位等。此外，关注这一特定的偏好领域将有助于展示平等解决方案的性质，同时，这将使问题变得足够复杂，以确定为什么收入相等的竞争平衡不能是唯一的，不能证明集团战略。其非唯一性背后的原因是，对于某些对象，可用的身份副本数量（其供应量）等于其总需求量。我称这些物体为完美。尽管perfectobjects应该如何分配毫无疑问，但如何定价的问题变得棘手。因为他们的需求总是等于供应，所以他们可以得到零竞争价格。

然而，他们也可以有一个积极的价格，从而减少购买他们的代理商的可用预算。完美的目标也是为什么竞争解决方案不能证明集团战略的原因。代理人联盟可以歪曲他们的引用，以使一组对象完美。这允许这些对象具有较低的价格（甚至零价格），从而允许代理增加其预算，从而增加其在其他过度需求对象中的份额。操纵代理人的好处是显而易见的，这意味着带有虚假偏好的分配问题的每一个竞争均衡都会比原始问题的唯一竞争均衡产生弱的更好的分配。更一般地说，完美的对象也会提出它们应该如何影响最终分配的问题。一些分配过程可以分解为完美对象和过度需求对象的分配，这意味着代理获得的过度需求对象的份额与他们对完美对象的需求无关。我把这个属性称为完美物体的独立性。在代理可以声称完美对象明确属于他们并且他们获得的完美对象的数量不应减少他们在过度需求对象中的份额的情况下，这是一个理想的属性。虽然平均主义解决方案不满足这一要求，但我们可以构造一个明确的平均主义解决方案，该解决方案对仅具有过度需求对象的分配问题是且也是Lorenz占优的。然而，完美目标的独立性是有代价的：重新定义的eGalitarian解决方案不是集团战略证明。1.1。相关文献我研究的理论模型与文献中存在的两个问题密切相关：1。Bogomolnaia和Moulin（2004）提出的具有二分偏好的单单元Random分配，此后为BM04。

我们的模型将他们的模型推广到代理可以接收多个对象。他们研究平等主义和平等收入竞争解决方案。他们表明，平等主义的解决方案是洛伦兹主导的，并且总是能够得到具有竞争力的价格的支持。由于竞争解是洛伦兹占优的，因此竞争解可以很容易地计算为代理人效用的纳什乘积的最大化。他们还证明了平等主义的解决方案是符合集团战略的。Roth et al.（2005）表明，在不必参与的任意图上的赋值问题中，平均主义解也是Lorenz占优的。他们使用二分法偏好来模拟一个人是否适合某个特定的器官或器官进行移植。用他们的话来说，“美国外科医生的经验表明，对肾脏的偏好可以很好地近似为0-1，也就是说，患者和外科医生在健康捐赠者的肾脏中应该或多或少有所不同，这些捐赠者是b型的，在免疫上与患者是可比的”。Bogomolnaia等人（2005年）、Katta和Sethuraman（2006年）以及Bouveret和Lang（2008年）进一步研究了偏好二分域的分配。Kurokawa et al.（2015）还研究了一个单单元分配问题，在该问题中，如果满足需求，代理可以得到等于1或零的效用。也就是说，如果一个n代理需要10个对象，那么如果他收到9个、2个或0个对象，他就获得了相同的零效用，而在本文中，代理的效用与他们认为可以接受的货物呈线性关系：每个额外的单位都具有相同的边际效用。他们考虑了一个更广泛的偏好领域，该领域满足四个条件，即共同性、平等性、转移分配和最佳利用率。

他们表明，对于这一偏好领域中的每一个多单元分配问题，平等主义解决方案都是组策略证明、无嫉妒和唯一的实用程序。他们表明，在这个更大的领域里，平等主义的解决方案并不是洛伦兹主导的。它们允许非单独的rat分配。在他们的组织中，想要苹果但不喜欢梨的代理实际上可能会得到梨。此外，他们还规定，代理人从获得苹果和梨，或仅从苹果中获得同样的效用。相比之下，在BM04和本文的模型中，代理无法接收他们认为不可接受的对象（因此他们对这些对象没有偏好）。更严格地说，转移分配的属性不适用于我们的设置，因为代理可能会收到非单独的比率分配。2、Brams和Kilgour（2001）描述的课程分配问题（CAP）；Budish（2011）；布达什和坎蒂隆（201 2）；Kominers等人（2010年）；Krishna and¨Unver（2008）；和S¨onmez和¨Unver（2010），有一些重要的区别。首先，在CAP中，学生可能对对象集有任意偏好，这比我在本文中研究的对象要复杂得多。然而，报告组合偏好对于很少的选择是不可行的，而且在实践中，组合机制永远不允许代理完全报告此类偏好，这不仅是因为此类披露会很复杂，而且还因为代理可能不知道其偏好的如此详细。因此，一种新的理论将重点放在具有更简单偏好的位置机制上（包括线性效用和二分法偏好，例如Bouveret和Lema^itre，20 16和Bogomolnaia等人，2017）。

尽管CAP中考虑的二分偏好域较小，但由于CAP排除了差异，因此其中任何一个都不包含二分偏好域。此外，Budish（2011）只考虑确定性分配。我转而研究随机分配：在实践中，许多分配机制使用某种程度的随机优化来实现更高程度的公平。1.2。结果总结我定义了平等主义和受限竞争解决方案。自由主义者在有效效用函数集（定理1）中处于洛伦兹主导地位，而竞争性者存在（定理2），但具有多值性（示例1）。平均主义的解决方案是集团战略证明，而竞争性的解决方案则不是（定理3）。这两种解决方案是不相交的（示例2），这是该模型与BM04之间的明显差异。随机化用于分配美国的永久签证和住房补贴，或英国的学校名额。资料来源：《卫报》，2017年2月5日，“为什么随机机会决定谁获得住房补贴？”，NPR，2016年3月5日，以及“学校招生：彩票是一种更公平的制度吗？”，《卫报》，2017年3月14日。因此，经典的结果表明，可以将竞争解NCA计算为效用的Na-sh乘积的最大值，这一结果已不再适用：这一结果被称为Eisenberg Gale程序。它的失败很重要，不仅因为它让我们没有计算竞争均衡的已知算法，还因为Eisenberg Gale程序是一个更为稳健的结果，适用于线性小写以外的一大类效用函数（Vazirani，200 7）和商品与商品的划分（Bogo mo Lnaia et al.，2017）。

竞争解决方案并不是唯一的，这是一个值得关注的事实，因为在费希尔市场总是可以获得一个独特的实用程序文件。我证明了平等主义解决方案并非独立于完美对象，并提出了一个实现这一特性的明确的平等主义解决方案，同时在过度需求对象的分配中处于Lo-renz主导地位（Lemma5）。与经典的平等主义解决方案（示例3）不同，这种重新定义的解决方案虽然看似可行，但却违反了groupstrategy的证明性。本文的结构如下。第2节和第3节分别对模型和我考虑的解决方案进行了形式化。第4节分析了群对解的操纵，而第5节介绍了完美对象的独立性。第6节总结全文。附录中提供了所有证据。模型I考虑将m个对象（每个对象本身可能有多个副本）分配给n个代理。对象k最多QK张∈ M可以分配给代理集N。I将整数向量q=（q，…，qm）称为对象的容量。代理对对象的偏好由m×n二进制矩阵r给出。如果代理发现对象k是可接受的，则每个条目rik=1，否则为0。RiM（resp.RNk）稍微滥用了这个符号，表示r的第i个路径（resp.k-th列）和一组对象（resp.agents），其中chrik=1。