New Convex Programs and Distributed Algorithms for Fisher Markets with Linear and Spending Constraint Utilities

In this paper we shed new light on convex programs and distributed algorithms for Fisher markets with linear and spending constraint utilities.

• We give a new convex program for the linear utilities case of Fisher markets. This program easily extends to the case of spending constraint utilities as well, thus resolving an open question raised by Vazirani.
• We show that the gradient descent algorithm with respect to a Bregman divergence converges with rate O(1/t) under a condition that is weaker than having Lipschitz continuous gradient (which is the usual assumption in the optimization literature for obtaining the same rate).
• We show that the Proportional Response dynamics recently introduced by Zhang is equivalent to a gradient descent algorithm for solving the new convex program. This insight also gives us better convergence rates, and helps us generalize it to spending constraint utilities.