Collaborative Research: Complex Networks Optimization

本研究项目将在复杂网络优化，特别是分散网络优化的背景下，研究基于博弈论思想的优化算法。管理这种分散网络的核心问题可能是如何设定价格，以激励竞争用户进化到整体系统的最佳配置。该研究将在离线进行的人工动态游戏框架中调查经济竞争的强大范例，从而得出一种可能适用于大规模系统优化的算法。我们将研究的基本范例来自于虚拟游戏，这是一种适应性过程，其中每个玩家都假设其他玩家将根据他们之前游戏的经验分布进行游戏。虚拟游戏方法是一种新的优化范例，它借鉴了几个不同的学科和应用领域，包括经典优化、博弈论、运输科学和排队网络协议。该算法的鲁棒性允许实际系统的非结构化黑箱模型很少表现出经典优化方法所要求的那种平滑特性。它在两个重要的现实世界系统中的适用性：a)互联网流量路由协议和b)动态路由引导将被测试。复杂网络优化是一种重要的能力，在一个日益由越来越复杂的人与机器网络所主导的社会。例子包括智能交通系统、计算机网络以及客户和供应商的供应链。该研究的成功将为这类复杂结构系统的优化提供理论基础。通过将所提出的博弈论算法范例应用于通信和运输网络的设计和操作中出现的现实问题，其适用性将得到测试和改进。这项研究不仅会导致这些应用领域的潜在改进，而且还需要与行业和政府进行重要的互动，以确保所开发的模型和数据的真实性。

This research project will study optimization algorithms rooted in the ideas of game theory in the context of complex network optimization, and particularly decentralized network optimization. Probably the central issue in managing such decentralized networks has been how to set prices so as to motivate the competing users to evolve to an overall system optimal configuration. The research will investigate the powerful paradigm of economic competition in the framework of artificial dynamic games that are played off-line, resulting in an algorithm that is potentially practical for large-scale systems optimization. The basic paradigm that will be investigated derives from Fictitious Play which is an adaptive procedure wherein each player assumes that other players will play according to the empirical distribution of their previous plays. The Fictitious Play method is a novel paradigm for optimization that draws from several distinct disciplines and application areas, including classical optimization, game theory, transportation science, and queueing network protocols. The robust nature of the algorithm allows for the ill-structured black box models of real systems which seldom exhibit the kind of smoothness properties that classical optimization methods demand. Its applicability in the context of two important real-world systems: a) internet traffic routing protocols and b) dynamic route guidance will be tested. Complex networks optimization is an important capability in a society increasingly dominated by ever more complex networks of people and machines. Examples include intelligent transportation systems, computer networks, and supply chains of customers and suppliers. The success of the research will lead to the development of a theoretical basis for the optimization of such complex-structured systems. The applicability of the proposed algorithmic paradigm of game theory through its application to realistic problems arising in the design and operation of the communications and transportation networks will be tested and refined. This research will not only lead to potential improvements in these application arenas but will also necessitate significant interactions with industry and government to insure realism for the models and data developed.