Distributed algorithms via gradient descent for fisher markets

Benjamin Birnbaum, Nikhil R. Devanur, Lin Xiao

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

45 Scopus citations

Abstract

Designing distributed algorithms that converge quickly to an equilibrium is one of the foremost research goals in algorithmic game theory, and convex programs have played a crucial role in the design of algorithms for Fisher markets. In this paper we shed new light on both aspects for Fisher markets with linear and spending constraint utilities. We show fast convergence of the Proportional Response dynamics recently introduced by Wu and Zhang. The convergence is obtained from a new perspective: we show that the Proportional Response dynamics is equivalent to a gradient descent algorithm (with respect to a Bregman divergence instead of euclidean distance) on a convex program that captures the equilibria for linear utilities. We further show that the convex program program easily extends to the case of spending constraint utilities, thus resolving an open question raised by Vazirani. This also gives a way to extend the Proportional Response dynamics to spending constraint utilties. We also prove a technical result that is interesting in its own right: that the gradient descent algorithm based on 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).

Original languageEnglish
Title of host publicationEC'11 - Proceedings of the 12th ACM Conference on Electronic Commerce
Pages127-136
Number of pages10
DOIs
StatePublished - 2011
Externally publishedYes
Event12th ACM Conference on Electronic Commerce, EC'11 - San Jose, CA, United States
Duration: Jun 5 2011Jun 9 2011

Publication series

NameProceedings of the ACM Conference on Electronic Commerce

Conference

Conference12th ACM Conference on Electronic Commerce, EC'11
Country/TerritoryUnited States
CitySan Jose, CA
Period06/5/1106/9/11

Keywords

  • distributed algorithm
  • gradient descent
  • market equilibrium
  • proportional response

Fingerprint

Dive into the research topics of 'Distributed algorithms via gradient descent for fisher markets'. Together they form a unique fingerprint.

Cite this