Statistical Physics Methods and Algorithmic Applications in Graphical Games and Combinatorial Optimization

统计物理领域致力于利用各种概率、统计和组合工具研究物质的宏观特性。然而，最近，很明显，一些源自统计物理学的工具和观察结果的应用远远超出了它们的预期范围，并且在统计物理学以外的各种领域中被发现有用，例如编码理论，信息论，马尔可夫随机场的统计推断，以及最近在运筹学的几个核心领域，例如组合优化和博弈论。具体来说，在PI之前的工作中，人们发现，在统计物理学中深入研究的所谓的相关衰减（远程独立性）特性，对算法的设计和分析具有深远的应用。本建议的目标是以系统的方式发展这一有前途的方法。具体来说，PI打算专注于在以下三个具有挑战性的算法领域设计快速（多项式时间）算法：a)计算图形游戏中的纯和混合纳什均衡；B)设计计算整数规划问题和多面体体积问题可行解个数的确定性近似算法；c)具有随机目标的组合优化/整数规划问题。这是一个令人兴奋的新的研究议程，这在运筹学领域是前所未有的。这项研究将导致新的算法设计工具，并加强算法、组合优化、博弈论和统计物理领域之间的新兴联系。

The statistical physics field is devoted to the macroscopic properties of matter using a variety of prob-abilistic, statistical and combinatorial tools. Recently, however, it became apparent that some of the tools and observations originating from statistical physics, have applications far beyond their intended scope and are found useful in a variety of fields outside of statistical physics, such as coding theory, information theory,statistical inference in Markov Random Field, and more recently in several core areas of operations research,such as combinatorial optimization and game theory. Specifically, it was discovered, partially in PI's prior work,that the so-called correlation decay (long-range independence) property studied in great depth in statistical physics, has far reaching applications for the design and analysis of algorithms. The goal of the present proposal is to develop this promising approach in a systematic way. Specifically, the PI intends to focus on designing fast (polynomial time) algorithms in the following three challenging algorithmic areas: a) computing pure and mixed Nash equilibrium in graphical games; b) designing deterministic approximation algorithms for counting the number of feasible solutions of an integer programming problem and the problem of computing a volume of a polytope; and c) combinatorial optimization/integer programming problems with stochastic objectives. This is an exciting new research agenda, which has not been pursued in the operation research field before. The research will lead to new algorithmic design tools and strengthen a newly emerging connections between the fields of algorithms, combinatorial optimization, game theory on the one hand, and statistical physics on the other hand.