Dynamic Service Fee Pricing under Strategic Behavior: Actions as Instruments and Phase Transition
Authors: Rui Ai
David Simchi-Levi
Feng Zhu
Venue: NeurIPS 2024 poster (2024)
Keywords: online learning
online platform
dynamic pricing
strategic behavior
instrumental variable
phase transition
Primary area: online_learning

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.

Dynamic Service Fee Pricing under Strategic Behavior: Actions as Instruments and Phase Transition
Rui Ai MIT ruiai @mit. edu
David Simchi-Levi MIT dslevi@mit. edu
Feng Zhu
MIT
fengzhuGmit, edu
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 to maximize total revenue over time horizon T' Our problem incorporates three practical challenges: (a) initially, the platform lacks knowledge the demand side beforehand, necessitating a balance between exploring (learning the demand curve) and exploiting (maximizing revenue) simultancously; (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: 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) low-switching cost design that promotes nearly truthful buyer behavior. We show an expected regret bound of and demonstrate its optimality, up to logarithmic factors, with respect to both the time horizon T' and the randomness in supply as. Despite its simplicity, our model offers valuable insights into the use of actions estimation instruments, the benefits of low-switching pricing policies mitigating strategic buyer behavior, and the role of supply randomness in facilitating exploration which leads phase transition of policy performance.
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 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.
40 49
that not only affects
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 any given moment. Simultancously, when buyers (passengers) request ride, it matches drivers with passengers and charges a certain fee. Uber charges booking fee for each reservation. Over a certain time period,
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Uber's booking fee remains approximately the same, as shown in Figure However, over 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 high even if these prices within their willingness to pay, aiming at inducing Uber to reduce the price or offer them coupons (which can be understood as negative service fee) reduce future purchase expenses. This phenomenon is common in both the psychology 6 and the economics 27 literature.
hope you enjoyed your ride this evening.
We hope you enjoyad your ride this evening.
Total
$24.17
Total
$14.03
Thp fore
$2290
from
$12.5
Subtotal
$22.00
Booking Fes
Rooking Far
$1.77
Figure I: 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 $1.27 for both, suggesting that fixed booking fee mechanism might be employed in February. However, over longer period of time, Uber may switch to a dynamic pricing strategy.
For third-party platforms, pricing service fees can face three challenges:
Demund information needs to learned. Typically platforms can observe the number and quoted prices of sellers on the platform. i.c., 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 uniform price for group buyers. Therefore, it crucial to learn about the buyer group's 's willingness pay.
2. Only equilibria can be observed. Regarding buyer information, platforms can only observe the equilibrium price and quantity, say pe and Q 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 Q*) may only reveal partial information about the demand curve and thus fail to recover the full demand curve. In the absence of randomness in the supply curve, (Pe, Q*) could even form an spward-sloping curve, far from the characteristics of demand curve.
3. Buyers muy exhibit strategic behavior. When buyers interact with the platform over an extended period, they may present false demand curve to the platform, hoping to gain benefits in future purchases, buyers increases the difficulty for the platform to accurately estimate demand, and at the same time, causes the service fee deviate from its optimal value, resulting in revenue loss. Pessimistically, Amin et al. [2] demonstrated that when the buyer possesses patience comparable that of the seller, no learning algorithm achieve sub-linear regret (cf.
shown in Example [.] The strategic behavior of
Appendix[F.G
In this paper, we address the above challenges by establishing the first 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 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.id.) random variables, or 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 algorithmss optimal regret bounds.
We discover that the randomness in supply can effectively assist in learning the demand curve. This counterintuitive fact reveals why, in Theorem 3.2 we can achieve a regret of (1), but in the case where there is no noise in supply, in Theorem 3.1 we can only expect regret of Ö(VT). We explain in Section via lower bound results (Theorem 4.1 and 4.2 that these orders magnitude differences are fundamental and unavoidable. Additionally, 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.
1.1 Related Work
This work is closely related instruments in machine learning
56
pricing with strategic buyers [55] 2 29 37 [I 38). and demand learning under uncertainty [14] 26
46 21 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
Notations. For any positive integer n, we let [rx] denote the set {1, n3 and n1 : m2 represent ( 72 1}. We use ((, d²) represent Gaussian random variable with mean j and variance a². Moreover, we use (.)) when ignoring constant terms while Ō(-) when ignoring constants and logarithmic terms. Similarly, we have 12(-). $2-). (--) and θ(-).
2 Model and Assumptions
We consider an online dynamic pricing problem faced by platform interacting with representative buyer for 7 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 f, multiple sellers pose different portfolios on the platform and thus form the cumulative supply curve, denoted by Ps: Pse (Q) function of Q. For example, Uber can observe in real-time how many different types of drivers are available on the platform, such UberX, UberXL, Black SUV, etc. Similarly, Ticketmaster knows how many tickets are still available in each area. Then, the platform sets a service fee 0e E IR RR20- Here we assume the sellers not strategic: as the platform formulates the fee-charging plan after observing (s((Q), there is no issue concerning trustfulness for sellers. In each round f, the representative buyer may receive private signal, such as a shock income, and form time-dependent demand curve, denoted by PD. = Prx (Q). However, the buyer may behave as if her demand is PD, rather than PDi because of her forward-looking strategic behavior, elaborating below. Together with service fee ag the platform observes an equilibrium price and equilibrium quantity in the market, denoted by (PF Qi), satisfying
P = Ps: (Qi) + a Pbe((.).
(I)
Then, the platform receives revenue IT = a. Qi Pbbss a+) in this round. a result, across the time horizon of T, the platform has cumulative revenue: Σ Q: (Pst. Pi az). As 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 [7] and instrumental variable models [56]
Assumption 2.1. Assume that the supply curve in round / has the form of
Pst (Q) <xp + aiQ Q + eSt
and the demand curve
Pp: 9o + $1 Q + Cpt- The independent noise terms Est and < follow normal distributions, o(0) and (00 o)), respectively.
3

---

To avoid nuisance from market feasibility, we assume that 3u > au 2 0, 01 20> 31, and that all equilibrium prices and quantities are positive and bounded. We note from Equation (T) that if Qi is negative, then optimal Qi shall be truncated as O. 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
service fees (37). Note that the buyer is only aware of the policy beforchand. If the policy involves randomization, the buyer knows in advance the policy but not the realization has suggested that
of the policy. In fact, previous behavior- based pricing literature
committing to a pricing strategy can help the platform earn more revenue.
In each time period t, the buyer receives surplus, say surplus, (Pst: PDL, PF. Qi, az), which depends on the supply curve, demand curve, equilibrium price, equilibrium quantity, and the service fee. For brevity, we will write Sur, as an abbreviation of surplus, (Pst, PDL, Pt: Qi, az). 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 7 E [0, 1). When 7 = O, the buyer is myopic and only considers her surplus in the current round f. She truthfully purchases the optimal quantity of items she needs. That is, her realized demand curve P/b, coincides with PDi- However, when Y E (0, 1), i.., the buyer is far-sighted [8] 72]. she may choose to misreport her demand curve Pb. Pp: in exchange for increasing long-term expected cumulative utility: EE 7 'Sur, where again Sur, is the surplus gained at time s. The expectation is taken over the randomness for all time s > t: supply randomness Es., demand randomness eDs, 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 s true demand. They can be either larger or smaller. Note that the buyer won't 't show her demand curve (Q) to the platform at all, and all the information the platform can learn is through observing equilibrium prices and quantities. Thus, is important for the platform design careful service charging mechanism motivate a truthful disclosure of the demand curve from the buyer.
Performance metric. With the help of the revelation principle 663, there is an incentive-compatibee direct mechanism for pricing to achieve the highest revenue. So, we can define optimal service fee from Equation T by
a
argmax Ela Qi Ppi, at)] 20
The expectation is taken over Pnr since the platform needs to set a, before the realization of Pn
Define the suboptimality at time / as
SubOpt, = Ela; (Pst, a;) - a. (Pst, Phrs 0:)]-
Our evaluation metric is then the revenue regret against a clairvoyant policy attained over the whole T' rounds, namely,
Regret(T) = Σ Sub)pt,
Remarks on the model. We would like to provide some further remarks on the model as follows.
Platform is patient while buyer's discount rate is ? E [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 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 localized segment of the market 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, Beshes and Zeevi [15] also suggests that in certain cireumstances, 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 non- linear models (e.g. log-log, semi-log model in hedonic pricing [66] and logistic model click prediction (51) like Ban and Keskin [3] with some extra assumption
non-linear factors, by utilizing the generalized method of moments (GMM). Our technique also has the potential to work in high- -igh-dimensional cases and even non non-nonnainn parametrii 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.
3 Regret Upper Bounds: Actions as Instruments
In this section, we present our main algorithm AaI aecion-as-Instrumennt and demonstrate its theoretical guarantees. We assume that T and as 2 are both known (oD need not be known priori). This assumption will be further relaxed in the next section.
Algorithm 1 Aal Algorithm.
Input: T.
Initialization: D < 0, A + and +- 0.
for episode 1, 2, ... do
Estimate unknown parameters: (9o, 31) IV(D,A) (Algorithm in Appendix C.
Form estimate for the demand curve Pn = Bo + 3.Q. Initialize datasets D and A 0.
for 7 = +++1 to + 2 do
Observe the supply curve Pst 02 + a2 Q.
Select the action a₂ Act(Pst. Pp) using Algorithm 2
Observe equilibrium = (P., Qi).
Update < D U or and A +- A dz.
end for
Update round index: f 4- t + 2 end for
Algorithm 2 Act Algorithm.
Input:
Ps and Pp.
Calculate â argmax,20 (a), where (a) is decided by Ps(2*) + Pb((0))
Generate an independent noise term N(0, (ive(A)+1
Set service fee a + a" + 1 = 0}.
Output: a.
We elaborate the design of AaI and how it overcomes the main challenges mentioned in Section [] We first demonstrate the design of our low-switching regime. In Algorithm T to deal with the far-sighted buyer, we update our policy when is power of 2. The intuition behind the low-switching cost update is that since the buyer has discount rate strictly lower than 1, long-run benefits will be hard compensate for short-run loss. Under low-switching regime, the gap between the buyer's behavior P/2 and the true demand curve Pp becomes small. In the existing literature. Ai al. utilizes explicit "buffer" periods against far-sighted buyers while other works such as Golrezaei et al. B7 38 use implicit methods to motivate truthfulness. In Algorithm [ we adopt an implicit way to punish untruthful behavior so that we don't '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 myopie buyer, though indispensable for a far-sighted buyer [34]]]] (
5

---

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 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 (5o, (31 which is rigorously shown in Lemma 3.1 (in the lemma only 31 is analyzed; similar result also holds for Bo).
Lemma 3.1. Let Bit be the estimated slope after round l. Then, under Assumptions 2.1 and 2.2 high probability, holds that
with
Vlog log
13 - - O
(1 (1-7)88 for all t E (T) when dg = O,
14
and
Vlog log T
13.. - Bil 0
o3(1 - 7)t for all E [T] when ag >
Jsvi
Now let's discuss the magnitude of the artificially added noise (see Algorithm 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: as = 0 and ag > O.
which serves as
3.1 05 0: Ö(VT) Regret
We first consider the case when there is no supply randomness. At the beginning of each episode m, we add a (1) noise 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 trade-off between utilizing early data and recent data the more data 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 ensure sufficient exploration.
Second, there is 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, episode m. the variance level of noise added is designed to be O /2mm on average where 2 is the length of the episode. It decays at relatively slow rate, aiming exploration without losing much exploitation. We note that special case of as is when the supply curve coincides with the Q-axis (Psr(Q) = 0) and the buyer has no strategic behavior
(y 0). This degenerates to the standard dynamic pricing problem 44] where ((VT) regret holds. The following theorem shows that with the additional features in our model (equilibrium observation, strategic behavior), an Ö(vT) regret bound still holds.
Theorem 3.1 (os = =0). Under Assumptions 2. and 2.2 for any fixed failure probability E (0, 1),
with probability at least - i, Algorithm achieves at most O(VT log( log
+ [1~7)² regret
log
against any buyer whose discount rate 7 E 0. 1) when supply doesn't 't have noise, i.e. of Here, O()) hides only absolute constants.
3.2 s 0: Noise Helps Learning
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 ā' (see Algorithm 2 The following theorem shows that noise helps learning
O(1) regret is obtainable.
Theorem 3.2 (as 0). Under Assumptions 2.1 and 2.2 for any fixed failure probability E (0, 1),
with probability at least 1 i, Algorithm achieves most (11o
log T log( lx log T
o3
a3(1->)
regret
against any buyer whose discount rate 0. 1). Here, (()) hides only absolute constants.
The regret upper bound in Theorem 3.2 contains two parts. The first Olog T) term 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 â" from Algorithm to vibrate around some intrinsic number. As result, the estimation of / generates a fast convergence rate of O(1/ vt) (see Lemma 3.1 even if no active exploration is presented. As a comparison, in Section 3.J 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 regret.
The second term is the extra regret due to the strategic behavior of the buyer. Golrezaei et al. regret in repeated auction pricing when the discount rate is
37 achieves extra O log (1/5)
log T
S 2(1 - 7) for y E [0. 1). we obtain better results in both the We note that since the implementation of Algorithm [ doesn't ' depend on the buyer's discount rate y, it can achieve O(log log log T) regret even if the discount rates are changing in different rounds as long as the discount rate "/ has uniform upper bound and 7 < 1, which is widely observed the real-world market, especially online advertising [31] Algorithm remains good permanence.
approaching one. Since log 1/7)
order of log T and order of
From Theorems 3.1 and 3.2 we know the key to achieve Õ(1) regret is the internal randomness of the supply curve. Therefore, we have the following corollary.
Corollary 3.2. the platform needs to uniform service fee in multi-markets, such as Order Processing Fee on Ticketmaster [17], the demand curve goes to
PD: = 3o + 31 & Q + ED:.
where & is the Kronecker product of two matrices. Then, as long as in one market, the corresponding supply has internal randomness, Algorithm can achieve ((1) regret by utilizing 0t as an instrument for all markets. Otherwise, it will suffer O (VVT) regret.
4 Regret Lower Bounds: Phase Transition
In this section, we present results on regret lower bounds. We will focus on the case when 7 = and investigate how the regret intrinsically scales function o' as well as. We will show that there exhibits a phase transition phenomenon with respect to and an inverse square law with respect to dg.. We first present 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 22( (TV In 2(-) we are hiding a constant term irrelevant with and T.
Next, we provide a lower bound when as can take any general positive number.
Theorem 4.2. Given any time horizon T and the supply noise level ds, the worst-case expected regret is lower bounded by
log T
Ω
OO log (1/os))
where log (+) max log(-)) In S2(-) we are hiding a constant term irrelevant with as and T.
The proof of Theorem 4.1 depends on constructing two hard-to-diiferrntiate instances such that the demand curves deviate with each other while the supply curves remain the same. The proof of Theorem 4.2 relics the multivariate Van Trees inequality [36] 44]. An important step in both of the proof is when considering the magnitude of demand noise p. it should be dependent on aj and 31- 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 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.
this will make it possible for a policy to learn more quickly by "cheating".
Now we give some remarks for the theorems. Theorem 4.1 states that the regret order in Theorem 3.1 is tight. It also implicitly provides some intuition for our choice of the magnitude of the artificially
7

---

introduced noise in our algorithm design. The total variance of noise we add is proportional to VT this shall be the largest noise magnitude we shall use for sufficient exploration to match the 52( [ (T) lower bound.
shows that if 0g > 0 is constant irrelevant with T, then our regret upper bound in Theorem 3.2 tight up log T factor. Moreover, Theorem 4.2 gives valid lower bound if as is entangled with T. To be precise, if o S O(L/VT), then the best we can hope is an ((VT) regret. Only when og Z (1/vT)) can we expect a regret bound better than (VTT).
Theorem 4.2
Readers may immediately notice that there is gap between our regret upper bounds (see Theorem 3.2 and the regret lower bound (see Theorem 4.2 when o & O(1/vT).. It raises the following question whether we can achieve the same regret upper bounds without knowing ag in advance. The answer is YES! We have the following theorem.
Theorem 4.3. Under Assumptions 2.7 and 2.2 there exists an algorithm, e.g., Algorithm 3 whose expected regret is at most Ó A as against any buyer with discount rate [0, Here, O()) hides only constants and logarithmic terms.
Algorithm 3 AAal (Adaptive Action-as- Instrummnts) Algorithm.
Input: T. for I. 1 to To ~ O(log 7') do
Observe market randomness Est or supply intercept Ogg + ESt-
end for
Hypothesis Test: Ho o's z O VT and H1 o 2 M ), denoting the result as Hll.
Conduct AaI(T - To) with Act Act-HT(II) HT( (IHI, .,)) (Algorithm) in Appendix C.2 replacing Act(,,)
In Algorithm 3 AT is essentially generalized version of Act: if Ho holds, we treat ds as if it is O; not, we treat ag as it is. When 7' 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, o x O(I/VT), the expected regret has fixed rate O ((VT), whereas when the supply randomness large enough, namely o3 2 R(1/vTT) the expected regret inversely proportional with respect to o² an inverse square law ignoring constants and logarithmic terms. Therefore, there exists an essential phase transition when o O(I/vT) (see Figure this tells us that we should take market randomness into consideration whenever solving pricing problems.
5 Numerical Study
In this section, 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
In the first experiment, we consider regret attained in Algorithm T under two scenarios. Here, we set T = 10". We replicate 10 times in each setting and draw the average regrets and their 95% confidence regions. We consider both constant o. and zero randomness Figure 2 It's obvious that when - = ((1), the growth rate of regret is significantly smaller than the growth rate when o. O. The first regret slightly larger than 200 and the second one is more than 1200, validating the respective (log 2 T) and O(vT D(VTlog T' expected regrets. Numerically, when 0 = 1, we find that the regrets when T = 20000, 40000, 60000, 80000, 100000 (log T 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 slope by linear regression is 0.47, testifying regret bound.
1.551)
supply, i.., 03 = 0, we have log (Regret) = 6.43, 6.75, 6.95, 7.10, 7.17, respectively. The estimated
Moreover, we increase the number of trajectories to 100 and observe that bandwidth of the corresponding confidence region significantly decreases (cf. Figure33rr (top, right)). Additionally, we test the regret under different o values, say 0.5. 1, 1.5 and We notice that the larger the a the smaller the regret, which confirms theoretical results (cf. Figure 3)

---

320
Mean
300
95% Confidence intrral
92% Corficence incaaal
10.0
250
200
600
100
250
0-
20300
40020
D00C0
50000
300000
20020
42020
50000
aboco
100202
Ro.ndk
Rourds
Figure 2: 95% confidence region of regret of Algorithm | over 10 trajectories: o3 (left) and o = 0 (right).
250
Near
250
Mitan
95% Confidence Interval
55% Confidence Inaeral
300
250
230
100
20000
40020
60000
50000
100000
20000
Pounds
Ibunds
Nean
Confidence Intarval
200
150
150
100
75-
25-
Figure 3: 95% confidence region of regret of Algorithm over 100 trajectories: o. = -,,5, (top bottom, left to right).
Then, we conduct the second experiment examining the dependency of regret supply randomness o... We set T 10 and range o from 0.001 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 HH, and we can observe the phase transition when o3 A 0.1. Notice that Algorithm has a (VT log 7') expected regret for Hg but O (TVoloog" T) for HI1 when o3 ~ O v
(cf. Appendix F.5). This additional log T factor explains why there is increasing fluctuation in regret near the phase transition point, as Algorithm engages in mixture of applying Hil and Hi, Finally, we employ locally weighted scatterplot smoothing (LOWESS) (25 to approximate regret for each level of randomness ag, with the fitting depicted by red line. We notice that regret first reaches plateau and keeps nearly constant and then gradually decreases, testifying Theorem 4.3

---

(R)
Data
8(v7)
600
400
200
6(1)
8(1)
08
Supply Randommess
Figure 4: Phase transition with supply randomness
Figure 5: Phase transition in Algorithm and its non-parametric local fitting.
o.. Aggregating Theorems
6 Conclusion
In this paper, 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 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 low-switching design. Specifically, in the case of supply fluctuations, achieve regret upper bound of (1), and when supply fixed, we achieve regret bound of Ö both of which match the cermmaationthhoreiiin 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 the discount rate y? Our conjecture is that a discount rate strictly less than will introduce inevitable Q ((==g) 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.
Acknowledgments
The authors would like to thank the reviewers for their valuable comments and suggestions, which have greatly improved the article.
References
[1] Rui Ai, Boxiang Lyu, Zhaoran Wang, Zhuoran Yang, and Michael I Jordan. A reinforcement learning approach in multi multi-phase second-price auction design. arXiv preprint 10Xiv:2210.102777 2022.
[2] Kareem Amin, Afshin Rostamizadeh, and Umar Syed. Learning prices for repeated auctions with strategic buyers. Advances in neural information processing systems, 26, 2013.
[3] Kareem Amin, Afshin Rostamizadeh, and Umar Syed. Repeated contextual auctions with strategic buyers. Advances in Neural Information Processing Systems, 27, 2014.
[4] Joshua D Angrist and Guido W Imbens. Two-stage least squares estimation of average causal ef- fects in models with variable treatment intensity. Journal of the American statistical Association, 90(430):431-4M)) 1995.
10

---

[5] Joshua D Angrist and Alan B Krueger. Instrumental variables and the search for identification: From supply and demand natural experiments. Journal of Economic perspectives. 15(4): 69-85, 2001.
[6] Bradley M Appelhans, Christy C Tangney, Simone A French, Melissa M Crane, and Yamin Wang. Delay discounting and household food purchasing decisions: The shopper study. Health Psychology, 38(4):334, 2019.
[7] Victor F Araman and René Caldentey. Dynamic pricing for nonperishable products with demand learning. Operations research, 57(5): 119-116991111 1188, 2009.
[8] William Ascher. Long-term strategy for sustainable development: strategies to promote far-
sighted action. Sustainability Science, 1:15-22, 2006.
(9] Peter Auer, Nicolo Cesa-Bianchi, and Claudio Gentile. Adaptive and self-confident on-line learning algorithms. Journal of Computer and System Sciences, (4(1))48-755 2002.
[10] Yossi Aviv and Amit Pazgal. Optimal pricing of seasonal products in the presence of forward- looking consumers. Manufacturing & service operations management, 10(3):339-359 2008.
[11] Yossi Aviv, Mike Mingcheng Wei, and Fuqiang Zhang. Responsive pricing of fashion products: The effects of demand learning and strategic consumer behavior. Management Science, 65(7): 2982-3000. 2019.
[12] Badi H Baltagi and Dan Levin. Estimating dynamic demand for cigarettes using panel data: the effects of bootlegging, taxation and advertising reconsidered. The Review of Economics and Statistics, pages 148-155, 1986.
[13] Gah-Yi Ban and Bora Keskin. Personalized dynamic pricing with machine learning: High- dimensional features and heterogeneous elasticity. Management Science, 67(9):5549-5568 2021.
[14] Omar Besbes and Assaf Zeevi. On the minimax complexity pricing in a changing environment. Operations research, 5911)66677, 2011.
[15] Omar Besbes and Assaf Zeevi. On the (surprising) sufficiency of linear models for dynamic pricing with demand learning. Management Science, 61(4):723-739, 2015.
[16] Lilian Besson and Emilie Kaufmann. What doubling tricks can and can't 't do for multi-armed bandits. arXiv preprint arXiv:1803.0699 2018.
[17] Milica Bosnjak. "get your tickets!" from a legitimate source: Primary and secondary ticketing markets nevada. UNLV Gaming Law Journal, 11(2):6. 2021.
[18] Josef Broder and Paat Rusmevichientong. Dynamic pricing under general parametric choice model. Operations Research, 60(4):965-980, 2012.
[19] Jinzhi Bu, David Simchi-Levi. and Yunzong Xu. Online pricing with offline data: Phase transition and inverse square law. In International Conference on Machine Learning, pages 1202-1210. PMLR, 2020.
[20] Felipe Caro and Jérémie Gallien. Dynamic assortment with demand learning for seasonal consumer goods. Management science, 53(2):276-29) 2007.
[21] Alexandre X Carvalho and Martin L Puterman. Learning and pricing in an internet environment with binomial demands. Journal of Revenue and Pricing Management, 3:320-336, 2005.
[22] G. Casella and R.I.. Berger. Statistical Inference. Duxbury advanced series in statistics and decision sciences. Thomson Learning, 2002. ISBN 9780534243128. URL https::/boook
google. cot.leeccoommbooosidd0oo 2tt.oookssPid-0S_.AAAAAA.. VAAAAMAAJ
[23] Shuxiao Chen and Bo Zhang. Estimating and improving dynamic treatment regimes with time-varying instrumental variable. Journal of the Royal Statistical Society Series Statistical Methodology, 85(2):427-433, 2023.
2023.

---

[24] Xiaohong Chen and Zhengling Qi. On well polsdeosssssss and minimax optimal rates of nonpara- metric q-function estimation in off off-po evaluation. In International Conference on Machine Learning, pages 3558-3582 PMLR, 2022.
[25] William Cleveland. Robust locally weighted regression and smoothing scatterplots. Journal of the American statistical association, 74(368):829-88) 836, 1979.
[26] Eric Cope. Bayesian strategies for dynamic pricing in e-commerce. Naval Research Logisties (NRL), 2463)2255-211, 2007.
[27] John G Cross. A theory of the bargaining process. The American Economic Review, 55(1/2): 67-94, 1965.
[28] Armoud V Den Boer and Bert Zwart. Simultaneously learning and optimizing using controlled variance pricing. Management science, 60(3):770-73,, 2014.
[29] Yuan Deng, Sébastien Lahaie, and Vahab Mirrokni. Robust pricing in dynamic mechanism design. In International Conference on Machine Learning, pages 2494 2503. PMLR, 2020.
[30] Alexey Drutsa. Horizon-independent optimal pricing in repeated auctions with truthful and strategic buyers. In Proceedings of the 26th International Conference on World Wide Web, pages 33-42, 2017.
[31] Alexey Drutsa. Reserve pricing in repeated second-price auctions with strategic bidders. In International Conference on Machine Learning, pages 2678-2689 PMLR, 2020.
[32] Alessandro Epasto. Mohammad Mahdian, Vahab Mirrokni, and Song Zuo. Incentive-aware learning for large markets. In Proceedings of the 2018 World Wide Web Conference, pages 1369-1378. 2018.
[33] Pnina Feldman, Andrew E Frazelle, and Robert Swinney. Service delivery platforms: Pricing and revenue implications. Available at SSRN, 3258739, 2018.
[34] Minbo Gao, Tianle Xie, Simon Du, and Lin F Yang. provably efficient algorithm for linear markov decision process with low switching cost. arXiv preprint arXiv:2101.004p0 2021.
[35] Ming Gao. Platform pricing in mixed two-sided markets. International Economic Review, 59 103-1193,,,,, 2018
[36] Richard D Gill and Boris Y Levit. Applications of the van trees inequality: bayesian cramér-rao bound, Bernoulli, pages 59-79, 1995.
[37] Negin Golrezaei, Adel Javanmard, and Vahab Mirrokni. Dynamic incentive-aware learning: Robust pricing in contextual auctions. Advances in Neural Information Processing Systems, 32, 2019.
[38] Negin Golrezaei, Patrick Jaillet, and Jason Cheuk Nam Liang. Incentive-awart contextual pricing with non-parametric market noise. In International Conference on Artificial Intelligence and Statistics, pages 9331-9361. PMLR, 2023.
[39] Harish Guda and Upender Subramanian. Your uber is arriving: Managing on-demand workers through surge pricing, forecast communication, and worker incentives. Management Science. 65(5):1995-2014 2014, 2019.
[40] Andrei Hagiu. Two-sided platforms: Product variety and pricing structures. Journal of Economics & Management Strategy, 1814):101 2009.
[41] Oliver D Hart and Jean Tirole. Contract renegotiation and coasian dynamics. The Review of Economic Studies, 55(4):509 1988.
[42] Conghui Jin. Research on consumers' delayed purchase. In 2018 2nd International Conference on Education Science and Economic Management (ICESEM 2018), pages 912-915. Atlantis Press, 2018
12

---

[43] Yash Kanoria and Hamid Nazerzadeh. Dynamic reserve prices for repeated auctions: Learning from bids. arXiv preprint arXiv:2002.07331, 2020.
[44] Bora Keskin and Assaf Zeevi. Dynamic pricing with an unknown demand model: Asymptoti- cally optimal semi-myopic policies. Operations research, 62(5):1142- 1167, 2014.
[45] L.R. Klein. Textbook of Econometrics. Row, Peterson, 1953. URL https://books:: google
com/booksiid-ae u2w.AAAAAAAAAAAAAA.
[46] Robert Kleinberg and Tom Leighton. The value of knowing demand curve: Bounds regret for online posted-price auctions. In 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings., pages 594 605. IEEE, 2003.
[47] Luofeng Liao, Zuyue Fu, Zhuoran Yang, Yixin Wang. Mladen Kolar, and Zhaoran Wang. Instrumental variable value iteration for causal offiin reinforcement learning, arXiv preprint arXiv:2102.09907, 2021.
[48] Kyle Lin. Dynamic pricing with real-time demand learning. European Journal of Operational Research, 174(1):522-5336 2006.
[49] Mei Lin, Xiajun Amy Pan, and Quan Zheng. Platform pricing with strategic buyers: The impact of future production cost. Production and Operations Management, 29(5): 122-11144 2020.
[50] Miguel Sousa Lobo and Stephen Boyd. Pricing and learning with uncertain demand. In INFORMS revenue management conference, pages 63 64. Citeseer, 2003.
[51] H Brendan McMahan, Gary Holt, David Sculley, Michael Young, Dietmar Ebner, Julian Grady, Lan Nie, Todd Phillips, Eugene Davydov, Daniel Golovin, et al. Ad click prediction: view from the trenches. In Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 1222-1230, 2013.
[52] Franco Modigliani and Shi Larry Cao. The chinese saving puzzle and the life-cycle hypothesis. Journal of economic literature, 42(1):145- 170, 2004.
[53] Mehryar Mohri and Andres Munoz Medina. Learning theory and algorithms for revenue optimization in second price auctions with reserve. In International conference on machine learning, pages 262-270. PMLR, 2014.
[54] Mehryar Mohri and Andres Munoz. Revenue optimization against strategic buyers. Advances in Neural Information Processing Systems, 28, 2015.
[55] Roger B Myerson. Optimal auction design. Mathematics of operations research, 6(1):58-73, 1981.
[56] Mila Nambiar, David Simchi-Levi, and He Wang. Dynamic learning and pricing with model misspecification. Management Science, 65(11):490055000, 2019.
[57] Maurice Obstfeld and Kenneth Rogoff. Foundations of international macroeconomics. MIT press, 1996.
[58] ROTT Peter et al. Personalised pricing (at a glance-study in focus). 2022.
[59] Amil Petrin and Kenneth Train. A control function approach to endogeneity in consumer choice models. Journal of marketing research, 47(1):3-13, 2010.
[60] Robert Phillips, Serdar Şimçek, and Garrett Van Ryzin. The effectiveness of field price discretion: Empirical evidence from auto lending. Management Science, 61(8):1741-1759, 2015.
[61] Sheng Qiang and Mohsen Bayati. Dynamic pricing with demand covariates. arXiv preprint 160iv:1604.00 07466,, 2016.
[62] Frank Plumpton Ramsey. A mathematical theory of saving. The economic journal, 38(152): 543-559, 1928.
13

---

[63] Tim Roughgarden. Algorithmic game theory. Communications of the ACM, 53(7):88-88 86, 2010.
[64] Stephen W Salant. When is inducing self-selection suboptimal for monopolist? The Quarterly Journal of Economics, 104(2)391-39) 1989.
[65] Rahul Singh. Kernel methods for unobserved confounding: Negative controls, proxies, and instruments. arXiv preprint 20X.:::0/22.03155, 2020.
[66] Stacy Sirmans, David Macpherson, and Emily Zietz. The composition of hedonic pricing models. Journal of real estate literature, 13(1):1-44, 2005.
[67] James H Stock and Mark W Watson. Introduction to econometrics. Pearson, 2020.
[68] Alexandre B Tsybakov. Introduction to nonparametric estimation, 2009. URL https://doi. org/10. 1017/b1390// Revised and extended from the, 9(10), 2004.
[69] Masatoshi Uchara, Haruka Kiyohara, Andrew Bennett, Victor Chernozhukov, Nan Jiang, Nathan Kallus, Chengchun Shi, and Wen Sun. Future-dependent value-based off-policy evaluation in pomdps. Advances in Neural Information Processing Systems, 36, 2024.
[70] Martin J Wainwright. High-dimensional statistics: non-asymptotic viewpoint, volume 48.
Cambridge university press, 2019.
[71] Tianhao Wang, Dongruo Zhou, and Quanquan Gu. Provably efficient reinforcement learning with linear function approximation under adaptivity constraints. Advances in Neural Information Processing Systems.
13536, 2021.
[72] Yinfei Xu, Yafei Zu, and Hui Zhang. Optimal inter-organization control of collaborative advertising with myopic and far-sighted behaviors. Entropy, 23(9):1144, 2021.
[73] Mengxin Yu, Zhuoran Yang, and Jianging Fan. Strategic decision-mate in the presence of information asymmetry: Provably efficient with algorithmic instruments. arXiv preprint arXiv: 11040, 2022.
[74] Feng Zhu and Zeyu Zheng. When demands evolve larger and noisier: Learning and carning in growing environment. In International conference on machine learning, pages 11629-11636 PMLR, 2020.
14

---

A Literature Review
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 [2]. 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, series of articles have emerged that use the IV method to estimate machine learning parameters. Yu et al.
773 Liao et al. 47] utilize
instruments to learn a nearly-optimal policy via offline data. Chen and Qi [24] Uehara et (69 adopt a parammrratticc instrumental variable framework to do off-policy evaluation. Chen and Zhang [3 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 IV in online learning problems, especially in pricing. Unlike offline data, the distribution of our instrument variable not only non-identical but also even non-independent. Meanwhile, we face a revenue- maximizing problem, we need to deal with the famous exploration-exploitttio tradeoff. More efficient instruments may decrease the estimation error leading to higher future revenue, but usually suffer larger short-term loss. Thus, prior research does not encompass our model and we examine the robustness of IV 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. [ study optimal reserve
design problem original from Myerson 555 facing strategic bidders while Mohri and Munoz [54] considers a corresponding revenue optimization problem. Golrezaei al. [38 considers pricing with strategic buyers under non-parame parametric market noise and Ai et al. [[] 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 econometries address this issue.
Demand Learning under Uncertainty. Demand learning is a hot topic in microeconomics, man- agement science, and operations research [14] 26 46 21 7 48 20) Lobo and Boyd [50] considers a linear demand model and invents a "price- ditcee-ithering" policy to add perturbation. Den Boer and
Zwart 28 invents the controlled variance pricing idea and Broder and Rusmevichientong
18 scales
exploration by adding 1114 which has similar connotations our approach.
Nambiar et al. (56] considers confounders in demand learning but doesn't 't involve strategic buyers. We extend high-level econometries ideas behind it and design recipes against non- non-trutioe 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.
B Discussion on Assumption 2.2
We clarify the definition of Sur, 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 producer surplus and consumer surplus. Then, it holds that
Sur, 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 common form of business organization, especially developing countries, such as China (see Modigliani and Cao (22 for more information). Because the buyer cannot receive dividends from companies, she
15

---

Specifically, Algorithm details the will only maximize their consumer surplus, namely,
Sur, Consumer surplus at time t.
Finally, for mixed-ownership enterprises, portion of the profits will be distributed the buyer in the form of dividends. We use a E 1) to denote the proportion. Therefore, we have
Sur, Consumer surplus time + Producer surplus at time t.
Hence, make Assumption 2.2 in our paper, all sellers civilian-run enterprises. We point out that this assumption won't 't affect our results and regrets with the same order can be obtained under state-owned enterprises and mixed-ownership enterprises. Here, detail Assumption 2.2 Assumption B.1
the definition of Sur, to
Assumption B.I. 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, has the form of
Sur; = Consumer surplus at time Producer surplus at time t.
C
Omitted Details of Algorithm Implementations
C.1 Omitted Details of Algorithm
In this section, we present the subroutine used in Algorithm] coefficient estimation process.
Algorithm 4 IV Algorithm.
Input: D and A.
Regress {Q=, pc} on {at]: Q = ā + aia, P = by + bia.
Estimate 31: 31 b1 ai
Calculate sample means
Q
size(A) E. and Pe Sue(A) E. Pe.
Estimate 0p: 8g Pe 3.Q
Output: (3o, B1).
C.2
Omitted Details of Algorithm 3
We fill in the details of Algorithm below.
Algorithm 5 Act-HT Algorithm.
Input: H. Ps and Pp-
Calculate â" +- argmax (a), where (a) is decided by Ps( + P)(Â9).
Generate independent noise term NNO,, Vsze((a)+1
Set service fee a +- a + 1H Ho).
Output: a.
D Concentration Inequalities
We now recall some inequalities 770 which bound the accumulated difference of martingale and are extensively used in our proofs.
We define g for convenience.
16

---

Lemma D.1 (Bernstein-tyy -type bound for a martingale difference sequence), Let be martingale difference sequence, and suppose that [eAD F S 1//2 almost surely for any
[|] 1/ag. Then the following hold:
(a) The sum Σi=1D Dy is sub-exponential with parameter tuple (v (vEn= U a.). where a, =
ma.k= Ock.
(b) The sum satisfies the concentration inequality
2
if0 S <t Σi= " ift Σk-1
2e
DR
1
S
2e
a.
Lemma D.2 (Hoeffding bound). Suppose that the variables X,, = I..... n. are independent, and X; has mean μr and Sabb-aassiin parameter de. Then for all 2 have
{
t2
Σ
(X: mi) 2 S exp
2 1==1
E
Omitted Proof in Section 3
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
E.1 Omitted Proof in Section 3.2
Since we assume that all equilibrium prices and quantities are bounded, reflecting the buyer's budget constraint and sellers' production capacity, use P and Q represent their upper bounds respectively. Moreover, recall that the buyer is myopic, so the demand curve behaved P is the same the real demand Pp.
We first consider the situation which the buyer myopic as warm-up. We have the following theorem.
Theorem F.1. Under Assumption 2.1 for any fixed failure probability E (0,1), 1), with probability at least 1 Algorithm achieves most O log logl loe
regret. where O(-) hides only absolute
constants when facing a myopic buyer.
E.1.1 Useful Facts for Proving Theorem
E.1
Now, we state the following lemma for the planning problem first.
Lemma E.1. If So and 31 are common knowledge, the optimal service fee is a" 90-00-20 -o- Meanwhile, the corresponding equilibrium quantity Q 2(01-81)
Proof. Since Ps = au + a1Q + eg and PD = Bo + BIQD + ep. applying Ps + a = PD leads
to Q
8o 0o atrp- As the platform cannot observe eD when setting the service fee a, i.c.
-1
eD is realized ex post, the expected revenue associated with a is Ea Qe (fo og -a-esa It's
maximized when
30 00
With some calculation, we know that the equilibrium quantity is
3o O'p 6. 2
Q
2( - B1)
The reason why es appears explicitly that the shock on the supple curve is ex-ante and observed by the platform.
D
17

---

Thereafter, we'd like to bound the estimation of 30 and 31 in Algorithm 4 proposition. We ignore the flooring in [log2 I throughout this section avoid notation clutter.
We have the following
Proposition E.2. Let 31 be the estimated slope of Algorithm 4 after the mith episode. Then, under Assumption 2.7 there exists a constant C₁ such that with probability at least 66, we have
131 - Bi Civlog log
for all m E [log2 T}
then
Vlog log
1i -11 O
for all & E [7],
JsVi
where subscript represents which round.
Proof. After the m-th episode, know that have data sets D and A with Size(A) = 2 Then, we need to prove that there exists a uniform constant C₁ such that |3= 311 < C Civlog T
Since during episode m, choose the service fee io-ap-rs where Bg is the latest estimate of So. i.c the estimate after m - 1-th episode. With a little abuse notation, we omit the subscript with 30 along the road of proof without confusion.
When Size(A) length n. We use E, to represent the sample mean and E to represent the population mean. With simple algebra, we know that
it means that there samples in the data set, that is to say, trajectory of
E, P En
E Pf a, Σ Q9 a,
3
En Qa - a.
Since P = 8o + +.000 E as (P",0* is on the demand curve, it holds that
E EDila: - E,
i 31
E Qi(a; a),
First, we bound the numerator プ Σ, zy denote Σ, CDiCsi for simplicity.
1= DD DD - am))
- 1 Ei EDiESI + + EnEEEEDD. We use
2n
For 1 E, F,, we leverage Lemma D.I to give Bernstein bound for the corresponding martingale difference sequence.
Lemma F.3. There exists constants ny and such that with probability least 1 5, it holds that for any n 2 ny where n = 2m and m E [log, T).
2y log( log
Proof. In our case, we know that ag depends on not only previous e and es, but also és;- However, doesn't 't rely éDi. This conditional independence motivates instruments. Similarly, x; has the same property. Therefore, by utilizing this independence, we know that
actions nearly valid
Elr; E1 x; - = [E(eDi] * IB[esi II,,.., r:-]] 0.
As result, ) becomes a martingale difference sequence and we use F denote associated filtration. Then, let's compute the noment-generatinn function (MGF).
E Ae Ar [(-1l= = expp(esstD)
20
20 degdep
V2T0S
V2ROD
VI
No0007
18

---

as long as X - 1 equation comes from simple algebra.
dg0D The first equation comes from the definition of ep and es while the second
Therefore, assuming 20 D. we know that for any d^] - a
Eie [F-11
20300
VI-XO
Then, assuming v = / D V2 it holds that vú is sub-exponential with parameters (v,a). a).
20 log( 2logg T
With the help of Lemma D.I
we know that long as
fi., with probability at
2vd log( alugg T)
least 1 log, Σ 24| I
Since there most log, T kinds of different
values for n, the total sum of probabilities of bad events is less than log.
8
loga T ô, which ends
the proof.
For E, we have the following lemma therein to bound it.
Lemma E.4. With probability at least - 5, it holds that for any 2 and m E [log2 T] that
20
log( 2og, T
ESi S
n
Proof. For any n = 2T where m E [log2 T7. we know that Est sub-Gaussian variable with parameter as because follows distribution (0)
By applying Lemma D.2 namely Hoeffding's s inequality, it holds that with probability 1 log, T
20 log( 210g,
csa S
n
Combining all nuisance leads to the probability of all inequalities holding, that is, 1 - 8, which finishes our proof.
Moreover, for Ex D. we have similar result whence giving an upper bound for it.
Lemma E.S. With probability at least - 8, it holds that for any 2 and E [log2 T] that
2a log(
21og, T
Dpa S
n
Proof.
The proof is the same as the one for Lemmal E.4 with replacement of Es; by EDi-
Second, let's give some concentration bounds for the denominator E.= Q7 a,
By applying Lemma E.1 we have the following decomposition of the denominator that
(iaa - E,a)
Σ 2(a, - E,a)eD Σ - E,a)es + Σ (at E,,))(20 -30 (an)
= 2n(a) - B1)
We use E, Ii E, 2i and E. 24 to denote for shorthand 2 - E,a)EDi. E, Ena)esi and Ea - (2,0 Bo an) respectively.
19

---

From Lemmas E.3 to E.5 we know that with probability at least 1 36, it holds that
2v² log( log T
go log( 2 log, T
where v are defined in Lemma
For 1/2 Ei Vi. we have the following lemma to illustrate its property.
Lemma E.6. There exists constant n2 such that with probability at least 36, holds that for any 2 f2 where 2 and m E [log2 T},
3P
log P 20 log
8log(
2o0g, T
1/
S
+
2
2
80
Proof. Let's decompose yi - E,, egi
eS
2
For - ESi. similar Lemma
E.4 it holds that with probability at least 6, for all n 2
E, * Essl
= Σ Esil *
aE
11
P Σ
ESt
20 log( 2 log T
< PV
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 Be=ca Est depends on previous ED and eg but don't est. So, it holds that E[t, (t..... denote the corresponding filtration. Since have the following MGF
denote it. Like the proof of Lemma E.3
know that 3o only = O and we use F to
A3 ag)
22
EleA1: [i
52
32
we know that f, sub-Gaussian random variable with parameter 4 which is also sub- exponential with parameters (=sP, 0). With Lemma D.1 we know that with probability - 5
30 an
o log( 21og, T
cssl S PV
for all E [log2 T] and 2
n
2
2n
For the term
2
since 8,
xi and xi is sub-exponential with parameters (2, 4). we know that
2
o
with probability
So log( 2 2loga T
St
03
<
2
2
as long as n 2 8 log(( 2 log T Accordingly, combining the above three terms leads to the needed lemma.
:= 722-
For 1 "E 2i, we notice that it's indeed zero. It holds that
n
Σ (a:
(280 300 -oo) = 0,
zz
due to the definition of a.
20

---

With the bounds for both nominator and denominator, it holds that
13 811
2v log( 2l
agop log( 2 T.
2( B1)(21
0 2v/2 log 2oog? ) 20 log( lowg
3/ 20 log( 2log2" )
Borg logl 2 2oog
a Then, there exists constants C2 C3 and C4 such that when a 2 max n2, C3 log log T} C4 log log T, 131 B1|
2
a
Øsvn Cavloglog T due
V2 Note that Cs E ( from previous
definitions and process of proof.
When - C4 log log T, can choose large enough constant C3 such that a is greater than trivial bound for 31. Since we care about the situation when dg is small, the probable appearance of it in the denominator won't cause trouble for Afterwards, by setting C1 max max/C2, C5}, find a uniform constant such that
Civlog log
B3 --11
2m
Moreover, we know that after the m-th episode, i.e. in the m + 1-th episode, {2th1 2m+2 - 1}, then z ((2)). Therefore, from the above, we know
B - 311 S O Vlog log for E [T].
asvl
Whereas when calculating the probability of bad events, there some redundancy, after calibration, the union bound on the probability of bad events is 66 which ends the proof.
Since we can estimate 31 with high accuracy. we similarly have the following proposition about the estimates of 3n when Proposition holds.
Proposition E.7. Let 3o be the estimated intercept of Algorithm 4 after the m-th episode. Then, under Assumption 2 and conditional on the event that Proposition E.2 holds, there exists a constant Dj such that with probability least 1 - 8, we have
D Divlog log for all m E (log, T),
130 - Bol s
@sv2m
then
Mog log
BB.. - -ol S 0
for all t [T],
asvi
where subseript t represents which round.
Proof. It holds that for any n = 2m , with probability at least - 8,
B
Bel 13 3, E,,Epl
< 18 Q - -3, En
[ 111 311 EnnDD
S CiQyToglog log
2 log( 2log, T
OsYR
The first equation comes from Algorithm 4 The first inequality holds due to the triangle inequality while the second inequality holds due to Proposition H.2 and Lemma E.5
Then, for any n 2mm there exists D2 such that 80 t == (n), it holds that
Bol S
Diyloglog Similarly, since asyi
log log T asvi
Box Bol $ O
Finally, bad events coming from E,ED have cumulative probability of å which closes the proof. -
21

---

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
E.1.2 Proof of Theorem E.1
Proof. With Appendix E.1.1 hand, we are ready give high probability upper bound for the total regret.
We use f() to denote Ea Q PPs, = -0 aa- a- a1 a. Then, with an ordinary Taylor-series
expansion and the mean value theorem, it holds that
(f(a)) (a) - -ae) + da
1 df faat + a)ass) (aū at)²
Sub
da²
where E [0,
we know that a/(a)) 0. Besides, it holds that (a; - -00200155 Bol3) s
From Lemma E.1
0 log log T
due to Proposition E.7 Then, since
is uniformly bounded by constant, namely df da
01 have that
log log T ozt
SubOpt, (a)) S 0
As result, it holds that
log log T oitt
log T log log T
Regret( (T) Σ (ubOpt, x
0
The last inequality holds due E.= 5 51 n.
The total odds of some inequalities not holding 78. Among them, 65 derives from Proposition E.2 and 8 originates from Proposition E.7 Note that only appears in log log T terms. Setting = 70 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.
E.1.3 Useful Facts for Proving Theorem 3.2
Since the buyer may behave having a different demand curve P/ rather than the true one PD, we first give the following proposition of depicting such untruthfulness.
Proposition E.8. For any behavior Pa we can fully characterize with a drift parameter yp- Consequently, without loss of generality, we can assume that
P Bu + 31Q cDt + TDE
Proof. Since the platform can only observe achieved equilibrium price P and quantity Qi each round, we only need to find an associated Tip leading to the same results.
By setting 7D: = P. 3o Q <Dt. we find that (P: Q?) will satisfy Equation T Since two lines in Euclidean space have most intersection point, we know that you fully describes Pb and this correspondence is unique, Hence, we can use Tip to represent untruthful behavior P/ and finishes our proof.
Using the equivalence in Proposition E.8 quantity and the service fee.
we present the relationship hetween equilibrium price and
Lemma E.9. For any valid service fee and tuple (Ps, Pb), the equilibrium price and quantity follow
Bo ag - a + ED - Es + dD
Q==
31
22

---

and
pe 01,30 00 - 3i0 + DIED - Bies + 0170
31
respectively. Then, the change coming from dyp leads to
[117DD IjD and A Ape
Q
01
01 - 11
Proof. From Proposition and Equation T we can have the formulas for Q and Pe with some simple algebra. Furthermore, comparing them and the ones without 1)n leads to the formulas about AQ" and AP", which finishes the proof.
With these preparations, we are ready give some properties of TJD and show good performance of Algorithm
Lemma E.10. Considering the m-th episode of Algorithm ! in the i-th round of this episode, we use nDi denote 1D(2=+i-2) though little abuse of notations. Then, it holds that for any rational buyer,
InDa S (01 3:1
VI-
where the m-th episode contains n 2 rounds. More precisely, holds that
(01 - -3
Proof. From Assumption 2.2 we know that
Sur [o (Po (Po-Ps-a)do a)QQ.
o
Therefore, know that in the i-th round of the m-th episode, the loss of surplus is
ASur 1 (B a1) 0r
v
Since the update of the estimation of (Bo, B1) happens in n i rounds, the maximum gain from misreport bounded by
7" n0- (a: - ²1) 2 (0 -11-
J+1 (an -1)00 < Σ 501 Σ ý=nーZ
2(1 2(1-7)
because the surplus is bounded by a trivial bound - in each round. The inequality holds because every term is positive. With some calculations, we have the final equation.
Hence, we know that the buyer is rational, she will guarantee that
Tix
n- i+1 (a1 [1)
2(1 7) 2 0,
2 01 - Bi
ending with
(a1 - -31
v1 7 7 n-1-1
When we consider all n rounds in the m-th episode as whole, we know the total loss of surplus at the point of the last round the m 1-th episode En 7 2 -1 The maximum surplus increment is less than n (a-8,) For a rational and strategic buyer, it holds that 2(1-))
nh
S 2nnt n+1 (a -1)@2
2n
31
2(1 7)
23

---

leading to
(al Q2
Σ i=
i-n
7-7
which finishes our proof.
We notice that since the buyer owns strictly less than discount rate, if we inverse time, the bound of misreport will exponentially decay. Therefore, have reason believe that these misreports will significantly affect the estimation of parameters. Consequently, we have the following propositions.
Proposition E.11. Let 3
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 - 68, it holds that when 2 2 O log log
0
Vlg log T
1
|3 B1 0
2m ama 7) for all [log2 T]:
JSV mm
then
log log
1
B3 - 311 O
for all [T],
JsVi
01s(1 - 7)t
where subscript t represents which round.
Proof. Similar Proposition
it holds that
- <Di - E,
Σ. nDi Ena)
3 = 31 +
+ 1 E (i E,
E Q9 - a)
For the numerator, we know that with probability at least - 35,
2v log( 2 T
D log( log,
Diaa, Bna)l S 2
8
due to Lemmas Moreover, we bound 1 Ei nDi(a, - an directly in leverage of Lemma E.10 It holds that
2P n
n nDi(a: Enaal= <
mDd
n
2P
7
TDi
2(01 - PQ ?
m/1 -
1
V1 1--7
2(0) - -3:)
n0l-7)
The first inequality holds due P while the second inequality holds due to Lemma E.10 and Cauchy-Schward inequality. The third inequality holds because every term in the summation positive and the geometric series sum formula.
For the denominator, since AQ nD/(ai 31) from Lemma N1 Di=1 - (a: E, It holds that
E.9
we only need bound
2PQV7 B1 (a: E,,) <
n(1 7)
due to the same process as bounding
1 Σn IDi(a, Ena)) above.
24

---

Therefore, we notice that
(a: - (naa) 2
1
03
2
2v² log
2ooga
8
20 log(
loga 7
71
2(
31)
n
3P
20 log( 2 logg T
80 s
log(
21og, T 6
2PQV7
2
n1 -7)
with probability at least 66 due to Lemma E.6 Combining all these terms, it holds that
EDi(a: a)
nDi E
13 Bi
n
i==1 Oi E
n
Q7 a)
(
Alog log
0 - O
Mlog log
0
O - O
Algg log
0
vn
/n2
Mogloog
Jsy'n
no 5 -7)
00 Vlog log T
1
5sV2" 2m
2m o
7)
The first inequality holds due 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 2 Besides, taking into account repeated bad events, the probability of all inequalities holding is at least 65. Here, we need O log log T
o3(1-1))
Considering that for any round in the 1-th episode, have & (2 - 1: 2 - 1}, it then holds that
v log
Vlog osvi ozi(1 - for all [T].
BIr o
which ends the proof.
Conditional on having good estimation of 31, we have the following proposition, saying that we can also estimate 3o precisely.
Proposition E.12. Let Bu be the estimated intercept of Algorithum after the m-th episode. Then,
under Assumptions 2.1 and and conditional on the event that Proposition E.17 holds, we have with probability at least
log log
130 - Bol S 0
2m am03(( - -7)) for all m E [logz T],
0 2
then
13w. - 3ol S O Vlog log
03 7)t for all [T].
osvi
where subseript t represents which round.
25

---

Proof. We know that 30 = Er, - B1E, Q" Thus, it holds that
18u Bul s En - 1² -ul
< 18, + ENED + +E - Q4
s 181 31|* 1a + ED + DD!
x 181 - 31 Q + cnc + Enlnol
Mog log T
20 D
log( 2oog, (a) 31)QV7
Q O
no (1)) +
ØsVn
11
n(1 (1)
2 00 log log'T
Jsvn
no 3 (1
The first inequality holds due to the definition of 3, 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 Jensen's inequality and trivial upper bound Q. The fifth inequality holds with probability at least 1 5 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
log log asvi
Bo - Bul 0(
rzt(1- (3((1-)) for all E [T].
which ends the proof.
Propositions E. and E. 1..2 highlight the statistical efficiency of Algorithm @ven when the buyer far-sighted, showing the robustness of our algorithm against non-myopic strategic agents.
E.1.4 Proof Theorem 3.2
Proof. We recall the definition of SubOpt, in round first, that is, (ae)
|saa Q* (Pst, (Psst,Pride az) a * (Ps Pe: de)].
Hence, the triangle inequality gain
SubOpt,(a))
Taaa Q (Pst. PDe, az) - a, * (Pstt PDi, at){+
Eaa+ (Psc PDu, 0z) a (Ps P at)l.
For the first term, it holds that
log log T ozt
Elaj * Q" (Pst, PD., ar (Ps,ss, adl & 0
pst(1 7)
where the first term similar to the proof of Theorem E.1 For the second term, since df we use the first-order approximation to obtain We thereafter know that
2P
(ai-31)
Σ Bla * (Pst PD., ai) - a, QPss,, at) S 0 log log log T
T
log T
o3
03
For the second term, holds that
E Eaa (Pst, PDu, at) a. Q" Pba ar)l < Elai (Q PDc, ai) - (Pst, Pby, a:)l
< P + E|Q" (Pst, PDr, a.) - Q" (Pst, P/ P/ 4:)
p
<
mDrl
01 9
26

---

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 inqquality holds due to Lemma E.9
Then, during the m-th episode, there are n. = 2 rounds and we have
P
PQ
DDi -
-I- (v7)
a1 - 31
and
(an 81
7hi I
1 1-9
Furthermore, it holds that
T
P
log,
2
P
log,
P
(01 31)QUT
PQ
log,
Σ
noa = Σ 31
nod
S
01
01 31
01
31
1
1-y
7
==
===
The inequality holds due to the same process when proving Proposition Lemma E. 10 and Cauchy-Schwand inequality.
E.1
It comes from
Consequently, we have
Regret (at)
log Tlog log T a's log Tlog log
log T
PQ PQ-Tloge T
log log T
1
+ +0
- 7) 0 5
1 1-7
T
0
log T
2 00
03 (1) )
with probability at least 1 78. 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 2 O log log T o3
Finally, 5 merely hides within log log T terms, setting 75 leads to the desired result and finishes our proof.
E.1.5 When Facing Time-varying Discount
When the buyer has time-varying discount rate Tt. we can replace it with its uniform upper confidence bound 7 in the proofs of Lemma E. propositions E.IT 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 7, Algorithm I still achieves Ollog 7 log log T') regret with high probability which ends the proof.
E.2 Omitted Proof in Section 3.1
So as to prove Theorem 3.1 we state some auxiliary lemmas at first.
E.2.1 Useful Facts for Proving Theorem 3.1
Recall that we use to represent added noise which follows (0,
(Aize(A)+11 and ni to represent
the distance between P/ and Pp thanks Lemma E.9 We have the following lemma to depict the equilibrium price and quantity in each round.
Lemma E.1 For any estimation 3o and tuple (Ps, Pb), the equilibrium price follows
Q = 2,8
Bo Og + 2 + 2np 2
2(01 - 31)
27

---

Then, the change coming from TlD leads to
1/D AQ
81
Proof. We get the formula of Q from Equation with es = 0 and the implementation of Algo- rithm Moreover, due to Lemma E.1 we know the optimal ex-ante service fee a* -e-do without
untruthful behavior and extra noise term E.
Since the choice of is independent of y/,, we know that Lemma 10 holds, that is, in the i-th round of m-th episode, the quantity of misreport fjnı follows that for the rational and strategic buyer,
(a1 01)²
Σ
DD
1 7
where the m-th episode contains n n rounds.
Subsequently, we are ready to bound the distance between the estimates of 9o and 31 and their true values.
Proposition E.14. Let 31 be the estimated slope of Algorithm 4 after the m-th episode. Then, under
Assumptions 2. and 2.2 with probability at least - 86, it holds that when n Z O(log T log log T
(1-7)))
Vlog log T
1
-1-B11 Bi1 0(
2 (1 77) for all m E [log, T},
2
then
Vlog log'?
13,1 - 3:1 S 0
(1 - >)v for all t E [T],
1
where subscript t represents which round.
Proof. Let's first decompose the error terms of estimating 31. Assume that n = 2m as usual. From the implementation of Algorithm 4 we know that
Em, Em_(( E, PE]
E Enilu; Bna)
+ Di=1 np: E,a)
3,
[a E,, QF B1
E Q7 Ena)
E Q9 (a: - Ena)
- it holds that 1 E (D: End) = 1 E. E #ED EnE ENED. Let's bound them one by one.
Since
First, let's give high probability upper bound for 1 Σn G * CDi. We note that it's a martingale difference sequence because epy has mean zero conditional on previous events. From the proof of Lemma E.3 we know that e * EDi is sub-exponential with parameters P/2 42% and a, 2/
because Var(c:) Vi Then, it holds that due to Lemma D.I
n2t²
P() Σ E end 2 nl) < 2exp(
2 Σi=1 0
< 2exp(
V 80 D m
3/2222
2exp(
808
The first inequality holds due to Lemma D.1 while the second inequality holds due to vn s
//83 log( 2logg T)
Σn vi S n Hence, by setting < log Besides, we need nt
it holds that P[ Σn E Enil 2
n3/4
Ei max, a. 2 O(log log T).). Finally, we have that with probability at least 1 8, for any m (log, T).
5
A sufficient condition is 2 (8 log( 2 2ogg T)) then
V 180 log( 20gg T
EDiei S
33/1
7
28

---

For the term EDE, we have the following result from Lemma
E.5
20 log(
2 loga T
E S
n
with probability at least -. 8.
For the term E,, we know that eq sub-Gaussian with parameter o; 774. Consequently, it holds that
V | 2oog, T
12/44
with cumulative probability at least 8 due Lemma D.2
We thereafter bound the term 1 Di= (a; a,).. From Equation n bound directly inherited from the proof of Proposition E.1 that
we can obtain the following
2(an -B1)PQTT
nDi(a E,a)l s
n(1 ((1-7) 7)
After that, we need to investigate the property of Ei= Qi Ena). We divide into three terms. It holds that
Qi a)
1=1
Di((a E, + 1 Σ (a - a, + Σ
(-;) E, a)]
0 B
i=1
From previous results, we know that with probability least 35
/802 log(
2log, T
/ /880 log2( 2 T
1911 <
3//
5/4
and
2(a1 - -B:)
1g2l 5
n(1 7)
For the last term (s. it holds that
43
71
1=1
Besides, we know that with probability at least
6, it holds that
4log( 2 T
4 <
3/2
due to Lemma D.2
Finally, for Σi e, we know that e; N(0, +t) and they are independent. Therefore, ef is
2 sub-exponential random variable with = vi and a; Vi with scaling of Xi random variable.
So, from Lemma D.I it holds that
n222
nt
P(
2 nt) max 2exp(
2 expp(-
8
8
2a*
29

---

where at max; ag 4. By choosing max
8(1++log T) Inge loga
8 log
luga
n
know that with probability at least 1 - 6, we have
1=1
8(1 log T) log(
2 log.
8 logg(
log,
T
v log T log log T
I max
2 0
n
n
n
for any 2"h Here, use facts log E 1 +
log and S T.
So, with probability at least 28, we know that
V 8(1 log T) log(
2 ioga T
8 8log(
2log
4 logg(
2 2loga T 3/3/2
max
Vn
7
v llg 7 log log T
O
Vn
7
Combing all these terms, we know that
1/80B log( Plnge T
188 log" 2log 2
(a1 - 31)
n5/s
n2/4
1211 n2(1-2)
131 - 111-
O y Vlog Flog log
B80B lop( 2logg T
v V80B lorg
2logg
2(m PQ
123/4
n574
m(1-7)
log log T
2 0
Vn(1 - 7)
1/4
long 2 Olog T log log T (1-)))))
Since we know that = O(n), holds that with probability at least 88,
log log T
18 B11 0
VB(1 - )
which ends the proof.
Now, we have the following proposition to bound the estimation error of 30 in a similar manner.
Proposition E.15. Let Bn be the estimated intercept of Algorithm 4 after the m-th episode. Then, under Assumptions 2.7 2.2 and conditional on the event that Proposition E. holds, have with probability at least b.
Vlo log T
1
130 Bol s 0
24 -)) for all E [log2 T},
then
Bu. Bul S O
Vlog log
(1 1-) for all t E (T),
1
tà
where subseript t represents which round.
30

---

Proof. Similar to the proof of Proposition E.12 it holds that 3. = Er, - -, L". Consequently, we have with probability at least d,
BBu Bul - E,, P B Q² Sol
s 11 Q" + E + BuTID 31 Bn Q
< 1 10.--11- * |n + [ + |E 7pDl
< 13 31 Q |BEED En!DD!
Vloglog log
2 log( 2108g
(01 - -1)QV n11 -1)
2 Q 0
n//
Vn(1 - -7)
n
Vlg logT
1 /m(1->)
x 0
1//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 14 and the last inequality comes from simple order of magnitude analysis.
Similarly, have that
log log
1 Sol 2 0
+
for all t E [T],
vi(1 7)
which ends the proof.
Propositions E.14 14 and E.15 show that although add approaching zero noise to explore the unknown environment, we can asymptotically estimate true parameters 30 and 31 accurately. Nevertheless, comparing with Propositions E.2
E. and E.12 the convergence rates have decreased to certain extent, ultimately resulting in larger regret.
E.2.2 Proof of Theorem 3.1
Proof. Basically, similar to the proof of Theorem 3.2
decompose the SubOpt(-) into two parts.
SubOpt,
< aa Q (Pst, ai) a. * Q" PDi, at)l+ Eaa (Pst. PDu, 0z) (P P az)l.
We know that the optimal service fee at round is at = fe-cn while the service fee we set is 0o og + Therefore, considering the Taylor's expansion, it holds that
Bla (Pst PDe, at) at * Q" PDi, az)l S O log T
111 11- + +7,
Vt
where the expectation is taken over EDz due Proposition E.15 and
+ b c)2 S 3(0² 62 d²).
Considering the m-th episode, we know that there are n 2m rounds it. Since we already have
that
1
log 7 log log
Σ
[=1
with probability at least
logz 7. it holds that
8
n
Σ
c soOVi Vlog log T")
This will lead to the following result that
Σ ((SOVTT)
31

---

because of the geometric series summation formula.
As result, get
PDi, Σ Ela (Ds, at (Pst, PDt, & O log T log I with probability at least - 8. As for the second term Ela, Q a+) (Pst, P 0z)l, similarly, we have
(1 7)2
T
a (Pst; PDi, 0z) - ar * (Pst, Drs at) PQ 202vlogg2 T
Σ
1-y
[=1
due to Equation 2
Recall that we also need that n Z Ollog T log log T (1-73r) to make Proposition E.14 hold. Combining all these terms, it holds that
Regret (T) = SubOpt,(a))
O (VT log log T + log T
PQV7log, T + O(log T log log T +
1
(1 7)2
1-7
7)2
I O log log T + log
(1 7)
with probability at least 108.
Recall that is exclusively concealed within log log T terms. By assigning = 106, we have reached the following conclusion that
l + log T
Regret(T) S OOV log(
(1 7)2
which finishes our proof.
F Omitted Proof in Section
F.1 Useful Facts for Proving Theorem 4.1
First, we introduce some auxiliary lemmas on Kullback-Leibhn (KL) divergence.
Lemma F.1. For two independent normal distributions p (f),,, and q N(22, the KL divergence between them is
KL(plg) of + (M - (1)= + log( 2 - 2
20
Proof. Recall that L fr p(x) log( dr. It leads the result with the expression of normal distribution and some calculations.
p(m) q(x))
Lemma F2 (168). For two probability distributions p. q over space (D,F), it holds that for any AEF
p(A) + +((9))
-L(pllo)
F.2 Proof Theorem 4.1
Proof. 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 Ps- Qs and the family of the demand curve parameterized by is (P.D 20 + 5e (1 e)QD + e where & ~N(0, (2
32

---

The system is depicted completely by (ar, Pa), where Qa = P. -0- ag. Recall that dr depends on
history up 1, namely, 1 = (01, ci ci.... .... at P c(t-1)) From Lemma E.1 we know that
Q 20+-c-atc..2
2tc 20+5e+ (esSeel+++epee (1te)ate.D 2-
P
Then, we know that P. ~ NN( 20+5e+(L+e))
1) due to the definition of e.p. Moreover, the ex-ante
2tc
optimal service fee is a" 20+
We now consider the situation when e = 0 and 6 = 7 and we use Pa to denote associated probability measure. With the help of Lemma ET it holds that
210 a)2 (L E. (F (-lo)) a] Ea! 2(2 + +)²
where we use the law of iterated expectations.
During the whole T round, we calculate the number of rounds with |10 - -ae 5e denoted by To- With slight abuse of notation, we use [To] to denote the corresponding index set. Let's consider achieved regret with To case by case.
2. it holds that one-round suboptimlality for e 0 is at least On the one hand, when To 2 T.
SubOptar (a:) (10-a)² when E [To]. Then, we have
Regret, (T) + Regret, (T) 2 Regret (T))
Σ
SubOpto
rE(T)]
25c
To
2
T 25
2 2
2 ((VT).
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 belongs to [To]. we have that [10 al 2 de while the fourth inequality holds due to the assumption of To.
On the other hand, when To T. there exists more than T rounds such that |10 - al S 5e. In 25c4
these rounds, denoted by [T Toj. it holds that K KL < inequality holds with need to consider the distribution of a because use union bound over all
2(2+c) S 25c
as S 1. The first
a. Then, the total K L. among these T To rounds is no larger than (T - To) e = 1/4 in leverage of properties of KL divergence.
25c
18 5 0(1) as
We define an event A that in more than _ rounds, a, rounds that a+ 40+ Therefore, holds that
4045e 4.c Therefore, A contains at least -
E 12 T1 [Regret, (T) + Regret_((T) 2 E +1126
(ubOptor(a)) + SubOpt
[E[T-
T
25c²
T T,T T 25c²
Po(A To <
+ +PAAA
< 2 4 16(2 +
2 4 32
25
192 (Po(A To <
+ P. To < )
25VT1
28
192 2
D(VT).
33

---

The first inequality holds due to the positivity of SubOpt(-) while the second inequality holds because the optimal service fee is 20+ and one-round loss is (e=(20+6e)/2) The third inequality holds due to e S 1 while the fourth inequality holds due to Lemma F.2
2+c
Therefore, holds that by combining both two cases
max (Eegrett (T), ERegret (T)}
[RRerett (7) ERegret, (T))
Regret (T) + Regret, (T)
(110s Regret + Regret, (T),
min
IT22 1
25
25
21 2 min!
e
25
4
384
((((T))
due 6 1/14 Therefore, for any algorithm against e = and 6 = T-1/1 at least one regret is no smaller than (T) which ends the proof.
There two key points when constructing such a hard-to- learn instance. When c 0, the optimal service fee is 10 and the expected equilibrium is (Pe Q*) = (15,5) 5). Then, we choose a special family of demand curves which are all through (Pe, @6) (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 e. However, the platform sets service fee deviated from 10, it will suffer high loss in the case when tradeoff leading to ((vT)) regret loss bound. However, when o3 > O, even if the platform sets optimal service fee for e = the noise Es plays the role 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.
= 0, ending with large total regret. This introduces an internal exploration-exploiatiii
Secondly, from technical perspective, we adaptively adjust the noise variance in the demand. For the tuned hyperparameter 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 c, entailing smaller KL divergence between different choices of demand. To sum up, these two crucial aspects make up this delicate and non-trivial example.
- and baseline parameter e 0, we shrink o from (2)
F.3 A Weaker Version of Theorem 4.2
Note that there a gap between the proposed upper bounds and corresponding lower bounds when of S O( w indicating essential hardness in this interval. Therefore, first give the following lemma which 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 complete information-theorett proof of Theorem 4.2 in Appendix F4
Algorithm Oracle-Variant Algorithm.
Input: T. T.
Initialization: Ho < 0 for t = 1 to T do
Generate noise: Est (0,
Generate virtual supply curve: Pk = on + aiQ + esc.
Call Oracle(,,)) )) âe + Oracle (H Ps.).
Select action: 0r = 4, + ESt.
Observe equilibrium:
(Pr, Qi) from Equation [I Update history: H, + H Est).
end for
34

---

Lemma F.3. It's impossible to find an algorithm such that there exists some o3g 2 of / and the corresponding expectation of regret belongs to ol T),, numely, ERegret( S dvT)).
Proof. We have proof by contradiction to demonstrate this lemma. We assume that when the supply randomness is d'g E of ) there exists an algorithm denoted by Oracle whose expected regret
belongs to ol (VT).. We use Hy to represent history until round t, namely, H, {ar, Pr, @+ Therefore, Oracle(;;)) is a mapping from H4-11 x Pst to R. Now, we are going to show that existing such Oracle, we can find variant called Oracle-Variane which achieves of (T)) without supply randommess, contradicting Theorem 4.1 We assume Y 0 which is enough to construct counterexample. We present the detail of Oracle-Variant in Algorithm 6 The input is the number of rounds T and the supply randomness og o( ( associated with Oracle.
We use Oe to denote the optimal service fee when there exists est ~ NN0, oi)) and oz to denote the one without randomness. Considering the following counterfactual case, if we adopt d when there exists (st. the equilibrium price and quantity will be
(Pr,Q Qi) = 0gg a4 + EDr est a1 - 0n - B an - -BESst
01 - 31
01 B1
according Lemma E.9 Fortunately, choosing a; dg + cst leads the same equilibrium price and quantity without randomness, that to say, (Pt, Qi) = (Pr Qi).
Since we use Oracle, the regret when baseline is dr is oov Therefore, we know that
a क. क. o(vT).
according the proof of Theorem E.1 Now, let's give decomposition of (at az)². S. It holds that (a, - a²)² 2 O((a- a))2) + O - ā, ",)))) + O(aai ā. a²²)²),
according to simple algebra. For the first term, we know that
E
O((a,- -
Σ
[=1
from the implementation of Algorithm For the last term, we know that
6
For the second term, holds that
T
E
O((ā
1=1
T E O((a; - - 0le,,) 5 O(To)).
because laž a, "1 Therefore, we know that without supply randomness, the expected regret Algorithm 6 satisfying
ESt
according Lemma E.1
RTg S o(VT) + O(To3) S o(VT). The last inequality holds due to o3 S of ) However, from Theorem 4.1 we know that (T) 2 ((VT). It then causes contradiction. We subsequently conclude that the ex- istence of Oracle untenable, which ends the proof.
F.4 Proof of Theorem 4.2
Proof. Let 3 (Bo, 31) and EDi ~ NO of) with op = (a1 - 31)or for some o > 0. To express concisely, subseript 3 and superscript to denote parameter and policy, respectively. We know that
aj (B) = 3u 0gp ESt
2
35

---

Also, when the decision maker sets any dg, we observe
Oi 3 EDi 8q 000 ESt
a1 31
Note that the only unknown randomness comes from EDI since est is always observable. Meanwhile, upon deciding a, and observing Qi and est. the price from both the demand and supply side can be uniquely decided. Therefore, the log- le-lliklihhodd prior to time t can be calculated as:
(-1
Σ
1 20
Qi
3o a; 00 eSi
2
+ +C,
a1 - 31
where C' is a constant only dependent on {az, Qi 1=11 k== matrix prior to time t can be calculated as
and not dependent on B.. The fisher information
80 80-a; -00
(B)
101-8
[0r 111--1122
0²
-o-0--00- EsE
(9a-0z- 00000000000 -8
(01-8.)²
(01- -11)
Let be an absolutely continuous density θ, 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 that
(Ex ((8)00(()))00)
Ex [3 [(a: - az (8)) 2
(3)
Ex [C(())F + F(A)
Let C(3) ((6u a2)/2 1]. Then we have
C(3)(Oa) (8))80)) [(80 a2)/2
11[1/2 0] (Bo an) 221)
and
80= 000
= 0² (()C01
Ey
(go
(st)
3112
2
i=1
Σ E3
f-1
8
00
ESi
ESi
27
0²(a1 - -3132
2
2
[=1
1-1
0
Σ
[
aa (B)) + 03)
Plugging the inequalities above into Inequality such that
we know that there exists positive constant
2c
Ex Eg (a-- ot [ (B))
>
1 -E= E
E [(a:
(3))2]] + (t 1)03
From now on, for notation simplicity, we denote [t: the formula above from É to T, we know that
ΣT= Ex
E3 (a: - at (3)))] Summing
T-1
2c
Σ
(4)
1+ +
+
i=t-1
Then supy Regretz ((Al.T))) We show the lower bound in two cases.
(a). T 1 + 1/03.
Then from Inequality (4) have
T
2c
2c(T - 1)
CT AUT
A
[I. +
i
1
11T +
/T
+2/T
36

---

Therefore,
(A + vT)² 2 (1+c)T,
which indicates that there exists constant cu = /1 - > 0 such that A A1:71 cOVT.
(b). 7>1++/00 1/03. Let K be the smallest positive integer such that 2 2 1 + 1/03. Then 2 -1
1+ 1/05. which indicate that
K+ - 1
l0gg(1 + + +2 6(1 log (1/as))
From (a) we know that for t 2", we have
K
A 1 2 0o + 1/0 2 2 1 log (1/0s) oz
03
where e is small positive constant irrelevant with K and øs such that ei (2 601) S Now we use induction. Suppose we have
A 1 1 log, + (1/os)
C1
k
(5)
o²
for some k: 2 K. From Inequality we have
A 112+1
(2 2)c
c
1 + +oz -2 1))
A112++1
1
2 k +
200
20
2
2
Note that we have utilized the following inequality:
2 2- # < 0
0 =03/2.
5
1
0
20
As result,
A1124+11
C1
+ log
(1/os)
o3
A 2
+ 20
If A [1,24+1]
k+1 then
1+log (1/08)
03
1
+ 20
k+1
20
2
1+ Hog (1/ag)
2
K+1 + 20² 1+log (1/or)
2 og
2 (2 602)03
2 C
0
This causes contradiction. Therefore, for any k K, Inequality T> 1 1/05. If < 2k then
holds. Now select any
A 1.7 2 c / +1 +1/0 2 1 log, (1/05)
C1
C1
log
+ log (1/as)
oz
IfT 2 2 choose k [log, T]. then
A [177] > [1.2*]
c
k
c
log T
>
1 log, (1/os) o
7
1 + log, (1/os)
o3
37

---

F,5 Proof of Theorem 4.3
Proof. Note that the buyer's strategic behavior only causes extra O log 0(log dg
in Theorem 3.2 and
Oloo 7) in Theorem 3.1 Since terms from estimation errors dominate them, we without loss of generality assume that the buyer is myopic i.c., ? = for simplicity without weakening our results.
From traditional results of hypothesis test [22], we know we need n @((²)=)) samples to distinguish Ho and HH] where 2a. a and E are the z-score, the population standard deviation and the acceptable margin of error, respectively. Here, we know that a ~ ( since Var(e ~ ((rr))
Besides, we set a ~ ( and then za ~ @(vlog due to Lemmas D.1 and D.2 The largest tolerance of enror is E (-7) Therefore, by setting To ~ O T' with some accurately designed constants, we can distinguish Hg and IiI, with probability at least 1 - (+)).
Then, in the case of HH,, will add some human- noise referring to Algorithm | Then, the randomness of a, comes from two parts. One is from original Est- The other one comes from artificially added noise. Therefore, the variance of is no smaller than the one in the proof of Theorem and 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, and ay will lead an ((VT) regret. The second part comes from the fact that the probability that some inequalities don't tt hold is at most (++). The last part comes from the first To rounds. Therefore, holds that
+ + O(To) S Ö(VT).
ERegret x ((VT) + 0
Recall that will suffer most extra Olog T) from strategic buyer which is indeed subdominant term. It covers cases when d3 $ of )
In the case of H it will reduce Theorem directly. The regret consists of three parts as well. The first part is O ( inherited from Theorem E. The second term comes from the ( probability of some incqualities being violated. The last term is from the first To rounds, yielding
ERegret S Õ
+ T + 0 O(T)) Ō
regret facing far-sighted buyer. This contains all situations when o3 2 w( (.) ). To be specifie, from the proof of Theorems 3.1 and 3.2
Note that will suffer an extra O log T o'
know
hide Ologg T) for IHI, but only O(log T) for Hlg-
Finally, when r² O } the policy we use might be mixture of the one under Hig and the one under Hj. Luckily, both of them will lead to an at most (vTT) expected regret.
To sum up, we know that the expected regret of Algorithm 3 satisfies
Ö(VT) when oz $
0
(ERegret(T) S
(8()) when
2
Let's now turn to the tightness of lower bounds. From Theorems 4.1
and 4.2
we have that
((VT) D( 2(
when o3 when o
ERegret(T) Z
when 03 2 22
Therefore, conclude that regret lower bounds tight and Algorithm of constants and logarithmic terms.
3 is optimal regardless
Moreover, we instantly obtain the phase transition of regret and it finishes our proof.
F.6 A Lower Bound When 7 =
We close off this section by giving an easy reduction to the Q(T) lower bound in Amin et al. 2 when the buyer is patient, i.e., equipped with discount rate 1. determine the optimal dependency on is beyond the scope of the current work and we leave it as an interesting future direction.
38

---

For each Sg. 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 value i.e., a" here, an S?(T) regret is inevitable for any algorithm when the buyer is patient, namely, ? Through the bijection between Bg and a", we know there exists some 90 that makes this pricing problem unlearnable.
G Details of Numerical Experiments
We choose parameters 7 = 0, ag = 1, a1 = 1. 31 = -1 and ED ~ NOO, 1) in both experiments.
In Section 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 :c)(;,). We actually update our pricing policy at the start of each stage. Therefore, the noise we add has a variance that starts from and decreases according to the inverse square root law.
For the second experiment, there are some hyper- hhper-paramenn parameters when implementing Algorithm 3 First, we set To 10 1ogg I' therein. Secondly, when we do the hypothesis test, we sample mean of èg is smaller than 10 and HHI otherwise. Among the 1000 choices of og, there are vT
Ho the
about 100 cases where HI Hl,, nearly to say, when o3 I 0.1. These choices hyper-parameters not essential and not well-tuned though enough for experiments. When using LOWESS set the hyperparameter "fraction" as 0.15. 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 z 9.21 so regret fluctuating between 300 and 600 around o² = 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 tightness our lower bounds and the existence of phase transition in Theorem 4.3 in concrete manner.
39

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The main claims made in the abstract and introduction accurately reflect the paper's 's contributions and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
The paper discusses the limitations of the work performed by the authors.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
40

---

The paper provides the full set of assumptions and complete (and correct) proof for each theoretical result.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: The paper fully discloses all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and conclusions of the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
41

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
The paper provides open access the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material.
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cc
aublic//uidees/Coeeuubtitt wtt.eeeeuuuiiiiioooooooooooo for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ wwtp:/cccpblccggiuiieeeee
www.sssoiccgyyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, 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 the core the paper to level 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, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
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 emoo bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
42

---

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 the standard error of the mean.
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 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 range (e.g. negative emror rates).
If error bars 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.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: The paper provides sufficient information 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 include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums 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).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.. http:////weaaappp..ccppppb//eaea inn
Answer: [Yes]
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 reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. 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 socictal impacts and negative societal impacts of the work performed.
Guidelines:
43

---

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 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 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 unintentional) misuse of the technology.
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).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
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 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 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 challenging, and many papers do not require this, but we encourage authors to take this into account and make 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 used and, 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.
44

---

If assets are released, the license, copyright information, and terms of use in the thcode. has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssi
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.
this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. 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/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent 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.
14. Crowdsoureing 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 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 the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
45

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere 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.
46


Reviews:
[{"review_id": "bsQJTngYX4", "reviewer": "Reviewer_pz8n", "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.", "questions": "see weakness.", "limitations": "NA.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "+ The motivation and challenge of solving demand prediction and optimizing long-term revenue is clear.\n+ Robustness consideration: the algorithm's design incorporates robustness by not requiring precise knowledge of the buyer's discount rate, enhancing its applicability across varying real-world scenarios.", "weaknesses": "-. Declaration: line 100, confusing definition of price P and demand Q.\n-. Limitation: lack of explanation of assumption 1, regarding the linearity with Gaussian noise.\n-. 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.\n-. The trade-offs of data amount and randomness are straightforward in Section 3.1.\n-. Lack of motivation and explanation of relaxing the two assumptions in Section 3.2.\n-. Lack of detailed definition of T_0 in Algorithm 3. The intuition of using hypothesis testing is quite straightforward.\n-. In Section 5, to show the regret order, it’s better to show a log-like figure which indicates the linearity relation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your remarks. The followings are our responses to your questions.\n\nRe Weakness 1: $P_{St}$ is the amount received by the seller at time $t$, and $P_{Dt}$ is the amount paid by the buyer. The gap between them is the service fee, which is $a_t$, and $Q$ is the transaction quantity. Then, $P_{St}(Q)$ and $P_{Dt}(Q)$ represent the supply curve and demand curve respectively.\n\nRe Weakness 2: We are sorry for the confusion and misunderstanding. In Lines 165-177, we introduced the motivation and extension of Assumption 1. Our results hold for general subGaussian noise, and we use Gaussian noise for ease of illustration. We assume linear models because they perform well locally and have strong robustness.\n\nRe Weakness 3: We use the service fee, i.e., action, as an instrumental variable, which is emphasized in the title. Since they are neither i.i.d. nor external, we used a martingale-based approach. Intuitively, at time $t$, $a_t$ only depends on the demand from times 1 to $t-1$; so given those, $a_t$ is independent of the demand at time $t$. We proved that in this case, the service fee can be used as an approximately valid IV.\n\nRe Weakness 4: The challenge in our problem lies in how to add randomness. We carefully choose the amount of data used to make $a_t$ an approximately valid IV. Additionally, we add noise with carefully chosen magnitude to balance between exploration and exploitation. \n\nRe Weakness 5: For Assumption 2.1, we can use the generalized method of moments (GMM), which is standard in econometrics, to handle non-linearity. For Assumption 3.2, we discuss other possible choices in Appendix B. Please refer to the discussion in lines 154-177. We use these assumptions to highlight our technical innovations while avoiding heavy notations, including (1) how to use endogenous actions as IVs, (2) how to deal with buyers' strategic behavior, and (3) how to explore the unknown environment through adaptive randomness injection.\n\nRe Weakness 6: $T_0$ is a constant multiple of $\\log T$. The constant does not affect the order of $T$ in the regret bound, and the concrete value is usually determined empirically, such as through cross-validation with past data. In our experimental design, as referenced in Line 1118, we chose $T_0 = 10 \\log_2 T$.\n\nRe Weakness 7: Although the idea of hypothesis testing is straightforward, our innovation lies in recognizing the phase transition and finding the optimal algorithm design through injecting randomness adaptively. This optimal algorithm is further achieved through hypothesis testing.\n\nRe Weakness 8: Thanks for your suggestion. From the experimental results, when $\\sigma_S^2=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. \nWhen $\\sigma_S^2=0$, $\\log(\\text{Regret})$ =   6.43, 6.75, 6.95, 7.10, 7.17 when $\\log T$ = 9.90,10.60,11.00,11.29,11.51. The estimated slope by OLS is 0.47, testifying our square root $T$ regret.\nWe will include this in the next version.\n\nThank you again for your comments. We hope you find the response satisfactory. Please let us know if you have further questions.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "0QIXJmo4cl", "reviewer": "Reviewer_Z4TZ", "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.\nThe 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.", "questions": "Could the authors provide more examples or case studies to illustrate how their algorithms perform in real-world scenarios?\nHow do the algorithms perform under different levels of noise in the supply curve, and what is their robustness to model misspecification?\nThe 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": "I did not find any limitations of the paper.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1 The paper is technically rigorous, providing a clear mathematical framework and novel algorithmic solutions for a complex problem in platform economics.\n2 The authors demonstrate an innovative use of non-i.i.d. actions as instrumental variables and the proposed algorithms are shown to have optimal regret bounds, which is a strong technical result.\n3 The paper is well-structured, with a clear explanation of the problem, related work, model assumptions, and a detailed description of the algorithms and their theoretical guarantees.", "weaknesses": "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.\n\n\n2 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.\n\n3 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your kind remarks and questions. The followings are our responses to your questions.\n\nRe Weakness 1: Thank you for your suggestion. If there is a suitable opportunity, we will consider conducting experiments on real-world data.\n\nRe Weakness 2: We are sorry for the confusion and misunderstanding. We discussed in Lines 165-177 why we use a linear model (based on market observations and the robustness of the linear model [15]) and how to go beyond it (using GMM and RKHS). We assumed a linear model to avoid heavy notations while expressing our main points: (1) how to use endogenous actions as IVs, (2) how to deal with buyers' strategic behavior, and (3) how to explore the unknown environment through adaptive randomness injection.\n\nRe Weakness 3 and Question 3: Recall that our goal is to maximize the total revenue. The revelation principle [63] tells us that there exists a DSIC mechanism that can achieve the optimal revenue. Therefore, we only need to consider the policy class satisfying DSIC. If we approach the optimal DSIC mechanism, then we can approach any optimal mechanism no matter it is DSIC or not. In other words, we identify there exists an optimal point in a smaller policy space and then approximate it within this smaller space. This not only simplifies the analysis but also makes it easier to apply in real-world scenarios (buyers don't have to struggle with searching for a good strategy).\n\nRe Question 1: Thanks for your question. One application scenario could be that some online platforms, e.g., Amazon, sells a large number of products daily, and takes service fees between sellers and buyers. At the same time, we notice that on ride-hailing platforms like Uber, prices in the app frequently fluctuate due to frequent changes in supply. While the booking fee doesn't change too often, promotions (which can be regarded as a reduction on the service fee) can change quickly and be highly personalized. Therefore, our model can also be applied to dynamic promotion pushes. This is another application scenario for our model.\n\nRe Question 2: We demonstrate the relationship between regret and the noise level in the supply curve in Figure 5. We also add another group of experiments (see pdf) showing their negative correlation. Additionally, a higher noise level in demand leads to greater regret, as it results in larger estimation errors for the parameters. Please refer to Line 688 for this impact on $\\hat\\beta_1$. [56] informs us that model misspecification causes additional unavoidable errors, while [15] explains that linear models are not so affected by misspecification. This is one of the reasons why we assume linearity.\n\nThank you again for your comments. We hope you find the response satisfactory. Please let us know if you have further questions.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nEkaqK915G", "reviewer": "Reviewer_EYLY", "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.", "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?\n1. Can the authors explain a bit more on the revelation principle and in particular how the buyer maximizes surplus?\n1. 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?\n1. 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?\n1. 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": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The paper is technically strong with several results and the presentation is clear: the study of \"noise helps learning\" and phase transition is  interesting\n1. The setting of supply equilibrium is nonstandard in dynamic pricing and less explored", "weaknesses": "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)\n1. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed remarks and questions. The followings are our responses to your questions.\n\nRe Weakness 1 and Question 1: One application scenario could be that some online platforms, e.g., Amazon, sells a large number of products daily, and takes service fees between sellers and buyers. \nAt the same time, we notice that on ride-hailing platforms like Uber, prices in the app frequently fluctuate due to frequent changes in supply. 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. This is another application scenario for our model.\n\nRe Weakness 2: We agree that this is an important and challenging future direction. We would like to note that although our results on $\\gamma$ may not be tight, we have improved upon previous results in the literature. Please refer to Lines 245-252. Compared to $O(1/(1-\\gamma)^2)$ regret in another similar pricing problem [37], we improved it to $O(1/(1-\\gamma))$ in Thm 3.2. Additionally, our algorithm does not require prior knowledge about $\\gamma$.\n\nRe Question 2: The revelation principle [63] tells us that for any mechanism that maximizes revenue, there exists an incentive-compatible (IC) mechanism that can achieve the same revenue. IC means that buyers can purchase according to their true demand, and the mechanism's incentives will guarantee them higher utility. Therefore, we study how to motivate and approximate within the IC mechanism framework, narrowing down the policy space and making it easier to find an approximately optimal mechanism. This not only simplifies the analysis but also makes it easier to apply in real-world scenarios (buyers don't need to struggle with searching for a good strategy).\n\nRe Question 3: $a_t$ is not i.i.d. because it depends on the supply from $1$ to $t$ and the demand from $1$ to $t-1$. Therefore, $a_m$ and $a_n$ are correlated, since they, for example, both depend on the supply at $t=1$. However, since the platform announces $a_t$ before observing the equilibrium at time $t$, $a_t$ and $P_{Dt}$ are conditionally independent given $P_{S1}, ..., P_{St}, P_{D1}, ..., P_{D(t-1)}$. Therefore, we model it as a martingale for parameter estimation. Thank you for your comment; we will include this discussion in the next version.\n\nRe Question 4: In our experiments, we chose $T_0 = 10\\log_2 T$. We also used $T_0$ data points to empirically estimate $\\sigma_S^2$. If the estimated value is greater than $10/\\sqrt{T}$, we consider it to belong to $\\mathbb{H}_1$; otherwise, we consider it to belong to $\\mathbb{H}_0$. The parameter 10 does not affect the order of the regret bound in terms of $T$, and the concrete value is usually determined empirically, such as through cross-validation with past data. We hope this helps with your understanding.\n\nRe Question 5: Thank you for your suggestion. We increased the number of trajectories to 100 and observed that the bandwidth significantly decreased. Please refer to Figure 1 in the newly added pdf. Additionally, we tested the regret under different $\\sigma_S^2$ values: 0.5, 1, 1.5, 2. Please refer to Figures 2-4 in the newly added pdf. We found that the larger the $\\sigma_S^2$, the smaller the regret, which confirms our theoretical results.\n\nThank you again for your comments. We hope you find the response satisfactory. Please let us know if you have further questions.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hTip5n6D75", "reviewer": "Reviewer_pXqU", "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.", "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": "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.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The problem is very interesting and the modelling is very realistic than hypothetical.\nTheoretical Analysis.", "weaknesses": "Some proofs could had been included in the main paper as theoretical contribution is the strength of the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments and encouragement. The followings are our responses to your questions.\n\nRe Weaknesses: Thank you for your suggestion. In the camera-ready version, we will include some core proofs on the additional page of the main body.\n\nRe Questions: $P_{St}$ represents the payment received by the seller, reflecting the supply curve, while $P_{Dt}$ represents the price paid by the buyer, reflecting the demand curve. Since the platform charges a service fee $a_t$, there is a gap between these two prices at equilibrium. In other words, at the equilibrium point where we use $Q_t^e$ to denote equilibrium quantity, we have $P_{Dt}(Q_t^e) = P_{St}(Q_t^e) + a_t$. However, buyers might not purchase according to their true demand, i.e., their willingness to pay. For example, a buyer may be able to afford Uber's price but choose to wait for some time until the price drops. Consequently, Uber may perceive the buyer's purchasing power as lower and reduce prices in future personalized pricing, thereby giving the buyer higher long-term utility. As a result, we use $P_{Dt}'$ to represent the buyer's apparent demand, based on which they choose the quantity to purchase, and it might be different from $P_{Dt}$ reflecting strategic behaviors. Therefore, we finally have $P_{Dt}'(Q_t^e) = P_{St}(Q_t^e) + a_t$.\n\nRe Limitations: Thank you for your comment. In Appendix B, we discuss how to generalize the 100% civilian-run seller assumption to $\\alpha$ civilian-run. We chose $\\alpha=100$% to concisely express our main contributions, namely (1) how to use endogenous actions as IVs, (2) how to deal with buyers' strategic behavior, and (3) how to explore the unknown environment through adaptive randomness injection.\n\nThank you again for your comments. We hope you find the response satisfactory. Please let us know if you have further questions.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
Thank you all for your meaningful reviews! We add a new experiment increasing the number of trajectories to 100 with various noise levels in the supply. Please see the added pdf for detailed results.

Meta-review: 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.
Decision: Accept (poster)