THE INVISIBLE HAND ALGORITHM - SOLVING THE ASSIGNMENT PROBLEM WITH STATISTICAL PHYSICS

We propose a novel method for solving the assignment problem using tec hniques adapted from statistical physics. We derive a convex effective energy function whose unique minimum corresponds to the optimal assig nment. Steepest descent results in a continuous-time dynamical system that is guaranteed to converge arbitrarily close to the optimal soluti on. Our algorithm has an appealing economic interpretation and has ver y interesting connections to the discrete auction algorithm proposed b y Bertsekas. We also derive an alternative discrete algorithm for mini mizing the effective energy based on a theorem by Sinkhorn.