Beyond Classical Fisher Markets: Nonconvexities and Online Allocations

The Fisher market is one of the most fundamental models for resource allocation. However, classical Fisher markets (i) only consider two types of constraints, i.e., budgets of individual buyers and capacities of goods, and (ii) involve a complete information setting wherein buyers' utilities are known, and all the transactions happen in a static market. In this talk, we present generalizations of classical Fisher markets to settings when agents have additional linear constraints and when buyers arrive at the market sequentially with utilities and budgets that are not known a priori to the market designer.

We first introduce Fisher markets with additional linear constraints and study the properties of the resulting equilibria. Notably, the addition of linear constraints introduces non-convexities into Fisher markets as the equilibrium price set may be non-convex, and computing equilibria is, in general, PPAD-hard. Yet, to set equilibrium prices, we introduce a budget-adjusted social optimization problem (BA-SOP), whose optimal dual variables correspond to the equilibrium prices. Further, since solving BA-SOP can be computationally intensive and requires centralized knowledge of all agents' utilities, we propose a new class of distributed algorithms based on the Alternating Direction Method of Multipliers (ADMM) to compute equilibrium prices.

Next, we extend the above-mentioned distributed implementation to the online setting when agents arrive sequentially at the market with privately known utility and budget parameters drawn i.i.d. from some distribution. In this setting, we study the performance limitations of static pricing approaches, which set the same prices for all users, and develop two adaptive pricing algorithms, one with knowledge of the distribution and another that solely relies on past observations of user consumption, i.e., revealed preference feedback, with improved performance guarantees. 

Please report video problems to itsupport@slmath.org.

See more of our Streaming videos on our main VMath Videos page.