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.