网站地图 | 联系我们 | English | 意见反馈 | 主任信箱
 
首页 中心概况 新闻动态 科研进展 交流合作 人才培养 研究队伍 人才招聘 政策规章 数学交叉科学传播
科研进展
科研成果
研究专题
获奖
现在位置:首页 > 科研进展 > 科研成果
动态流的网络博弈研究取得进展
【打印】【关闭】

  2017-10-10 | 编辑:文/信息技术部

路由通常指在网络中选择路径连接起点-终点对;它是网络优化的基本任务之一。在自私路由(selfish routing)中,各点对之间的路径选择由不同的希望自身延迟尽可能小的自私网络用户共同完成。自私路由是Tim Roughgarden在2006年世界数学家大会(ICM)上作关于算法博弈论的45分钟报告时谈到的三个主要模型之一。已有的大多数工作都是研究静态交通流,而近些年来动态交通流开始引起了研究人员的注意。

信息技术部陈旭瑾、曹志刚与合作者最近完成了一项工作《动态流的网络博弈》。他们考虑了在一种无圈有向网络上的博弈,网络中有两个特殊点,分别称作源点和终点,网络中的每一条边至少在一条连接源点和终点的路上,每一条边有一个负载上限和传输费用。另外,假设时间是离散的,在每一个时间点,一组自私用户从网络的源点进入网络,期望尽快到达网络的终点。当一个用户使用一条边时,需要承担两个费用,一个是固定的传输费用,另外一个与用该边的用户多少以及边的负载相关。他们证明了该类路由的第一个子博弈精炼纳什均衡存在性结果。这个进展是对已有结果的一个重要拓展,因为它在纯理论模型和更加实用模型之间架起了一座桥梁。

上述研究工作的论文A Network Game of Dynamic Traffic被2017年国际计算机协会的经济与计算年会(2017 ACM Conference on Economics and Computation,简称EC)录用,陈旭瑾7月赴美国麻省理工学院参加会议并做了报告。该会议是国际计算机协会的顶级会议之一,今年的会议仅录用了两篇中国大陆作者的文章,另外一篇的作者是清华大学的图灵奖获得者姚期智院士。

欢迎访问国家数学与交叉科学中心 
地址:北京海淀区中关村东路55号 邮编:100190 电话: 86-10-62613242 Fax: 86-10-62616840 邮箱: ncmis@amss.ac.cn