ABSTRACT
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.
- G. Aggarwal, T. Feder, R. Motwani, and A. Zhu. Algorithms for multi-product pricing. In Proc. of ICALP, 2004.Google ScholarCross Ref
- G. Aggarwal and J. Hartline. Knapsack auctions. In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, 2006. Google ScholarDigital Library
- M.-F. Balcan, A. Blum, J. Hartline, and Y. Mansour. Mechanism Design via Machine Learning. In Proc. of the 46th IEEE Symp. on Foundations of Computer Science, 2005. Google ScholarDigital Library
- N. Balcan and A. Blum. Approximation algorithms and online mechanisms for item pricing. In Proc. 8th ACM Conf. on Electronic Commerce, 2006. Google ScholarDigital Library
- P. Briest and P. Krysta. Buying cheap is expensive: Hardness of non-parametric multi-product pricing. In Proc. 18th ACM Symp. on Discrete Algorithms. ACM/SIAM, 2007. To appear. Google ScholarDigital Library
- J. Bulow and J. Roberts. The simple economics of optimal auctions. The Journal of Political Economy, 97:1060--90, 1989.Google ScholarCross Ref
- E. Demaine, U. Feige, M. Hajiaghayi, and M. Salavatipour. Combination can be hard: Approximability of the unique coverage problem. In Proc. 17th ACM Symp. on Discrete Algorithms, 2006. Google ScholarDigital Library
- E. Elkind. Designing and learning optimal finite support auctions. In Proc. 18th ACM Symp. on Discrete Algorithms, 2007. Google ScholarDigital Library
- V. Guruswami, J. Hartline, A. Karlin, D. Kempe, C. Kenyon, and F. McSherry. On profit-maximizing envy-free pricing. In Proc. 16th ACM Symp. on Discrete Algorithms, 2005. Google ScholarDigital Library
- J. Hartline and V. Koltun. Near-Optimal Pricing in Near-Linear Time. In Proc. of 9th Workshop on Algorithms and Data Structures. Springer-Verlag, 2005. Google ScholarDigital Library
- V. Krishna. Auction Theory. Academic Press, 2002.Google Scholar
- R. Myerson. Optimal auction design. Mathematics of Operations Research, 6:58--73, 1981.Google ScholarDigital Library
Index Terms
- Algorithmic pricing via virtual valuations
Recommendations
Envy-Free Pricing in Large Markets: Approximating Revenue and Welfare
We study the classic setting of envy-free pricing, in which a single seller chooses prices for its many items, with the goal of maximizing revenue once the items are allocated. Despite the large body of work addressing such settings, most versions of ...
Pricing commodities
How should a seller price her goods in a market where each buyer prefers a single good among his desired goods, and will buy the cheapest such good, as long as it is within his budget? We provide efficient algorithms that compute near-optimal prices for ...
Pricing Equilibria and Graphical Valuations
We study pricing equilibria for graphical valuations, whichare a class of valuations that admit a compact representation. These valuations are associated with a value graph, whose nodes correspond to items, and edges encode (pairwise) complementarities/...
Comments