{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:28:56Z","timestamp":1787340536242,"version":"build-2736575974"},"reference-count":27,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2013,1]]},"abstract":"<jats:p>We consider the item pricing problem for revenue maximization, where a single seller with multiple distinct items caters to multiple buyers with unknown subadditive valuation functions who arrive in a sequence. The seller sets the prices on individual items, and we design randomized pricing strategies to maximize expected revenue. We consider dynamic uniform strategies, which can change the price upon the arrival of each buyer but the price on all unsold items is the same at all times, and static nonuniform strategies, which can assign different prices to different items but can never change it after setting it initially. We design pricing strategies that guarantee poly-logarithmic (in number of items) approximation to maximum possible social welfare, which is an upper bound on revenue. We also show that any static uniform pricing strategy cannot yield such approximation, thus highlighting a large gap between the powers of dynamic and static pricing. Finally, our pricing strategies imply poly-logarithmic approximation for revenue-optimal incentive compatible mechanisms, in multiparameter combinatorial auctions with subaddititve buyer valuations, which is the best known guarantee given by efficient mechanisms for both prior-free and Bayesian settings.<\/jats:p>","DOI":"10.1137\/100787799","type":"journal-article","created":{"date-parts":[[2013,12,17]],"date-time":"2013-12-17T11:45:59Z","timestamp":1387280759000},"page":"2424-2451","source":"Crossref","is-referenced-by-count":11,"title":["Dynamic and Nonuniform Pricing Strategies for Revenue Maximization"],"prefix":"10.1137","volume":"42","author":[{"given":"Tanmoy","family":"Chakraborty","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zhiyi","family":"Huang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sanjeev","family":"Khanna","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2013,12,17]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","unstructured":"G. Aggarwal, T. Feder, R. Motwani, and A. Zhu,\n                      Algorithms for multi-product pricing\n                      , in Proceedings of the 31st International Colloquium on Automata, Languages, and Programming, 2004, pp. 72-83.","DOI":"10.1007\/978-3-540-27836-8_9"},{"key":"atypb2","unstructured":"M. Babaioff, L. Blumrosen, S. Dughmi, and Y. Singer,\n                      Posting prices with unknown distributions\n                      , in Proceedings of the International Conference on Supercomputing, 2011."},{"key":"atypb3","doi-asserted-by":"crossref","unstructured":"M.F. Balcan, A. Blum, J. D. Hartline, and Y. Mansour,\n                      Mechanism design via machine learning\n                      , in Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, 2005, pp. 605-614.","DOI":"10.1109\/SFCS.2005.50"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1145\/1386790.1386802"},{"key":"atypb5","first-page":"29","author":"Balcan M.-F.","year":"2006","journal-title":"Proceedings of the ACM Conference on Electronic Commerce"},{"key":"atypb6","doi-asserted-by":"crossref","unstructured":"S. Bhattacharya, G. Goel, S. Gollapudi, and K. Munagala,\n                      Budget constrained auctions with heterogeneous items\n                      , in Proceedings of the 42nd ACM Symposium on the Theory of Computing, 2010, pp. 379-388.","DOI":"10.1145\/1806689.1806743"},{"key":"atypb7","doi-asserted-by":"crossref","unstructured":"L. Blumrosen and N. Nisan,\n                      Combinatorial auctions\n                      , in Algorithmic Game Theory, N. Nisan, T. Roughgarden, E. Tardos, and V. Vazirani, eds., Cambridge University Press, Cambridge, UK, 2007.","DOI":"10.1017\/CBO9780511800481.013"},{"key":"atypb8","first-page":"133","author":"Briest P.","year":"2008","journal-title":"Proceedings of the Symposium on Theoretical Aspects of Computer Science"},{"key":"atypb9","doi-asserted-by":"crossref","unstructured":"P. Briest and P. Krysta,\n                      Single-minded unlimited supply pricing on sparse instances\n                      , in Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, 2006, pp. 1093-1102.","DOI":"10.1145\/1109557.1109678"},{"key":"atypb10","doi-asserted-by":"crossref","unstructured":"S. Chawla, J. D. Hartline, D. L. Malec, and B. Sivan,\n                      Multi-parameter mechanism design and sequential posted pricing\n                      , in Proceedings of the 42nd ACM Symposium on the Theory of Computing, 2010, pp. 311-320.","DOI":"10.1145\/1806689.1806733"},{"key":"atypb11","doi-asserted-by":"crossref","unstructured":"P. Cramton, Y. Shoham, and R. Steinberg,\n                      Combinatorial Auctions\n                      , MIT Press, Cambridge, MA, 2005.","DOI":"10.7551\/mitpress\/9780262033428.001.0001"},{"key":"atypb12","doi-asserted-by":"crossref","unstructured":"E. D. Demaine, M. T. Hajiaghayi, U. Feige, and M. R. Salavatipour,\n                      Combination can be hard: Approximability of the unique coverage problem\n                      , in Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, 2006, pp. 162-171.","DOI":"10.1145\/1109557.1109577"},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"S. Dobzinski, N. Nisan, and M. Schapira,\n                      Truthful randomized mechanisms for combinatorial auctions\n                      , in Proceedings of the 38th ACM Symposium onf the Theory of Computing, 2006, pp. 644-652.","DOI":"10.1145\/1132516.1132607"},{"key":"atypb14","first-page":"89","author":"Dobzinski S.","year":"2007","journal-title":"APPROX"},{"key":"atypb15","unstructured":"S. Dobzinski,\n                      private communication\n                      , Cornell University, 2010."},{"key":"atypb16","doi-asserted-by":"crossref","unstructured":"U. Feige,\n                      On maximizing welfare when utility functions are subadditive\n                      , in Proceedings of the 38th ACM Symposium on the Theory of Computing, 2006, pp. 41-50.","DOI":"10.1145\/1132516.1132523"},{"key":"atypb17","doi-asserted-by":"crossref","unstructured":"A. Fiat, A. V. Goldberg, J. D. Hartline, and A. R. Karlin,\n                      Competitive generalized auctions\n                      , in Proceedings of the 34th ACM Symposium onf the Theory of Computing, 2002, pp. 72-81.","DOI":"10.1145\/509907.509921"},{"key":"atypb18","unstructured":"A. V. Goldberg, J. D. Hartline, and A. Wright,\n                      Competitive auctions and digital goods\n                      , in Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, 2001, pp. 735-744."},{"key":"atypb19","unstructured":"V. Guruswami, J. D. Hartline, A. R. Karlin, D. Kempe, C. Kenyon, and F. McSherry,\n                      On profit-maximizing envy-free pricing\n                      , in Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, 2005, pp. 1164-1173."},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2006.02.003"},{"key":"atypb21","doi-asserted-by":"crossref","unstructured":"J. Hartline and A. Karlin,\n                      Profit maximization in mechanism design\n                      , in Algorithmic Game Theory, N. Nisan, T. Roughgarden, E. Tardos, and V. Vazirani, eds., Cambridge University Press, Cambridge, UK, 2007.","DOI":"10.1017\/CBO9780511800481.015"},{"key":"atypb22","unstructured":"J. Hartline,\n                      private communication\n                      , Northwestern University, 2010."},{"key":"atypb23","doi-asserted-by":"crossref","unstructured":"R. Lavi and C. Swamy,\n                      Truthful and near-optimal mechanism design via linear programming\n                      , in Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, 2005, pp. 595-604.","DOI":"10.1109\/SFCS.2005.76"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2005.02.006"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1145\/585265.585266"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1287\/moor.6.1.58"},{"key":"atypb27","doi-asserted-by":"crossref","unstructured":"K. Talluri and G. van Ryzin,\n                      The Theory and Practice of Revenue Management\n                      , Kluwer, Dordrecht, The Netherlands, 2004.","DOI":"10.1007\/b139000"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/100787799","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:38:37Z","timestamp":1787337517000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/100787799"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,1]]},"references-count":27,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2013,1]]}},"alternative-id":["10.1137\/100787799"],"URL":"https:\/\/doi.org\/10.1137\/100787799","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,1]]}}}