Last-Iterate Convergence in No-Regret Learning: Games with Reference Effects Under Logit Demand

This work examines the behaviors of the online projected gradient ascent (OPGA) algorithm and its variant in a repeated oligopoly price competition under reference effects. In particular, we consider that multiple firms engage in a multiperiod price competition, where consecutive periods are linked by the reference price update and each firm has access only to its own first-order feedback. Consumers assess their willingness to pay by comparing the current price against the memory-based reference price, and their choices follow the multinomial logit (MNL) model. We use the notion of stationary Nash equilibrium (SNE), defined as the fixed point of the equilibrium pricing policy, to simultaneously capture the long-run equilibrium and stability. We first study the loss-neutral reference effects and show that if the firms employ the OPGA algorithm—adjusting the price using the first-order derivatives of their log-revenues—the price and reference price paths attain last-iterate convergence to the unique SNE, thereby guaranteeing the no-regret learning and market stability. Moreover, with appropriate step-sizes, we prove that this algorithm exhibits a convergence rate of $\tilde{\mathcal{O}}(1/t^2)$ in terms of the squared distance and achieves a constant dynamic regret. Despite the simplicity of the algorithm, its convergence analysis is challenging due to the model lacking typical properties such as strong monotonicity and variational stability that are ordinarily used for the convergence analysis of online games. The inherent asymmetry nature of reference effects motivates the exploration beyond loss-neutrality. When loss-averse reference effects are introduced, we propose a variant of the original algorithm named the conservative-OPGA (C-OPGA) to handle the nonsmooth revenue functions and show that the price and reference price achieve last-iterate convergence to the set of SNEs with the rate of $\mathcal{O}(1/\sqrt{t})$. Finally, we demonstrate the practicality and robustness of OPGA and C-OPGA by theoretically showing that these algorithms can also adapt to firm-differentiated step-sizes and inexact gradients.

This paper was accepted by Chung Piaw Teo, optimization and decision analytics.

Funding: J. Lavaei acknowledges the support from the U.S. Army Research Laboratory and the U.S. Army Research Office under Grant W911NF2010219, Office of Naval Research under Grant N000142412673, AFOSR, NSF, and the UC Noyce Initiative.

Supplemental Material: The online appendix and data files are available at https://doi.org/10.1287/mnsc.2023.03464.