Fisher markets with linear constraints: Equilibrium properties and efficient distributed algorithms

• 成果类型: Article
• 署名作者: Jalota, Devansh; Pavone, Marco; Qi, Qi; Ye, Yinyu
• 署名单位: Stanford University; Renmin University of China
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2023.06.007
• 发表日期: 2023
• 页码: 223-260
• 关键词: Fisher market; Market equilibrium; resource allocation; Distributed algorithms

摘要

The Fisher market is one of the most fundamental models for resource allocation. However, Fisher markets are less amenable for resource allocation settings when agents have additional linear constraints beyond the budget constraints of buyers and the capacity constraints of goods. Thus, in this work, we introduce a modified Fisher market, where agents may have additional linear constraints, and study the properties of the resulting equilibria. To set equilibrium prices, we introduce a budget-adjusted social optimization problem (BA-SOP), whose optimal dual variables correspond to the equilibrium prices. 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. Our ADMM approach has strong convergence guarantees and provides a general-purpose method for computing market equilibria for Fisher markets with homogeneous linear constraints and classical Fisher markets. & COPY; 2023 Published by Elsevier Inc.