CAREER: Algorithms for Risk Mitigation in Networks

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