动态网络流博弈问题的研究

The model of dynamic network flow games(DNFG)，which emphasizes the dynamic feature of network flows and the distributed characteristic of network games, is among the important problems in the area of Algorithmic Game Theory (AGT). The study of DNFG is of both theoretical and practical significance. It is a new research direction, for which related results and resolving methods are very limited. Many important problems remain unsolved. In this project, we will conduct thorough study on two important DNFG models – the discrete one and the continuous one. Our research focus includes: the existence of equilibrium, the inefficiency of equilibrium (a.k.a. price of anarchy), equilibrium computation and algorithmic mechanism design, which have been attracting a lot of attentions from AGT and combinatorial optimization communities.

动态网络流博弈问题着眼于网络流的动态性和博弈分布式特点，是一个既有很强实际背景又有非常重要理论价值的算法博弈论问题。其研究才刚刚起步；相应成果和研究工具、方法还比较有限；有许多重要问题有待回答和解决。项目拟深入研究动态网络流博弈问题的离散模型和连续模型。研究重点包括博弈均衡的存在性、均衡的有效性、均衡的计算及算法机制设计等算法博弈论、组合优化领域关注的核心问题。

动态网络流博弈目前是一个较为前沿的研究课题，在该项目中，我们研究了动态网络流博弈问题。这是一个具有重要理论和实际价值的研究课题。在该研究中，我们提出了一个新的离散个体自私路由博弈模型，并分别考虑了参与个体是非自适应的（每个个体在开始选一个从起点到终点的路并沿着走）和自适应的（每个个体每到一个中间节点就做一次在线的选择）两种情况。对非自适应个体，我们通过构造性方法证明了该博弈永远存在一个纯策略纳什均衡。我们给出了所有纳什均衡的结构刻画并证明每个纳什均衡都是帕累托最优和满足先进先出等性质。我们另外我们设计了快速算法来找一个纳什均衡或者求任意一个个体的最优选择。对自适应个体，我们是第一个研究这种博弈模型的。我们首次证明了子博弈精炼纳什均衡的存在性。并且对于非自适应个体下的任意纳什均衡，我们都可以构造一个子博弈精炼纳什均衡使得它实现的路集恰好是给定的纳什均衡，但反过来则不成立。对于系列-平行网络，我们证明了（入流流速小于网络容量时）均衡下每条边上队列的有界性，这表明均衡的无政府代价是有上界的，这推广了之前关于无政府代价有界的结果。另外我们还考虑了连续动态网络流博弈并得到了一些关于纳什流动态变换的结果。