学海网

毕业论文-算法博弈论中的两个均衡问题，共69页，31976字，附外文资料等
中文摘要
在博弈论中，以 John Forbes Nash 命名的纳什均衡已成为最广泛的解概念。
纳什均衡是指这样的策略配置，其中任何一个玩家都不愿意单边修改自己的策略。
最近兴起的算法博弈论这一领域，吸引了诸多的计算机科学家，他们从理论算法
的角度分析譬如说可计算性或者近似性。
本篇论文研究了算法博弈论中的两个均衡问题：
第一个是在不完全信息下的最佳定价策略。我们通过贝叶斯纳什均衡定义了
什么是参与者的理性，并且将其与单调函数的迭代联系在了一起。基于这个关系，
我们通过分析的方法以及矩阵分析中的技巧，设计了一个精确计算均衡以及最优
定价的多项式算法。
第二个是机制设计问题，我们需要建立可信机制，使得每个玩家都愿意汇报
自己的真实信息，且这一策略处在纳什均衡。我们的工作与大部分工作的不同在
于我们不允许金钱的传递。对于度量空间中的二设施选址问题，我们在确定性和
随机性两个模型下，证明了近似比的上下界。我们的界在常数倍的比下是紧的，
这大大改进了目前最优的结果。
关键词：纳什均衡；定价；可信机制；设施选址问题

目录
第 1 章
第 2 章
引文 ...1
社交网络下的定价问题 ...3
2.1 问题背景 .3
2.1.1 主要贡献 .......4
2.1.2 相关工作 .......5
2.2 问题描述 .6
2.3 均衡的迭代表示 7
2.3.1 均衡的迭代定义 .....8
2.3.2 均衡的性质 ...9
2.4 核心算法 ......... 10
2.4.1 一个指数复杂度的例子 .. 10
2.4.2 扫描法（ Line Sweep Method） . 10
2.5 对角优限制下的扫描法 ....... 11
2.5.1 算法细节与证明 ... 12
2.5.2 结论 .. 15
2.6 无限制的扫描法 ........ 16
2.7 小结 ....... 20
第 3 章 无金钱参与的可信机制 . 22
3.1 问题背景 ......... 22
3.1.1 主要贡献 ..... 23
3.1.2 相关工作 ..... 24
3.2 预备知识 ......... 25
3.2.1 半组群可信（ Partial Group Truthfulness） ... 26
3.3 确定性机制的线性下界 ....... 27
3.3.1 像集（ Image Set） 27
3.3.2 下界的证明 . 29
3.3.3 讨论 .. 31
3.4 比例分配机制（ Proportional Mechanism） ....... 32
3.4.1 可信性 ........ 32
3.4.2 对社会成本的近似比 ...... 34
3.4.3 讨论 .. 37
3.5 圆上的机制 ...... 37
3.5.1 组群可信性 . 39
3.5.2 对社会成本的近似比 ...... 40
3.5.3 讨论 .. 41
3.6 未决问题及讨论 ........ 42
第 4 章
总结 . 43
插图索引 ......... 44
表格索引 ......... 45
参考文献 ......... 46
致 谢 ..... 49
声 明 ..... 50
附录 A 外文资料的调研阅读报告 51
Robust Mechanism Design 51
Introduction. 51
Equilibrium Selection ...... 52
Preliminaries ......... 52
The Results . 54
Distinguishable Dominance and Rationally Robust Implementation........ 55
The 1/6 Mechanism on the Total Performance 56
Open Questions ..... 58
Reference ...... 59
在学期间参加课题的研究成果 ...... 60