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

统计物理方法和算法在图形游戏和组合优化中的应用

• 批准号: 1031332
• 负责人: David Gamarnik
• 金额: $ 33.71万
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2010
• 资助国家: 美国
• 起止时间: 2010-09-01 至 2013-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1031332&HistoricalAwards=false
• 关键词: Statistical; Physics; Methods; Algorithmic; Applications

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.

统计物理领域使用多种概率，统计和组合工具致力于物质的宏观特性。然而，最近，很明显，起源于统计物理学的某些工具和观察结果远远超出了其预期范围，并且在统计物理以外的各个领域中都有用，例如编码理论，信息理论，Markov Random中的统计推断，最近在多个核心领域中，例如组合式优化和游戏理论。具体而言，在PI先前的工作中部分发现，所谓的相关性衰减（远程独立性）属性在统计物理学中深入研究，对算法的设计和分析已远远达到了应用。本提案的目的是以系统的方式开发这种有前途的方法。具体而言，PI打算专注于在以下三个具有挑战性的算法领域中设计快速（多项式时间）算法：a）计算图形游戏中纯和混合的NASH平衡； b）设计确定性近似算法，以计算整数编程问题的可行解决方案的数量以及计算多层级体积的问题；和c）与随机目标的组合优化/整数编程问题。这是一个令人兴奋的新研究议程，以前从未在操作研究领域中提出过。这项研究将导致新的算法设计工具，并加强算法，组合优化，游戏理论以及另一方面的统计物理之间的新出现的联系。