Computer Science – Computer Science and Game Theory
Scientific paper
2008-08-12
Computer Science
Computer Science and Game Theory
A preliminary version of this work appeared at the ACM EC'07 conference. The current version contains improved results and sim
Scientific paper
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 et al. (2005) propose this problem and give logarithmic approximations (in the number of consumers) when each consumer's values for bundles are known precisely. Subsequently several versions of the problem have been shown to have poly-logarithmic inapproximability. This problem has direct ties to the important open question of better understanding the Bayesian optimal mechanism in multi-parameter settings; however, logarithmic approximations are inadequate for this purpose. It is therefore of vital interest to consider special cases where constant approximations are possible. We consider the unit-demand variant of this problem. Here a consumer has a valuation for each different item and their value for a set of items is simply the maximum value they have for any item in the set. We assume that the preferences of the consumers are drawn from a distribution, the standard assumption in economics; furthermore, the setting of a specific set of customers with known preferences, which is employed in all prior work in algorithmic pricing, is a special case of this general problem, where there is a discrete Bayesian distribution for preferences specified by picking one consumer uniformly from the given set of consumers. 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 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.
Chawla Shuchi
Hartline Jason
Kleinberg Robert
No associations
LandOfFree
Algorithmic Pricing via Virtual Valuations does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Algorithmic Pricing via Virtual Valuations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Algorithmic Pricing via Virtual Valuations will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-202966