The Limits of Optimal Pricing in the Dark∗

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.

heading: 1 Introduction
text: Pricing is 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 a seller (she). The seller produces d types of divisible goods for sale and has production cost c(x) for producing bundle x ∈ Rd+ of the d goods. Using a standard linear pricing scheme with unit price pi for goods i ∈ [d], the seller charges the buyer x · p when he purchases bundle x ∈ 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 [v(x)− x · p]. The key question of interest is how the seller can compute the revenue-maximizing optimal prices assuming rational buyer purchase behaviors.
∗This work is supported by a Google Faculty Research Award and an NSF grant CCF-2132506.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
The above basic problem can be easily solved if the seller has access to the buyer’s value function v(x). However, in practice, this value function is usually private and unknown to the seller. To address this challenge, there has been a rich line of recent research which looks to design the optimal pricing scheme against an unknown buyer. Some of these work have adopted learning-based approaches that aim to compute the profit maximizing price by interacting with the buyer and gleaning information about the buyer’s utility function [3, 33, 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, 5, 26, 27, 38].
A 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 algorithms. Indeed, as observed in previous studies, online advertisers may strategically respond to an ad exchange platform’s prices in order to induce a 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 optimal pricing against such a strategic and possibly manipulative 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 a 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 commitment to an imitative value function captures a simple yet powerful buyer manipulation strategy that can be used against any seller learning algorithms — that is, the buyer simply behaves consistently according 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 no information about the buyer and has to optimize pricing “in the dark”. Consequently, if the buyer consistently behaves according to 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 3). Moreover, such an imitation strategy is also easy to 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 imitative value function.
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 to 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 [18, 30, 29]. Our optimal pricing problem is also a Stackelberg model and thus a natural fit for the study. The crucial difference between our work and previous studies is 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 a 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.

heading: 1.1 Our Results and Implications
text: Given the effectiveness and easy applicability of the buyer’s imitative strategy described above, this paper studies what the optimal buyer imitative value function is and how it 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 a specific bundle of products x∗ that is most desirable to the buyer. Interestingly, it turns out
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 strictly 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 0. The fortunate news for the seller, however, is 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 0 and the x∗ bundle mentioned above. This illustrates an interesting message that convex production costs are “better” at handling buyer’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, 34].
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 to 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.

heading: 1.2 Additional Related Works
text: Due to space limit, here we only briefly discuss the most related works while refer readers to Appendix A.1 for more detailed discussions and comparisons. Closely related to ours is a 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 a single indivisible item with no production costs whereas our seller sells multiple divisible items with production costs. Another recent work [28] also studies buyer’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 strategy) with separated exploration-exploitation phases motivated by [4]. Another very relevant literature is 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 [4, 5, 27] or the seller sells a single indivisible good with discrete agent utilities. Thus, their results are not comparable to us.
There have also been studies on learning the optimal prices from truthful revealed preferences, i.e., assuming the buyer will honestly best respond to seller prices [8, 39, 6, 42, 3, 33, 32]. Our works try to understand if the assumption of truthful revealed preferences does not hold and if 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 as a 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, 43, 17, 25, 21, 12], regression problems [31, 15, 13] and distinguishing distributions [40, 41]. Our work however focuses on learning the optimal pricing scheme.

heading: 2 Preliminaries
text: Basic Setup of the Optimal Pricing Problem. A seller (she) would like to sell d different types of divisible goods to a buyer (he). It costs her c(x) to produce x ∈ Rd bundle of these goods. Let
X ⊂ Rd denote the set of all feasible bundles that the seller can produce. We assume X is convex, closed and has positive measure. As a standard assumption [24, 33, 8, 6, 39], the buyer has a concave value function v(x) for any goods bundle x ∈ X . We do not make any assumption about the seller’s production cost c(x), except that it is monotone non-decreasing. For normalization, we assume 0 ∈ X and v(0) = c(0) = 0. The seller aims to find a revenue-maximizing pricing scheme assuming rational buyer behaviors. A seller pricing scheme is a function p(x) that specifies the sale price for any bundle x. By convention, p(0) = 0 always. Let the set P 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 is parameterized by a price vector p (to be designed) such that p(x) = p · x where i’th entry pi is interpreted as the unit price for goods i. Let set
PL = {p : p(x) = p · x for some p ∈ Rd+}
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 ∈ P , a rational buyer looks to purchase bundle x∗ that maximizes his utility; That is, x∗ = arg maxx∈X [ v(x)− p(x) ] . Ties are broken in favor of the seller.2 The buyer’s best response can thus be viewed as a function x∗(p) of the seller’s price function p(x). Knowing that the buyer will best respond, the seller would like to pick the pricing function p∗ ∈ P to maximize her revenue. Formally, p∗ is the solution to the following bi-level optimization:
p∗ = argmax p∈P [p(x∗(p))− c(x∗(p))], where x∗(p) = argmax x∈X
[ v(x)− p(x) ] (1)
The optimal solution ( p∗,x∗(p∗) ) to such a bi-level optimization problem forms an equilibrium of this pricing game. More formally, this is often called the optimal Stackelberg equilibrium or strong Stackelberg equilibrium [14, 33]. We call p∗ the equilibrium pricing function and x∗ the equilibrium bundle. Note that this is a challenging functional optimization problem since the seller is picking a function p ∈ P , while not a vector variable. However, when P = PL is the set of linear pricing scheme, the above problem becomes a bi-level variable optimization problem since any p(x) ∈ PL can be fully characterized by a price vector p.
Terminologies from Convex Analysis. We defer basic definitions like convex/concave functions and super/sub-gradients to Appendix B, and only mention two useful notations here: (1) the set of super/sub-gradient for concave/convex function f is denoted as ∂f(x); (2) The Bregman divergence of a function f is defined as Df (z,x) = f(z)− f(x)−∇f(x) · [z− x]. Df (z,x) is an important distance notion and is strictly positive for strictly convex functions when z 6= 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 a different perspective and seeks to understand how a buyer can strategically deceive the seller, through a 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 a buyer manipulation strategy that is oblivious to any pricing algorithm. That is, the buyer simply imitates a different value function u(x) by consistently responding to any seller acts according to u(x). 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(x). Nevertheless, the buyer’s objective is still to maximize his true utility by carefully crafting an imitative value function u(x) to commit to. Given the buye’s commitment to value function u(x), the best pricing scheme for the seller is to use the optimal pricing function against buyer value function u(x). 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):
2This is usually without loss of generality since the seller can always induce desirable tie breaking by providing a negligible additional incentive to the buyer.
• The buyer with true value function v(x) (unknown to seller) commits to react optimally according to an imitative value function u(x) ∈ C.
• The seller learns the buyer’s imitative value function u(x) and compute the optimal pricing function p∗ ∈ P by solving bi-level Optimization Problem (1) w.r.t. u(x).
• 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 maxx∈X [u(x)− p(x)].
We remark that such commitment to a 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, 10] and security games [18, 30, 29]. 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(x), i.e., 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 1 (Equilibrium of PADD). The equilibrium of PADD consists of the optimal imitative value function u∗ ∈ C that the buyer commits to, the seller’s optimal pricing function p∗ ∈ P against u∗(x), and the buyer’s response bundle x∗ ∈ X . Formally, (u∗, p∗,x∗) is an equilibrium for a buyer with true value function v(x) to PADD if
u∗ = argmax u∈C [v(x∗)− p∗(x∗)], where p∗ = argmax p∈P [p(x∗)− c(x∗)],
where x∗ = argmax x∈X
[ u∗(x)− p∗(x) ] . (2)
The equilibrium of PADD gives rise to a challenging tri-level functional optimization problem.3 Note that, the dependence of the buyer’s objective [v(x∗) − p∗(x∗)] 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., P = PL = {p : p(x) = p · x for some p ∈ Rd+} consists of all linear pricing functions. A linear pricing function is determined by a non-negative price vector p ∈ Rd+. To distinguish functionals from vector variables, we will use PL = {p : p ∈ Rd+} to denote the set of all possible non-negative price vectors so that each p ∈ PL uniquely corresponds to a linear pricing function in PL. Under linear pricing, the equilibrium in Def. 1 denoted by (u∗,p∗,x∗) is characterized by Eq. (2) where P = PL. Even with linear pricing, this is still a very challenging tri-level functional optimization problem since u∗ is a function chosen from the set of all possible functions from X to R+, denoted by set C. A first thought one might have is: why doesn’t the buyer simply imitate u∗(x) = c(x). We will see later that this is not — in fact far from being — optimal since it makes the game zero-sum and the seller will pick a price that guarantee 0 revenue, e.g., a price of∞. This leads the trade to happen at 0 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(x). Theorem 1. In the equilibrium of PADD under linear pricing, the optimal buyer imitative value function u∗ can w.l.o.g. be written as the following concave function parameterized by production amount x∗ ∈ X and a real value p∗ ∈ R+:
u∗(x) = p∗ ·min{x1 x∗1 , · · · xd x∗d , 1} (3)
3Even for linear pricing where P = PL, this is still a functional optimization problem since the buyer’s imitative value function u is an arbitrary function in C.
where
x∗ = arg max x∈X
[ v(x)− sup
α∈[0,1)
c(x)− c(αx) 1− α
] and p∗ = sup
α∈[0,1)
c(x∗)− c(αx∗) 1− α
(4)
Moreover, under imitative value function u∗(x),
1. For any vector λ ∈ ∆d in the d-dimensional simplex, the linear pricing scheme with price vector p∗ = (λ1 p ∗
x∗1 , λ2
p∗ x∗2 , · · · , λd p ∗ x∗d ) 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 is [v(x∗)− p∗] and the seller revenue is [p∗ − c(x∗)].
Note that the u∗ described by Equation (3) may not be the unique optimal buyer imitative value function, but it 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 a formal proof, it is worthwhile to take a closer look at the characterization of the buyer’s optimal imitative value function u∗ characterized by Theorem 1 and the special pricing problem it ultimately induces. At a high level, the buyer has a 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 x will linearly depend on the minimum possible coordinate-wise fraction of x∗ that x contains, i.e., the min{x1x∗1 , · · · xd x∗d , 1} term in u∗.4
The p∗ is chosen as the largest possible slope of the segment between c(x∗) to c(αx∗) among all possible α ∈ [0, 1) (see Figure 1 for an illustration in one dimension about how p∗ is chosen based on the cost function c). This is certainly a very carefully chosen value. Note that
p∗ = sup α∈[0,1) c(x∗)− c(αx∗) 1− α ≥ c(x ∗)− c(0) 1− 0 = c(x∗),
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 ≥ 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 ∈ [0, 1] of x∗, the seller’s optimal pricing will charge rp∗ for the bundle
x = rx∗ and this total charge rp∗ can be distributed arbitrarily over the d products, e.g., by charging λirp
∗ = λi p∗·xi x∗i for product i where ∑d i=1 λi = 1. Overall, Theorem 1 fully characterized what the pricing problem is like at the equilibrium of PADD. Remark 1. Theorem 1 only provides a structural characterization about the equilibrium but does not imply that the equilibrium (u∗,p∗,x∗) can be computed efficiently since we still need to solve the optimization problem (4) to find the optimal x∗. As we will show later, this turns out actually to be an NP-hard problem in general. This is an interesting situation where the result reveals useful structural insights despite its computational intractability.
Proof Sketch of Theorem 1. The proof of Theorem 1 is somewhat involved. We give a sketch here and defer formal arguments to Appendix C. The most challenging part is to find the optimal function u∗ ∈ 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
4Notably, the format of this value function appears to have interesting connections to the well-known Leontief production function [2] which has the format of mini{xiai }. However, leontief functions are 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 to be optimal for buyer’s strategic manipulation.
optimization problem to a variable optimization problem since any function of Format (3) can be characterized by d+ 1 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 a 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 a slightly simpler version of the question. That is, fixing any bundle x ∈ 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 x ∈ X , the optimal buyer imitative value function u(x), subject to that the resultant optimal buyer purchase response is bundle x, can without loss of generality have the following piece-wise linear concave function format, parameterized by a real number p ∈ R:
u(x) = p ·min{x1 x1 , · · · xd xd , 1} (5)
where p ∈ R is the solution to the following linear program (LP): maximize v(x)− p subject to p− c(x) ≥ α · p− c(αx), for α ∈ [0, 1].

heading: 5 Explicit Characterizations for Convex and Concave Costs
text: In this section, we instantiate Theorem 1 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 [7, 37]. When c(x) 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 c is convex and differentiable, the piece-wise linear concave value function u∗(x) defined by Equation (3), with p∗ = x∗ · ∇c(x∗) and x∗ = arg maxx∈X [v(x)− x · ∇c(x)], is an optimal buyer imitative value function.
Under u∗(x), the trade happens at bundle x∗ with payment p∗ = x∗ · ∇c(x∗). The seller revenue [x∗ · ∇c(x∗)− c(x∗)] is precisely the Bregman divergence Dc(0,x∗) between 0 and x∗. The buyer surplus is [v(x∗)− x∗ · ∇c(x∗)].
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.
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 maxx∈X [v(x)− c(x)], is an optimal buyer imitative value function.
Under u∗(x), the trade happens at bundle x∗ with payment p∗ = c(x∗). The seller revenue will be 0. The buyer extracts the maximum possible surplus maxx∈X [v(x)− c(x)]. Graphical visualizations for the above two theorems are depicted in Figure 2. Note that both examples in Figure 2 show the sub-optimality of imitating u∗(x) = c(x) for the buyer. To see this, note u∗(x) = c(x) makes the game zero-sum. To guarantee non-negative revenue, the seller must pick a price p such that the line p · x is always above u∗(x). A buyer imitating u∗(x) = 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 3 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.e., 0.5 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 to 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(x) 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 P = NP.
Theorem 4. [Intractability of Equilibrium] It is NP-hard to approximate the buyer equilibrium surplus in PADD games to be within ratio 1/d1− for any > 0. This hardness result holds even when the production cost function c(x) is concave and the buyer’s true value function v(x) is simply the linear function ∑d i=1 xi.
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∗ = argmaxx[u(x)− x · ∇c(x)] for any value function u, however how to derive the optimal u∗ remains challenging.

heading: 6 The Risk of Over-exploiting Buyer’s Incentives
text: To counteract the buyer’s strategic manipulation, one of the most natural approaches is perhaps to use a richer or more powerful class of pricing schemes, as opposed to only using linear pricing. Such additional power of pricing will always increase the revenue when facing an honest buyer. Unfortunately, however, we show that it does not necessarily help in the presence of buyer manipulation — in fact, the seller may suffer the risk of over-exploiting the buyer’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.
We first prove that the strictly more general class of concave pricing schemes can 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 as 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 a bi-level optimization problem (in particular, FOP (6)). Recall that the proof of Theorem 1 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 3 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 (11) we solve in the proof of Theorem 1. Nevertheless,
5In 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.
through careful convex analysis, we are able to show that the optimal solution to FOP (6) also admits an optimal solution of similar structure as characterized by Theorem 1. Theorem 5. The equilibrium of PADD under concave pricing is exactly the same as the equilibrium under linear pricing as characterized by Theorem 1.
Proof Sketch of Theorem 5. We start by examining how the use of concave pricing schemes may simplify FOP (2). Recall that both value functions and pricing functions are monotone non-decreasing and normalized to be 0 at 0. For any concave buyer value function u ∈ C, it is easy to see that the optimal pricing function p simply equals u (i.e., charging buyer exactly his imitative value) and ask the buyer to break ties in favor of the seller by picking x∗ = arg maxx∈X [u∗(x) − 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:
u∗ = argmax u∈C [v(x∗)− p∗(x∗)], where x∗ = argmax x∈X
[ u∗(x)− c(x) ] We fix a particular bundle x and examine what buyer value function u ∈ C would maximize the buyer’s utility subject to that the trade will happen at bundle x. This results in the following functional optimization problem (FOP) for the buyer with functional variable u.
maximize v(x)− u(x) subject to u(x)− c(x) ≥ u(x′)− c(x′), for x′ ∈ 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 x. The remaining proof relies primarily on the following lemma.
Lemma 2. The following concave function is optimal to FOP (6):
u(x) = p ·min{x1 x1 , · · · xd xd , 1}, where p = sup α∈[0,1) c(x)− c(αx) 1− α . (7)
Given this characterization, the buyer simply needs to look for the best x. This then leads to the same characterization as in Theorem (1) since Equation (7) is the same as the value function characterized in Equation (5). The proof of Lemma 2 is deferred to Appendix E.1.
Theorem 5 shows that more general class of pricing schemes may not help the seller to obtain more revenue. One might then wonder whether it at least never hurts since if that is the case, at least it would never be a worse choice. Unfortunately, our following example shows that a richer class of pricing schemes may bring strict harm to the seller and strict benefit to the seller. Example 1 ( The Risk of Overexploiting Buyer Incentives). There is a single type of divisible good to sell, i.e., d = 1. Let the seller’s production cost function be the convex function c(x) = x2 and let the buyer’s true value function v(x) be the following piece-wise linear concave function
v(x) = { 10x 0 ≤ x ≤ 0.81 8.1 x > 0.81
Let PC denote the set of all concave pricing schemes. The following proposition completes Example 1 and its proof can be found in Appendix E.2. Proposition 1. For the instance in Example 1, there exists pricing scheme class P with PL ⊂ P ⊂ PC such that when the seller changes from linear pricing class PL to the richer class P , the seller’s revenue strictly decreases and the buyer’s surplus strictly increases at the equilibrium of PADD.

heading: 7 Conclusions
text: Motivated by optimal pricing against an unknown buyer, this paper put forwards a simple variant of the very basic pricing model by augmenting it 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 in the dark. We fully characterize the equilibrium of this new game model. The equilibrium 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 a 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 to 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 learning and resultant revenue may increase when the seller has some prior knowledge about the buyer’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.

Review summaries:
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.   The 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.

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  * given a mechanism (seller) and a value function (buyer), the buyer plays a one-shot best response. * given a value function (buyer), the seller chooses the optimal mechanism (knowing the buyer will play best response) * given this previous knowledge, the buyer chooses a *fake* value function to announce to the seller to optimize his objective.  This paper describes the properties of the solutions of this tri-level optimization problem and characterize the complexity of solving it.

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.   In 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.   The 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).   The 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.