Online Equilibrium Pricing for Stochastic Fisher Markets
- Prof. Yinyu Ye, Stanford University
- Time: 2023-03-31 14:00
- Host: Prof. Xiaotie Deng
- Venue: Room 204, Courtyard No.5, Jingyuan
Abstract
In a static Fisher market, agents (customers) spend a budget of (artificial) currency to buy goods that maximize their utilities while a central planner sets prices on capacity-constrained goods such that the market clears. However, the efficacy of pricing schemes in achieving an exact equilibrium outcome in Fisher markets relies on complete knowledge of agents' budgets and utility functions and requires that transactions happen when all agents are present simultaneously. Motivated by these practical considerations, in this work, we study an online variant of stochastic Fisher markets, wherein budget-constrained agents with privately known utility and budget parameters, drawn i.i.d. from an unknown distribution D, enter the market sequentially. In this setting, we develop an online algorithm that adjusts post-prices solely based on observations of agent consumption, i.e., revealed preference feedback, and achieves a regret and capacity violation of $O(\sqrt{n})$, where $n$ is the number of agents and the good capacities scale as $O(n)$. Here, our regret measure is the optimality gap in the objective of the Eisenberg-Gale program between an online algorithm and an offline oracle with complete information on agents' budgets and utilities. Furthermore, if a discrete distribution D is known, we develop an adaptive variant of online equilibrium pricing achieves $O(\log(n))$ regret and constant capacity violation. On the other hand, we show that any static pricing algorithm, including one that sets expected equilibrium prices with complete knowledge of the distribution D, cannot achieve both a regret and constraint violation of less than $\Omega(\sqrt{n})$.
Biography
Yinyu Ye is currently the K.T. Li Professor of Engineering at Department of Management Science and Engineering and Institute of Computational and Mathematical Engineering, Stanford University. He received the B.S. degree in System Engineering from the Huazhong University of Science and Technology, China, and the M.S. and Ph.D. degrees in Engineering-Economic Systems and Operations Research from Stanford University. His current research interests include Continuous and Discrete Optimization, Data Science and Applications, Computational Algorithm Design and Analyses, Algorithmic Game/Market Equilibrium; and he was one of the pioneers of Interior-Point Methods, Conic Linear Programming, Distributionally Robust Optimization, Online Linear Programming, Algorithm Analyses for Reinforcement Learning and Markov Decision Process, and etc. He has received several academic awards including: the inaugural 2006 Farkas Prize on Optimization, the 2009 IBM Faculty Award, the 2009 John von Neumann Theory Prize for fundamental sustained contributions to theory in Operations Research and the Management Sciences, the inaugural 2012 ISMP Tseng Lectureship Prize for outstanding contribution to continuous optimization (every three years), the winner of the 2014 SIAM Optimization Prize awarded (every three years), the 2015 SPS Signal Processing Magazine Best Paper Award, etc.. He has supervised numerous doctoral students at Stanford who received various prizes such as INFORMS Nicholson Prize, Student Paper Competition, the INFORMS Combputing Society Prize, the INFORMS Optimization Prize for Young Researchers. According to Google Scholar, his publications have been cited 52,000 times.