有趣的是，我们知道每个代理最多使用3种类型，所有关于不可实现性的具体证明。Clayton Thomas 16我们通常会写申请人的偏好列表，比如pia= 1,2,3，表示申请人a 带类型pia最喜欢位置1，其次是2，然后是3。我们经常抄写申请者提出延期受理的情况，以了解结果，并追踪关于优先事项的哪些事实对申请者来说是重要的。我们这样写，职位是1,2,3，他们的行显示了申请人向他们提出的建议，垂直栏显示了不同“时间步”中出现的不同建议。当我们应用MMA A A.1时，我们构建了申请人偏好的子域，并表明每个所需的ca se（其中一些申请人在机制的根节点处行事）都是满足的。为了清楚起见，我们展示了哪些情况是“获得ba d结果的真相”（计算DA）q(i, -i) 如图A.1）所示，这是一个“得到正确结果的谎言”（计算DA）q(′i, ′-i)).B.1列举三个申请人和职位我们首先列举三个职位{1,2,3}的所有可能优先顺序，超过三个申请人{a, b, c}, 直到重新贴标签。在B.2节中，我们将[AG 18]尚未处理的所有病例归类为eitherOSP或非OSP。首先，确定第一位的优先顺序为：a  b  c 并考虑其他两个位置。第二个位置也有优先顺序的情况有6例a  b  c （第1项和第2项各包含3个不同的案例）。有10个=在优先级集合中，所有位置的优先级列表都是不同的，但实际上只有四种情况需要重新标记（项目3到6，每个项目都包含一种情况需要重新标记）。（1） 非循环病例。

这些是OSP，如[AG18，第3节]所示（这是定理3.2的特例）。这些是：a b c2 a b ca b canda b c2 a b cb a canda b c2 a b ca c b。（2）位置1和2具有相同优先级的循环情况。通过修改[AG18，附录B]中的证明，我们在第B.2.1节中显示了这些不是OSP。这些是：a b c2 a b c3 c a波段1 a b c2 a b c3 c a和1 a b c2 a b c3 b c a。（3）“全循环”情况。在[AG18，第4节]中，这不是OSP。这是：abcbca3cab。（4）循环但OSP的情况。这些都相当于重新贴标签。在[AG18，第3节]中构造了一个用于这种情况的OSP机制（这是定理3.2的特例）。这些是：a b c2 b a ca c banda b c2 b a cb c aanda b c2 a c bc a b.（5）两个职位具有相同的最高优先级申请人（但优先级列表不同）的情况。这些都相当于重新贴标签。我们证明这些不是OSP第B.2.2条。这些是：a b c2 a c b3 c b a和1 a b c2 a c b3 b c a和1 a b c2 c b a3 c a b。克莱顿·托马斯171 a b c2 a b c3 a b c1 a b c2 a b c3 b c1 a b c2 a b c3 a c b（a）OSP通过非循环性1 a b c2 a c b3 b a c（b）OSP但循环案例图。7.三个职位和三名申请人的外包服务提供商案例。1 a b cb c a3 c a b（a）非外包服务提供商b y[AG18，第4节]a b c2 a b c3 c a b1 a b c2 a b c3 c b a1 a b c2 a b c3 b c a（b）非外包服务提供商由[AG18，附录b]和b.2.11 a b ca c b3 c b a（c）非外包服务提供商由b.2.21 a b cb a c3 c b（d）非外包服务提供商由b.2.3节图。8.三个职位和三名申请人的外包服务提供商案例。（6） 所有职位都有不同的最高优先申请者的情况（除了“FullyCycle”情况）。这些都相当于重新贴标签。我们在下面证明，这不是第B.2.3条。这些是：a b cb a c3 c a banda b cb a c3 c b aanda b cc b a3 b c a。检查上述病例后，立即出现以下引理。

在B.3节中，我们使用该命题的条件来确定四名申请人和职位的哪些情况不包含非OSP的限制。引理B.1。如果有一组3个职位优先于3个申请者的优先级，其中每个申请者在某个职位上都有最高优先级，那么优先级如图8所示（因此不是OSP）。引理B.2。如果有一组优先级为3个职位而不是3个申请人，并且是循环的，并且其中两个优先级列表是相同的，那么优先级如图8所示（因此不是OSP）。引理B.3。如果有一组优先级为3个职位而不是3个申请人，其中两个职位的优先级列表正好相反，那么优先级集如图8所示（因此不是OSP）。引理B.4。如果3个职位的3个职位的一组优先级高于图8中的3个申请人（即，如果优先级为OSP），则存在一对申请人a, c 以至于a 她的先天性比c 每个位置。B.2在本小节中，我们证明图8的子图（B）至（d）为非OSP。这就完成了三个申请人和三个职位的OSP优先级别。克莱顿·托马斯18B。2.1两个优先级相同的情况。[AG18]的附录B显示了B c2 a B c3 c a裸无n-OSP的优先级。我们再次证明了这一点，并指出，给定的pro（申请人的偏好相同）不需要任何关于职位3优先于申请人的信息b.索赔B.5。任何优先事项，如1：a  b  c2 : a  b  c三：c  a我们不是OSP。证据

我们将MMA A A.1应用于申请人可能具有以下偏好的子域：pa= 3, 1, 2 pb= 1, 2, 3 pc= 1, 2, 3pa= 3, 2, 1 pb= 2, 1, 3 pc= 1, 3, 2pc= 2, 3, 1o a 在根节点上执行操作。“真相带来坏结果”：pa, pb, pc:b c2 a3 a c.随时可用b c 和c a.“撒谎得到好结果”：pa, pb, pc:cb3 a.无论优先级如何，这都有效b 在根节点上执行操作。“真相带来坏结果”：pa, pb, pc:b c a2 b3 a c.随时可用b c, c a, a b.“撒谎得到好结果”：pa, pb, pc:bb c a3 a c.随时可用b c, c a, a b.o c 在根节点上执行操作。有三个子案例，取决于选择哪一个c 是“单挑的”——pc单挑出来。“真相带来坏结果”：pa, pb, pc这需要b c.“撒谎得到好结果”：pa, pb, pc:c2 b3 a.不管怎样，这都有效。克莱顿·托马斯19-pc单挑出来。这与之前的情况基本相同，我们只需要b c 为了让这个案子起作用pc单挑出来。“真相带来坏结果”：pa, pb, pcab c3 AC.这需要b c.“撒谎得到好结果”：pa, pb, pc:1 b c2 c3 a.这需要b c.请注意，在上述案例分析中，我们没有要求任何关于3的偏好b （事实上，在这场辩论中，DA，b 从不求婚。B.2.2两个优先事项的最高申请人相同的情况。考虑B.2.1节中的论点，它详细地说明了立场的优先性是论证所必需的事实。注意2的优先级高于b 和c 不要对论点影响太大——只有“撒谎”的情况b“从根本上行动”和“真相”案例pc“单挑”要求b c. 我们想利用这一观察结果进一步证明，优先级a b c2 a c b3 c b a是不可实现的OSP。事实证明，我们需要一个额外的偏好b （即pb).索赔B.6。

优先事项1：a  b  c2 : a  c  b三：c  b  a我们不是OSP。我们将MMA A A.1应用于申请人可能具有以下偏好的子域：pa= 3, 1, 2 pb= 1, 2, 3 pc= 1, 2, 3pa= 3, 2, 1 pb= 2, 1, 3 pc= 1, 3, 2pb= 2, 3, 1 pc= 2、3、1请注意，第B.2.1节中的所有首选项仍在子域中–我们只是添加了pb. 我们描述了第B.2.1节中的论点必须如何改变a 在根节点上执行操作。这个论点和以前一样有效：a’s的首选项是sam e，而2的优先级列表与此c a se无关。要想让它发挥作用，只需要b c 和c a.o b 在根节点上执行操作。这个论点现在有三个子类别pb单挑出来。这与最初的情况不同b 成为一个t字根，但需要修改（实际上更容易满足）。Clayton Thomas 20“真相得到了一个坏结果”：（和以前一样）pa, pb, pc:1 b c a2 b3 a c.随时可用b c, c a, a b.“撒谎得到好结果”：pa, pb, pc:b2 b c3 a.这需要c b （就像现在的ca se一样）。-pb单挑出来。“真相带来坏结果”：pa, pb, pc:b2 b c3 a.这需要c b.“撒谎得到好结果”：pa, pb, pc:cb3 a.无论优先级如何，这都有效pb单挑出来。“真相带来坏结果”：pa, pb, pc:1 a2 b c3 a b.这要求c b.“撒谎得到一个好结果”：（如前一子类）：pa, pb, pc:cb3 a.无论优先级如何，这都有效c 在根节点上执行操作。其中一个子类别发生了变化pc单挑出来。这个案子仍然像以前一样有效。这需要b c.– pc单挑出来。这个案子仍然像以前一样有效。这需要b c.– pc单挑出来。

由于原始论点依赖于不同的逻辑，因此这种情况下会产生不同的逻辑b c （事实上，我们之所以需要增加这种偏好，是因为有了这种子类别。）pb进行分析）。“真相带来坏结果”：pa, pb, pcb2 b c a3 a b c.这需要c b, b a, a c.“撒谎得到好结果”：（和以前一样）pa, pb, pc:这需要b c.B.2.3所有优先级都有不同的顶级申请人的情况。我们现在考虑的情况有3个职位和三个申请人，名义上是A，B，B，C，C，C，A，B。克莱顿·托马斯21B.7索赔。优先事项1：a  b  c2 : b  a  c三：c  a  b我们不是OSP。证据我们将MMA A A.1应用于申请人可能具有以下偏好的子域：pa= 2, 1, 3 pb= 3, 2, 1 pc= 2, 3, 1pa= 3, 1, 2 pb= 1, 3, 2 pc= 1, 2, 3pa= 3, 2, 1 pc= 1, 3, 2o a 在根节点上执行操作pa单挑出来。“真相带来坏结果”：pa, pb, pc:a2 a c b3 b c.“撒谎获得好结果”：pa, pb, pc:b c2 aa c.——pa单挑出来。“真相带来坏结果”：pa, pb, pc:b c a2 ba c b.“撒谎获得好结果”：pa, pb, pc:b2约-pa单挑出来。这与previo us案基本相同。在“真相带来坏结果”中a GetSkike从3分中脱颖而出，但在“谎言中获得了一个好的结果”b和c中，让a独自一人b 在根节点上执行操作。“真相带来坏结果”：pa, pb, pc:b c a2 ba c b.“撒谎获得好结果”：pa, pb, pc:c2 ab.oc 从根本上说pc单挑出来。“真相带来坏结果”：pa, pb, pc:b2 c a3 c.“撒谎获得好结果”：pa, pb, pc:b c2 c3 a.克莱顿·托马斯22——pc单挑出来。“真相带来坏结果”：pa, pb, pc:b c2 c3 a.“撒谎获得好结果”：pa, pb, pc:ca3 b.——pc单挑出来。这与之前的案例基本相同。

在“真相带来坏结果”中c GetSkike从1中退出，但在“谎言中得到了一个好结果”b 和c 离开a 单独地B.3四位申请人和职位的列举我们现在描述并列举四位申请人和四个职位的所有循环优先权集，其中三位a申请人和三个职位不受限制为非OSP。由于（最多）三个申请人中只有一组循环优先级是OSP，因此我们需要考虑的优先级集合相当小。我们的枚举通过一系列引理进行。引理B.8。考虑一系列优先事项n ≥ 3个职位超过3个申请人。假设优先级是循环的，但没有一组3个位置的优先级高于三个应用程序，这三个应用程序与图8中的任何一个优先级集相等（即，没有对3个位置的限制是非OSP的）。在重新标记之前，每个职位的优先级列表都是x 除了两个u 和v, 我们在哪里xa b cu a c bvb a c即优先事项q 是两个相邻的交替。证据特别是，这样一个优先级集必须包含一个OSP和一组3个位置的循环优先级。根据第B.1节，直到重新标记，唯一的3个申请人和3个职位优先设置是OSPxa b cua c bv b a c.因此，通过重新标记，我们不能假设三个位置的优先级列表是x,u, v. 我们现在考虑其他职位的优先顺序。ByLemma B.1，其他职位不能有c 作为他们的首要任务。因此，除了x, u, v 是w : b  c  a. 但接下来是位置u, v, w 共同形成与第B.2.2节相同的模式，且不是OSP。因此，所有其他职位的优先级列表必须等于x, u, 或v.

如果优先权列表u 或v 重复，比如在位置上y, 恩莱玛B.2意味着u, v, 和y 一起形成一个参考列表，如图8所示。因此，唯一的可能性是重复x.引理B.9。认为q 是一套4个职位优先于4个申请人的优先顺序。补充q 是循环的，yetno限制q 等于（直到重新标记）图8中的任何优先级集。然后，直到重新贴标签，qClayton Thomas 23必须等于以下优先级集之一：d a b cd a b c3 d a c bd b a ca d b cd a b c cd a b c3 a d c bd b c1 a b c d d c d3 a c b d d c d c d c d c c d c c c d c c d c c d c c d c c d c c d c d c d c d c d c d d c d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d c d d d d d d d d d d d d d d d d d d d。假设优先顺序是循环的，而不是申请人a, b, c. BYLEMA B.8，我们可以在不失去普遍性的情况下假设优先权仅限于申请人a, b, c, B区C2 A B C3 A C BB A cTHE，我们只需考虑申请人在哪里d 插入到每个位置的优先级列表中。我们根据申请人的职位将其分为几个案例d 在第四位的名单上。在整个证明过程中，我们大量使用了引理。1至B.4。为了使证明更可读，我们在4的列表中损坏了这个假设（D），当我们考虑一个优先权列表中的位置D时，我们写“D”。4 | (d) b a c.拜莱玛B.3，d 不可能b 在任何优先权列表中i ∈ {1,2,3}（那时我们会有d b a 和a ib id 对一些人来说i ∈ {1, 2, 3}). 因此d 可以在以下位置：d？d？b cd？d？b和d？d？CD？b4（d）b a cByLemma b.2，最多一个位置i ∈ {1,2,3}可以有a id ib （正如我们所做的那样b a).此外，如果i = 1和2都有d ia ic, 那我们就不能c d （B.2适用于d, a, c).

因此，在重新标记1和2之前，这些病例被称为a b cd a b c3 d a c b（d）b a ca d b cd a b c3 d a c b（d）b a cd a b cd a b c c（d）b co4 |b (d) a c.ByLemma B.1或a li ∈ {1,2,3}有d ia, 或者他们都没有。此外，在Emma B.3中，我们从来没有a id ib （作为b d a). 因此，d能承受的地方是什么？a b c2 d？b cd？a c b4 b（d）a cora b d？CD？2 a b d？CD？对于这两种情况，我们都可以使用引理b.2（适用于职位1、2、4和申请人）d, a, b) 查看所有这些案例都包含图8的优先级集。因此，不存在4|的可能案例b (d) a c.克莱顿·托马斯24o4 |b a (d) c.B.3.我们从来没有d ia ib 对于i ∈ {1,2,3}（正如我们所做的那样b a d).此外，我们没有c d b （正如我们所做的那样b d c). 如果我们有d c b, 那么由引理B.3我们就不能b ic id 对于i ∈ {1, 2}. 因此，可能的情况是：a d？b-d？c2和d？b-d？可以吗？c b4 b a（d）ca d？b-d？CD？2 a d？b-d？CD？a c b d？4 b a（d）cLet检查第一个子类别。如果有的话i ∈ {1,2}有a id ib, 然后优先考虑的是不适用于申请人的tOSP（byLemma B.2）a, d, b 和职位i, 3和4）。但如果两者都有i ∈ {1,2}有b id ic, 那么优先选择也不是OSP byLemma B.2（适用于职位1、2、3和申请人）b, d, c). 因此，此子类别中的首选项都不能是OSP。现在让我们来考虑一下第二个例子。根据引理B.3，我们不能d ib ic 对他们来说i ∈ {1,2}（正如我们所做的那样c b d). 此外，我们也不能b id ic 弗雷瑟i ∈ {1,2}byLemma B.2（适用于职位）i, 3、4和申请人b, d, c). 因此，剩下的唯一可能的情况是isa b c d2 a b c da c b d4 b a（d）co4 |b a c (d).B.3.我们从来没有d ia ib 无论如何i ∈ {1,2,3}（正如我们所做的那样b a d), 而且我们不能d c b （正如我们所做的那样b c d).

因此，可能的位置d d区？b-d？CD？d？b-d？CD？3 a c d？b-d？b a c（d）署名Emma b.3，如果我们有c d b, 那我们就不能b id ic 为了你们俩i ∈ {1,2}，如果c b d, 那我们就不能d ib ic 为了你们俩i ∈ {1, 2}. 因此，可以是OSP的情况是：a d？b c d？2 a d？b c d？3 a c d bb a c（d）a b d？CD？2 a b d？CD？3 a c b db a c（d）考虑上述第一个子类。ByLemma B.2（适用于职位1、2、3和申请人b, d, c) , 在上面的第一个子类中，我们不能d ib ic 两者皆有i ∈ {1, 2}. 但如果b ic id 对一些人来说i ∈ {1，2}，那么首选项不是OSP，同样是由Emma B.2（应用于位置i, 3、4和申请人b, c, d) . 因此，在这个子类别中，没有一个优先级是OSP。现在考虑上面的第二个例子。同样是引理B.2（适用于职位1、2、3和申请人b,d, c), 在第二个子类中，我们不能拥有b id ic 两者皆有i ∈ {1, 2}.因此，在重新标记位置1、2之前，可能的OSP病例区域b d c2 a b c d3 a c b d4 b a c（d）1 a b c d2 a b c d3 a c d4 b a c（d）Clayton Thomas 25在上述l emma中的六个优先级集中，有四个是有限循环的（因此OSP）。另外两个，名字是1 a d b cd a b c 3 d a c b b a c c d b a cq =b c da b d c3 a c b db a c dare等同于重新标记（要了解这一点，请在第一种情况下重新标记申请人a s如下：a →b, b → c, c → d, d → a). 我们证明了这个优先级集不是OSP第B.4节中的优先级集。回想一下，图1正好由图8中的优先级集以及q 如上所述。推论B.10。4个职位相对于4个申请人的唯一一组优先权是循环的，但不包含图1中的任何优先权列表，等于以下之一（直到重新标记）：d a b c2 d a b cd a c b4 d b a c d2 a b c d b d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d。

由Lemm a B.9和q （如上所述）如图1所示，只有4种可能的情况。给出了其中三个，以及最终的isd a b cd a b c3 a d c bd b c，其相当于重新标记到推论声明中设置的中间优先级。B.4有四名申请人和四个职位的案例我们现在提供了一个需要的直接证据，证明有四名申请人和四个职位的一组优先事项不是OSP。这将完成所有优先级集显示在图1 arenon OSP中的证明。索赔B.11。优先事项1：a  b  c  d2 : a  b  d  c三：a  c  b  d4 : b  a  c  d我们不是OSP。证据我们将MMA A A.1应用于申请人可能具有以下偏好的子域：pa= 4, 2 pb= 3, 1 pc= 2, 3 pd= 1, 2pa= 4、3pb= 3, 4 pc= 3, 1 pd= 2、1为了简单起见，我们在这里不指定完整的偏好列表，只有那些与论点相关的立场（以任何方式填充剩余的立场都会使argum Ent保持不变）a 在根节点上执行操作。Clayton Thomas 26“真相带来坏结果”：pa, pb, pc, pd:1 d2 a3 b c4 a b.“撒谎获得好结果”：pa, pb, pc, pd:d2 cb4 a.ob 在根节点上执行操作。“真相带来坏结果”：pa, pb, pc, pd:bd3 b c4 a.“撒谎获得好结果”：pa, pb, pc, pd:dd c3 b4 a.oc 在根节点上执行操作。“真相带来坏结果”：pa, pb, pc, pd:cd3 b c a4 a b.“撒谎获得好结果”：pa, pb, pc, pd:bd c3 b c4 a.od 在根节点上执行操作。“真相带来坏结果”：pa, pb, pc, pd:d b2 db c4 a.“撒谎获得好结果”：pa, pb, pc, pd:d2 d a3 b c4 a b。B.5主要结果的证明我们现在准备好完成我们的证明。回想一下，图1包含的正是图8中的偏好集，以及第B.4节中的偏好集。

直观地说，证明从引理B.8开始，然后利用B.4节中的优先级集是向循环和OSP优先级列表中再添加一个应用程序的唯一非平凡方式这一事实。新申请者必须以特定的方式进行排名，以确保B.4部分的优先权列表也是增加更多申请者的唯一方式。formalproof的关键在于显示这两个位置u 和v 其中，优先权清单“偏离规范”必须与添加的每个申请人保持一致。定理（4.2）。考虑任何优先级设置q. 如果没有限制q 等于图1中的任何优先级设置q 是有限的循环。克莱顿·托马斯：证据。允许q 满足定理的逻辑。固定任何位置i*并构造一个有序分区S, S, . . . , SL申请人名单如下：按优先顺序排列i*并反复将所有申请者分组a, b 具有a i*b 这样就存在一个位置j 哪里b ja. 就是{S, . . . , SL} 申请者的最可能分区是否为：a ∈ Sk, b ∈ Sl具有k < l, 我们有a i*b, 2）如果a i*b 和b ja 或者一些j ≠ i*, 然后a, b 都在同一组Si. 任何时候都要注意这一点a ∈ Sk, b ∈ Sl具有k < l, 我们有a jb 所有职位j （这是因为a i*b 顺便说一下，我们构造了分区，如果b ja 换个职位j, 然后a, b 应该在同一组Si). 因此，为了证明我们的定理，我们只需要证明Si与|Si| ≥ 3.优先事项限于：Si是定义3.1中的两个相邻备选方案。为了证明这一点，请i 让我|Si| = K ≥ 3.我们使用归纳法K. 允许q′是q, 每个优先权名单只限于Si. 根据提案2.8，q′是循环的。因此，如果K = 定理B.8证明了基本情况。否则，让我们|Si| = K ≥ 4.

通过归纳法假设S′i与|S′i| ≤ K -1.优先事项仅限于：S′i是两个相邻的交替。允许q′是q, 每个优先列表仅限于Si. B.1.最多可以有两名申请人a, a这样一些职位就会a, a优先考虑q′. 此外，肯定存在一些问题a以至于q′仅限申请者{a, a, a} 是循环的（根据命题2.8，如果不是这样，Si会相等吗{a, a} ). 根据引理B.8，每个优先级列表q′, 当仅限于{a, a, a}, 一定是平等的x,u, v, 哪里u和v每一个都出现在同一个位置u 和v, （分别）和我们xaaauaaavaaa作为|Si| ≥ 4.必须有其他申请人a以至于a出现在你的面前a, a, 或a关于某个职位的优先权。允许y 任何排名的职位a超过至少一个a, a,或a. 考虑任何限制q′′属于q′到任何四个位置，包括y, u, v. 这形成了一个由四个申请人的四个职位组成的周期性OSP优先级集，ThusCollary B.10适用。推论B.10中的o nl ycased 有时（但并非总是）排名高于a, b, c 这是中间的情况。也就是说，如果我们让xaaaauaaaavaaaa,然后q′′限于{a, a, a, a} 必须包含x重复两次，每一次u, v就一次。特别是，我们必须y = v, 和u 必须有优先权u在里面q′′和v 一定有v. 这个论点适用于我们考虑任何位置。i, i′连同u, v, 因此我们可以看到，除了u 和v 必须有优先权清单x当仅限于{a, a, a, a}.这一论点也适用于任何申请人a谁的排名高于任何一位a, a, 或a, 因此，请特别注意a在申请的每个职位上都有更高的优先权q′除了a（位置）v).现在，考虑移除a从每个职位的优先级列表中。

剩下的仍然是一组至少有三名申请人的循环优先名单。因为a只排在下面a, 没有其他申请者，申请者在Si\\ {a} 无法进一步分区，并且仍然满足分区上的假设(Si)i. 因此，在归纳法中，优先顺序是两个相邻的交替顺序，仅限于Si\\ {a}. 我们已经知道，仅限于{a, a, a}, 优先事项q′通常，归纳假设是q′有优先权吗K 申请人不受以下限制：q′等同于图1中的任何优先级集，以及2）构建在其上的分区q′正如本理论的第一段所述，它只包含一个集合q′是两个相邻的交替。克莱顿·托马斯28号xaaauaaavaaa,哪里u优先顺序是什么u 和v优先顺序是什么v （所有其他职位都有优先权名单。）x). 因此，当限制为Si\\{a}如果我们有xaaaaaa.. .uaaaaaa.. .vaaaaa.. ..此外，情况必须如此：u h.a.优先权u, v 有优先权v, 所有其他人都有优先权x. 因此a此外，优先权清单的格式必须为xaaaaaaa.. .uaaaaaaa.. .vaaaaaa.. ..就是，q′是两个相邻的交替。通过归纳，这证明了q′是两个相邻的交替，因此q 是有限的循环。C扩展到不平衡匹配市场在本附录中，我们简要讨论了将我们的分类扩展到具有不同数量申请人和职位的匹配环境的可能性，即“不平衡”环境。我们考虑了“外部选择”的环境，即申请人可能会将职位标记为不可接受（并选择不匹配，而不是与不可接受的职位匹配）。在这种环境下，非限制性循环优先级可能是OSP。

具体而言，考虑以下优先事项，图9描述了OSP机制：q =a b（dc）2 a（cb）d（ba）c有趣的是，在这种OSP机制中，一次可以有四个代理处于活动状态（在第一行最右边的节点，其中c （使徒行传）。然而，该机制仍然与每个代理最多交互两次。这个反例只能以非常有限的方式扩展，所有反例都必须有三个位置。要看到这一点，首先要观察Lemma 2.6可以适应有外部选择的不平衡环境（通过让限制之外的申请人提交诱人的首选列表）。每当有四个或更多职位和三个或更多申请人时，引理B.8和/或定理4.2的证明适用，并表明OSP优先级必须是有限的。有可能考虑一个不平衡的环境，但没有外部选择。在这样的环境下，应聘者总是会对每个职位进行排名，以尽量避免不匹配。这样的环境会导致一些病态的匹配规则。例如，考虑两个职位1, 2和三申请人。a, b, c, 优先事项1：a  c  b 和2：b  c  a.在没有外部选项的环境中，存在唯一的稳定匹配{（1，a), (2, b) } 无论三位申请人的偏好如何，我们都会优先考虑这些问题。从更技术的角度来看，如果没有外部选择，Criculalemma 2.6在不平衡的环境中无法运行。此外，我们的观点是，如果机制设计师想要让某些代理不匹配，他们应该模拟代理实际不匹配的可能性。克莱顿·托马斯29（a）C（1）C（2）C（)（b） C（1）C（3）C（)（d） {1}是可能的（i）C（)（c） {2}是可能的（)（ii）2。3.2.1.（ii）：（b）{1，3}是可能的)（a） C（1）C（2）C（)C（3）图9。

一组OSP优先级，不受循环限制（在不平衡的匹配环境中）。在方形子节点中，剩余的优先级是非循环的；在三角形子节点中，剩余的优先级是有限的；在圆形子节点中，匹配是完全确定的。在节点(i), 申请人d 退出，机制以与图4中的平衡情况相同的方式进行。该机制属于节点(ii) 在图的下半部分继续。