具有最小优先级的概率序列和随机优先级机制

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

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

立即领取

感谢您参与论坛问题回答

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

+2 论坛币

英文标题：
《The Probabilistic Serial and Random Priority Mechanisms with Minimum
  Quotas》
---
作者：
Marek Bojko
---
最新提交年份：
2020
---
英文摘要：
  Consider the problem of assigning indivisible objects to agents with strict ordinal preferences over objects, where each agent is interested in consuming at most one object, and objects have integer minimum and maximum quotas. We define an assignment to be feasible if it satisfies all quotas and assume such an assignment always exists. The Probabilistic Serial (PS) and Random Priority (RP) mechanisms are generalised based on the same intuitive idea: Allow agents to consume their most preferred available object until the total mass of agents yet to be allocated is exactly equal to the remaining amount of unfilled lower quotas; in this case, we restrict agents\' menus to objects which are yet to fill their minimum quotas. We show the mechanisms satisfy the same criteria as their classical counterparts: PS is ordinally efficient, envy-free and weakly strategy-proof; RP is strategy-proof, weakly envy-free but not ordinally efficient.
---
中文摘要：
考虑将不可分割的对象分配给对对象具有严格顺序偏好的代理的问题，其中每个代理都有兴趣消费最多一个对象，并且对象具有整数最小和最大配额。我们定义一个任务是可行的，如果它满足所有的配额，并假设这样的任务总是存在的。概率序列（PS）和随机优先级（RP）机制基于相同的直观想法进行了推广：允许代理使用其最喜欢的可用对象，直到尚未分配的代理的总质量完全等于剩余的未完成较低配额；在这种情况下，我们将代理的菜单限制为尚未满足其最低配额的对象。我们证明了这些机制满足与经典机制相同的标准：PS是顺序有效、无嫉妒且弱策略证明的；RP是一种策略证明，没有嫉妒感，但效率不高。
---
分类信息：

一级分类：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.
包括对契约理论、决策理论、博弈论、一般均衡、增长、学习与进化、宏观经济学、市场与机制设计、社会选择的理论贡献。
--
一级分类：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下载：
--> The_Probabilistic_Serial_and_Random_Priority_Mechanisms_with_Minimum_Quotas.pdf (391.9 KB)

2022-4-26 14:49:37 上传

扫码加我 拉你入群

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

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

分享0 收藏0 回帖

关键词：优先级 Coordination Applications Environments Contribution

具有最小引数的概率序列和随机优先级机制*摘要考虑将不可分割的对象分配给具有严格顺序优先权的代理的问题，其中每个代理都有兴趣消费最多一个对象，并且对象具有整数最小和最大配额。我们定义一项任务是可行的，前提是它满足所有配额，并假设该任务始终存在。概率序列（PS）和随机优先级（RP）机制基于相同的直观想法进行了概括：允许参与者消费他们最喜欢的可用对象，直到尚未分配的代理的总质量与剩余未完成的较低配额数量完全相等；在这种情况下，我们将代理的菜单限制为尚未完成其最低配额的对象。我们证明了这些机制满足与经典机制相同的标准：PS通常是有效的、无嫉妒的和弱策略证明；RP是一种策略证明，虽然没有嫉妒感，但并不普遍有效。关键词：随机分配，概率序列，随机优先级，与配额匹配，学生项目分配JEL代码：C78，D82*剑桥大学菲茨威廉学院经济学系。电子邮件：marek。bojko@outlook.com.Most本文以我在格拉斯哥大学撰写的本科论文为基础，由Herve Moulin指导，我感谢他提供了宝贵的指导和深入的讨论。这项工作还得益于Aytek Erdil、Yehuda John Levy和Nick S cholz的评论。所有的错误都是我的。1导言本文考虑的问题是，将不可分割的对象分配给对对象有顺序偏好的代理，这些代理最多使用一个对象，并且不可能进行货币转移。这类问题称为指派问题。

在本文中，对象既有最大配额又有最小配额，我们假设这样的约束是有约束的，而可行解总是存在性别歧视。虽然匹配理论已经被广泛应用于代理或对象具有最大配额的情况，但关于最小配额匹配的文献只是最近才出现的。我们以学生项目分配问题为例，其中学生是对项目有偏好的代理人，项目是被动的对象。上下q uotason项目由负载平衡和经常关联的组组件驱动。其他激励性的例子包括将学员分配到军种，每个军种都要求最低数量的学员（S"onmez，2013；S"onmez和Switzer，2013）；将学生分配到考虑负载平衡的学校、实验室和辅导班（Fragiadakis等人，2016年）；当每个房间需要最少数量的占用人时（例如，支付与购买家具和取暖相关的固定成本），将j OB分配给工人，将房间分配给室友。在许多考虑公平性的现实环境中，随机化是常见且首选的。在许多分配问题中，它被用作打破联系的手段。我们只考虑顺序彩票机制，在这种机制中，代理只会显示他们对对象的偏好，而不是对彩票的偏好。这一点得到了实验证据的支持，即经纪人的有限理性，对于他们来说，披露对彩票的偏好通常过于复杂（Kagel和Roth，2016）。有序参考归纳出一阶随机优势关系，即确定性对象的偏序，用于比较随机分配。我们将公平性、效率和激励相容性视为我们的设计目标。

如果报告真实偏好的随机分配在任何其他行为下随机支配随机分配，那么随机分配机制是策略证明的，换句话说，报告真实偏好是弱支配策略；如果每个代理都喜欢自己的随机分配，而不是任何其他代理的随机分配，这是没有嫉妒的。在顺序偏好的背景下，我们认为顺序效率是我们的效率概念。如果随机分配不是由任何其他可行的随机分配随机支配的，则随机分配通常是有效的（Bogomolnaia和Moulin，2001）。Bogomolnia和Moulin（2001）的概率序列（PS）机制和随机优先机制已被广泛研究（s ee e.g.Zhou（1990）；Abdulkadiroglu和Sonmez（1998）；Bogomolnaia和Moulin（2001）；Budish等人（2013年），以及其他许多人）。PS mechSee e.g.Roth和Sotomayor（1992年）；Bogomolnaia和Moulin（2001）；Pápai（2000）分别为双面匹配和单面匹配。例如，格拉斯哥大学（University of Glasgow）数学、计算机科学和医学专业的本科生以讲师领导的研究项目的形式完成他们的期末论文或学期论文。在相关学期开始前，导师会发布一份简短的项目主题描述，供其指导。每个项目都有一个相关的最小和最大学生人数，监管者可以支持。在上一学年结束时，学生通过订购他们想写本科学位论文的项目来表明他们的偏好，然后根据这些项目来确定他们的项目。序数彩票机制的术语在《奥戈莫尼亚和磨坊》（2001）中使用。

与常规机制相比，基数彩票机制在彩票上引出冯·诺伊曼效用函数。如下所述，随机优先级和概率串行机制是顺序机制。Hyland and Zeckhauser（1979）的伪o-m市场机制将等收入竞争均衡（CEEI）应用于随机分配问题，可能是随机分配问题中最广泛考虑的主要彩票机制。在文献中，随机优先级机制通常被称为随机序列专政，参见经典分配问题的anism，该问题将每个对象视为可分割的，其中分类分配指代理接收特定对象的概率。时间在0到1之间连续运行，每个代理都可以以恒定的单位速度从其最喜欢的可用对象“吃”。一旦一个对象被完全消耗，代理就会继续吃下下一个最喜欢的可用对象。随机分配通常是有效的、无嫉妒的，并且满足了激励相容性的较弱概念，即弱策略证明，即没有代理人可以获得严格随机的随机分配，从而控制她在真实报告下将获得的随机分配（Bogomolnaia和Moulin，2001）。RP机制从均匀分布中对代理进行排序，然后让第一个代理从剩余的对象中选择她最喜欢的对象，第二个代理从剩余的对象中选择她最喜欢的对象，依此类推。RP机制是战略证明，平等对待；这是事后的效率，但可能会在事前造成明确的效率损失，因此不是一般的效率。我们考虑将这两种机制自然推广到我们的领域。

较低配额下的随机优先级机制（RPLQ）随机统一绘制代理的顺序，并允许代理根据该顺序进行顺序选择。在整个执行过程中，我们会跟踪仍然需要分配的对象的副本数量，以获得可行的解决方案。如果尚未分配的代理总数正好等于这个数字，则我们将其限制为配额较低但未完成的对象。作为一个连续的模拟，在低配额下的概率序列机制（PSLQ）中，我们将代理菜单限制为配额较低的对象，而如果代理继续当前的饮食模式稍长一点，我们将获得不可行的最终分配。这两种机制都保留了其经典对应机制的特性。我们的PSLQ的弱策略证明提供了对附加约束下随机签名问题中的策略问题的洞察。Katta和Sethuraman（2006）表明，当允许管理者报告其偏好的差异时，不存在通常有效、无嫉妒和弱策略证明的机制。在最近的一项工作中，Ashlagi等人（2020年）考虑了分配约束下的学校学生分配问题，在分配约束下，每所学校根据学生的类型对学生子集施加配额。他们基于适当限制提供给学生的菜单的相同基本原则对PS机制进行了概括，并表明在他们的环境中不存在常规有效、类型内无嫉妒且弱策略证明机制。关于toAshlagi et al.（2020），我们可以将对象上下配额的问题视为经典随机分配问题和具有分布约束的随机分配问题之间的中间地带。

因此，有趣的是，尽管我们引入了重要的约束，但仍然保留了一个普通高效、无嫉妒、弱策略证明机制的积极结果。我们的证明取决于整数配额，受现实世界环境的激励。我们还证明了如果配额是非负实数，则不存在顺序有效、无嫉妒和弱策略证明的随机分配机制。我们将该模型推广到具有多个不可分割对象的随机分配问题，其中每个agent最多接收q个对象。b oth机制的扩展非常简单：使用与原始代理相同的首选项创建每个代理的q“克隆”。即使在阿杜卡迪罗格鲁和桑梅兹（1998年）的著作中，PS机制的相应推广也无法与激励相容。经典的分配问题是指将n个不可分割的对象分配给n个代理的问题，其中每个代理只想消耗最多一个对象。Bogomolnaia和Moulin（2001）指出，他们的模型和论文中关于PS机制的所有结果都适用于一个有上限且没有超能力的分配问题。我们总是要求任何项目的上限配额至少与相应的下限配额一样大。由于小岛（2009）的不可能结果，感觉很弱；然而，其余的财产被保留了下来。论文的其余部分组织如下。第2节简要概述了关于最低配额下匹配和分配的相关文献，第3节介绍了符号并正式确定了本文使用的理论框架，第4节和第5节分别定义了RPLQ和PSLQ机制，并讨论了它们的性质。

最后，在第6节中，我们将模型扩展到具有多个不可分割对象的随机分配问题，并在第7节中讨论开放问题和结论。2.大量研究了最大配额下的相关文献分配机制。例如，考虑将项目分配给员工、将学生分配给学校、将房间分配给室友、将时段分配给公共资源的用户（Shapley and Scarf，1974；Roth，1984；Abdulkadiroglu and S"onmez，1999，2003；Abdulkadiroglu et al.，2005b，a；Bogomolnaia and Moulin，2001；Budish et al.，2013）。关于最低配额匹配的文献仍然代表着一个相当狭窄的丰富匹配理论流，尽管在过去几年中，越来越多的论文关注最低配额问题。最低配额主要是在有上下配额和分配限制的择校问题中考虑的（例如Biróet al.（2010）；小岛（2012）；埃勒斯等人（2014年）；H afalir等人（2013年）；Kominers和S"onmez（2013）；Fragiadakis等人（2016年）。由于Biróet al.（2010）证明，在配额较低的情况下，可能不存在稳定匹配，因此许多论文都考虑了软边界。在本文中，我们只考虑硬约束。此外，上述论文只考虑了双边匹配市场。Arulselvan等人（2018年）从算法角度研究了学生项目分配问题背景下的最大权重多对一二分体匹配，其中二分体顶点的一侧具有上限和下限配额。它们描述了当一个实例是NP难的且易于处理时的特征，并为后者定义了一个有效的算法。

然而，他们关注的是基本的公用事业，不考虑激励、公平和效率（关于代理人的福利）。Monte和Tumennasan（2013）考虑了一个相关的问题，在这个问题中，如果每个对象都满足较高的容量，或者满足较低的配额，或者分配给noagent，分配是可行的，这被称为关闭项目。他们展示了在他们的论文中称为“连续独裁”的确定性优先权机制，它不能证明帕累托有效性和策略性，并描述了纠正它的机制。在本文中，我们定义了一个分配是可行的，如果所有的对象都满足他们的配额，我们假设这样的分配总是存在的。我们指出，在学生项目分配中，不希望让学生未分配任务，因为在大多数情况下，学生必须接受项目，而学校会提前调整配额，以便有可行的任务存在。我们将在第7节中讨论我们的模型可能扩展到带结束项目的设置。Budish et al.（2013）和Fujishige et al.（2018）分别将随机分配问题扩展到具有双层次分布和子模块约束的领域，但考虑到学校选择问题，学生对学校有偏好，学校有学生优先列表。由学校动态控制的灵活限制。例如，学校可能会选择一种动态的骚乱，在这种情况下，他们会优先考虑那些没有填满教室的学生，那些只填满较低但没有填满较高配额的学生会获得中等优先级，而其他学生的优先级最低。在我们的环境中，项目没有优先级排序，我们只考虑硬边界，即。

必须满足所有约束条件，才能确定可行的任务。双层次约束结构是指两个层流族的不相交并。有关更多详细信息，请参见其PS机制中的上限。Ashlagi等人（2020年）对s学校选择问题的优先权和PS机制进行了扩展，其中每所学校根据学生的类型对学生的子集施加上限和下限配额。他们对PS机制的概括是基于相同的总体思路，即在约束变得严格时限制学生的菜单。我们在他们论文中的贡献有三个方面：（i）我们更简单的约束结构允许我们使用简单的分析公式化和解决问题，而无需抽象的线性程序，从而允许我们在额外的约束下开发EATE算法背后的核心直觉；（ii）我们描述了我们环境中的日常效率；（iii）与Ashlagi等人（2020年）的广义PS机制相比，我们证明了在我们的环境中，PSLQ机制是缺乏策略性的。设N=[N]={1，…，N}为学生集合，P={P，…，pk}为项目集合。每个项目都有上限和下限配额u（p）∈ N和l（p）∈ N、 u（p）≥ 分别为l（p）。我们假设PP∈Pl（p）≤ N≤聚丙烯∈Pu（p），以确保存在可行的任务。设l=[l（p）]p∈P、 u=[u（P）]P∈低配额和高配额的Pbe向量。每个我认识的学生都有严格的偏好洛弗P。我们假设所有的项目都是所有学生都能接受的。我们用P表示这个偏好域= (i） 我∈Na偏好文件。对于任何偏好文件 学生i，我们用-这是通过忽略学生i而获得的优先成绩。