论文部分内容阅读
本文所考虑的模型是非原子型自私路由博弈模型,它是博弈论研究中一个经典的模型。模型模拟人们自利的路径选择而形成交通流状况,其均衡流代表着系统趋于稳定时人们日常的路径选择。在该模型中,有一个著名的布雷斯悖论:给定网络中,存在一个真子网络,其均衡流费用低于全网络均衡流费用。该悖论是德国数学家布雷斯1968年发现的。布雷斯悖论是非常反直观的;它的出现表明:增添路径反而使得交通状况更加拥挤。借助博弈论的经典概念分析可知,布雷斯悖论的发生意味着均衡流不是弱帕累托最优解。以此为出发点,本文研究并回答了如下几个网络设计方向广泛关注的问题:什么样的网络拓扑结构能够保证其中的自私路由不会发生布雷斯悖论?在什么样的网络拓扑结构下自私路由的均衡流始终是弱帕累托最优的?在什么样的网络拓扑结构下自私路由的均衡流始终是帕累托最优的? 第一章引言部分概述自私路由问题的研究背景,实际应用和相关研究。 第二章首先定义了若干网络图类,并对相应的网络结构进行了刻画。然后介绍了非原子型自私路由博弈模型,分别给出其均衡流发生布雷斯悖论,均衡流是弱帕累托最优和均衡流是帕累托最优的严格数学定义。 第三,四,五,六章分别针对含固定的单对始终点的网络,含非固定的单对始终点的网络,含固定的多对始终点的网络,含非固定的多对始终点的网络,具体回答了上述问题:刻画了不会发生布雷斯悖论的网络拓扑结构,均衡流是弱帕累托最优的网络拓扑结构以及均衡流是帕累托最优的网络拓扑结构。 第七章中总结论文结果,讨论未解决的问题和将来的研究方向。