CAREER: Algorithms for Risk Mitigation in Networks

随着世界越来越多地连接和嵌入到计算系统中，网络算法具有巨大影响的潜力。一个关键的挑战是，尽管在计算、连接和数据分析方面取得了巨大的进步，但不确定性仍然普遍存在于生活的各个方面，我们需要从根本上改变我们所寻求的解决方案的定义。例如，在交通不确定的情况下，最优路线是什么？这取决于用户的风险厌恶程度，他们会寻求最小化预期延迟和路线的可变性之间的平衡。我们如何计算这条风险最小化的路线？更一般地说，我们如何在复杂网络中计算风险最小化的解决方案，以及风险是如何定义的？风险一直是金融经济学研究和实践的前沿。然而，仍然主要需要设计与这些风险模型相对应的计算方法，以及开发特定于网络系统的新风险模型和解决方案技术。CAREER项目的目标是通过结合计算机科学、运筹学、经济学和金融学的跨学科方法，为网络系统（如交通、电信、能源等）的风险缓解新领域奠定算法基础。技术里程碑是：(1)开发网络系统风险模型的综合理论，部分受金融和经济学风险模型的启发，部分受网络系统的具体要求的驱动；(2)通过整合不确定性和风险，推进经典算法理论，其中所有输入数据都是预先可用的——这将通过开发非线性和非凸组合优化的新技术来实现；(3)利用动态数据来改进自适应决策，使用和推进马尔可夫决策过程中的工具，开发新的工具来逼近最优解；(4)通过发展从非线性（风险规避）公式到标准线性公式的约简，进一步发展了用于重复决策的在线算法理论。在高水平上，拟议研究的变革潜力是从根本上改变对网络算法领域随机问题的思考，从预期性能转向理解和降低风险。这项研究的动机是交通、电信和能源等国家重要问题。它有潜力改善涉及不确定性和风险规避用户的各种应用，例如，减少交通和电信网络的拥堵，改善智能电网的运行等。PI将积极致力于建立与其他学科的桥梁，例如，通过组织跨学科讲习班。PI还将参与高中拓展项目、大学生夏令营以及提高女性和少数族裔在计算机领域参与度的项目。

As the world becomes increasingly connected and embedded in computational systems, network algorithms have the potential for tremendous impact. A key challenge is that, despite the enormous progress in computing, connectivity and data analytics, uncertainty remains pervasive in all aspects of life and we need a fundamental shift in the definition of what solutions we seek. For example, what is the optimal route under uncertain traffic? That depends on the risk-averseness of a user, who would seek to balance minimizing expected delay and the variability of the route. How can we compute this risk-minimizing route? More generally, how can we compute risk-minimizing solutions in complex networks and how is risk defined? Risk has been at the forefront of research and practice in finance and economics. However, there is still a major need for designing computational approaches corresponding to these risk models, as well as developing new risk models and solution techniques that are specific to networked systems. The goal of this CAREER project is to lay the algorithmic foundation of a new area of risk mitigation for networked systems (such as transportation, telecommunications, energy, etc.) via an interdisciplinary approach that unifies Computer Science, Operations Research, Economics and Finance. The technical milestones are to: (1) Develop a comprehensive theory of risk models for networked systems, in part inspired by risk models in finance and economics, and in part driven by the specific requirements of networked systems; (2) Advance the classic theory of algorithms, in which all input data is available upfront, by integrating uncertainty and risk---this will be achieved by developing novel techniques for nonlinear and nonconvex combinatorial optimization; (3) Leverage dynamic data to improve adaptive decision-making, using and advancing tools from Markov Decision Processes and developing new tools for approximating the optimal solutions; (4) Further the theory of online algorithms for repeated decision-making by developing reductions from nonlinear (risk-averse) formulations to the standard linear formulations.On a high level, the transformative potential of the proposed research is to fundamentally shift thinking about stochastic problems in the field of network algorithms away from expected performance and instead towards understanding and mitigating risk. The research is motivated by problems of national importance in transportation, telecommunications and energy. It has the potential to improve a variety of applications that involve uncertainty and risk-averse users, for example, reducing congestion in transportation and telecommunication networks, improving the operation of the smart grid, etc. The PI will actively work on building bridges to other disciplines, for example, via organizing interdisciplinary workshops. The PI will also participate in high-school outreach programs, summer camps for undergraduates and programs for increasing the participation of women and underrepresented minorities in computing.