Speaker: Prof. Yinyu Ye, Stanford University

Time: 14:00 p.m., March 31, 2024, GMT+8

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})$. 

Source: Center on Frontiers of Computing Studies, PKU