Theory Tea Meeting Talk: On Local Dynamics for Two Equilibrium Concepts

I’ll talk about two projects I worked on this summer at MSR. The first project was to find local dynamics that lead to balanced outcomes in exchange networks, an equilibrium concept that combines notions of stability and fairness. I’ll present a distributed algorithm that computes a balanced outcome on bipartite graphs that builds on the auction algorithm for the assignment problem. The second project was to find local dynamics that lead to equilibrium in the Linear Fisher Market. I’ll describe an approach we have for analyzing some “proportional response” dynamics that we hope will allow us to prove true polynomial-time convergence. This approach formulates the proportional response dynamics as a descent algorithm on a convex program that describes equilibria in the Fisher Market.