论文标题
下降稳定的匹配晶格：将悲观的人转变为最佳性需要多少个战略代理？
Descending the Stable Matching Lattice: How many Strategic Agents are required to turn Pessimality to Optimality?
论文作者
论文摘要
一组稳定的匹配会引起分布晶格。稳定的匹配晶格的最高效果是男孩最佳的（女孩）稳定的匹配，而最恰当的是女孩最佳（男孩）稳定的匹配。经典的男孩宣传延期接受算法返回了格子的至上，即男孩最佳稳定的匹配。在本文中，我们研究了最小的女孩群体，称为{\ em最低获胜的女孩联盟}，它们可以策略性地行事，但可以独立地迫使男孩宣传延迟受众算法来输出女孩优越稳定的稳定匹配。我们以稳定的匹配轮换为角度表征了最低获胜的联盟，并表明其基数可以在$ 0 $和$ \ left \ left \ lfloor \ frac {n} {n} {2} \ right \ rfloor $之间使用$ n $男孩和$ n $女孩的实例。我们的主要结果是，对于随机匹配模型，最小获胜联盟的预期基数为$（\ frac {1} {2} {2}+o（1））\ log {n} $。这解决了kupfer \ cite {kup18}的猜想。
The set of stable matchings induces a distributive lattice. The supremum of the stable matching lattice is the boy-optimal (girl-pessimal) stable matching and the infimum is the girl-optimal (boy-pessimal) stable matching. The classical boy-proposal deferred-acceptance algorithm returns the supremum of the lattice, that is, the boy-optimal stable matching. In this paper, we study the smallest group of girls, called the {\em minimum winning coalition of girls}, that can act strategically, but independently, to force the boy-proposal deferred-acceptance algorithm to output the girl-optimal stable matching. We characterize the minimum winning coalition in terms of stable matching rotations and show that its cardinality can take on any value between $0$ and $\left\lfloor \frac{n}{2}\right\rfloor$, for instances with $n$ boys and $n$ girls. Our main result is that, for the random matching model, the expected cardinality of the minimum winning coalition is $(\frac{1}{2}+o(1))\log{n}$. This resolves a conjecture of Kupfer \cite{Kup18}.
