带受限配对的稳定婚姻问题Gale-Shapley算法适配方案咨询

问题基础前提 #

我们讨论的是加入配对硬限制的稳定婚姻问题变体：配对限制核心参考两个维度——双方是否居住在同一城市、是否接受异地恋，场景默认所有人无法变更居住地点。
男性主动求婚的原生Gale-Shapley（简称GS）算法有明确的特性：输出结果一定是男性最优、女性最劣的稳定匹配，即所有男性能在所有可行稳定匹配中拿到自己最偏好的伴侣，所有女性会拿到所有可行稳定匹配中自己最不偏好的伴侣。我们的核心目标是在保留这个特性的前提下，设计合理的偏好列表规则、必要的算法修改规则，尽可能让女性避免匹配到自己无法接受的异地不兼容伴侣。

两种常规处理方案的缺陷 #

• 方案1：直接从偏好列表中移除所有不兼容对象
  规则逻辑为：如果男性不在女性的偏好列表中，哪怕男性本身接受异地，女性也不能和该男性订婚。
  这个方案的核心问题是直接破坏了原生GS算法的完备性保证：当存在无法形成全匹配的限制条件时（比如所有人分住不同城市且全员不接受异地），算法必然无法输出全员配对结果。虽然在实际场景中多数人集中居住在少数几个城市，全匹配失败的概率不高，但算法层面没有稳定匹配的输出保障。
• 方案2：保留长度为n的固定长度偏好列表，按兼容性分梯队排序
  规则逻辑为：所有参与者的偏好列表长度统一为总人数n，把对自己而言位置兼容的伴侣（满足双方同城，或本人接受异地，和对方的异地接受意愿无关）排在列表前半段，位置不兼容的伴侣（双方异地且本人不接受异地）排在列表后半段，同梯队内按个人真实偏好排序。
  这个方案确实能大概率保证男性匹配到位置兼容的对象，但没有解决女性侧的问题：原生GS算法本身会让女性拿到所有可行稳定匹配里最差的选项，如果大量女性有明确的同城匹配要求，这个单纯的列表排序方式反而会提升女性被迫匹配到异地不兼容对象的概率。

最小修改适配方案 #

不需要大幅改动GS算法的核心流程，只需要在女性拒婚环节增加一层硬约束优先级判断，就能在保留「男性主动求婚下男性最优、女性最劣」特性的基础上，最大程度降低女性匹配到不兼容对象的概率：

1. 偏好列表统一采用固定长度n，排序规则保持和方案2一致：自己可接受的位置兼容对象排在前半段，自己不可接受的位置不兼容对象排在后半段，同梯队内完全按个人真实偏好排序即可。
2. 对原生GS算法的女性选择规则做如下修改：

   女性每次收到男性求婚时，先对求婚者、自己当前的订婚对象（如果存在）做兼容性分层判断，再做选择：

   • 如果求婚者属于位置兼容对象，当前订婚对象属于位置不兼容对象：直接解除原有婚约，和求婚者订婚
   • 如果求婚者属于位置不兼容对象，当前订婚对象属于位置兼容对象：直接拒绝本次求婚
   • 只有当求婚者和当前订婚对象同属位置兼容梯队、或同属位置不兼容梯队时，才按照原生GS规则，选择偏好列表中排序更靠前的对象，拒绝排序靠后的对象

3. 这个修改不会破坏GS算法的稳定性：位置不兼容的配对本质是优先级低于所有兼容配对的不可接受选项，最终输出的结果依然是男性最优的稳定匹配，同时会最大程度压缩女性匹配到不兼容对象的空间——只有当整个问题不存在任何能让该女性匹配到兼容对象的稳定解时，才会出现女性匹配到异地不兼容对象的情况，这也是所有可行方案里能达到的最优结果。

内容的提问来源于stack exchange，提问作者Cole