Fast and Interpretable Dynamics for Fisher Markets via Block-Coordinate Updates

Tianlong Nan, Yuan Gao, Christian Kroer

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

Performance on simulated low-rank instances. The stochastic BCDEG and BCPR methods (solid lines) reach lower duality gaps significantly faster than their deterministic counterparts.

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.

Performance on real-world movie rating data. The block-coordinate methods show a significant advantage in computational efficiency over full-gradient approaches.

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

BibTeX
@inproceedings{nan2023fast,
  author = {Tianlong Nan and Yuan Gao and Christian Kroer},
  title = {{Fast and Interpretable Dynamics for Fisher Markets via Block-Coordinate Updates}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.1609/aaai.v37i5.25723},
}
Figure