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

OSP但循环案例更严格地说，我们的证明首先列举了申请人和三个职位的所有循环优先级。事实证明，在重新标记之前，只有一种情况是OSP（即图3的情况），而所有其他情况（即图1的（a）-（d）都不是n-OSP。正如[AG18]中所指出的，只有当优先权的每一个限制（对某些子类申请人和职位）也是OSP时，一组优先权才可以是OSP（我们在EMMA 2.6中回顾了这一点）。因此，三个申请人和职位只有一个循环案例是OSP，这一事实提供了一种非常可控的形式，四个申请人和职位的循环和OSP优先级可以采用这种形式。唯一这样的非平凡情况是有限循环情况，即图1中的OSP和（e），它不是OSP。这再次给出了一个非常可控的形式，超过四个申请人和职位的OSP优先级可以循环使用，事实上，这表明对于任何数量的代理，所有OSP优先级都必须是有限的循环。1.2讨论虽然我们的结果允许一个循环的但OSP优先级的一般类别，但像等式（*）这样的优先级与非循环偏好相比，明显不那么“多样化”。在非循环偏好中，所有职位的HALF可能会给一些申请人a 但另一半可能会给一些申请人b 首要任务。但我们的描述表明，当某些申请人的优先顺序是循环的时，所有职位的优先顺序必须相同，只有两个职位例外。因此，优先权的表达能力非常有限——优先权可能一次只影响两个申请人，或者只影响两个职位（以非常可控的方式）。将我们对OSP延迟接受机制的描述与[Tro19]中介绍的顶级交易周期的OSP实现进行比较是有意义的。

OSP对toptrading cycles的实施也有相当严格的限制，但例如，可能会逐渐赋予申请者一组更大、更大的位置，他们可能会“成交”，并多次查询这些位置。如果申请人的优先职位不在该“授权”范围内，申请人将不会获得任何职位，并且根据其他申请人的行动，他们可能会逐渐被授予更多职位，并被多次要求在该机制中行事。相比之下，在2Tr和3Lu机制中，因此在所有延迟接受的OSP实现中，申请人最多被调用两次。这可能表明延迟承兑从根本上来说比顶部交易周期更“战略复杂”，因为使用明显的策略性限制似乎对延迟承兑比顶部交易周期要求更高。也就是说，“更复杂”的延迟接受机制应该有一个更小的OSP子集，其可能的OSP与申请人的互动应该更有限。另一方面，在OSP延迟接受的实施中（在机制3Lu期间），三个代理可能同时处于活动状态，这在顶级交易周期中是不可能发生的，因此比较是微妙的。这符合我们的直觉，即为什么DA的OSP实现不能要求代理移动两次以上。在DA，很难保证申请人在没有最高优先权的情况下获得任何职位。另一方面，在执行顶级交易周期的过程中，投保人可以保证获得一个位置（至少与当前位置）（直接或间接）的任何位置相同。

O顶级交易周期的SP实现正是利用了这一事实，以便（潜在地）与代理进行多次交互。Clayton Thomas 6Limited Cycle priorities（有限循环优先级）以及除OSP可实现优先级之外的所有循环优先级，是[AG18]所用示例的推广，该示例旨在证明非循环性对于OSP可实现性不是必需的（因此，我们的机制3Lu概括了他们构建的机制）。这让我们非常惊讶。事实上，我们研究这个问题的第一个目标是确定有固定优先级的延迟接受的有趣的新案例（例如，一次超过3名申请人活跃，或一名申请人移动超过两次）。最后，我们证明没有这样的案例。我们认为，这一结果进一步证明了以下观点：虽然明显的策略性是机械设计简单性的一个基本概念，但需要新的定义，以允许仍然具有策略性简单或易于解释的实用机制。研究图1中“不可简化”的非外包服务提供商优先事项可能是制定此类定义的一个小垫脚石。1.3其他相关工作关于明显的战略可靠性和战略简单性的各种相关概念的工作正在迅速增长。[Li17]介绍了OSP，用这个概念研究了升价拍卖，并证明了序列专政是OSP可实现的，但具有初始禀赋的顶级交易周期不是OSP可实现的。[AG18]是本论文最相关的工作，是[Li17]的首次发布后续工作。[Tro19]和[MR20]研究没有初始捐赠的顶级交易周期，并对那些使顶级交易周期OSP可实施的优先级进行分类。

我们的分类完成了[AG18]发起的系列研究，回答了他们的主要开放性问题。本论文比之前关于优先权基础上的OSP匹配机制的工作涉及更多，为了完成我们的分类，我们必须仔细分析优先权集的子模式，并证明某些优先权集导致的几种特定匹配机制是无法实现的。[BG16]研究了一系列社会选择设置，并研究了OSP和帕累托最优社会选择函数的可能性。周期性偏好的延迟接受不是帕累托最优[Erg02]，因此不属于这种范式。[PT19]为一大类他们称之为“丰富”的领域提供了各种简化结果。[Bad19]为房屋匹配问题构建了一个有趣的OSP机制，在初始捐赠中，代理人具有单峰偏好。[Mac20]对OSP机制进行了广泛研究，证明了几种等价性和简化。[ZL17]提供了一个决策理论框架，证明了显而易见的优势。[GL21]提供了与SP可实现性等效的任何环境的一般条件，并提供了一种时间检查该条件的算法，该算法在计算社会选择函数的表（即，列出代理类型的每个可能元组的结果的表）中是多项式。对外包服务提供商的概念进行了补充和概括。[PT19]介绍强明显的战略证明和一步预见的概念，显然是战略预防机制，这是OSP机制的一个子集，它甚至“更简单”地被视为战略证明。

[TM20]引入了非明显可操作机制的概念，它概括了防战略机制，允许进行一些战略操作（但不是“明显的”操作）。[LD20]朝着另一个截然不同的方向发展，为战略上简单的代理设计收入最大化的机制（例如，他们可能会采用计划主导的策略，但不会采用明显主导的策略）。致谢。我们感谢Yannai Gonczarowski为本手稿的呈现提供了宝贵的指导。我们感谢伊泰·阿什拉吉、琳达·蔡和马特·温伯格的有益讨论。克莱顿·托马斯72场预赛和之前的结果2。1机制和明显的战略证明（有序）环境E = (Y, （T）i)i ∈N） 由一系列结果组成Y , 一组代理（也被称为玩家）N=[n], 和T型i对于每个代理i ∈ N.每种类型ti∈ Ti与弱秩序相对应tii过度的结果Y, 这代表了特工i 将每个结果按Y当他们的类型是ti. 社会选择函数E 这是一个映射f : T×··×Tn→ Y 从每个代理的类型到结果。在机构设计中，最常被研究的问题是一个整体性的社会选择函数：定义2.1。社会选择函数f 是否具有战略可行性i ∈ Nt∈ Ttn∈ Tn,和t′i∈ Ti, 我们有f (ti, t-i) tiif (t′i, t-i).为了研究认知受限的代理人（他们可能不完全理解他们正在玩的游戏），还需要知道社会选择功能是如何实现的，即社会规划者如何与战略代理人互动以进行计算f . 这是通过一种机制实现的。机械论E 是一个元组G=(H, E, Pl，（T）i(·))i ∈Ng) 这样：oH 是一组状态（也称为d节点），以及E 是状态之间的一组有向边，例如(H, E) 形成一棵有限的定向树（每个边缘都指向根部）。

让这组叶子被表示出来Z , 让根被表示出来h. 无论如何h ∈ H, 让我们成功吧(h)  H是一组节点，这些节点是h 在游戏树中Pl:H \\ Z → N是player choice函数，它为每个非叶节点添加标签H \\Z 与在该节点行动的代理一起每人i ∈ N和h ∈ H , 我们有i(h)  Ti代理的类型集i 在h. 对于任何人来说，这些都必须满足h 与Pl(h) = i, 集合{Ti(h′)}h′∈成功(h)形成T的一个分区i(h).– 如果Pl(h) ≠ i, 那么无论如何h′∈ 成功(h), 我们没有i(h′) = Ti(h).o g : Z → Y 在每个叶节点上标记一个结果Y .对于类型t∈ Ttn∈ Tn, 我们让G(t, . . . , tn) 标志g(l), 哪里l 是唯一的叶子节点H 与(t, . . . , tn) ∈ T(l) × . . . ×Tn(l). 我们说G实现了社会选择函数f 惠恩(t, . . . , tn) = f (t, . . . , tn). 请注意，节点的集合h 在哪里(t, . . . , tn) ∈ T(h) ×··×Tn(h) 始终形成一条从根到叶的路径l. 直觉上，这条路径就是G的“执行路径”(t, . . . , tn). 节点h Pl在哪里(h) = i 代表了一个机械主义的球员i 问题是“哪个集合{Ti(h′)}h′∈成功(h)你喜欢什么类型的人？”。如果特工i 带类型ti老实说，该机制只到达节点h 如果ti∈ Ti(h), 而经纪人将“扮演一个角色”引领这场独一无二的比赛h′具有ti∈ Ti(h′).显而易见的战略可靠性（OSP）可以定义如下：定义2.2（OSP，[Li17，AG18]）。结束E OSP在节点上吗h ∈ H 如果以下情况成立：如果(h) = i, 每ti∈ Ti(h), 允许h′∈ 成功(h) 成为的唯一继承节点h 以至于ti∈ Ti(h′).

然后每一片叶子l 它是h 以至于ti∈ Ti(l), 每一片叶子l′它是h 但不是h′, 我们有g(l) tiig(l′).如果每个节点都是OSP，那么机制G就是OSPh ∈ H.社会选择函数f 结束E 如果存在实现OSP的OSP机制，OSP是否可以实现（简称OSP）f .微弱的命令结束了Y 是一个可反射的和可传递的二元关系Y 这样的话x, y ∈ Y , 我们有一个x  y 或y  x. 我们写a  b 当我们a  b 但我们没有b  a.在技术方面，我们认为一种机制是一种确定性的完全信息形式的博弈，其结果是Y . 正如[AG18]中所述，将注意力限制在这些机制上不会失去普遍性。Clayton Thomas 8换句话说，一种机制是OSP if，对于每个节点h 你是特工吗i 是不是要采取行动，如果i 在接下来的比赛中继续诚实地比赛对我们来说并不糟糕i比如果i 在节点处偏离h. 特别是，这意味着该机制（以及它所实现的社会选择功能）具有战略可行性。2.1.1 OSP可实施性的单调性。环境的子域E = (Y , （T）i)i ∈N） 这只是另一个环境E′= (Y′, （T′）i)i ∈N） ，其中Y′ Y 和T′i Ti每人i ∈ N=[n]. 对社会选择函数的限制f 到E′这就是社交功能吗f |E′以至于f |E′(t, . . . , tn) = f (t, . . . , tn) 每人(t, . . . , tn) ∈ T′×。×T′n, 前提是f (t, . . . , tn) ∈ Y′给每个人(t, . . . , tn) ∈ T′×···×T′n.下面的引理本质上是[Li17]开创的“修剪”技术，并在大多数已知的OSP机制工作中使用。引理2.3。如果一个社会选择函数f 结束E 是OSP，那么每个限制f |E′属于f 到子域E′也是OSP。证据考虑任何OSP实现Gf 结束E.

构造一个G′over机制E′=(Y′, （T′）i)i ∈N） 具有相同的状态集、相同的玩家函数Pl和相同的结果函数g. 定义类型集合T′i(h) = T′i∩Ti(h) 每一次都没有h 关于G′。很明显，G′实现了f |E′. 更重要的是，它直接来自于这样一个定义：如果G′不能成为OSP，那么G就不能成为OSP，这是一个矛盾。2.2匹配机制我们的主要利益是与n 申请人及n 位置。结果Y 这种环境的一部分包括所有申请人分配给某个（不同）职位的一系列任务。就是，Y 是所有bije事件的集合μ 在申请者和职位之间。我们通常用字母来表示申请人ai或者{a, b, c, . . .}, 我们把位置表示为pi还是整数x ∈ {1, 2, 3, . . .}. 我们让μ(ai) 表示位置ai分配给，让μ( pi) 指被分配到该职位的申请人pi.每个申请人ai, 类型集ai由整个订单的所有总订单组成n 位置。每个申请者在分配给同一职位的匹配中是不同的。正式地，f或ti∈ Tai, 我们有μ tiiμ′如果且仅当μ( ai) tiμ′(ai). 我们指的是应用程序类型的偏好，而不是位置，并表示它们i∈ Tai. 我们通常会抑制noμ iiμ′赞成简单地μ(ai) iμ′(ai).考虑一组q = {i}i ∈[n]对申请人的偏好，每个职位一个。我们将其称为优先事项，因为它们是固定的，不被认为是战略性的。匹配的μ 是稳定的，如果，对于每一对a, p o申请者和职位μ(a) ≠ p, 我们要么有μ(a) ap,或μ(p) pa. 也就是说，没有一对求职者和一个职位愿意彼此匹配，而不是根据自己的任务进行匹配μ.

请注意，我们将注意力限制在完整的首选项列表（每个申请人对每个职位进行排名，反之亦然）和具有相同申请人和职位数量的环境（因此，稳定匹配必须使每个申请人和职位匹配）。[GS62]的著名结果是，存在唯一的申请人最优稳定匹配（即，在任何稳定匹配中，每个申请人都被分配到他们所分配到的一组位置中，他们最喜欢的位置）。此外，这种匹配可以在申请人提出延期接受的多项式时间算法中找到。因此，我们定义了函数的社会选择q如下所示：这是对概念的轻微滥用，因为适当的延迟接受算法构成了一种机制，但我们使用q指社会选择函数。克莱顿·托马斯9定义2.4。对于一组固定的优先级q = {i}i, 我们让爸爸q表示社会选择函数，对于任何一组申请人的偏好{a}a, 输出申请人的最佳稳定匹配。这个社会选择函数是策略证明[DF81]，本文的主要问题是当DAq显然是更具策略性的。定义2.5（外包服务提供商优先级）。我们说有一系列的优先事项q = {i} 属于n 位置超过n申请人可以实施OSP（或简称OSP），前提是DAqOSP是可实现的。2.2.1外包服务提供商优先级的单调性。第2.1.1节描述了OSP机制的一般单调性条件：将注意力限制在每个代理类型的子集上可以保留OSP属性。在将环境与固定优先级相匹配的情况下，我们还需要考虑第二种单调性。引理2.6。考虑一组优先级q = {i}i属于n 位置超过n 申请人。

如果q 这是OSP吗m ≤ n 以及任何子集S 属于m 申请人及T 属于m 立场，限制q′= {i|S}i ∈T也是OSP。证据让G成为DA的OSP实现q. 考虑任何子域E′其中申请者S 将所有职位排列在T 在所有不在T , 所有不在学校的申请者S 有一个固定的偏好排名，将不同的位置放在第一位S 作为他们的首选。在一系列带有偏好的错误接受中E′, 所有申请者不在S 会立即把seto推荐给他们的首选，而且永远不会被拒绝。此外，境外的代理人S 将不会影响DA的运行S 和偏好E′. 因此，考虑G胡E′. 将G′限制为S 给出DA的OSP实现q′. 2.2.2循环优先级。在研究DA的背景下引入了循环优先级q根据[Erg02]，它将非循环优先级准确地归类为q总是会产生一个匹配，这对申请者来说是帕累托最优的。定义2.7（[Erg02]）。优先级设置{i}i如果存在应用程序，则N上是循环的a, b, c 和位置i, j 以至于a ib ic 和c ja.否则，优先级被称为非循环。非周期性条件非常强，即非周期性不允许在优先级上有广泛的多样性。我们通常使用以下特征来描述非循环优先级：命题2.8。当且仅当存在有序分区时，优先级是非循环的S, . . . , Sk1≤ |Si| ≤ 2.为了所有人a ∈ Si和b ∈ Si+1.∪ · · · ∪ Sk, 每个位置x 有a xb.证据如果存在这样一个分区，并且存在一个位置x 具有a xb xc, 然后a, c 不能位于分区的同一元素中。