静5杰出讲座 | Online Equilibrium Pricing

关键词：杰出讲座系列

Online Equilibrium Pricing for Stochastic Fisher Markets

报告人

Yinyu Ye

K. T. Li Professor of Engineering

Stanford University

时  间

2023年3月31日 星期五 14:00

地  点

静园五院204

Host

邓小铁 教授

 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   , where    is the number of agents and the good capacities scale as   . 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    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   .  

 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 ISMPTseng 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 Computing Society Prize, the INFORMS Optimization Prize for Young Researchers. According to Google Scholar, his publications have been cited 52,000 times.

杰 出 讲 座 系 列

—   版权声明  —

本微信公众号所有内容，由北京大学前沿计算研究中心微信自身创作、收集的文字、图片和音视频资料，版权属北京大学前沿计算研究中心微信所有；从公开渠道收集、整理及授权转载的文字、图片和音视频资料，版权属原作者。本公众号内容原作者如不愿意在本号刊登内容，请及时通知本号，予以删除。

点“阅读原文”转报告海报