← All papers
First page of RARE: Response-Aware Rational Equilibrium in Pricing Games

RARE: Response-Aware Rational Equilibrium in Pricing Games

Bhaskar Ray Chaudhury, Jugal Garg, Xin Huang, Eklavya Sharma

cs.GT Oct 28, 2026 · v1
The main results (RARE existence, convergence of dynamics, Nash non-existence) are formally verified in Lean 4, with proofs generated using Claude.
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).

Pure Nash equilibria often fail to exist in pricing games where budget-constrained buyers buy rivalrous or non-rivalrous goods. Nash's deviation test assumes competitors keep their prices fixed, ignoring that they may respond to a price change.

The authors define Response-Aware Rational Equilibrium (RARE): a price vector is stable if every seller deviation can be deterred by an individually rational response from the other sellers. Existence is proved with two nested applications of the KKM lemma. They also analyze a price-raising dynamic. The main results were formalized in Lean 4, with proofs generated using Claude.

Under continuous allocation rules, a RARE exists for rivalrous goods, and for non-rivalrous goods when budgets are equal. With unequal budgets, a b_avg/b_min-approximate RARE exists. The dynamic reaches a δ-additive approximate RARE within ⌊B/δ⌋ rounds.

Marketνβκ = B/(νβ)
Rivalrous1B1
Non-rivalrousnb_minb_avg/b_min
Parameters for the rivalrous and non-rivalrous settings