Fisher markets with linear constraints: Equilibrium properties and efficient 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.

Automated summary

This paper introduces a modified Fisher market model where agents may have additional linear constraints, and studies the properties of the resulting equilibria. To determine equilibrium prices, a budget-adjusted social optimization problem (BA-SOP) is introduced, whose optimal dual variables correspond to the equilibrium prices. To address the computational intensity and centralized knowledge requirement, a new class of distributed algorithms based on the Alternating Direction Method of Multipliers (ADMM) is proposed for computing equilibrium prices. The ADMM approach provides strong convergence guarantees and a general-purpose method for computing market equilibria for Fisher markets with homogeneous linear constraints and classical Fisher markets.