Fisher market models and market equilibrium computation algorithms have long been central research topics in economics, operations research, and theoretical computer science. Recently, they have found diverse applications in the design of Internet marketplaces. In this thesis, we develop tractable optimization models and algorithms for computing market equilibria under various practically relevant settings.
In Chapter 1, we study first-order methods for computing market equilibria under a finite number of buyers with linear, quasilinear or Leontief utilities. For linear and Leontief utilities, we show that their corresponding convex programs---whose solutions are market equilibria and vice versa---exhibits strong-convexity-like structures after simple reformulations. This allows us to design the first gradient-based algorithms that achieve a linear rate of convergence for computing market equilibria. For buyers with quasilinear utility functions, we propose a new convex program capturing market equilibria, which is analogous to the Shmyrev convex program for linear utilities. Applying the mirror descent algorithm to this convex program leads to a distributed and interpretable Proportional Response (PR) dynamics that converges to equilibrium prices and utilities. This generalizes the classical PR dynamics and its convergence guarantees, previously known for linear utilities, to the case of quasilinear utilities.
In Chapter 2, we consider a generalization of a linear Fisher market where there is a finite set of buyers and a measurable item space. We introduce generalizations of the Eisenberg-Gale convex program and its dual to this setting, which leads to infinite-dimensional Banach-space optimization problems. We show that these convex programs always have optimal solutions and these optimal solutions correspond to market equilibria. In particular, a market equilibrium always exists. We also show that KKT-type optimality conditions for these convex programs imply the defining properties of market equilibria and are necessary and sufficient for a solution pair to be optimal. Then, we show that, similar to the classical finite-dimensional case, a market equilibrium is Pareto optimal, envy-free and proportional. Moreover, when the item space measure is atomless, we show that there always exists a pure equilibrium allocation, which can be viewed as a generalized fair division, that is, a Pareto optimal, envy-free, and proportional partition of the item space. This leads to generalizations of classical results on the existence and characterizations of fair divisions of a measurable set. When the item space is a closed interval and buyers have piecewise linear valuations, we show that the infinite-dimensional Eisenberg-Gale-type convex program can be reformulated as a finite-dimensional convex conic program, which can be solved efficiently using off-the-shelf optimization software. Based on the convex conic reformulation, we also develop the first polynomial-time algorithm for finding a fair division of an interval under piecewise linear valuations. For general buyer valuations or a very large number of buyers, we propose computing market equilibria using stochastic optimization and give high-probability convergence guarantees. Finally, we show that most of the above results easily extend to the case of quasilinear utilities.
In Chapter 3, we consider an online market setting where items arrive sequentially and must be allocated to buyers irrevocably. We define the notion of an online market equilibrium as time-indexed allocations and prices which guarantee buyer optimality and market clearance in hindsight. We propose simple, scalable and interpretable allocation and pricing dynamics termed as PACE (Pacing ACcording to Estimated utilities). When items are drawn independently from an unknown distribution with a possibly continuous support, we show that PACE leads to an online market equilibrium asymptotically. In particular, PACE ensures that buyers' time-averaged utilities converge to the equilibrium utilities of a static market with item supplies being the unknown distribution and that buyers' time-averaged expenditures converge to their per-period budget. Hence, many desirable properties of market equilibrium-based fair division such as envy-freeness, Pareto optimality, and the proportional-share guarantee are also attained asymptotically in the online setting. Next, we extend the dynamics to handle quasilinear buyer utilities, which gives the first online algorithm for computing pacing equilibria in first-price auctions. Finally, numerical experiments show that the dynamics converges quickly under various metrics.
| Identifer | oai:union.ndltd.org:columbia.edu/oai:academiccommons.columbia.edu:10.7916/h03t-kk89 |
| Date | January 2022 |
| Creators | Gao, Yuan |
| Source Sets | Columbia University |
| Language | English |
| Detected Language | English |
| Type | Theses |
Page generated in 0.0051 seconds