Walrasian Dynamics in Multi-Unit Markets.

Simina Brânzei, Aris Filos-RatsikasAAAI 2019 · OpenReview

Abstract

In a multi-unit market, a seller brings multiple units of a good and tries to sell them to a set of buyers that have monetary endowments. While a Walrasian equilibrium does not always exist in this model, natural relaxations of the concept that retain its desirable fairness properties do exist. We study the dynamics of (Walrasian) envy-free pricing mechanisms in this environment, showing that for any such pricing mechanism, the best response dynamic starting from truth-telling converges to a pure Nash equilibrium with small loss in revenue and welfare. Moreover, we generalize these bounds to capture all the (reasonable) Nash equilibria for a large class of (monotone) pricing mechanisms. We also identify a natural mechanism, which selects the minimum Walrasian envy-free price, in which for $n=2$ buyers the best response dynamic converges from any starting profile. We conjecture convergence of the mechanism for any number of buyers and provide simulation results to support our conjecture.

Introduction

In online multi-unit markets where buyers have fixed budgets, the stability of prices and allocations under repeated strategic updates is a critical concern. This paper investigates whether "envy-free" pricing mechanisms—where every buyer receives their preferred allocation at the given price without envying others—can lead to stable outcomes when buyers iteratively update their bids through best-response dynamics.

The central question is whether these dynamics converge to a Nash equilibrium and what the resulting impact is on social welfare and seller revenue. While strategic behavior often complicates market efficiency, this work demonstrates that under specific conditions, stability is guaranteed with minimal performance loss.

Methodology

The authors model a market consisting of one seller with $m$ identical units and $n$ buyers, each possessing a private valuation and a known budget. The analysis focuses on the trajectory of market prices and buyer utilities during iterative best-response updates.

A key theoretical approach involves proving that starting from a "truth-telling" profile (where initial bids equal true valuations), the price monotonically decreases until a pure Nash equilibrium is reached. To evaluate equilibrium quality, the authors introduce the "budget share" metric ($\alpha$), representing the maximum fraction of total revenue contributed by a single buyer.

Empirical validation was conducted through synthetic simulations. Market profiles were generated with $n=25$ buyers and $m=20$ items, with budgets drawn uniformly from ranges such as $[1, 50]$ and $[1, 125]$.

Theoretical Results

Convergence from Truth-Telling

The study proves that for any envy-free pricing mechanism, best-response dynamics starting from truth-telling are guaranteed to converge to a pure Nash equilibrium. This occurs because strategic improvements for buyers typically involve driving the unit price downward. Since the price is bounded below by zero, the process must terminate.

Welfare and Revenue Guarantees

At equilibrium, buyers generally achieve weakly higher utility and more items compared to truthful reporting. Furthermore, the seller's revenue loss is bounded: the revenue at equilibrium is at least $\frac{1}{2}(\beta - \alpha)$ of the optimal revenue, where $\beta$ is a baseline efficiency constant. In highly competitive markets where $\alpha \to 0$, the seller retains at least half of the optimal revenue.

Convergence Speed

While worst-case convergence can be slow ($\Omega(1/\epsilon)$), a specific class of "consistent" mechanisms is shown to converge in at most $n$ steps, where $n$ is the number of buyers.

The ALL-OR-NOTHING Mechanism and Empirical Stability

A significant finding is the robustness of the "ALL-OR-NOTHING" (AON) mechanism, which selects the minimum Walrasian envy-free price. This mechanism allocates items fully to buyers valuing them above the price and distributes remaining units to those whose valuations match the price. Unlike other mechanisms that may cycle endlessly from arbitrary (non-truthful) starting points, AON demonstrates remarkable stability in practice.

Simulation of the ALL-OR-NOTHING (AON) mechanism showing price convergence from arbitrary initial profiles across different market settings.

Simulations involving 25 buyers and 20 items showed that the AON mechanism converged to a Nash equilibrium in 100% of cases across 100 random starting profiles, even when those profiles were not truthful. As shown in the simulation results, prices stabilize within approximately 40 steps regardless of the initial starting price.

Conclusion and Future Work

The research establishes that envy-free pricing mechanisms provide a stable and relatively efficient framework for multi-unit markets under best-response dynamics. While convergence from truth-telling is theoretically sound, the AON mechanism shows promise for even broader stability.

The authors have mathematically proven that the AON mechanism converges from any starting profile for $n=2$ buyers. They conjecture that this property holds for any number of buyers, a hypothesis supported by their empirical simulations. Proving this conjecture remains an open challenge for the algorithmic mechanism design community.

Summary updated

Abstract

In a multi-unit market, a seller brings multiple units of a good and tries to sell them to a set of buyers that have monetary endowments. While a Walrasian equilibrium does not always exist in this model, natural relaxations of the concept that retain its desirable fairness properties do exist. We study the dynamics of (Walrasian) envy-free pricing mechanisms in this environment, showing that for any such pricing mechanism, the best response dynamic starting from truth-telling converges to a pure Nash equilibrium with small loss in revenue and welfare. Moreover, we generalize these bounds to capture all the (reasonable) Nash equilibria for a large class of (monotone) pricing mechanisms. We also identify a natural mechanism, which selects the minimum Walrasian envy-free price, in which for n=2 buyers the best response dynamic converges from any starting profile. We conjecture convergence of the mechanism for any number of buyers and provide simulation results to support our conjecture.
BibTeX
@inproceedings{branzei2019walrasian,
  author = {Simina Brânzei and Aris Filos-Ratsikas},
  title = {{Walrasian Dynamics in Multi-Unit Markets.}},
  booktitle = {AAAI},
  year = {2019},
  url = {https://openreview.net/forum?id=HQYbfWMe_TS},
}
Figure