摘要
本文主要研究了与网络博弈和优化相关的三个问题，分别是负外部性产品的社会网络推广顺序问题（第二章），负外部性产品的社会网络定价问题（第三章）和平行网络拥塞博弈问题（第四章）。 一.负外部性产品的社会网络推广顺序模型从产品推广顺序的角度探讨了之前较少被研究的社会网络负外部性。产品的负外部性使得对每个消费者而言，他购买产品的愿望会随着其拥有该产品的网络邻居的增多而减小。该模型从卖家的角度寻找一个推广具有负外部性的产品的关于消费者的顺序;目标是最大化其中某种产品的被选购的数量。我们证明了该模型中的两个最大化产品数量问题都是NP-难的，并为它们设计了两个具有常数近似的多项式时间算法来找出所需要的顺序。另外我们考虑了如何在保证稳定状态（消费者最终不后悔自己的购买选择）的前提下寻找推广顺序以最大化产品数量的问题。我们设计了性能良好的多项式时间近似算法求解该问题。 二.负外部性产品的社会网络定价模型研究在社会网络中如何给具有负外部性的产品定价;其目标是最大化卖家的收益。产品对于消费者的价值由两部分构成:内在价值和外在价值;而外在价值与外部性密切相关。我们分内在价值为完全信息时和内在价值为非完全信息两种情况来分别研究: (1)当内在价值为完全信息时，我们考虑最优多次定价问题。我们证明了即使在网络结构和内在价值都非常特殊情况下，找一个最优的多次定价策略是NP-难的。与该困难性形成对照，我们设计了一个简单快速的贪婪算法;该算法得出的定价策略可以保证获得至少一半的最优收益。我们还证明了单次最优定价作为最优多次定价的近似，在很多情形下具有令人满意的性能。 (2)当内在价值为非完全信息时，我们假设消费者是策略性的，且他们的内在价值都服从某一个均匀分布;我们研究如何确定单次定价来最大化贝叶斯纳什均衡的期望收益。我们证明了求一般网络中的贝叶斯纳什均衡的收益是NP-难的。对于特殊的网络拓扑结构，我们在多项式时间内给出了完全网络上的最优定价以及正则网络上的1/4-近似定价。 三.平行网络拥塞博弈（亦称为排序博弈）模型研究了机器类型相同情况下的最差均衡效率(即无政府代价price of anarchy,简记为PoA)。与传统模型只把工件看成自私的参与者不同，我们将工件和机器都看作博弈的自私参与者，提出了新博弈模型下的稳定状态的概念—对偶均衡，并且证明了在对偶均衡意义下PoA严格等于1.4，大大改进了传统模型的PoA（其值为2）。我们的结果揭示了一个与人们一般直观相悖的有趣现象:在有些情况下，增加系统中个体的自私性反而会提高系统的均衡效率。
NETL