Gibbard的定理与稳定匹配

以下是博弈论的两个定理，最初似乎彼此矛盾。通过比较它们，我们可以在情况下发现一些隐藏的细微差别。

最初由Allan Gibbard和Gibbard和其他人概括的第一个定理表明，任何集体决策过程必须有三个属性之一：

有一个独裁者，无论任何其他人所做的任何选择如何，都可以选择结果。

它是战略性的，这意味着获得你想要的最佳方式，而不仅仅取决于您的首选结果，而且还要预期别人会做什么。

这是一个非常大的交易。例如，考虑Electio NS。假设我们有两个以上的候选人，并且没有独裁统治，必须可以进行战略投票。这太糟糕了，因为我们希望能够告诉人们，他们总是可以投票给他们最喜欢的候选人。唉，这绝不会有这种情况。众所周知，无望的第三方可以通过从主要候选人的虹吸票“破坏”选举。像即时径流这样的聪明系统应该解决这个问题，但Gibbard一般来说，它永远无法完全修复。 （至少没有接受有限的双方制度或独裁统治。）

它并不是吉巴德定理的一部分，但吉巴德和其他人稍后表现出来，即使涉及随机性，这仍然存在。您可以等到投票发生后选择独裁者，或者决定允许哪两个结果;但最终适用相同的条件。但是，这对本文的其余部分并不重要。

虽然Gibbard的定理解决了任何集体决策过程，但大风和福利的延期验收（DA）算法是一个具体决策问题的解决方案：匹配。这个想法是将一些候选人与一些职位匹配。每个候选人都有偏好于他们想要的位置，每个位置都有偏好，他们更喜欢哪种候选者。 （演示文稿是在婚姻方面举起的，但在考虑同性婚姻，性别认同等时呈现困难，所以让我们称之为候选人和职位！）

大风和福利证明，候选人对稳定的阵地存在匹配，无论没有候选人都更喜欢也更喜欢它们的位置。 （“稳定”这个词可能来自这样一个候选者然后可以切换到他们的首选位置，因此不稳定的匹配不会持续很长时间。）它们给出了一种称为DA或延迟接受的特定算法以前的链接。它从每个候选和位置的偏好列表开始，并生成稳定的匹配。他们继续证明它产生的匹配是所有候选人都同意的独特之一。

您可能想象一个非常聪明的人可以通过这种匹配算法对他们的偏好不诚实地找到更好的位置。例如，如果有人想要一个职位但不认为他们会被接受，那么表明更加现实的偏好会是明智的吗？令人惊讶的是，Alvin Roth表明这是不可能的！ DA算法是策略的证明，从而获得最佳职位的最佳方式是为您提供诚实的真实偏好列表。

所以现在我们有困境。稳定的匹配肯定有两个以上的结果。它绝对没有独裁者。所以它必须由Gibbard的定理，成为战略性。但坚持...罗斯表明，无论他人的偏好如何，诚实的偏好清单总是最好的。既是怎么样的？答案是微妙的，它将表明我们需要小心在每种情况下都意味着什么。

Gibbard的定理假设每个参与者都有一系列关于该过程的整个结果的偏好。在这种情况下，该过程的结果是所有候选人对所有位置的匹配。

另一方面，罗斯认为每个候选人都有一组关于它们单独分配的位置的一组偏好。它们无权享受关于哪些候选候选人的偏好。

Roth的偏好是限于它们只能间接产生冲突，例如当有更多候选人的候选人，这些候选人的候选人比在那里接受它们的插槽时。事实证明，产生足够的松弛，以逃避Gibbard的定理的后果，并允许决策过程在罗斯的意义上是非战略性的。

但小心点！这意味着如果候选人确实有依赖于其他人的放置的偏好，则罗斯的结果不再适用。要采取一个简单的例子，假设两个亲密的朋友想要在同一位置一起工作。尽管罗斯解雇了战略，但他们需要战略制定这一点。例如，他们将得到充分建议，以申请可能一般不受欢迎的位置。他们还应该避免申请不想要的职位也想要他们的朋友。这两个都是战略选择，涉及预期他人的偏好。

最后，当然，吉巴德和罗斯的结果可以共同存在，但是一定必须小心他们的意思。 我想清楚，这不是新的。 事实上，罗斯引用了Gibbard在匹配问题上的论文中的结果，显然意识到了这种细微差别。 对于此分析，我只考虑候选人作为决策过程中的参与者，以及雇主偏好作为被烘焙到决策算法中。 罗斯的结果并没有向雇主延伸到表达其真实偏好的人！ 事实上，罗斯表明，没有任何过程也可以促进雇主，以表明他们在候选人之间的真实偏好。