Computer Science – Computer Science and Game Theory
Scientific paper
2011-06-02
Computer Science
Computer Science and Game Theory
45 pages, 1 figure
Scientific paper
We provide a Polynomial Time Approximation Scheme for the multi-dimensional unit-demand pricing problem, when the buyer's values are independent (but not necessarily identically distributed). For all epsilon>0, we obtain a (1+epsilon)-factor approximation to the optimal revenue in time polynomial, when the values are sampled from Monotone Hazard Rate (MHR) distributions, quasi-polynomial, when sampled from regular distributions, and polynomial in n^poly(log r), when sampled from general distributions supported on a set [u, r * u]. We also provide an additive PTAS for all bounded distributions. Our algorithms are based on novel extreme value theorems for MHR and regular distributions, and apply probabilistic techniques to understand the statistical properties of revenue distributions, as well as to reduce the size of the search space of the algorithm. As a byproduct of our techniques, we establish structural properties of optimal solutions. We show that, for all epsilon >0, g(1/epsilon) distinct prices suffice to obtain a (1+epsilon)-factor approximation to the optimal revenue for MHR distributions, where g(1/epsilon) is a quasi-linear function of 1/epsilon that does not depend on the number of items. Similarly, for all epsilon>0 and n>0, g(1/epsilon * log n) distinct prices suffice for regular distributions, where n is the number of items and g() is a polynomial function. Finally, in the i.i.d. MHR case, we show that, as long as the number of items is a sufficiently large function of 1/epsilon, a single price suffices to achieve a (1+epsilon)-factor approximation.
Cai Yang
Daskalakis Constantinos
No associations
LandOfFree
Extreme-Value Theorems for Optimal Multidimensional Pricing 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 Extreme-Value Theorems for Optimal Multidimensional Pricing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Extreme-Value Theorems for Optimal Multidimensional Pricing will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-222773