英语原文共 10 页，剩余内容已隐藏，支付完成后下载完整资料
提案中策略的不对称性：图上的Gale-Shapley算法
Yoshiteru Ishida* and Shigetaka Ikeno
Department of Computer Science and Engineering
Toyohashi University of Technology
Tempaku, Toyohashi 441-8580, Japan
摘要
本文提出了一个新的图来解决一个特殊的匹配问题：稳定的婚姻问题。该图不仅允许我们引出与代表配对的节点之间的阻断关系的结构，还允许我们引出DA算法（Gale-Shapley算法）动作的不对称性。稳定婚姻问题的对称性和不对称性允许我们推导出是否和何时应该提出求婚的策略。文中还讨论了对博弈论模型中奖罚不对称的一些影响。
关键词：图；稳定婚姻问题；概率算法、策略；决策；教育模型；匹配自动机
1.引言
对于人类来说，图表如果能正确地可视化，那么在视觉、听觉、触觉、嗅觉和味觉五种感官中，它的信息处理效率最高，发挥着重要作用。图表不仅在科学领域，而且在技术领域也被研究了很久。仅举几例，控制工程师的框图；铁路工程师的铁路图，计算机工程师的网络图等等。本文所提出的图基于铁路图而来（列车服务的线索、规划图）6、10。
另一方面，稳定的婚姻问题(SMP)3、4、7已被广泛研究，其过程和策略方面如何形成特定的稳定匹配是最近的一个焦点话题8。为了让问题解决者(决策者)找到一个合适的安排，不仅需要结构性知识，还需要过程性知识。
命名法
N为SMP的大小
Rmi,wj是mi对wj的一个等级，第一优先时为1，最后优先时为N。
Pwj为wj的人气，最受欢迎时为N，最不受欢迎时为N2。
N对男女的配对的表示方法{( mi, wj): i, j=1, ..., N}
本文主要研究用图表示的过程知识。通常，SMP假设每个代理只知道自己的偏好，而不知道其他代理的偏好。然而，我们假设问题解决者知道所有的偏好，并且问题解决者可以直观地获得问题全局图。
我们还提出了几个计算问题的图，特别是稳定的婚姻问题5。我们将提出另一个可以用于决策者策略的图。
这项工作的动机是为匹配问题提供一个新的图，利用GaleShapley算法引出过程方面的问题；并推导出决策的策略。
而在博弈论模型中找到奖励和惩罚的不对称的方面。这些方面可能会对主动学习的教育模型有所启示，该模型试图使教师和学生之间的行动从单向变为双向。我们将使用稳定的婚姻问题(或匹配自动机8)，因为著名的Gale-Shapley算法可以关注过程方面。
第2节简要回顾了稳定婚姻问题和Gale-Shapley算法。第3节提出了两个侧重于动态方面的SMP图，并与现有的侧重于静态方面的图进行了比较。第4节讨论了基于这两张图的每个代理的策略和决策者的策略。第5节讨论了可能应用于教育模式和与地方政府形成互助协议的问题。
2.稳定的婚姻问题是一个匹配问题。
匹配问题获得匹配：一组离散元素内部或之间的一组对子。例如，室友问题得到的匹配：为一对室友；稳定的婚姻问题得到的匹配：为两个组之间找出的一对夫妻：一组女性和一组男性。
稳定室友问题(stable roommate problem 简称SRP)假设有2N个参与者，每个参与者对其他2N -1个参与者有严格的(不绑定的)有序偏好。SRP寻求由N对参与者组成的完全匹配而不被阻塞。如果参与者A在匹配中偏好参与者C而非当前室友B，且偏好参与者C在匹配中也偏好参与者A而非当前室友D，则称该匹配被阻断。A-C这一对称为匹配中的阻断对。
稳定的婚姻问题(stable marriage problem 简称SMP)5、6、9假设有N个女人和N个男人，每个人对异性都有严格的(不绑定的)有序偏好。在允许未婚状态的框架下，每个人对异性成员和自己都有严格的偏好顺序。9从下例1可以看出，男人m2有一个排序（w2，w1，w3），即m2最喜欢w2，比w1更喜欢w2；比w3更喜欢w1。
SMP的问题实例可以用多种类型的图来描绘，然而，图通常侧重于节点如何连接。如 铁路图，可以包括交叉点甚至边缘的方向，作为视觉识别的重要信息。
例1.(SMP的示意图)
图1是以铁路图的结构为基础，以类似于铁路图的列车的方式表示阻塞方面的图。表 1 是一个 3 乘 3 的 SMP 实例的排序矩阵，图 1 右侧是一个与铁路图类似的图10。在图中，女性和男性都被放置在一条以人气为坐标的线上（全局坐标）。在每一个表示女人wi（男人mi）的点上，都有一个局部坐标，表示每个男人对女人wi的受欢迎程度（每个女人对男人mi的受欢迎程度）。
由图可知，即使一个男人在全局坐标上不受欢迎，但如果目标女性喜欢全球不受欢迎的男人而不是受欢迎的男人，那么他的求婚成功率可以超过更受欢迎的男人（提前到达车站）。这种情况用线的角度（相对人气）、两条线的交叉（阻挡求婚）和线的长度（求婚成功的可能性）来表示。右图1显示，即使从m3到w1 的提案比从m1到w1的提案成功的可能性大，也会被m1到w1的提案阻挡。
表1：三男三女的SMP排名矩阵。三男三女的SMP排名矩阵。
(a) 妇女与男子的排名；(b) 男子与妇女的排名；
(a) ( b)
图1.显示男女匹配的二方图（左）；以及用人气（右）表示求婚难度的图，用边的长度表示求婚难度，用两条边的交叉来阻挡其他求婚。
3.匹配问题的图示
本节介绍几个匹配问题的图，特别是稳定婚姻问题（SMP）5,6,9。SMP假设有N个女人和N个男人，每个人对异性都有严格的（不绑定的）排序偏好。在一个允许未婚状态的框架中，每个人对异性成员和自己都有严格的偏好顺序。9从下例2可以看出，男人m2有一个排序（w1，w2），即m2最喜欢w1，比w2更喜欢w1。
SMP寻求的是满足稳定性的完全匹配。稳定性要求有阻断对的概念。如果mi比wp更喜欢wq，wq比mj更喜欢mi，则两对（mi，wp）和（mj，wq）被对（mi，wq）阻断。没有被阻断的完全匹配称为稳定匹配。(mi,wp)和(mj,wq)是占优势的。
3.1.静态和结构方面的图示
N乘N的SMP有(N!)2N个不同的组合实例(即使是3个女性乘3个男性，也有46,656个(3!)6)。然而，当忽略女性的标签和男性的标签时，它们可以减少，当进一步忽略性别时，可以进一步减少到一半。本质上，偏好矩阵可以用图形来可视化。例如，可以用有向图和加权的双位图来表示；有向图（称为稳定婚姻图）等等。因此，我们只需要通过图的等价关系，将类的规模缩小。
例2.
作为静态和结构方面的图例，图2(a)显示了由表1的排序表指定的同一SMP实例的还原稳定结婚图。在稳定婚姻图中，行mi和列wj处的节点表示一对mi和wj；弧线表示偏好。在图2(a)中，m1行中w3到w1的弧线表示m1比w3更喜欢w1。在还原的稳定婚姻图中，从其他偏好推导出的偏好所对应的弧线被删除。
由于SMP可以看作是一个以偏好为输入，以匹配为输出的自动机（称为匹配自动机），因此可以画出状态转换图。图2（b）是在亲和空间中绘制的状态转换图（称为亲和空间图）。亲和空间图类似于相位空间图，相位空间图通常是为连续动态模型所画。亲和力用来衡量一对人的幸福感。A(mi，wj)是男人mi对女人wj的亲和力，A(wj，mi)是女人wj对男人mi的亲和力。让Rmi，wj表示男人mi对女人wj的等级。亲和力由等级定义为。A(mi,wj) = N 1 - Rmi,wj ，随着等级从1到N的变化，从N到1的变化。 以下是男女的总幸福感，用于在二维坐标中安排所有可能的匹配： <!--
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[259508]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
