Abstract
Fisher markets are a fundamental model for understanding fair and efficient resource allocation. Traditional full-gradient optimization methods for computing market equilibria scale poorly, requiring $O(nm)$ operations per step for $n$ buyers and $m$ items. We present two stochastic block-coordinate algorithms—BCDEG and BCPR—that update the market state incrementally by focusing on individual items or buyers. These methods significantly outperform deterministic state-of-the-art algorithms in convergence speed and correspond to interpretable economic dynamics like price-setting and budget adjustments. Experimental results on synthetic and real-world datasets demonstrate the superior efficiency of these approaches, especially when combined with adaptive line search.
1. Introduction
In algorithmic game theory, the Fisher Market model is essential for understanding how resources are allocated fairly. Finding the "market equilibrium" (ME)—the set of prices and allocations where supply perfectly meets demand—is a critical computational challenge. As markets grow to include millions of buyers and items, traditional full-gradient methods become computationally prohibitive. This paper proposes a shift toward block-coordinate updates to achieve both speed and interpretability.
2. Methodology
We leverage block-coordinate descent (BCD) to reduce the per-iteration computational cost. Instead of updating the entire allocation matrix simultaneously, we update a single "block" at a time:
- BCDEG (Block Coordinate Descent on Eisenberg-Gale): This method updates the allocation of a single item across all buyers in each iteration.
- BCPR (Block Coordinate Proportional Response): This method updates the bids of a single buyer across all items.
By focusing on one item or buyer, the work per iteration is reduced from $O(nm)$ to $O(n)$ or $O(m)$. Furthermore, we introduce Line Search (LS) variants for both algorithms. These adaptive methods dynamically test for larger step sizes, which drastically speeds up convergence in practice.
3. Economic Interpretation
A significant insight of this work is that the mathematical updates of BCDEG are equivalent to a tâtonnement-style pricing dynamic. Specifically, the projection step in the algorithm is mathematically identical to finding a market-clearing price for a single item given current buyer demands. This provides a clear economic narrative for the algorithm's behavior, mapping optimization steps to real-world market dynamics.
4. Experimental Results
The algorithms were evaluated on three types of data: simulated low-rank instances, real-world movie rating data from MovieTweetings, and complex Constant Elasticity of Substitution (CES) utility instances.
4.1 Performance Analysis
Across all datasets, the block-coordinate methods consistently outperformed previous state-of-the-art methods like Projected Gradient with Line Search (PGLS).
As seen in Figure 1, the line search variants (BCDEG-LS and BCPR-LS) were the clear winners, achieving better early-stage performance and maintaining their lead as precision requirements increased.
In Figure 2, the efficiency gains are further demonstrated on real-world data. While stochastic methods may require more iterations, their significantly lower cost per iteration allows them to reach high-precision solutions much faster than full-information algorithms. For more complex CES utilities, while vanilla Proportional Response (PR) is surprisingly fast, the block-coordinate framework remains a robust alternative.
5. Conclusion
By decomposing massive optimization problems into economically meaningful chunks, this research provides a faster and more interpretable way to find balance in complex markets. Future research directions include extending these algorithms to distributed systems for Internet-scale markets and establishing formal convergence proofs for the adaptive BCPR variant.
Summary updated