Stable Matching问题及GSA算法略解
zombie462
·
·
个人记录
1.什么是 \texttt{Stable Matching} 问题
考虑一个这样的问题：
\texttt{Description}
在大学校园内有 n 个男生和 n 个女生。每个男生心目中有他对每个女生喜欢程度的一个排列，每个女生心目中也有她对每个男生喜欢程度的一个排列。某一天，这些学生想要集体脱单，请你找到一个匹配方案，使得这个脱单计划是稳定的。
如果存在一个男生 i，他被匹配到的对象是女生 x，又存在一个女生 y，她被匹配到的对象是男生 j，然而在 i 心目中，他比起 x 更喜欢 y，在 y 心目中，她比起 j 更喜欢 i，那么这个匹配方案就是不稳定的，因为男生 i 和女生 y 可能会私奔。
相反，没有出现不稳定情况的匹配方案是稳定的。
\texttt{Input Format}
第 1 行一个数 n。
第 2 行至第 n+1 行，每行 n 个数，第 i+1 行表示第 i 个男生心目中对女生的喜爱程度排列。
第 n+2 行至第 2n+1 行，每行 n 个数，第 n+i+1 行表示第 i 个女生心目中对男生的喜爱程度排列。
\texttt{Output Format}
共 n 行，表示一个稳定匹配的方案。第 i 行表示第 i 个女生匹配到的男生序号。方案可能有多种，你只需要给出一种方案即可。
\texttt{Sample Input}
4
1 2 3 4
3 1 2 4
2 1 3 4
2 3 1 4
2 1 4 3
1 3 2 4
4 1 2 3
3 4 1 2
\texttt{Sample Output}
2
1
4
3
\texttt{Hint}
对于 100\% 的数据，n\leq 1000。
测评地址：【模板】Stable Matching 稳定匹配问题
这个问题就叫做 \texttt{Stable Matching} 问题，也称作男女稳定匹配问题。
2.\texttt{GSA} 算法
那么，如何求解这个问题呢？
先来回顾一下题意：
我们假设 n=4，有 4 位男生 a,b,c,d，4 位女生 A,B,C,D。假定他（她）们心目中最理想配偶的排列是：
a\to A,B,C,D
b\to C,A,B,D
c\to B,A,C,D
d\to B,C,A,D
A\to b,a,d,c
B\to a,c,b,d
C\to d,a,b,c
D\to c,d,a,b
其中一个合法的配对方案：
a\to B,b\to A,c\to D,d\to C
在这种方案下，不存在不稳定的情况。
其中一个不合法的配对方案：
a\to A,b\to B,c\to C,d\to D
在这种方案下，b 更喜欢 C 而不是 B，C 更喜欢 b 而不是 c，所以这个配对方案是不稳定的。
为了解决这个问题，\texttt{Gale} 和 \texttt{Shapley} 想出了一种算法，也就是所谓的 \texttt{Gale-Shapley Algorithm(GSA)}。
他们首先证明了无论对于哪种情况，一定存在稳定匹配。
然后，他们想出了这样一种做法：
$2$. 对于每个女生，她会挑选向她表白的男生中最合她心意的一位，不过，傲娇的她并不会直接同意，而是暂时保留意见。然而，其他的那些向她表白的男生将会被她直接拒绝。
$3$. 对于每个男生，如果他受到了某位女生的拒绝，他会毅然放弃这位女生，从心中将她删去。
$4$. 第二天，每个昨天被拒绝的男生再去向自己最喜欢的女生表白，但不包括他已经放弃的那些女生。
$5.$ 对于每个女生，她会再次挑选向她表白的男生（包括她昨天没有拒绝的那位）中最合她心意的一位，她仍旧不会直接同意。然而，其他的那些向她表白的男生还是会被她直接拒绝。
$6.$ 返回第 $3$ 步，循环直到每个女生都有一个她没有拒绝的配偶为止，此时便达成了**稳定匹配**。
时间复杂度 $O(n^2)$。
还是拿刚才的例子：
第一天，$a$ 向 $A$ 表白，$b$ 向 $C$ 表白，$c,d$ 向 $B$ 表白。
$A$ 不会拒绝 $a$，$C$ 不会拒绝 $b$，$B$ 拒绝了 $d$ 因为她更喜欢 $c$，而她不会拒绝 $c$。
$d$ 被拒绝后，不再打 $B$ 的主意。$d$ 心目中的名单：$C,A,D$。
第二天，$d$ 向 $C$ 表白，$C$ 拒绝了 $b$ 因为她更喜欢 $d$，而她不会拒绝 $d$。
$b$ 被拒绝后，不再打 $C$ 的主意。$b$ 心目中的名单：$A,B,D$。
第三天，$b$ 向 $A$ 表白，$A$ 拒绝了 $a$ 因为她更喜欢 $b$，而她不会拒绝 $b$。
$a$ 被拒绝后，不再打 $A$ 的主意。$a$ 心目中的名单：$B,C,D$。
第四天，$a$ 向 $B$ 表白，$B$ 拒绝了 $c$ 因为她更喜欢 $a$，而她不会拒绝 $a$。
$c$ 被拒绝后，不再打 $B$ 的主意。$c$ 心目中的名单：$A,C,D$。
第五天，$c$ 向 $A$ 表白，$A$ 拒绝了 $c$ 因为她还是更喜欢之前的 $b$。
$c$ 被拒绝后，不再打 $A$ 的主意。$c$ 心目中的名单：$C,D$。
第六天，$c$ 向 $C$ 表白，$C$ 拒绝了 $c$ 因为她还是更喜欢之前的 $d$。
$c$ 被拒绝后，不再打 $C$ 的主意。$c$ 心目中的名单：$D$。
第七天，$c$ 向 $D$ 表白，$D$ 不会拒绝 $c$。
至此，每个女生都有了一个她不曾拒绝的男生。这些女生同时答应了对应的男生的表白。
最终的匹配：$a\to B,b\to A,c\to D,d\to C
这是一个稳定匹配。
3.\texttt{GSA} 算法证明
对这个算法的证明可以划分为 3 个子问题：
$B$. 算法不会进入死循环。
$C$. 算法不会出现无法匹配的情况。
对于子问题 $A$ 的证明：
假使男生 $i$ 被匹配到的对象是女生 $x$，那么对于任何一个在男生心目中排名在女生 $x$ 之前的女生 $y$，女生 $y$ 早已拒绝过男生 $i$，因为男生 $i$ 是在追求不到女生 $y$ 的情况下才退而求其次去追求女生 $x$ 的。显然，既然女生 $y$ 已经拒绝过男生 $i$，那么女生 $y$ 必然有一个比男生 $i$ 更好的选择男生 $j$，不然女生 $y$ 不可能拒绝男生 $i$。所以匹配方案不存在不稳定情况，根据稳定匹配的定义，这个匹配是**稳定匹配**。
对于子问题 $B$ 的证明：
算法结束等价于某一次迭代中没有女生拒绝男生的表白。表白最多只会进行 $n^2$ 次（因为一个男生对一个女生最多只会进行 $1$ 次表白）所以拒绝最多也只会进行 $n^2$ 次，也就是说，算法最多进行 $n^2$ 次迭代（事实上，绝大多数情况下算法只会最多进行 $2n$ 次迭代）。所以算法不会进入死循环。
对于子问题 $C$ 的证明：
如果存在一个还没有被匹配上的男生，那么必定存在一个还没有匹配上的女生，显然这个女生必定没有拒绝过这个男生，否则她一定早已匹配上另一个男生了。所以，对于任何男生而言，他一定不会找不到女生和他匹配。
既然证明了这三个子问题，我们可以认定，算法是正确的并且无论对于什么情况，都至少存在一个**稳定匹配**。
## 4.$\texttt{GSA}$ 算法实现
既然知道了方法，那么实现起来也是相当容易的。
$\texttt{GSA}$ 算法代码：
```cpp
#include <bits/stdc++.h>
using namespace std;
#define INF 2147483647
inline int read(){
int x=0,f=1;
char c=getchar();
while (c<'0' || c>'9'){
if (c=='-') f=-1;
c=getchar();
}
while (c>='0' && c<='9'){
x=x*10+c-48;
c=getchar();
}
return x*f;
}
#define N 5555
queue <int> boy[N];
//boy[i]队列表示第i个男生的表白顺序队列
int girl[N][N];
//girl[i][j]表示第i个女生对第j个男生的喜欢程度，越小代表越喜欢（即排列越靠前）
queue <int> active,wait;
//active队列表示等待着向女生表白的男生队列
//wait队列作为辅助，表示下一天等待着向女生表白的男生队列
int love[N];
//love[i]表示当前第i个女生匹配到的男生序号。若为INF，则还未匹配
int main(){
int n=read();
for (int i=1;i<=n;++i){
for (int j=1;j<=n;++j){
boy[i].push(read());
}
active.push(i);
}
for (int i=1;i<=n;++i){
for (int j=1;j<=n;++j){
girl[i][read()]=j;
}
love[i]=INF;
}
int ok=0;
while (true){
while (!active.empty()){
int now=active.front();
active.pop();
int to=boy[now].front();
boy[now].pop();//一个男生只会对一个女生表白一次，表白后直接pop就行
if (love[to]==INF){//如果此女生还未匹配的话
ok++;//已经匹配的女生+1，显然的女生不会失配
love[to]=now;
if (ok==n){//全部匹配完就直接输出方案
for (int i=1;i<=n;++i){
printf("Girl %d -> Boy %d\n",i,love[i]);
}
return 0;
}
}else{
if (girl[to][love[to]]>girl[to][now]){//如果这个女生更喜欢现在向她表白的男生，那么把旧的男生剔除
wait.push(love[to]);//原来的男生又要去重新表白
love[to]=now;
}else{
wait.push(now);//否则现在的男生表白失败
}
}
}
while (!wait.empty()){//将wait队列里的内容转移到active中去
active.push(wait.front());
wait.pop();
}
}
return 0;
}
```
附加代码：判断一个方案是否是**稳定匹配**：
```cpp
#include <bits/stdc++.h>
using namespace std;
inline int read(){
int x=0,f=1;
char c=getchar();
while (c<'0' || c>'9'){
c=getchar();
}
while (c>='0' && c<='9'){
x=x*10+c-48;
c=getchar();
}
return x*f;
}
#define N 5555
int boy[N][N],boy2[N][N],girl[N][N];
int boynow[N],girlnow[N];
int main(){
int n=read();
for (int i=1;i<=n;++i){
for (int j=1;j<=n;++j){
int x=read();
boy[i][x]=j;
boy2[i][j]=x;
}
}
for (int i=1;i<=n;++i){
for (int j=1;j<=n;++j){
int x=read();
girl[i][x]=j;
}
}
for (int i=1;i<=n;++i){
int x=read(),y=read();
boynow[y]=x;
girlnow[x]=y;
}
for (int i=1;i<=n;++i){
for (int j=1;j<boy[i][boynow[i]];++j){
int to=boy2[i][j];
if (girl[to][i]<girl[to][girlnow[to]]){
printf("Not a Stable Matching: Boy %d prefers Girl %d rather than Girl %d; Girl %d prefers Boy %d rather than Boy %d!\n",i,to,boynow[i],to,i,girlnow[to]);
return 0;
}
}
}
printf("A Stable Matching!\n");
return 0;
}
```
## 5.$\texttt{GSA}$ 算法拓展
那么，接下来就是 $\texttt{GSA}$ 算法的一个最经典的问题了：
由于 $\texttt{GSA}$ 算法的流程很接近日常生活，所以人们不禁要问，在这种算法下，究竟是男生占到了便宜还是女生占到了便宜呢？
一眼看过去，男生只会匹配到越来越差的配偶，女生只会匹配到越来越好的配偶，并且决定权在女生手上，看起来女生似乎占到了便宜。然而真的是这样吗？
答案是否定的。在所有稳定匹配中，用 $\texttt{GSA}$ 算法得到的一组稳定匹配里，男生得到了最好的配偶，女生得到了最差的配偶。
也就是说，任何一个男生都不可能得到一个比 $\texttt{GSA}$ 算法跑出来的匹配更好的女生，否则匹配就是**不稳定**的。
相反，任何一个女生都不可能得到一个比 $\texttt{GSA}$ 算法跑出来的匹配更差的男生，否则匹配就是**不稳定**的。
为什么呢？
我们继续来证明。假使在 $\texttt{GSA}$ 算法中，$i$ 号男生匹配到了他第 $j$ 喜欢的女生 $x$，是否存在另一个稳定匹配的方案，使得男生 $i$ 被匹配到一个比 $x$ 更好的女生 $y$ 呢？显然，男生 $i$ 在向女生 $x$ 表白前，他早就向他前 $j-1$ 喜欢的女生表白过了，其中包括女生 $y$。这些女生一定已经拒绝了他。为什么这些女生会拒绝他呢？还是拿女生 $y$ 举例，女生 $y$ 拒绝男生 $i$ 的理由是，存在一个男生 $p$，使得女生 $y$ 更喜欢男生 $p$ 而不是男生 $i$。如果女生 $y$ 拒绝了男生 $p$ 而接受了男生 $i$，那么男生 $p$ 会去匹配下一个女生 $z$，显然这位男生更喜欢女生 $y$ 而不是女生 $z$，不然他也不会先向女生 $y$ 表白。这时就有不稳定的情况了：男生 $p$ 更喜欢女生 $y$ 而不是女生 $z$，女生 $y$ 更喜欢男生 $p$ 而不是男生 $i$。这个匹配并不是稳定匹配，男生 $i$ 不能再得到比女生 $x$ 更好的配偶了。所以，男生能够得到的配偶是所有合法方案中他可以得到的最好情况。
相反，假使在 $\texttt{GSA}$ 算法中，$x$ 号女生匹配到了他第 $j$ 喜欢的男生 $i$，是否存在另一个稳定匹配的方案，使得女生 $x$ 被匹配到一个比 $i$ 更差的男生 $k$ 呢？如果女生 $x$ 接受了男生 $k$ 的表白，那么很显然，她拒绝了 $i$ 的表白。此时男生 $i$ 将会去匹配下一个女生 $y$，显然，男生 $i$ 更喜欢女生 $x$ 而不是女生 $y$。这时就有不稳定的情况了：男生 $i$ 更喜欢女生 $x$ 而不是女生 $y$，女生 $x$ 更喜欢男生 $i$ 而不是男生 $k$。这个匹配并不是稳定匹配，女生 $x$ 不能再得到比男生 $i$ 更差的配偶了。所以，女生能够得到的配偶是所有合法方案中她可以得到的最坏情况。
那么，如果主动表白的是女生，情况会不会发生转变呢？没错，女生将得到最好配偶，男生将得到最坏的配偶。也就是说，主动表白的人可以占到便宜。
除了主动表白之外，女生还可以通过撒谎的方式得到更好的配偶，不过这个内容已经是题外话了，所以只举一个简单的例子来说明这一点。比如，男生 $1$ 更喜欢女生 $2$，次喜欢女生 $1$。男生 $2$ 恰好相反。女生 $1$ 更喜欢男生 $1$，次喜欢男生 $2$。女生 $2$ 恰好相反。按照标准的 $\texttt{GSA}$ 算法流程，男生 $1$ 将匹配上女生 $2$，男生 $2$ 将匹配上女生 $1$。然而，对于女生而言，这是她们的最坏选择。如果女生 $1$ 和女生 $2$ 在第一回合表白时都拒绝了对方，那么男生 $1$ 将去向女生 $1$ 表白，男生 $2$ 将去向女生 $2$ 表白。此时女生们都得到了最好的选择。
在这种情况下，如果仅有一个女生撒谎，那么情况也将发生改变——比如女生 $1$ 没有拒绝男生 $2$，而女生 $2$ 拒绝了男生 $1$，此时男生 $1$ 会去向女生 $1$ 表白，女生 $1$ 将拒绝男生 $2$，受挫的男生 $2$ 去向女生 $2$ 表白。此时女生们仍旧可以得到最好的选择。
那么男生如果撒谎了会怎样呢？男生们将得到更差的配偶。这一点可以比较容易证明，这里不加赘述。
## 6.后记
$\texttt{Stable Matching}$ 问题除了在选配偶的时候出现，同时也会在高校选学生，公司选员工的时候出现。这些问题的共同之处是，都有决定方（女生、高校、公司）和主动方（男生、学生、员工），根据 $\texttt{GSA}$ 算法，我们可以得出以下结论：
如果两方都坦诚相见，那么主动方更具优势。
如果决定方使用了阴谋诡计，那么决定方更具优势。
如果主动方使用了阴谋诡计，那么决定方更具优势。
如果双方都使用了阴谋诡计，那么……事情将会变得异常复杂，不在 $\texttt{OI}$ 探究的范畴内。
但是，在这个宣扬 `爱国 敬业 诚信 友善` 的社会里，我们是不是更应当通过主动来获得优势而不是通过欺骗来获得优势呢？
~~当然这已经和 $\texttt{Stable Matching}$ 没有关系了~~
好了做一下真正的总结：
$\texttt{GSA}$ 算法是解决 $\texttt{Stable Matching}$ 问题的不二之选，这个算法其实是基于贪心的，通过这种算法，我们可以在 $O(n^2)$ 的复杂度内找出稳定匹配。稳定匹配问题虽然在 $\texttt{OI}$ 中不常见，但也不失为是一个经典的问题。
### 参考文献：
[男女稳定匹配问题 stable matching](https://blog.csdn.net/alwaysik/article/details/78949250)
最后附加一篇输出中间过程的 $\texttt{GSA}$ 代码：
[GSA-中间过程](https://zombie462.github.io/others/GSA.html)
## 谢谢观看！