No-Regret Learning in Dynamic Competition with Reference Effects Under Logit Demand
Authors: Mengzi Amy Guo
Donghao Ying
Javad Lavaei
Zuo-Jun Shen
Venue: NeurIPS 2023 poster (2023)
Keywords: no-regret learning
price competition
reference effect
last-iterate convergence
TL;DR: This work is dedicated to the algorithm design in a competitive framework, with the primary goal of learning a stable equilibrium.

Abstract: This work is dedicated to the algorithm design in a competitive framework, with the primary goal of learning a stable equilibrium. We consider the dynamic price competition between two firms operating within an opaque marketplace, where each firm lacks information about its competitor. The demand follows the multinomial logit (MNL) choice model, which depends on the consumers' observed price and their reference price, and consecutive periods in the repeated games are connected by reference price updates. We use the notion of stationary Nash equilibrium (SNE), defined as the fixed point of the equilibrium pricing policy for the single-period game, to simultaneously capture the long-run market equilibrium and stability. We propose the online projected gradient ascent algorithm (OPGA), where the firms adjust prices using the first-order derivatives of their log-revenues that can be obtained from the market feedback mechanism. Despite the absence of typical properties required for the convergence of online games, such as strong monotonicity and variational stability, we demonstrate that under diminishing step-sizes, the price and reference price paths generated by OPGA converge to the unique SNE, thereby achieving the no-regret learning and a stable market. Moreover, with appropriate step-sizes, we prove that this convergence exhibits a rate of $\mathcal{O}(1/t)$.

No-Regret Learning in Dynamic Competition with Reference Effects Under Logit Demand
Mengzi Amy Guo IEOR Department
Donghao Ying IEOR Department UC Berkeley donghaoy@berkeleeyyoo edu
Javad Lavaei IEOR Department UC Berkeley
UC Berkeley
mengzii_guooberkkeeeyy.ee
lavaei wwerkeleyycccooo. edu
Zuo-Jun Max Shen
IEOR Department UC Berkeley maxshen@berkeley.co edu
Abstract
This work is dedicated the algorithm design competitive framework, with the primary goal of learning stable equilibrium. We consider the dynamic price competition between two firms operating within an opaque marketplace, where each firm lacks information about its competitor. The demand follows the multinomial logit (MNL)) choice model, which depends on the consumers' observed price and their reference price, and consecutive periods in the repeated games are connected by reference price updates. We use the notion of stationary Nash equilibrium (SNE), defined as the fixed point of the equilibrium pricing policy for the single-period game, to simultaneously capture the long-run market equilibrium and stability. We propose the online projected gradient ascent algorithm (OPGA), where the firms adjust prices using the first-order derivatives their log legerevesees that be obtained from the market feedback mechanism. Despite the absence of typical properties required for the convergence online games, such strong monotonicity and variational stability. we demonstrate that under diminishing step-sizes, the price and reference price paths generated by OPGA converge the unique SNE, thereby achieving the no-regret learning and stable market. Moreover, with appropriate step-sizes, we prove that this convergence exhibits rate of (11tt).
Introduction
The memory-based reference effect is well-studied strategic consumer behavior in marketing and economics literature, which refers to the phenomenon that consumers shape their price expectations (known reference prices) based the past encounters and then them to judge the current price (see I for a review). A substantial body of empirical research has shown that the current demand is significantly influenced by the historical prices through reference effects (see, e.g., 2 4 5l). Driven by the ubiquitous evidence, many studies have investigated various pricing strategies in the presence of reference effects 66. 7 8 g
However, the aforementioned works have all focused on the case with a monopolistic seller, leaving the understanding of how the reference effect functions in competition relatively limited compared its practical importance. This issue becomes even more pronounced with the surge of e-commerce, as the increased availability of information incentivizes consumers to make comparisons among different retailers.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Moreover, we notice that in competitive markets, the pricing problem with reference effects is further complicated by the lack of transparency, where firms are cautious about revealing confidential information to their rivals. Although the rise of digital markets greatly accelerates data transmission and promotes the information transparency, which is generally considered beneficial because of the improvement in marketplace efficiency [10], many firms remain hesitant to fully embrace such transparency for fear of losing their informational advantages. This concern is well-founded in the literature, for example the work TT demonstrates that dealers with lower transparency levels generate higher profits than their more transparent counterparts, and 12] highlights that in reverse auctions, transparency typically enables buyers to drive the price down to the firm's 's marginal cost. Hence, as recommended by [3],, companies should focus on the strategic and selective disclosure of information to enhance their competitive edge, rather than pursuing complete transparency.
Inspired by these real-world practices, this article, we study the duopoly competition with reference effects in an opaque market, where each firm has access to its own information but does not possess any knowledge about its competitor, including their price, reference price, and demand. The consumer demand follows the multinomial logit (MNL) choice model, which naturally reflects the cross-prodee prosspp effects among substitutes. Furthermore, given the intertemporal characteristic of the memory-based reference effect, we consider the game in a dynamic framework, i.e., the firms engage in repeated competitions with consecutive periods linked by reference price updates. In this setting, it is natural to question whether the firms can achieve some notion of stable equilibrium by employing common online learning algorithmss to sequentially set their prices. A vast majority of the literature on online games with incomplete information targets the problem of finding no-regret algorithms that can direct agents toward a Nash equilibrium, a stable state at which the agents have no incentive to revise their actions (see, e.g.. 11 15 16). Yet, the Nash equilibrium alone is inadequate to determine the stable state for our problem of interest, given the evolution of reference prices. For instance, even if an equilibrium price is reached in one period, the reference price update makes it highly probable that the firms will deviate from this equilibrium in subsequent periods. As a result, to jointly capture the market equilibrium and stability, we consider the concept of stationary Nash equilibrium (SNE), defined as the fixed point of the equilibrium pricing policy for the single-period game. Attaining this long-tern long-term market stability is especially appealing for firms market fosters favorable conditions for implementing efficient planning strategies and facilitating upstream operations in supply chain management
competitive environment, as stable
[17. In contrast, fluctuating demands necessitate
more carefully crafted strategies for effective logistics management [8] 19. 10.
The concept of SNE has also been investigated in 21 and (22). Specifically, 21 examines the long-run market behavior in a duopoly competition with linear demand and a common reference price for both products. However, compared the MNL demand in our work, linear demand models On the other reference price formulation; yet, their analysis of long-term market dynamics relies on complete information and is inapplicable to an opaque market. In contrast, our work accommodates both the partial information setting and MNL choice model. We summarize our main contributions below:
generally fall short in addressing interdependence among multiple products [4] 23 24
hand, (22) adopts the MNL demand with product-speciffs
1. Formulation. We introduce duopoly competition framework with an opaque market setup that takes into account both cross-period and cross- pposscp effects through consumer reference effects and the MNL choice model. We use the notion of stationary Nash equilibrium (SNE) to simultaneously depict the equilibrium price and market stability.
2. Algorithm and convergence. We propose a no-regret algorithm, namely the Online Projected Gradient Ascent (OPGA), where each firm adjusts its posted price using the first-order derivative of its log-revenue. When the firms execute OPGA with diminishing step-sizes, we show that their prices and reference prices converge to the unique SNE, leading the long-run market equilibrium and stability. Furthermore, when the step-sizes decrease appropriately in the order of ((1/t), we demonstrate that the prices and reference prices converge
rate of O(1/t).
3. Analysis. We propose a novel analysis for the convergence of OPGA by exploiting characteristic properties of the MNL demand model. General convergence results for online games typically require restrictive assumptions such as strong monotonicity [25]
14 [6 or variational stability
[26] 15 27 28 as well as the convexity of the loss function [29 30 However, our problem lacks
these favorable properties, rendering the existing techniques inapplicable. Additionally, compared to standard games where the underlying environment static, the reference price evolution in this work further perplexes the convergence analysis.

---

4. Managerial insights. Our study illuminates a common issue in practice, where the firms are willing to cooperate but are reluctant to divulge their information to others. The OPGA algorithm can help address this issue by guiding the firms to achieve the SNE as if they had perfect information, while still preserving their privacy.
2 Related literature
Our work on the dynamic competition with reference effects in an opaque market is related to the several streams of literature.
Modeling of reference effeet. The concept of reference effeets can be traced back to the adaptation- level theory proposed by [3I], which states that consumers evaluate prices against the level they have adapted to. Extensive research has been dedicated to the formulation of reference effects in the marketing literature, where two mainstream models emerge: memory-based reference price and stimulus-basee based reference price [4] The memory-based reference model, also known the internal reference price, leverages historical prices to form the benchmark (see, e.g., [ 32 5)). On the contrary, the stimulus-baseds reference model, the external reference price, asserts that the price judgment is established at the moment of purchase utilizing current external information such as the prices of substitutable products, rather than drawing on past memories (see, e.g.. to the comparative analysis by [. among different reference models, the memory-base model that relies on a product's own historical prices offers the best fit and strongest predictive power in multi-produs settings. Hence, our paper adopts this type of reference model, referred to as the brand-specifie past prices formulation in 4
33 2). According
Dynamic pricing in monopolist market with reference effect. The research on reference effects has recently garnered increasing attention in the field of operations research, particularly in monopolist pricing problems. As memory-based reference effect models give rise to the intertemporal nature, the price optimization problem is usually formulated as a dynamic program. Similar to our work, their objectives typically involve determining the long-run market stability under the optimal or heuristic pricing strategies. The classic studies by 77) and ( show that in either discrete- or continuous- sartinuous-timeeeee framework, the optimal pricing policy converges and leads to market stabilization under both loss-neutral and loss-averse reference effects. More recent research on reference effects primarily concentrates on the piecewise linear demand in single- pegle--poductttt contexts and delves into more comprehensive characterizations of myopic and optimal pricing policies (see. e.g., 34] Deviating from the linear demand, (9] and 24 employ the logit demand and analyze the long-term market behaviors under the optimal pricing policy, where the former emphasizes on consumer heterogeneity and the later innovates in the multi-produc setting.
While the common assumption in the aforementioned studies is that the firm knows the demand function, another line of research tackles the problem under uncertain demand, where they couple monopolistic dynamic pricing with reference effects and online demand learning [35] Although these works include an online learning component, our paper distinguishes itself from them in two aspects. Firstly. the uncertainty that needs to be learned is situated in different areas. The works by (35) and [36] assume that the seller recognizes the structure of the demand function (i.c., linear demand) but requires to estimate the model's responsiveness parameters. By contrast, in our competitive framework, the firms are aware of their own demands but lack knowledge about their rivals that should be learned. Secondly, the objectives of [35 and (36) are design algorithms to boost the total revenues from monopolist perspective, whereas our algorithm aims to guide firms to reach Nash equilibrium and market stability concurrently.
Price competition with reference effects. Our work is pertinent to the studies on price competition
with reference effects (37 38 39 22 In particular. (38) is concerned with single-period price competitions under various reference price formulations. The paper [37] expands the scope to a dynamic competition with symmetric reference effects and linear demand, though their theoretical analysis on unique subgame perfect Nash equilibrium is confined to two-period horizon. The more recent work (39] further extends the game to the multi-stage setting, where they obtain the Markov perfect equilibrium for consumers who are either loss-averse or loss-neutral. Nonetheless, unlike the discrete-time framework in 37 and this paper, (39 employs the continuous-time framework, which significantly differs from its discrete-time counterpart in terms of analytical techniques. The recent article [22] also studies the long-run market behavior and bears similarity to our work in model formulations. However, crucial difference exists: 22 assumes transparent market setting,
3

---

whereas we consider the more realistic scenario where the market is opaque and firms cannot access information of their competitors.
More closely related to our work, the work 21 also looks into the long-run market stability of the duopoly price competition in an opaque marketplace. However, there are two notable differences between our paper and theirs. The key distinction lies in the selection of demand function. We favor the logit demand over the linear demand used in (21). as the logit demand exhibits superior performance in the presence of reference effects 223 91. However, the logit model imposes challenges for convergence result since a crucial part of the analysis in 21 hinges on the demand linearity [21 Lemma 9. 9.1], which is not satisfied by the logit demand. Second, [2]] assumes uniform reference price for both products, whereas we consider the product-specific reference price, which has the best empirical performance as illustrated in A These adaptations, even though beneficial to the expressiveness and flexibility of the model, render the convergence analysis [1] not generalizable to our setting.
General convergence results for online games. Our paper closely related to the study of online games, where a typical research question is whether online learning algorithms can achieve the Nash equilibrium for multiple agents who aim minimize their local loss functions. In this section, we review a few recent works in this field. For games with continuous actions, 14 and [40] show that the online mirror descent converges to the Nash equilibrium in strongly monotone games. The work [16] further relaxes the strong monotonicity assumption and examines the last-iterate convergence for games with unconstrained action sets that satisfy the so-called "cocoercive" condition. In addition. [26 and [15] establish the convergence of the dual averaging method under more general condition called global variational stability, which encompasses the cocoercive condition as a subcase. More recently, [1 27 28 demonstrate that extra- satra-gradient approaches, such as the optimistic gradient method, can achieve faster convergence to the Nash equilibrium in monotone and variationally stable games. We point out that in the cited literature above, either the assumption itself implies the convexity of the local loss function such as the strong monotonicity or the convergence to the Nash equilibrium additionally requires the loss function to be convex. By contrast, in our problem, the revenue function of each firm is not concave in its price and does not satisfy either of the properties listed above. Additionally, incorporating the reference effect further complicates the amalysis, the standard notion of Nash equilibrium is insufficient to characterize convergence due to the dynamic nature of reference price.
3
Problem formulation
3.1 MNL demand model with reference effects
We study duopoly price competition with reference price effects, where two firms each offer substitutable product, labeled as H and L,, respectively. Both firms set prices simultaneously in each period throughout an infinite-time horizon. To accommodate the interaction between the two products, we employ a multinomial logit (MNL) model, which inherently captures such cross-product effects. The consumers' utility at period which depends on the posted price pt and reference price rf, is defined as:
U. (pi,r!) u, rp).r!) + 4 a, - +
(ri-p)) + Vi (H,
(1)
where u,(pi, r!) is the deterministic component, and (at, b,, ci) are the given parameters. In addition, the notation of denotes the random fluctuation following the i.i.d. standard Gumbel distribution. According to the random utility maximization theory 42 the demand/market share at period with the posted price p' (P' pL)
and reference price r' (rl, r1) for product i {H. L.) is given by
exp (up(p))()))
di (p'p' d, (1/ (p..pL.) (ri,
+ exp (u. r2) exp (F,,
where the subseript -i denotes the other product besides product i. Consequently, the expected revenue for each firm/product at period can be expressed
[p' r²) = (1, (r) ()) pt d'(p'r Vie (H,
The interpretation of parameters (a,, by c4) in Fq. 1 as follows. For product i E (H, I.), a; refers to product's ' intrinsic value. b; represents consumers' responsiveness to price, also known price

---

sensitivity, and corresponds to the reference price sensitivity, When the offered price exceeds the internal reference price (r² < pt), consumers perceive it as a loss or surcharge, whereas the price below this reference price (r) > p{) is regarded as a gain or discount. These sensitivity parameters are assumed to be positive, i.e., bi. C4 > for E {H. L.J. which aligns with consumer behaviors towards substitutable products and has been widely adopted in similar pricing problems (see, e.g.. 34, 8 21, (21). Precisely, this assumption guarantees that an increase in P would result in a lower consumer utiliiyy for product i, which in turn reduces its demand di (p',, r²) and increases the demand of the competing product (p, r'). Conversely, a rise in the reference price r increases the utility for product i, consequently influencing the consumer demands in the opposite direction.
We stipulate the feasible range for price and reference price to be P [p. Fl. where p. > denote the price lower bound and upper bound, respectively. This boundedness of prices is in accordance with real-world price floors or price ceilings, whose validity is further reinforced by its frequent use in the literature on price optimization with reference effects (see, e.g.,
21
We formulate the reference price using the brand-specific past prices (PASTBRSP) model proposed by [4) which posits that the reference price is product-specific and memory-based. This model is preferred over other reference price models evaluated in 4 as it exhibits superior performance in terms of fit and prediction. In particular, the reference price for product is constructed by applying exponential smoothing to its own historical prices, where the memory parameter a E [0. 1] governs the rate at which the reference price evolves. Starting with an initial reference price ro. the reference price update for each product at period can be described as
+ ++ a - rf + (1 - a) pi: (H, 12 0.
The exponential smoothing technique is among the most prevalent and empirically substantiated
reference price update mechanism in the existing literature (see, e.g. α 6 34 (). We remark that
the theories established in this work are readily generalizable to the scenario of time-varying memory parameters a, and we present the static setting only for the sake of brevity.
3.2 Opaque market setup
In this study, we consider the partial information setting where the firms possess no knowledge of their competitors, their own reference prices, as well as the reference price update scheme. Each firm is only aware of its own sensitivity parameters b, C₁ and its previously posted price. Under this configuration, the firms cannot directly compute their demands from the expression in Eq. (2). However, legitimate assume that each firm can access its own last-period demands through market feedback, i.e., determining the demand as the received revenue divided by the posted price. We point out that, in this non-transe contrransparent and non-cooperative market, the presence of feedback mechanisms is crucial for price optimization.
3.3 Market equilibrium and stability
The goal of our paper is to find a simple and intuitive pricing mechanism for firms so that the market equilibrium and stability can be achieved in the long-run while protecting firms' privacy. Before introducing the equilibrium notion considered in this work, we first define the equilibrium pricing policy denoted by (r(r)= (ri, PÝ. (r)). which is a function that maps reference price to price and achieves the pure strategy Nash equilibrium in the single-pente perloe game. Mathematically, the equilibrium pricing policy satisfies that
pt (r) = arg max P. (T). Vi (H.
(5)
p.EP
Next, we formally introduce the concept of stationary Nash equilibrium, which is utilized to jointly characterize the market equilibrium and stability.
Definition 3.1 (Stationary Nash equilibrium) A point p** is considered a stationary Nash equilib- rium (SNE) if p' (p**) = =p", i.e., the equilibrium price is equal to its reference price.
The notion of SNE has also been studied in 21 22 From Eq. (5) and Definition 3.1 we observe
that an SNE possesses the following two properties
5

---

Equilibrium. The revenue function for each firm E {H, }} satisfies II, (ppp,pp))) p=*) S (p, p=*) for all p: P, i.c., when the reference price and firm -i's price are equal to the SNE price, the best-response price for firm is the SNE price p."
Stability, the price and the reference price attain the SNE at some period the reference price remains unchanged in the following period, i.e., p' = r = p" implies that r²+1 = =p"
As result, when the market reaches the SNE, the firms have no incentive to deviate, and the market remains stable in subsequent competitions. The following proposition states the uniqueness of the SNE and characterizes the boundedness of the SNE.
Proposition 3.1 There exists unique stationary Nash equilibrium, denoted by p = (PH-PL"). In addition, it holds that
1 =<p' bi C
b; + + -
- (
b. ( exp (a:
bi + )) ViE (H,L),
by
(6)
where (-) is the Lambert W function (see definition in Eq. 12
Without loss of generality, we assume that the feasible price range p [p. 2 is sufficiently large to contain the unique SNE, i.e., p" E [p. p|² Proposition 3.1 provides a quantitative characterization for this assumption: it suffices to choose the price lower bound p to be any real number between (0, (H. (1/(b: + c.))). and the price upper bound ア can be any value such that
1 bi +
(,, b. ( exp (a:
by + c; ))}
by
p
max (E)
+ b;
W
This assumption is mild as the bound in Eq. 7 is independent of both the price and reference price, and it does not grow exponentially fast with respect to any parameters. Hence, there no need for to be excessively large. For example, when az a1 10 and by by = CH CL 1, Eq. (7) becomes p 2 7.3785. We refer the reader to Appendix B for further discussions on the structure and computation of the equilibrium pricing policy and SNE, well the proof of Proposition 3.1
4 No-regret learning: Online Projected Gradient Ascent
In this section, we examine the long-term dynamics of the the price and reference price paths to determine if the market stabilizes over time. As studied in [22] under perfect information, the firms operating with full rationality will follow the equilibrium pricing policy in each period, while those functioning with bounded rationality will adhere the best-response pricing policy throughout the planning horizon. In both situations. the market would stabilize in the long run. However, with partial information, the firms are incapable of computing either the equilibrium or the best-response policies due to the unavailability of reference prices and their competitor's 's price. Thus, one viable strategy to boost firms' revenues is to dynamically modify prices in response to market feedback.
In light of the success of gradient-bass based algorithms in the online learning literature (see, e.g.. 43 44 (45), we propose the Online Projected Gradient Ascent (OPGA) method, outlined in Algorithm Specifically, in each period, both firms update their current prices using the first-order derivatives of their log-revenues with the same learning rate (see Eq. (. ) is noteworthy that the difference between the derivatives of the log-revenue and the standard revenue is a scaling factor equal the revenue itself, i.c.
i log (I.) Op.
1 (II,(p.)))
Vi LH.
(p,) Op:
Therefore, the price update in Algorithm | can be equivalently viewed as adaptively regu- larized gradient ascent using the standard revenue function, where the regularizer at period is (I/II 1/Il
We highlight that by leveraging the structure MNL model, each firm can obtain the derivative of its log-revenue DJ in Eq. 9 through the market feedback mechanism, i.e., last-period demand. The firms do not need to know their own reference price when executing the OPGA algorithm, and the reference price update in Line 6 is automatically performed by the market. In fact, computing the

---

Algorithm 1 Online Projected Gradient Ascent (OPGA)
1: Input: Initial reference price r (r r)) initial price pd (p) pL), and step-sizes (120
2: for i- 1==0, 0, ....... do
3:
for i [.] do
4: Compute derivative Dj from price and demand of firm at period t:
Ölog (II, r'))
Dj
(b. + c.) di(p', -b;; +a).
(9)
Op:
P1
5: Update posted price: p,+1 t- Projp (pf + 1/ D1).
6: Reference price update: p1+1 ar + a)pp'
derivative D; is identical to querying the first-order oracle, which is common assumption in the optimization literature [46]. Further, this derivative can also be acquired through a minor perturbation of the posted price, even when the firms lack access to historical prices and market feedback, making the algorithm applicable in a variety of scenarios.
There are two potential ways to analyze Algorithm I using well-established theories. Below, we briefly introduce these methods and the underlying challenges, while referring readers to Appendix A for more detailed discussion.
First, by adding two virtual firms to represent the reference price, the game can be converted into a standard four-player online game, effectively eliminating the evolution of the underlying state (reference price). However, the challenge in analyzing this four-player game arises from the fact that, while real firms have the flexibility to dynamically adjust their step-sizes, the learning rate for virtual firms fixed to the constant updates. This disparity hinders the direct application of the existing results from multi-agent online learning literature, as these results typically require the step-sizes of all agents either diminish at comparable rates or remain as small enough constant [47 48 [4 15.
a). where is the memory parameter for reference price
The second approach involves translating the OPGA algorithm into discrete nonlinear system i.e., (p*+1, p f(p', r') for some function f(-). In this context, analyzing the convergence of Algorithm I is equivalent to examining the stability of the fixed point of f()). which related to the spectral radius of the p²*) [4]] [5). However, the SNE lacks closed-fome expression, making
by treating (p" +11 r(+1) as vector-valued function of
Jacobian matrix (p(p" ""*"" it difficult calculate the eigenvalues of Vf(p"*, p**). In addition, the function f(-) mmn-shooth due to the presence of the projection operator and can become non-stationary when the firms adopt varying step-sizes, such as diminishing step-sizes. Moreover, typical results dynamical systems only guarantee local convergence [51]. i.e., the asymptotic stability of the fixed point, whereas our goal is to establish the global convergence of both the price and reference price.
In the following section, we show that the OPGA algorithm with diminishing step-sizes converges to the unique SNE by exploiting characteristic properties of our model. This convergence result indicates that the OPGA algorithm provably achieves the no-regret learning, i.e., in the long run, the algorithm performs at least as well as the best fixed action in hindsight. However, it is essential to note that the reverse is not necessarily true: being no-regret does not guarantee the convergence at all, let alone the convergence to equilibrium (see, e.g., [52 53 In fact, beyond the finite games, the agents may exhibit entirely unpredictable and chaotic behaviors under a no-regret policy [54].
5 Convergence results
In this section, we investigate the convergence properties of the OPGA algorithm. First, in Theorem 5.1 we establish the global convergence of the price path and reference price to the unique SNE under diminishing step-sizes. Subsequently, in Theoremm5.2 we further show that this convergence exhibits a rate of (1/t),, provided that the step-sizes are selected appropriately. The primary proofs for this Cand
section can be found in Appendices and D while supporting lemmas are located in Appendix
7

---

Theorem 5.1 (Global convergence) Let the step-sizes {n' h120 be a non con-incressing sequence such that lim n¹ 0 and Σi= n oc hold. Then, the price paths and reference price paths generated by Algorithm 0 converge to the unique stationary Nash equilibrium.
Theorem 5.1 demonstrates the global convergence of the OPGA algorithm to the SNE, thus ensuring the market equilibrium and stability in the long-run. Compared to [2] that establishes the convergence to SNE under the perfect information setting. Theorem e.nesuress be achieved in an opaque market where the firms are reluctant to share the information with their competitors. The only condition we need for the convergence is diminishing step-sizes such that lim;- 1/' = 0 and t- 1) co. This assumption is widely adopted in the study of online games (see, e.g., [55 14 40). Since the firms will likely become more familiar with their competitors through repeated competitions, it is reasonable for the firms to gradually become more conservative in adjusting their prices and decrease their learning rates.
ensures that such convergence can also
As discussed in Sections 2 and 4 the existing methods in the online game and dynamical system literatures are not applicable to our problem due to the absence of standard structural properties and the presence of the underlying dynamic state, i.e., reference price. Consequently, we develop a novel analysis to prove Theorem 5.1 leveraging the characteristic properties of the MNL. demand model. We provide proof sketch below, with the complete proof deferred to Appendix C Our proof consists of two primary parts:
In Part 1 (Appendix C.1 we show that the price path {p') would enter the neighborhood
NO := {p p2 {p)) < infinitely many times for any e >> O, where s(-) is a weighted & distance function defined s(p) := lp PH1/ (ber + cH) Ipi pul/(br + cz)). To prove Part 1, we divide pp into four quadrants with p* as the origin. Then, employing a contradiction- based argument, we suppose that the price path only visits N! finitely many times. Yet, we show that this forces the price path to oscillate between adjacent quadrants and ultimately converge to the SNE, which violates the initial assumption.
In Part 2 (Appendix C.2)
we show that when the price path (p')22) enters the fz-neighborhood
p* < } for some sufficiently small >> and with small enough step-sizes, the price path will remain in Na in subsequent periods. The proof of Part relies on a local property of the MNL demand model around the SNE, with which we demonstrate that the price update provides adequate ascent to ensure the price path stays within the target neighborhood.
N? = {p E p2
|P
Owing to the equivalence between different distance functions in Euclidean spaces [55] these two parts jointly imply the convergence of the price path to the SNE. Since the reference price is equal to an exponential smoothing of the historical prices, the convergence of the reference price path follows that of the price path.
It is worth noting that [21, Theorem 5.1] also employs a two-part proof and shows the asymptotic convergence of online mirror descent [56] 57 to the SNE in the linear demand setting. However, their analysis heavily depends on the linear structure of the demand, which ensures that a property similar the variational stability is globally satisfied 21 Lemma 9.1]. In contrast, such properties no longer hold for the MNL demand model considered in this paper. Therefore, we come up with two distinct distance functions for the two parts of the proof, respectively. Moreover, the proof by [21] relies on assumption concerning the relationship between responsiveness parameters, whereas our convergence analysis only requires the minimum assumption that the responsiveness parameters are positive (otherwise, the model becomes -unter-intuitive for substitutable products).
Theorem 5.2 (Convergence rate) When both firms adopt Algorithm ! there exists a sequence of step-sizes {n' J120 with n² (L/tt) and constants dpp dy > O such that
dp
dr 7 1121.
- p'
p
(10)
Theorem 5.2 improves the result of Theorem 5.1 by demonstrating the non-asymptotic convergence rate for the price and reference price. Although non-concavity usually anticipates slower convergence, our rate of (1/()) matches [21] Theorem 5.2] that assumes linear demand and exhibits concavity.
The proof of Theorem 5.2 is primarily based on the local convergence rate when the price vector remains in a specific neighborhood N2 of the SNE after some period Teg As the choice n¹ ((l/t)
8

---

ensures that 1om rf' = 0 and Σ'= = co, the existence of such period Tea is guaranteed by Theorem 5.1 Utilizing an inductive argument, we first show that the difference between price
and reference price decreases at a faster rate of ((1/E), i.e., ||' -p'll O (1/1), At > 1 (see Eq. (67) Then, by exploiting local property around the SNE (Lemmal F.3 we use another induction to establish the convergence rate of the price path after it enters the neighborhood N In the meanwhile, the convergence rate of the reference price path can be determined through
triangular inequality: ||D* r'1 = |p - p' + p' - r'112 < 2/Ip** p'1l2 + 2||p' - r 1 Finally, due to the boundedness of the feasible price range p², rate for all 2 1 by choosing sufficiently large constants dp and dy.
obtain the global convergence
Remark 5.3 (Constant step-sizes) The convergence analysis presented this work can be readily extended to accommodate constant step-sizes. Particularly, our theoretical framework supports the selection of ny = Oleo), where E, refers to the size of the neighborhood utilized in Theorem 5.2 When n' = (Eo), approach akin to Part can be employed to demonstrate that the price path enters the neighborhood N2 infinitely many times for any e 2 (EO). Subsequently, by exploiting the local property in munner similar to Part 2, we can establish that once the price path enters the neighborhood N for some e = (EE)), it will remain within that neighborhood.
2.50-
3.0
2.25
2.5
2.0
Price
1.75
1.50
1.75
1.00
0.5-
10
20
30
40
450
400
470
450
490
10
20
30
40
50
Time
Time
Time
(a) Convergence with 1/ = 3/t.
(b) Cyclic pattern with ry = 1.
(c) OPGA vs. equilibrium policy.
Figure 1: Price and reference price paths for Examples 1, 2, and 3, where the parameters are (aH, (H,CH) cH) (8.70, 2.00, 0.82). br, = (4.30, 1.20, 0.32), (rh:.9))) (0.10, 2.95). ph.) = (4.85, 4.86), and a = 0.90.
We perform numerical experiments, differentiated solely by their sequences of step-sizes, to highlight the significance of step-sizes in achieving the convergence. In particular, Example (see Figure
aa) corroborates Theorem b. demonstrating that the price and reference price trajectories converge to the unique SNE when we choose diminishing step-sizes that fulfill the criteria specified in Theorem 5.1 By comparison, the over-large constant step-sizes employed in Example (see Figure 1b fails to ensure convergence, leading to cyclic patterns in the long run. Moreover, in Example 3 (see Figure Ic], we compare the OPGA algorithm and the repeated application of the equilibrium pricing policy in Eq. (5) by plotting the reference price trajectories produced by both approaches. Figure con that the two algorithms reach the SNE at a comparable rate, which indicates that the OPGA algorithm allows firms to attain the market equilibrium and stability as though they operate under perfect information, while preventing excessive information disclosure.
Extensions
In previous sections, we assume that each firm possesses accurate information regarding its sensitiv- ity parameters (b,, c) as well as its realized market share df. This is equivalent to having access to an exact first-order oracle. However, more practical scenario to consider is one where the firm can only obtain a rough approximation for its market share and needs to estimate the sensitivities from historical data. This would bring extra noise the computation of the first-order derivative D in Eq. (9). In this section, we first elaborate on the feasibility of estimating the market share and sensitivities from realistic data. Then, we discuss the impact of an inexact first-order oracle on the convergence.
We consider the approximation of market share and the calibration of sensitivities under both uncensored and censored data cases. With uncensored data, both purchase and no-purchase data are

---

available, a scenario analogous to firms selling substitute goods on third-party online retail platforms like Amazon. The platform can track the non-purchase statistics by monitoring consumers who visited its website but did not purchase any product. Consequently, this facilitates a direct estimation of the total market size and, when complemented with sales quantities, allows for a precise computation of the firm's 's market share. Additionally, sensitivity parameters can be efficiently calibrated through the classical Maximum Likelihood Estimation (MLE) method. Due to the concavity of the log-likelihood function for the MNL model with respect to its parameters, many numerical algorithms (e.g.. Newton- Raphson, BHHH-2 [58], and the steepest ascent) are guaranteed to improve at each iteration and achieve fast convergence [59 [60]
In many cases, the traditional transaction data only captures the realized demand, with non- non- purchasssss typically unrecorded. This scenario is known as the censored data case. In this case, the sensitives and the total market size of the MNI. model can estimated via the generalized expectation- -axiaiiiinmaiiizzaiionn (GEM) gradient method proposed by [59], which is an iterative algorithm that is inspired by the expectation-maxin maximizaaiiinn (EM) approach. The capability to approximate the sensitivity parameters, the market share, and thereby the gradient D enhances the credibility and practicability of the OPGA algorithm, suggesting its great potential for broader applications in retailing.
In the presence of approximation errors, firms cannot precisely compute the derivative D Hence, the convergence results in Section 5 are not directly applicable. Indeed, if the errors are disruptive enough, one can anticipate Algorithm to possibly not show any convergent behavior. However, if the errors are uniformly bounded by some small number 8. the following theorem demonstrates that both the price and reference price paths converge to (6)) neighbbogoor of the unique SNE,
Theorem 6.1 (Inexact first-order oracle) Suppose both firms only have access to an inexact first- order oracle such that DDj - (p' /'0pp S 6, vi {H, L} and Vt 2 0. Let the step-sizes fnt Je20 be non-increasing sequence such that lim nf and Lt=o n¹ oo hold. Then, the price paths reference price paths generated by Algorithm converge to neighborhood with radius (8) of the unique SNE.
We remark that the inexact first-order oracle studied in our setting is different from the stochastic gradient, which generally assumes a zero-mean noise with finite variance. In that case, it is possible to derive the convergence to a limiting point in expectation or with high probability. contrast, the noise in D is a kind of approximation error without any distributional properties. Therefore, with the step-sizes defined in Theorem 6.I] we expect the price and reference price paths to converge to the neighborhood of the SNE, but continue to fluctuate around the neighborhood without admitting limiting point.
The proof of Theorem 6.1 is based upon Theorem 5.1 Specifically, we demonstrate that the inexact gradient still guides the price path toward the SNE if the magnitude of the true gradient dominates the noise. Conversely, if noise levels are comparable with the true gradient, we show that the price path is already close to the SNE. The formal proof of Theorem 6.1 can be found in Appendix E
7 Conclusion and future work
This article considers the price competition with reference effects an opaque market, where we formulate the problem price. We accomplish the goal of simultaneously capturing the market equilibrium and stability via proposing the no-regret algorithm named OPGA and providing the theoretical guarantee for its global convergence to the SNE. In addition, under appropriate step-sizes, we show that the OPGA algorithm has the convergence rate of (L/tt)
online game with underlying dynamic state, known as reference
In this paper, we focus on the symmetric reference effects, where consumers exhibit equal sensitivity to the gains and losses. As empirical studies suggest that consumers may display asymmetric reactions 66 32 622. one possible extension involves accounting for asymmetric reference effects displayed by loss avsr-e and gain-seeking consumers. Additionally, while our study considers the duopoly competition between two firms, it would be valuable to explore the more general game involving n players. Lastly, our research is based on deterministic setting and pure strategy Nash equilibrium. Another intriguing direction for future work is to investigate mixed-strategy learning [3 dynamic competition problems.
10

---

Acknowledgement
We extend our gratitude to the anonymous reviewers for their insightful comments. This research was particularly supported by NSF China Grant 71991462.
References
[1] Tridib Mazumdar, Sevilimedu P Raj, and Indrajit Sinha. Reference price research: Review and propositions. Journal of Marketing, 69(4):84-10) 102, 2005.
[2] Bruce GS Hardie, Eric J Johnson, and Peter S Fader. Modeling loss aversion and reference dependence effects brand choice. Marketing Science, 12(4):378- 394, 1993.
[3] James Lattin and Randolph Bucklin. Reference effects of price and promotion on brand choice behavior. Journal of Marketing Research, 26(3):299-310 1989.
[4] Richard A Briesch, Lakshman Krishnamurthi, Tridib Mazumdar, and Sevilimedu P Raj. A comparative analysis of reference price models. Journal of Consumer Research, 24(2):202-214, 1997.
[5] Gurumurthy Kalyanaram and Russell Š Winer. Empirical generalizations from reference price research. Marketing Science, 14(3_supplee (tl.sspppeeeeenii11--iiiii
1995.
[6] Ioana Popescu and Yaozhong Wu. Dynamic pricing strategies with reference effects. Operations Research, 55(3):413-453 2007.
[7] Gadi Fibich, Arieh Gavious, and Oded Lowengart. Explicit solutions of optimization models and differential games with nonsmooth (asymmetric) reference-price effects. Operations Research, 51(5):721-734, 2003.
[8] Xin Chen, Peng Hu, and Zhenyu Hu. Efficient algorithms for the dynamic pricing problem with reference price effect. Management Science, 63(12):4389 4408, 2017.
[9] Hansheng Jiang, Junyu Cao, and Zuo-Jun Max Shen. Intertemporal pricing via nonparametric estimation: Integrating reference effects and consumer heterogeneity. Manufacturing & Service Operations Management, Article in advance, 2022.
[10] Don Tapscott and David Ticoll. The naked corporation: How the age of transparency will revolutionize business. Simon and Schuster, 2003.
[11] Robert Bloomfield and Maureen O' D'Hara. Can transparent markets survive? Journal of Financial Economics, 55(3):425-455 459, 2000.
[12] Tim Wilson. B2b sellers fight back on pricing. Internet Week, 841:1-2, 2000.
[13] Nelson Granados and Alok Gupta. Transparency strategy: Competing with information in digital world. MIS quarterly, pages 637-641, 2013.
[14] Mario Bravo, David Leslie, and Panayotis Mertikopoulos. Bandit learning in concave n n-person games. Advances in Neural Information Processing Systems, 31, 2018.
[15] Panayotis Mertikopoulos and Zhengyuan Zhou. Learning in games with continuous action sets and unknown payoff functions. Mathematical Programming. 173:465-555 507, 2019.
[16] Tianyi Lin, Zhengyuan Zhou, Panayotis Mertikopoulos, and Michael Jordan. Finite-time last- iterate convergence for multi-agent learning in games. In International Conference on Machine Learning, pages 6161-6171. PMLR, 2020.
[17] Richard E Caves and Michael E Porter. Market structure, oligopoly, and stability of market shares. The Journal of Industrial Economics, pages 289-313, 1978.
[18] Jing-Sheng Song and Paul Zipkin. Inventory control in fluctuating demand environment. Operations Research, 41(2):551-37,, 1993.

---

[19] Yossi Aviv and Awi Federgruen. Capacitated multi-item inventory systems with random and seasonally fluctuating demands: implications for postponement strategies. Management Science, 4774):512-531, 2001.
[20] James T Treharne and Charles Sox. Adaptive inventory control for nonstationary demand and partial information. Management Science, 48(5):607-624, 2002.
[21] Negin Golrezaei, Patrick Jaillet, and Jason Cheuk Nam Liang. No-regret learning in price competitions under consumer reference effects. Advances in Neural Information Processing Systems, 33:214166214444 2020.
[22] Mengzi Amy Guo and Zuo-Jun Max Shen. Duopoly price competition with reference effects under logit demand. Available at SSRN 4389003, 2023.
[23] Ruxian Wang.
When prospect theory meets consumer choice models: Assortment and pric- ing management with reference prices. Manufacturing & Service Operations Management, 20(3):583-600, 2018.
[24] Mengzi Amy Guo, Hansheng Jiang, and Zuo-Jun Max Shen. Multi-product dynamic pricing with reference effects under logit demand. Available at SSRN 4189049, 2022.
[25] Tatiana Tatarenko and Maryam Kamgarpour: Learning generalized nash equilibria in a class of convex games. IEEE Transactions on Automatic Control, 64(4): 1416))4422-,,9,,, 2018.
[26] Panayotis Mertikopoulos and Mathias Staudigl. Convergence to nash equilibrium continuous games with noisy first-order feedback. In 2017 IEEE 56th Anmual Conference on Decision and Control (CDC), pages 5609-5614. IEEE, 2017.
[27] Yu-Guan Hsieh, Kimon Antonakopoulos, and Panayotis Mertikopoulos, Adaptive learning in continuous games: Optimal regret bounds and convergence to nash equilibrium. In Conference on Learning Theory, pages
PMLR, 2021.
[28] Yu-Guan Hsieh, Kimon Antonakopoulos, Volkan Cevher, and Panayotis Mertikopoulos. No- regret learning in games with noisy feedback: Faster rates and adaptivity via learning rate separation. Advances in Neural Information Processing Systems, 35:6544-6556, 2022.
[29] Jacob Abernethy, Peter L Bartlett, Alexander Rakhlin, and Ambuj Tewari. Optimal strategies and minimax lower bounds for online convex games. COLT '08: Proceedings of the 21 Anmual Conference Leurning Theory, pages 415-423, 2008
[30] Geoffrey J Gordon, Amy Greenwald, and Casey Marks. No-regret learning in convex games. In Proceedings of the 25th international conference on Machine learning. pages 360-361 2008.
[31] Harry Helson. Adaptation-leva theory: An experimental and systematic approach to behavior. Harper and Row: New York, 1964.
[32] Gurumurthy Kalyanaram and John DC Little. An empirical analysis of latitude of price acceptance consumer package goods. Journal of Consumer Research, 21(3):408-41) 1994.
[33] John G Lynch Jr and Thomas K Srull. Memory and attentional factors in consumer choice: Concepts and research methods. Journal of Consumer Research, 91):18-37, 1982.
[34] Zhenyu Hu, Xin Chen, and Peng Hu. Dynamic pricing with gain-seeking reference price effects. Operations Research, 64(1): 500-15,,,, 2016.
[35] Arnoud V den Boer and N Bora Keskin. Dynamic pricing with demand learning and reference effects. Management Science, 68(10):7112-7336 2022.
[36] Sheng Ji, Yi Yang, and Cong Shi. Online learning and pricing for multiple products with reference price effects. Available at SSRN 4349904, 2023.
[37] Brian Coulter and Srini Krishnamoorthy, Pricing strategies with reference effects competitive industries. International transactions in operational Research, 21(2):263-277 2014.
12

---

[38] Awi Federgruen and Lijian Lu. Price competition based on relative prices. Columbia Business School Research Paper, (13-9), 2016.
[39] Luca Colombo and Paola Labrecciosa. Dynamic oligopoly pricing with reference-pricn effects. 2021.
European Journal of Operational Research,
[40] Tianyi Lin, Zhengyuan Zhou, Wenjia Ba, and Jiawei Zhang. Optimal no-regret learning in strongly monotone games with bandit feedback. arXiv preprint arXiv:2112.02856, 2021.
[41] Noah Golowich, Sarath Pattathil, and Constantinos Daskalakis. Tight last-iterate convergence rates for no-regret learning in multi- aulte- games. Advances in neural information processing systems, 33:20766-20778, 2020.
[42] Daniel McFadden. Conditional logit analysis of qualitative choice behavior. Frontiers in Econometrics, pages 105-142, 1974.
[43] Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th international conference on machine learning (icml-03), pages 928-936, 2003.
[44] Elad Hazan, Amit Agarwal, and Satyen Kale. Logarithmic regret algorithms for online convex optimization. Machine Learning, 169--191 2007.
[45] Jacob Abernethy, Peter L Bartlett, and Elad Hazan. Blackwell approachability and no-regret learning are equivalent. In Proceedings of the 24th Annual Conference on Learning Theory, pages 27-46. JMLR Workshop and Conference Proceedings, 2011.
[46] Yurii Nesterov. Introductory lectures on corvex optimization: A basic course, volume 87. Springer Science Business Media, 2003.
[47] Anna Nagurney and Ding Zhang. Projected dynamical systems and variational inequalities with applications, volume 2. Springer Science & Business Media, 1995.
[48] Gesualdo Scutari, Daniel P Palomar, Francisco Facchinei, and Jong-Shi Pang. Convex opti- mization, game theory, and variational inequality theory. IEEE Signal Processing Magazine, 27(3):35-99, 2010.
[49] David K Arrowsmith, Colin M Place, CH Place, al. An introduction dynamical systems. Cambridge university press, 1990.
[50] Peter Olver. Nonlinear systems. Lecture Notes, University of Minnesota, 2015.
[51] H.K. Khalil. Nonlinear Systems. Pearson Education. Prentice Hall, 2002.
[52] Panayotis Mertikopoulos, Christos Papadimitriou, and Georgios Piliouras. Cycles in adver- sarial regularized learning. SODA '18: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2703-2717, 2018.
[53] Panayotis Mertikopoulos, Bruno Lecouat, Houssam Zenati, Chuan-Sheng Foo, Vijay Chan- drasekhar, and Georgios Piliouras. Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile. In ICLR 2019-7th International Conference on Learning Representa- tions, pages 1-23, 2019.
[54] Gerasimos Palaiopanos, Joannis Panageas, and Georgios Piliouras. Multiplicative weights update with constant step-size in congestion games: Convergence, limit eycles and chaos. Advances in Neural Information Processing Systems, 30, 2017.
[55] W. Rudin. Real and Complex Analysis. Mathematics series. McGraw-Hill, 1987.
[56] Zhengyuan Zhou, Panayotis Mertikopoulos, Aris Moustakas, Nicholas Bambos, and Peter Glynn. Mirror descent learning in continuous games. In 20/7 IEEE 56th Annual Conference on Decision and Control (CDC), pages 5776-5788 5783. IEEE, 2017.
[57] Steven CH Hoi, Doyen Sahoo, Jing Lu, and Peilin Zhao. Online learning: comprehensive survey, Neurocomputing, 459:249-289, 2021.
13

---

[58] Ernst R Berndt, Bronwyn H Hall, Robert E Hall, and Jerry A Hausman. Estimation and inference in nonlinear structural models. In Annals of Economic and Social Measurement, Volume 3, Number 4, pages 633 665.665. NBER, 1974.
[59] Ruxian Wang and Zizhuo Wang. Consumer choice models with endogenous network effects. Management Science, 63(11)) 63(11):3944 -):3944-3960, 2017.
[60] Kenneth E Train. Discrete choice methods with simulation. Cambridge university press, 2009.
[61] MU Kalwani, CK Yim, HJ Rinne, and Y Sugita. Oa price expectations model of consumer brand choice. Journal of Marketing Research, 27, 1990.
[62] Robert Slonim and Ellen Garbarino. Similarities and differences between stockpiling and reference effects. Managerial and Decision Economics, 30(6):351-371, 2009.
[63] Steven Perkins, Panayotis Mertikopoulos, and David S Leslie. Mixed-strategy learning with continuous action sets. IEEE Transactions on Automatic Control, 62(1):379-384, 2015.
[64] Eric Mazumdar, Lillian J Ratliff, and S Shankar Sastry. On gradient-based learning in continuous games. SIAM Journal on Mathematics of Data Science, 2(1):103-131 131, 2020.
[65] Eric W Weisstein. Lambert w- w-function. https:/mmatworldd. wolfram, com/, 2002.
14

---

Appendix A Discussion about alternative methods
As we briefly mentioned in Section 3 our problem can also be translated into a four-player online game dynamical system. In this section, we will discuss these alternative methods and explain why existing tools from the literature of online game and dynamical system cannot be applied.
A.1 Four-player online game formulation
By viewing the underlying state variables (r",rri, rr.) as virtual players that undergo deterministic transitions, we are able to convert our problem into general four-player game. Specifically, we can construct revenue functions R& (p(,,, r.) for E {H. )} and a common sequence of step-sizes {ny Jeo for the two virtual players such that when firms H, L and virtual players implement OPGA using the corresponding step-sizes, the resulting price path {p' 1220 and reference price path {r' h:20 recover those generated by Algorithm | specified as follows
The functions R, (, Vi {HI L} and step-sizes {n/ h22
1
Ra(p, = - + Ph Vi [H
2
(11)
nr = 0, 2.00.
Then, given the initial reference price r and initial price pº: the four players respectively update their states through the online projected gradient ascent specified as follows, for t 2 0:
log (I+ ,r))
PH
Projp
PH +np
Projr (p' 1/ D'/))))
Öpи a log (p',
1+1 Projp PT
pt. nn¹
Proje (pt. + 1/ Di
Spr.
(12)
OPH Orn
.41 Proje "
I' + n
Projo (artr + (1 (11a))ptn
(Ri(Pi,
.41 Proje
ri + n
Proje (art + (1 -a)pt)
Ør1.
It can be easily seen that the pure strategy Nash equilibrium of this four- pour-player static game is equivalent the SNE of the original two-player dynamic game, as defined in Definition However, even after
converting the static game, no general convergence results are readily applicable in this setting.
One obstacle on the convergence analysis comes from the absence of critical properties, such as
monotonicity of the static game [4] 16] variational stability at its Nash equilibrium [26]] [5]
Meanwhile, anther obstacle stems from the asynchronous updates for real firms (price players) and virtual firms (reference price players). While the real firms have the flexibility in adopting time-
varying step-sizes, the updates for the two virtual firms in Eq. ([2) stick to the constant step-size of (1 a). As a result, this rigidity of virtual players perplexes the analysis, given that the typical convergence results of online games call for the step-sizes of multiple players to have the same pattern (all diminishing or constant step-sizes)
47
A.2 Dynamical system formulation
The study of the limiting behavior of a competitive gradient-basee baadee learning algorithm is related to dynamical system theories [64]. In fact, the update of Algorithm [ can be viewed nonlinear dynamical system. Assume a constant step-size is employed, i.e., ") = Vt 2 0. Then, Lines 5 and 6 in Algorithm I are equivalent to the dynamical system
(p+ 1 )= f(p',r') V2 0,
(13)
15

---

where f(-) is vector-valued function defined as
1
Projp
PH +1
(6H + (H)))r (6x + cH)
PH
r(
Projp
pr. +1|
(br. ct. (p, (br. + ct.)
(14)
Pr.
Projp (arn + a)pH)
Projp (arr, + (1 a)pr..)
Under the assumption that p** E Pp2 it is evident that p** is the unique fixed point of the system in Eq. 13). Generally, fixed points can be categorized into three classes:
asymptotically stable, when all nearby solutions converge to it,
stable, when all nearby solutions remain in close proximity,
unstable, when almost nearby solutions diverge away from the fixed point.
Hence, if we can demonstrate the asymptotic stability of p** we can at least prove the local convergence of the price and reference price.
Standard dynamical systems theory 499 [50] states that p** is asymptotically stable the spectral radius of the Jacobian matrix Vf(p"', p=*) is strictly less than one. However, computing the spectral radius straightforward. The primary challenge stems from the fact that, while the entries of Vf(p"*, p**) contain p** and (p" "p'p" there is no closed-form expression for p**
Apart from the above issue, it is worth noting that the function f(+) is not globally smooth due the presence of the projection operator. Furthermore, the function f(()) also depends on the step-size When firms adopt time-van maneiia step-sizes, the dynamical system in Eq. (13) becomes non-stationary.
ie.. (p*+1 ) = f' (p'''rr) Although the sequence of functions f'120 shares the same fixed point, verifying the convergence (stability) of the system requires examining the spectral radius of Vf'(p"* "** for all 2 0.
Most importantly, even if asymptotic stability holds, it only guarantee local convergence of Algorithm [] Our goal, however, is to prove global convergence, such that both the price and reference price converge to the SNE for arbitrary initializations.
Appendix B More details about SNE
B.1
Connection between equilibrium pricing policy and SNE
First, we further elaborate on the connection between equilibrium pricing policy and SNE. The work 22 investigates the properties of equilibrium pricing policy under the full information setting, They demonstrate that the policy p* (r) is well-defined function since it outputs unique equilibrium price for every given reference price r. Further, for any given reference price r, the equilibrium price (phr (r), (r)) is the unique solution to the following system of first-order equations [2] Eq. (B.10)):
(r,(r)=
(bn + CH) (1 (n
(15)
(T. = (br. + cr.) (1 (1-dr(pp(r),r))
The intertemporal aspect of the memory- based reference effect prompts researchers to examine the long-term consequence repeatedly applying the equilibrium pricing policy in conjunction with reference price updates. Theorem in [22 confirms that in the complete information setting, the price paths and reference price paths generated by the equilibrium pricing policy will converge the SNE in the long run. Moreover, based on Eq. [15) for the equilibrium pricing policy, the SNE p* is
16

---

the unique solution of the following system of equations:
1
+ exp(an bn pH) + exp(ar. - by. pt")
PH (bH + (CH) (1 - dH (D",
(bH + +cH) (1 exp(ar (p.)),)
1 + exp(an - by pi + exp(ar. br. (p.))
PÊ (br + ct) (1 (1- (p"",,,""
(b1. + cL) (1 + exp(aн by PH))
(16)
can be seen from Eq. 16 that the value of SNE depends only on the model parameters.
B.2 Proof of Proposition 3.1
Proof. Firstly, the uniqueness of SNE has been established the discussion Appendix B.1 Below, we show the boundedness of the SNE. By performing transformation Eq. 16 we obtain the following inequality for p**
exp(a: - b, p. (b. G G)p;
1 expla- b.i p >1
Vi LH
(17)
To make the above inequality valid, it immediately follows that
b, + P 1+ exp((; p.") Vi E ( (H, L).
1
(18)
b, + Cs
Now, we derive the upper bound for p," from the second inequality in Eq. 18) Since the quantity on the right-hand side of Eq. (18) is monotone decreasing in p,* . the value of p. must be upper- upper-bounder bounded by the unique solution to the following equation with respect to p::
1 exp(a: Pt) pj
(19)
b, 6;
Define x := (b: ci) + Pe- Then, one can easily verify that the above equation can be converted into
ba exp
bi b, Ci )a)
cxp((x) = by + c
(20)
which implies that
b,
b;
x
W
exp a,
(21)
b + cs
+ C₁
where W-)) is known as the Lambert W function unique real solution to the equation
665
For any value y 2 0, W(y) is defined as the
W(y) exp (W(r)) = y.
(22)
Hence, we have
by
bi by +
p
< P:
W
exp
04
(23)
b, +
Cs
b.
b, +
Together with the lower bound provided in Eq.
18 this completest the proof.
Appendix C Proof of Theorem 5.1
Proof. In this section, present the proof of Theorem 5.1 By Lemma F.1 when the step-sizes in Algorithm I are non non-increasing and lim;-roc 17' 0, the difference between reference price and price converges
goes to infinity, i.e., lim (r' p²) 0. Thus,
left to verify that
the price path (p') converges the unique SNE, denoted by p** (see Definition 3.1 Recall that the uniqueness of the SNE established in Proposition 3.1
Consider the following weighted é ddiitanec between point p and the SNE p**
|p
PH
lpt pr.
(pp)
(24)
by
CH
by + CL
In nutshell, our proof contains the following two parts:
17

---

In Part (Appendix
C.1
we show that the price path {p" hr20 would enter the neighbooodo Eu} infinitely many times for any en O.
N2, to = {p pa
p
Part (Appendix C.2) we show that when the price path (p")12 enters the Eg-neighborhood Nº = {p pa
p p**ll2 cu for some sufficiently small 0 with small enough
step-sizes, the price path will stay in 2 during subsequent periods.
Due to the diminishing step-sizes and the equivalence between & and & norms, Part guarantees that the price path would enter any fz-neighborhood 2 of p** with arbitrarily small step-sizes. Together with Part this proves that for any sufficiently small 6g > there exists some Te, such that Ip p=1 Eo for every 2 Teg which implies the convergence to the SNE.
C.1 Proof of Part 1
We argue by contradiction. Suppose there eixsts cp > such that (Ph22 only visits N finitely many times. This is equivalent to say that 37 such that (p' (p')120 never visits N if 2 7 Firstly, let (p,,, the scaled partial derivative the log-revenue, defined as
a log (p.)
1 + dd(p))) -1
Gp(prr) = b; + c.
Vi (H
(25)
Öp.
(b, + c)pp
For the ease of notation, we denote P: = (p/ (b+ + (3)
| P) as the scaled price range. Then, the Proje,
price update in Line 5 of Algorithm is equivalent to
pt by + 6,
(
p bi + G
D )
( pi_ + +rG:orr)))
Proje,
+ n/
by o3)
(26)
by +
Let sign(-) ) be the sign function defined
1,
if > 0,
(ign(x) =
0, if 0,
(27)
-1
if x < 0.
Then, an essential observation from Eq. (26) is that: if sign(p;* - pt) G:(p', ('(p',r') r²) > 0, we have that sign - y = sign (G,(p', r²) = (p:" - pf), i.e., the update from p to 2t is toward the direction of the SNE price p²* Conversely, if sign(p;" - pt) Gp r²) < 0, the update from of to p is deviating from p;*
We separate the whole feasible price range into four quadrants with p ** being the origin:
N₁ = {p E p2 > PH and Pt 2 p }; N₂ = {p p2 рH S p and pt > p
(28)
рH < PH and pL p } N₂ = {pe pa N3 {p E p2
pи p and pL < p
Below, we first show that when & is sufficiently large, prices in consecutive periods cannot always stay within a same region. We prove by contradiction argument. Suppose that there exists some period T T after which the price path {p' 12212 stays within same region, i.c.,
18

---

sign (pt* -p(²)= = sign (p," - -) Vti, t2 2 T Vi E (H,L). Then, for t 2 TT it holds that
=(p = 1/ PH
pt PL 1+1
by + Cи
br. + CT.
PH
PLo]PH ('Gu(D'',r)
D'd by + CH
by + CH
pł Proje, (/Gr(D'rr))
pi
by. Cr.
by. + ct.
(A1)
Pi
G'Gn(p',r'
P't
+
Pł.
- - Gr - dy CL
ph.
by CH
by
CH
by CL
(Ag)
sign (pil p111)
PH
of GH(('',r"
P'H
bH
cH
by + CH
pi
r br. + cr.
+ sign (p2' -p2)
br. cr.
Pi
P'1
= sign (pit p'n1)
by CH G'Hz(p',p")
bи + CH
pp
p 11 + CL
+ sign (pt: - -())
bL cc - "G'G'''''pp')
+ +nl ( - Gp(p' - p') + GL(p',r) GL(p", pt) p')
(Ag)
Pi P't
pp pl,
S sign (p# p'n)
+ sign (vī pi)
by + CH
by + CL
n/ sign (p pin) Gn p') + sign (p ph) Gr(p',
((p')
+ 2n -,,l11' - -p'll2
(A.) pi ptrl
-, pp. n/'((')) + 2n 1r -p'll2
by cH
b1. + ct
= =(p') - n (g(p') 22, ||r" - -p'1l2)
(As) S =(p') ni (Meo - 20rl1r* - p'll2). Vt 2 T
(29)
where the property of the projection operator in (A1). The equality (A2) follows since
sign (p** -p/+1 11 sign (p pf) for {H,L}, and the projection does not change the sign, then we have
p G
pf
sign
= sign (p, pi), Vi LH.
b, +
b, + c:
The inequality (Az) results from Lemma
F.5 In particular, since (p. I fr, where
e, = (1/4) + 2, follows that (.((p'rr)) - Gp p')l < [[,,G(p.r)]l ||r p'll, s E -pll,y Vi (H, L). (30) In step (Aa), we introduce the function ((p), which is defined
(p)) == sign(pH -PH) GH(P, + sign(rž PL) Gz(p.)), pppp? (31)
19

---

Finally, the last step (As) is due to Lemma F.2 which states that 2M > 0 such that ((p) 2 Me. for every p E p2 with E(p) ep. Since for 2 TT To we have {p') ) 2 en by the premise, follows that (pp))
)² 2 Me..
By Lemma F.1 the difference (r'- -r'-p') -p'"p22 converges 0 as approaches to infinity As result, we can always find " > 0 to ensure ||r" -p'la S / for all t 2 T2" Then, the last line in Eq. (29) can be further upper-bounded as
<p' S <(pp)) -n (Meo 26, 1lrl -2e,
p'llz)
<<((") n/' {MMMo
2 Mea)
(32)
S <<(p') 2"¹ Menx
Vt : [TTo T2
T 1-12 To down to period Tea we have that By telescoping sum from any period
M c(p") S <(pp"
Tmo
n
(33)
2
t-
Since the step-sizes satisfy Ei 11 o0, co, have that limr (Moo L n = which further implies the contradiction that lim e(p") + -00. Thus, the prices in consecutive period will not always stay in the same region, i.e., the price path (p') keeps oscillating between different regions Nj for j E (1,2,3,4 3,44). 4).
Next, we prove that 373" > T such that the price path {p' ID")e22z Je2:7o only oscillates between adjacent
quadrants. Arguing by contradiction, we assume 17 T7 c2/(2Mc), where Me is the upper bound of (.(,,,)) | defined in Eq. (100) in Lemma F.5 If pf E Ni (or N2) and p'+1 E Ng (or N4), i.e., sign (p²** * p o sign (pt- p; +1) for both L}, then automatically follows from the update rule (see Eq. (26) that
= S n/ ([Gn(p', r²) + (r(('r
(34)
cu 2Mg = ED
$
2Ma
which again contradicts the premise that (p')e2 never visits N1 ep" path {p') {p')2270 only oxcillates between adjacent quadrants.
Thus, when / T3, the price
Because of the following two established facts: (i) when 2 max TT }. the price path will not remain in the same quadrant but can only oscillate between adjacent quadrants, and (ii) the step-sizes (17 J220 decrease to as -> DC, we conclude that the price path {p)220 must visit the set
No, { pa
PH
PH!
1p Prl 1y
<1 or
(35)
Py + cH
infinitely many times for any > O. Intuitively, set No, can be understood as the boundary regions between adjacent quadrants. We define Te, as the set of "jumping periods" from (N1 U N to (N₂ U N4) n N., after i.e,
Ta = (12 T I E (N, No, and p'+1 E (N2
(36)
Then, the above fact (i) implies that [T,, = co for any 61 > 0.
The key idea of the following proof is that if (p') visits Ne, with some sufficiently small 61 and relatively smaller step-size, it will stay in Ne, and converge to N1, concurrently. This results in contradiction with our initial assumption that [p') never visits N1, when t 2 T
Let TT E Te, be jumping period with E < Eg. Without loss of generality, suppose that lpū
T/1 PH 1/ +cH) < E1. Then, since 7T & N1 accordingly have that -177" 1 1/(bbtzz)
20

---

60 61. By the update rule of price in Eq.
26 it holds that
Ti +1
T +1 př. Pr.
p7 PL
sign (pī
Pt.
Ti'+ +1)
by + CL
by + CL
Tf'
sign (p PL
17 +
Projp, by tCL
PL
+npi" GL (p (p""), ,
Py + CL
p1 Pi Tt
S sign (ptt - PL
-nj''GL(p"'
GL(p"i" ,,
by + CL
Pr Tt
= sign (pr:
P
sign (pïz - PL ) (nff' GL(P"i ,x"")) ))
PL
2y eL
(37)
We note that, the last step above is due to the premise that the step-size is sufficiently small: since
pr
Pi T"1
(bb ct)) > 6o- E₁, the equality sign (pî 1 + sign (pt pp holds
n7t²
< (5o MI Next, we show that the second term on the right-hand side of Eq. (37 is upper-bounded away from zero:
sign (pt Pr. Th
Gp(""' Th ,,"))
2 sign (pi. PL
T: GL
Ti", ,PTi)) - (p _ (pTi",TTi))) - GL G Tip ,p'i)) |
(A1)
2 sign (pī PL T:1 GL pTT²) fo|l - -p= 1l
= sign (pi - PL T:1
+ dp p -1 1 1
e, |T -p²i' l12
T.
(br + cL)Pr
[
2 sign (pî: )
1
T + d (pH Tht) (pH. T:t) ))
(br. + cr.
- d (p""" , ) dr. (vtt pit ) WH.rr"" pi )) ey 1|-1 - 12
(Az)
2 sign (pt - 1L-
+ dr (PH Ti ) -1 1 - e | -p7 112
(bL + CI)PTT" Th
(d, OpH
} 11 - PHH
max pEp
(Ag)
2 sign (pi: p(t)))
[ 1
+ dr (wtii Tht (o. -1 - e,|l1r? -p=t" l1
(bL + cL)PE
1 bbbb + cH)E1
( T lx 1 -DT''1
112 - bn + en)e1.
1
(38)
where (Ai) holds because of the mean value theorem and the fact that (p)) e, for p.r E p2 by Lemma F.5 inequality (Az) applies the mean value theorem again to the demand
T
function. In (As), we use the assumption that 1p PH (bæ + cc)e1 and apply similar
21

---

argument as Eq. 101 to derive that
0dr. (p. p)
= bb d.(P.P))dr(PP. - ihn Vp E p2.
(39)
Öpи
Since ((PH I1 )) > 60 - 61, by Lemma F.2 there exists a constant Men-a > 0, such that ((PH T:
)) 2 Meo-er Meanwhile, we can choose E1 sufficiently smaller than to ensure that (1/2) (1/4)bm + ccree > 0. Furthermore, recall that 77 can be arbitrarily chosen from Tap where [T 0o. Thus,
always find sufficiently large 7 E Tr guarantee
that e 1 TT l12 & (1/2)Mee-e1 (1/4)bb (bH + cH)Ei by Lemma F.1
Back to Eq. (38).
follows that
Tf' sign (p -pr Gr.(p" Ti rT"))
2 S((P
Th1 )) lr |||1" -p" l12
1
ber (b + cc)a
4
(40)
1 M
1 bon (bn + +nn)ee)
1 bun(bn + cn)e
2 Meg-11
1
1 Meo-e1
By substituting Eq. (40) into Eq.
37
we further derive that
pt: Pí.
+1 +1 br. + Cr
I sign (pi. - Pi
T:d
P0 PL sign (pt - -pi Hit).
T
(I"")
by et
1 Pr.
Ti
2"
T
Mea-es-
by CL
(41)
Tt' T +1 is towards the SNE price pt. when |pi
This indicates that the price update from Pt to PL Th1 PH < (bHr + cH)e..
Now, we use a strong induction to show that PH - p/gl/(bb + CH) < 61 holds for all t 2 T provided that e sufficiently small and T is sufficiently large. Suppose there exists T5 2 T such that 1p p/bl/(bu + CH) < 61 holds for all T T 1,..., T2., we aim to show that
PH that
PH
T +1
1(bss + cis) < 61- Following the same derivation from Eq. 37 to Eq. it holds
1 PL br. Cr.
1pt S--Ph pil by. + cr.
1
2 Meg-en t= T
T
(42)
By telescoping the above inequality from T - down to T we have that
T 1p_ Pr.
7
T
T pL - Pr.
pp - Pr.
M Men-es
<
n
(43)
by + CL
by + CL
2
by CL
1=
Additionally, we note that 1p pinl/(bH + cH) <e and pt N1 together imply that |p
p/l//bb. + et) > (5o 61) for all = Tú, TT, + 1,...,, T As the step-size sufficiently small, we conclude that the price path {rL (=1p1 lies on the same side of the SNE price p1* and T
thus sign (pi. Tr PH PH
PL T
= sign (pt. PL ). Below, we discuss two cases based on the value of
T 1/bb + +ca) < < 7² Mc.
Case 1: p2
PH
22

---

Following a similar derivation as Eq. E7. we have that
T22 +1 pH
T2
PH
sign (pii
PH
22
PH
PH
- -n7²²
sign (ptt - p/
G (p" 20 ,r'')
bи + CH
bн - CH
T2
PH PH
+ 1)
GH GH ,²2
bu + CH
(A1)
E1 - Ti Mc) + t MG
(Aa)
61:
(44)
where (A1) is from Lemma F.5 that [Gr(p,r) & Mg for p, E P2, and (Az) is because the sequence of step-sizes is non-increasing, hence 17 7T 2 n??
/bb + cH) E [e] 11-17 Mc. M1. Case 2: PH PH T
It suffices to show that 1o7 - -P this is equivalent to showing that
T 7 +1 S PH PH
According to the observation below Eq. 27
sign (p#
PH
T TT (p 2 0.
(45)
We further discuss two scenarios depending on whether T E N1 N Tt E N2 U4.
1. Suppose that p²² E N1 U Ng. According to the definition of set Te, in Eq. (3) we have that
pFi' E N₁ N3 since T Tey is jumping period. Together with the established fact that 221 sign (pi* -pi" (see the argument below Eq. 433 ). we conclude that p sign (pH PH
sign (pi* Pr.
and pT. are in the same quadrant, and sign (p PH write that
2
pH ). Then, we can
sign (pii - PH
T:t GH (p Th (T+)
2 sign (p PH
T:
GH (T .TT²' - - -p7 T2² ||2
Th
(A)
2 sign (pii PH
T
Gn((PT Th T
PL
). (P
T T:t e 1F T
,PL
p 1z
(46)
= sign (pi - P T
GH (p" Th - -p""" l|2
+ sign (ptt
PH ((H
Tet
To T
PL ) (PH PL I - GH - (I'"""",,p''" -p²ft))
(p"t"
To where we apply Lemma F.4 in (A) by utilizing the relation |p - Pt.
S 1p pr. proved
T
in Eq. (43). Next, T a jumping period, it follows from the price update rule in Eq. (26
T that FH PH 1/(br cn) S | Gn (p=t', " ))l S T Me. Thus, when the chosen jumping period 7 is sufficiently large so that the step-size n/"f* is considerably smaller than e1. we further derive that
T, > (bH + cCH) (E1 - "M) PH
Mc) 2 (bи + +cH) TT Mc 2 1p -PTi Tt'
pH
(47)
23

---

With Eq. 47
we use Lemma F.4
again to upper- upper-bound bound the last term on the right-hand side of Eq.
46
(pi PH 7
(Gu((P PE P ( - GH "p""')
sign
sign
(pii
T:
GH( PE (P Pr sign (p Th) GH GH ,²?"'"
To
(A
+ du (PH PL ) (PH T. 1 -
T T
T (bn + cH)PH
(0r
+ dæ (p .p=i -1)
(bx (by + CH)P#
T
1
1
du
(PH To
.PL ) ( T
PL
du T. .p .p:.))
by (P
+ CH
T2
T
PH
diff
diff,
(Ag)
1
by +
T PH
PH
(48)
where (A1) holds since the difference in the previous step is non-negative by Lemma F.4 Fur- thermore, is straightforward to observe that the terms diff, and diff's have the same sign, which results in the final inequality (A2). We substitute Eq. 448) back into Eq. (46):
To sign (pt - PH (p
2 sign (pit - pH Til)
Gn Tr, "''''""'' ) - -rl1r -p=²" 112
by + CH
T22
T
Pıi
PH
2
sign (p#
PH
(D ,ttt er (111 p==²" lll + || 1,71 11))
1 1
bu
+ CH
T
T
PH
Ph
T
T
(A1)
2 l, (11x222 1= 1l2 + ||2""² p²1"" l12)
PH
- PH
(PH T. Tet
(bH + +CH)
PH
(A2) 2 - Ey (11
122) + (G - T7T MM) TTT Mcl
p 112 + TI
T
(bи + c.).
(49)
In inequality (A1), we use the fact that sign (pi PH T: (DT ,TT'", 0 since T is
jumping period in Tep- Then, inequality (A2) is implied by the properties that sign (pit PH T
)
sign (pit - PH )- 1pit
T PH 1/bn + cH) 2 6 - 7 Mc. and |N - Pr 1/ + cH) S n Mg. Since both the step-size 1) and the difference ||r p' ||2 decrease to 0 as + oo,
by choosing a sufficiently large jumping period 7 from Te,, the right-hand side of Eq. (46) is guaranteed to be neg-tega,,ve i.e., sign (pit PH Gn (D ,T= 2 0. This completes the proof of scenario 1.
24

---

2. Suppose p²2² E N2 U N4. We deduce that
sign (r Pn
12
GH (p ,
2 sign (p
Pn
T: Gp To .p=²' -,1(1'2' - -p" 112
(Ai)
2 sign (yii PH
T
GH (PH T .PE) (PH .Pt) 2 -p==" 1/2
(50)
( ((P 22
.pi.)) er ||rd
-p" l|2
(As)
2 M2, - lr 41|1"=2 T2 - p
_ 1|,
where čl == =1 117 Ma.
The inequality (A1) follows from Lemma F.4 where sign (PH PH) GH (p.p) deceasing when lpi - Py decreases The equality (Ag) is due to the definition of (()) Eq. (31) and the fact that sign(pł* PΣ*) 0. Finally, in the last line (As), leverage the initial
assumption of Case 2, which implies that e( Th .Pt')
p/ T
PH 1/(b CH) E [4
n Mc. c1). Then, by Lemma F22 there must exist M2, > with E = E1 - 17 MG such that T H .P1))
g((P
oo, we can pick a sufficiently large T E Te to guarantee that - M2, for t 2 Tí by Lemma F.1 Consequently, we obtain the desired conclusion
2 Ma. As (T
l, r' - p']
that sign (pit of scenario 2.
PH -G (p Th r
T
when x TT E N2 N4, which completes the proof
T2i +1 1/bb < e1, which completes Combining Case and Case 2, we have shown that - Pi
the strong induction, i.e., |p p'u D'xl/(br + ch) < 61 for all t 2 T Under the assumption that {p')>0 never visits N/ if 2 T we accordingly have that p2_ - -P- w + cL) > (co (1) for all / 2 7H.. Therefore, following the derivations from Eq. (37) to Eq. (41). we deduce that Eq. (42) holds for all 2 Tf. Using a telescoping sum, it holds for any period T 7 that
PF Pf. T:
M M
T-1
n7.
(51)
19 + el
19 + CL
t=
Since Men-e > 0 is constant and limy 000 pp" - -PE /bbr +bb,, + -o as T + xc. Consequently, our initial assumption is incorrect and the price path {p' ip')120 would visit the é eiiiehhbborooo N2, infinitely many times for any eo > O, which completes the proof of Part 1.
21=r; T-1 n7' = co, we arrive at the contradiction that
C.2 Proof of Part 2
In particular, we show that when p' E N2 for some sufficiently large I, then it also holds p e N2 The value of will be specified later in the proof.
60'
25

---

By the update rule of Algorithm 1 it holds that
105" Pi 1
1, Projp (Di D!) ?
< |0 (pi + n/' Dt) ?
(0 - pi) - v/(4, + 4.) r'('',
= lp5" - pi - -21 +c) G,(p', r¹) - p!) + (v' + +c) G.(p', r'))
= 105" -:--pie p/1²
+ 2 Gp(p', p²) (pt - -;) + (17(b, +c) Gi(p', x²))²
-2
+ 22/ + +4) (Gi(p': p²) - G:(p', r²)) (pt - p!)
$ 1p5 - 2=1²= 21/ (b: + ()) Gp p²) (v - pi) + (1/ Ma(b, + tc))² + 227 (b; + c.) |p;- pl 4/11=' pll12
(52)
where we use [G, r) < Mc and the mean value theorem in the last inequality (see Lemma Let H()) be a function defined as
F.5
H(p) =- (brr + cn) GH(P.P) (pi -PH) + (br + cz) Gr(p.P) (0 PL).
(53)
Then, by summing Eq. 52) over both products E {H, L}, we have that
|p - -p 11 < 1 - p² p²12
2n²
Σ
(a++a)GGG(p'ppp (vz - pi)
+ (a)
Σ
(b: + c;)² 2 + 2n/ E.llr' - -p'll2 Σ
(be + ci) -1t - -pi
(E(H.L}
(E(H,L}
= =||p"* - p² p01 _ - 2n HH('') + Mc)²
Σ (b. + c.)²
iE(H.L)
+ 22 -p'l2 Σ
(b: + t;i 1, - -P-l
(H(
< 11pp"'p'''" n¹ 27((p') n/Cr C2ll1' - -p'llz
(54)
where we denote C == (Mc)² Eie(H (b; + c2)2 and C2 = 26rlp - 1l Eie(H, (b: + ct).
By Lemma F.3 there exist > 0 and a open set U., e p such that H(p) 2 1--1pp-p p 1 Vp E Un.
Consider <o > 0 such that the fz-neighborhood N2 = {p E p2 |pp - p ll2 < { C Ug.
Furthermore, let T.y be some period such that
n (1'C V2Cx(p 2) S and n/ C2lle' - -p'll2 < T(0022
=
14 Ty.
(55)
The existence of such number T.y follows from the fact that lim 7f 0 and 1im ||r p'1la 0 (see Lemma F.I. Below, we discuss two cases depending on the location of pt in N2.
Case 1: p' E N2 2 22 i.., I|p" - -p'll, < e
26

---

Since H((p) 2 0, vp E Un by Lemma F.3 it follows from Eq. 544 and Eq. (55) that
-p*"-'++ 2 < 1p" - p'112 r/ (1OO + C2flr' - p'll2
(en)²
+ r/ (1'C+ + v2C2(1 - 2)
4
(56)
(co)²
(co)
+
4
4
(co)² 2
where incquality (A) is due to ||r - p'l12 5 v2(ō (07-p) p). Eq. (56) implies that p E N co
Case 2: p' E 22 //2 <0/2 i.e. ||p 1|p--p''1 E (c0/2, co).
-p'll2
By Lemma
F3 we have that H(p') 2 7||p"* p¹112 2 >(00)//4 /4. Thus, again by Eq. 54 and Eq.
555
have that
1p"
11 - 11''''-' -p'll2 -n'
v/' (2H(D') r/Cr Callr p
$ 1|" p'l12 n/ (>lay)
2 r/02 C2l1r' - -p'll2
(57)
< || p'112
(co)?,
which implics pt E 2N-- Therefore, we conclude by induction that the price path will stay in the Ez-neighborhood N This completes the proof of Theorem 5.1
Appendix D Proof of Theorem 5.2
By Lemma F.3 there exist 7 > 0 and p vp E Uy. Consider > 0 such that the (z-neighborhood .22 = {p E p2 llp lip-p"lle < <o C Uy. Below, we first show that the price path {p' h12 enjoys the sublinear convergence rate in N when is greater than some constant Teg Then, we will show that this convergence rate also holds for any t < Tep-
Proof. Recall the function H(p) defined Eq. (53
open set U., p** such that H()) 2 Y ||p
By Part 2 in the proof of Theorem 5.1 there exists T > 0 such that p' E N2 for every t 2 Te.. Following a similar argument as Fq. 52 and Eq. (54). we have that
|p"
1
(A))
|p
p²112
CC()))
p'll2 Σ
(b. + cz) -ptt - pfl
iE(H.L)
(A2)
|p - p'1l2 - 20'>|1p"* (
+ 27 e, - -p'll2 kllp** 11 -p'll2
(As)
1p* 1'1l2 2n'>/ 2n/>||p** p'l + Ci + e
-11p - -p'11 + egk 11 pz 112
2
e,k
?
(A4)
|p"
- 1'112 ,'7||p"* -p'lpppp < 10112- 2
(58)
27

---

In step (A1), e, is the Lipschitz constant defined in Eq. (00) and the constant C1 is defined in Eq.
(4). In step (A2), we utilize Lemma F.3 and the following inequality
Σ
(b; + +.)lpp pil =
max 16, + -aBl|p"'pp'1 (e(H,L)
TE (H
I /2 max (E(H,L)
{b; + ci ci> -p'll
(59)
=b|lp" -p"ll 1''12
where we define h == max (H.1) (b, + 4.) Step (Ag) in Eq. 58 follows from the inequality
of arithmetic and geometrie means, i... 2zy 3 Az + (1/A)y² for any constant A >> 0. The value of constant k in (Aa) is given by k =- (f, / 2f, ma 1b, + <,))
To upper-bound the right-hand side of Eq. (58). we first focus on the term |||' - -p'll2 and inductively show that
||' - pp 00 t2
A1 T = V V2X
(60)
where \ = 21+ < We use the notation D == (D'r D2) ((bn + en +enenGGn Gn r)), (br. (D') where we recall that D is the partial derivative specified in Eq. 4 and function G((,.) defined in Eq. (25). Then, the term ||r - p' p'l1 can be upper-bounded follows
||re p'l 1211
| 1 + (1 - - p'1
|a(F 1- p"
) + 1- - 1p--1-p')) -p)
a²
22111'
p" - 1 |p -- p'1l2 + 2a(r' 1-1 -pp' -p'
(p- - -p')
(A))
S a²
1 p
[| D' 11 + 2a
1r- 1--1-p" -p--11 112111 - DD= 1
(A.)
I a²
1 - -p' 1-
2
1-a²
1-
|
1- - -p'ppp''1 11 +
2a
||
D' 1
2
2
1- a
1 2
1 a
p p' 1|
Im
1n=''"* 1
a
2
p² 11- 1| +
1 1+a² a²
Σ
(b, + ci)² [G((p' ( -17-112
1 - a²
iE(HI.)
(Aa) S
1 a+a²
- 112 +
(Ma)² Σ
(b: + cs)2 -1pt
1 a²
iE(H,L)
Ao
(61)
where (A1) holds due to the Cauchy-Schward inequality and the property of the projection operator (see Line 5 in Algorithm [p. Step (Az) is derived from the inequality of arithmetic and geometric
means. Lastly, step (Aa) applies the upper bound on function G.(..) in Lemma F.5 and the definition
of C in Eq. (54). For the simplicity of notation, we denote the coefficient of (17 )² in the last line as Ap-
Let the step-size be n) = d + 1) for & 2 0, where d, is some constant that will be determined later. Suppose that there exists a constant drp such that
drp
|||'
p² - 112 < (t - 1)2
(62)
28

---

for some t 2 + Then, together with Eq. 66 we have that
|| - p'112
| p² p 112
20(11=112
Adrp
+ 2o(d,))
(t 1)2
f²
Adrp
12
Ao(dn)
t2
(t=1)2
+
t²
(63)
Adro
A+1
An(dg)²
+
t2
2x
f2
0.5(A 1) drp + )o(d,))
where the inequality (A) results from the choice of Tx, Hence, the induction follows 0.5
1) >o( 2 s drp. which is further equivalent to
(d) drp Z X
(64)
Lastly, the base case of the induction requires that || p pT 11 - (7>)²²
drp
Therefore, by Eq.
664
and the definition of feasible price range = (p.p). it suffices to choose
22p(d 2(TH) p)²
d.p max
(65)
where the constants Åo and Tx are respectively defined in Eq. [6] band Eq. (00) Note that, under this choice of constant dyps also holds that
||' - -p'1p = 2 2( p)²
2(T)) - p)2
drp
V
(66)
12
Together with Eq. 660
we derive that
rr
p'll2
dep
V12
(67)
For every / 2 Teg can further upper-bound the right-hand side of Eq. 588 by exploiting the upper
bound of ||rd - p'1 1| in Eq. (67) and the choice of т)- = d,/ (t + 1):
ydg
11p*~-p'1 + (dd,) (t + 1)2
d drp (t + 1)t²
|p** p +2
+ 1
ydn
(id,) + d
(68)
1|p* -p'1p11
+ 1
t(t + 1)
Teo
Cs
Now, we inductively show that
(
p" o
Vt > Teg
(69)
Suppose there exists a constant dp such that for a fixed period t 2 Ten
| - 21 4
(70)
To establish the induction, it suffices for the following inequality to hold
1 - 1 < (1-
ydg
dg +
C3
dp
< t i+1
(71)
1 1+1
((t
29

---

which is further equivalent to
(gd - 1)dp 2 Cg.
(72)
To satisfy the base case of the induction, summary, one possible set of constants (d,, drpp dp) that satisfies all the requirements be
select dp such that dp 2 Teo 1p" -p" To
2 In
2 d, y² drp max (dp
1 2(Tx) - 2)² -
dz max C3. 2T
2) (73)
where the constants Ao Tx, and C3 are respectively defined in Eq. 61 for any period 1 S < Teg it follows that
Eq. 60
and Eq. 68 Now,
2I T p)²
dp
p
p' 2(
(74)
t
Together with Eq.
669 this proves the convergence rate for the price path, i.e.,
| p
121
(75)
Finally, the convergence rate of the reference price path can be deduced from the following triangular inequality:
||D" - r'1 = =||p" p' + p' - r-112
$ <21|p** -p' p'112 221lpp - -r' r
(A) 2dg + 2d
(76)
2dp + 2drp
Vt 1,
where (A) follows from Eq. (67) and Eq. 75 Therefore, it suffices choose d, 2dp + 2drp. and this completes the proof.
Appendix E Proof of Theorem 6.1
Proof. Recall the definition of Gp from Eq. (25). We can write the inexact derivative as D (b; + (p' r²) + ni, where n. represents the error satisfying |nt] < 8, Vi E {H, L} and VI 0.
We also recall the two-part proof for Theorem 5.1 in Part 1, we show that the price path and reference price paths converge towards the SNE and visit the neighborhood N! infinitely many times, for any > O. In Part 2, we establish that, given is below a certain threshold ep, the price vector would remain in the neighborhood N2 after entering with sufficiently small step-size. Since the relative scale of 8 and is unsure, our proof below is mainly based on Part 1.
In Part 1, the original proof assuming the exact gradient oracle employs contradiction based argument. Suppose the price path does not converge to the SNE, the proof consists of the following major steps (different from Appendix C. we use in lieu of en avoid confusion in the following proof):
In Eq. 29 it is demonstrated that the price path steadily approaches the SNE if it stays in the same quadrant defined in Eq. (8). The main technique we use is ((p) > M, when <(p) > e. The
definition of ((p) and the validation for the technique stated in Lemma F2
In Eq. 64 we show that the price path only oscillates between adjacent quadrants provided the step-sizes are sufficiently small.
(41), prove that even when the price path does stay in the same quadrant, it will still converge toward the SNE if it is at the boundary regions between two quadrants. The pivotal
From Eqs
inequality employed here is again ((Ptt, T )) 2 Mc-qy provided e((i)) .PL
T )) > < - 61 (see
the end of Eqs. 38 and (40)
30

---

Finally, in Eq. 44 and subsequent equations, we provide supplementary justification for the above bullet that the price path remains adjacent the boundaries given that the step-size is small. A crucial consideration here is opting for a much smaller 61 relative to when defining the boundary
region. In addition, the inequality ((PH 222
-PL')) 2 Ma, is also utilized in Eq. 550..
To summarize, the key to the proof is Lemma F22 i.e., ((p) > M, > 0 as long as s(p) > c. By definition, G(p') approximately characterizes the difference s(p') (1) as seen in Eq. (29). As a result, the effect of the lower bound M. is that, if other terms can be upper- bounded by M. we can show that the updated price is closer to the SNE. For example, the right-hand side of Eq. (29). once
the term 26, || p'li 2 is below Mc. it suggests that the price vector is heading towards the SNE.
With inexact first-order oracles, the immediate consequence is that there will always be error term accompanying (p). For instance, given Dj = (b; + G)) r²) + nn, we observe that Eq. 29 evolves to
n (bs + ci)
e(p s(ptt))s((p) <e(p') 1/6 M. Mc--2e11r -
26r11r
Σ #E(HLL)
(77)
This observation is consistent across the proof. Thus, if the error nı is substantially smaller than Mc the proof of Theorem 5.1 remains valid, implying that the price vector converges towards the SNE. The subtlety arises when the size of nz is comparable with M.. Under such circumstances, the analysis in both Eq. (29) and Eqs. (37) (41) becomes invalid, as the errors are substantial enough to negate any assurance that the price path strictly approaches the SNE.
However, if the error nf is similar in magnitude G(p), we show that the price vector p is already close to the SNE p** More precisely, since the errors are bounded by ó, it is equivalent to show that (p) (6) also implies ||p p'* (6)). This can be proved by refined version of Lemma
Lemma E.1 (Refined Lemma F.2 Let (p)) be the function defined in Eq. 86 Then, it holds that
g(p) 2 Σ
lps PP--p"" P.
(78)
i.e., (p)) is lower-bounder by a weighted ( distance between p and p** By the equivalence of norms in the Euclidean space, there exists some constant C such that ((p) > C ||p p 2
Proof. Similar to the proof of the original Lemma F.2, we separately consider the four possible scenarios where p belongs to one of the quadrant defined in Eq. (28).
1. Suppose pa pi and pt 2 PL. i.e. p Ni. Since Gi(p**) O, we have that
1 ( p,;
(1-11) -1-1) do(p. p) dolp"
- - G(p")) = Σ b, + c:
Σb,
(79)
By definition of the non-purchase probability, we observe that do(p. do(p" ,p*) > 0. Hence, the above equation implies that
(p))
P. P-PP.
E
Σ
1 L.P.
Σ
lp; p. "
(80)
by c
bb
P
(b:
where we use the fact that p: E P = pp.p] and the presumption E Ni.
2. Suppose pи S pi and Pr. > pi, i.e., p E N2. Again, using the fact that G₂(p**) = 0, we derive that
1
1
1
1
1
_1
((p) by + CH
PH
Pi
by. + Cr.
pi Pt.
(81)
+ |d (p. p) - du (p* p=))] + (d'' ,p"') - dr. (p.
Since p E N2, we have that di (p. p) du (p*t ,p*) > and dr (p* pp*)) - dr. > Hence, similar to the first case, it follows that
1
pi - pt*
(()) > bn + CH
+
N Σ
(82)
PH
PH
br. + CL
vi
pr.
bg + Cs "p,""""
31

---

The same conclusion can be drawn when UN,, and the proof is intrinsically the same. Hence, we conclude the proof of this lemma.
Finally, due Lemma E have that Ip-pp"lle S 1/C) Therefore, when G(p) O we also have Ip p" 2 (()), i.e., the price vector is already in (6)) neighborhood of the SNE. This completes the proof of Theorem
Appendix F Supporting lemmas
Lemma F.1 (Convergence of price to reference price) Let (p2) and (r') be the price path and reference path generated by Algorithm
[ with non-increasing step-sizes he2o such that lim 1/ = 0. Then, their difference {r" P reza converges to as goes to infinity.
Proof. First, we recall that DJ (b; + +c) (p r'), where G, r) is the scaled partial derivative
defined (25). Thus, it follows from Lemma E.3 that |D S (b; + c. Since Jr2 is non-increasing sequence with lime- v/ 0, for any constant 1/ > 0, there exists Ta E N such that |ny DiI S v for every To and for every E {H, L). Therefore, holds that
P.
p = Projp (pt + r/ D)) p s I mn
Vt TT
(83)
where the first inequality is due to the property of the projection operator. Then, by the reference price update, have for f. Tr and for i {H, I.) that
|r |rtt1
Pi c+1
ar! + (1 a appp p. pl
a (r) p\) + (p:t x+ pt)
(84)
I a |r ppl + p p
S a arrr p1 +
where the last line follows from the upper bound in Eq. T,, we further derive that
83
Applying Eq.
84 recursively from to
r( (+1
ps: [+]
S a
To
To Pi
a T-Tn
+ +1
T=Tr
(85)
<a 1- To (p p) +
Vi E [}
1-a"
Since be arbitrarily close to 0, we have that |r p/1 - 0 co, which completes the proof the convergence.
Lemma F22 Define the function ((p)
((p) sign(pH pn) Gn(p.p) sign(pž pL) Gr(p.p).
(86)
where (p, is the scaled partial derivative introduced in Eq. (25). Then, always holds that G(p) > 0, Vp E pay (p=* where pa* (p"t,P;;) denotes the unique SNE, and the function sign(.) is defined Eq.
Furthermore, for every >> O, there exists M. > such that g(p) 2 M. if if=(p) 2 where s(p) is the weighted ( liddistance function defined in Eq. 24
Proof. Firstly, by the first-order condition the SNE (see Eq. 16 ) we have Gp pp*)
Gr(p" ,p*))= = 0, which also implies G(p**) 0. Then, we recall the definition of four regions
Ni, N2, Ng. and N4 in Eq. (28). We show that (p)) > 0 when p belongs to either one of the four
regions.
32

---

1. When p E N1, i.e., PH > PH and 2 PŁ, the function (p)) becomes
((p) GH.(p.) p) - (P.
( +2
(by + CHDPH
(97 CLLPL
+ do(p.p) +1
(qy + CHIPH
(9y cL)PL
1 explan bnPH) + exp(as bLPT. +1,
(bu CH)PH
(br. + CI.pL
(87) where do (p,r) = dH (p. (p. denotes the no purchase probability. We observe from Eq. (87) that (p) is strictly increasing in pH and PL. Together with the fact that pH and pr are lowered bounded by pi and p respectively, and G(p"*) O, we verify that (()) E N1. With the similar approach, we show that when E N3. i.c. < Pÿ and PL S PT. it also follows that ((p) >
when
2. When p E N2, i.e., pH S PH and PL > Ph, the function ((p) becomes
G(p) = GH p) - GL(P.))
(bL + cLLPL (p.Pp dr
(bn CH JPH
(88)
exp(ax-baHin ЫнРн) -xpH))exp(aa PIPI)
(bn cH) (br. cr. 1+ explan bнрH) exp(ar. bI.p..)
By Eq. (8). we notice that G(p) under region N2 is strictly decreasing in pH and strictly increasing PL. Meanwhile, since ph S P.j pt > pt. and G(p**) 0, implies that ((p) > 0 when p E N2. Moreover, by similar reasoning, we show that when p E N4. i.e., PH 2 PH and PL < pf." the inequality ((p) also holds.
Finally, we are left to establish the existence of Mc. It suffices show that min s(p)=o
((p) > min ((p).
(89)
c(p)=c2
for every 61 > 62 > 0. Suppose ps = arg min m()==p)=e G()). Define p == (e2/61)p* + (1
<2/E1))**, which satisfies that sp = eg. Then, we have that
g(p sign(phi pit) (p 2) + sign(pž pf) ") ,p*)
sign - (μ - -ii) ( ,2²) + sign [ (pt - -Pi)) Gr.pp?,,p'
61
(90)
sign(y
pii) (n ppt) + sign(ri pi) Gr ,p²)
sign(pH - -ii) GH ,p') + sign(pī pf:) Gr(p") (t("",,p'')
where (Ai) follows from substituting pf" in sign(p,* -,.2) with p.2 = (e2/e1
(2-e2/Es)) "p
To see why (A2) holds, recall that we have shown in Eq. (87) and Eq. (8) that when two prices in the same region (see four regions defined in Eq. (8)). ). the price closer to p** in terms of the
metric E(-) has greater value of (p)). Since pd and p are from the same region and > 62, we conclude that min ((p) ((p"t) > ( 2 min G(p).
Lemma F3 Define function H()) as follows
H(p) (b + cH) G (p.p) (pit - PH) + (br, + ct.) Gz(p. (pt PL)
(91)
Then, there exist > 0 and open set U, 3 p* such that
H(P) 2 ||p p 1 Vp E Uy.
(92)
Proof. According to the partial derivatives in Eq. 998 and Eq. (98b) from Lemma F3 have
(G.P)
1
b, dp (1 -p.(ppp))):
Op, (b, + cpp
(93)
(p.P). = b . dd p) dp(p.
Op-s
33

---

Then, to compute the gradient VH(p) = ( (H(pp) we utilize partial derivatives
of (P p) Eq. (93) and obtain the partial derivatives H((p) for (H,
0H(P)
(G.(P.P)
(p," - p.) Gi(p, + (b_: +c. - -p_;) 8G 3G- p)
-(b; + +.))
Op:
8p:
Op:
pt"
- + (a)d 1) 1ith + (.) di(p.)) (1 - (p. - pi) p3
+ b,bbb (p dp. (n --s)).
(94)
From the definition of G)( in Eq. 31 and the system equations of first-order condition in Eq. (16). we have (p p=*) 1/ (b, + pp -d,;" 1) 0. where d := d, (pp",, .p*)) denotes the market share of product at the SNE. Thereby, it follows that VH(p"*) = 0.
Next, the Hessian matrix (p) evaluated p** be computed as
{²H(p**)
PH(("')
0pn
Opn@pr.
PH(("*))
(²H(("**)
Opr.0pH
Opr.2
2p
+ 2bH + +cw) dif (1 - -djf),
- -[bm + ct.) + + br + +cm]] djj
(Fji)3
2p (pi+)3
[bu + cL) + (bu cx)] d#d
+ 2b2 + tc)) dī dī²)
2(b + cH) (1 (1-dj) dzi) [bb + ch) - cHdæ],
- (bb + cL) + by (by + cH]] di di
(bz oL) + bz ch)l d
2(b2 + cL) (1 (1-dī;) (bb + cL) cyd
Note that the last equality results again from substituting in the identity G,(p**, = 1/((b+ +
c:) pi*l + (d,* - 1) = 0.
34

---

The diagonal entries of (2H('"") are clearly positive. For i E {H, L), define k; :- b,/(b; + +a) [0, 1]. Then, the determinant of (²H(p"*) can be computed as follows:
det (V²H(D"')) 4(b cH) + ot) (1 - dd) (1 dī,) [(H +cH) cHdHi [bb + +ct) crdi]]
(lbu(br Ct) + br (b# + cH)] dif dī
(bи + cH) (b2 + tz)² (4(1- (1 dī [1- (1- (1-k))d71
-(k + k2) 2
(d' d'""" di:))
(A)
2 4(bu en (bn + tz)2 (11- (1 - df [1 11 )d))d 1k1,kk)) (r.
(a2z dl (dz7 2)
(4.)
2 4(bH + cH (b2 + tz) di d2 (11 (1 kz )d [ (1 - KL) d%[1 d'i di
(Ag)
2 A(bu cn en) (br =z)² dz (1 (1-d -'fp dz') di
4(bx ch (b2 + +z)2 dij dr. (1 (1- d'j dī"))
(A)) 0,
(95)
where inequalities respectively result from the following facts (A1): kH + kg S 2: (A2): d: >
d=; for i (H, L): (Aa): 1 1- k; S 1 for E {H, L): (A4): di + di < 1. Thus, we conclude that (HH(p**) is positive definite.
By the continuity of (2H(p), there exists some constant 7 > and a open set Uy 9 p** such that (PH(p) = 2, Vp Un. where is the x 2 identity matrix. Using the second-order Taylor expansion at p for all Uy, there exists p E Uy such that
H()) H(p"*) VH(p"*) (p p=") - 2 -p0) vHH(D) (p (p-"")
1 (p- (p- T. v²H(f) (p-pr (p-p"*)
(96)
1
(p- p'1) T 2712 pp""")
2
=>lpp p*1
where the second equality arises from that H(p"*) = 0 and VH(p"*) = 0.
Lemma F.4 For any product E (H, L}. let
G.(p) = sign (p p.) G. (p.
(97)
where Gp r) is the scaled partial derivative defined in Eq. 25 as lpt* pel increases, and
Then, G((p) is always increasing
1. when p E N₁ U Na (see the definition in Eq. 28 (p( is decreasing as 1p p-il increases;
2. when p E N2 U N4. G,(p) is increasing as 1p p-il increases.
Proof. Without loss of generality, consider the case that product i = Hl and product -i L.
Apparently, we have sign (p#t pH) < 0 in Ni U N4. and sign (p7 PH) > 0 in N2 N3 by definitions (see Eq. 28 ). On the other hand, by Eq. (88) in Lemma F5 it holds that HG (p. /0pup and dc (p. ppppp > 0, Vp p?. Thus,
1. in N₁ 4., GH (p. p) is decreasing as pp pHl increases; in N₂ N,,, GH (p.p) is increasing as 1p PHl increases;
35

---

2. in N1 22, GH p) is increasing as IpE" PL increases; conversely, GH (p. is decreasing as Ip PL increases in N3 U N4-
The final results directly follows by combining the above pieces together.
Lemma E5 Let (p, be the scaled partial derivative defined in Eq. (25). then partial derivatives of G.(P.r) r) with respect to and are given as
(G.
0p: (b, c,ppp (b. + c.) d.(p,r) (1 (-d(())))):
(98a)
(G, (b + c.i) dp. d_.(p.r;;
(98b)
Op-i
@G. r) = (.dd(((p.)) (1 - (p.rr));
(98c)
Òr;
(G, -c_; -c...d((prr) (p.
(98d)
Ør-s
Meanwhile, Gi(p, r) and its gradient are bounded as follows
G.( S Ma. [|, r)ll2 St,, Vp,r E P and vi E (H, L}.
(99)
where the upper bound constant Mg and the Lipschitz constant l, are defined as
MG == max
{ (by + cL)D (bL + cL)D
+ 1,
4 4V c4 oz
(100)
Proof. We first verify the partial derivatives from Eq. 98a) to Eq. (98)):
(G,(p.r)
(p.r).
Öp:
(b: + c)pp
Öp:
(b, + ci) exp (u)(p.rr)) (1 + exp (u-((p-sr-s))
(be + G)pt
(1 + exp (us(pe) exp exp((uill (v-((-iir--))
(b, + c.) d((p.r) (1 d((pr))).
(b: + c.)p
(101)
@Gv(p.r)
(p.r)
Öp-i
Öp_i
(b- + c- exp (us(pi, ri)) exp (I=((=-;,--)))
exe (u:(p,, r:)) + exp (u-r(p-;;
=b_, - (p. d_.(p.r..
Then, the partial derivatives with respect r, as shown Eq. (9cc and Eq. (9d). can be similarly computed.
In the next part, show that (p, is bounded for p. p2:
1
[.(p =
+ d, dg(p,, r) -
(b. + c:pp
1
+ +ld((p,r) -1
(102)
(b. + c)pp
+ 1.
(b: + G)p
36

---

Hence, it follows that G. r) for every i E {H, L} is upper bounded by
1
[G(p,) max
+1 Ma, tp, (103)
(bu + et) (br + cz)p
Finally, we demonstrate that |V, r)ll is also bounded vp,r E p2 and Vi E (H, LJ. From Eq. (98c) and Eq. (98d), have
(V..((p.r) (a: (e.d((p.r- (1-d(p.r))) + d_
= (d((p.)) (1- (1.)( 2 + +ci (d((p.r) dp.,) 2
(104)
1 ( c
where the inequality follows from the fact that yy S 11/4 for any two numbers such that æ, > and x + y S 1. Thus, it follows that (V,, s (1/4) + = I,, Vp,r p and Vi E L..
Limitaions
This is a theoretical work that concerns with algorithm design in competitive market, with the primary goal of learning stable equilibrium. The consumer demand follows the multinomial logit model, and we assume that their price/reference price sensitivities are positive, i.e., bx, > 0. The feasible price range P = [p. p] is assumed to contain the unique SNE, with the lower bound >> We have justified both assumptions in the main body of the paper (see the discussion below Eq. and Proposition 3.T.
The convergence results in the paper assume the firms take diminishing step-sizes (n')) with Ei 17 co, which common in the literature of online games (see, e.g., [5] We also discuss the extension to constant step-sizes in Remark 5.3
37


Reviews:
[{"review_id": "lf9RG79qbE", "reviewer": "Reviewer_CZUh", "summary": "This paper investigates the problem of dynamic pricing in a competitive environment, where there are two revenue-maximizing competing firms selling substitutable products to customers and each of them has no access to the information of its competitor. In addition, customer’s utility follows a linear function with current price and reference prices, while the demand function is captured by a MNL model. The authors propose a simple online projected gradient ascent algorithm to update the price based on the historical prices and observed demands. The main contribution of this paper is that the authors provide the convergence guarantee of this algorithm to a unique stable Nash equilibrium and shows the convergence rate when choosing step size optimally.", "questions": "See above.", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. This paper analyzes a very interesting problem --- dynamic pricing in the presences of competition across firms and reference prices of customers and provides a very succinct formulation to abstract this problem.\n\n2. The paper is well-written and I really enjoy reading this paper even though I don't have much background on MNL model.\n\n3. The results are promising that the authors show that a simple online projected gradient ascent algorithm works well in practice and it can converge to the unique stable NE. \n\n4. The paper is technically solid and the proof is nontrivial to me, however, I have no expertise to determine the novelty of the proof shown in the paper compared with the related work [21].", "weaknesses": "In general, I find the paper interesting, technically solid and shows a very promising result. Though I still have some questions needed to be clarified.\n\n1. I find the uniqueness of the stable NE in this paper very important and crucial to the convergence results. Can authors discuss whether this property can be generalized? In addition, with this property, can we replace online projected gradient ascent algorithm by other online optimization algorithm to achieve similar convergence rate?\n\n2. If I understand correctly, the authors need $d_i(p^t, r^t)$ can be directly observed, right? If so, please clarify it more explicitly in the algorithm.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for appreciating our work. We hope our responses below provide further clarity.\n> S4: Comparison with the related work [21].\n\nA: We thank the reviewer for the feedback. We'd like to clarify the distinctions between our work and [21] from two perspectives.\n\n**Model Formulation:**  Our paper employs the MNL demand, which is distinct from the linear demand used in [21]. The linear demand in [21] results in a quadratic revenue function, which possesses favorable properties such as supermodularity and concavity. These properties  facilitate the convergence analysis of online games (see e.g., [R1]). On the other side, the revenue function under the MNL model lacks these properties, and it does not satisfy other useful characteristics such as cocoercive or variational stability (see the discussion in Section 2). Moreover, in Section 4 and Appendix A, we demonstrate that standard techniques from multi-agent games and dynamical systems are also not applicable to our problem, making it necessary to develop a novel analysis for the convergence of the OPGA.\n\nBesides the demand, another difference lies in the reference price formulation. In particular, the duopoly competition in [21] assumes that the two firms share a common reference price, whereas we allow firms to have different reference prices. Our formulation offers greater flexibility in modeling. We note that our analysis also applies to the scenario where two firms share a common reference price.\n\n**Proof Technique:** While both our work and [21] utilize a two-part proof for showing the asymptotic convergence, the essence of our proofs is significantly different from that of [21]. A key result in [21] is their Lemma 9.1, which ensures the following inequality holds globally (see Eq. (19) and Eq. (20) in [21] and note that their problem adopts the minimization formulation): $\\sum_{i} (g_i^{\\star\\star}-g_i^t)(p_i^{\\star\\star}-p_i^t) > 0$, where $g_i$ is used to denote the derivative of their revenue function. This property is known as variational stability (see e.g., [R2]), under which the convergence results have been established for various algorithms. Our work, however, doesn't benefit from such properties. To address this, we introduce two distinct metrics respectively for the two parts of our convergence analysis. In Part 1, we divide the feasible price range into four quadrants with the SNE $\\mathbf{p}^{\\star\\star}$ being the origin. Our proof is based on drawing contradiction: suppose that the price vector does not converge to the SNE, we can prove the following in sequence (1) the price path cannot always stay in the same quadrant; (2) when $t$ is large, the price path can only oscillate between adjacent quadrants; (3) the price path would converge to the boundaries between some adjacent quadrants; (4) afterward, the price path would stay close to the boundaries and converge to the SNE, resulting in the contradiction. In Part 2, we exploit a local property of our model (see Lemma E.3) by showing that the auxiliary function $\\mathcal{H}(\\mathbf{p})$ is lower-bounded by some quadratic function around the SNE. This enables us to establish our final conclusion.\n\nIn summary, we believe that our paper is technically novel and significantly different from [21].\n\n> W1: I find the uniqueness of the stable NE ... by other online optimization algorithm to achieve similar convergence rate?\n\nA: Thank you for your insightful comments. The uniqueness of SNE plays an important role in the convergence analysis of this paper. This property naturally results from the MNL demand model used in this paper. Yet, we believe similar convergence results can also be derived for certain models where the SNE is not unique.\n\nIn fact, we are currently considering an extension to the asymmetric reference effects, which exhibits the non-uniqueness property as the reviewer mentioned. Under asymmetric reference effects, the utility for product $i$ changes to \n$$u_i(p_i^t, r_i^t)=a_i-b_i \\cdot p_i^t+c_i^{+} \\cdot(r_i^t-p_i^t)_{+}+c_i^{-} \\cdot(r_i^t-p_i^t)\\_-,$$\n\nwhere the notations $(\\cdot)\\_{+}:=\\max \\\\{\\cdot, 0\\\\}$ and $(\\cdot)\\_{-}:=\\min \\\\{\\cdot, 0\\\\}$ are adopted to account for consumers' potentially asymmetric reactions to discounts and surcharges, respectively. When $c_i^- <c_i^+, \\forall i\\in \\\\{H,L\\\\}$ (referred to as the loss-averse scenario), it can be shown that there exists a set of SNEs. With some slight modifications of the OPGA, we have established the convergence result. The difference is that, instead of converging to a unique SNE, the algorithm converges to the set of SNEs, and the limit may depend on the initialization. Due to the length restriction on the rebuttal response, we regret that we couldn't elaborate more on this extension. If the reviewers are interested, we are delighted to share more details about this modified algorithm and analysis during the discussion period.\n\nFinally, we believe it is possible to generalize to other online learning methods, such as online mirror ascent (OMA). In Figure 1 of the rebuttal PDF, we verify that another variant of OMA, the Multiplicative Weight Update (MWU) method, also converges to the SNE. Thus, we expect the general OMA can also converge for our problem. We kindly refer the reviewer to our response to reviewer **M19q (Q1)** for a more detailed discussion on OMA and a potential method to generalize our proof.\n\n\n> W2: The authors need $d_i(p^t, r^t)$ can be directly observed.\n\nA: Yes, we have discussed this assumption in Section 3.2. In the revised paper, we'll declare this requirement more clearly in Section 4 when presenting the OPGA. Due to the length limit, we kindly refer the reviewer to **General Response Q1 and Q2** for a detailed discussion about the assumption needed for observing $d_i(\\mathbf{p}^t,\\mathbf{r}^t)$.\n\n### Reference\n[R1] Bandit learning in concave N-person games.\n\n[R2] Learning in games with continuous action sets and unknown payoff functions."}, {"review_id": "JOXsWUeoEg", "reviewer": "Reviewer_M19q", "summary": "The authors' objective is to develop an algorithm to aid the firms in converging to a stationary Nash equilibrium (SNE). In pursuit of this, the authors have:\n\n* Proposed an online projected gradient ascent (OPGA) algorithm.\n* Proven the global convergence of the OPGA to SNE within the given problem setting.\n* Established the convergence rate of the proposed algorithm to SNE.", "questions": "Despite the significant merits of the work, I do have a few queries. If the authors could address these, I would be more than pleased to highly rate the paper:\n\n* My first question might be rather straightforward. Could you please elaborate on why online mirror descent, proposed to solve a similar problem, does not apply in your problem setting? If online mirror descent does apply, what advantages does your OPGA algorithm offer?\n* As for the assumptions listed above, I'm somewhat puzzled:\n    - The last assumption posits that each firm can access its own demand from the last period. However, I would argue that this \"demand\" differs from the one defined by\n$$d_i(\\bm{p}^t, \\bm{r}^t) = \\frac{\\exp(u_i(p_i^t, r_i^t))}{1+\\exp(u_i(p_i^t, r_i^t)) + \\exp(u_{-i}(p_{-i}^t, r_{-i}^t))}.$$ \nwhich, to the best of my understanding, represents the market share of firm $i$ at period $t$. While the \"demand\" that firm $i$ can access using the proposed method is the quantity of product sold by firm $i$, such as 1000 electronic devices. Aren't these two different concepts? I may be overlooking something, but it would be helpful if you could clarify the potential connection. It would also be instructive if you could provide an example explaining the use of $d_i(\\bm{p}^t, \\bm{r}^t)$ in the numerical example.\n    - It is assumed that $b_i$ and $c_i$ are known to firm $i$. However, I believe these parameters can only be learned from data. Therefore, what is the role of the learning process in the convergence to SNE? Do we handle them as a two-stage problem, or can we combine the two learning processes?", "limitations": "NA", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "I commend the authors for their clear and engaging writing. The background, related literature, concepts, algorithms, and more, are all explained lucidly. The proposed algorithm, and the results derived from it, are noteworthy contributions to the field. The technical addition to extend the algorithm's convergence beyond linear demand and convex loss function is particularly valuable.", "weaknesses": "I noticed certain assumptions and explanations that might require further substantiation. Please refer to the \"questions section\" for a detailed account. I believe addressing these points could add considerable depth and credibility to the paper's findings and arguments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the insightful questions. Please find our responses below. We highly appreciate your re-evaluation of our work and a kind reconsideration of the review score.\n> Q1: Discussion about online mirror descent.\n\nA: For consistency, we assume a maximization form and use the term Online Mirror Ascent (OMA).\n* Firstly, we clarify that we did not eliminate the application of OMA to our problem. We are aware that OMA is a widely used online learning method, and OPGA is indeed a special case of OMA by using the Euclidean distance as the Bregman divergence. We've conducted numerical tests on other OMA variants (see Figure 1 in the rebuttal PDF), such as the multiplicative weight update (MWU). The results suggest that OMA could very likely converge to the SNE for our problem.\n* We choose OPGA due to its simplicity, efficiency, and the geometric structure of our problem. The general OMA is known for its capability in exploiting specific geometric structures of the problem (e.g. when the feasible region is a probability simplex). However, the feasible price region in our problem is just a rectangle, making the simple gradient update a natural and intuitive choice. Indeed, our numerical results also demonstrate that OPGA and MWU show comparable performances with OPGA exhibiting less fluctuant price updates at the early stages. Besides, with OPGA, we do not suffer from the complexity of evaluating certain complicated mirror maps. \n* Lastly, we discuss a potential way to generalize our proof to OMA. Let $\\Phi(x)$ be a $\\kappa$-strongly convex function and define the associated Bregman divergence as $D_\\Phi(x,y)=\\Phi(x)-\\Phi(y)-\\langle\\nabla\\Phi(y),x-y\\rangle$. The OMA update can be written as$$p_i^{t+1}=\\text{Proj}_{\\mathcal{P}}[(\\nabla\\Phi)^{-1}(\\nabla\\Phi(p_i^t)+\\eta^t D_i^t)].$$\n\n    Recall that Eq. (29) and Eq. (52) are two key inequalities we use for the convergence of OPGA. Now, we derive a corresponding inequality for OMA and use Bregman divergence to measure the convergence. By the generalized Pythagoras identity, we have$$D_\\Phi(p_i^{\\star\\star},p_i^{t+1})\\leq D_\\Phi(p_i^{\\star\\star},p_i^t)-D_i(p_i^t,p_i^{t+1})+\\eta^tD_i^t(p_i^{\\star\\star}-p_i^t+p_i^t-p_i^{t+1}).$$\n\n    Applying the strong convexity to $D_i(p_i^t,p_i^{t+1})$ and maximizing the right-hand side (RHS) w.r.t. $(p_i^t-p_i^{t+1})$, we derive$$D_\\Phi(p_i^{\\star\\star},p_i^{t+1})-D_\\Phi(p_i^{\\star\\star},p_i^t)\\leq \\eta^tD_i^t(p_i^{\\star\\star}-p_i^t)+\\frac{(\\eta^tD_i^t)^2}{2\\kappa}. (\\*)$$\n    \n    Similar to the proof in our paper, the RHS of $(\\*)$ is controlled by the first term when $\\eta^t$ is small. In addition, when $\\mathbf{r}^t$ and $\\mathbf{p}^t$ are close, we have $D_i^t\\approx(b_i+c_i)\\cdot G_i(\\mathbf{p}^t,\\mathbf{p}^t)$. Hence, by Lemma E.2, we can show from $(\\*)$ that the price of at least one product $i$ will strictly approach the SNE during the update unless it is already close to $p_i^{\\star\\star}$. After $\\mathbf{p}^t$ enters a neighborhood of SNE with a small enough step-size, we consider the sum of Eq. $(\\*)$ for two products. By Lemma E.3, we can show that the RHS of the summation is non-positive (compare to Eq. (52)-(54)), which implies that the price will stay in the neighborhood.\n\n    While there may exist subtleties to work out, we believe this proof sketch is a promising starting point for proving the convergence of OMD. A comprehensive study on this topic will be part of our future work.\n> Q2-1: Connection between demand (quantity sold) and market share.\n\nDue to the length limit in the response for each reviewer, we kindly refer you to our **General Response Q1 and Q2**, where we clarify the assumption and the connection between demand and market share.\n> Q2-2: Estimation of $b_i$ and $c_i$.\n\nA: Thank you for your insightful feedback. We believe both approaches you mentioned are feasible. Below, we elaborate on the estimation process.\n* When treated as a two-stage problem, the firms can estimate $b_i,c_i$ from historical data. This falls in the domain of MNL parameter estimation, a well-explored topic in economics. The most common method is maximizing the log-likelihood, i.e., the product of market share for all firms. Notably, [R1] shows that the log-likelihood function for MNL is globally concave in parameters $(\\mathbf{a}, \\mathbf{b}, \\mathbf{c})$. This nice concavity property facilitates the computational algorithms. Specifically, several prominent algorithms (i.e., (1) Newton-Raphson, (2) BHHH-2 [R3], and (3) the steepest ascent) studied in Chapter 8 of [R2] are all guaranteed to get an improved estimation at each iteration. We refer the reviewer to [R2] for a more detailed analysis of the strengths and drawbacks of each algorithm.\n* Second, the learning process of $b_i, c_i$ can also be integrated with the OPGA aglorithm. Indeed, existing papers like [R4, R5] have done so for the monopoly setting. The benefit of this method is that little historical data is required, and the firms can refine their estimations along the repeated competition. Meanwhile, the firms may incur additional regret during the exploration stage. However, as long as firms can estimate $b_i, c_i$ accurately, our existing analysis ensures that the firm can reach the SNE. Hence, the overall regrets for both firms are still sublinear.\n\n    Finally, we remark that, when $b_i$ and $c_i$ must be estimated from data, it is more practical to assume that firms can obtain a noisy estimation for the derivatives. Though our current analysis is based on the exact gradient, we believe the generalization to the noisy first-order feedback is a promising yet interesting future research.\n\n### Reference\n[R1] Conditional logit analysis of qualitative choice behavior.\n\n[R2] Discrete choice methods with simulation.\n\n[R3] Estimation and inference in nonlinear structural models.\n\n[R4] Multi-product dynamic pricing in high-dimensions with heterogeneous price sensitivity.\n\n[R5] Demand learning and pricing for varying assortments. "}, {"review_id": "X7M5g0QD0V", "reviewer": "Reviewer_8Smn", "summary": "The author consider a multi-period pricing competition problem between two firms, dubbed H and L. Each of these firms sells 1 product. At each time step, the demands on each product is governed by an MNL model, which is paramaterized by not only the firms' offered prices in the current time period, but also the current reference prices of the firms. These reference prices are dependent on the past prices. In the game theoretic setting, each of the firm is to set prices under the uncertainty on the other firms strategy. The authors' main result is that, when each of the firms applies the standard online gradient descent algorithm, they both converge to a stationary Nash equilibrium, and the rate of convergence is also provided.", "questions": "(1) Can the authors provide a discussion on how easy or how difficult it is to generalize from the Gumbel distribution noise to a more general class of noise (for example, 1-subGassuian)?\n\n(2) As shown in Figure 1a, b, the choice of learning rate is rather important. Can the authors demonstrate a plot with the setting of learning rate $\\eta^t = \\Theta(1/t)$ in Theorem 5.2? I think it will be more informative than setting $\\eta^t = 1/\\sqrt{t}$ in Figure 1a. In addition, can the authors provide explicit expressions for the coefficients $d_r, d_p$ in Theorem 5.2, on how they depend on the MNL assumption and the model parameters?", "limitations": "This is a theoretical work, there is minimal negative societal impact.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The pricing problem combines both the game theoretic element in a duopoly pricing setting, as well as the reference price setting, which are both well known in the literature. The provided algorithm is sensible and reasonable, and these results are supported with numerical experiments. The analysis in the gradient descent algorithm seems interesting, since it seems to deviate from the traditional Online Gradient Descent works that require convexity.", "weaknesses": "- The model assumption on the demand model seems quite strong, since it requires the random noise to follow a particular probability distribution (Gumbel), in order for the result to hold. While there is another linearity assumption on the utility, I find it a milder assumption than the Gumbel assumption. While I understand that the Gumbel distribution, which gives rise to the MNL model, is a common assumption in assortment optimization, I find that it could be a limiting assumption in the pricing setting. Crucially, if the noise distribution is changed, it is not quite clear of the OPGA still converges to a stationary Nash equilibrium.\n\n- While Theorem 5.2 is a more refined form than Theorem 5.1 in that the former provides a finite time performance guarantee, I am not clear on what is the hidden parameter in the $\\Theta(\\cdot)$ notation for the learning rate $\\eta_t$. While the OPGA can be implemented with any sequence of learning rates, it is desirable to have a set of default learning rates that come with an explicit performance guarantee.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful comments. We hope the responses below address your concerns. We highly appreciate a re-evaluation of our work and a kind reconsideration of the review score.\n> W1: The model assumption ... equilibrium.\n\nA: We agree with you that the Gumbel noise is somewhat restrictive. Yet the MNL is by far the most popular choice model, due to its elegant closed-form expression for market share. Beyond the assortment problem, the MNL choice model and its variants (e.g. nested logit) have also been widely studied in the pricing literature. We kindly refer the reviewer to [R1-- R9] for notable works on the pure pricing problem under the MNL and its variants.\n> W2: While Theorem 5.2 ... performance guarantee.\n\nA: We appreciate the reviewer's advice about having a default learning rate that guarantees the $\\Theta(1/t)$ convergence rate. The hidden parameter in the choice of $\\eta^t=\\Theta(1 / t)$, denoted by $d_\\eta$, hinges on Eq.(72):$$(\\gamma d_\\eta-1)d_p\\geq C_3.(\\*)$$\n\nRecall that $\\gamma$ is defined in Lemma E.3 and $C_3>0$ is defined in Eq.(68). Hence, if $\\gamma d_\\eta-1>0$, there exists suitable $d_p$ to make Eq.$(*)$ hold, which subsequently guarantees the $\\Theta(1/t)$ convergence rate. Therefore, analytically, firms can adopt any step-size $\\eta^t=d_\\eta/(t+1)$ with $d_\\eta>1/\\gamma$. The only subtlety lies in $\\gamma$, whose exact value depends on both firms' parameters and the SNE market share (Eq.(89)) and the derivation afterward). Below, we describe a mechanism for firms to obtain a suitable step-size without disclosing private information.\n\nIt suffices to find a lower bound $\\underline\\gamma\\in(0,\\gamma)$ and let the firms agree on the choice $d_\\eta=1/\\underline\\gamma>1/\\gamma$. By Eq.(89), we have$$\\gamma\\geq\\min_i\\{b_i+c_i\\}\\cdot\\min_i\\{d_i^{\\star\\star}\\}\\cdot(1-d_H^{\\star \\star}-d_L^{\\star \\star}).(\\**)$$\n\nIn Prop 3.1, we establish lower and upper bounds for $p_i^{\\star\\star}$. For brevity, denote Eq.(6) as $m_i<p_i^{\\star\\star}<M_i$, and the utility at SNE as $u_i=a_i-b_ip_i^{\\star\\star}$. Then, each firm $i$ can bound $u_i$ by $u_i^m:=a_i-b_iM_i<u_i<a_i-b_im_i=:u_i^M$. Instead of sharing the true values, each firm $i$ can disclose an arbitrary lower bound $m_i^{bc}>0$ for $b_i+c_i$, and two arbitrary numbers $\\underline u_i^m$ and $\\overline u_i^M$ with $\\underline u_i^m\\leq u_i^m$ and $\\overline u_i^M\\geq u_i^M$. Using Eq $(**)$, the two firms can compute that $$\\gamma\\geq\\min_i\\\\{m_i^{bc}\\\\}\\cdot\\min_i\\left\\\\{\\frac{\\exp(\\underline u_i^m)}{1+\\exp(\\underline u_i^m)+\\exp(\\overline u_{-i}^M)}\\right\\\\}\\cdot\\frac{1}{1+\\exp(\\overline u_{H}^M)+\\exp(\\overline u_{L}^M)}=:\\underline\\gamma.$$\n\nThus, firms can obtain the constant $d_\\eta = 1/\\underline{\\gamma}$ without disclosing their information.\n> Q1: Can the authors ... (for example, 1-subGassuian)?\n\nA: We kindly refer the reviewer to **General Response Q3** for background on choice models and the popularity of Gumbel noise. Shifting from Gumbel noise introduces challenges. For example, multivariate Gaussian noise results in the probit model, while arbitrary noise distributions lead to the mixed logit model. Both lack closed-form expressions for market share [R10], thereby making the properties of their revenue functions undefined and elusive. Further, changes in noise distribution can significantly affect equilibrium behavior in price competition [R5]. Specifically, while MNL models guarantee the existence and uniqueness of a Nash equilibrium (NE) [R11], such NE may not even exist in models with general noise distributions [R5]. This absence creates significant hurdles, as the existence of NE is fundamental for achieving a stable equilibrium.\nExtending noise distributions beyond Gumbel is an intriguing research direction, with the key first step may be to show that NE exists under distributions of interest.\n> Q2: As shown in Figure 1a, b, ... parameters?\n\nA: We performed additional experiments with $\\eta^t=\\Theta(1/t)$ (see Figure 2 in the rebuttal PDF), and we will add this figure to the revised paper.\nBelow, we elaborate on the expressions of $d_p$ and $d_r$. According to Eq.$(\\*)$, $d_p$ depends on the choice of $d_\\eta$. Without loss of generality, let $d_\\eta=2/\\gamma$ (it is easy to observe $d_\\eta = O(1/\\gamma)$ yields the best $d_p$). By Eq.$(*)$, it suffices to take $d_p = C_3$ (see definition in Eq.(68)), which further implies that $d_p\\leq C_1(d_\\eta)^2+d_\\eta kd_{rp}$ (the definitions of $C_1,k,d_{rp}$ can be found in Eqs.(54), (59), and (65)). After unfolding the definitions and using simple algebras, we observe that $$C_1=O(\\sum_{i} (b_i+c_i)^2/\\underline{p}^2)$$$$k= O((c_H+c_L)^2\\sum_{i} (b_i+c_i)^2/\\gamma)$$\n$$d_{rp}=O\\left(\\frac{1+\\alpha^2C_1}{(1-\\alpha^2)^2\\gamma^2} + \\frac{3+\\alpha^2}{1-\\alpha^2}(\\bar{p}-\\underline{p})^2\\right).$$\n\nCombining the above pieces, we obtain that $$d_p = O\\left(\\frac{B^2}{\\gamma^2(1-\\alpha^2)}\\left[\\frac{B}{\\gamma^2\\underline{p}^2(1-\\alpha^2)}+(\\bar{p}-\\underline{p})^2 \\right]\\right),$$\n\nwhere $B=\\sum_i(b_i^2+c_i^2)$. Finally, as $d_r=2d_p+2d_{rp}$ (see Eq.(76)), we conclude that $d_r$ has the same order as $d_p$.\n### Reference \n[R1] Optimal bundle pricing.\n\n[R2] Product line selection and pricing with modularity in design.\n\n[R3] Pricing multiple products with the multinomial logit and nested logit models: Concavity and implications.\n\n[R4] Optimal pricing for a multinomial logit choice model with network effects.\n\n[R5] Price competition under mixed multinomial logit demand functions.\n\n[R6] Multiproduct price optimization and competition under the nested logit model with product-differentiated price sensitivities.\n\n[R7] Dynamic pricing of perishable assets under competition. \n\n[R8] Optimal pricing of correlated product options under the paired combinatorial logit model.\n\n[R9] Optimizing Risk-Balancing Return Under Discrete Choice Models.\n\n[R10] Discrete choice methods with simulation.\n\n[R11] Discrete choice theory of product differentiation."}, {"review_id": "HejuS1OZ84", "reviewer": "Reviewer_aAW7", "summary": "The paper studies gradient descent dynamics in duopoly competitions with reference effects and logit demand. \nConvergence results are proven to show that Online Projected Gradient Ascent (OPGA) with decreasing step size converges to a stationary Nash equilibrium. This is a novel result requiring new analysis because the considered game is neither convex nor strongly monotone or variationally stable. The setup and results extend the ones of (Golrezaei et al., 2020) which however considered linear demands and a uniform reference price. ", "questions": "How realistic is it for the competing firms to compute exact gradients? Which set of information is required to do so at each round?\nAlso, as pointed out by the authors, one-point gradient estimates could be obtained. Does the current analysis allow draw conclusions on the resulting convergence results?", "limitations": "Limitations are discussed in combination with future directions.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper is well written and the results are sound and original\n- The authors did a good job of connecting the considered games with the existing literature and explaining why existing results do not apply\n- The proven theorems are novel and the analysis seems somewhat original. ", "weaknesses": "- The analysis is very specific to the considered duopoly games. Although they are widely studied in the Marketing and Management literature, they may not be of high interest to the machine learning community. That said, online learning and convergence to NE is a relevant topic within NeurIPS.\n- The authors repeatedly refer to no-regret (even in the title). However, the notion of regret is never defined and -- moreover -- bounds on the regret are not provided. I agree that last-iterate convergence to NE is a stronger guarantee, but it is not clear to me that this implies sublinear regret.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive feedback. Please find our responses below. We hope they address your concerns and provide further clarity.\n> W1: The analysis is ... relevant topic within NeurIPS.\n\nA: We understand your concern and agree that deriving convergence results for general online games is a meaningful research direction. Meanwhile, we believe that analyzing specific instances with practical importance is also a great contribution to the community. In our competitive framework, we consider a popular demand model, namely the MNL, which is a famous choice model from [R1] and has been empirically validated for its good representation of consumer purchasing behavior. Additionally, the general convergence results for online games are often built on certain assumptions, such as concavity [R2], strong monotonicity [R3], or variational stability [R4]. Hence, the general results usually fail or become weaker when applied to problems without corresponding properties, such as our problem. Yet, by leveraging the distinctive properties of the MNL model and developing a new line of analysis, we demonstrate that the global convergence and a $\\Theta(1/t)$ rate still hold for our problem under minimal assumptions (the market feedback mechanism). For the above reasons, we believe our work aligns well with the scope of NeurIPS in terms of both practical significance and theoretical analysis.\n> W2: The authors repeatedly refer to no-regret ... sublinear regret.\n\nA: We appreciate the reviewer for pointing out the source of confusion. We will include the following definition of regret in our revised paper. \n\nIn a competitive framework, the ***regret*** of player $i$ is a quantity used to measure the performance of an online learning algorithm, which is the difference between the total reward of the best fixed action in hindsight and the realized total reward of player $i$ over $T$ periods. Formally, the regret of player $i$ at period $T$ is defined as $$R_i^T:= \\max_{p_i \\in \\mathcal{P}} \\bigg\\\\{\\sum_{t = 1}^T \\Pi_i\\big((p_i,p_{-i}^t), \\mathbf{r}^t\\big)\\bigg\\\\} -\\sum_{t=1}^T \\Pi_i\\big((p_i^t,p_{-i}^t), \\mathbf{r}^t\\big).$$\n\nThen, an algorithm is said to be ***no-regret*** if $R_i^T$ grows sub-linearly with respect to $T$ for every player $i$. The established results in our paper imply that OPGA is no-regret, with reasoning as follows:\n* The convergence of the OPGA algorithm to the SNE (see Theorem 5.1 of the paper) guarantees that $\\lim_{t \\rightarrow \\infty} (\\mathbf{p}^t, \\mathbf{r}^t) = (\\mathbf{p}^{\\star\\star}, \\mathbf{r}^{\\star\\star})$. Hence, when $T$ is sufficiently large, by the definition of SNE, the best fixed price in hindsight for firm $i$ is the SNE price $p_i^{\\star\\star}$ (note that when $p_{-i}^{t}\\rightarrow p_{-i}^{\\star\\star}$ and $\\mathbf{r}^t\\rightarrow \\mathbf{p}^{\\star\\star}$, then $p_i^{\\star\\star}$ is the unique optimal price for firm $i$).\n*  In the meanwhile, since the revenue functions are Lipschitz continuous in prices and reference prices, we have that $\\lim_{t\\rightarrow\\infty}\\big\\\\{\\Pi_i(\\mathbf{p}^{\\star\\star},\\mathbf{r}^{\\star\\star})-\\Pi_i(\\mathbf{p}^t,\\mathbf{r}^t)\\big\\\\}\\rightarrow 0$. Therefore, it follows that $\\lim_{T\\rightarrow \\infty} {R_i^T}/{T}  = 0$, as $T\\rightarrow \\infty, \\ \\forall i\\in \\\\{H, L\\\\},$ which indicates that $R_i^T = o(T)$, i.e., the regret is sublinear.\n\nFinally, we remark that our result is stronger than merely being no-regret, as the no-regret alone does not guarantee convergence at all, let alone the convergence to SNE. In fact, the players may exhibit entirely unpredictable and chaotic behaviors under a no-regret policy [R5], with the only exception being the finite game, where players only compete for finitely many rounds (note that our problem does NOT fall under this category).\n\n> Q1: How realistic ... compute exact gradients? Which set of info ... round? \n\nA: Thank you for your comments. Computing the gradient $D_i^t$ in Eq. (9) of the paper is feasible and realistic in practice. For firm $i$, the required information includes its previously posted price $p_i^t$, its own sensitivities to price and reference price $(b_i, c_i)$ (which can be estimated from historical data), and its demand from the last period. We note it is reasonable to assume that the firm has access to the aforementioned information, as it exclusively pertains to its internal data, and not that of its competitor. This also aligns with the opaque market setup in our paper, where both computing gradient $D_i^t$ and implementing the OPGA do not require firms to have any knowledge of their competitors.\n> Q2: Also, as pointed out ... convergence results?\n\nA: Our current analysis is based on the exact gradient, and we recognize that it may be more practical to use noisy first-order feedback or even zeroth-order feedback. In terms of difficulties, we believe that the generalization to the noisy first-order oracle is relatively straightforward, where the main difference would be an extra error term in the analysis, causing the price path to converge to a neighborhood of SNE, whose size is determined by the magnitude of noises. Yet, the extension to the zeroth-order oracle might be a meaningful future work. In addition, we hope to highlight that the core of this paper is to show that firms can achieve a stable equilibrium while safeguarding their private data. Our convergence results, even with an exact first-order oracle, are highly non-trivial. The techniques developed for the convergence analysis are both original and innovative.\n\n### Reference\n[R1] Conditional logit analysis of qualitative choice behavior.\n\n[R2] Bandit learning in concave N-person games.\n\n[R3] Optimal no-regret learning in strongly monotone games with bandit feedback.\n\n[R4] Learning in games with continuous action sets and unknown payoff functions.\n\n[R5] Multiplicative weights update with constant step-size in congestion games: Convergence, limit cycles and chaos."}]

Author rebuttal:
# General Response
We would like to express our sincere gratitude to the reviewers for reading our paper and providing valuable feedback. Below, we answer two common questions and provide a background for the discrete choice model. Please find our responses to other questions in the personalized rebuttals.
> Q1: Clarification on observing market share $d_i$, and the connection between demand (quantity sold) and market share (CZUh W2, M19q Q2-1).

A: Sorry for the confusion. To observe $d_i$, each firm needs to know its own last-period demand (quantity sold), and both firms should agree on an estimated market mass. While the first point is rather intuitive, we'll elaborate on the market mass. 

The realized demand and market share $d_i$ are connected via the market mass (the largest potential demand, including no-purchase quantity). For instance, if firm H sells 1000 units and firm L sells 1500, with a market mass of 5000, then their market shares are $d_H=0.2$ and $d_L=0.3$, respectively, and the no purchase market share is $d_0=1-d_H -d_L=0.5$. Hence, given the market mass, a firm can easily convert the sold quantity into its market share. We'll now justify the assumption of knowing the market mass from two points.

* First, adding market mass information is feasible and practical. Indeed, it is sufficient for the two firms to agree on an estimated market mass. Under this agreement, the market will still reach an SNE under the OPGA. We only need to account for the error in market mass estimation. This is equivalent to using the noisy first-order oracle, which is a direct extension of our current analysis. Additionally, we note that in the fields of economics and operations research, the assumption of knowing the market mass is prevalent and standard under the MNL model (see, e.g., [R6--R13]), where this stream of papers typically uses the market share as the demand function while doing the pricing and assortment optimization on the MNL model.

* Second, having the information on market mass will NOT disclose a firm's market share or demand to its competitor, thereby safeguarding the firm's privacy. Note that even with an agreement on the market mass, firms remain unaware of their rivals' market share, as the market mass encompasses the quantity of no purchases. Thus, having this piece of information will NOT compromise the objective of this paper, i.e., achieving the SNE while preserving firms' privacy.

> Q2: Accessing the gradient $D_i^t$ under the opaque market (CZUh W2, M19q Q2-1, aAW7).

A: Obtaining $D_i^t$ in Eq.(9) is identical to accessing the first-order oracle, which is a common assumption in the optimization and gradient-based online learning literature [R1,R2,R3,R4,R5]. In this paper, rather than abstractly assuming direct access to a first-order oracle, we'd like to explain it in a more concrete and interpretable way, i.e., what elements do we need to get this oracle? Indeed, to compute $D_i^t$, a firm requires only (i) its own sensitivity parameters $(b_i, c_i)$ and (ii) its last-period demand. This aligns with the opaque market setup, i.e., there's no dependency on a rival's information.

A more practical setting may be accessing a noisy first-order oracle or even zeroth-order feedback. Yet, the main message we want to convey in this paper is that under the MNL, firms can reach an SNE while protecting their privacy, and our conclusions in the context of an exact first-order oracle are already highly non-trivial. We believe further relaxing the exact first-order oracles would be a very interesting future work (in fact, the generalization to a noisy first-order oracle is likely to be straightforward, with the zero-order feedback being the exciting one). 

> Q3: Background on discrete choice models and prevalence of Gumbel noise.

A: The discrete choice models, built on random utility theory [R14], help predict consumer choices among multiple options. The utility $U_i$ for product $i$ comprises a deterministic part $u_i$, and a random part $\epsilon_i$. Consumers are assumed to pick the product with the highest utility (with no-purchase utility being 0). The choice probability for product $i$ thus becomes $$P(U_i > U_j, \forall j \neq i)=P(\epsilon_j - \epsilon_i < u_i - u_j, \forall j \neq i). (\*)$$

In fact, only when $\epsilon_i$ follows the Gumbel does the market share in Eq.$(*)$ have the closed-form expression [R15]. The MNL model, while simple, offers accurate predictions and speedy parameter estimation through techniques like MLE. In contrast, models using other noise distributions lack closed-form expressions, requiring less efficient numerical simulation for parameter estimation. More detailed discussion on choice models can be found in this book [R15].
### Reference
[R1] Introductory lectures on convex optimization: A basic course.

[R2] Online first-order framework for robust convex optimization.

[R3] Learning in games with continuous action sets and unknown payoff functions.

[R4] Faster first-order methods for stochastic non-convex optimization on Riemannian manifolds.

[R5] Adaptive learning in continuous games: Optimal regret bounds and convergence to Nash equilibrium.

[R6] Discrete choice analysis: theory and application to travel demand.

[R7] Discrete choice theory of product differentiation.

[R8] The theory and practice of revenue management.

[R9] When prospect theory meets consumer choice models: Assortment and pricing management with reference prices.

[R10] Multiproduct price optimization and competition under the nested logit model with product-differentiated price sensitivities.

[R11] Pricing multiple products with the multinomial logit and nested logit models: Concavity and implications.

[R12] Product line selection and pricing with modularity in design.

[R13] Dynamic pricing and inventory control of substitute products.

[R14] Conditional logit analysis of qualitative choice behavior.

[R15] Discrete choice methods with simulation. 

Meta-review: I am recommending this paper for acceptance. The final scores are (7,6,6,6) --- so all reviewers are supportive. Importantly, the rebuttal and discussion phase could clarify some technical concerns of the reviewers. We would be happy to see those being incorporated in the camera-ready version.
Decision: Accept (poster)