对优先事项进行分类，以确保延期验收明显有效

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

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

立即领取

感谢您参与论坛问题回答

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

+2 论坛币

英文标题：
《Classification of Priorities Such That Deferred Acceptance is Obviously
  Strategyproof》
---
作者：
Clayton Thomas
---
最新提交年份：
2021
---
分类信息：

一级分类：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系统重叠），非合作计算环境的协调、规范和形式化方法。该领域还涉及博弈论在电子商务等领域的应用。
--

---
英文摘要：
  We study the strategic simplicity of stable matching mechanisms where one side has fixed preferences, termed priorities. Specifically, we ask which priorities are such that the strategyproofness of deferred acceptance (DA) can be recognized by agents unable to perform contingency reasoning, that is, \\emph{when is DA obviously strategyproof} (Li, 2017)?   We answer this question by completely characterizing those priorities which make DA obviously strategyproof (OSP). This solves an open problem of Ashlagi and Gonczarowski, 2018. We find that when DA is OSP, priorities are either acyclic (Ergin, 2002), a restrictive condition which allows priorities to only differ on only two agents at a time, or contain an extremely limited cyclic pattern where all priority lists are identical except for exactly two. We conclude that, for stable matching mechanisms, the tension between understandability (in the sense of OSP) and expressiveness of priorities is very high.
---
PDF下载：
--> Classification_of_Priorities_Such_That_Deferred_Acceptance_is_Obviously_Strategyproof.pdf (366.74 KB)

2022-4-24 15:26:41 上传

扫码加我 拉你入群

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

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

分享0 收藏0 回帖

关键词：Environments Coordination Applications Contribution Game Theory

优先权的分类，以便延迟接受具有明显的战略性。Clay TON THOMAS，美国普林斯顿大学。我们研究了稳定匹配机制的战略简单性，其中一方有固定的偏好，称为优先权。具体地说，我们询问哪些优先级可以使无法执行应急推理的代理识别延迟接受（DA）的策略性，即，DA什么时候是明显的策略性预防（Li，2017[Li17]）？我们通过完全描述使DA具有明显的战略证据（OSP）的优先级来回答这个问题。这解决了Ashlagi和Gonczarowski的一个公开问题，2018[AG18]。我们发现，当NDA是OSP时，优先级要么是非循环的（Ergin，2002[Erg02]），这是一种限制性条件，允许一次仅对两种试剂的优先级差异太大，要么包含一种极为有限的循环模式，其中除两种试剂外，所有优先级列表都是相同的。我们的结论是，对于稳定的匹配机制，不可理解性（在OSP意义上）和优先级表达之间的紧张关系非常高。Clayton Thomas 11简介机制设计的中心任务是在存在战略行为的情况下实现理想的结果。传统上，这是通过防战略的方法来实现的，在这种方法中，讲真话是一种占主导地位的策略。然而，假设代理人不是完全理性的，并且并不总是能够确定他们的主导策略。为了确保在这样的环境中取得成功，机制必须在战略上简单，也就是说，讲真话应该很容易被视为一种主导战略。近年来，明显的战略可靠性（OSP）概念已成为战略简单性的基本标准[Li17]。

简言之，OSP机制是指一个代理可以根据自己的行为识别出的机制，该代理不完全理解他们正在参与的机制，但只理解遗传算法的可能结果如何取决于他们自己的行为（因此，该代理无法执行证明某些策略占主导地位所需的应急推理）。通过消除执行偶然推理的需要，inOSP机制的主导策略更容易识别，对于有限的复杂代理来说，游戏变得更简单[Li17，ZL17]。匹配环境对于复杂度有限的代理来说是至关重要的环境。在现实世界中，集中机制被用来匹配劳动力市场中的工人与企业、住院医师与医院、学生与择校环境中的学校。在许多这样的市场中，稳定性是一个主要目标，并且通常是防止市场崩溃所必需的[Rot02]。从形式上讲，稳定性意味着没有一对不匹配的代理希望与指定的合作伙伴决裂，而是彼此配对。[GS62]的“受欢迎的接受”（DA）算法有效地确定了稳定的匹配，并为市场的一方提供了策略支持[DF81]。这些吸引人的理论特性导致许多现实世界的匹配市场实施DA。不幸的是，参与这些机制的代理人通常没有认知资源来准确识别和理解他们应该如何参与该机制，并且在实践中，即使该机制是无策略的，他们也往往会做出代价高昂的战略决策[HMRS17，RJ1 8]。

这就引出了一个问题：为什么被要求的验收应用程序在战略上是复杂的，尽管它是战略证明？为了了解匹配市场的战略复杂性，我们研究了具有一个战略方面的稳定匹配机制中的明显战略安全性。在这样的环境中，一组n 战略申请人（例如，与学校匹配的学生）被分配到一对一匹配到一组n 职位（如学校）。申请人对职位有偏好，从最喜欢的职位到最不喜欢的职位，如果他们认为这对他们有利，他们可能会误报。另一方面，职位对申请人的偏好是固定的、非战略性的，因此，长期优先于申请人。我们关注的是申请者提出延迟接受（DA），这是战略申请者的标准稳定匹配机制。由于稳定匹配问题至关重要，因此对延迟接受的战略复杂性有一个明确而准确的理解至关重要。此外，对于无法执行偶然推理的代理，明显的战略证明已被确定为战略简单性的基本理论标准。因此，本文的中心问题是：对于哪些优先事项是战略证明？没有一种稳定的匹配机制可以对市场的两个方面都提供战略支持[Rot82]。因为所有明显的防战略机制都是防战略的，所以将我们的注意力限制在一个战略方面是必要的。DA是一种独特的稳定匹配机制，对一方而言是无策略的[GS85，CEPY16]。

因此，对于发现明显具有策略性的稳定匹配机制的问题，限制对DA建议的关注是不会失去通用性的。Clayton Thomas 2这篇论文是[AG18]的后续，AG18是第一篇研究OSP在稳定匹配机制中的实现的论文。[AG18]提供了一个优先级条件，该条件有助于OSP的实施。如[Erg02]所述，这种情况是非循环的。无环性是优先权的一个重要条件，直觉上说，优先权只能在两个代理的相邻集合上不一致。对于mally来说，如果申请者可以被分成几个小组，那么一组优先级是非循环的S, . . . , Sk, 与|Si| ≤ 每人2个i, 这样每个职位都会优先考虑应聘者Si比申请者Sj任何一对i, j 具有j > i （请参见位置2.8）。[AG18]证明，只要优先级是非循环的，DA isOSP就可以实现。然而，[AG18]表明，要实现OSP，优先级不需要非循环性。也就是说，它们给出了一个循环但可实现的优先级示例。不幸的是，[AG18]还证明了存在固定的优先级集，因此无法使用OSP机制实现DA。然而，它们并不能准确地证明哪些优先级是OSP可实施的，因此有可能存在OSP可实施优先级，这些优先级在某种有用的意义上是“多样的”（也就是说，可能存在允许位置之间无任何差异的优先级，以便在某些匹配环境中捕获实际有用的约束）。我们发现，对于稳定的匹配机制，OSP可实现优先级和非循环优先级之间的差距非常小。

也就是说，通过对哪些优先级是OSP可实现的进行分类，我们表明，使用循环但OSP可实现的优先级几乎不可能。我们现在举一个例子，说明6名申请人和6个职位的OSP优先顺序。我们把优先事项列为一个列表，从最优先的事项开始往下写。在本例中，职位1、2、3、4的优先级与所有申请人相同，但5和6的优先级略有不同（我们用括号突出显示了5和6与1、2、3、4不同的申请人对）：1、2、3、4：a  b  c  d  e  f5 : a  (c  b)  (e  d)  f (*)6 : (b  a)  (d  c)  (f  e)事实证明，除了OSP之外，所有循环优先级都可以由非循环优先级和与本例完全相同的优先级（推广到任意数量的应用程序）构成。特别是，当某些申请人的优先顺序是循环的时，除两个职位外，每个职位都必须有相同的优先顺序列表（此外，剩下的两个职位必须以仅适用于相邻申请人的精确模式进行区分）。我们将此类优先级称为有限循环（定义3.1）。当优先级是非循环的时，[AG18]表明用于DA的OSP机制是由我们称之为2Tr的机制的简单组合构成的。他们的机制在某种程度上类似于一个连续的独裁统治（申请者以某种固定的顺序到达，并与他们最喜欢的剩余职位永久匹配），但两个申请者可能同时被解雇。这两个代理通过机构2Tr分配到其余位置。当优先级是有限的循环时，OSP机制可以由2Tr和一个相当简单的机制（我们称之为3Lu）组合而成，该机制一次与三个申请者交互。

有趣的是，这意味着在某种意义上，只有两种“不可约”的、明显具有策略性的稳定匹配机制，即2Tr和3Lu。我们描述的cr-ux围绕着证明当优先级不受限制时，DA是不可实现的OSP。下面我们简要介绍一下这个证明是如何实现的。有趣的是，在组合机制中，没有任何代理参与两个不同的“子机制”2Tr或3Lu。这给了一种强烈的感觉，在这种感觉中，2Tr和3Lu可以构建出永远稳定的OSP匹配机制。Clayton Thomas 31 a b c2 b c a3 c a b（a）非OSP b y[AG18，第4节]a b c2 a b cc a b c2 a b cc b aa b c2 a b cb c a（b）非OSP由[AG18，附录b]和b.2.11 a b c2 a c bc b a（c）非OSP由b.2.21 a b c2 b a cc b a（d）非OSP由b.2.31 a b d2 a b d c c3 a b db a（e）非OSP由b b由b.4节图。1.此处显示的每一组优先级都不是OSP可实现的。此外，OSP无法实现的任何一组优先级都包含这些优先级中的一组作为子paern（直到重新标记）。证明的结构允许OSP可实现优先级的另一个特征。具体而言，当且仅当优先权的限制（即限制对职位和申请人的某些子集的关注）不等于图1中列出的优先权集之一时，一组优先权才是OSP可实施的。因此，我们的特征不仅意味着本质上只有两个OSP稳定匹配机制，而且在某种意义上，存在一个“不可约”非OSP优先级集的有限列表。总之，我们的描述可以简明扼要地表述如下。我们用定理3.2、定理4.1和定理4.2的简单组合来证明第4节中的主要定理。定理（主要定理）。

对于任何一组优先级q, 以下是等效的：（1）具有优先权的延期验收q OSP是可实现的。(2) q 是有限的循环。（3） 具有优先级的延迟接收OSP机制q 可由2Tr和3Lu组成。（4） 不限制q 在重新标记之前，与图1.1.1“直觉和证明布局”中显示的任何优先级集相等。我们现在给出非正式的直觉，说明为什么人们可能会期望对优先级集进行如此严格的限制具有明显的策略性。显而易见的战略证明要求，每次管理层执行该机制时，如果他们完全诚实（对于该机制的其余部分），可能发生的最糟糕的事情不会比他们撒谎时可能发生的最好的事情更糟。当优先级是非循环的时，最多有两个申请者被某一组职位排在第一位。如[AG18]所示，这些申请者可以通过机制2Tr以OSP的方式分配到职位，我们在图2中回忆了这个机制。2Tr机制只与前两名申请者通信，最多查询两次，也就是说，只有这两名申请者处于“活动”状态，每个申请者最多“移动”两次。为了使循环优先级成为OSP，机制中必须发生以下两种情况之一：一些申请者必须移动两次以上，或者两个以上的申请者必须在某个点处于活动状态。正式地说，在某个州h 申请者a 如果a 移动h, 或者如果a 他们过去已经搬家了，但他们的对手还没有完全确定。克莱顿·托马斯4U :a  b  . . .a  b  . . ....V :b  a  . . .b  a  . . ....（a） （b）。。。抓住任何v ∈ U ∪ V \\ {u }克林查尼u ∈ U（b） （a）。。。抓住任何u ∈ U ∪ V \\ {v }克林查尼v ∈ U ∪ VV . . .图2。

一个非循环优先级的例子，以及匹配“前两名”申请人的机制2Tra, b （在一系列职位中，谁拥有最高优先权U 和V , 分别）。“锁定”一个位置x 允许申请人退出机制，并永久匹配到该职位。在应用程序所在的右上角节点b acts，申请人a 已经搬家了，但他们的匹配还没有确定，所以有两个申请者是活跃的。这种机制是OSP，因为在第二个节点a acts（即bo）右节点），a 他们能在比赛中获得他们最喜欢的位置吗V , 或者（如果）b （已经稳住了那个位置）他们可以稳住任何东西U （他们被要求在第一个节点处抱住）。从直觉上看，在OSP延期接收的实施中，没有一个申请者可以做出两个以上的非琐碎动作，因为申请者很难保证自己处于一个没有最高优先权的位置。这是因为当一些申请人a 提议这样做x, 更高优先级的申请者在以后向该职位提出申请几乎是有风险的。如果OSP机制从申请人处了解a 它们的旋涡位置是x, 但是a 后来被拒绝x, 他们必须能够保证自己在第一次担任职务时的每一个职位。因此，该机制不能再次询问申请人a 进一步的问题会导致a, i、 e.提出的第二个问题a 应该决定a’这是最后一场比赛。三位申请人可能会在OSP实施延期接收的某个时候积极参与。事实上，3Lu就是这样。然而，这只能以非常特殊的方式发生。允许a 成为这三位申请者中的第一位。

事实证明，为了使这个ofDA实例成为OSP，该机制必须从提出的第一个问题中推导出来a 另一个申请人（打电话给他们c) 不可能获得某个职位。由于DA的定义，这意味着机制必须知道a’她最喜欢的位置c 必须比a在这个位置。但如果匹配机制是OSP，那么它唯一能推断出a’sfavorite的位置是x 是为了a “抱住”除了x, 也就是说，a 必须能够保证自己在其他任何位置x 如果他们愿意。因此a 除此之外，任何职位都必须具有最高优先权x. 对于a 为了在他们搬家后保持活跃，必须有一位申请人b以至于x 有优先权b  a  c. 此外b 和c 同时，要想积极主动，还必须有一个职位y 为什么c  b.这个非正式的论点要求ins解释为什么图3的优先级集可能不是三个申请人和三个职位的唯一循环但OSP优先级集。事实的确如此。此外，删除申请人a 通过反复考虑和应用论点，我们可以预期b 应该是第一申请人（除a) 除了一个以外，每个位置都有。实际上，LimitedCycle priority集合这样的等式（*）满足这样一个递归属性，其中Removing对于熟悉[BG16]的读者来说，这正是申请人u 可能会成为一个“潜伏者”x.Clayton Thomas 5他们的顶级申请人产生了另一个相同模式的有限循环优先级集。这也为证明的结构提供了直觉——OSP递归施加的高要求约束，以及图3的推广，如等式（*），是唯一循环但OSP优先级集的例子。a b ca c b3 b a cFig。3.