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.

统计物理领域致力于使用各种概率、统计和组合工具来研究物质的宏观性质。然而，最近变得明显的是，一些起源于统计物理的工具和观测，其应用远远超出了它们预期的范围，并在统计物理之外的各种领域被发现有用，例如编码理论、信息论、马尔可夫随机场中的统计推理，以及最近在运筹学的几个核心领域，如组合优化和博弈论。具体地说，人们发现，在统计物理学中深入研究的所谓的相关衰变(长程独立)性质，在算法的设计和分析中有着深远的应用。本提案的目标是以系统的方式发展这一有希望的办法。具体地说，PI计划致力于在以下三个具有挑战性的算法领域中设计快速(多项式时间)算法：a)计算图形游戏中的纯和混合纳什均衡；b)设计用于计算整数规划问题和计算多面体体积的可行解的确定性近似算法；以及c)具有随机目标的组合优化/整数规划问题。这是一个令人振奋的新研究议程，这是运筹学领域以前从未追求过的。这项研究将带来新的算法设计工具，并加强算法、组合优化、博弈论和统计物理等领域之间新出现的联系。