The Limits of Optimal Pricing in the Dark
Authors: Quinlan Dawkins
Minbiao Han
Haifeng Xu
Venue: NeurIPS 2021 Poster (2021)
Keywords: Strategic Learning
Pricing
Stackelberg Games

Abstract: A ubiquitous learning problem in today’s digital market is, during repeated interactions between a seller and a buyer, how a seller can gradually learn optimal pricing decisions based on the buyer’s past purchase responses. A fundamental challenge of learning in such a strategic setup is that the buyer will naturally have incentives to manipulate his responses in order to induce more favorable learning outcomes for him. To understand the limits of the seller’s learning when facing such a strategic and possibly manipulative buyer, we study a natural yet powerful buyer manipulation strategy. That is, before the pricing game starts, the buyer simply commits to “imitate” a different value function by pretending to always react optimally according to this imitative value function. 

We fully characterize the optimal imitative value function that the buyer should imitate as well as the resultant seller revenue and buyer surplus under this optimal buyer manipulation. Our characterizations reveal many useful insights about what happens at equilibrium. For example, a seller with concave production cost will obtain essentially 0 revenue at equilibrium whereas the revenue for a seller with convex production cost is the Bregman divergence of her cost function between no production and certain production. Finally, and importantly, we show that a more powerful class of pricing schemes does not necessarily increase, in fact, may be harmful to, the seller’s revenue. Our results not only lead to an effective prescriptive way for buyers to manipulate learning algorithms but also shed lights on the limits of what a seller can really achieve when pricing in the dark.

fundamental The Limits of Optimal Pricing in the Dark
Quinlan Dawkins
Minbiao Han Department Computer Science
Department of Computer Science University of Virginia wedd4g@virrgim edu
University of Virginia mh2ye@virgin rigini edu
Haifeng Xu
Department of Computer Science
University of Virginia hx4ad@virginia edu
Abstract
A ubiquitous learning problem in today's digital market is, during repeated inter- actions between a seller and buyer, how seller can gradually learn optimal pricing decisions based on the buyer's past purchase responses. challenge of learning in such strategic setup is that the buyer will naturally have incentives to manipulate his responses order to induce more favorable learning outcomes for him. To understand the limits of the seller's learning when facing such strategic and possibly manipulative buyer, we study a natural yet powerful buyer manipulation strategy. That is, before the pricing game starts, the buyer simply commits to "imitate" a diffcrent value function by pretending to always react optimally according to this imitative value function.
We fully characterize the optimal imitative value function that the buyer should imitate as well as the resultant seller revenue and buyer surplus under this optimal buyer manipulation. Our characterizations reveal many useful insights about what happens at equilibrium. For example, a seller with concave production cost will obtain essentially revenue equilibrium whereas the revenue for seller with convex production cost is the Bregman divergence of her cost function between no production and certain production. Finally, and importantly, we show that a more powerful class of pricing schemes does not necessarily increase, in fact, may be harmful to, the seller's ' revenue. Our results not only lead to an effective prescriptive way for buyers to manipulate learning algorithms but also shed lights on the limits of what a seller can really achieve when pricing in the dark.
Introduction
Pricing a basic question in microeconomics (24 as well as a ubiquitous problem in today's digital markets [16). In its textbook style setup, there are two agents: a buyer (he) and seller (she). The seller produces d types of divisible goods for sale and has production cost c(x) for producing bundle RR of the d goods. Using standard linear pricing scheme with unit price p; for goods i [d]. the seller charges the buyer p when he purchases bundle E Rd under price vector p Rd Naturally, the buyer's optimal bundle for purchase depends on his value function v(x) about the products. We assume that, given price vector p. the rational buyer will always pick the optimal bundle that maximizes his quasilinear utility [u(æ)) æ p). The key question of interest is how the seller can compute the revenue- maximmiimaiiizznngggg optimal prices assuming rational buyer purchase behaviors.
"This work is supported by Google Faculty Research Award and an NSF grant
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

The above basic problem can be easily solved if the seller has access to the buyer's 's value function v(z)). However, in practice, this value function usually private and unknown to the seller. To address this challenge, there has been rich line of recent research which looks to design the optimal pricing scheme against an unknown buyer. Some of these work have adopted learning-basee approaches that aim to compute the profit maximizing price by interacting with the buyer and gleaning information about the buyer's utility function B3 32). These are motivated by the wide spread of e-commerce today where the seller can repeatedly interact with the same buyer or buyers from the same population with similar preferences. For example, in online advertising, ad exchange platforms learn to price advertisers from past behaviors; in online retailing, retailers learn to price customers from their past purchase history; and in crowdsourcing, platforms learn to reward workers' efforts. Another line of works look to design dynamic pricing mechanisms that dynamically adjusts the price based on the observed past buyer purchase behaviors with the objective of maximizing the aggregated total
revenue 4 26 38
key challenge of pricing against such unknown buyers, regardless through learning or dynamic pricing, is that the buyer may manipulate his responses in order to mislead the seller's algorithm and induce more favorable outcomes for themselves. This is a fundamental issue when learning from strategic data sources, and is particularly relevant in this pricing setup due to the strategic nature of the problem. In this case, the buyer controls the information content to the seller, therefore he naturally has incentives to utilize this advantage to gain more payoff by strategically misleading the seller's s algorithms. Indeed, as observed in previous studies, online advertisers may strategically respond to an ad exchange platform's 's prices in order to induce lower future price [22; Consumers strategically time their purchases in order to obtain lower prices at online retailing platforms 23
To understand the limits of the seller's 's optimal pricing against such strategic and possibly ma- nipulative buyer, we put forward a natural model which augments the above basic pricing problem with only one additional step - i.e., we assume that the game starts with the buyer committing to different value functions, coined the imitative value function, after which the seller will compute the optimal pricing scheme against this imitative buyer value function. The buyer's 's commitment to an imitative value function captures a simple yet powerful buyer manipulation strategy that can be used against any seller learning algorithms to this imitative value function during the entire interaction process. Intuitively, the motivation of such commitment assumption comes directly from the fact that the seller has information about the buyer and has to optimize pricing "in the dark". Consequently, if the buyer consistently behaves according some different imitative value function, the seller is not able to distinguish this buyer from another buyer who truly has the value function (see more justifications of the commitment assumption in Section B). Moreover, such an imitation strategy is also easy execute in practice by the buyer regardless whether the seller is learning from him or is adopting dynamic pricing schemes. In fact, the buyer could even just report his imitative value function to the seller directly at the beginning of any interaction. In this situation, no learning or dynamic pricing will be needed as the buyer will indeed always behave according to the imitative value function. Therefore. all the seller can do is to directly apply the optimal pricing scheme for the buyer's 's imitative value function.
that is, the buyer simply behaves consistently according
We remark that such imitation- based manipulation strategy has attracted much interest in recent works, with similar motivations as us - i.e., trying to understand how to manipulate learning algorithm or conversely, how design strategy-aware learning algorithms to mitigate such manipulation. However, most of these works have focused on the general Stackelberg game model [19 10 as well as the
Stackelberg security games [8 30 29). Our optimal pricing problem is also Stackelberg model and thus a natural fit for the study. The crucial difference between our work and previous studies that both agents in our model have continuous utility functions whereas all these previous works [19 18, 30 10) have discrete agent utility functions. Therefore, our model leads to functional analysis and optimization problem, which is more involved. Fortunately, we show that the optimal functional solution can still be characterized by leveraging the structure of the pricing problem.
1.1 Our Results and Implications
Given the effectiveness and easy applicability of the buyer's 's imitative strategy described above, this paper studies what the optimal buyer imitative value function is and how would affect buyer's surplus and the seller's revenue. Our main result provides a full characterization about the optimal buyer imitative value function. We show that the optimal buyer imitative value function u² features specific bundle of products x" that is most desirable to the buyer. Interestingly, it turns out
2

---

that u" is a Leontief-type piece-wise linear concave value function 2 such that the buyer would only proportionally value a fraction of the desired bundle x" and nothing else. Moreover, we also characterize the seller revenue and buyer surplus at equilibrium as well as necessary and sufficient conditions under which the seller obtains strietly positive revenue.
The optimal buyer imitative value function turns out to depend crucially on the seller's production cost function. When the cost function is concave, we show that the optimal buyer imitative value function u" will "squeeze" the seller revenue essentially to O. The fortunate news for the seller, however, that finding out the u² turns out to be an NP-hard task for the buyer. In fact, we prove that it is NP-hard to find the u" that can guarantee a polynomial faction of the optimal buyer surplus. For the widely adopted convex production cost, we show that the equilibrium seller revenue is the Bregman divergence between production O and the x" bundle mentioned above. This illustrates an interesting message that convex production costs are "better" at handling buyer's 's strategic manipulations. Note that production costs are indeed more often believed to be convex since economic models typically assume that marginal costs increase as quantity goes up 35
All our characterizations so far focus on the standard linear pricing scheme. Our last result examines the possibility of using a more general class of pricing schemes address the buyer's strategic manipulation. Surprisingly, we show that for the strictly more general class of concave pricing functions (i.e., the seller is allowed to use any concave function as a pricing function), the equilibrium will remain the same as described above. Therefore, the more general pricing schemes do not necessarily help to address buyer's manipulation behavior. In fact, we show that there exist examples where strictly broader class of pricing functions leads to strictly worse seller revenue. This is because more general pricing schemes may "overfit" buyer's incentives, which renders it easier to manipulate. This illustrates an interesting phenomenon in learning from strategic data sources and shares similar spirit to overfitting in standard machine learning tasks.
1.2 Additional Related Works
Due to space limit, here we only briefly discuss the most related works while refer readers to Appendix A.I for more detailed diseussions and comparisons. Closely related to ours is recent study by Tang and Zeng [36]. They study the bidders' problem of committing to "imitate" a fake value distribution in auctions and acting consistently as if the bidder's value were from the fake distribution. This is similar in spirit to our buyer's ' commitment to an imitative value function. However, there is significant difference betweens our setting and that of (36. which leads to very different conclusions as well. Specifically, the seller in [36 auctions single indivisible item with no production costs whereas our seller sells multiple divisible items with production costs. Another recent work (2 also studies buyer's 's strategic manipulation against seller's pricing algorithms, but in a single-item multi-buyer situation. Moreover, they assume a fixed seller learning strategy (thus not adaptive to buyer's 's strategy) with separated exploration-exploiatiio learning the optimal prices or optimizing aggregated total revenue by repeatedly interacting with a single buyer [4] 5 26 27 38). These works all focus on designing learning algorithms that can learn from strategically buyer responses. Our work complements this literature by studying the limits of what learning algorithms can achieve. Moreover, the setups of these previous works are also different from us - they either assume buyer values are drawn from distributions single indivisible good with discrete agent utilities. Thus, their results are not comparable to us.
phases motivated by 4. Another very relevant literature is
5 27 or the seller sells a
There have also been studies on learning the optimal prices from truthful revealed preferences, i.c., assuming the buyer will honestly best respond to seller prices g 39
33 32]
Our works
try to understand if the assumption of truthful revealed preferences does not hold and the buyer will strategically respond to the seller's learning, what learning outcome could be expected when the buyer simply imitates a different value function that is optimally chosen. From this perspective, these works serve key motivation for the present paper. More generally, our work subscribes to the general line of research on learning from strategic data sources. Most works in this space has focused
on classification 11 20
17
25 21 12 regression problems 31 15 [3] and distinguishing
distributions
40
Our work however focuses on learning the optimal pricing scheme.
2 Preliminaries
Basic Setup of the Optimal Pricing Problem. A seller (she) would like to sell d different types of divisible goods to buyer (he). It costs her c(x) to produce E IRd bundle of these goods. Let
3

---

X C CRA denote the set of all feasible bundles that the seller can produce. We assume X is convex, closed and has positive measure. As standard assumption [2
8 6 39]. the buyer has concave value function v(xz) for any goods bundle a E X. We do not make any assumption about the seller's production cost c(r)) except that it monotone non-decreasing. For normalization, we assume 0 E X and o() c(O) = O.
33
The seller aims to find a revenue-mante meeenue-mximiizing pricing scheme assuming rational buyer behaviors. seller pricing scheme is a function p(æ) that specifies the sale price for any bundle æ. By convention, p(0) always. Let the set denote the set of all pricing functions that are allowed to use by the buyer. The majority of this paper will focus on the textbook-style linear pricing scheme [24]. A
linear pricing scheme parameterized by price vector p (to be designed) such that p(x:) = p x where i' t'th entry p; is interpreted as the unit price for goods i. Let set
PL = {p p(æ) = p a for some E R
denote the set of all linear pricing functions. In Section 6 we will also study the broader classes of concave pricing schemes where the set P consists of all monotone non-decreasing concave functions.
For any price function p E P. a rational buyer looks to purchase bundle x that maximizes his utility; That is, x² arg maX=ex [u(()) p- Ties are broken in favor of the seller The buyer's best response can thus be viewed buyer will best respond, the seller would like to pick the pricing function p" E P to maximize her revenue. Formally, p" is the solution to the following bi-level optimization:
function x: (p) of the seller's price function p(æ). Knowing that the
p- argmax pp(=" (p)) - cp))( where x' (p) = argmax [u(2) - p(x)) pEP
(1)
#eX
The optimal solution (o"))"""")) to such a bi-level optimization problem forms an equilibrium of this pricing game. More formally, this is often called the optimal Stackelherg equilibrium or strong Stackelberg equilibrium 14 333. We call p" the equilibrium pricing function and x' the equilibrium bundle. Note that this is a challenging finctiioal optimization problem since the seller picking a function E P. while not vector variable. However, when P Pt is the set of linear pricing scheme, the above problem becomes bi-level variable optimization problem since any p(æ) PL can be fully characterized by a price vector p.
Terminologies from Convex Analysis. We defer basic definitions like convex/concave functions and super//ub-gradient to Appendix [ and only mention two useful notations here: (1) the set of super/sub- gradient for concave/convex function f is denoted as O [x(x: (2) The Bregman divergence of a function f is defined as D (z. x) = f(z) f(x) V f - [z x]. D (2, x) is an important distance notion and is strictly positive for strictly convex functions when + x.
3 A Model of Pricing Against a Deceptive Buyer in the Dark (PADD)
As mentioned in related work section 1.2 the literature of algorithms to learn pricing schemes from unknown buyers is massive. This work, however, takes different perspective and seeks to understand how a buyer can strategically deceive the seller, through simple yet effective class of manipulation strategies. Our model naturally captures a buyer's strategic responses to seller's pricing algorithms when the seller has no prior knowledge about the buyer, i.e., pricing "in the dark".
Thus, we study buyer manipulation strategy that is oblivious to any pricing algorithm. That is, the buyer simply imitates a different value function u(ar) by consistently responding to any seller acts according to (z)). Consequently, whatever the seller learns will be with respect to this imitative value function u(x). Alternatively, one can think of the buyer as committing to always behave according to value function u(æ). Nevertheless, the buyer's objective is still to maximize his true utility by carefully crafting an imitative value function u(w) to commit to. Given the buye's s commitment to value function u(æ). the best pricing scheme for the seller is to use the optimal pricing function against buyer value function u(z). Similar to v(x). ). the imitative value functions u(x) is assumed to be concave and monotone non-decreasing as well. Let set C denote the set of all such functions. These resulted in the following model of Pricing Against a Deceptive buyer in the Dark (PADD):
"This is usually without loss of generality since the seller can always induce desirable tie breaking by providing negligible additional incentive to the buyer.

---

The buyer with true value function 2(z) (unknown to seller) commits to react optimally according to an imitative value function u(z) C.
The seller learns the buyer's 's imitative value function u u(x) and compute the optimal pricing function p" E P by solving bi-level Optimization Problem [ w.r.f. u(æ:).
The buyer observes the seller's pricing function p", and then follows his commitment to react optimally w.r.t. to u(x;) by purchasing bundle x arg m [u( p(z))-
We remark that such commitment fake value function is not uncommon in the literature; similar assumptions have been adopted in many recent works in, e.g., auctions (36), general Stackelberg games [19 [Q] and security games [18 30, [9]. The buyer's ability of making such a commitment fundamentally comes from the fact that the seller has no prior knowledge about the buyer's true value
function v (z)). ). i.c., has to "price in the dark". We refer curious reader to Appendix A.2 for a more detailed discussion about this assumption.
Naturally, the buyer with true value function v(x) would like to find the optimal imitative value function u² (x)) to maximizes his utility. This results in the following equilibrium definition.
Definition (Equilibrium of PADD). The equilibrium of PADD consists of the optimal imitative value function u' E C that the buyer commits to, the seller's ss optimal pricing function p" E P against u (z), and the buyer's 's response bundle x² E X. Formally, (u" ,p' x²'" with true value function v(x) to PADD if
x²) is an equilibrium for a buyer
ut = argmax((((a [x(=") - pp'(x")
where
p" = argmax(p(x*) - c(xx)),
REC
PEP
where
x² argmax [u" [x'(x) - p" (x))
øEX
The equilibrium of PADD gives rise to a challenging tri-level functional optimization problem! Note that, the dependence of the buyer's objective [=(x=)- p" p²xx") on u is indirectly through the two argmax problems afterwards. The buyer is assumed to know the production cost function c(x), which is needed to compute his optimal u². This can be easily justified in situations where the seller has been on the market for some time, therefore her production cost gradually becomes public knowledge.
4 The Equilibrium of PADD under Linear Pricing, and Implications
In this section, we characterize the equilibrium of PADD under linear pricing schemes, i.e., PL = {p: p(z) = x for some p E R4] consists of all linear pricing functions. A linear pricing function is determined by a non-negative price vector p E TRQ. To distinguish functionals from vector variables, will use Pz = {p: p E R4, } to denote the set of all possible non-negative price vectors so that each p E PL uniquely corresponds to a linear pricing function in PL. Under linear pricing, the equilibrium in Def. denoted by (u", pp, x²)) (") is characterized by Eq. 2 where P = Pi.
fistinguisfuuncionnaa
Even with linear pricing, this is still a very challenging tri-level functional optimization problem since u² is function chosen from the set of all possible functions from X to R4,, denoted by set C. first thought one might have is: why doesn't It the buyer simply imitate u" (x) = c(x). We will see later that this is not not-in in fact far from being optimal since it makes the game zero-sum and the seller will pick a price that guarantee revenue, e.g., a price of co. This leads the trade to happen at production, which is clearly not optimal for the buyer. The optimal u² should provide some incentive for the seller to produce some amount x that is in some sense the best for the buyer. We will provide two concrete examples in the next section in Figure 2]
The main result of this section is the following characterization for the equilibrium of PADD. This general characterization does not depend on any specific property about function v(x)), c(xr).
Theorem 1. In the equilibrium of PADD under linear pricing. the optimal buyer imitative value function o² w.l.o.g. be written as the following concave function parameterized by production amount x= E X and a real value pd E R.::
Ed 27
u (x) = p"
(3)
'Even for linear pricing where P = Pz. this is still functional optimization problem since the buyer's imitative value function is an arbitrary function in C.
5

---

where
c(x) c(axx
c(x") - -(ax")
x=" arg max ØEX ac(o.1) 1
[+(x))
- sup
and p¹ = sup aE(u,1) 1
(4)
Moreover, under imitative value function u" (a:),
1. For any vector X E Da in the d-dimensional simplex, the linear pricing scheme with price vector p" (21 22
Aa -.) is optimal for u²
2. In any of the above optimal linear pricing schemes, the buyer's optimal bundle response is always x² and the buyer payment will always equal p".
3. At equilibrium, the buyer surplus [u((=)) - p²) and the seller revenue is Ip" -o=="(x")
Note that the u" described by Equation B may not be the unique optimal buyer imitative value function, but is one of the optimal ones. Moreover, any optimal imitative value function will result in the same buyer surplus and seller revenue.
Interpretation of Theorem 1 Before formal proof, is worthwhile take closer look the characterization of the buyer's optimal imitative value function u² characterized by Theorem | and the special pricing problem it ultimately induces. At a high level, the buyer has desirable amount of products x" in mind, characterized by the first equation in (4). He would pretend that his value for x equals p". Moreover, the value of any production amount will linearly depend on the minimum possible coordinate-wise fraction of x" that x contains, i.c., the min
Ee 1) term in u
The p" chosen as the largest possible slope of the segment between c(x*) c(ax") among all possible E 1) (see Figure [ for illustration in one dimension about how p" is chosen based on the cost function c). This is certainly very carefully chosen value. Note that
p*(x)
c(x²) clacx) c(xxx) c(0) c(xx),
sup (0((0.1)
1
which implies non-negativity of the seller's revenue [p" - c(x²) )). In fact, the seller can achieve strictly positive revenue if and only if the above 2 is strict. Finally, the optimal buyer imitative value function u' leads to a special pricing problem for the seller. Since the buyer's value is designed such that he is only interested in purchasing some fraction r E [0, 1] of x², the seller's optimal pricing will charge rp" for the bundle = rx" and this total charge rp" can be distributed arbitrarily over the d products, e.g., by charging
Figure I: Illustration of p" Theorem
Arrp" X; p-= for product where Dí A = 1. Overall, Theorem fully characterized what the pricing problem is like the equilibrium of PADD.
x.
Remark 1. Theorem Theoremoonly provides structural characterization about the equilibrium but does not imply that the equilibrium (u", ,x)) can be computed efficiently since we still need to solve the optimization problem (4) find the optimal x² As we will show later, this turns out actually to be an Na-hard problem in general. This is an interesting situation where the result reveals useful structural insights despite its computational intractability.
Proof Sketch of Theorem 7 The proof of Theorem [ somewhat involved. We give sketch here and defer formal arguments to Appendix C The most challenging part is to find the optimal function u" E C, which is a functional optimization problem. Standard optimization analysis only apply to programs with vector variables, while not functional variables. To overcome this challenge, our proof has two major steps. First, we argue that the concave functions of the specific format as in Equation 3 would suffice to help the buyer to achieve optimality. This effectively reduce the functional
'Notably, the format of this value function appears have interesting connections to the well-known Leontief production function (2) which has the format of mins{ + ). However, leontief functions used to describe seller's production quantities as a function of quantities of different factors with no substitutability. It is an expected surprise that similar type of value function turns out be optimal for buyer's strategic manipulation.

---

optimization problem to a variable optimization problem since any function of Format can be characterized by d + variables. Second, we then analyze the variable optimization problem we get and prove characterization of its optimal solutions. The first step is the most involved part and uses significant amount of convex analysis. Such complication comes from the reasoning over the tri-level optimization problem (2). Tri-level optimization is generally highly intractable [9] indeed, as
we will show later, computing the equilibrium (u" p x²)) is NP-hard in general. Nevertheless, our analysis was able to bypass the difficulty by leveraging the special structure of the pricing problem and leads to a clean and useful characterization for the structure of the equilibrium.
A crucial intermediate step is the following characterization for slightly simpler version of the question. That is, fixing any bundle ह E X, which imitative value function u(x) will maximize the utility of the buyer with true value function v(x), subject to that the optimal buyer purchase response under u(x)) is x? Fortunately, this question indeed admits a succinct characterization as shown below.
Lemma 1. For any bundle E E X, the optimal buyer imitative value function u(xx), subject to that the resultant optimal buyer purchase response is bundle I, can without loss of generality have the following piece-wise linear concave function fnrccionformat, parameterized by real number ア E R:
Fd
π(z)
= min
(5)
Id
where p E IR is the solution to the following linear program (LP):
maximize subject to p c 2 aa.p- aaap--caat c(az)) for E [0,1]. 1].
v(z) -p
5 Explicit Characterizations for Convex and Concave Costs
In this section, we instantiate Theorem to both convex and concave cost functions, arguably the most widely adopted two classes of cost functions. In both cases, we give more explicit characterizations of the equilibrium outcome, including the buyer's optimal imitative value function as well as both agents' payoffs.
Convex production costs are widely adopted in many applications 377. When c(z) is convex and differentiable, we show the following explicit characterization about the equilibrium outcome. A graphical visualization for this theorem is depicted in the left panel of Figure 2
Theorem 2. When e is convex and differentiable, the piece-wise linear concave value function u' (æ) defined by Equation (3), with p" xx' Vc(x") and xx arg maX optimal buyer imitative value function.
[u(x:) x Ve(ær)), is an
Under u (x). the trade happens at bundle x' with payment p' x² Ve(x*). The seller revenue [x* Ve(x") c(xx)] is precisely the Bregman divergence De(0, x²) between O and x". The buyer surplus is [v(x²) x=" Vv((=)).
((K)
(x)
Beyer
u*(x)
Buyer Unilky
o(x)
uT(K)
(a): An example for convex cost: v(x) = 64/x,
(b): An example of one-dimensional concave costs: u(x) 4 c(z) = VT. Theorem implies
<(x) = x². Theorem 2 2iimlliss x¹ = 4,
p' Ve(x") 8, seller utility (0, 4) 16 and buyer utility v(x') p"
x¹ = 16, p² = <(x") = 1/1, seller utility is and buyer utility 00 p" = 4.
96.
Illustration of the equilibrium characterization: v(z) is buyer's true value function, c(x) is the seller's cost function, and u² (I) is the optimal buyer imitative value function.
Figure 2:
We now consider concave costs and prove the following characterization. A graphical visualization for the theorem is depicted in the right panel of Figure 2
7

---

Theorem 3. When c(x) is concave. the piece-wise linear concave value function u' (x) defined by
Equation 3 with p³ = c(x*) and x² arg max [o( c(x)), is an optimal buyer imitative value function.
Under u" (x)), the trade happens bundle x² with payment p" = c(="). The seller revenue will be O. The buyer extracts the maximum possible surplus maX [u(x)) c(x)].
Graphical visualizations for the above two theorems are depicted in Figure 2 Note that both examples in Figure show the sub-optimality of imitating (xx = c(x) for the buyer. To see this, note u" (x:) c(2) makes the game zero-sum. To guarantee non-negative revenue, the seller must pick price p such that the line p- z is always above u" (x). A buyer imitating u" (z) = c(x) will end up purchasing a 0 amount in both cases, and thus are sub-optimal for him.
An important conceptual message from Theorem is that when the seller production cost is concave and known to the buyer, the buyer can always come up with an imitative value function which squeeze the seller's revenue to its extreme, i.c., 0 Under the seller's optimal imitative value function, the trade will happen at his most favorable bundle amount x' and the seller pays just the cost function c(x') ) to the seller.
Theorem 3 is certainly bad news for the seller. However, it is a descriptive result and only shows it is possible for the buyer achieve maximum possible surplus. Our next result brings somewhat good news to the seller. Specifically, we show it is NP-hard for the buyer to optimize, even approximately, his optimal surplus. The hardness holds even when the production cost function c(a:) is concave, in which case the surplus is characterized by Theorem 3 This shows that even though in theory the buyer can derive large surplus from strategic manipulation, even approximately figuring out such an optimal manipulation is impossible in general, unless NP.
Theorem 4. [Intractability of Equilibrium] It is NP-hard to approximate the buyer equilibrium surplus in PADD games to be within ratio 1/d for any > O. This hardness result holds even when the production cost function c(x) is concave and the buyer's 's true value function v(x) is simply the linear function Σ T.c-
Formal proofs for both equilibrium characterizations and the hardness of approximating the buyer equilibrium surplus can be found in Appendix [D] We note that an intriguing open question is whether optimal imitative value function can be computed for convex production cost c(x). In this case, the optimal bundle x" can be explicitly expressed as x" = argmax, [u(x) x Vc(x)] for any value function u, however how derive the optimal u" remains challenging.
6
The Risk of Over-exploiting Buyer's Incentives
To counteract the buyer's strategic manipulation, one of the most natural approaches is perhaps to use richer more powerful class of pricing schemes, as opposed only using linear pricing. Such additional power of pricing will always increase the revenue when facing an honest buyer. Unfortu- nately, however, fact, the seller may suffer the risk of over-exploiting the buyer's 's incentives so that it becomes easier for the buyer to manipulate. This phenomenon is similar in spirit to the overfitting phenomenon in machine learning. That is, using a richer hypothesis class does not necessarily reduce the testing error, though it does reduce the training error. We believe that our findings in this section partially explain why simple pricing schemes like linear pricing are preferred in reality.
show that it does not necessarily help in the presence of buyer manipulation - in
We first prove that the strictly more general class of concave pricing schemes never do better for the seller than the (much) restricted class of linear pricing. In fact, surprisingly. the equilibrium of PADD under concave pricing turns out to be exactly the same the equilibrium under linear pricing. This time, our proof utilizes a crucial observation that under concave pricing, the tri-level optimization problem of PADD can be reduced to solving bi-level optimization problem (in particular, FOP (6). Recall that the proof of Theorem I also reduces the tri-level FOP to a bi-level FOP through a characterization about the price and optimal buyer bundle in Lemma 3 However, Lemma does not hold any more if the seller uses the richer class of concave pricing schemes. Therefore, the FOP (6) we obtain here is different from the core FOP we solve in the proof of Theorem I Nevertheless.
II real practice, the buyer can slightly deviate from his value function to given a small amount of incentive for the seller to strictly prefer production.
8

---

through careful convex analysis, we are able to show that the optimal solution to FOP (6 also admits an optimal solution similar structure as characterized by Theorem [
Theorem 5. The equilibrium of PADD under concave pricing is exactly the same as the equilibrium
under linear pricing as characterized by Theorem 7
We start by examining how the use concave pricing schemes may simplify FOP (2. Recall that both value functions and pricing functions are monotone non-decreasing and normalized to be O. For any concave buyer value function u E C. is easy to see that the optimal pricing function y simply equals (i.e., charging buyer exactly his imitative value) and ask the buyer to break ties in favor of the seller by picking x' = arg m [u" (æ: - c(x)] to maximize the seller's ' revenue. Consequently, the use of concave pricing simplifies FOP 2 to the following bi-level functional optimization problem:
Proof Sketch of Theorem [
" argmax((((=)) p" (xxx)), where x argmax [x) c(x)]] aEC
=EX
We fix particular bundle æ and examine what buyer value function a would maximize the buyer's utility subject to that the trade will happen at bundle æ. This results in the following optimization problem (FOP) for the buyer with functional variable u.
fontoiinnnnniiinaal functional
maximize
v ( uxx) subject to u(z)) c 2 u(x') - c(x'), for x' E X.
6
where the constraint means the seller's optimal price for value function u is u(x) and thus the buyer best response amount is indeed The remaining proof relies primarily the following lemma.
Lemma 2. The following concave function is optimal to FOP (6)
31
Ld
C 2 c(oa)
u(x) = min
1}. Fd
where p
sup cE((..1
1 1
Given this characterization, the buyer simply needs to look for the best æ. This then leads to the same characterization as in Theorem (I) since Equation ( is the same as the value function characterized in Equation 5 The proof of Lemma 2 is deferred to Appendix E.
Theorem shows that more general class of pricing schemes may not help the seller to obtain more revenue. One might then wonder whether at least never hurts since that is the case, least would never be a worse choice. Unfortunately, our following example shows that richer class of pricing schemes may bring strict harm the seller and strict benefit the seller.
Example 1 The Risk of Overexploiting Buyer Incentives). There is single type of divisible good to sell, i.e., d = 1. Let the seller's 's production cost function be the convex function c(x) = x² and let the buyer's true value function v(x) be the following piece-wise linear concave function
10x
< x S 0.81
u(x) =
8.1
x > 0.81
Let Pe denote the set of all concave pricing schemes. The following proposition completes Example and its proof can be found in Appendix E2.]
For the instance in Example 7 there exists pricing scheme class P with Pt, C P C Pc such that when the seller changes from linear pricing class L to the richer class P, the seller's 'ss revenue strictly decreases and the buyer's surplus strictly increases at the equilibrium of PADD.
Proposition 1.
Conclusions
Motivated by optimal pricing against an unknown buyer, this paper put forwards a simple variant of the very basic pricing model by augmenting with an additional stage of buyer commitment at the beginning. This motivation is driven by the seller's ignorance of the buyer's value function and thus have to price the dark. We fully characterize the equilibrium this new game model. The cquilibrium reveals interesting insights about what the seller can learn, and how much seller revenue

---

and buyer surplus it may result in. We also show that more general class of pricing schemes may overfit the buyer's incentive and lead to a pricing game that is even easier for the buyer to manipulate.
Our results opens the possibilities for many other interesting questions. For example, given the risk of using too general class of pricing schemes, what class of pricing schemes is a good compromise between extracting revenue and robust to buyer manipulations? Is linear pricing scheme the best such class or any other pricing scheme? Second, as the first study of our setup, we have chosen focus on a simple setup where the seller has completely no knowledge about the buyer's value function. An interesting question is, how the seller's s learning and resultant revenue may increase when the seller has some prior knowledge about the buyer's s values. In fact, one natural modeling question is how to model the seller's prior knowledge about the buyer's value function. Is the prior knowledge about which subclass the value functions are from or about what distribution the parameters of the value functions are from? Finally, our model assumes that the buyer has full knowledge about the seller. An ambitious though extremely intriguing question to ask is what if the buyer also has incomplete knowledge about the seller and how to analyze the equilibrium under the information asymmetry from both sides.
References
[1] E. Akyol, C. Langbort, and T. Basar. Price of transparency in strategic machine learning. arXiv, pages arXiv-1610, 2016.
[2] R. Allen. Macro-economic theory: a mathematical treatment. 1967.
[3] K. Amin, R. Cummings, L. Dworkin, M. Kearns, and A. Roth. Online learning and profit maximization from revealed preferences. In Twenty-Ninth AAAI Conference on Artificial Intelligence, 2015.
[4] K. Amin, A. Rostamizadeh, and U. Syed. Learning prices for repeated auctions with strategic buyers. In Advances in Neural Information Processing Systems, pages 1169-1177, 2013.
[5] K. Amin, A. Rostamizadeh, and U. Syed. Repeated contextual auctions with strategic buyers. In Advances in Neural Information Processing Systems, pages 622-630, 2014.
[6] M.-F. Balcan, A. Daniely, R. Mehta, R. Umer, and V. V. Vazirani. Learning economic parameters from revealed preferences. In International Conference on Web and Internet Economics, pages 338-353. Springer, 2014.
[7] P. Beato and A. Mas-Colell. On marginal cost pricing with given tax-subsidy rules. Journal of Economic Theory, 37(2)355--35, 1985.
[8] E. Beigman and R. Vohra. Learning from revealed preference. In Proceedings of the 7th ACM Conference on Electronic Commerce, pages 36 42, 2006.
[9] O. Ben-Ayed and C. E. Blair. Computational difficulties of bilevel linear programming. Opera- tions Research, 38(3)556-550, 1990.
[10] G. Birmpas, J. Gan, A. Hollender, F. Marmolejo, N. Rajgopal, and A. Voudouris. Optimally deceiving a learning leader in stackelberg games. Advances in Neural Information Processing Systems, 33, 2020.
[11] M. Brückner and T. Scheffer. Stackelberg games for adversarial prediction problems. In Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 547-555, 2011.
[12] Y. Chen, Y. Liu, and C. Podimata. Learning prategy-aware linear classifiers. Advances in Neural Information Processing Systems, 33, 2020.
[13] Y. Chen, C. Podimata, A. D. Procaccia, and N. Shah. Strategyproof linear regression in high dimensions. In Proceedings of the 2018 ACM Conference Economics and Computation, EC '18, page 9-26, New York, NY, USA, 2018. Association for Computing Machinery.
[14) V. Conitzer and T. Sandholm. Computing the optimal strategy to commit to. In Proceedings of the 7th ACM conference on Electronic commerce, pages 82-90, 2006.
10

---

[15] O. Dekel, F. Fischer, and A. D. Procaccia. Incentive compatible regression learning. Journal of Computer and System Sciences, 76(8):759-777, 2010.
[16] A. V. den Boer. Dynamic pricing and learning: historical origins, current research, and new directions. Surveys in operations research and management science, 20(1):1-18, 2015.
[17] Dong, A. Roth, Z. Schutzman, B. Waggoner, and Z. S. Wu. Strategic classification from revealed preferences. In Proceedings of the 2018 ACM Conference Economics and Compu- tation, EC '1, page 55-70, New York, NY, USA, 2018. Association for Computing Machinery.
[18] J. Gan, Q. Guo, L. Tran-Thanh, Thanh, B. An, and M. Wooldridge. Manipulating learning defender and ways to counteract. Advances in Neural Information Processing Systems, pages 8272- 8281, 2019.
[19] Gan, H. Xu, Q. Guo, L. Tran-Thanh, Rabinovich, and M. Wooldridge. Imitative follower deception in stackelberg games. In Proceedings of the 2019 ACM Conference on Economics and Computation, pages 639-657, 2019.
[20] M. Hardt, N. Megiddo, C. Papadimitriou, and M. Wootters. Strategic classification. In Proceedings of the 2016 ACM Conference Innovations in Theoretical Computer Science, ITCS '16, page 111-122, New York, NY, USA, 2016. Association for Computing Machinery.
[21] L. Hu, N. Immorlica, and J. W. Vaughan. The disparate effects of strategic manipulation. In Proceedings of the Conference on Fairness, Accountability, and Transparency, FAT '19, page 259-268 New York, NY, USA, 2019. Association for Computing Machinery.
[22] N. Korula, V. Mirrokni, and H. Nazerzadeh. Optimizing display advertising markets: Challenges and directions. IEEE Internet Computing, 20(1):28-35, 2015.
[23] Li, N. Granados, and Netessine, Are consumers strategic? structural estimation from the air-travel industry. Management Science, 6009):211422137, 2014.
[24] A. Mas-Colell, M. D. Whinston, J. R. Green, et al. Microeconomic theory, volume 1. Oxford university press New York, 1995.
[25] S. Milli, J. Miller, A. D. Dragan, and M. Hardt. The social cost of strategic classification. In Proceedings of the Conference on Fairness, Accountability, and Transparency, FAT* '19, page 230-239, New York, NY, USA, 2019. Association for Computing Machinery.
[26] M. Mohri and A. Munoz. Optimal regret minimization in posted-price auctions with strategic buyers. In Advances in Neural Information Processing Systems, pages 1871-1879, 2014.
[27] M. Mohri and A. Munoz. Revenue optimization against strategic buyers. In Advances in Neural Information Processing Systems, pages 2530-2538, 2015.
[28] T. Nedelec, C. Calauzenes, V. Perchet, and N. El Karoui. Robust stackelberg buyers in repeated auctions. In International Conference on Artificial Intelligence and Statistics, pages 1342-1351. PMLR, 2020.
[29] H. Nguyen, N. Vu, A. Yadav, and U. Nguyen. Decoding the imitation security game: Handling attacker imitative behavior deception. In 24th European Conference on Artificial Intelligence, ECAI 2020, including 10th Conference on Prestigious Applications of Artificial Intelligence, PAIS 2020, pages 179-186. IOS Press BV, 2020.
[30] T. H. Nguyen and H. Xu. Imitative attacker deception in stackelberg security games. In Proceedings of the 28th International Joint Conference on Artificial Intelligence, pages 528- 534, AAAI Press, 2019.
[31] J. Perote and J. Perote-Peña. Strategy-proof estimators for simple regression. Math. Soc. Sci., 47:153-176, 2004.
[32] A. Roth, A. Slivkins, J. Ullman, and S. Wu. Multidimensional dynamic pricing for welfare maximization. ACM Transactions Economics and Computation (TEAC), 8(1):1-35, 2020.
11

---

[33] A. Roth, J. Ullman, and Z. S. Wu. Watch and learn: Optimizing from revealed preferences feedback. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing. pages 949-962, 2016.
[34] P. Samuelson and W. Nordhaus. Microeconomics, Itwin/McGraw-Hill, 1998.
[35] R. W. Shephard and R. Färe. The law of diminishing returns. Zeitschrift für Nationalökonomie, 34(1-2):69-99) 90, 1974.
[36] 'ang and Y. Zeng. The price of prior dependence in auctions. In Proceedings of the 2018 ACM Conference on Economics and Computation, pages 485-502, 2018.
[37] R. Turvey. Marginal cost. The Economic Journal, 79(314):282-999 1969.
[38] A. Vanunts and A. Drutsa. Optimal pricing in repeated posted-price auctions with different patience of the seller and the buyer. In Advances in Neural Information Processing Systems, pages 939-951, 2019.
[39] M. Zadimoghaddam and A. Roth. Efficiently learning from revealed preference. In International Workshop Internet and Network Economics, pages 114 114-127. Springer, 2012.
[40] H. Zhang, Y. Cheng, and V. Conitzer. Distinguishing distributions when samples strategically transformed. In Advances in Neural Information Processing Systems, pages 3193-3201, 2019.
[41] H. Zhang, Y. Cheng, and V. Conitzer. When samples are strategically selected. In International Conference on Machine Learning, pages 7345-7353, 2019.
[42] H. Zhang and V. Conitzer. Learning the valuations of k-demand agent. D. III and A. Singh, editors, Proceedings of the 37th International Conference Machine Learning, volume 119 Proceedings of Machine Learning Research, pages 1066-11075. PMLR, 13-18 Jul 2020.
[43] H. Zhang and V. Conitzer. Incentive-aware pac learning. AAAI 2021, 2021.
12


Reviews:
[{"review_id": "hLGda_eDKn3", "reviewer": "Reviewer_ZMGR", "summary": "This paper studies the problem of pricing against a strategic buyer in the digital good market. The authors consider a two-player game environment in which the buyer first commits to imitate a different value function and react optimally according to the imitative value function. And the seller optimizes the pricing strategy against the imitative value function. \n\nThe authors fully characterize the optimal imitative function for the buyer as well as seller's revenue and buyer's surplus in the equilibrium when the seller adopts linear pricing. The results demonstrate a sharp contrast between concave production cost and convex production cost. In particular, for concave production cost, the seller obtains 0 revenue. The authors also provide results for pricing schemes beyond linear pricing.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "This paper is generally well-written, clear, and easy to follow. The collection of results seems to be novel and technically strong. The sharp contrast between convex and concave production cost is very interesting and provides useful insights for practice. The reviewer did not check all the proofs but they all look plausible in hindsight.\n\nComments:\n\n1. If the reviewer understands correctly, although the problem studied in this paper is better motivated in a repeated setting, the concrete setting considered in this paper is essentially a one-shot game instead of a repeated game (e.g., see Definition 1). In other words, the repeated game is essentially compressed into a one-shot game in this paper.\n\n2. It is unclear whether that the buyer commits first and then the seller responds gives the buyer a disadvantage or an advantage. The typical order in online pricing would be that the seller commits to a mechanism first, and then the buyer best responds to the mechanism. In a one-shot game, it would be the seller commits to the allocation and payment rule (depending on the buyer's imitative value function) and then the buyer best responds with an imitative value function. The reviewer is curious about what the results would look like in this setting. In Tang and Zeng [35], if the reviewer understands correctly, the seller already commits to using the Myerson's auction (or the second-price auction) first and then the buyer best responds with a fake distribution.\n\n3. The reviewer appreciates the nice plots in Figure 2. It would be great if the authors can provide high-level intuitions behind Theorem 2.\n\n4. For Theorem 4, the reviewer wonders whether the problem would be tractable when the production cost is convex.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The model choice, in which the buyer commits first and then the seller responds, needs more justification.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "TBdJtK_WXT", "reviewer": "Reviewer_ocDy", "summary": "This paper consider a problem of buying/selling multiple divisible items with a posted price mechanism between one buyer and one seller, in a noiseless setting. It consider the problem that through repeated trades, buyer and seller learn from each other, leading them to adopt strategies that maximizes their revenue over time, breaking classical incentive compatibility properties. More precisely, this paper considers that \n* given a mechanism (seller) and a value function (buyer), the buyer plays a one-shot best response.\n* given a value function (buyer), the seller chooses the optimal mechanism (knowing the buyer will play best response)\n* given this previous knowledge, the buyer chooses a *fake* value function to announce to the seller to optimize his objective.\n\nThis paper describes the properties of the solutions of this tri-level optimization problem and characterize the complexity of solving it.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "**Clarity and quality**\n* The paper is easy to read and maths are clearly written. I just wish the appendix was more self-contained, e.g. with cited results and optionally their proofs restated, especially for intermediate results that are pointing towards articles behind paywalls and thus not available. \n* This paper manages to bring some good insights on the complex problem of understanding buyers strategies and more especially how seller optimization impacts buyers' strategies.\n* Maybe a more recent work to position in you related work (related to Tang and Zheng 2018) *Robust Stackelberg buyers in repeated auctions.* (AISTATS 2020).\n\n\n**Originality and significance**\n* While there is a significant amount of work about how seller should behave in repeated settings, there is much little work on the strategies buyers could use. As such, I find this paper original.\n* Some comments about the setting and maybe an ask for better explaining its limitations:\n  * It studies an equilibrium of a repeated game, but does not provide insights on whether this equilibrium is reachable by dynamic strategies.\n  * It considers a specific class of strategies for the buyer: a one shot best-response $x^*(.)$ based on a fake value function $u$ concave and monotone, non-decreasing. I'm wondering whether when optimizing on *any* fake value function $u$ (not necessarily concave), the optimum $u^*$ is still concave when $v$ is so or not. For instance, in Tang and Zheng 2018, even if the true value distribution is regular, the optimal fake distribution is not regular. Is there a similar phenomenon here ?\n* Maybe a future direction: the seller generally does not have a perfect knowledge of $u$ (but estimates it from historical interactions for instance), how sensitive is the optimal $u$ to the seller only knowing it at precision $\\varepsilon$ ?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "see main review", "review_text": "", "extra_scores": {"ethical_concerns": "Not that I can think of.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "HfUlDExlsW6", "reviewer": "Reviewer_Abq4", "summary": "The paper discusses an economic strategic learning scenario, where a seller and a buyer repeatedly engage in selling a bundle of d divisible goods, and where the seller attempt to learn the pricing scheme leading to a maximal revenue. \n\nIn this scenario, there is only one seller and one buyer, i.e. no competition could be introduced (such as what would happen in an auction for example). The buyer could manipulate the seller by refusing to buy at certain prices even if that single purchase has a positive utility to them, so as to lead the seller to change the prices in a way that improves the buyer's utility in the future. \n\nThe proposed scheme is a simple Stackelberg model, where the buyer commits to \"pretending\" they have a different utility function (i.e acting as if they were making local buying decisions without trying to manipulate under a utility that is different to their true one). \n\nThe authors characterize teh the optimal value function the buyer should imitate, and examines the resulting equilibrium. Under concave production functions, the seller ends up with zero revenue (i.e. the buyer would manipulate in a way that extracts all the surplus), whereas for a convex production they give an equilibrium with a positive seller utility. Another key result is that a different class of pricing schemes does not mitigage this effect, and would in fact be harmful for the seller. ", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "The problem studied here seems to be a natural economic problem, and the results are insightful. \n\nEconomically, the scenario strikes me as a bit odd, as there is no competition here (so alternatively, one might view this as a seller and buyer negotiating a pricing scheme for multiple transactions in the future, in a case where the seller has no knowledge of the buyer's utility). This is in sharp contrast to perfect competition between firms or a repeated auction. However, the authors provide some justification as to why some domains might behave this way. \n\nIn terms of the key takeaways, I think they relate to economics rather than machine learning. While some of the related work deals with e.g. classification in strategic settings, I feel like the results here have much less to do with learning, but rather with optimization and economics, so I am not sure whether this is the best venue for this work (as opposed to say ACM EC, WINE or even some of the tracks at WWW). \n\nThe analysis is non-trivial, but again I'm not sure whether most in the general ML community would be able to put the techniques applied here to use in their own domains. Overall, the authors need to do a better job at tying this to related ML literature (e.g. a table comparing the results here with strategic classification). I also think a comparison with other Stackelberg domains is in order; the key insight here is that a very simple manipulation works --- the buyer just needs to pretend they have a different valuation function and follow that in a naive (truthful) way, so a more sophisticated manipulation is not required (in contrast to other Stackleberg domains). What are the connections between this and the field of mechanism design?\n\nTo conclude, interesting paper, but not a great fit for the conference - not sure what the key takeaway message is for an ML audience. Also, the authors need to better connect it to existing work. On the positive side, interesting technique, and a good presentation of the key results with some insight. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors fully discuss the limitations of their work, and I do not see a need to dig deeper into possible societal impact. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5 hours"}, "extra_text": {}}, {"review_id": "AAo8GMLvQE", "reviewer": "Reviewer_dqi7", "summary": "This paper considers the dynamic of a pricing game between a strategic buyer and a revenue-maximizing seller. The main contribution of this paper is that they give a complete characterization of buyer's optimal strategy and seller's corresponding response (which forms an equilibrium). \n\n", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "This paper considers the dynamic of a pricing game. The story of this paper is like, in reality, sellers often have no chance to gather any information about the potential buyer. Therefore the only way to know something about the preference is learning buyer's valuation function through repeated auctions. However the buyer could play strategically to improve his own utility. This paper considers a quite natural class of strategies of the buyer -- he just pretends their valuation to be another one and plays consistently with this fake valuation. Thus, the only thing that the seller can do is finding the optimal to maximize her revenue. This paper studies the best responses for each player in this game when seller's pricing is restricted to linear pricing.\n\nThe main contribution is that this paper fully characterizes the equilibrium of the game. It is a complex tri-level functional optimization problem, and the result equilibrium is surprisingly neat. \n\nOverall I think it's a paper of good quality. The story is interesting to me and setting just makes sense. The highlight of this work is that the characterization of linear pricing is complete and neat. I also really like discussion of non-linear pricing schemes and insightful observations of the possibility of over-exploiting buyer's incentives. I would encourage the author to make proof sketches not that dense, although much of abstraction comes from the nature of functional optimization, maybe adding some examples would help.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have adequately addressed the limitations and I see no potential negative societal impact of this work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper deals with a novel novel question, provides a non-trivial and gets to a surprisingly clean result.

There were some concerns regarding the relation to Tang and Zheng and the learning angle to justify publication in NeurIPS, but both points were adequately addressed by the authors in their response.

The review team is confident that this is a strong contribution to NeurIPS.
Decision: Accept (Poster)