相关概念的界定及解析

本书研究的HSM（1，1，n，1）问题是家政服务人员与雇主的一对一双边匹配问题，与以往双边匹配问题不同的是家政服务人员与雇主的双边匹配需要考虑技能约束。下面给出偏好可接受对、技能可接受对以及可行技能约束匹配的定义。

在家政服务人员和雇主给出的偏好排序中，若家政服务人员认为雇主是可接受的，且该雇主认为家政服务人员也是可接受的，则称家政服务人员和雇主是偏好可接受对；否则，称为偏好不可接受对。

定义6.4（偏好可接受对） 在HSM（1，1，n，1）问题中，对于∀Wi∈W，∀Ej∈E，若（Wi，Ej）∈W×M满足rij≠n+1且tij≠m+1，则称（Wi，Ej）为偏好可接受对；否则，称为偏好不可接受对。

在HSM（1，1，n，1）问题中，若家政服务人员所具备的技能能够满足雇主的服务技能需求，则称家政服务人员和雇主为技能可接受对；否则，为技能不可接受对。

定义6.5（技能可接受对） 在HSM（1，1，n，1）问题中，对于∀Wi∈W，∀Ej∈E，若（Wi，Ej）∈W×M满足，则称（Wi，Ej）为技能可接受对；否则，称为技能不可接受对。

定义6.6（可行技能约束匹配） 设μ是HSM（1，1，n，1）问题的一个一对一双边匹配，若对于∀（Wi，Ej）∈μ都是偏好可接受对，并且也都是技能可接受对，则称匹配方案μ为可行技能约束匹配。

在家政服务人员与雇主的双边匹配问题HSM（1，1，n，1）中，若家政服务人员Wi的服务技能满足雇主Ej的技能需求，并且Wi认为Ej要优于当前服务的雇主，Ej也认为Wi要优于当前雇佣的家政服务人员，那么Wi将存在动机从当前雇主处辞职，Ej也会有动机解雇当前雇佣的家政服务人员，而Wi和Ej将私下进行匹配。显然这种情形会扰乱正常的家政服务市场秩序，为避免这种现象出现，本书给出技能约束稳定匹配的概念。

下面首先给出技能约束阻塞对的定义。

在匹配方案μ中，若家政服务人员Wi和雇主Ej都认为对方优于他们在匹配方案μ中的匹配对象，并且Wi满足Ej的服务技能需求，则称（Wi，Ej）是一个技能约束阻塞对。

定义6.7（技能约束阻塞对） 在HSM（1，1，n，1）问题中，设家政服务人员与雇主的一对一双边匹配μ：W∪E→W∪E，在匹配方案μ中，对于∀Wi∈W，∀Ej∈E，若偏好可接受对（Wi，Ej）同时满足以下条件：

（i）μ（Wi）=Wi或μ（Wi）=Eh，且rij＜rih；(www.xing528.com)

（ii）μ（Ej）=Ej或μ（Ej）=Wk，且tij＜tkj；

(iii)。

则称（Wi，Ej）是匹配方案μ的技能约束阻塞对。

定义6.8（技能约束稳定匹配） 在HSM（1，1，n，1）问题中，设家政服务人员与雇主的一对一双边匹配μ：W∪E→W∪E，若匹配方案μ是可行技能约束匹配，并且μ中不存在技能约束阻塞对，则称匹配方案μ为技能约束稳定匹配。

由定义6.4—定义6.7容易获得以下性质：

性质6.1 在HSM（1，1，n，1）问题中，若（Wi，Ej）是匹配方案μ的技能约束阻塞对，则μ一定是技能可接受对。

性质6.2 在HSM（1，1，n，1）问题中，若匹配方案μ是技能约束稳定匹配，则μ中的任意一个匹配对都是偏好可接受对，同时也是技能可接受对。

定理6.1（技能约束稳定匹配存在性） HSM（1，1，n，1）问题的技能约束稳定匹配集合是非空的。

证明：设家政服务人员Wi和雇主Ej给出的偏好序值列表分别为P（Wi）和P（Ej），i=1，2，…，m；j=1，2，…，n。把HSM（1，1，n，1）问题进行如下处理：对于∀Wi∈W，∀Ej∈E，若（Wi，Ej）不是技能可接受对，则将Ej从Wi的偏好序值列表P（Wi）中删除，同时把Wi从Ej的偏好序值列表P（Ej）中删除。记处理后的HSM（1，1，n，1）问题为HSM′（1，1，n，1），那么显然在HSM′（1，1，n，1）问题中，家政人员的技能都能满足偏好列表中雇主的服务技能需求。因此，可将HSM′（1，1，n，1）视为具有不完全偏好列表的婚姻匹配问题。在婚姻匹配问题中，若匹配方案不存在同时满足定义6.7中条件（i）和（ii）的匹配对，则称匹配方案为稳定匹配。由此可知，若HSM′（1，1，n，1）存在稳定匹配方案，则原问题HSM（1，1，n，1）也必定存在技能约束稳定匹配。而Gale和Shapley通过构造的延迟接受算法DAA已经证明婚姻匹配问题至少存在一个稳定匹配。因此，HSM（1，1，n，1）中的技能约束稳定匹配集合也一定是非空的。证毕

本书要解决的问题是：依据家政服务人员Wi的服务技能向量Pi、雇主Ej需要的服务技能向量Qj以及Wi给出的Ej的偏好序值rij、Ej给出的Wi的偏好序值tij，通过某种决策分析方法，获得家政服务人员与雇主满意度都尽可能高的技能约束稳定匹配。