分配最大化

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

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

立即领取

感谢您参与论坛问题回答

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

+2 论坛币

英文标题：
《Assignment Maximization》
---
作者：
Mustafa O\\u{g}uz Afacan and In\\\'acio B\\\'o and Bertan Turhan
---
最新提交年份：
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 evaluate the goal of maximizing the number of individuals matched to acceptable outcomes. We show that it implies incentive, fairness, and implementation impossibilities. Despite that, we present two classes of mechanisms that maximize assignments. The first are Pareto efficient, and undominated -- in terms of number of assignments -- in equilibrium. The second are fair for unassigned students and assign weakly more students than stable mechanisms in equilibrium.
---
PDF下载：
--> Assignment_Maximization.pdf (184.34 KB)

2022-4-24 18:34:28 上传

扫码加我 拉你入群

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

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

分享0 收藏0 回帖

关键词：最大化 maximization Contribution equilibrium Theoretical

任务最大化穆斯塔法OGUZ AFACAN，IN\'ACIO B\'O和伯坦o图尔哈纳摘要。我们评估的目标是最大化符合可接受结果的个体数量。我们表明，它意味着激励、公平和实施的不可能性。尽管如此，我们提出了两类最大化分配的机制。第一种是帕累托效率，在分配数量方面，处于平衡状态。第二类是公平的未分配学生，与稳定的平衡机制相比，ssign的学生人数略多。JEL分类：D47、C78、D63。关键词：市场设计，匹配，最大匹配，公平，目标分配，学校选择。1引言在本文中，我们考虑了市场设计者所面临的经济问题，他们想要生产匹配的（或对象分配），它响应于代理人的偏好，并留下最不匹配的数量（例如，在个体间的离子匹配中有最大的基数）。研究这一问题的主要动机之一是，在实践中，市场设计师经常对标准程序进行调整，以防止代理商无法匹配。例如，在学校cho ice程序中，分配机制的实际使用通常包括使用标准机制，例如Gale-Shapley延迟录取（Gale and Shapley，1962），然后再使用一些附加程序将不匹配的学生分配到某个学校。然而，这些次要步骤或其他填充剩余座位的特殊方法会导致失去最初使用的机制的属性，例如公平性和策略证明性（Dur和Kesten，2019）。

在本文中，我们从假设市场设计师的目标是让最少的学生数量不匹配开始。虽然这一目标无法通过策略证明机制实现，但我们提出了在学生非策略时产生最大匹配和效率或满足新标准的机制。我们还证明了它们在均衡状态下满足期望的特征，并且随着代理比例的增加，匹配的基数也增加。Mustafa Oguz Afacan：萨班克大学艺术与社会科学学院，O rhanli，34956，土耳其伊斯坦布尔。电子邮件：mafacan@sabanciuniv.edu.InAsio B o o：约克大学，经济学系及相关研究。网站：http://www.inaciobo.com;电子邮件：inacio。lanaribo@york.ac.英国。Bertan Turhan：爱荷华州州立大学经济系，地址：美国伊利诺伊州艾姆斯市海迪厅260号，邮编：50011。电子邮件：bertan@iasta特朗普。伊杜。我们感谢艾哈迈特·阿尔坎、奥汉·艾根、迈赫迈特·巴洛、乌穆特·杜尔、安德烈·贡伯格、伊萨·哈法勒、奥努尔·凯斯滕、维克拉姆·曼朱纳、特里迪布·夏尔马、泰芬·桑麦斯、亚历克斯·泰特伯姆、威廉·汤姆森和乌特库·安沃的帮助。Afacan承认玛丽·居里国际重返社会补助金。B\'o感谢德意志联邦储备银行（KU 1971/3-1）的支持。尽管我们的整个分析自然而然地转化为大多数单元需求离散作业问题，但我们将在整篇论文中介绍学校分配的框架。任务最大化22。相关文献虽然找到最大匹配的算法是众所周知的（Kuhn，1955；Berge，1957），但对使用这些过程引起的激励的研究是有限的，通常依赖于随机机制。

一个例外是isAfacan和Dur（2018），这是本文的后续部分，表明没有任何策略证明和个人理性机制比Boston、Gale Shapley延迟录取和连续独裁机制更能系统地匹配更多学生。Krista等人（2014）考虑在房屋分配问题中产生最大匹配的问题。它们表明，不存在确定性、最大性和防策略性的机制，而是提供了一种防策略性的随机机制，并产生近似最大的结果。博格莫尔尼亚和穆林（2015）评估了马西拉席和嫉妒自由之间的矛盾，没有公平性，这比我们在这方面所考虑的更为公平。BoGoMulnaa和MurLin（2004）考虑AG有二分引用时的随机赋值。在这种情况下，帕累托效率相当于匹配的最大化，而且，由于代理在所有“可接受”的分配之间是不同的，所以即使在确定性机制中，最大化也不会导致激励问题。野田佳彦（2018）在一个约束匹配的一般模型中研究了策略证明机制实现的匹配规模。在某些约束条件下，找到最大基数的匹配也是文献中探讨的一个问题。欧文和曼弗莱（2010）考虑了当优先级有联系时，具有最大基数的席定稳定问题，这是NP困难问题，以及目前的启发式算法。AsGaLi等人（2020）也考虑了分布约束下的对象分配问题。

作者表明，序列独裁和概率序列（Bogomolnaia和Moulin，2001）机制的变体至少分配了在约束条件下可以匹配的代理数，而违反约束的情况相对较小。分配最大化一直是器官交换文献中的主要目标，asit指的是最大数量的转移植物。本文献由Roth等人（2004年）的精液workon肾脏交换发起。在随后的一项研究中，为了适应运输厂运营中的一些物理和地理限制，Roth等人（2005）介绍了成对肾脏交换的概念，即只能在两对肾脏之间进行交换。他们建议从组合优化文献中实现基于优先级的最大匹配算法（Korte和Vygen，2011）。EAM和FAM的第一阶段均采用基于优先级的最大匹配算法。其他一些关于器官交换的研究包括：onmez等人（2018年）、Andersson和Kratz（2018年）、Chun等人（2018年）、Ergin等人（2017年）、Nicol\'o和Rodriguez Alvarez（2017年）和Ergin等人（2018年）。难民重新分配是另一个现实世界中的应用，最大化可能是主要的设计目标。Andersson和Ehlers（2018）研究了难民一旦获得庇护后的住房问题。作者提出了一种易于实现的机制，可以有效地找到稳定的最大匹配。它们表明，这样一种匹配的保证，即住房能够有效地提供给最多数量的难民，而且没有匹配的难民房东对，这是相互促进的。我们的“未分配学生的公平性”削弱了Gale和Shapley（1962）通常的稳定性，因此，当前的研究也与大量关于以不同方式削弱稳定性的文献有关。

其中，Dur等人（2018）、Afacan等人（2017）、Morrill和Ehlers（2018）以及Troyan等人（2018）是该文献中的最新论文。3.模型a学校选择问题包括一组有限的学生I={I，…，in}，一组有限的学校s={s，…，sm}，这是学校的严格优先结构= (s） s∈游泳sis是I上的一个线性阶，一个容量向量q=（qs，…，qsm），以及一个学生严格偏好的函数P=（Pi）I∈一、 其中Pi是student I对s的偏好关系∪ {} 和 表示未分配的选项。WeASSIGNMENT MAXIMIZATION 3denote学生所有可能的偏好集合，由P.让Ridenote至少与Pi相关的良好参考关系，即：sRis′<=> sPis′或s=s′。如果是sPi，学校s是可以接受的toi, 否则是不可接受的。设Ac（Pi）={c∈ S:cPi}.在本文的其余部分，我们考虑元组（I，S，, q） 作为问题的通俗原语，并将其称为市场。我们从问题符号中抑制所有这些，并简单地写P来表示pr问题。匹配是一个函数u：I→ s∪ {} 因此，对于任何∈ S、 |u-1(s)≤ qs。如果u（i）6=. 对于任何k∈ 我∪ S、 我们用uk表示k的分配。让|u|为u下分配的学生总数。如果任何学生i∈ 一、 uiRi. 如果任何学校的sPiui对某些学生来说∈ 一、 |us |=qs。如果没有像sPiui这样的学生-学校对，那么匹配的u是公平的，并且对于一些学生j∈ 是的，我sj。如果个体理性、不浪费、公平，那么一个团队是稳定的。在本文的其余部分，我们将只考虑单独的理性匹配。因此，当我们提到匹配时，除非明确说明，否则我们指的是单独的理性匹配。

让我来做一组配对。一个匹配的u支配另一个匹配的u′，如果对于任何一个学生∈ S、 uiRiu′i，对于某些学生j，则为ujPju′j。如果没有任何其他匹配项占主导地位，则mat chingu是有效的。我们认为，如果|u|>|u′|，则一个匹配的u尺寸方向主导另一个匹配的u′。如果匹配的u不是按大小控制的，则为最大值。机制ψ是从P | I |到M的函数。如果不存在问题P，那么机制ψ是策略证明，并且具有错误偏好P′的学生I与ψI（P′I，P′）是一致的-i） πψi（P）。如果对于任何问题P，φ（P）不在尺寸上支配ψ（P），而对于某些问题P′，ψ（P′）在尺寸上支配φ（P′）。无机制ψ是最大的，如果它在大小上不受任何其他机制的支配。我们首先观察到，对于我们正在考虑的分配问题，四种常见且被考虑的著名机制——延迟接受（DA）、顶级交易周期（TC）、波士顿（BM）和连续独裁（SD）——中没有一种是最大的。提议1。DA、TC、BM和SD都不是最大值。当然。设I={I，I}和S={a，b}，每个都有单位配额。让Pi:a，b， Pi:a，. 优先级是这样的，代理I是目标a的最高优先级。然后，DA、TC和BMT的结果是相同的。如果我们为他们的结果写u，那么ui=a和ui=. 同样，对于SD，让我们考虑代理ICAMS RST的排序。然后，SD结果与u相同。这表明这些机制中没有哪一个是最大的，因为匹配的u′i=b和u′i=a是单独的，匹配的试剂比u多。鉴于已知机制缺乏极大性，在本文的其余部分，我们介绍了两种极大机制并研究了它们的性质。3.1. 一类有效的最大机制。

给出一个问题P和一个学生s的枚举，在I（I，…in）中，步骤0。设ξ=M。步骤1。子步骤1.1。定义集合ξ ξ如下：注意，我们使用的大小控制和最大化的概念是在一个匹配中涉及的代理（或节点）集合中。在大多数图论文献中，匹配的基数是在作为匹配一部分的图的边集合中度量的。当康塞德环集的边缘有一个最大和最大基数匹配之间的差异，在我们的设置中，这些是等价的：最大匹配总是最大的。关于这些机制的描述，读者可以参考BDulkadiroglu和S¨onmez（2003）。分配最大化4ξ={u ∈ ξ：ui6=} 如果u ∈ ξ，即ui6=ξ一般来说，对于每k≤ n、 子步骤1。k、 定义集合ξk ξk-1as如下：ξk={u ∈ ξk-1：uik6=} 如果u ∈ ξk-1这类微体6=ξk-1否则，步骤1以选择匹配的选项结束∈ ξn.第2步。一般情况下：子步骤2。k、 设|u为在程序的前一步中获得的匹配。如果|u没有引入改进链或循环，则算法以|u的最终结果结束。否则，选择这样一个链或循环，并通过将所选链（循环）中的每个学生分配到链（循环）中他喜欢的学校来获得新的匹配，然后转到下一个子步骤。定理1。每个EAM机制都是最大且有效的。然而，请注意，尽管EAM机制是最大的，但它们并不公平。一类最大且公平的未分配学生机制。如果没有学生-学校对（i，s），且ui=而我sj代表一些j∈ us.如果对于任何问题P，ψ（P）对未分配的学生是公平的，那么机制ψ对未分配的学生是公平的。下面是这个类中每个机制的工作原理的描述。

给出一个问题P，第一步。选择一个n EAM机制ψ，让ψ（P）=u。第二步。一般来说，子步骤2。k、 设|u为上一步中获得的匹配。如果对于未分配的学生来说√u是公平的，则算法将以结果√u终止。否则，选择一对学生学校（i，s），使sPi, ui=, 而我sj代表一些j∈ §us.将学生i安排在学校s，让低优先级的学生不被分配，同时保持其他所有学生的分配不变。请注意，在每个子步骤中，分配的学生人数都是保留的，~u是最大的。因此，我们有| |us |=qs。让^u成为获得的匹配，并移动到下一个子步骤。由于在每个子步骤中，优先级别较高的学生被安排在学校，而优先级别较低的学生被安排在学校，而且学生和学校都是有限的，因此算法会在无数轮中终止。上述程序定义了一类机制，每个机制都与第一阶段EAM机制的不同选择以及第2步课程中的学生-学校对相关联。我们称之为“公平分配最大化”（FAM）机制。定理2。每个FAM机制对未分配的学生来说都是公平的，并且是最大的。当然。设ψ为fam机制，u为其第一步的结果。由于u是EAM机制的结果，在ψ的第2步中，没有学生被分配到他不可接受的选择中，ψ是个体理性的。因为u是最大的，并且在第2步中指定的学生人数保持为|u|，所以ψ是最大的。此外，由于ψ在没有学生学校违反未分配学生的公平性之前不会停止，因此ψ对未分配学生也是公平的。4.激励与均衡分析在本节中，我们展示了EAM和F AM类的机制在均衡结果方面具有惊人的调节特性。

通过机制席，考虑偏好报告博弈归纳分配最大化问题。在问题P中，偏好提交P′=（P′i）i∈iisa（Nash）平衡ψif对于每个学生i，ψi（P′）Riψi（P′i，P′）-i） 对于任何P′i∈ 让我Ohm 是一组在任何问题上都允许平衡的机制∈ P | I |。在本节的其余部分中，我们仅考虑Ohm.提议2。每个EAM和F AM mec hanism都在Ohm. 此外，对于任何问题，EAM机制都有一个唯一的均衡结果，它相当于连续独裁的结果，而学生顺序与EAM机制中使用的相同。因此，命题2表明，EAM的均衡结果不仅是帕累托有效的，而且将与常用的防策略机制一样匹配。我们的下一个问题是，在平衡状态下，机制如何在分配数量方面进行比较。为此，我们定义了均衡中规模主导的概念。定义1。对于给定的市场（I，S，, q） 在平衡态下，一个机制ψ的大小决定了另一个机制φ的大小，如果对于任何问题P和每个平衡态P′，P′分别在ψ和φ下|ψ（P′）|≥ |φ（P′）|，存在一个问题P*对于每一个平衡点^P，~Punderψ和φ，分别为|ψ（^P）|>φ（~P）|。定理3。在任何市场（I，S，, q） 然而，没有哪种EAM机制是由一种均衡的个体理性机制主导的。虽然我们没有与上述F AM机制类似的结果，但我们能够比较F AM均衡和DA弱优势策略均衡下分配的学生数量，这是讲真话的。定理4。