Recently MV18a identified and initiated work on the new problem of understanding structural relationships between the lattices of solutions of two ``nearby'' instances of stable matching. They also gave an application of their work to finding a robust stable matching. However, the types of changes they allowed in going from instance $A$ to $B$ were very restricted, namely, any one agent executes an upward shift. In this paper, we allow any one agent to permute its preference list arbitrarily. Let $M_A$ and $M_B$ be the sets of stable matchings of the resulting pair of instances $A$ and $B$, and let $\mathcal{L}_A$ and $\mathcal{L}_B$ be the corresponding lattices of stable matchings. We prove that the matchings in $M_A \cap M_B$ form a sublattice of both $\mathcal{L}_A$ and $\mathcal{L}_B$ and those in $M_A \setminus M_B$ form a join semi-sublattice of $\mathcal{L}_A$. These properties enable us to obtain a polynomial time algorithm for not only finding a stable matching in $M_A \cap M_B$, but also for obtaining the partial order, as promised by Birkhoff's Representation Theorem, thereby enabling us to generate all matchings in this sublattice. Our algorithm also helps solve a version of the robust stable matching problem. We discuss another potential application, namely obtaining new insights into the incentive compatibility properties of the Gale-Shapley Deferred Acceptance Algorithm.


翻译:最近,MV18a确定并开始研究了稳定匹配的两个“近邻”实例的解的格之间的结构关系问题。他们还将他们的工作应用于寻找鲁棒的稳定匹配。但是,他们在从实例$A$到$B$的变化类型非常有限,即任何一个代理都需要执行向上的位移。在本文中,我们允许任何一个代理将其偏好列表任意置换。让$M_A$和$M_B$分别为得到的实例$A$和$B$的稳定匹配集合,让$\mathcal{L}_A$和$\mathcal{L}_B$为相应的稳定匹配格。我们证明了$M_A\cap M_B$中的匹配形成了$\mathcal{L}_A$和$\mathcal{L}_B$的子格,并且$M_A\setminus M_B$中的匹配形成了$\mathcal{L}_A$的半格。这些属性使我们能够不仅在$M_A\cap M_B$中找到一个稳定的匹配,而且还能够像Birkhoff的表示定理承诺的那样得到偏序,从而使我们能够生成这个子格中的所有匹配。我们的算法还有助于解决鲁棒性稳定匹配问题的一个版本。我们讨论了另一个可能的应用,即对Gale-Shapley延迟接受算法的激励兼容属性获得新的洞见。

0
下载
关闭预览

相关内容

不可错过!《机器学习100讲》课程,UBC Mark Schmidt讲授
专知会员服务
72+阅读 · 2022年6月28日
Artificial Intelligence: Ready to Ride the Wave? BCG 28页PPT
专知会员服务
26+阅读 · 2022年2月20日
【干货书】开放数据结构,Open Data Structures,337页pdf
专知会员服务
16+阅读 · 2021年9月17日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
VCIP 2022 Call for Demos
CCF多媒体专委会
1+阅读 · 2022年6月6日
Hierarchically Structured Meta-learning
CreateAMind
25+阅读 · 2019年5月22日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
【论文】图上的表示学习综述
机器学习研究会
14+阅读 · 2017年9月24日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
2+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2009年12月31日
Arxiv
0+阅读 · 2023年5月19日
Arxiv
0+阅读 · 2023年5月19日
VIP会员
相关资讯
VCIP 2022 Call for Demos
CCF多媒体专委会
1+阅读 · 2022年6月6日
Hierarchically Structured Meta-learning
CreateAMind
25+阅读 · 2019年5月22日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
【论文】图上的表示学习综述
机器学习研究会
14+阅读 · 2017年9月24日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
相关基金
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
2+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2009年12月31日
Top
微信扫码咨询专知VIP会员