Timezone: »

 
Poster
First-Order Methods for Large-Scale Market Equilibrium Computation
Yuan Gao · Christian Kroer

Wed Dec 09 09:00 AM -- 11:00 AM (PST) @ Poster Session 3 #1065
in Poster Session 4 »

Market equilibrium is a solution concept with many applications such as digital ad markets, fair division, and resource sharing. For many classes of utility functions, equilibria can be captured by convex programs. We develop simple first-order methods suitable for solving these convex programs for large-scale markets. We focus on three practically-relevant utility classes: linear, quasilinear, and Leontief utilities. Using structural properties of market equilibria under each utility class, we show that the corresponding convex programs can be reformulated as optimization of a structured smooth convex function over a polyhedral set, for which projected gradient achieves linear convergence. To do so, we utilize recent linear convergence results under weakened strong-convexity conditions, and further refine the relevant constants in existing convergence results. Then, we show that proximal gradient (a generalization of projected gradient) with a practical linesearch scheme achieves linear convergence under the Proximal-PL condition, a recently developed error bound condition for convex composite problems. For quasilinear utilities, we show that Mirror Descent applied to a new convex program achieves sublinear last-iterate convergence and yields a form of Proportional Response dynamics, an elegant, interpretable algorithm for computing market equilibria originally developed for linear utilities. Numerical experiments show that Proportional Response is highly efficient for computing approximate market equilibria, while projected gradient with linesearch can be much faster when higher-accuracy solutions are needed.

Author Information

Yuan Gao (Columbia University)

I am a PhD student in Operations Research (IEOR) at Columbia University working on large-scale optimization in machine learning and decision-under-uncertainty. I have also passed the CFA Level I Exam.

Christian Kroer (Columbia University)

More from the Same Authors