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

Speaker  Ben Birnbaum

Affiliation  Theory Tea Meeting Talk

Host  David Wilson

Duration  00:52:46

Date recorded  17 September 2009

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.

©2009 Microsoft Corporation. All rights reserved.
> Theory Tea Meeting Talk: On Local Dynamics for Two Equilibrium Concepts