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.