- 文献综述（或调研报告）：
1962年，Gale和Shaply在论文“大学招生与稳定婚姻”中开创性地提出了“稳定匹配”的概念，分别提出了“大学招生”与“稳定婚姻”两个模型，他们最先提出和介绍了双边匹配模型，并且提供了一个合适的解决方案，该概念被称为“稳定” (stability)。 他们还通过一个简单的迭代算法——递延接受算法 (deferred acceptance algorithm)，证明了稳定匹配的存在。文章中提到的经典双边匹配模型涉及两个不相交集的个体：男人和女人。其中每个人对于来自另一组的一个子集进行严格地优先排序。每个个体可以和另一边的至多一个个体匹配，因此该模型也被称为“严格偏好的一对一匹配”。之后，稳定匹配问题得到了越来越多的关注，基于实际应用，很多稳定匹配问题的变体被提了出来。
1971年，Shaply和Shubkik提出了分配博弈的双边市场模型，在这个市场中，大量不可分割的单位（如房屋、汽车等）成为货币交换的产品，并且每个参与者都提供或要求仅一个单位。单位不一定相同，同一个单位也可能对不同的参与者有不同的价值。他们证明这种博弈的核心结果，即那些不能被部分玩家改善的结果，是与最优分配问题相对应的某个线性规划问题的分配策略，并且这些结果对应于完全符合竞争性平衡供求关系的价格表。同时他们用经济术语来描述和解释核心的几何结构，明确地注意其中没有产品差异的特殊情况，并且表明使用其他博弈论分配策略概念进一步分析是可取的。
1990年，Harold N.Gabow研究了具有链接的加权匹配和最近公共祖先的数据结构，证明一般图的加权匹配问题可以在时间O(n(m nlogn))内求解，其中n和m分别是顶点和边的数目，此前这一结论只被运用在二部图中。同时他还证明在n个节点上的一系列m个nca和链接操作可以在时间O(malpha;(m,n) n)内处理，此前只有对受限类型的链接操作才有这一结论。
Baiou和Balinski在2000年提出了稳定的一夫多妻制模型，进行了多对多稳定分配问题的建模，将该问题转化为一个定义在网格上的有向图和正整数向量的组合，并对该模型下不同稳定分配方案的结构进行了阐释。
Irving,Manlove与Scott在2000年研究了医院/居民关系问题，其中参与者的偏好涉及关系或其他形式的中立。由此，他们提出了最强标准下的第一线性时间算法，即所谓的超稳定性。他们给出了一个复杂度为O(n2)的算法来找到一个强稳定匹配，其中n是相互接受的住院对夫妇的数目。同时，在这种情况有一个下界，即判定一个偶图是否包含完美匹配的复杂性。他们通过对比，证明了如果偏好被允许为任意偏序，则判定是否存在强稳定匹配是NP完全问题。此后，他们在2003年的“医院/居民问题中的强稳定性”一文中给出了更详尽的阐述。
Endre Borosa,Vladimir Gurvicha,Steven Jaslara和Daniel Krasner在2004年发表了论文，研究了具有循环偏好的三边系统中的稳定匹配问题，提供了一个例子来证明在Gale和Shaply提出的三边家庭稳定婚姻问题中，稳定的匹配并不总是存在；同时他们证明，如果偏好是循环的，并且智能体的数量限于每个性别三个，那么总是存在稳定的匹配。此后在2006年，Kimmo Eriksson,Jonas Sjouml;strand, Pontus Strimling将这个结果扩展到每个性别四个智能体，并且证明一些众所周知的稳定性充分条件不适用与循环三性别稳定匹配。
2005年，Roth、Sonmez和Unver提出了成对肾脏交换模型。在肾脏交换中，交换的大小尺寸受到了限制，最初，肾脏交换也仅能在两个患者和捐赠者之间实现。他们证明了当成对患者-捐助者和医生之间具有0-1偏好时，存在一大类有约束的交换机制。这包括了确定性机制，使器官库目前用来分配尸体器官的随机机制的公平问题适应优先级设置， 实现了在两对不兼容的患者和捐献者之间的肾脏交换，对提高美国的肾脏交换成功率起到了巨大推动效果。
Chan,P.H.、Huang,X.,Liu,Z.,Zhang,C.和Zhang,S在2016年提出了室友市场模型，该模型讨论了将2n个人分配到n个房间的各种分配方案的可行性，并提出了社会福利、稳定性、人员无嫉妒和房间无嫉妒的概念。在论文中，他们证明了对于一个给定的室友市场实例，即便所有人的估值都在0-1之间，寻找社会福利最大化的分配策略是NP难问题，并给出了一个时间复杂度为O()、至少达到2/3最大社会福利的多项式时间算法；同时，找到2人稳定的分配策略、甚至是判断这一分配策略是否存在，都是NP难问题；从4人稳定的角度考虑，他们证明总是存在一个4人稳定的分配策略，同时给出了一个可以找到4人稳定分配策略的时间复杂度为O()的算法，并找到了一个使社会福利至少达到最优的2/3的4人稳定分配策略；最后，他们考虑了无嫉妒属性，并证明人员无嫉妒是一个过于强大的属性，其对应的分配策略一般不存在，而相对较弱的房间无嫉妒属性，其对应的分配策略总是存在并可以有效地被找到。
2017年，Guangda Huzhang,Xin Huang,Shengyu Zhang,Xiaohui Bei在前人提出的室友市场模型基础上，研究了随机到达的在线室友问题，提出了一种常数因子竞争算法，并将结果推广到每个房间智能体数不相同的情况。它还显示了在这种在线设置中满足不同稳定性条件的正面和负面结果。这种模式旨在与捕获一种通用的在线资源分配策略，该分配策略可以将资源分配给多个智能体，共享相同资源的智能体具有外部积极性。也就是说，智能体对资源的评估还取决于分配了相同资源的其他智能体的身份。该框架留下了许多未来工作的方向，它对于所提供算法与最优分配策略的近似程度保持开放；同时，在线室友问题设置中考虑策略行为和研究真实机制也是值得的。
参考文献
以上是毕业论文文献综述，课题毕业论文、任务书、外文翻译、程序设计、图纸设计等资料可联系客服协助查找。
