Linear Fisher markets are a fundamental model in theoretical computer science and economics with diverse applications. In the classical case of n buyers and m items, a market equilibrium---a pair of allocations and item prices satisfying buyer optimality and market clearance---can be computed using the Eisenberg-Gale convex programs. Motivated by large-scale Internet advertising and fair division applications, we considered linear Fisher markets with a finite set of buyers and a continuous/measurable item space. We introduced infinite-dimensional generalizations of the well-known (primal and dual) Eisenberg-Gale convex programs. We showed that, under a continuous/measurable item space, a market equilibrium always exists and corresponds to an optimal solution of the convex programs.
Furthermore, we showed that there exists a pure equilibrium allocation, i.e., a (generalized) fair division, if the item space is "continuous", i.e., equipped with a finite, atomless measure. When the item space is a closed interval and buyers have piecewise linear valuations, we showed that the (primal) infinite-dimensional convex program can be reformulated as a compact, finite-dimensional convex conic program, which can be solved efficiently using interior-point optimization software. Based on our convex conic reformulation, we also developed the first polynomial-time cake-cutting algorithm for piecewise linear valuations.
Finally, we showed that the dual convex program leads to a simple, interpretable online fair division algorithm for general buyer valuations as well as the first online algorithm for computing pacing equilibria of repeated first-price auctions.
This talk will conclude with an overview of the speaker ongoing research and future research plans.
About the Speaker
GAO Yuan is a 5th-year PhD candidate in Operations Research (IEOR) at Columbia University. Before that, he graduated from National University of Singapore with a Bachelor’s Degree in Applied Mathematics. Yuan's research focuses on optimization models and methods in the context of game theory, market design, and machine learning. Motivated by real-world applications such as Internet ad auctions and fair resource allocation, Yuan has proposed new models of competitive markets that capture the large-scale or continuous nature of these settings, and developed efficient online and offline optimization methods for computing their respective equilibria. Concurrently with this work, Yuan has also contributed new algorithmic techniques and convergence results for first-order methods in convex optimization.
He is a tenure-track faculty candidate for Artificial Intelligence & Data Science, Intelligent Systems & Optimization cluster.
