Algorithmic pricing via virtual valuations

By S. Chawla, Jason D. Hartline, Robert D. Kleinberg. ACM Conference on Economics and Computation, 2007

323 citations recorded by the source corpus.

Algorithmic pricing is the computational problem that sellers (e.g.,in supermarkets) face when trying to set prices for their items to maximize their profit in the presence of a known demand. Guruswami etal. (SODA, 2005) proposed this problem and gave logarithmic approximations (in the number of consumers) for the unit-demand and single-parameter cases where there is a specific set of consumers and their valuations for bundles are known precisely. Subsequently several versions of the problem have been shown to have poly-logarithmic in approximability. This problem has direct ties to the important open question of better understanding the Bayesian optimal mechanism in multi-parameter agent settings; however, for this purpose approximation factors logarithmic in the number of agents are inadequate. It is therefore of vital interest to consider special cases where constant approximations are possible. We consider the unit-demand variant of this pricing problem. Here a consumer has a valuation for each different item and their value for aset of items is simply the maximum value they have for any item in the set. Instead of considering a set of consumers with precisely known preferences, like the prior algorithmic pricing literature, we assume that the preferences of the consumers are drawn from a distribution. This is the standard assumption in economics; furthermore, the setting of a specific set of customers with specific preferences, which is employed in all of the prior work in algorithmic pricing, is a special case of this general Bayesian pricing problem, where there is a discrete Bayesian distribution for preferences specified by picking one consumer uniformly from the given set of consumers. Notice that the distribution over the valuations for the individual items that this generates is obviously correlated. Our work complements these existing works by considering the case where the consumer's valuations for the different items are independent random variables. Our main result is a constant approximation algorithm for this problem that makes use of an interesting connection between this problem and the concept of virtual valuations from the single-parameter Bayesian optimal mechanism design literature.

Subfields: Management Information Systems, Management Science and Operations Research, Marketing

View Paper: https://www.semanticscholar.org/paper/ee967f77da91b3851c0dc144297470a08c54f9f6

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Management Information Systems

In Management Science and Operations Research

In Marketing

Citations in the corpus

Simple versus optimal mechanisms (2009, background): “3 ([2]) There are non-identical irregular distributions such that the expected revenue of Vickrey with the best anonymous reserve is no better than a logarithmic approximation to that of the optimal auction.”
Multi-parameter mechanism design and sequential posted pricing (2010, methodology): “We extend the setting from [10] to multiple agents and improv e their approximation for a single agent from 3 to 2.”
The sample complexity of revenue maximization (2014, background): “[6, 14]) or even, when there is no bidder with a unique valuation distribution, with no dependence on the valuation distributions [7, 8, 18].”
Opening the online marketplace: An examination of hotel pricing and travel agency on-line distribution of rooms (2014, background): “As indicated by Thanassoulis (2004), Chawla, Hartline, and Kleinberg (2007), and Chawla et al. (2012), potential customers can be classified into (mþ1) types according to their preferences for service level.”