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

Massachusetts Institute Of Technology, Cambridge MA

Investigators

Abstract

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.