基于多样性约束的匹配模型与算法

发布时间：2017-05-20 08:28

  本文关键词：基于多样性约束的匹配模型与算法，由笔耕文化传播整理发布。

【摘要】：1962年David Gale和Lloyd Shapley提出了稳定匹配的概念,以此为基础的理论及应用获得了2012年的诺贝尔经济学奖。该模型涉及应用数学、经济学和计算机科学,在市场机制设计和工程实践中有很多重要的应用。在多元化的今天,很多实际的匹配问题需要结果中更多考虑多样性要求。因为背景的差异性往往使得这样的群体更活跃、更有创造力也更稳健。本文研究基于多样性约束的单边偏好列表的匹配问题。多样性的描述中包含大量的互补性,这给经典的稳定匹配算法带来了本质性的困难。本文通过对参与者分类并控制每一个子类的上下限来间接地描述多样性。考虑到单边偏好列表,我们分别提出松弛优化方法和动态清仓价格机制来解决该问题。在松弛优化方法中,我们在满足子类上下限约束的前提下,把最大化偏好得分的总和作为优化目标。我们证明了在子类不交的情况下,松弛后的优化问题仍然可以得到整数最优解。为了进一步平衡公平性和多样性,我们在优化目标中加入多样性的惩罚项,通过调整惩罚系数来把握两者之间的平衡。结合升价拍卖和降价拍卖,我们提出了两阶段的动态清仓价格机制。在第一阶段我们对供不应求的商品进行升价拍卖,以满足上限约束;在第二阶段,我们对还有剩余的商品进行降价拍卖,以满足下限约束。最终得到满足上下限约束的清仓价格和稳定匹配。类似于松弛优化方法中公平性和多样性的平衡,我们的动态机制在满足上下限约束之后,启发式地尝试优化多样性度量,进一步平衡公平性和多样性。付费搜索是商业搜索引擎主要的赢利方式,其本质上就是一个匹配的优化问题,这个领域的研究也称为计算广告。本文给出匹配模型和算法在计算广告中的应用,并进行了数值实验。
【关键词】：稳定匹配 清仓价格 动态机制 NP完全问题 计算广告
【学位授予单位】：清华大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：TP301.6
【目录】：

• 摘要3-4
• abstract4-8
• 第1章 引言8-35
• 1.1 稳定匹配的模型与算法9-22
• 1.1.1 延迟接受算法10-12
• 1.1.2 Top Trading Circle算法12-14
• 1.1.3 市场机制下的匹配算法14-21
• 1.1.4 四种算法的联系21-22
• 1.2 稳定匹配的扩展及变型22-30
• 1.2.1 偏好列表的扩展22-24
• 1.2.2 一对多的扩展24-29
• 1.2.3 高维匹配问题29-30
• 1.3 研究内容30-35
• 1.3.1 问题的描述、思路及解决方案30-33
• 1.3.2 各章内容简介33
• 1.3.3 主要贡献33-35
• 第2章 容量下限与多样性约束35-45
• 2.1 容量下限约束35-36
• 2.2 多样性约束36-39
• 2.3 多样性约束的分类刻画39-41
• 2.4 相关工作41-45
• 第3章 松弛优化方法45-61
• 3.1 多样性作为上下限约束45-54
• 3.1.1 数学表达45-46
• 3.1.2 松弛后的解46-51
• 3.1.3 对偶问题51-54
• 3.2 多样性和公平的平衡54-61
• 3.2.1 二次规划56-58
• 3.2.2 一些其他选择58-61
• 第4章 动态清仓价格机制61-75
• 4.1 动态清仓价格机制研究现状61-63
• 4.2 上下限约束的动态机制算法63-68
• 4.3 子类约束的动态机制算法（SCDM）68-69
• 4.4 考虑平衡的子类约束动态机制算法（SCDMB）69-72
• 4.5 讨论72-75
• 第5章 计算广告75-80
• 5.1 付费搜索系统75-76
• 5.2 广义二价竞拍76-77
• 5.3 广告选择77-80
• 第6章 总结与展望80-82
• 6.1 总结80-81
• 6.2 展望81-82
• 参考文献82-88
• 致谢88-90
• 个人简历、在学期间发表的学术论文与研究成果90

【相似文献】

中国期刊全文数据库 前2条

1 季晓慧;张健;;一种求解混合约束问题的快速完备算法[J];计算机研究与发展;2006年03期

2 ;[J];;年期

中国重要会议论文全文数据库 前1条

1 沈杰;王艳;张芳明;;市场经济条件下诚信理论和我国的政策[A];国有经济论丛(2012)——深入推进国有经济战略性调整[C];2012年

中国重要报纸全文数据库 前6条

1 本报特约评论员;化要素约束压力为转型发展动力[N];中国城乡金融报;2013年

2 唐人;“约束”与“速度”不能再打架[N];中国国土资源报;2006年

3 陶金节;从四个方面约束政府权力[N];民主与法制时报;2013年

4 杨成超;民主社会的危机与非选举约束[N];中国图书商报;2004年

5 牛润霞;无差异法则是医治自主创新缺乏的良药[N];学习时报;2012年

6 夏兴园 赵明岚;提高资源配置使用效率[N];吉林日报;2005年

中国博士学位论文全文数据库 前3条

1 崔卿;基于多样性约束的匹配模型与算法[D];清华大学;2015年

2 闫邹先;我国上市公司最优激励约束结构研究[D];山东大学;2008年

3 杨丹妮;政府筹资方式选择与约束:一项思想史考察及对中国财政体制改革的意义[D];浙江大学;2015年

中国硕士学位论文全文数据库 前4条

1 王恒进;国有企业高层管理人员的约束与激励问题研究[D];苏州大学;2003年

2 黄志鹏;中国企业对欧盟直接投资研究[D];福州大学;2005年

3 宋其勤;带二维装箱约束的团队定向问题的研究[D];重庆交通大学;2014年

4 柯丹;国有商业银行激励与约束问题研究[D];广西大学;2004年

  本文关键词：基于多样性约束的匹配模型与算法，，由笔耕文化传播整理发布。

本文编号：381120