Dynamic Service Fee Pricing under Strategic Behavior: Actions as Instruments and Phase Transition

Authors: rui  ai
david  simchi-levi
feng  zhu
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 21:12:12

Abstract: We study a dynamic pricing problem for third-party platform service fees under strategic, far-sighted customers. In each time period, the platform sets a service fee based on historical data, observes the resulting transaction quantities, and collects revenue. The platform also monitors equilibrium prices influenced by both demand and supply. The objective is to maximize total revenue over a time horizon $T$. Our problem incorporates three practical challenges: (a) initially, the platform lacks knowledge of the demand side beforehand, necessitating a balance between exploring (learning the demand curve) and exploiting (maximizing revenue) simultaneously; (b) since only equilibrium prices and quantities are observable, traditional Ordinary Least Squares (OLS) estimators would be biased and inconsistent; (c) buyers are rational and strategic, seeking to maximize their consumer surplus and potentially misrepresenting their preferences. To address these challenges, we propose novel algorithmic solutions. Our approach involves: (i) a carefully designed active randomness injection to balance exploration and exploitation effectively; (ii) using non-i.i.d. actions as instrumental variables (IV) to consistently estimate demand; (iii) a low-switching cost design that promotes nearly truthful buyer behavior. We show an expected regret bound of $\tilde{\mathcal{O}} (\sqrt{T}\wedge\sigma_S^{-2})$ and demonstrate its optimality, up to logarithmic factors, with respect to both the time horizon $T$ and the randomness in supply $\sigma_S$. Despite its simplicity, our model offers valuable insights into the use of actions as estimation instruments, the benefits of low-switching pricing policies in mitigating strategic buyer behavior, and the role of supply randomness in facilitating exploration which leads to a phase transition of policy performance.

Main paper: 
 introduction: 
 A large number of transactions nowadays take place on third-party platforms, such as shopping on Amazon, taking rides on Uber, and ordering takeout food on DoorDash [33, 39] . For these platforms, deciding how to set the service fee is an important issue [35, 40, 49] that not only affects the platform's short-term revenue but also impacts long-term user retention. Therefore, understanding buyers' demand curve is of significant importance for platforms aiming to maximize their revenue. Example 1.1. As an illustrative example, as a ride-hailing platform, Uber possesses information on the supply side (drivers), specifically the number of drivers available on the road at any given moment. Simultaneously, when buyers (passengers) request a ride, it matches drivers with passengers and charges a certain fee. Uber charges a booking fee for each reservation. Over a certain time period, Uber's booking fee remains approximately the same, as shown in Figure 1 . However, over a longer period of time, an exploratory dynamic pricing strategy can be beneficial to acquire more demand information.Meanwhile, consumers often refrain from taking rides when prices are high even if these prices are within their willingness to pay, aiming at inducing Uber to reduce the price or offer them coupons (which can be understood as a negative service fee) to reduce future purchase expenses. This phenomenon is common in both the psychology [6] and the economics [27, 42] literature.Figure 1 : Uber. Above are two Uber rides from the same city in February 2024. The price of the two rides differs by nearly double, yet the booking fee remains at $1.27 for both, suggesting that a fixed booking fee mechanism might be employed in February. However, over a longer period of time, Uber may switch to a dynamic pricing strategy.For third-party platforms, pricing service fees can face three challenges:1. Demand information needs to be learned. Typically platforms can observe the number and quoted prices of sellers on the platform, i.e., the supply curve, but the preference of buyers, or the demand curve, is not observable. At the same time, due to legal restrictions [58] , platforms in many cases cannot personalize pricing for different buyers but can only set a uniform price for a group of buyers. Therefore, it is crucial to learn about the buyer group's willingness to pay.2. Only equilibria can be observed. Regarding buyer information, platforms can only observe the equilibrium price and quantity, say P e and Q e respectively, which depend on the service fee set by the platform itself and the changing supply curve. Thus, due to changes in the demand curve, (P e , Q e ) may only reveal partial information about the demand curve and thus can fail to recover the full demand curve. In the absence of randomness in the supply curve, (P e , Q e ) could even form an upward-sloping curve, far from the characteristics of a demand curve.3. Buyers may exhibit strategic behavior. When buyers interact with the platform over an extended period, they may present a false demand curve to the platform, hoping to gain more benefits in future purchases, as shown in Example 1.1. The strategic behavior of buyers increases the difficulty for the platform to accurately estimate demand, and at the same time, causes the service fee to deviate from its optimal value, resulting in revenue loss. Pessimistically, Amin et al. [2] demonstrated that when the buyer possesses patience comparable to that of the seller, no learning algorithm can achieve sub-linear regret (cf. Appendix F.6).In this paper, we address the above challenges by establishing the first set of theories for pricing service fees on third-party platforms. We summarize our contributions in the following.• To the best of our knowledge, we are the first to attempt applying non-i.i.d. actions as instrumental variables in the problem of online pricing. In the traditional econometric framework [67] , researchers often seek external instrumental variables to estimate the demand curve. However, this method has significant limitations because good instrumental variables are hard to find. We demonstrate that even when actions are not independent and identically distributed (i.i.d.) random variables, or even possess strong correlations with one another, they still lead to excellent estimate of the demand curve. In Theorems 3.1, 3.2 and 4.3, we show our algorithms' optimal regret bounds. • We discover that the randomness in supply can effectively assist us in learning the demand curve. This counterintuitive fact reveals why, in Theorem 3.2, we can achieve a regret of O (1) , but in the case where there is no noise in supply, in Theorem 3.1, we can only expect a regret of O( √ T ). We explain in Section 4 via lower bound results (Theorem 4.1 and 4.2) that these orders of magnitude differences are fundamental and unavoidable. Additionally, we detailed the phase transition points of regret bounds regarding supply randomness.• We investigate robust pricing in the absence of prior knowledge of the buyer's discount rate.Our AaI and AAaI algorithms don't require the input of a discount rate to initiate, but can instead universally motivate buyers whose time has value to nearly truthfully report the demand curve. Specifically, our algorithm is also applicable in scenarios where the discount rate varies. The robustness of our algorithm is benign both in theory and applications.This work is closely related to instruments in machine learning [4, 5, 12, 56, 73, 47, 24, 69, 23] , pricing with strategic buyers [55, 2, 29, 37, 1, 38] , and demand learning under uncertainty [14, 26, 46, 21, 7, 48, 20, 50, 28] . Due to space constraints, additional references are provided in Appendix A for readers' reference. Detailed discussion of the relation and comparison between our work and previous work is also presented in Appendix A.Notations. For any positive integer n, we let [n] denote the set {1, ..., n} and n 1 : n 2 represent {n 1 , ..., n 2 -1}. We use N (µ, σ 2 ) to represent a Gaussian random variable with mean µ and variance σ 2 . Moreover, we use O(•) when ignoring constant terms while O(•) when ignoring constants and logarithmic terms. Similarly, we have Ω(•), Ω(•), Θ(•) and Θ(•). 
model and assumptions: 
 We consider an online dynamic pricing problem faced by a platform interacting with a representative buyer for T rounds. The platform aims to maximize its revenue against the rational and strategic buyer by dynamically adjusting the service fees.Information structure of platform pricing. In each round t, multiple sellers pose different portfolios on the platform and thus form the cumulative supply curve, denoted by P St = P St (Q) as a function of Q. For example, Uber can observe in real-time how many different types of drivers are available on the platform, such as UberX, UberXL, Black SUV, etc. Similarly, Ticketmaster knows how many tickets are still available in each area. Then, the platform sets a service fee a t ∈ R ≥0 . Here we assume the sellers are not strategic: as the platform formulates the fee-charging plan after observing P St (Q), there is no issue concerning trustfulness for sellers. In each round t, the representative buyer may receive a private signal, such as a shock on income, and form a time-dependent demand curve, denoted by P Dt = P Dt (Q). However, the buyer may behave as if her demand is P ′ Dt rather than P Dt because of her forward-looking strategic behavior, elaborating below. Together with service fee a t , the platform observes an equilibrium price and equilibrium quantity in the market, denoted by (P e t , Q e t ), satisfying P e t := P St (Q e t ) + a t = P ′ Dt (Q e t ).(1) Then, the platform receives revenue Π t = a t • Q e t (P St , P ′ Dt , a t ) in this round. As a result, across the time horizon of T , the platform has a cumulative revenue: T t=1 a t • Q e t (P St , P ′ Dt , a t ). As a concrete setting, we study the case when both the supply and demand curves have linear forms following canonical literature of both demand learning [19, 61, 44, 74] and instrumental variable models [56] . Assumption 2.1. Assume that the supply curve in round t has the form ofP St (Q) = α 0 + α 1 Q + ϵ Stand the demand curve is P Dt (Q) = β 0 + β 1 Q + ϵ Dt . The independent noise terms ϵ St and ϵ Dt follow normal distributions, N (0, σ 2 S ) and N (0, σ 2 D ), respectively.To avoid nuisance from market feasibility, we assume that β 0 > α 0 ≥ 0, α 1 ≥ 0 > β 1 , and that all equilibrium prices and quantities are positive and bounded. We note from Equation (1) that if Q e t is negative, then optimal Q e t shall be truncated as 0. For simplicity of analysis, we will not make truncation throughout the paper. This shall not influence the validity of our analysis and results.Utility-maximizing buyer. We assume the representative buyer fully knows the learning policy used by the platform to set service fees [37] . Note that the buyer is only aware of the policy beforehand. If the policy involves randomization, the buyer knows in advance the policy but not the realization of the policy. In fact, previous behavior-based pricing literature [41, 64, 10, 11] has suggested that committing to a pricing strategy can help the platform earn more revenue.In each time period t, the buyer receives a surplus, say surplus t (P St , P Dt , P e t , Q e t , a t ), which depends on the supply curve, demand curve, equilibrium price, equilibrium quantity, and the service fee. For brevity, we will write Sur t as an abbreviation of surplus t (P St , P Dt , P e t , Q e t , a t ). We utilize the Ramsey model [62] , which originates from the economic literature, to calculate the surplus. More rigorously, we employ Assumption 2.2. We postpone the discussion of the economic intuition behind Assumption 2.2 and its implications for calculating the surplus to Appendix B for interested readers.Assumption 2.2. We assume a private market where all sellers are civilian-run enterprises.The representative buyer has a discount rate γ ∈ [0, 1). When γ = 0, the buyer is myopic and only considers her surplus in the current round t. She truthfully purchases the optimal quantity of items she needs. That is, her realized demand curve P ′ Dt coincides with P Dt . However, when γ ∈ (0, 1), i.e., the buyer is far-sighted [8, 72] , she may choose to misreport her demand curve P ′ Dt ̸ = P Dt in exchange for increasing long-term expected cumulative utility: E[ T s=t γ s-t Sur s ], where again Sur s is the surplus gained at time s. The expectation is taken over the randomness for all time s > t: supply randomness ϵ Ss , demand randomness ϵ Ds , and potential randomness from the platform pricing policy. Here, we use the general economic term "misreport" to represent that the equilibrium price and quantity are not aligned with the buyer's true demand. They can be either larger or smaller. Note that the buyer won't show her demand curve P Dt (Q) to the platform at all, and all the information the platform can learn is through observing equilibrium prices and quantities. Thus, it is important for the platform to design a careful service charging mechanism to motivate a truthful disclosure of the demand curve from the buyer.Performance metric. With the help of the revelation principle [63] , there is an incentive-compatibledirect mechanism for pricing to achieve the highest revenue. So, we can define optimal service fee from Equation (1) bya * t = argmax at≥0 E[a t • Q e t (P St , P Dt , a t )].The expectation is taken over P Dt since the platform needs to set a t before the realization of P Dt .Define the suboptimality at time t asSubOpt t (a t ) = E[a * t • Q e t (P St , P Dt , a * t ) -a t • Q e t (P St , P ′ Dt , a t )].Our evaluation metric is then the revenue regret against a clairvoyant policy attained over the whole T rounds, namely,Regret(T ) = T t=1 SubOpt t (a t ).Remarks on the model. We would like to provide some further remarks on the model as follows.1. Platform is patient while buyer's discount rate is γ ∈ [0, 1). In practice, platforms are usually less time-sensitive compared with individuals, for instance, in a sponsored search auction, where the platform usually auctions off large numbers of ad slots each time while buyers usually urgently need advertisement and value future rewards less. On the other hand, the platform is not especially concerned with slight decreases in immediate rewards and maybe more on user stickiness. Readers can refer to Drutsa [30] , Golrezaei et al. [37] for more information on different time values for different market forces. Additionally, from a theoretical standpoint, achieving sub-linear regret is impossible when the buyer discount rate is one [2] . Therefore, our paper focuses on strategic buyers whose discount rates fall within the [0, 1) range, accommodating both real-world scenarios and theoretical constraints.2. On and beyond the linear model. In this paper, we focus on linear models. In practical scenarios, particularly when considering a localized segment of the market to avoid eliciting competitive reactions, there often emerges a pattern of linearity (which also serves as the cornerstone for the application of the so-called "Delta method" [45] ). Further, Besbes and Zeevi [15] also suggests that in certain circumstances, misspecification stemmed from assuming a linear model is less detrimental than anticipated. We note that although we explicitly assume the linearity of the demand curve and the supply curve in the model, it should not be difficult to extend to some variations of nonlinear models (e.g. log-log, semi-log model in hedonic pricing [66] and logistic model in click prediction [51] ) like Ban and Keskin [13] with some extra assumption on non-linear factors, by utilizing the generalized method of moments (GMM). Our technique also has the potential to work in high-dimensional cases and even non-parametric Reproducing Kernel Hilbert Space (RKHS). Despite such extensions, we will adopt the linear model throughout this work for brevity and clarity. We leave further generalizations for future work. 
regret upper bounds: actions as instruments: 
 In this section, we present our main algorithm AaI (Action-as-Instruments) and demonstrate its theoretical guarantees. We assume that T and σ S ≥ 0 are both known (σ D need not be known a priori). This assumption will be further relaxed in the next section. S ( Q e ) + a = P D ( Q e ).Generate an independent noise term ϵ ∼ N (0,1 √ size(A)+1 ) Set service fee a ← a * + ϵ • 1{σ S = 0}. Output: a.We now elaborate on the design of AaI and how it overcomes the main challenges mentioned in Section 1. We first demonstrate the design of our low-switching regime. In Algorithm 1, to deal with the far-sighted buyer, we update our policy when t is a power of 2. The intuition behind the low-switching cost update is that since the buyer has a discount rate strictly lower than 1, long-run benefits will be hard to compensate for short-run loss. Under a low-switching regime, the gap between the buyer's behavior P ′ D and the true demand curve P D becomes small. In the existing literature, Ai et al. [1] utilizes explicit "buffer" periods against far-sighted buyers while other works such as Golrezaei et al. [37, 38] use implicit methods to motivate truthfulness. In Algorithm 1, we adopt an implicit way to punish untruthful behavior so that we don't need information about the buyer's discount rate, thus enhancing the robustness and universality of our algorithm. We note that the use of low-switching cost algorithms may not be necessary when facing a myopic buyer, though indispensable for a far-sighted buyer [34, 71] .Second, the proof of Theorem 3.1 and 3.2 relies on solving the challenge that the platform can only observe equilibrium prices and quantities. The novel approach we take here is to utilize the service fee price as an instrumental variable (reflected in Algorithm 4). Despite the fact that the service fees as actions are correlated, we prove they provide valid estimates of the true coefficients (β 0 , β 1 ), which is rigorously shown in Lemma 3.1 (in the lemma only β 1 is analyzed; a similar result also holds for β 0 ). Lemma 3.1. Let β 1t be the estimated slope after round t. Then, under Assumptions 2.1 and 2.2, with high probability, it holds that| β 1t -β 1 | ≲ O( √ log log T t 1 4 + 1 (1 -γ) √ t) for all t ∈ [T ] when σ S = 0, and| β 1t -β 1 | ≲ O( √ log log T σ S √ t + 1 σ 2 S (1 -γ)t) for all t ∈ [T ] when σ S > 0. Now let's discuss the magnitude of the artificially added noise (see Algorithm 2) -which serves as an exploration step to learn demand information. Combined with our previous discussion, we will present our main theorems in this section. We differentiate between two cases: σ S = 0 and σ S > 0.S = 0: O( √ T ) RegretWe first consider the case when there is no supply randomness. At the beginning of each episode m, we add a O(1) noise to the service fee. Then, we decay the magnitude of noise variance at an inverse square root rate. There are two key points when implementing the algorithm.First, there is a trade-off between utilizing early data and recent data -the more data we use, the better estimate we will have, but the early data may have bad data-generating processes which may cause extra nuisances. Therefore, we choose only to use data from the last episode, whose length is roughly half of all available data and we reset the magnitude of noise as long as we start a new episode to ensure sufficient exploration.Second, there is a trade-off between adding larger and smaller randomness -the more randomness we add to the service fee, the more accurate estimate we will obtain, whereas higher noise leads to larger revenue loss. In our design, in episode m, the variance level of noise added is designed to be O( 1 √ 2 m ) on average where 2 m is the length of the episode. It decays at a relatively slow rate, aiming at exploration without losing much exploitation. We note that a special case of σ S = 0 is when the supply curve coincides with the Q-axis (P St (Q) = 0) and the buyer has no strategic behavior (γ = 0). This degenerates to the standard dynamic pricing problem [44] where a O( √ T ) regret holds. The following theorem shows that with the additional features in our model (equilibrium observation, strategic behavior), an O( √ T ) regret bound still holds.Theorem 3.1 (σ S = 0). Under Assumptions 2.1 and 2.2, for any fixed failure probability ι ∈ (0, 1), with probability at least 1 -ι, Algorithm 1 achieves at most O( √ T log( log T ι ) + log T (1-γ) 2 ) regret against any buyer whose discount rate γ ∈ [0, 1) when supply doesn't have noise, i.e. σ 2 S = 0. Here, O(•) hides only absolute constants.We then consider the case when there is supply randomness. In contrast to Section 3.1, here no random noise is injected into the empirical optimal action a * (see Algorithm 2). The following theorem shows that noise helps learning -an O(1) regret is obtainable. Theorem 3.2 (σ S > 0). Under Assumptions 2.1 and 2.2, for any fixed failure probability ι ∈ (0, 1), with probability at least 1 -ι, Algorithm 1 achieves at most O(log T log( log T ι ) σ 2 S + log T σ 2S (1-γ) ) regret against any buyer whose discount rate γ ∈ [0, 1). Here, O(•) hides only absolute constants.The regret upper bound in Theorem 3.2 contains two parts. The first O(log T ) term is the main regret incurred by learning the demand curve -which illustrates how noise helps learning. Although the platform can only observe equilibrium prices and quantities, the extra randomness in the supply curve automatically generates exploration and pushes the empirical optimal action a * from Algorithm 2 to vibrate around some intrinsic number. As a result, the estimation of β generates a fast convergence rate of O(1/ √ t) (see Lemma 3.1) even if no active exploration is presented. As a comparison, in Section 3.1 when the supply curve is deterministic, the problem becomes "degenerate" to some extent. The equilibrium prices on the supplier side and equilibrium quantities lie on one line (the fixed supply curve) in the 2-dimensional space, which forces us to do active exploration that leads to a O( √ T ) regret.The second term is the extra regret due to the strategic behavior of the buyer. Golrezaei et al. [37] achieves an extra O( log 2 T log 2 (1/γ) ) regret in repeated auction pricing when the discount rate is approaching one. Since log(1/γ) ≤ 2(1 -γ) for γ ∈ [0, 1), we obtain better results in both the order of log T and order of 1 1-γ . We note that since the implementation of Algorithm 1 doesn't depend on the buyer's discount rate γ, it can achieve O(log T log log T ) regret even if the discount rates are changing in different rounds -as long as the discount rate γ t has a uniform upper bound γ and γ < 1, which is widely observed in the real-world market, especially online advertising [31] , Algorithm 1 remains good permanence.From Theorems 3.1 and 3.2, we know the key to achieve O(1) regret is the internal randomness of the supply curve. Therefore, we have the following corollary. Corollary 3.2. If the platform needs to set a uniform service fee in multi-markets, such as Order Processing Fee on Ticketmaster [17] , the demand curve goes to⃗ P Dt = ⃗ β 0 + ⃗ β 1 ⊗ ⃗ Q + ⃗ ϵ Dt ,where ⊗ is the Kronecker product of two matrices. Then, as long as in one market, the corresponding supply has internal randomness, Algorithm 1 can achieve O(1) regret by utilizing a t as an instrument for all markets. Otherwise, it will suffer O( √ T ) regret. 
regret lower bounds: phase transition: 
 In this section, we present results on regret lower bounds. We will focus on the case when γ = 0 and investigate how the regret intrinsically scales as a function of T as well as σ S . We will show that there exhibits a phase transition phenomenon with respect to T and an inverse square law with respect to σ S . We first present a result when there is no supply randomness. Theorem 4.1. Given any time horizon T , when the supply doesn't have noise, the worst-case expected regret is lower bounded by Ω( √ T ). In Ω(•) we are hiding a constant term irrelevant with σ S and T .Next, we provide a lower bound when σ S can take any general positive number. Theorem 4.2. Given any time horizon T and the supply noise level σ S , the worst-case expected regret is lower bounded byΩ √ T ∧ log T σ 2 S (1 + log + (1/σ S )),where log + (•) = max{0, log(•)}.In Ω(•) we are hiding a constant term irrelevant with σ S and T .The proof of Theorem 4.1 depends on constructing two hard-to-differentiate instances such that the demand curves deviate with each other while the supply curves remain the same. The proof of Theorem 4.2 relies on the multivariate Van Trees inequality [36, 44] . An important step in both of the proof is when considering the magnitude of demand noise σ D , it should be dependent on α 1 and β 1 .The reason is that if the noise magnitude is irrelevant with the slope parameters, the standard deviation of equilibrium prices and quantities observed by the platform can provide additional information on the true parameters -this will make it possible for a policy to learn more quickly by "cheating". Only when the noise magnitude posits a delicate dependence on the true parameters, the equilibrium prices/quantities exhibit constant deviation across all instances without information leakage. H 0 : σ 2 S ≲ O( 1 √ T ) and H 1 : σ 2 S ≳ Ω( 1 √ T ), denoting the result as H. Conduct AaI(T -T 0 ) with Act-HT(H, •, •) (Algorithm 5 in Appendix C.2) replacing Act(•, •).In Algorithm 3, Act-HT is essentially a generalized version of Act: if H 0 holds, we treat σ S as if it is 0; if not, we treat σ S as it is. When T is unknown or infinite, we can leverage the well-known doubling trick [9, 16] to achieve the same order of regret. From Theorem 4.3, we know that when the supply randomness is small enough, namely, σ 2 S ≲ O(1/ √ T ), the expected regret has a fixed rate Θ( √ T ), whereas when the supply randomness is large enough, namely σ 2 S ≳ Ω(1/ √ T ), the expected regret is inversely proportional with respect to σ 2 S -an inverse square law ignoring constants and logarithmic terms. Therefore, there exists an essential phase transition when σ 2 S ≂ Θ(1/ √ T ) (see Figure 4 )this tells us that we should take market randomness into consideration whenever solving pricing problems. 
numerical study: 
 In this section, we conduct two simulation experiments. The goal is to test the performance of our algorithms as well as numerically demonstrate the phase transition phenomenon. We provide detailed experimental descriptions in Appendix G.In the first experiment, we consider regret attained in Algorithm 1 under two scenarios. Here, we set T = 10 5 . We replicate 10 times in each setting and draw the average regrets and their 95% confidence regions. We consider both constant σ 2 S and zero randomness in Figure 2 . It's obvious that when σ 2 S ≂ Θ(1), the growth rate of regret is significantly smaller than the growth rate when σ 2 S = 0. The first regret is slightly larger than 200 and the second one is more than 1200, validating the respective O(log 2 T ) and O( √ T log T ) expected regrets. Numerically, when σ 2 S = 1, we find that the regrets when T = 20000, 40000, 60000, 80000, 100000 (log T = 9.90,10.60,11.00,11.29,11.51) are 220, 230, 234, 236, and 237, respectively. These points are even slightly sublinear. So, the actual performance is even better than the theoretical bound. In addition, when there is no randomness in the supply, i.e., σ 2 S = 0, we have log(Regret) = 6.43, 6.75, 6.95, 7.10, 7.17, respectively. The estimated slope by linear regression is 0.47, testifying our regret bound.Moreover, we increase the number of trajectories to 100 and observe that the bandwidth of the corresponding confidence region significantly decreases (cf. Figure 3 (top, right)). Additionally, we test the regret under different σ 2 S values, say 0.5, 1, 1.5 and 2. We notice that the larger the σ 2 S , the smaller the regret, which confirms our theoretical results (cf. Figure 3 ). Then, we conduct the second experiment examining the dependency of regret on supply randomness σ 2 S . We set T = 10 4 and range σ 2 S from 0.001 to 1. We replicate the simulation 20 times and use quantile statistics to enhance the robustness (see raw results in Figure 5 , i.e., blue points). There are around 100 points choosing H 0 and we can observe the phase transition whenσ 2 S ≈ 0.1. Notice that Algorithm 3 has a O( √ T log T ) expected regret for H 0 but O( √ T log 2 T ) for H 1 when σ 2 S ≂ Θ( 1 √ T ) (cf. Appendix F.5). This additional log T factor explains why there is increasing fluctuation in regret near the phase transition point, as Algorithm 3 engages in a mixture of applying H 0 and H 1 . Finally, we employ locally weighted scatterplot smoothing (LOWESS) [25] to approximate regret for each level of randomness σ 2 S , with the fitting depicted by a red line. We notice that regret first reaches a plateau and keeps nearly constant and then gradually decreases, testifying Theorem 4.3.  
conclusion: 
 In this paper, we study the dynamic pricing problem for third-party platforms. Our model incorporates practical challenges involving lack of demand knowledge, limited observation of equilibria, and buyer strategic behavior. We design an effective policy that obtains optimal performance guarantees to address the challenges by injecting carefully chosen randomness, using non-i.i.d. actions as instruments, and forcing a low-switching design. Specifically, in the case of supply fluctuations, we achieve a regret upper bound of O(1), and when supply is fixed, we achieve a regret bound of O( √ T ), both of which match the information-theoretical lower bounds. Additionally, we demonstrate the relationship between regret and supply randomness, and provide their optimal dependency and phase transition points.Questions arise for future explorations. What is the dependence of regret on the discount rate γ? Our conjecture is that a discount rate strictly less than 1 will introduce inevitable Ω( 11-γ ) regret universally, meaning the regret upper bound in Theorem 3.2 is optimal with respect to γ but the bound in Theorem 3.1 may not. Unfortunately, the analysis can be very challenging, which we leave as an open question. Furthermore, one future work is to extend the linear model to more complex models and investigate whether the insights in this paper (e.g., phase transition) still hold. Despite the simplicity of our model, we hope our results offer valuable insights into solving general service fee pricing problems for third-party platforms.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes]Justification: The paper specifies all the training and test details necessary to understand the results.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [Yes]Justification: The paper reports error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments.Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.• The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors).• It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes]Justification: The paper provides sufficient information on the computer resources needed to reproduce the experiments. All experiments can be conducted on a personal computer.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [Yes] Justification: The paper discusses both potential positive societal impacts and negative societal impacts of the work performed.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA] Justification: The paper poses no such risks. Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort. 12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer: [NA] Justification: The paper does not use existing assets. Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.• If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?Answer: [NA]Justification: The paper does not release new assets.Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
crowdsourcing and research with human subjects: 
 Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?Answer: [NA]Justification: The paper does not involve crowdsourcing nor research with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: This work contributes to the theory of econometrics, demand learning, and pricing with strategic buyers. We summarize below three lines of existing literature pertinent to our work.Instruments in Machine Learning. Instrumental variable is a powerful tool in econometrics [4, 5, 12] . Nambiar et al. [56] uses IV to learn the demand curve under model misspecification, inspired by Petrin and Train [59] , Phillips et al. [60] . In recent years, a series of articles have emerged that use the IV method to estimate machine learning parameters. Yu et al. [73] , Liao et al. [47] utilize instruments to learn a nearly-optimal policy via offline data. Chen and Qi [24] , Uehara et al. [69] adopt a non-parametric instrumental variable framework to do off-policy evaluation. Chen and Zhang [23] considers a time-varying instrument and Singh [65] extends the kernel methods to scenarios with confounders.Unlike existing literature, our paper first leverages endogenous proactive actions as IV in online learning problems, especially in pricing. Unlike offline data, the distribution of our instrument variable is not only non-identical but also even non-independent. Meanwhile, as we face a revenuemaximizing problem, we need to deal with the famous exploration-exploitation tradeoff. More efficient instruments may decrease the estimation error leading to higher future revenue, but usually suffer a larger short-term loss. Thus, prior research does not encompass our model and we examine the robustness of IV to market randomness with novelty.Pricing with Strategic Buyers. There is a burgeoning amount of literature on pricing with strategic buyers. Amin et al. [2] first proves that no algorithm can achieve sublinear regret when buyers are as patient as sellers. Deng et al. [29] considers pricing in dynamic mechanism design with less patient buyers. It obtains sublinear regret in contextual auctions. Golrezaei et al. [37] study optimal reserve design problem original from Myerson [55] facing strategic bidders while Mohri and Munoz [54] considers a corresponding revenue optimization problem. Golrezaei et al. [38] considers pricing with strategic buyers under non-parametric market noise and Ai et al. [1] extends to Markov decision process (MDP) pricing models. Mohri and Medina [53] , Kanoria and Nazerzadeh [43] , Epasto et al. [32] , Amin et al. [3] also study such issues under different information structures and depict different scenarios in real markets.The difficulty in our model is that we can only observe equilibrium prices and quantities. Worst yet, there are confounders behind the information feedback. Therefore, the methods from previous literature cannot be directly applied to our model. Consequently, we explore a robust pricing framework originating from econometrics to address this issue.Demand Learning under Uncertainty. Demand learning is a hot topic in microeconomics, management science, and operations research [14, 26, 46, 21, 7, 48, 20] . Lobo and Boyd [50] considers a linear demand model and invents a "price-dithering" policy to add perturbation. Den Boer and Zwart [28] invents the controlled variance pricing idea and Broder and Rusmevichientong [18] scales exploration by adding t -1/4 which has similar connotations to our approach. Nambiar et al. [56] considers confounders in demand learning but doesn't involve strategic buyers. We extend high-level econometrics ideas behind it and design recipes against non-truthful buyers. We construct a robust pricing framework free of prior knowledge of both discount info and market randomness and attain optimal regret bounds across all settings.We clarify the definition of Sur t first. Similar to the Ramsey model [62] , there are three different types of sellers, namely, civilian-run enterprises, state-owned enterprises, and mixed-ownership enterprises [57] . For civilian-run enterprises, 100% of the profits belong to individuals, namely the representative buyer, so she aims to maximize the sum of producer surplus and consumer surplus. Then, it holds that Sur t = Consumer surplus at time t + Producer surplus at time t.Meanwhile, for state-owned enterprises, their goal is to maximize their own scale. This is a common form of business organization, especially in developing countries, such as China (see Modigliani and Cao [52] for more information). Because the buyer cannot receive dividends from companies, she will only maximize their consumer surplus, namely, Sur t = Consumer surplus at time t.Finally, for mixed-ownership enterprises, a portion of the profits will be distributed to the buyer in the form of dividends. We use α ∈ (0, 1) to denote the proportion. Therefore, we have Sur t = Consumer surplus at time t + α * Producer surplus at time t.Hence, we make Assumption 2.2 in our paper, all sellers are civilian-run enterprises. We point out that this assumption won't affect our results and regrets with the same order can be obtained under state-owned enterprises and mixed-ownership enterprises. Here, we use the definition of Sur t to detail Assumption 2.2 as Assumption B.1.Assumption B.1. Without loss of generality, we assume that all sellers are civilian-run enterprises. Then, the strategic representative buyer aims to maximize her cumulative surplus aligned with the sum of the corresponding consumer surplus and provider surplus. In other words, Sur t has the form of Sur t = Consumer surplus at time t + Producer surplus at time t.C.1 Omitted Details of Algorithm 1In this section, we present the subroutine used in Algorithm 1. Specifically, Algorithm 4 details the coefficient estimation process. Qe .Output: ( β 0 , β 1 ).We fill in the details of Algorithm 3 below.Algorithm 5 Act-HT Algorithm.Input: H, P S andP D . Calculate a * ← argmax a≥0 a • Q e (a), where Q e (a) is decided byP S ( Q e ) + a = P D ( Q e ).Generate an independent noise term ϵ ∼ N (0,1 √ size(A)+1 ) Set service fee a ← a * + ϵ • 1{H = H 0 }. Output: a.We now recall some inequalities [70] which bound the accumulated difference of a martingale and are extensively used in our proofs. P n k=1 D k ≥ t ≤    2e - t 2 2 n k=1 v 2 k if 0 ≤ t ≤ n k=1 v 2 k α * 2e -t 2α * if t > n k=1 v 2 k α *Lemma D.2 (Hoeffding bound). Suppose that the variables X i , i = 1, . . . , n, are independent, and X i has mean µ i and sub-Gaussian parameter σ i . Then for all t ≥ 0, we haveP n i=1 (X i -µ i ) ≥ t ≤ 2 exp - t 2 2 n i=1 σ 2 i .We first prove results in Section 3.2 and then prove results in Section 3.1 in leverage of some lemmas derived from the proof of Theorem 3.2.Since we assume that all equilibrium prices and quantities are bounded, reflecting the buyer's budget constraint and sellers' production capacity, we use P and Q to represent their upper bounds respectively. Moreover, recall that the buyer is myopic, so the demand curve behaved P ′ D is the same as the real demand P D .We first consider the situation in which the buyer is myopic as a warm-up. We have the following theorem.Theorem E.1. Under Assumption 2.1, for any fixed failure probability ι ∈ (0, 1), with probability at least 1 -ι, Algorithm 1 achieves at most O(log T log( log T ι ) σ 2 S) regret, where O(•) hides only absolute constants when facing a myopic buyer.Now, we state the following lemma for the planning problem first.Lemma E.1. If β 0 and β 1 are common knowledge, the optimal service fee is a * = β0-α0-ϵ S 2 . Meanwhile, the corresponding equilibrium quantity isQ e = β0-α0-ϵ S +2ϵ D 2(α1-β1) . Proof. Since P S = α 0 + α 1 Q + ϵ S and P D = β 0 + β 1 Q D + ϵ D , applying P S + a = P D leads to Q e = β0-α0-a+ϵ D -ϵ S α1-β1. As the platform cannot observe ϵ D when setting the service fee a, i.e. ϵ D is realized ex post, the expected revenue associated with a is Ea * Q e = (β0-α0-a-ϵ S )a α1-β1 . It's maximized whena * = β 0 -α 0 -ϵ S 2 .With some calculation, we know that the equilibrium quantity isQ e = β 0 -α 0 -ϵ S + 2ϵ D 2(α 1 -β 1 ).The reason why ϵ S appears explicitly is that the shock on the supple curve is ex-ante and observed by the platform.Thereafter, we'd like to bound the estimation of β 0 and β 1 in Algorithm 4. We have the following proposition. We ignore the flooring in ⌊log 2 T ⌋ throughout this section to avoid notation clutter.Proposition E.2. Let β 1 be the estimated slope of Algorithm 4 after the m-th episode. Then, under Assumption 2.1, there exists a constant C 1 such that with probability at least 1 -6δ, we have| β 1 -β 1 | ≤ C 1 √ log log T σ S √ 2 m for all m ∈ [log 2 T ],then| β 1t -β 1 | ≲ O( √ log log T σ S √ t ) for all t ∈ [T ],where subscript t represents which round.Proof. After the m-th episode, we know that we have data sets D and A with Size(A) = 2 m := n. Then, we need to prove that there exists a uniform constantC 1 such that | β 1 -β 1 | ≤ C1 √ log log T σ S √ n .Since during episode m, we choose the service fee as β0-α0-ϵ S, where β 0 is the latest estimate of β 0 , i.e. the estimate after m -1-th episode. With a little abuse of notation, we omit the subscript of it with β 0 along the road of proof without confusion.When Size(A) = n, it means that there are n samples in the data set, that is to say, a trajectory of length n. We use E n to represent the sample mean and E to represent the population mean. With simple algebra, we know thatβ 1 = E n [P e (a -E n a)] E n [Q e (a -E n a)] = 1 n n i=1 P e i (a i -E n a) 1 n n i=1 Q e i (a i -E n a).Since P e = β 0 + β 1 Q e + ϵ D as (P e , Q e ) is on the demand curve, it holds thatβ 1 = β 1 + 1 n n i=1 ϵ Di (a i -E n a) 1 n n i=1 Q e i (a i -E n a).First, we bound the numerator1 n n i=1 ϵ Di (a i -E n a) = -1 2n n i=1 ϵ Di ϵ Si + 1 2 E n ϵ S E n ϵ D .We use i x i to denote i ϵ Di ϵ Si for simplicity. For 1 n i x i , we leverage Lemma D.1 to give a Bernstein-type bound for the corresponding martingale difference sequence.Lemma E.3. There exists constants n 1 and ν such that with probability at least 1 -δ, it holds that for any n ≥ n 1 where n = 2 m and m ∈ [log 2 T ],| 1 n n i=1 x i | ≤ 2ν 2 log( 2 log 2 T δ ) n .Proof. In our case, we know that a i depends on not only previous ϵ D and ϵ S , but also ϵ Si . However, it doesn't rely on ϵ Di . This conditional independence motivates us to use actions as nearly valid instruments. Similarly, x i has the same property. Therefore, by utilizing this independence, we know thatE[x i | x 1 , ..., x i-1 ] = E[ϵ Di ] * E[ϵ Si | x 1 , ..., x i-1 ] = 0.As a result, {x i } n i=1 becomes a martingale difference sequence and we use F to denote associated filtration. Then, let's compute the moment-generating function (MGF).E[e λxi | F i-1 ] = exp(λϵ S ϵ D ) 1 √ 2πσ S e - ϵ 2 S 2σ 2 S 1 √ 2πσ D e - ϵ 2 D 2σ 2 D dϵ S dϵ D = 1 1 -λ 2 σ 2 S σ 2 D .as long as |λ| ≤ 1 σ S σ D . The first equation comes from the definition of ϵ D and ϵ S while the second equation comes from simple algebra. Therefore, assuming α = 2σ S σ D , we know that for any |λ| ≤ 1 α ,E[e λxi | F i-1 ] ≤ 1 1 -λ 2 σ 2 S σ 2 D ≤ e λ 2 σ 2 S σ 2 D . Then, assuming ν = 2σ 2 S σ 2 D = √ 2σ S σ D , it holds that x i is sub-exponential with parameters (ν, α).With the help of Lemma D.1, we know that as long as n ≥2α 2 log( 2 log 2 T δ ) ν 2 := n 1 , with probability at least 1 -δ log 2 T , | 1 n n i=1 x i | ≤ 2ν 2 log( 2 log 2 T δ ) n. Since there are at most log 2 T kinds of different values for n, the total sum of probabilities of bad events is less than δ log 2 T * log 2 T = δ, which ends the proof.For E n ϵ S , we have the following lemma therein to bound it.Lemma E. 4 . With probability at least 1 -δ, it holds that for any n = 2 m and m ∈ [log 2 T ] that| 1 n n i=1 ϵ Si | ≤ 2σ 2 S log( 2 log 2 T δ ) n .Proof. For any n = 2 m where m ∈ [log 2 T ], we know that ϵ Si is a sub-Gaussian variable with parameter σ S because it follows distribution N (0, σ 2 S ). By applying Lemma D.2, namely Hoeffding's inequality, it holds that with probability 1 -δlog 2 T | 1 n n i=1 ϵ Si | ≤ 2σ 2 S log( 2 log 2 T δ ) n .Combining all nuisance leads to the probability of all inequalities holding, that is, 1 -δ, which finishes our proof.Moreover, for E n ϵ D , we have a similar result whence giving an upper bound for it.Lemma E.5. With probability at least 1 -δ, it holds that for any n = 2 m and m ∈ [log 2 T ] that| 1 n n i=1 ϵ Di | ≤ 2σ 2 D log( 2 log 2 T δ ) n .Proof. The proof is the same as the one for Lemma E.4 with replacement of ϵ Si by ϵ Di .Second, let's give some concentration bounds for the denominator1 n n i=1 Q e i (a i -E n a). By applying Lemma E.1, we have the following decomposition of the denominator that1 n n i=1 Q e i (a i -E n a) = 1 2n(α 1 -β 1 ) i 2(a i -E n a)ϵ Di - i (a i -E n a)ϵ Si + i (a i -E n a)(2β 0 -β 0 -α 0 ) .We use i x i , i y i and i z i to denote for shorthand2 i (a i -E n a)ϵ Di , i (a i -E n a)ϵ Si and i (a i -E n a)(2β 0 -β 0 -α 0 ) respectively.From Lemmas E.3 to E.5, we know that with probability at least 1 -3δ, it holds that| 1 n i x i | ≤ 2ν 2 log( 2 log 2 T δ ) n + 2σ S σ D log( 2 log 2 T δ ) n ,where ν are defined in Lemma E.3.For 1 n i y i , we have the following lemma to illustrate its property. Lemma E.6. There exists constant n 2 such that with probability at least 1 -3δ, it holds that for any n ≥ n 2 where n = 2 m and m ∈ [log 2 T ],| 1 n n i=1 y i + σ 2 S 2 | ≤ 3 P 2 2σ 2 S log( 2 log 2 T δ ) n + 8 log( 2 log 2 T δ ) n .Proof. Let's decomposey i as -E n a * ϵ Si + β0-α0 2 ϵ Si - ϵ 2 Si 2 .For -E n a * ϵ Si , similar to Lemma E.4, it holds that with probability at least 1 -δ, for all n = 2 m ,| 1 n i -E n a * ϵ Si | = | 1 n i ϵ Si | * |E n a| ≤ P | 1 n i ϵ Si | ≤ P 2σ 2 S log( 2 log 2 T δ ) n .The first equation holds due to simple algebra while the first inequality holds because the service fee has a trivial upper bound P . The last inequality holds due to Lemma D.2.As for term β0-α0 2 ϵ Si , we use t i to denote it. Like the proof of Lemma E.3, we know that β 0 only depends on previous ϵ D and ϵ S but don't ϵ Si . So, it holds that E[t i | t 1 , ..., t i-1 ] = 0 and we use F to denote the corresponding filtration. Since we have the following MGFE[e λti | F i-1 ] = e λ 2 σ 2 S ( β 0 -α 0 ) 32 ≤ e λ 2 σ 2 S P 2 32 ,we know that t i is a sub-Gaussian random variable with a parameter σ S P 4 , which is also subexponential with parameters ( σ S P 4 , 0). With Lemma D.1, we know that with probability 1 -δ| 1 n i β 0 -α 0 2 ϵ Si | ≤ P σ 2 S log( 2 log 2 T δ ) 2nfor all m ∈ [log 2 T ] and n = 2 m .For the termσ 2 Si 2 , since ϵ 2 Si σ 2 S ∼ χ 2 1and χ 2 1 is sub-exponential with parameters (2, 4), we know that with probability 1 -δ,| 1 n i ϵ 2 Si 2 - σ 2 S 2 | ≤ 8σ 4 S log( 2 log 2 T δ ) n , as long as n ≥ 8 log( 2 log 2 T δ ) := n 2 .Accordingly, combining the above three terms leads to the needed lemma.For 1 n i z i , we notice that it's indeed zero. It holds that| 1 n i z i | = | 1 n i (a i -E n a)(2β 0 -β 0 -α 0 )| = 0,due to the definition of E n a.With the bounds for both nominator and denominator, it holds that| β 1 -β 1 | ≤ 2(α 1 -β 1 )( 1 2 2ν 2 log( 2 log 2 T δ ) n + σ S σ D log( 2 log 2 T δ ) n ) σ 2 S 2 - 2ν 2 log( 2 log 2 T δ ) n - 2σ S σ D log( 2 log 2 T δ ) n -3 P 2 2σ 2 S log( 2 log 2 T δ ) n - 8σ 4 S log( 2 log 2 T δ ) n .Then, there exists constants C 2 , C 3 and C 4 such that when n ≥ max{n 1 , n 2 , C 3 log logEQUATION) from previous definitions and process of proof.When n ≤ C 4 log log T , we can choose large enough constant C 5 such that C5 σ S √C4 is greater than a trivial bound for β 1 . Since we care about the situation when σ S is small, the probable appearance of it in the denominator won't cause trouble for us. Afterwards, by setting C 1 = max{C 2 , C 5 }, we find a uniform constant such that| β 1 -β 1 | ≤ C 1 √ log log T σ S √ 2 m .Moreover, we know that after the m-th episode, i.e. in the m + 1-th episode, t ∈ {2 m+1 -1 : 2 m+2 -1}, then t ≂ Θ(2 m ). Therefore, from the above, we know| β 1t -β 1 | ≲ O( √ log log T σ S √ t ) for all t ∈ [T ].Whereas when calculating the probability of bad events, there is some redundancy, after calibration, the union bound on the probability of bad events is 6δ which ends the proof.Since we can estimate β 1 with high accuracy, we similarly have the following proposition about the estimates of β 0 when Proposition E.2 holds.Proposition E.7. Let β 0 be the estimated intercept of Algorithm 4 after the m-th episode. Then, under Assumption 2.1 and conditional on the event that Proposition E.2 holds, there exists a constant D 1 such that with probability at least 1 -δ, we have| β 0 -β 0 | ≤ D 1 √ log log T σ S √ 2 m for all m ∈ [log 2 T ],then| β 0t -β 0 | ≲ O( √ log log T σ S √ t ) for all t ∈ [T ],where subscript t represents which round.Proof. It holds that for any n = 2 m , with probability at least 1 -δ,| β 0 -β 0 | = |β 1 E n Q e -β 1 E n Q e + E n ϵ D | ≤ |β 1 E n Q e -β 1 E n Q e | + |E n ϵ D | = |E n Q e | * |β 1 -β 1 | + |E n ϵ D | ≤ C 1 Q√ log log T σ S √ n + 2σ 2 D log( 2 log 2 T δ ) n .The first equation comes from Algorithm 4. The first inequality holds due to the triangle inequality while the second inequality holds due to Proposition E.2 and Lemma E.5.Then, for any n = 2 m , there exists aD 1 such that | β 0 -β 0 | ≤ D1 √ log log T σ S √ n . Similarly, since t ≂ Θ(n), it holds that | β 0t -β 0 | ≲ O( √ log log T σ S √ t ).Finally, bad events coming from E n ϵ D have a cumulative probability of δ which closes the proof.Up to now, we provide proof of Propositions E.2 and E.7 showing that even when IV is not i.i.d. with respect to time, we can obtain good estimation results, demonstrating the effectiveness of our Algorithm 4.Proof. With Appendix E.1.1 in hand, we are ready to give a high probability upper bound for the total regret.We use f (a) to denote Ea * Q e (P S , P D , a) = β0-α0-a-ϵ S α1-β1 a. Then, with an ordinary Taylor-series expansion and the mean value theorem, it holds thatSubOpt t (a t ) = df (a * t ) da (a * t -a t ) + 1 2 d 2 f (αa * t + (1 -α)a t ) da 2 (a * t -a t ) 2 ,where α ∈ [0, 1]From Lemma E.1, we know thatdf (a * t ) da = 0. Besides, it holds that (a * t -a t ) 2 ≲ O(| β 0t -β 0 | 2 ) ≲ O( log log T σ 2 S t ) due to Proposition E.7. Then, since | d 2 f da 2 | is uniformly bounded by a constant, namely 2 α1-β1 , we have that SubOpt t (a t ) ≲ O( log log T σ 2 S t).As a result, it holds thatEQUATION).The last inequality holds due to n i=11 i ≤ 1 + log n.The total odds of some inequalities not holding is 7δ. Among them, 6δ derives from Proposition E.2 and δ originates from Proposition E.7. Note that δ only appears in log log T terms. Setting ι = 7δ ends our proof.We then turn to prove Theorem 3.2. We begin this section with some preparing lemmas. Then, we will prove Theorem 3.2 in leverage of them. Finally, we will give a brief proof of the statement on time-varying discount.Since the buyer may behave as having a different demand curve P ′ D rather than the true one P D , we first give the following proposition of depicting such untruthfulness. Proposition E.8. For any behavior P ′ D , we can fully characterize it with a drift parameter η D . Consequently, without loss of generality, we can assume thatP ′ Dt = β 0 + β 1 Q + ϵ Dt + η Dt .Proof. Since the platform can only observe achieved equilibrium price P e t and quantity Q e t each round, we only need to find an associated η Dt leading to the same results.By setting η Dt = P e t -β 0 -β 1 Q e t -ϵ Dt , we find that (P e t , Q e t ) will satisfy Equation (1). Since two lines in Euclidean space have at most one intersection point, we know that η Dt fully describes P ′ Dt , and this correspondence is unique. Hence, we can use η D to represent untruthful behavior P ′ D and it finishes our proof.Using the equivalence in Proposition E.8, we present the relationship between equilibrium price and quantity and the service fee. Lemma E.9. For any valid service fee a and tuple (P S , P ′ D ), the equilibrium price and quantity followQ e = β 0 -α 0 -a + ϵ D -ϵ S + η D α 1 -β 1andP e = α 1 β 0 -α 0 β 1 -β 1 a + α 1 ϵ D -β 1 ϵ S + α 1 η D α 1 -β 1 ,respectively. Then, the change coming from η D leads to∆Q e = η D α 1 -β 1and∆P e = α 1 η D α 1 -β 1 .Proof. From Proposition E.8 and Equation (1), we can have the formulas for Q e and P e with some simple algebra. Furthermore, comparing them and the ones without η D leads to the formulas about ∆Q e and ∆P e , which finishes the proof.With these preparations, we are ready to give some properties of η Dt and show good performance of Algorithm 1. Lemma E.10. Considering the m-th episode of Algorithm 1, in the i-th round of this episode, we use η Di to denote η D(2 m +i-2) though a little abuse of notations. Then, it holds that for any rational buyer,EQUATION,where the m-th episode contains n = 2 m rounds. More precisely, it holds thatn i=1 γ i-n-1 η 2 Di ≤ (α 1 -β 1 ) 2 Q2 1 -γ .Proof. From Assumption 2.2, we know that Sur = Q e 0 (P D -P S -a)dQ.Therefore, we know that in the i-th round of the m-th episode, the loss of surplus is∆Sur i = 1 2 (∆Q e i ) 2 (β 1 -α 1 ) = - 1 2 η 2 Di α 1 -β 1 .Since the update of the estimation of (β 0 , β 1 ) happens in n -i rounds, the maximum gain from misreport is bounded byT j=n-i γ j+1 1 2 (α 1 -β 1 ) Q2 ≤ ∞ j=n-i γ j+1 1 2 (α 1 -β 1 ) Q2 = γ n-i+1 (α 1 -β 1 ) Q2 2(1 -γ) ,because the surplus is bounded by a trivial bound 1 2 (α 1 -β 1 ) Q2 in each round. The inequality holds because every term is positive. With some calculations, we have the final equation.Hence, we know that if the buyer is rational, she will guarantee thatEQUATIONEQUATION.When we consider all n rounds in the m-th episode as a whole, we know the total loss of surplus at the point of the last round in the m -1-th episode isn i=1 γ i 1 2 η 2Di α1-β1 . The maximum surplus increment is less than γ n+1 (α-β1) Q22(1-γ) . For a rational and strategic buyer, it holds that n i=1 γ i 1 2η 2 Di α 1 -β 1 ≤ γ n+1 (α -β 1 ) Q2 2(1 -γ) , leading to n i=1 γ i-n-1 η 2 Di ≤ (α 1 -β 1 ) 2 Q2 1 -γ ,which finishes our proof.We notice that since the buyer owns strictly less than 1 discount rate, if we inverse time, the bound of misreport will exponentially decay. Therefore, we have reason to believe that these misreports will not significantly affect the estimation of parameters. Consequently, we have the following propositions.Proposition E.11. Let β 1 be the estimated slope of Algorithm 4 after the m-th episode. Then, under Assumptions 2.1 and 2.2, with probability at least 1 -6δ, it holds that when2 m ≳ O( log log T σ 2 S + 1 σ 2 S (1-γ) ), | β 1 -β 1 | ≲ O( √ log log T σ S √ 2 m + 1 2 m σ 2 S (1 -γ) ) for all m ∈ [log 2 T ],then| β 1t -β 1 | ≲ O( √ log log T σ S √ t + 1 σ 2 S (1 -γ)t ) for all t ∈ [T ],where subscript t represents which round.Proof. Similar to Proposition E.2, it holds thatβ 1 = β 1 + 1 n n i=1 ϵ Di (a i -E n a) 1 n n i=1 Q e i (a i -E n a) + 1 n n i=1 η Di (a i -E n a) 1 n n i=1 Q e i (a i -E n a).For the numerator, we know that with probability at least 1 -3δ,| 1 n n i=1 ϵ Di (a i -E n a)| ≤ 1 2 2ν 2 log( 2 log 2 T δ ) n + σ S σ D log( 2 log 2 T δ ) n ,due to Lemmas E.3 to E.5.Moreover, we bound 1 n n i=1 η Di (a i -E n a) directly in leverage of Lemma E.10. It holds that| 1 n n i=1 η Di (a i -E n a)| ≤ 2 P n n i=1 |η Di | ≤ 2 P n n i=1 γ i-n-1 η 2 Di n i=1 γ n+1-i ≤ 2(α 1 -β 1 ) P Q n √ 1 -γ γ 1 -γ = 2(α 1 -β 1 ) P Q√ γ n(1 -γ) .The first inequality holds due to a i ≤ P while the second inequality holds due to Lemma E.10 and Cauchy-Schwarz inequality. The third inequality holds because every term in the summation is positive and the geometric series sum formula.For the denominator, since ∆Q e = η D /(α 1 -β 1 ) from Lemma E.9, we only need to bound1 n n i=1 η D α1-β1 (a i -E n a). It holds that 1 n n i=1 η D α 1 -β 1 (a i -E n a) ≤ 2 P Q√ γ n(1 -γ)due to the same process as bounding| 1 n n i=1 η Di (a i -E n a)| above.Therefore, we notice that| 1 n n i=1 Q e i (a i -E n a)| ≥ 1 2(α 1 -β 1 ) σ 2 S 2 - 2ν 2 log( 2 log 2 T δ ) n - 2σ S σ D log( 2 log 2 T δ ) n - 3 P 2 2σ 2 S log( 2 log 2 T δ ) n - 8σ 4 S log( 2 log 2 T δ ) n - 2 P Q√ γ n(1 -γ) ,with probability at least 1 -6δ due to Lemma E.6.Combining all these terms, it holds that| β 1 -β 1 | ≤ 1 n n i=1 ϵ Di (a i -E n a) 1 n n i=1 Q e i (a i -E n a) + 1 n n i=1 η Di (a i -E n a) 1 n n i=1 Q e i (a i -E n a) ≲ O(σ S √ log log T √ n ) O(σ 2 S ) -O(σ S √ log log T √ n ) -O( 1 n(1-γ) ) + O( 1 n(1-γ) ) O(σ 2 S ) -O(σ S √ log log T √ n ) -O( 1 n(1-γ) ) ≲ O( √ log log T σ √ n + 1 nσ 2 S (1 -γ) ) ≲ O( √ log log T σ S √ 2 m + 1 2 m σ 2 S (1 -γ)).The first inequality holds due to the triangle inequality while the second inequality holds due to previously presented concentration bounds. The third inequality holds due to simple algebra while the last one holds due to n = 2 m . Besides, taking into account repeated bad events, the probability of all inequalities holding is at least 1 -6δ. Here, we need n ≥ O( log log Tσ 2 S + 1 σ 2 S (1-γ) ).Considering that for any round in the m + 1-th episode, we have t ∈ {2 m+1 -1 : 2 m+2 -1}, it then holds that| β 1t -β 1 | ≲ O( √ log log T σ S √ t + 1 σ 2 S t(1 -γ)) for all t ∈ [T ],which ends the proof.Conditional on having a good estimation of β 1 , we have the following proposition, saying that we can also estimate β 0 precisely.Proposition E.12. Let β 0 be the estimated intercept of Algorithm 4 after the m-th episode. Then, under Assumptions 2.1 and 2.2 and conditional on the event that Proposition E.11 holds, we have with probability at least 1 -δ,| β 0 -β 0 | ≲ O( √ log log T σ S √ 2 m + 1 2 m σ 2 S (1 -γ) ) for all m ∈ [log 2 T ],then| β 0t -β 0 | ≲ O( √ log log T σ S √ t + 1 σ 2 S (1 -γ)t ) for all t ∈ [T ],where subscript t represents which round.Proof. We know that β 0 = E n P e -β 1 E n Q e . Thus, it holds that| β 0 -β 0 | ≤ |E n P e -β 1 E n Q e -β 0 | ≤ |β 1 E n Q e + E n ϵ D + E n η D -β 1 E n Q e | ≤ | β 1 -β 1 | * |E n Q e | + |E n ϵ D | + |E n η D | ≤ | β 1 -β 1 | * Q + |E n ϵ D | + E n |η D | ≲ Q * O( √ log log T σ S √ n + 1 nσ 2 S (1 -γ) ) + 2σ 2 D log( 2 log 2 T δ ) n + (α 1 -β 1 ) Q√ γ n(1 -γ) ≲ O( √ log log T σ S √ n + 1 nσ 2 S (1 -γ)).The first inequality holds due to the definition β 0 while the second inequality holds due to Proposition E.8. The third inequality holds due to the triangle inequality while the fourth inequality holds due to Jensen's inequality and trivial upper bound Q. The fifth inequality holds with probability at least 1 -δ because of the results achieved in the proof of Proposition E.11 while the last inequality holds due to simple algebra.Similarly, we have that| β 0t -β 0 | ≲ O( √ log log T σ S √ t + 1 σ 2 S t(1 -γ)) for all t ∈ [T ],which ends the proof.Propositions E.11 and E.12 highlight the statistical efficiency of Algorithm 1 even when the buyer is far-sighted, showing the robustness of our algorithm against non-myopic strategic agents. The first inequality holds due to simple algebra while the second inequality holds because the service fee is always no larger than P . The last inequality holds due to Lemma E.9.EThen, during the m-th episode, there are n = 2 m rounds and we have Pα 1 -β 1 |η Di | ≤ P Q √ 1 -γ ( √ γ) n-i+1 ,andn i=1 γ i-n-1 η 2 Di ≤ (α 1 -β 1 ) 2 Q2 1 -γ .Furthermore, it holds thatT t=1 P α 1 -β 1 |η Dt | = log 2 T m=1 2 m i=1 P α 1 -β 1 |η Di | ≤ log 2 T m=1 P α 1 -β 1 (α 1 -β 1 ) Q√ γ 1 -γ = P Q√ γ log 2 T 1 -γ .The inequality holds due to the same process when proving Proposition E.11. It comes from Lemma E.10 and Cauchy-Schwartz inequality.Consequently, we haveRegret(T ) = T t=1 SubOpt t (a t ) ≲ O( log T log log T σ 2 S + log T σ 2 S (1 -γ) ) + P Q√ γ log 2 T 1 -γ + O( log log T σ 2 S + 1 σ 2 S (1 -γ) ) ≲ O( log T log log T σ 2 S + log T σ 2 S (1 -γ)),with probability at least 1 -7δ. For the first inequality, the first term comes from suboptimal service fees while the second term comes from misreport. The last term is needed because of the requirement of n ≥ O( log log Tσ 2 S + 1 σ 2 S (1-γ) ).Finally, as δ merely hides within log log T terms, setting ι = 7δ leads to the desired result and finishes our proof.When the buyer has a time-varying discount rate γ t , we can replace it with its uniform upper confidence bound γ in the proofs of Lemma E.10, propositions E.11 and E.12, and theorem 3.2. Since we use upper bound γ for every spot discount rate, all estimators become more conservative. Intuitively, the higher the discount rate, the greater the buyer's motivation to misreport. So, all inequalities will hold with corresponding probabilities. Therefore, when the discount rates are changing in different rounds but with a uniform upper bound γ, Algorithm 1 still achieves O(log T log log T ) regret with high probability which ends the proof.So as to prove Theorem 3.1, we state some auxiliary lemmas at first.Recall that we use ϵ to represent added noise which follows N (0,1 √ Size(A)+1) and η D to represent the distance between P ′ D and P D thanks to Lemma E.9. We have the following lemma to depict the equilibrium price and quantity in each round. Lemma E.13. For any estimation β 0 and tuple (P S , P ′ D ), the equilibrium price followsQ e = 2β 0 -β 0 -α 0 + 2ϵ D + 2η D -2ϵ 2(α 1 -β 1 ).Then, the change coming from η D leads to∆Q e = η D α 1 -β 1 .Proof. We get the formula of Q e from Equation ( 1) with ϵ S = 0 and the implementation of Algorithm 2. Moreover, due to Lemma E.1, we know the optimal ex-ante service fee a * = β0-α02 without untruthful behavior and extra noise term ϵ.Since the choice of ϵ is independent of η D , we know that Lemma E.10 still holds, that is, in the i-th round of m-th episode, the quantity of misreport η Di follows that for the rational and strategic buyer,EQUATION)where the m-th episode contains n = 2 m rounds.Subsequently, we are ready to bound the distance between the estimates of β 0 and β 1 and their true values.Proposition E.14. Let β 1 be the estimated slope of Algorithm 4 after the m-th episode. Then, under Assumptions 2.1 and 2.2, with probability at least 1-8δ, it holds that when2 m ≳ O(log T log log T + 1 (1-γ) 2 ), | β 1 -β 1 | ≲ O( √ log log T 2 m 4 + 1 2 m 2 (1 -γ) ) for all m ∈ [log 2 T ],then| β 1t -β 1 | ≲ O( √ log log T t 1 4 + 1 (1 -γ) √ t ) for all t ∈ [T ],where subscript t represents which round.Proof. Let's first decompose the error terms of estimating β 1 . Assume that n = 2 m as usual. From the implementation of Algorithm 4, we know thatβ 1 = E n [(a -E n a)P e ] E n [(a -E n a)Q e ] = β 1 + 1 n n i=1 ϵ Di (a i -E n a) 1 n n i=1 Q e i (a i -E n a) + 1 n n i=1 η Di (a i -E n a) 1 n n i=1 Q e i (a i -E n a).Since a = β0-α0 2 + ϵ, it holds that 1 n n i=1 ϵ Di (a i -E n a) = 1 n n i=1 ϵ i * ϵ Di -E n ϵ * E n ϵ D .Let's bound them one by one.First, let's give a high probability upper bound for 1 n n i=1 ϵ i * ϵ Di . We note that it's a martingale difference sequence because ϵ Di has mean zero conditional on previous events. From the proof of Lemma E.3, we know that ϵ i * ϵ Di is sub-exponential with parametersν i = √ 2 σ D i 1/4 and α i = 2 σ D i 1/4 because Var(ϵ i ) = 1 √ i .Then, it holds that due to Lemma D.1,EQUATION).The first inequality holds due to Lemma D.1 while the second inequality holds due to√ n ≤ n i=1 1 √ i ≤ 2 √ n. Hence, by setting t = 8σ 2 D log( 2 log 2 T δ ) n 3/4 , it holds that P(| 1 n n i=1 ϵ i * ϵ Di | ≥ t) ≤ δ log 2 T . Besides, we need nt ≤ n i=1 ν 2 i maxi αi . A sufficient condition is n ≥ (8 log( 2 log 2 T δ )) 2 , then n ≳ O((log log T ) 2 ). Finally, we have that with probability at least 1 -δ, for any m ∈ [log 2 T ],| 1 n n i=1 ϵ Di ϵ i | ≤ 8σ 2 D log( 2 log 2 T δ ) n 3/4 .For the term E n ϵ Di , we have the following result from Lemma E.5|E n ϵ Di | ≤ 2σ 2 D log( 2 log 2 T δ) n with probability at least 1 -δ.For the term E n ϵ i , we know that ϵ i is sub-Gaussian with parameter σ i = 1 i 1/4 . Consequently, it holds that|E n ϵ i | ≤ 4 log( 2 log 2 T δ ) n 3/4 ,with cumulative probability at least 1 -δ due to Lemma D.2.We thereafter bound the term1 n n i=1 η Di (a i -E n a).From Equation ( 2), we can obtain the following bound directly inherited from the proof of Proposition E.11 that| 1 n n i=1 η Di (a i -E n a)| ≤ 2(α 1 -β 1 ) P Q√ γ n(1 -γ) .After that, we need to investigate the property ofn i=1 Q e i (a i -E n a). We divide it into three terms. It holds that1 n n i=1 Q e i (a i -E n a) = 1 α 1 -β 1 [ 1 n n i=1 ϵ Di (a i -E n a) q1 + 1 n n i=1 η Di (a i -E n a) q2 + 1 n n i=1 (-ϵ i )(a i -E n a) q3 ].From previous results, we know that with probability at least 1 -3δ|q 1 | ≤ 8σ 2 D log( 2 log 2 T δ ) n 3/4 + 8σ 2 D log 2 ( 2 log 2 T δ ) n 5/4 ,and|q 2 | ≤ 2(α 1 -β 1 ) P Q√ γ n(1 -γ) .For the last term q 3 , it holds that-q 3 = 1 n n i=1 ϵ 2 i -( 1 n n i=1 ϵ i ) 2 .Besides, we know that with probability at least 1 -δ, it holds that( 1 n n i=1 ϵ i ) 2 ≤ 4 log( 2 log 2 T δ ) n 3/2 , due to Lemma D.2.Finally, for 1 n n i=1 ϵ 2 i , we know that ϵ i ∼ N (0, 1 √ i ) and they are independent. Therefore, ϵ 2 i is sub-exponential random variable with ν i = 2 √ i and α i = 4 √ i with scaling of χ 2 1 random variable. So, from Lemma D.1, it holds thatP(| n i=1 ϵ 2 i - n i=1 1 √ i | ≥ nt) ≤ max 2 exp(- n 2 t 2 8 n i=1 1 i ), 2 exp(- nt 2α * ) ,where α * = max i α i = 4. By choosing t = max8(1+log T ) log( 2 log 2 T δ ) n , 8 log( 2 log 2 T δ) n , we know that with probability at least 1 -δ, we have1 n | n i=1 ϵ 2 i - n i=1 1 √ i | ≤ max    8(1 + log T ) log( 2 log 2 T δ ) n , 8 log( 2 log 2 T δ ) n    ≲ O( √ log T log log T n ),for any n = 2 m . Here, we use facts log n ≤ n i=11 i ≤ 1 + log n and n ≤ T . So, with probability at least 1 -2δ, we know that|q 3 | ≥ 1 √ n -max    8(1 + log T ) log( 2 log 2 T δ ) n , 8 log( 2 log 2 T δ ) n    - 4 log( 2 log 2 T δ ) n 3/2 ≳ 1 √ n -O( √ log T log log T n ).Combing all these terms, we know that|β 1 -β 1 | ≤ (α 1 -β 1 ) 8σ 2 D log( 2 log 2 T δ ) n 3/4 + 8σ 2 D log 2 ( 2 log 2 T δ ) n 5/4 + 2(α1-β1) P Q√ γ n(1-γ) 1 √ n -O( √ log T log log T n ) - 8σ 2 D log( 2 log 2 T δ ) n 3/4 - 8σ 2 D log 2 ( 2 log 2 T δ ) n 5/4 - 2(α1-β1) P Q√ γ n(1-γ) ≲ O( √ log log T n 1/4 + 1 √ n(1 -γ) ).as long as n ≳ O(log T log log T + 1 (1-γ) 2 ). Since we know that t ≂ Θ(n), it holds that with probability at least 1 -8δ,| β 1t -β 1 | ≲ O( √ log log T t 1 4 + 1 √ t(1 -γ) ),which ends the proof. Now, we have the following proposition to bound the estimation error of β 0 in a similar manner.Proposition E.15. Let β 0 be the estimated intercept of Algorithm 4 after the m-th episode. Then, under Assumptions 2.1 and 2.2 and conditional on the event that Proposition E.14 holds, we have with probability at least 1 -δ,| β 0 -β 0 | ≲ O( √ log log T 2 m 4 + 1 2 m 2 (1 -γ) ) for all m ∈ [log 2 T ],then| β 0t -β 0 | ≲ O( √ log log T t 1 4 + 1 (1 -γ) √ t ) for all t ∈ [T ],where subscript t represents which round.Proof. Similar to the proof of Proposition E.12, it holds that β 0 = E n P e -β 1 E n Q e . Consequently, we have with probability at least 1 -δ,| β 0 -β 0 | ≤ |E n P e -β 1 E n Q e -β 0 | ≤ |β 1 E n Q e + E n ϵ D + E n η D -β 1 E n Q e | ≤ | β 1 -β 1 | * |E n Q e | + |E n ϵ D | + |E n η D | ≤ | β 1 -β 1 | * Q + |E n ϵ D | + E n |η D | ≲ Q * O( √ log log T n 1/4 + 1 √ n(1 -γ) ) + 2σ 2 D log( 2 log 2 T δ ) n + (α 1 -β 1 ) Q√ γ n(1 -γ) ≲ O( √ log log T n 1/4 + 1 √ n(1 -γ) ).The first four inequalities are the same as the one in the proof of Proposition E.12. Moreover, the fifth inequality comes from Proposition E.14 and the last inequality comes from simple order of magnitude analysis.Similarly, we have that| β 0t -β 0 | ≲ O( √ log log T t 1 4 + 1 √ t(1 -γ) ) for all t ∈ [T ],which ends the proof.Propositions E.14 and E.15 show that although we add approaching zero noise to explore the unknown environment, we can asymptotically estimate true parameters β 0 and β 1 accurately. Nevertheless, comparing with Propositions E.2, E.7, E.11 and E.12, the convergence rates have decreased to a certain extent, ultimately resulting in a larger regret.Proof. Basically, similar to the proof of Theorem 3. We know that the optimal service fee at round t is a * t = β0-α0 2 while the service fee we set isa t = β0t-α0 2 + ϵ t .Therefore, considering the Taylor's expansion, it holds thatE|a * t * Q e (P St , P Dt , a * t ) -a t * Q e (P St , P Dt , a t )| ≲ O( log log T √ t + 1 t(1 -γ) 2 + ϵ 2 t ),where the expectation is taken over ϵ Dt due to Proposition E.15 and(a + b + c) 2 ≤ 3(a 2 + b 2 + c 2 ).Considering the m-th episode, we know that there are n = 2 m rounds in it. Since we already have that1 n | n i=1 ϵ 2 i - n i=1 1 √ i | ≲ O( √ log T log log T n ),with probability at least 1 -δ log 2 T , it holds thatn i=1 ϵ 2 i ≲ O( √ n + log T log log T ).This will lead to the following result thatT t=1 ϵ 2 t ≲ O( √ T )because of the geometric series summation formula.As a result, we getT t=1 E|a * t * Q e (P St , P Dt , a * t ) -a t * Q e (P St , P Dt , a t )| ≲ O( √ T log log T + log T (1 -γ) 2 ),with probability at least 1 -δ.As for the second term E|a t * Q e (P St , P Dt , a t ) -a t * Q e (P St , P ′ Dt , a t )|, similarly, we haveT t=1 E|a t * Q e (P St , P Dt , a t ) -a t * Q e (P St , P ′ Dt , a t )| ≤ P Q√ γ log 2 T 1 -γ due to Equation (2).Recall that we also need that n ≳ O(log T log log T + 1 (1-γ) 2 ) to make Proposition E.14 hold. Combining all these terms, it holds thatRegret(T ) = T t=1 SubOpt t (a t ) ≲ O( √ T log log T + log T (1 -γ) 2 ) + P Q√ γ log 2 T 1 -γ + O(log T log log T + 1 (1 -γ) 2 ) ≲ O( √ T log log T + log T (1 -γ) 2 ),with probability at least 1 -10δ.Recall that δ is exclusively concealed within log log T terms. By assigning ι = 10δ, we have reached the following conclusion thatRegret(T ) ≲ O( √ T log( log T ι ) + log T (1 -γ) 2 ),which finishes our proof.F.1 Useful Facts for Proving Theorem 4.1 First, we introduce some auxiliary lemmas on Kullback-Leibler (KL) divergence. Lemma F.1. For two independent normal distributions p = N (µ 1 , σ 2 1 ) and q = N (µ 2 , σ 2 2 ), the KL divergence between them isEQUATIONProof. Recall that KL(p∥q) = x p(x) log( p(x) q(x) )dx. It leads to the result with the expression of normal distribution and some calculations.). For two probability distributions p, q over space (Ω, F), it holds that for anyA ∈ F p(A) + q(A c ) ≥ 1 2 e -KL(p∥q) .F.2 Proof of Theorem 4.1Proof. We only prove the lower bound against myopic buyer which is the loosest one. Let's consider the following case. We assume the supply curve is P S = Q S and the family of the demand curve parameterized by ϵ is{P ϵD = 20 + 5ϵ -(1 + ϵ)Q D + ϵ ϵD } where ϵ ϵD ∼ N (0, ( 2+ϵ 2 ) 2 ).The system is depicted completely by (a t , P e ϵt ), where Q e ϵt = P e ϵt -a t . Recall that a t depends on history up to t -1, namely, H t=1 = (a 1 , P e ϵ1 , ..., a t-1 , P e ϵ(t-1) ). From Lemma E.1, we know thatQ e ϵ = 20+5ϵ-a+ϵ ϵD 2+ϵ , P e ϵ = 20+5ϵ+(1+ϵ)a+ϵ ϵD 2+ϵ.Then, we know that P e ϵ ∼ N ( 20+5ϵ+(1+ϵ)a 2+ϵ , 1 4 ) due to the definition of ϵ ϵD . Moreover, the ex-ante optimal service fee is a * = 20+5ϵ 2 . We now consider the situation when ϵ = 0 and ϵ = T -1 4 and we use P ϵ to denote associated probability measure. With the help of Lemma F.1, it holds thatKL(P 0 ∥P ϵ ) = E a [KL(P 0 (• | a)∥P ϵ (• | a)) | a] = E a [ ϵ 2 (10 -a) 2 2(2 + ϵ) 2 ],where we use the law of iterated expectations.During the whole T round, we calculate the number of rounds with |10 -a t | ≥ 5ϵ denoted by T 0 . With a slight abuse of notation, we use [T 0 ] to denote the corresponding index set. Let's consider achieved regret with T 0 case by case.On the one hand, when T 0 ≥ T 2 , it holds that one-round suboptimlality forϵ = 0 is at least SubOpt 0t (a t ) = (10-a) 2 2 when t ∈ [T 0 ]. Then, we have Regret 0 (T ) + Regret ϵ (T ) ≥ Regret 0 (T ) ≥ t∈[T0] SubOpt 0t (a t ) ≥ T 0 25ϵ 2 2 ≥ T 2 25 2 √ T ≳ Ω( √ T ).The first inequality holds due to the positivity of regret while the second inequality holds due to the positivity of SubOpt(•). The third inequality holds because when t belongs to [T 0 ], we have that |10 -a| ≥ 5ϵ while the fourth inequality holds due to the assumption of T 0 .On the other hand, when T 0 < T 2 , there exists more than T 2 rounds such that |10 -a| ≤ 5ϵ. In these rounds, denoted by [T -T 0 ], it holds that KL(P 0 ∥P ϵ ) ≤ 25ϵ 4 2(2+ϵ) 2 ≤ 25ϵ 4 18 as ϵ ≤ 1. The first inequality holds with no need to consider the distribution of a because we use a union bound over all a. Then, the total KL among these T -T 0 rounds is no larger than (T -T 0 ) 25ϵ 4 18 ≤ 25 18 ≲ O(1) as ϵ = T -1/4 in leverage of properties of KL divergence.We define an event A that in more than T 4 rounds, a t ≥ 40+5ϵ 4 . Therefore, A c contains at least T 4 rounds that a t < 40+5ϵ 4 . Therefore, it holds thatE [•|T0< T 2 ] [Regret 0 (T ) + Regret ϵ (T )] ≥ E [•|T0< T 2 ]   t∈[T -T0] SubOpt 0t (a t ) + SubOpt ϵt (a t )   ≥ P 0 (A | T 0 < T 2 ) T 4 25ϵ 2 32 + P ϵ (A c | T 0 < T 2 ) T 4 25ϵ 2 16(2 + ϵ) ≥ 25ϵ 2 T 192 (P 0 (A | T 0 < T 2 ) + P ϵ (A c | T 0 < T 2 )) ≥ 25 √ T 192 1 2 e -25 18≳ Ω(The first inequality holds due to the positivity of SubOpt(•) while the second inequality holds because the optimal service fee is 20+5ϵ 2 and one-round loss is[a-(20+5ϵ)/2] 2 2+ϵ. The third inequality holds due to ϵ ≤ 1 while the fourth inequality holds due to Lemma F.2.Therefore, it holds that by combining both two cases max{ERegret 0 (T ), ERegret ϵ (T )}≥ 1 2 (ERegret 0 (T ) + ERegret ϵ (T )) ≥ min{E [•|T0≥ T 2 ] Regret 0 (T ) + Regret ϵ (T ) 2 , E [•|T0< T 2 ] Regret 0 (T ) + Regret ϵ (T ) 2 } ≥ 1 2 min{ 25 √ T 4 , 25 √ T 384 e -25 18 } ≳ Ω( √ T ),due to ϵ = T -1/4 . Therefore, for any algorithm against ϵ = 0 and ϵ = T -1/4 , at least one regret is no smaller than Ω( √ T ), which ends the proof.There are two key points when constructing such a hard-to-learn instance. When ϵ = 0, the optimal service fee is 10 and the expected equilibrium is (P e , Q e ) = (15, 5) . Then, we choose a special of demand curves which are all through (P e , Q e ) = (15, 5) in expectation. Therefore, when the platform chooses a = 10, it cannot infer the value of ϵ which ends with large regret for non-zero ϵ. However, if the platform sets service fee deviated from 10, it will suffer a high loss in the case when ϵ = 0, ending with large total regret. This introduces an internal exploration-exploitation tradeoff leading to Ω( √ T ) regret loss bound. However, when σ 2 S > 0, even if the platform sets optimal service fee for ϵ = 0, the noise ϵ S plays the role in exploring the environment. The platform can utilize such information to do casual inference which heavily reduces the regret to O(1). So, we answer the question that noise helps learning essentially.Secondly, from a technical perspective, we adaptively adjust the noise variance in the demand. For the tuned hyperparameter ϵ = T -1 4 and baseline parameter ϵ = 0, we shrink σ 2 ϵD from ( 2+ϵ 2 ) 2 to 1. Since the randomness of demand introduces noise into the equilibrium retrospectively, the equilibrium price and quantity appear nebula-like. The shrinkage of variance results in greater overlap between the two nebulae, which complicates the learning process. Mathematically, it causes the equilibrium price to have the same variance regardless of the value of ϵ, entailing smaller KL divergence between different choices of demand. To sum up, these two crucial aspects make up this delicate and non-trivial example.Note that there is a gap between the proposed upper bounds and corresponding lower bounds whenσ 2 S ≲ O( 1 √ T ), indicating essential hardness in this interval. Therefore, we first give the following lemma which is a little bit weaker than the original Theorem 4.2 but depicts the characteristics in this area. Here, we use a constructive proof and then we give a complete information-theoretic proof of Theorem 4.2 in Appendix F. 4 T ) without supply randomness, contradicting Theorem 4.1. We assume γ = 0 which is enough to construct a counterexample. We present the detail of Oracle-Variant in Algorithm 6. The input is the number of rounds T and the supply randomness σ 2 S ≲ o( 1 √ T ) associated with Oracle. We use a t * to denote the optimal service fee when there exists ϵ St ∼ N (0, σ 2 S ) and a * t to denote the one without randomness. Considering the following counterfactual case, if we adopt a t when there exists ϵ St , the equilibrium price and quantity will be( P e t , Q e t ) = ( β 0 -α 0 -a t + ϵ Dt -ϵ St α 1 -β 1 , α 1 β 0 -α 0 β 1 -β 1 a t + α 1 ϵ Dt -β 1 ϵ St α 1 -β 1 )according to Lemma E.9. Fortunately, choosing a t = a t + ϵ St leads to the same equilibrium price and quantity without randomness, that is to say, (P e t , Q e t ) = ( P e t , Q e t ). Since we use Oracle, the regret when baseline is a t * is o( √ T ). Therefore, we know thatE[ T t=1 ( a t -a t * ) 2 ] ≲ o( √ T ),according to the proof of Theorem E.1. Now, let's give a decomposition of (a t -a * t ) 2 . It holds that(a t -a * t ) 2 ≲ O((a t -a t ) 2 ) + O(( a t -a t * ) 2 ) + O((a * t -a t * ) 2 ),according to simple algebra. For the first term, we know thatE[ T t=1 O((a t -a t ) 2 )] ≲ E[O( T t=1 ϵ 2 St )] ≲ O(T σ 2 S ),from the implementation of Algorithm 6. For the second term, it holds thatE[ T t=1 O(( a t -a t * ) 2 )] ≲ o( √ T ).For the last term, we know thatE[ T t=1 O((a * t -a t * ) 2 )] ≲ E[ T t=1 O(ϵ 2 St )] ≲ O(T σ 2 S ), because |a * t -a t * | = | ϵ St 2 |according to Lemma E.1. Therefore, we know that without supply randomness, the expected regret of Algorithm 6 satisfyingRegret(T ) ≲ o( √ T ) + O(T σ 2 S ) ≲ o( √ T ).The last inequality holds due to σ 2 S ≲ o( 1 √ T ). However, from Theorem 4.1, we know that ERegret(T ) ≳ Ω( √ T ). It then causes a contradiction. We subsequently conclude that the existence of Oracle is untenable, which ends the proof.Proof. Let β = (β 0 , β 1 ) and ϵ Dt ∼ N (0, σ 2 D ) with σ D = (α 1 -β 1 )σ for some σ > 0. To express concisely, we use subscript β and superscript π to denote parameter and policy, respectively. We know thata * t (β) = β 0 -α 0 -ϵ St 2 .Also, when the decision maker sets any a t , we observeQ e t = β 0 + ϵ Dt -a t -α 0 -ϵ St α 1 -β 1Note that the only unknown randomness comes from ϵ Dt since ϵ St is always observable. Meanwhile, upon deciding a t and observing Q e t and ϵ St , the price from both the demand and supply side can be uniquely decided. Therefore, the log-likelihood prior to time t can be calculated as:L t-1 (β) = t-1 i=1 - 1 2σ 2 Q e i - β 0 -a i -α 0 -ϵ Si α 1 -β 1 2 + C,where C is a constant only dependent on {a i , Q e i } t-1 i=1 and not dependent on β. The fisher information matrix prior to time t can be calculated asF π t-1 (β) = E π β -∂ 2 L t-1 (β)/∂β 2 = 1 σ 2 E π β t-1 i=1 1 (α1-β1) 2 -β0-at-α0-ϵ St (α1-β1) 2 -β0-at-α0-ϵ St (α1-β1) 2 (β0-at-α0-ϵ St ) 2 (α1-β1) 2.Let λ be an absolutely continuous density on Θ, taking positive values on the interior of Θ and zero on its boundary (see, e.g., Keskin and Zeevi [44] ). Then the multivariate Van Trees inequality [36] implies thatEQUATIONLetEQUATIONC(β)F π t-1 (β)C(β) ⊤ = 1 σ 2 (α 1 -β 1 ) 2 E π β t-1 i=1 β 0 -α 0 2 -(β 0 -a t -α 0 -ϵ St ) 2 = 1 σ 2 (α 1 -β 1 ) 2 t-1 i=1 E π β a i - β 0 -α 0 -ϵ Si 2 + ϵ Si 2 2 = O t-1 i=1 E π β (a i -a * i (β)) 2 + σ 2 S .Plugging the inequalities above into Inequality (3), we know that there exists a positive constant c such thatE λ E π β (a t -a * t (β)) 2 ≥ 2c 1 + t-1 i=1 E λ E π β [(a i -a * i (β)) 2 ] + (t -1)σ 2 S .From now on, for notation simplicity, we denote 2 . Summing the formula above from t to T , we know that∆ [t,T ] = T i=t E λ E π β (a i -a * i (β))EQUATIONThen sup β Regret π β (T ) = Θ(∆ [1,T ] ). We show the lower bound in two cases. (a). T ≤ 1 + 1/σ 4 S . Then from Inequality (4) we have∆ [1,T ] ≥ T -1 i=1 2c 1 + ∆ [1,i] + σ 2 S • i ≥ 2c(T -1) 1 + ∆ [1,T ] + √ T ≥ cT ∆ [1,T ] + 2 √ T .Therefore,(∆ [1,T ] + √ T ) 2 ≥ (1 + c)T,which indicates that there exists a constantc 0 = √ 1 + c -1 > 0 such that ∆ [1,T ] ≥ c 0 √ T . (b). T > 1 + 1/σ 4 S .Let K be the smallest positive integer such that 2 K ≥ 1 + 1/σ 4 S . Then 2 K-1 < 1 + 1/σ 4 S , which indicate thatK + 1 = K -1 + 2 < log 2 (1 + 1/σ 4 S ) + 2 ≤ 6(1 + log + (1/σ S )).From (a) we know that for t = 2 K , we have∆ [1,t] ≥ c 0 1 + 1/σ 4 S ≥ c 0 1 σ 2 S ≥ c 1 1 + log + (1/σ S ) K σ 2 S ,where c 1 is a small positive constant irrelevant with K and σ S such that c 1 (2 + 6c 1 ) ≤ c. Now we use induction. Suppose we have∆ [1,2 k ] ≥ c 1 1 + log + (1/σ S ) k σ 2 S (5)for some k ≥ K. From Inequality (4) we have∆ [2 k +1,2 k+1 ] ≥ (2 k+1 -2)c 1 + ∆ [1,2 k+1 ] + σ 2 S • (2 k+1 -1) ≥ c 2 -k + ∆ [1,2 k+1 ] 2 k + 3 2 σ 2 S ≥ c ∆ [1,2 k+1 ] 2 k + 2σ 2 S .Note that we have utilized the following inequality:2 -k ≤ σ 4 S 1 + σ 4 S ≤ σ 4 S 2σ 2 S = σ 2 S /2.As a result,∆ [1,2 k+1 ] ≥ c 1 1 + log + (1/σ S ) k σ 2 S + c ∆ [1,2 k+1 ] 2 k + 2σ 2 S . If ∆ [1,2 k+1 ] < c1 1+log + (1/σ S ) k+1 σ 2 S , then c ∆ [1,2 k+1 ] 2 k + 2σ 2 S > c c1 1+log + (1/σ S ) k+1 2 k σ 2 S + 2σ 2 S ≥ c c1 1+log + (1/σ S ) K+1 2 K σ 2 S + 2σ 2 S ≥ c (2 + 6c 1 )σ 2 S ≥ c 1 σ 2 S .This causes a contradiction. Therefore, for any k ≥ K, Inequality (5) holds. Now select any T > 1 + 1/σ 4 S . If T < 2 K , then ∆ [1,T ] ≥ c 0 1 + 1/σ 4 S ≥ c 1 1 + log + (1/σ S ) K σ 2 S ≥ c 1 1 + log + (1/σ S ) log T σ 2 S . If T ≥ 2 K , choose k = ⌊log 2 T ⌋, then ∆ [1,T ] ≥ ∆ [1,2 k ] ≥ c 1 1 + log + (1/σ S ) k σ 2 S ≥ c 1 /2 1 + log + (1/σ S ) log T σ 2 S .) in Theorem 3.2 and O(log T ) in Theorem 3.1. Since terms from estimation errors dominate them, we without loss of generality assume that the buyer is myopic i.e., γ = 0 for simplicity without weakening our results.From traditional results of hypothesis test [22] , we know we need n ≂ Θ(( zασ E ) 2 ) samples to distinguish H 0 and H 1 , where z α , σ and E are the z-score, the population standard deviation and the acceptable margin of error, respectively. Here, we know that σ ≂ Θ(σ 2 S ) since Var(ϵ 2 St ) ≂ Θ(σ 4 S ). Besides, we set α ≂ Θ( 1T ) and then z α ≂ Θ( √ log T ) due to Lemmas D.1 and D.2. The largest tolerance of error is E ≂ Θ( 1 √ T ). Therefore, by setting T 0 ≂ Θ(log T ) with some accurately designed constants, we can distinguish H 0 and H 1 with probability at least 1 -Θ( 1T ). Then, in the case of H 0 , we will add some human-made noise referring to Algorithm 5. Then, the randomness of a t comes from two parts. One is from original ϵ St . The other one comes from artificially added noise. Therefore, the variance of a t is no smaller than the one in the proof of Theorem 3.1 and the estimation of parameters will be more accurate. Subsequently, we can bound three parts of regret which construct the total Regret(T ). The first one comes from the gap between a t and a * t . It will lead to an O( √ T ) regret. The second part comes from the fact that the probability that some inequalities don't hold is at most O( 1T ). The last part comes from the first T 0 rounds. Therefore, it holds thatEQUATIONT ) + O(T 0 ) ≲ O( √ T ).Recall that we will suffer st most extra O(log T ) from a strategic buyer which is indeed a subdominant term. It covers cases when σ 2 S ≲ o( 1 √ T ). In the case of H 1 , it will reduce to Theorem E.1 directly. The regret consists of three parts as well. The first part is O( 1 σ 2) inherited from Theorem E.1. The second term comes from the O( 1T ) probability of some inequalities being violated. The last term is from the first T 0 rounds, yieldingEQUATION).Note that we will suffer an extra O( log T σ 2) regret facing a far-sighted buyer. This case contains all situations when σ 2 S ≳ ω( 1 √ T ). To be specific, from the proof of Theorems 3.1 and 3.2, we know we hide O(log 2 T ) for H 1 but only O(log T ) for H 0 .Finally, when σ 2 S ≂ Θ( 1 √ T ), the policy we use might be a mixture of the one under H 0 and the one under H 1 . Luckily, both of them will lead to an at most O( √ T ) expected regret.To sum up, we know that the expected regret of Algorithm 3 satisfiesERegret(T ) ≲ O( √ T ) when σ 2 S ≲ O( 1 √ T ) O( 1 σ 2 S ) when σ 2 S ≳ Ω( 1 √ T ).Let's now turn to the tightness of lower bounds. From Theorems 4.1 and 4.2, we have thatEQUATIONT ). Therefore, we conclude that our regret lower bounds are tight and Algorithm 3 is optimal regardless of constants and logarithmic terms. Moreover, we instantly obtain the phase transition of regret and it finishes our proof.We close off this section by giving an easy reduction to the Ω(T ) lower bound in Amin et al. [2] when the buyer is patient, i.e., equipped with discount rate 1. To determine the optimal dependency on γ is s beyond the scope of the current work and we leave it as an interesting future direction.For each β 0 , we have a unique optimal service fee a * corresponding to it. In the meanwhile, a * is the marginal willingness to pay and we focus on the pricing problem for those with value a * . From Theorem 3 in Amin et al. [2] , we know there exists a value v, i.e., a * here, an Ω(T ) regret is inevitable for any algorithm when the buyer is patient, namely, γ = 1. Through the bijection between β 0 and a * , we know there exists some β 0 that makes this pricing problem unlearnable.We choose parameters γ = 0, α 0 = 1, α 1 = 1, β 0 = 5, β 1 = -1 and ϵ D ∼ N (0, 1) in both experiments.In Section 5, we notice that the increment of regret has several stages. At the beginning of each stage, the regret will increase relatively rapidly, and then the rate decrease gradually. The reason behind this phenomenon is the way we implement Act(•, •). We actually update our pricing policy at the start of each stage. Therefore, the noise we add has a variance that starts from 1 and decreases according to the inverse square root law.For the second experiment, there are some hyper-parameters when implementing Algorithm 3. First, we set T 0 = 10 log 2 T therein. Secondly, when we do the hypothesis test, we set H = H 0 if the sample mean of ϵ 2 S is smaller than 10T and H 1 otherwise. Among the 1000 choices of σ 2 S , there are about 100 cases where H = H 0 , nearly to say, when σ 2 S ≤ 0.1. These choices of hyper-parameters are not essential and not well-tuned though enough for our experiments. When using LOWESS, we set the hyperparameter "fraction" as 0.15. It means that we use 15% nearest points when fitting the needed function value. Similarly, it is not carefully selected but rather folklore. Besides, note that log T ≈ 9.21 so regret fluctuating between 300 and 600 around σ 2 S = 0.1 should be acceptable. In conclusion, the first experiment testifies regret upper bounds in Theorems 3.1 and 3.2 while the second experiment validates results about the tightness of our lower bounds and the existence of phase transition in Theorem 4.3 in a concrete manner.Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [Yes] Justification:The paper provides open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material. Guidelines:• The answer NA means that paper does not include experiments requiring code. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.Justification: The research conducted in the paper conforms, in every respect, with the NeurIPS Code of Ethics.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).We define 0 0 = 0 for convenience. 


Decision: The paper analyzes a dynamic pricing problem faced by a platform in setting its service fees, in the presence of strategic, long-living and far-sighted customers. The platform does not know the demand information.  At each time, the platform sets the service fees, and observes the resulting equilibrium prices and quantities. Using this information, the platform seeks minimize its regret against the benchmark with known demand information. The authors develop an "actions-as-instrument" approach to learn the demand, and achieve vanishing regret. 

The overall consensus is that the paper is technically rigorous, and interesting, and makes a solid contribution. There were some questions about the problem motivation and connection to real world application. Given the consensus and the ratings, the paper would be a good addition to the conference program.

Reviews: review: paper_summary: paper_summary: The paper tackles the dynamic pricing problem faced by third-party platforms specifically concerning the optimal setting of service fees in the presence of strategic and far-sighted customers. The objective is to maximize the total revenue over a given time horizon.
strength_weakness: strength_weakness: -. Declaration: line 100, confusing definition of price P and demand Q.
-. Limitation: lack of explanation of assumption 1, regarding the linearity with Gaussian noise.
-. There is a lack of details on instrumental variables in Algorithm 1, which is crucial in solving the regret bounds since instrumental variables are non-iid and non-external.
-. The trade-offs of data amount and randomness are straightforward in Section 3.1.
-. Lack of motivation and explanation of relaxing the two assumptions in Section 3.2.
-. Lack of detailed definition of T_0 in Algorithm 3. The intuition of using hypothesis testing is quite straightforward.
-. In Section 5, to show the regret order, it’s better to show a log-like figure which indicates the linearity relation.
questions: questions: see weakness.
limitations: limitations: NA.
paper_summary: paper_summary: The primary goal of the paper is to maximize total revenue over a given time horizon by dynamically adjusting service fees on third-party platforms, considering the strategic nature of customers and the lack of complete information on demand.
The paper presents a novel approach to dynamic pricing for third-party platforms, addressing the challenges of unknown demand, equilibrium observation limitations, and strategic buyer behavior. The authors propose an algorithmic solution that incorporates active randomness injection, non-i.i.d. actions as instrumental variables, and a low-switching cost design to balance exploration and exploitation while estimating demand and mitigating strategic behavior.
strength_weakness: strength_weakness: 1 While the paper is comprehensive, it could benefit from more real-world examples or case studies to illustrate the practical application of the proposed algorithms.


2 The assumptions made for the model may not always hold in real-world scenarios. For example, in reality, there is often a situation of diminishing marginal utility. so the assumption that supply and demand curves have linear forms hinder the practical application of this algorithm. The authors could discuss the robustness of the algorithms under different conditions.

3 The author say that they can consider incentive-compatible direct mechanism with the help of revelation principle. But the design space of the platform must be constrained compared to the original space. The authors do not discuss the impact of this change on their design of the algorithms.
questions: questions: Could the authors provide more examples or case studies to illustrate how their algorithms perform in real-world scenarios?
How do the algorithms perform under different levels of noise in the supply curve, and what is their robustness to model misspecification?
The direct and IC mechanism could be constrained compared to the original space. Could the authors discuss the impact of this on their design of the algorithms?
limitations: limitations: I did not find any limitations of the paper.
paper_summary: paper_summary: This paper considers a dynamic pricing problem where the buyer is strategic and provides regret analysis under this setting. In particular, they propose to use instrumental variables to estimate demand and discuss the impact of the supply randomness.
strength_weakness: strength_weakness: 1. The problem motivation is questionable as the service fee does not change often in practice whereas the online learning problem considered effectively relies on frequent changes (equivalently, a large number of periods)
1. It is a pity that the regret dependence on $\gamma$ is not captured in the current analysis, as also mentioned in the future direction of this paper.
questions: questions: 1. As mentioned in Example 1.1,  the service fee is constant in a short period of time, and might not be that dynamic (compared to typical applications of dynamic pricing such as retailing or ride-hailing pricing). However, the numerical experiments involve a very large number fo time periods, in particular, the regret converges at around 20,000. The inconsistencies make the proposed algorithm inviable in practice. Can the authors reconcile the inconsistency and provide a more convincing motivation?
1. Can the authors explain a bit more on the revelation principle and in particular how the buyer maximizes surplus?
1. The paper mentions using non-i.i.d. action as an instrument; however, a rigorous exposition on conditional independence (i.e., sanity check) is missing, which decreases the theoretical credibility of this work. Can the authors enrich this part?
1. The noise-agnostic algorithm in Algorithm 3 is interesting but the current description is a bit concise. Can authors add explanation on how to implement the hypothesis test?
1. The confidence region is rather wide in Figure 2. Can authors check the algorithm performances and maybe present more results with different $\sigma_S$ values? It also might be worthwhile to increase the number of trajectories from $10$.
limitations: limitations: N/A
paper_summary: paper_summary: The paper studies the problem of dynamic pricing of service fees in a setting where only equilibrium quantities of supply and demand curves are observable. The main contributions of the paper lies in using Instrumental Variables in an online setting, and consequently, theoretically bounding the regret of the model.
strength_weakness: strength_weakness: Some proofs could had been included in the main paper as theoretical contribution is the strength of the paper.
questions: questions: The equilibrium equation (1) between supply and demand was unclear. How does the equation be helpful for the buyer’s strategies. Some intuition could be provided here
limitations: limitations: The paper makes good theoretical observations about the setting in consideration. However, the 100% civilian-run seller assumption could be relaxed to make it a more impactful contribution. Other limitations are stated by the authors and these are not straightforward to fix and I agree with authors that these should be left for future.

Comments: title: Score adjusted
comment: Thanks a lot!
Thanks a lot!
I thank the authors for clarifying the details. Based on the response, I would like to raise my scores.
Thank you for your comment. We would like to emphasize that in this paper we take the first steps towards understanding service fee pricing in third-party platforms. We take an "actions as instruments" perspective and observe a "phase transition" phenomenon. We hope to extend the techniques to nonlinear functions in our next step (we believe the techniques and insights still hold). Thanks again for your review.
Thank you for the response. I understand that using a linear model simplifies notation and presentation. However, This also simplifies the learning process. It is still difficult to evaluate the performance of the algorithm in much more complicated, real-world applications. I will maintain my score.
Thanks for the response. I retain my score.
Thank you for your feedback! Our analysis of the model is twofold. First, charging service fees is critical for third-party platforms as it constitutes a significant portion of a company's revenue. This work makes initial attempts to integrate various factors of service fee pricing into an intuitive model, illustrating the concept of actions as instruments and the phenomenon of phase transition. Second, our paper adopts an experimental approach, commonly used by many online platforms. If a platform lacks prior market information, it must explore to learn about the environment while maximizing total rewards. This includes dynamically adjusting service fees and personalizing promotional efforts, both fitting well within such an experimental framework. Nervertheless, we look forward to incorporating promotions and developing more practical models as an exciting avenue for future research. Please let us know if you have any more questions. Thank you once again for your insights!
Thank you for your thoughtful feedback. Overall this is a technically strong and well-rounded paper. My previous concerns are largely well addressed and I appreciate the authors' efforts in addressing them. I have thus adjusted my score accordingly. Last minor note, though I remain a little skeptical about the motivation. As the authors have replied "While the booking fee doesn't change too often, promotions can change quickly and be highly personalized. Therefore, our model can also be applied to dynamic promotion pushes." -- if this is the case, it is probably more appropriate not to use service pricing as the problem background (just for the sake of being unique) if it does not fit the model well.