The Limits of Optimal Pricing in the Dark

Quinlan Dawkins, Minbiao Han, Haifeng Xu

In today's digital markets, sellers frequently rely on machine learning algorithms to "price in the dark," gradually discovering a buyer's willingness to pay through repeated interactions. However, this paper reveals a critical vulnerability in these systems: a strategic buyer can systematically defeat these algorithms by committing to an "imitative value function"—essentially a consistent lie about their preferences—forcing the seller into sub-optimal pricing.

The Challenge of Strategic Manipulation

In modern e-commerce and online advertising, sellers rarely know a buyer’s true valuation for a product upfront. Instead, they use repeated interactions to learn it over time. A major flaw in most pricing algorithms is the assumption that the buyer is a "passive" agent who simply reacts truthfully to prices.

If a buyer knows the seller is learning from their behavior, they have a strong incentive to act as if they value the goods less than they actually do. By doing so, they can induce lower future prices. The authors formalize this dynamic as Pricing Against a Deceptive buyer in the Dark (PADD). In this framework, the buyer commits to a specific (fake) value function before the game begins, and the seller must optimize their pricing against this imitation.

Modeling the Deception

The researchers model this interaction as a tri-level functional optimization problem:

  1. The Buyer chooses an imitative value function $u(x)$ to maximize their true utility.
  2. The Seller observes this behavior and chooses an optimal pricing scheme $p(x)$ to maximize revenue against the perceived $u(x)$.
  3. The Buyer then "best responds" to that price according to their committed fake function $u(x)$.

Moving beyond standard discrete models, the authors use functional analysis and convex optimization to characterize the equilibrium. They identify the specific structure of the "optimal lie" and examine how different production cost structures (convex vs. concave) and pricing classes affect the final outcome.

Key Insights and Findings

The "Leontief" Lie

Surprisingly, the optimal strategy for a buyer isn't just to pretend they value everything uniformly less. Instead, the optimal imitative function $u^*(x)$ takes the shape of a "Leontief-type" function. The buyer pretends they only care about one specific "perfect bundle" of goods and value nothing beyond it. This forces the seller to price that specific bundle aggressively just to make a sale.

Optimal imitative value function $u^*(x)$ against concave costs, driving seller revenue to zero.

The Power of Convexity

The seller’s fate depends entirely on their production costs. If costs are concave (indicating economies of scale), the strategic buyer can squeeze the seller's revenue down to exactly zero.

However, if costs are convex (indicating increasing marginal costs), the seller retains some power. Against convex costs, the seller can still capture revenue equal to the Bregman divergence of their cost function between no production and certain production.

Under convex costs, the seller retains some utility despite the buyer's optimal manipulation.

The Overfitting Paradox

One might assume a seller could thwart manipulation by deploying more complex, non-linear pricing models. The authors prove this intuition wrong. Moving to a broader class of "concave pricing" does not help the seller. In fact, it can be harmful. A more flexible pricing model "overfits" to the buyer's strategic incentives, making it even easier for the buyer to manipulate the outcome. The paper proves that the equilibrium under complex concave pricing is identical to the equilibrium under simple linear pricing, providing a strong theoretical justification for why simple linear pricing remains so prevalent in the real world.

Strategic Complexity as a Defense

While a devastating "optimal lie" exists in theory, the paper proves it is NP-hard for the buyer to actually compute it. Specifically, it is NP-hard to approximate the buyer's maximum surplus within a factor of $1/d^{1-\epsilon}$. This suggests that in high-dimensional markets with many types of goods, buyers likely cannot find the absolute best way to deceive the seller. The computational complexity of finding the perfect manipulation serves as a natural defense for the seller.

Limitations and Future Work

The current model assumes the buyer has full knowledge of the seller's production cost function. In reality, this is often private information, which would lead to a "double-blind" scenario. Additionally, the paper assumes the buyer can perfectly commit to their imitative function without deviating mid-stream.

Future research could explore what happens when the buyer's commitment power is relaxed, or investigate how even a small amount of prior knowledge about the buyer's true valuation distribution could shift the balance of power back toward the seller.

Summary updated

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.
BibTeX
@inproceedings{dawkins2021limits,
  author = {Quinlan Dawkins and Minbiao Han and Haifeng Xu},
  title = {{The Limits of Optimal Pricing in the Dark}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=TqvwWkdlLIk},
}
Figure