通讯网络中的算法博弈

论文摘要

在现实世界中的大多数复杂网络,例如互联网,都是由数以千计的大大小小的用户（或代理商）组成的,这些用户都试图使自己的收益最大化。这样的用户被称为自利的（或者自私的,理性的）的用户。对于这样的大规模非合作网络问题,博弈论和数理经济学为我们提供了很好的研究手段。为了衡量整个系统性能的优劣程度,我们设立一个目标函数作为评价标准,称之为系统目标函数,它的最优解称为全局最优解。从单独的用户来看,每个用户又都有一个反映其个人偏好的收益函数,理性的用户都是以最大化其收益函数来选择策略的。显然,所有自利用户选择的策略组合往往不是全局最优,甚至和全局最优值相差甚远。近年来,计算机科学家们对估计非合作网络下的稳定状态和全局最优解的差距表现出浓厚的兴趣。Koutsoupias和Papadimitriou在文献[44;55]中正式提出调和率的概念,用于研究所有实例下纳什均衡对应的系统费用和全局最优解的最大比率。这个概念量化了系统在完全缺乏中央调控的情况下,纳什均衡解和全局最优解的最大差值。与之相连的另一个概念是稳定率,它是所有实例下最好的纳什均衡（使系统目标最优的纳什均衡）和全局最优值的最大比率。稳定率有着网络协议方面的现实背景,在非合作网络中,一方面用户可以理性的选择自己的行为策略,网络的管理者不能对用户采取任何强制的措施;另一方面网络的管理者又想得到一个系统总收益尽可能大的稳定解,怎么才能这满足两方面的要求呢?很自然的,网络管理者可以想到以下方案:先制定一个系统总收益尽可能大的稳定的网络用户协议（即如果用户都按照这个协议行动,那么它构成一个纳什均衡）,并向用户推荐这个协议。稳定率反映的是面对自利的用户,在最坏的情况下,网络管理者所能得到的最大收益和全局最优解的比率。计算机科学家感兴趣的另一个主题是怎么设计网络以有效的避免Braess悖论。Braess悖论并不是说数学理论上有什么自相矛盾的地方,而是反映一个和人们的直觉相违背的现象。1968年Dietrich Braess[11]举出了一个实例,说明交通网络中增加一条通路不仅没有改善网络交通,反而使网络上的出行时间增加了,而且是所有出行者的出行时间都增加了。自此以后,这种出力不讨好且与人们直观感受相背的交通网络现象就被命名为Braess悖论。Braess悖论激发了如下的网络设计问题[60]:即给定一个网络,这个网络中是否存在悖论边?如何高效地寻找图中存在的悖论边并去掉这些边,使网络处于最优的纳什均衡状态（即最坏的纳什均衡对应的系统目标值尽量的小）?对这个问题进行进一步推广,又可以提出另外一个网络设计问题,称为有选择性的网络设计问题[5]:给定一个网络G=（V,E）,以及一个边子集E1（?）E,如何找出G的一个子图H,使得H包含边子集E1,且子图H上的网络处于最优的纳什均衡状态?换句话说,就是在不涉及边子集E1的情况下,如何高效地寻找图中存在的悖论边并去掉这些边,使网络处于最优的纳什均衡状态?本文分为以下三个方面:首先,我们考虑线性拥塞博弈,对总体加权延迟函数、用户延迟和函数、资源延迟和函数等三种系统目标函数,分别给出了稳定率的上界。对带全局优先序的拥塞博弈和无限可分加权拥塞博弈,我们证明用户单回合最优反应导致的近似程度是常数界的。对带固定序的拥塞博弈,我们给出了相关均衡的调和率。其次,我们讨论了带“刻板用户”的路由博弈问题,即在平行机背景中探讨线性函数及M/M/1函数下纳什均衡流的调和率。最后,我们从计算复杂性的角度分析了瓶颈路由博弈的可选择网络设计问题。

论文目录

• 摘要
• Abstract
• 第一章 概述
• 1.1 相关问题简介
• 1.2 本文主要结果
• 第二章 预备知识
• 2.1 最优化问题
• 2.2 计算复杂性
• 2.3 近似算法
• 2.4 博弈的策略式
• 2.4.1 纳什均衡
• 2.4.2 相关均衡
• 第三章 线性加权拥塞搏弈
• 3.1 拥塞博弈和势博弈
• 3.2 稳定率
• 3.3 单回合最优反应的近似程度
• 3.4 相关均衡的调和率
• 第四章 包含"刻板的用户"的Wardrop路由博弈
• 4.1 Wardrop路由博弈及其调和率
• 4.1.1 数学模型
• 4.1.2 纳什流及最优流
• 4.1.3 调和率（The price of anarchy）
• 4.2 包含"刻板的用户"的摸型
• 4.2.1 模型介绍
• 4.2.2 线性函数下最大费用模型
• 4.2.3 M/M/1型函数下用户和函数模型
• 第五章 瓶颈路由博弈中有选择性网络设计问题的计算复杂性
• 5.1 引言
• 5.2 预备知识
• 5.3 计算复杂性结果
• 参考文献
• 致谢
• 在学期间完成的论文