Cited By
View all- Alaei SChawla SMakhdoumi AMalekian A(2023)Countering Value Uncertainty via Refunds: A Mechanism Design ApproachSSRN Electronic Journal10.2139/ssrn.4561235Online publication date: 2023
Pricing ordered items
Pages 722 - 735
Abstract
We study the revenue guarantees and approximability of item pricing. Recent work shows that with n heterogeneous items, item-pricing guarantees an O(logn) approximation to the optimal revenue achievable by any (buy-many) mechanism, even when buyers have arbitrarily combinatorial valuations. However, finding good item prices is challenging – it is known that even under unit-demand valuations, it is NP-hard to find item prices that approximate the revenue of the optimal item pricing better than O(√n).
Our work provides a more fine-grained analysis of the revenue guarantees and computational complexity in terms of the number of item “categories” which may be significantly fewer than n. We assume the items are partitioned in k categories so that items within a category are totally-ordered and a buyer’s value for a bundle depends only on the best item contained from every category.
We show that item-pricing guarantees an O(logk) approximation to the optimal (buy-many) revenue and provide a PTAS for computing the optimal item-pricing when k is constant. We also provide a matching lower bound showing that the problem is (strongly) NP-hard even when k=1. Our results naturally extend to the case where items are only partially ordered, in which case the revenue guarantees and computational complexity depend on the width of the partial ordering, i.e. the largest set for which no two items are comparable.
References
[1]
Moshe Babaioff, Nicole Immorlica, Brendan Lucier, and S Matthew Weinberg. 2014. A simple and approximately optimal mechanism for an additive buyer. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science. 21–30.
[2]
Maria-Florina Balcan and Avrim Blum. 2006. Approximation algorithms and online mechanisms for item pricing. In Proceedings of the 7th ACM Conference on Electronic Commerce. 29–35.
[3]
Patrick Briest. 2008. Uniform budgets and the envy-free pricing problem. In International Colloquium on Automata, Languages, and Programming. 808–819.
[4]
Patrick Briest, Shuchi Chawla, Robert Kleinberg, and S Matthew Weinberg. 2015. Pricing lotteries. Journal of Economic Theory, 156 (2015), 144–174.
[5]
Patrick Briest and Piotr Krysta. 2006. Single-minded unlimited supply pricing on sparse instances. In Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm. 1093–1102.
[6]
Yang Cai and Constantinos Daskalakis. 2011. Extreme-value theorems for optimal multidimensional pricing. In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science. 522–531.
[7]
Yang Cai and Mingfei Zhao. 2017. Simple mechanisms for subadditive buyers via duality. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. 170–183.
[8]
Parinya Chalermsook, Julia Chuzhoy, Sampath Kannan, and Sanjeev Khanna. 2012. Improved hardness results for profit maximization pricing problems with unlimited supply. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Springer, 73–84.
[9]
Parinya Chalermsook, Bundit Laekhanukit, and Danupon Nanongkai. 2013. Graph products revisited: Tight approximation hardness of induced matching, poset dimension and more. In Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms. 1557–1576.
[10]
Parinya Chalermsook, Bundit Laekhanukit, and Danupon Nanongkai. 2013. Independent set, induced matching, and pricing: Connections and tight (subexponential time) approximation hardnesses. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science. 370–379.
[11]
Shuchi Chawla, Jason D Hartline, and Robert Kleinberg. 2007. Algorithmic pricing via virtual valuations. In Proceedings of the 8th ACM Conference on Electronic Commerce. 243–251.
[12]
Shuchi Chawla, Jason D Hartline, David L Malec, and Balasubramanian Sivan. 2010. Multi-parameter mechanism design and sequential posted pricing. In Proceedings of the forty-second ACM symposium on Theory of computing. 311–320.
[13]
Shuchi Chawla, David Malec, and Balasubramanian Sivan. 2015. The power of randomness in bayesian optimal mechanism design. Games and Economic Behavior, 91 (2015), 297–317.
[14]
Shuchi Chawla and J Benjamin Miller. 2016. Mechanism design for subadditive agents via an ex ante relaxation. In Proceedings of the 2016 ACM Conference on Economics and Computation. 579–596.
[15]
Shuchi Chawla, Yifeng Teng, and Christos Tzamos. 2019. Buy-Many Mechanisms are Not Much Better than Item Pricing. In Proceedings of the 2019 ACM Conference on Economics and Computation. 237–238.
[16]
Shuchi Chawla, Yifeng Teng, and Christos Tzamos. 2020. Menu-size complexity and revenue continuity of buy-many mechanisms. In Proceedings of the 21st ACM Conference on Economics and Computation. 475–476.
[17]
Xi Chen, Ilias Diakonikolas, Anthi Orfanou, Dimitris Paparas, Xiaorui Sun, and Mihalis Yannakakis. 2015. On the complexity of optimal lottery pricing and randomized mechanisms. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science. 1464–1479.
[18]
Xi Chen, Ilias Diakonikolas, Dimitris Paparas, Xiaorui Sun, and Mihalis Yannakakis. 2014. The complexity of optimal multidimensional pricing. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms. 1319–1328.
[19]
Nikhil R Devanur, Kira Goldner, Raghuvansh R Saxena, Ariel Schvartzman, and S Matthew Weinberg. 2020. Optimal mechanism design for single-minded agents. In Proceedings of the 21st ACM Conference on Economics and Computation. 193–256.
[20]
Nikhil R Devanur and S Matthew Weinberg. 2017. The optimal mechanism for selling to a budget constrained buyer: The general case. In Proceedings of the 2017 ACM Conference on Economics and Computation. 39–40.
[21]
Paul Dütting, Thomas Kesselheim, and Brendan Lucier. 2020. An O(log log m) Prophet Inequality for Subadditive Combinatorial Auctions. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS). 306–317. https://doi.org/10.1109/FOCS46700.2020.00037
[22]
Khaled Elbassioni, Rajiv Raman, Saurabh Ray, and René Sitters. 2009. On profit-maximizing pricing for the highway and tollbooth problems. In International Symposium on Algorithmic Game Theory. 275–286.
[23]
Amos Fiat, Kira Goldner, Anna R Karlin, and Elias Koutsoupias. 2016. The FedEx Problem. In Proceedings of the 2016 ACM Conference on Economics and Computation. 21–22.
[24]
Iftah Gamzu and Danny Segev. 2010. A sublogarithmic approximation for highway and tollbooth pricing. In International Colloquium on Automata, Languages, and Programming. 582–593.
[25]
Yannai A Gonczarowski and S Matthew Weinberg. 2021. The sample complexity of up-to-ε multi-dimensional revenue maximization. Journal of the ACM (JACM), 68, 3 (2021), 1–28.
[26]
Fabrizio Grandoni and Thomas Rothvoß. 2016. Pricing on paths: A ptas for the highway problem. SIAM J. Comput., 45, 2 (2016), 216–231.
[27]
Venkatesan Guruswami, Jason D Hartline, Anna R Karlin, David Kempe, Claire Kenyon, and Frank McSherry. 2005. On profit-maximizing envy-free pricing. In SODA. 5, 1164–1173.
[28]
Sergiu Hart and Noam Nisan. 2013. The menu-size complexity of auctions. Center for the Study of Rationality.
[29]
Rohit Khandekar, Tracy Kimbrel, Konstantin Makarychev, and Maxim Sviridenko. 2009. On hardness of pricing items for single-minded bidders. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Springer, 202–216.
[30]
Pravesh Kothari, Sahil Singla, Divyarthi Mohan, Ariel Schvartzman, and S Matthew Weinberg. 2019. Approximation Schemes for a Unit-Demand Buyer with Independent Items via Symmetries. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS). 220–232.
[31]
Euiwoong Lee. 2015. Hardness of graph pricing through generalized max-dicut. In Proceedings of the forty-seventh annual ACM symposium on Theory of Computing. 391–399.
[32]
Xinye Li and Andrew Chi-Chih Yao. 2013. On revenue maximization for selling multiple independently distributed items. Proceedings of the National Academy of Sciences, 110, 28 (2013), 11232–11237.
[33]
Jean-Charles Rochet. 1985. The taxation principle and multi-time Hamilton-Jacobi equations. Journal of Mathematical Economics, 14, 2 (1985), 113–128.
[34]
Aviad Rubinstein and S Matthew Weinberg. 2018. Simple mechanisms for a subadditive buyer and applications to revenue monotonicity. ACM Transactions on Economics and Computation (TEAC), 6, 3-4 (2018), 1–25.
[35]
Raghuvansh R Saxena, Ariel Schvartzman, and S Matthew Weinberg. 2018. The menu complexity of “one-and-a-half-dimensional” mechanism design. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. 2026–2035.
[36]
Andrew Chi-Chih Yao. 2014. An n-to-1 bidder reduction for multi-item auctions and its applications. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms. 92–109.
Recommendations
Price Doubling and Item Halving: Robust Revenue Guarantees for Item Pricing
EC '17: Proceedings of the 2017 ACM Conference on Economics and ComputationWe study approximation algorithms for revenue maximization based on static item pricing, where a seller chooses prices for various goods in the market, and then the buyers purchase utility-maximizing bundles at these given prices. We formulate two ...
Item pricing for revenue maximization
In this note we report recent results on item pricing for revenue maximization in the presence of buyers with complex, unknown preferences. We focus on two important classes of settings: buyers with general valuations for the case of items in unlimited ...
Dynamic and Non-uniform Pricing Strategies for Revenue Maximization
FOCS '09: Proceedings of the 2009 50th Annual IEEE Symposium on Foundations of Computer ScienceWe study the Item Pricing problem for revenue maximization in the limited supply setting, where a single seller with $n$ distinct items caters to $m$ buyers with unknown subadditive valuation functions who arrive in a sequence. The seller sets the ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
June 2022
1698 pages
Copyright © 2022 Owner/Author.
This work is licensed under a Creative Commons Attribution 4.0 International License.
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 10 June 2022
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
STOC '22
Sponsor:
Acceptance Rates
Overall Acceptance Rate 1,469 of 4,586 submissions, 32%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 414Total Downloads
- Downloads (Last 12 months)108
- Downloads (Last 6 weeks)19
Reflects downloads up to 19 Nov 2024
Other Metrics
Citations
Cited By
View all- Alaei SChawla SMakhdoumi AMalekian A(2023)Countering Value Uncertainty via Refunds: A Mechanism Design ApproachSSRN Electronic Journal10.2139/ssrn.4561235Online publication date: 2023
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in