article

Pricing commodities

Authors:

Robert Krauthgamer,

Atri RudraAuthors Info & Claims

Theoretical Computer Science, Volume 412, Issue 7

Pages 602 - 613

https://doi.org/10.1016/j.tcs.2009.10.002

Published: 01 February 2011 Publication History

Abstract

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 this problem, focusing on a commodity market, where the range of buyer budgets is small. We also show that our LP rounding based technique easily extends to a different scenario, in which the buyers want to buy all the desired goods, as long as they are within budget.

References

[1]

Aggarwal, G., Feder, T., Motwani, R. and Zhu, A., Algorithms for multi-product pricing. In: Lecture Notes in Computer Science, vol. 3142. Springer. pp. 72-83.

Digital Library

[2]

Alon, N. and Spencer, J.H., The Probabilistic Method. 1992. John Wiley & Sons, Inc., New York.

[3]

Balcan, M.-F. and Blum, A., Approximation algorithms and online mechanisms for item pricing. In: Proceedings of the 7th ACM conference on Electronic commerce, ACM Press. pp. 29-35.

[4]

Balcan, M.-F., Blum, A., Hartline, J.D. and Mansour, Y., Mechanism design via machine learning. In: 46th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society. pp. 605-614.

Digital Library

[5]

Nikhil Bansal, Ning Chen, Neva Cherniavsky, Atri Rudra, Baruch Schieber, Maxim Sviridenko, Dynamic pricing for impatient bidders, in: Proceedings of the Eightteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, 2007, pp. 726-735

[6]

P. Briest, P. Krysta, Single-minded unlimited supply pricing on sparse instances, in: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, 2006, pp. 1093-1102

Digital Library

[7]

P. Briest, P. Krysta, Buying cheap is expensive: Hardness of non-parametric multi-product pricing, in: Proceedings of the Eightteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, 2007

[8]

E.D. Demaine, U. Feige, M.T. Hajiaghayi, M. R. Salavatipour, Combination can be hard: Approximability of the unique coverage problem, in: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, 2006, pp. 162-171

[9]

Guruswami, V., Hartline, J.D., Karlin, A.R., Kempe, D., Kenyon, C. and McSherry, F., On profit-maximizing envy-free pricing. In: Proceedings of the 16th annual ACM-SIAM symposium on Discrete algorithms, Society for Industrial and Applied Mathematics. pp. 1164-1173.

[10]

Goldberg, A., Hartline, J., Karlin, A., Saks, M. and Wright, A., Competitive auctions. Games and Economic Behavior. v55 i2. 242-269.

[11]

Michel X. Goemans, Mathematical programming and approximation algorithms, Lecture at Udine School, Undine, Italy, 1996

[12]

Goemans, M.X. and Williamson, D.P., New 3/4-approximation algorithms for the maximum satisfiability problem. SIAM Journal on Discrete Mathematics. v7. 656-666.

[13]

R. Khandekar, J. Konemann, E. Markakis, Private communication, 2007

[14]

Luby, M. and Wigderson, A., Pairwise independence and derandomization. Foundations and Trends(R) in Theoretical Computer Science. v1 i4. 237-301.

[15]

Srinivasan, A., Approximation algorithms via randomized rounding: a survey. In: Karonski, M., Promel, H.~J. (Eds.), Series in Advanced Topics in Mathematics, Polish Scientific Publishers PWN. pp. 9-71.

[16]

Vazirani, Vijay V., Approximation Algorithms. 2001. Springer Verlag, New York, NY.

Cited By

Gamzu ISegev D(2017)A Sublogarithmic Approximation for Tollbooth Pricing on TreesMathematics of Operations Research10.1287/moor.2016.080342:2(377-388)Online publication date: 1-May-2017
https://dl.acm.org/doi/10.1287/moor.2016.0803
Lee EServedio RRubinfeld R(2015)Hardness of Graph Pricing Through Generalized Max-DicutProceedings of the forty-seventh annual ACM symposium on Theory of Computing10.1145/2746539.2746549(391-399)Online publication date: 14-Jun-2015
https://dl.acm.org/doi/10.1145/2746539.2746549
Zhang YChin FTing H(2014)Online pricing for bundles of multiple itemsJournal of Global Optimization10.1007/s10898-013-0043-458:2(377-387)Online publication date: 1-Feb-2014
https://dl.acm.org/doi/10.1007/s10898-013-0043-4
Show More Cited By

Pricing commodities
1. Theory of computation

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 ...
Equilibrium pricing with positive externalities

We study the problem of selling an item to strategic buyers in the presence of positive historical externalities, where the value of a product increases as more people buy and use it. This increase in the value of the product is the result of resolving ...
Pricing public goods for private sale
EC '13: Proceedings of the fourteenth ACM conference on Electronic commerce

We consider the pricing problem faced by a seller who assigns a price to a good that confers its benefits not only to its buyers, but also to other individuals around them. For example, a snow-blower is potentially useful not only to the household that ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Theoretical Computer Science

Theoretical Computer Science Volume 412, Issue 7

February, 2011

78 pages

ISSN:0304-3975

Issue’s Table of Contents

Copyright © Elsevier B.V. © 2009.

Publisher

Elsevier Science Publishers Ltd.

United Kingdom

Publication History

Published: 01 February 2011

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 10 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Gamzu ISegev D(2017)A Sublogarithmic Approximation for Tollbooth Pricing on TreesMathematics of Operations Research10.1287/moor.2016.080342:2(377-388)Online publication date: 1-May-2017
https://dl.acm.org/doi/10.1287/moor.2016.0803
Lee EServedio RRubinfeld R(2015)Hardness of Graph Pricing Through Generalized Max-DicutProceedings of the forty-seventh annual ACM symposium on Theory of Computing10.1145/2746539.2746549(391-399)Online publication date: 14-Jun-2015
https://dl.acm.org/doi/10.1145/2746539.2746549
Zhang YChin FTing H(2014)Online pricing for bundles of multiple itemsJournal of Global Optimization10.1007/s10898-013-0043-458:2(377-387)Online publication date: 1-Feb-2014
https://dl.acm.org/doi/10.1007/s10898-013-0043-4
Chen NEngelberg RThach Nguyen CRaghavendra PRudra ASingh G(2013)Improved Approximation Algorithms for the Spanning Star Forest ProblemAlgorithmica10.1007/s00453-011-9607-165:3(498-516)Online publication date: 1-Mar-2013
https://dl.acm.org/doi/10.1007/s00453-011-9607-1
Zhang YChin FTing H(2012)Online pricing for multi-type of itemsProceedings of the 6th international Frontiers in Algorithmics, and Proceedings of the 8th international conference on Algorithmic Aspects in Information and Management10.1007/978-3-642-29700-7_8(82-92)Online publication date: 14-May-2012
https://dl.acm.org/doi/10.1007/978-3-642-29700-7_8

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents