RARE: Response-Aware Rational Equilibrium in Pricing Games

Bhaskar Ray Chaudhury, Jugal Garg, Xin Huang, Eklavya SharmaarXiv 2026 · arXiv

TL;DR

This paper introduces Response-Aware Rational Equilibrium (RARE), a new stability notion for pricing games where buyers have fixed budgets. Unlike standard Nash equilibria, which frequently fail to exist in these markets, RARE accounts for the fact that competitors will rationally respond to price changes, providing a more robust and existentially guaranteed framework for market stability.

What Problem Does This Paper Address?

In many modern markets—from physical goods to datasets—buyers operate under strict budget constraints. In these settings, sellers are locked in a fierce competition: every dollar a buyer spends on one good is a dollar unavailable for another.

Standard game theory relies on the Pure Nash Equilibrium (PNE), where no seller wants to change their price assuming everyone else's price stays the same. However, in budget-constrained markets, PNE often simply doesn't exist. A seller might see a "myopic" opportunity to raise prices and capture more revenue, but this gain is often illusory because it harms competitors, who will likely react (e.g., by price-matching) to protect their own interests.

The authors argue that the instability of Nash equilibria in these models stems from ignoring these inevitable counter-responses. They seek a new equilibrium concept that is both practically motivated and mathematically guaranteed to exist.

Methods

The authors propose RARE, where a price vector is considered stable if every possible deviation by a seller can be "deterred" by a rational response from the other sellers.

Key components of the methodology include:

  • Individual Rationality (IR): A response is only valid if no responding seller earns less than they did immediately after the initial deviation. This ensures the response is credible.
  • Market-Share-Restoring Responses: The authors prove existence by showing that responders can often adjust prices to restore their original market shares, thereby neutralizing the deviator's gains.
  • Mathematical Proofs: The existence proofs rely on two nested applications of the KKM lemma (a fixed-point theorem for simplices). They first find a response for a fixed price vector (inner KKM) and then find a price vector where all deviations have such responses (outer KKM).
  • Formal Verification: The core results were formally verified using the Lean 4 proof assistant, ensuring the highest level of mathematical correctness.

Datasets

This is a theoretical paper focused on equilibrium analysis and does not use empirical datasets. The "benchmark" for this work is the formal verification of its theorems in the Lean 4 repository.

Key Insights and Ideas

  • Nash is too rigid: The failure of Nash equilibria in these games isn't a sign of market chaos, but a limitation of the Nash definition itself. Real-world sellers anticipate reactions.
  • Budgets Couple Everything: Even if buyers have simple linear utilities, their finite budgets couple the revenues of all sellers. This makes the pricing game behave similarly to a fixed-sum game when prices are high enough to exhaust budgets.
  • The Power of Price Matching: A simple response like matching a competitor's price increase can often deter that increase in the first place.
Figure 1: The market of Example 1. Each bar shows how a buyer splits her budget between the two goods. If seller 1 raises her price and seller 2 keeps her price fixed, then seller 1 gains. If seller 2 responds by matching seller 1’s new price, then seller 2’s revenue increases and seller 1’s revenue drops back to its original value.
  • Why Individual Rationality Matters: The authors show that requiring responders to gain collectively isn't enough; for a response to be a credible deterrent, each responder must have a reason to participate.
Figure 2: The market with three goods from the paragraph on why each responder must gain. Each bar shows how a buyer splits her budget among the goods, which is also each seller’s revenue per buyer. The response by sellers 1 and 3 eliminates seller 2’s gain and increases the responders’ total revenue, but seller 1’s revenue drops compared to her revenue right after the deviation. Hence, RARE does not allow this response.

Key Results

  • Existence for Rivalrous Goods: For physical goods (where one unit sold to A cannot be sold to B), a RARE always exists under continuous allocation rules.
  • Existence for Non-Rivalrous Goods: For goods like data (which can be copied infinitely), a RARE exists if all buyers have equal budgets.
  • Approximate RARE for Unequal Budgets: In non-rivalrous markets with unequal budgets, the authors prove the existence of a $\kappa$-RARE, where a deviator can increase revenue by at most a factor of $\kappa = b_{avg}/b_{min}$ (the ratio of average to minimum budget).
  • Efficient Dynamics: The paper describes a natural "price-raising" dynamic where sellers iteratively increase prices to their "guaranteed" revenue levels. This process converges to an approximate RARE within $\lfloor B/\delta \rfloor$ rounds, where $B$ is the total market budget.

Limitations and Future Work

  • Exact RARE for Unequal Budgets: The paper leaves open whether an exact RARE always exists for non-rivalrous goods when budgets are unequal.
  • Computational Complexity: While the dynamics converge, the paper does not provide a polynomial-time algorithm for computing the exact "optimal deviation revenue" ($V_j$) in all settings.
  • Broader Game Classes: RARE is defined generally; exploring its application to games beyond pricing (e.g., resource allocation or network games) is a promising future direction.
  • Allocation Rules: The existence results depend on the continuity of the allocation rule (how ties are broken when buyers are indifferent). While the authors identify large classes of continuous rules, exploring more "discrete" tie-breaking remains a challenge. Not discussed in the paper.

Summary updated

Abstract

We study a pricing game in markets with budget-constrained buyers, where each seller offers a single good at a price she sets, and each buyer chooses a utility-maximizing bundle subject to her budget. We consider both the rivalrous setting, such as markets for physical goods, and the non-rivalrous setting, such as markets for datasets. Pure Nash equilibria often fail to exist in this game. However, Nash equilibrium assumes that the other sellers keep their prices fixed when one seller deviates, whereas in practice, sellers harmed by a price change may respond, for example, by matching the new price. We propose a new equilibrium notion called Response-Aware Rational Equilibrium (RARE). At a RARE, every deviation by a seller can be deterred by a response from the other sellers, in which no responder earns less than she did right after the deviation. Every Nash equilibrium is a RARE. Assuming that buyers' purchases (among their optimal choices) change continuously with prices, we show that a RARE always exists for rivalrous goods, and for non-rivalrous goods when buyers have equal budgets. Moreover, the RARE that we construct extracts the buyers' entire budget. For non-rivalrous goods with unequal budgets, we show that an approximate RARE exists, where a deviating seller can increase her revenue by a factor of at most $b_{\mathrm{avg}}/b_{\min}$, the ratio of the average budget to the minimum budget. Our proof uses two nested applications of the KKM lemma. We also study a natural dynamic in which sellers repeatedly raise their prices to earn the revenue that they could guarantee themselves by deviating, and show that it reaches an approximate RARE, with additive error $δ$, within $\lfloor B/δ\rfloor$ rounds, where $B$ is the buyers' total budget. The main results of this paper are formally verified in the Lean 4 proof assistant (https://github.com/sharmaeklavya2/dm-rare).
BibTeX
@misc{chaudhury2026rare,
  author = {Bhaskar Ray Chaudhury and Jugal Garg and Xin Huang and Eklavya Sharma},
  title = {{RARE: Response-Aware Rational Equilibrium in Pricing Games}},
  year = {2026},
  eprint = {2610.38897},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.38897},
}
Figure