经典稳定婚配问题(SM)的定义是Gale和Shapley^[1]首次提出的: SM的一个实例$I_{n}=(M,W,P)$, 其中$M=\{m_{1},m_{2},\cdots,m_{n}\}$表示未婚男士集合, $W=\{w_{1},w_{2},\cdots,w_{n}\}$表示未婚女士集合, $P_{i}$为个体$i$的偏好序, $P=(P_{i})_{i\in M\cup W}$为偏好断面.对于任意的男士$m_{i}\in M$, 定义他在$W$上的严格偏好关系:如果$m_{i}$认为$w_{j}$比$w_{k}$好, 记作$w_{j}\succ_{m_{i}}w_{k}$.类似地, 对于任意的女士$w_{i}\in W$, 定义$m_{j}\succ_{w_{i}}m_{k}$表示$w_{i}$认为$m_{j}$比$m_{k}$好.

令$E=M\times W$, 实例$I_{n}$中一个匹配$\mu$是$E$的一个子集, 它把$M$和$W$中的人配成对, 且不允许重复. $\forall (m_{i},w_{j}) \in \mu$, 记$\mu(m_{i})=w_{j}$, $\mu(w_{j})=m_{i}$分别表示$m_{i}$和$w_{j}$在匹配$\mu$下的匹配对象; $I_{n}$中的匹配$\mu$称为完美匹配, 若它把集合$M$和$W$配成$n$对, 使得每人有且仅有唯一配偶.

定义1.1 ^[1] 设$I_{n}$为SM的一个实例, $\mu$为中$I_{n}$的一个匹配, 若存在$(m_{i},w_{j})\in E\backslash\mu$, 满足:

(1) $w_{j} \succ_{m_{i}} \mu(m_{i})$;

(2) $m_{i} \succ_{w_{j}} \mu(w_{j})$;

则称$(m_{i},w_{j})$是的匹配$\mu$一个阻止对.即$m_{i}$和$w_{j}$可以各自离开原来的婚姻匹配$\mu$的安排, 私自结婚.若$\mu$中无阻止对存在, 则称匹配$\mu$是稳定的.

文献[1]中Shapley等已经证明了在完全严格偏好下婚配问题一定存在稳定的完美匹配, 并给出了求稳定完美匹配的GS算法, 得到的稳定匹配记为$\mu$.当男士优先选择, 女士接受时，称为男士优先的GS算法, 记为MGS算法, 得到的稳定匹配记为$\mu_{M}$.类似地, 也有女士优先的GS算法, 记为WGS算法, 得到的稳定匹配记为$\mu_{W}$.

例1 设$I_{3}=\langle M,W,P\rangle$为某一SM的实例, 其中$M=\{m_{1},m_{2},m_{3}\}$ $,W=\{w_{1},w_{2},w_{3}\}$, 偏好断面$P$如下:

$\begin{array}{cc} m_{1}: w_{1}\succ w_{2}\succ w_{3} w_{1}: m_{2}\succ m_{3}\succ m_{1}\\ m_{2}: w_{2}\succ w_{3}\succ w_{1} w_{2}: m_{3}\succ m_{1}\succ m_{2}\\ m_{3}: w_{3}\succ w_{1}\succ w_{2} w_{3}: m_{1}\succ m_{2}\succ m_{3} \end{array}$

采用MGS算法, 得男士优先完美婚姻匹配为$\mu_{M}=\{(m_{1},w_{1}),(m_{2},w_{2}),(m_{3},w_{3})\}$.

采用WGS算法, 得女士优先完美婚姻匹配为$\mu_{W}=\{(m_{1},w_{3}),(m_{2},w_{1}),(m_{3},w_{2})\}$.

然而在实际生活中, 参与婚配的男女也许只愿意接受他(她)偏好排序顺序中的前几位，对于在自己的偏好排序下的后几位异性发出的求婚信号不予理睬, 而宁愿保持单身.即在经典婚配问题中的完全偏好变为不完全偏好.本文主要研究在不完全偏好下:稳定匹配的婚配率及婚配中的男女对各自婚配的满意程度等问题, 具有一定的实际意义.

设$I_{n}=(M,W,P)$是SM的一个实例, 假定每人只对其偏好序中前$k(1\leq k < n)$位进行偏好排列, 即在严格的偏好关系下进行部分排序, 用$P^{k}$表示不完全偏好下的偏好断面, 这种婚配问题为不完全偏好下的婚配问题(PSM), PSM的一个实例记为$I_{n}^{k}$.当$k=n$时, 即为SM, 称为为完全偏好下的婚配问题.

类似地, PSM的实例$I_{n}^{k}$中一个匹配$\mu$是$E=M\times W$的一个子集, 它把$M$和$W$中的人配成对, 且不允许重复.则每个人$x\in M\cup W$在匹配$\mu$下的匹配对象$\mu (x)$规定如下:

$$ \label{eq:1} \mu(x)=\left\{ \begin{aligned} y,\exists y\in M \cup W,(x,y)\in \mu {\hbox{或者}} (y,x)\in \mu,\\ x,\forall y\in M \cup W,(x,y)\not\in\mu {\hbox{和}} (y, x)\not\in \mu, \end{aligned} \right. $$

其中$\mu(x)=x$表示$x$单身.同样利用GS算法, 可以求出不完全偏好下的婚配问题的稳定匹配, 记为$\mu(I_{n}^{k})$, 此时不一定是完美匹配.

例2 设$I_{4}=(M,W,P)$为某一SM的实例, 偏好断面$P$如下:

$\begin{array}{cc} m_{1}: w_{1}\succ w_{2}\succ w_{3}\succ w_{4} w_{1}: m_{4}\succ m_{3}\succ m_{1}\succ m_{2}\\ m_{2}: w_{1}\succ w_{4}\succ w_{3}\succ w_{2} w_{2}: m_{2}\succ m_{4}\succ m_{1}\succ m_{3}\\ m_{3}: w_{2}\succ w_{1}\succ w_{3}\succ w_{4} w_{3}: m_{4}\succ m_{1}\succ m_{2}\succ m_{3}\\ m_{4}: w_{4}\succ w_{2}\succ w_{3}\succ w_{1} w_{4}: m_{3}\succ m_{2}\succ m_{1}\succ m_{4}\\ \end{array}$

采用GS算法, 得唯一稳定完美婚姻匹配(即采用MGS算法和WGS算法得到的结果相同):

$$\mu(I^{4}_{4})=\{(m_{1},w_{3}),(m_{2},w_{4}),(m_{3},w_{1}),(m_{4},w_{2})\}.$$

假定男女在婚配时只选择自己偏好序中的前2名(即此时$n=4,k=2$).得到一个PSM的实例$I^{2}_{4}=(M,W,P^{2})$, 不完全偏好断面$P^{2}$如下:

$\begin{array}{cccc} m_{1}: w_{1}\succ w_{2}&m_{2}: w_{1}\succ w_{4}&m_{3}: w_{2}\succ w_{1}&m_{4}: w_{4}\succ w_{2}\\ w_{1}: m_{4}\succ m_{3}&w_{2}: m_{2}\succ m_{4}&w_{3}: m_{4}\succ m_{1}&w_{4}: m_{3}\succ m_{2} \end{array}$

采用GS算法, 得$I^{2}_{4}$的唯一稳定婚姻匹配: $\mu(I^{2}_{4})=\{(m_{2},w_{4}),(m_{3},w_{1}),(m_{4},w_{2})\}$.其中$m_{1},w_{3}$仍然维持单身.

定义2.1 对于上述提到的完全偏好婚配问题(SM)和不完全偏好婚配问题(PSM), 他们的某一个实例$I^{k}_{n}(1\leq k\leq n)$可以由一个三元组$(M,W,P^{k})$完全确定, 以后统称之为婚配市场, 记为$I=(M,W,P)$(即$I\in \bigcup\limits^{n}_{k=1}I^{k}_{n}$).

在婚配市场的一个实例中, 完全偏好下得到的稳定婚配是完美匹配, 但是, 不完全偏好下得到的稳定婚配不一定是完美匹配(即有人可能单身), 因此有必要研究稳定婚配的匹配率.

定义2.2 匹配率为某婚配市场$I$在匹配$\mu$下配对成功的人数$2a$与参与人数$2n$比值, 即

$$\rho( P^{k})=\frac{a}{n}.$$

如例1(完全偏好下)匹配率为$\rho=100\%$; 例2(不完全偏好下)匹配率为$\rho=75\%$.虽然不完全偏好下的匹配率低于完全偏好下的匹配率, 是因为有人觉得宁可单身也不愿意选择自己不太喜欢的伴侣, 因此, 研究婚配市场中男女对稳定婚配结果的满意程度也是有必要的.定义满意度函数如下:

定义2.3 设$I_{n}^{k}=(M,W,P^{k})(1\leq k\leq n)$为婚配市场的一个实例, $\mbox{rank}_{x}(y)$表示$y$在$x$偏好排序下排名数.函数$f_{\mu}: M\cup W\rightarrow R^{+} $称为满意度函数, 若满足: $\forall x\in M\cup W$,

(a)在同一稳定匹配$\mu$下:

(1) 若$\mu(x)=x,\mu(y)=y$, 则$f_{\mu}(x)=f_{\mu}(y)$;

(2) 若$\mu(x)\neq x,\mu(y)=y$, 则$f_{\mu}(x)>f_{\mu}(y)$;

(b)在不同稳定匹配$\mu_{1}$, $\mu_{2}$下:

(1) 若$\mu_{i}(x)=y_{i}\neq x(i=1,2)$, 则$f_{\mu_{1}}(x)>f_{\mu_{2}}(x)\Longleftrightarrow {\hbox{rank}}_{x}(y_{1})< {\hbox{rank}}_{x}(y_{2})$;

(2) 若$\mu_{i}(x)=x(i=1,2)$, 则$f_{\mu_{1}}(x)=f_{\mu_{2}}(x)$;

(3) 若$\mu_{1}(x)=y\neq x,\mu_{2}(x)=x$, 则$f_{\mu_{1}}(x)>f_{\mu_{2}}(x)\Longleftrightarrow {\hbox{rank}}_{x}(y)< k$, $f_{\mu_{1}}(x)<f_{\mu_{2}}(x)\Longleftrightarrow {\hbox{rank}}_{x}(y)> k$.

定义2.4 设$I_{n}^{k}=(M,W,P^{k})(1\leq k\leq n)$为婚配市场的一个实例, $f_{\mu}$为满意度函数, $\mu$为$I_{n}^{k}$的一个匹配, 对$\mu$的满意度定义如下:

(1) 参与者平均满意度:

男士的平均满意度: $\Pi_{\mu}(M)=\frac{1}{n}\sum\limits_{x\in M}(f_{\mu}(x))$;

女士的平均满意度: $\Pi_{\mu}(W)=\frac{1}{n}\sum\limits_{x\in W}(f_{\mu}(x))$;

参与者平均满意度: $\Pi_{\mu}(n)=\frac{1}{2n}\sum\limits_{x\in M\cup W}(f_{\mu}(x))$.

(2) 匹配成功者平均满意度: $\Pi_{\mu}(a)=\frac{1}{2a}\sum\limits_{\mu(x)\neq x}(f_{\mu}(x))$, 其中$2a$表示匹配成功的人数.

设$I_{n}^{k}=(M,W,P^{k})(1\leq k\leq n)$为婚配市场的一个实例, 不完全偏好下得到的稳定婚配不一定是完美匹配(即有人可能单身), $\rho( P^{k})\leq 1$.显然, 稳定婚配的匹配率受偏好断面$P^{k}$影响.

例3 设$I_{5}^{k}=(M,W,P^{k})(1\leq k\leq 5)$, $II_{5}^{k}=(M,W,Q^{k})(1\leq k\leq 5)$为婚配市场的两个实例, 相应的偏好断面如下:

偏好断面$P$:

$\begin{array}{cc} m_{1}: w_{1}\succ w_{3}\succ w_{5}\succ w_{2}\succ w_{4}& w_{1}: m_{3}\succ m_{2}\succ m_{5}\succ m_{4}\succ w_{1}\\ m_{2}: w_{4}\succ w_{2}\succ w_{1}\succ w_{3}\succ w_{5}& w_{2}: m_{5}\succ m_{3}\succ m_{4}\succ m_{1}\succ w_{2}\\ m_{3}: w_{1}\succ w_{4}\succ w_{2}\succ w_{3}\succ w_{5}& w_{3}: m_{1}\succ m_{4}\succ m_{2}\succ m_{3}\succ w_{5}\\ m_{4}: w_{2}\succ w_{1}\succ w_{5}\succ w_{4}\succ w_{3}& w_{4}: m_{1}\succ m_{5}\succ m_{3}\succ m_{2}\succ w_{4}\\ m_{5}: w_{5}\succ w_{2}\succ w_{1}\succ w_{3}\succ w_{4}& w_{5}: m_{2}\succ m_{1}\succ m_{4}\succ m_{5}\succ w_{3}\\ \end{array}$

偏好断面$Q$:

$\begin{array}{cc} m_{1}: w_{2}\succ w_{5}\succ w_{3}\succ w_{4}\succ w_{1}& w_{1}: m_{1}\succ m_{4}\succ m_{2}\succ m_{5}\succ w_{3}\\ m_{2}: w_{3}\succ w_{1}\succ w_{4}\succ w_{2}\succ w_{5}& w_{2}: m_{3}\succ m_{1}\succ m_{4}\succ m_{2}\succ w_{5}\\ m_{3}: w_{5}\succ w_{3}\succ w_{2}\succ w_{4}\succ w_{1}& w_{3}: m_{1}\succ m_{2}\succ m_{5}\succ m_{3}\succ w_{4}\\ m_{4}: w_{2}\succ w_{1}\succ w_{5}\succ w_{3}\succ w_{4}& w_{4}: m_{2}\succ m_{4}\succ m_{1}\succ m_{5}\succ w_{3}\\ m_{5}: w_{2}\succ w_{4}\succ w_{3}\succ w_{5}\succ w_{1}& w_{5}: m_{3}\succ m_{5}\succ m_{4}\succ m_{1}\succ w_{2}\\ \end{array}$

在不完全偏好$P^{2}$下, 实例$I_{5}^{2}$的稳定匹配: $\mu(I_{5}^{2})=\{(m_{1},w_{3}),(m_{3},w_{1}),(m_{5},w_{2})\}$, 匹配率为$\rho( P^{2})=60\%$.

在不完全偏好$Q^{2}$下, 实例$II_{5}^{2}$的稳定匹配: $\mu(II_{5}^{2})=\{(m_{1},w_{2}),(m_{2},w_{3}),(m_{3},w_{5}),(m_{4},w_{1})\}$, 匹配率为$\rho( Q^{2})=80\%$.

上例说明:当参与婚配的人数, 不完全偏好下参与排名的人数均相同时$(n=5,k=2)$, 不同的偏好断面直接影响着不完全偏好下的匹配率.

对例3的实例$I_{5}^{k}=(M,W,P^{k})(1\leq k\leq 5)$, 利用GS(MGS或WGS)算法分别算出$I_{5}^{k}$的稳定匹配如下:

$\begin{array}{*{20}{c}} {{\mu _M}(I_5^1) = {\mu _W}(I_5^1):}&{({m_3},{w_1})}&{\rho ({P^1}) = 20\% }\\ {{\mu _M}(I_5^2) = {\mu _W}(I_5^2):}&{\{ ({m_1},{w_3}),({m_3},{w_1}),({m_5},{w_2})\} }&{\rho ({P^2}) = 60\% }\\ {{\mu _M}(I_5^3) = {\mu _W}(I_5^3):}&{\{ ({m_1},{w_3}),({m_3}\} ,{w_1}),({m_4},{w_5}),({m_5},{w_2})\} }&{\rho ({P^3}) = 80\% }\\ {{\mu _M}(I_5^4):}&{\{ ({m_1},{w_3}),({m_2},{w_4}),({m_3},{w_1}),({m_4},{w_2}),({m_5},{w_5})\} }&{\rho ({P^4}) = 100\% }\\ {{\mu _W}(I_5^4):}&{\{ ({m_1},{w_3}),({m_2},{w_4}),({m_3},{w_1}),({m_4},{w_5}),({m_5},{w_2})\} }&{\rho ({P^4}) = 100\% }\\ {{\mu _M}(I_5^5):}&{\{ ({m_1},{w_3}),({m_2},{w_4}),({m_3},{w_1}),({m_4},{w_2}),({m_5},{w_5})\} }&{\rho ({P^5}) = 100\% }\\ {{\mu _W}(I_5^5):}&{\{ ({m_1},{w_3}),({m_2},{w_4}),({m_3},{w_1}),({m_4},{w_5}),({m_5},{w_2})\} }&{\rho ({P^5}) = 100\% } \end{array}$

从上面的实例, 可以看出匹配率随$k$值增大而增大, 但得到稳定匹配不完全相同, 有以下结果.

定理2.5 设$I_{n}^{k}=(M,W,P^{k})(1\leq k\leq n)$, $II_{n}^{k}=(M,W,Q^{k})(1\leq k\leq n)$为婚配市场的两个实例, 则有

(1) 一般有$\rho( P^{k})\neq\rho( Q^{k})$, $1\leq k<n$;

(2) $1\leq k< n$, $\rho( P^{k})\leq \rho( P^{k+1})$, 但是不一定有

$$\mu( I_{n}^{k})\subseteq\mu(I_{n}^{k+1}).$$

证 (1) 显然成立.

(2) 不失一般性, 假定在MGS算法下, 令$A_{k}(x)$表示男士$x$在$I_{n}^{k}$中可接受异性匹配集合, 显然$A_{1}(x) \subset A_{2}(x)\subset\cdots\subset A_{n-1}(x)\subset A_{n}(x)$.设$x\in M$在$I_{n}^{k}$下是匹配成功者, 即存在$(x,y)\in \mu(I_{n}^{k})$且rank$_{x}(y)\leq k,{\hbox{rank}}_{y}(x)\leq k$.则在$I_{n}^{k+1}$下:若$x$仍是匹配成功者, 则

$$|\mu(I_{n}^{k})|\leq |\mu(I_{n}^{k+1})|,$$

即结论成立.现在证明若$x$单身, 则会导致一个新的男士$x'$($x'$在$I_{n}^{k}$下单身), 使$(x',y)\in\mu(I_{n}^{k+1})$.即仍有

$$|\mu(I_{n}^{k})|\leq |\mu(I_{n}^{k+1})|.$$

断言(i)若$x$在$I_{n}^{k+1}$下单身, 则$y$一定不是单身.否则$(x,y)$就是一个阻止对, 矛盾; 即有$(x',y)\in\mu(I_{n}^{k+1})$.

断言(ii) rank$_{y}(x')<{\hbox{rank}}_{y}(x)\leq k$, 即$y$和一个优于$x$的男士$x'$匹配, 且${\hbox{rank}}_{x'}(y)=k+1$.否则$(x',y)$在$I_{n}^{k}$下就是一个阻止对, 矛盾.

断言(iii) $x'$在$I_{n}^{k}$下单身.否则存在$(x',y')\in \mu(I_{n}^{k})$, 且rank$_{x'}(y')\leq k$; 而rank$_{x'}(y)=k+1$, 这样$(x',y')$在$I_{n}^{k+1}$就是一个阻止对, 矛盾.

综上所述, 有$1\leq k< n$, $\rho( P^{k})\leq \rho( P^{k+1})$.

从上述例3发现$\mu(I^{1}_{5})\subseteq \mu(I^{2}_{5})\subseteq \mu(I^{3}_{5})\subseteq\mu_{w}(I^{4}_{5})$, 但是$ \mu(I^{3}_{5})\not\subseteq\mu_{M}(I^{4}_{5})$, 故不一定有$\mu( I_{n}^{k})\subseteq\mu(I_{n}^{k+1})$.

根据满意度函数的定义, 下面给出一个具体的满意度函数来刻画上述的婚配市场.

设$I^{k}_{n}$为一个婚配市场, $\mu$为$I^{k}_{n}$的一个匹配.定义参与人$x\in M\cup W$对匹配$\mu$的满意度函数:

$$f_{\mu}(x)=\left\{ \begin{array}{ll} \frac{1}{{\hbox{rank}}_{x}(y)},\mu(x)=y\neq x;\\ \frac{1}{2}(\frac{1}{k}+\frac{1}{k+1}),\mu(x)=x. \end{array} \right.$$

下面分析例3中实例$I_{5}^{k}=(M,W,P^{k})(1\leq k\leq 5)$的满意度, 首先根据上述满意度函数的定义, 得到满意度函数表如下

根据满意度函数表计算实例$I_{5}^{k}=(M,W,P^{k})(1\leq k\leq 5)$的满意度如下(均保留小数点后4位有效数字)

从上表可以发现如下规律

(1) 在任意实例下, 匹配成功者的平均满意度均不低于参与者的平均满意度, 即

$$\Pi_{a}(\mu)\geq\Pi_{n}(\mu).$$

这样才会激励剩男剩女们积极参与婚配.而$\Pi_{a}(\mu)$和$\Pi_{n}(\mu)$对$k$的增加没有严格的递增(或递减)关系.

(2) 同一婚配市场实例$I$中, 在男士优先情况下(MGS算法)男士的平均满意度不低于女士优先情况下(WGS算法)男士的平均满意度, 即$\Pi_{\mu_{M}}(M)\geq \Pi_{\mu_{W}}(M)$; 类似的, 在女士优先情况下(WGS算法)女士的平均满意度不低于男士优先情况下(MGS算法)女士的平均满意度, 即$\Pi_{\mu_{W}}(W)\geq \Pi_{\mu_{M}}(W)$.这进一步说明, 男士优先算法当然对男性有利, 女士优先算法当然对女士有利.

由上述分析得到如下的定理.

定理2.6 设$I_{n}^{k}=(M,W,P^{k})(1\leq k\leq n)$为婚配市场的任意一个实例, $\mu$为一稳定匹配, 在任意给定的满意度函数下, 有

(1) $\Pi_{a}(\mu)\geq\Pi_{n}(\mu)$;

(2) $\Pi_{\mu_{M}}(M)\geq \Pi_{\mu_{W}}(M)$, $\Pi_{\mu_{W}}(W)\geq \Pi_{\mu_{M}}(W)$.

证 (1) 设$\mu$的匹配率为$\rho=\frac{a}{n}$; 当$\mu(x)=x$时, 令$f_{\mu}(x)=f_{k}$, 由定义2.3的(a)(2) 知$\Pi_{a}(\mu)>f_{k}$, 则有

$\begin{array}{l} {\Pi _a}(\mu ) - {\Pi _n}(\mu )\\ = \frac{1}{{2a}}\sum\limits_{\mu (x) \ne x} {({f_\mu }(x))} - \frac{1}{{2n}}\sum\limits_{x \in M \cup W} {({f_\mu }(x))} \\ = \frac{1}{{2an}}(n\sum\limits_{\mu (x) \ne x} ( {f_\mu }(x)) - a(\sum\limits_{\mu (x) \ne x} {({f_\mu }(x))} + \sum\limits_{\mu (x) = x} {({f_\mu }(x))))} \\ = \frac{1}{{2an}}((n - a)\sum\limits_{\mu (x) \ne x} {({f_\mu }(x))} - a\sum\limits_{\mu (x) = x} ( {f_\mu }(x)))\\ = \frac{1}{{2an}}((n - a)2a{\Pi _a}(\mu ) - a \cdot 2(n - a){f_k}) \ge 0. \end{array}$

故有$\Pi_{a}(\mu)\geq\Pi_{n}(\mu)$成立.

(2) 由MGS算法和WGS算法, 易证(参见文献[1]).