Buying cheap is expensive: hardness of non-parametric multi-product pricing

ABSTRACT

We investigate non-parametric unit-demand pricing problems, in which we want to find revenue maximizing prices for products P based on a set of consumer profiles C. A consumer profile consists of a number of non-zero budgets for different products and possibly an additional product ranking. Once prices are fixed, each consumer chooses to buy one of the products she can afford based on some predefined selection rule. We distinguish between the min-buying, max-buying, and rank-buying models.

For the min-buying model we show that it is not approximable within O(logε |C|) for some constant ε > 0, unless NP ⊆ DTIME(n^O(loglogn(), thereby closing the gap between the known algorithmic results and previous lower bounds. We also prove inapproximability within O(ℓ^ε), ℓ being an upper bound on the number of non-zero budgets per consumer, and O(|P|^epsi;) under slightly stronger assumptions and provide matching upper bounds. Surprisingly, these hardness results hold even if a price ladder constraint, i.e., a predefined order on the prices of all products, is given.

For the max-buying model a PTAS exists if a price ladder is given. We give a matching lower bound by proving strong NP-hardness. Assuming limited product supply, we analyze a generic local search algorithm and prove that it is 2-approximate. Finally, we discuss implications for the rank-buying model.

REFERENCES

• 1: G. Aggarwal, T. Feder, R. Motwani, and A. Zhu. Algorithms for Multi-Product Pricing. In Proc. of 31st ICALP, 2004.
• 2: Gagan Aggarwal , Amos Fiat , Andrew V. Goldberg , Jason D. Hartline , Nicole Immorlica , Madhu Sudan, Derandomization of auctions, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060682]
• 3: Noga Alon , Uriel Feige , Avi Wigderson , David Zuckerman, Derandomized graph products, Computational Complexity, v.5 n.1, p.60-75, Jan. 1995 [doi>10.1007/BF01277956]
• 4: Aaron Archer , Christos Papadimitriou , Kunal Talwar , Éva Tardos, An approximate truthful mechanism for combinatorial auctions with single parameter agents, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 5: Sanjeev Arora , Carsten Lund , Rajeev Motwani , Madhu Sudan , Mario Szegedy, Proof verification and the hardness of approximation problems, Journal of the ACM (JACM), v.45 n.3, p.501-555, May 1998 [doi>10.1145/278298.278306]
• 6: Giorgio Ausiello , M. Protasi , A. Marchetti-Spaccamela , G. Gambosi , P. Crescenzi , V. Kann, Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, Springer-Verlag New York, Inc., Secaucus, NJ, 1999
• 7: Maria-Florina Balcan , Avrim Blum, Approximation algorithms and online mechanisms for item pricing, Proceedings of the 7th ACM conference on Electronic commerce, p.29-35, June 11-15, 2006, Ann Arbor, Michigan, USA [doi>10.1145/1134707.1134711]
• 8: Yair Bartal , Rica Gonen , Noam Nisan, Incentive compatible multi unit combinatorial auctions, Proceedings of the 9th conference on Theoretical aspects of rationality and knowledge, June 20-22, 2003, Univerity of Indiana, Indiana [doi>10.1145/846241.846250]
• 9: Piotr Berman , Georg Schnitger, On the complexity of approximating the independent set problem, Information and Computation, v.96 n.1, p.77-94, Jan. 1992 [doi>10.1016/0890-5401(92)90056-L]
• 10: Avrim Louis Blum , Ronald L. Rivest, Algorithms for approximate graph coloring, Massachusetts Institute of Technology, 1991
• 11: M. Bouhtou, A. Grigoriev, S. van Hoesel, A. van der Kraaij, and M. Uetz. Pricing Network Edges to Cross a River. In Proc. of 2nd WAOA, 2004.
• 12: Patrick Briest , Piotr Krysta, Single-minded unlimited supply pricing on sparse instances, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1093-1102, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109678]
• 13: Patrick Briest , Piotr Krysta , Berthold Vöcking, Approximation techniques for utilitarian mechanism design, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060597]
• 14: William J. Cook , William H. Cunningham , William R. Pulleyblank , Alexander Schrijver, Combinatorial optimization, John Wiley & Sons, Inc., New York, NY, 1998
• 15: Erik D. Demaine , Mohammad Taghi Hajiaghayi , Uriel Feige , Mohammad R. Salavatipour, Combination can be hard: approximability of the unique coverage problem, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.162-171, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109577]
• 16: Shahar Dobzinski , Michael Schapira, An improved approximation algorithm for combinatorial auctions with submodular bidders, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1064-1073, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109675]
• 17: Shahar Dobzinski , Noam Nisan , Michael Schapira, Truthful randomized mechanisms for combinatorial auctions, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132607]
• 18: Uriel Feige , Magnús M. Halldórsson , Guy Kortsarz , Aravind Srinivasan, Approximating the Domatic Number, SIAM Journal on Computing, v.32 n.1, p.172-195, 2003 [doi>10.1137/S0097539700380754]
• 19: Amos Fiat , Andrew V. Goldberg , Jason D. Hartline , Anna R. Karlin, Competitive generalized auctions, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509921]
• 20: D. Fudenberg and J. Tirole. Game Theory. MIT Press, 1991.
• 21: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 22: Paat Rusmevichientong , Benjamin Van Roy , Peter W. Glynn, A Nonparametric Approach to Multiproduct Pricing, Operations Research, v.54 n.1, p.82-98, January-February 2006 [doi>10.1287/opre.1050.0252]
• 23: Andrew V. Goldberg , Jason D. Hartline , Andrew Wright, Competitive auctions and digital goods, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.735-744, January 07-09, 2001, Washington, D.C., United States
• 24: Venkatesan Guruswami , Jason D. Hartline , Anna R. Karlin , David Kempe , Claire Kenyon , Frank McSherry, On profit-maximizing envy-free pricing, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 25: J. Hartline and V Koltun. Near-Optimal Pricing in Near-Linear Time. In Proc. of WADS, 2005.
• 26: E. Koutsoupias and C. H. Papadimitriou. Worst-Case Equilibria. In Proc. of 16th STACS, 1999.
• 27: P. Krysta. Greedy Approximation via Duality for Packing, Combinatorial Auctions and Routing. In Proc. of 30th MFCS, 2005.
• 28: Ron Lavi , Ahuva Mu'alem , Noam Nisan, Towards a Characterization of Truthful Combinatorial Auctions, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.574, October 11-14, 2003
• 29: Ron Lavi , Chaitanya Swamy, Truthful and Near-Optimal Mechanism Design via Linear Programming, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.595-604, October 23-25, 2005 [doi>10.1109/SFCS.2005.76]
• 30: Daniel Lehmann , Liaden Ita O'Callaghan , Yoav Shoham, Truth revelation in approximately efficient combinatorial auctions, Proceedings of the 1st ACM conference on Electronic commerce, p.96-102, November 03-05, 1999, Denver, Colorado, United States [doi>10.1145/336992.337016]
• 31: Noam Nisan , Amir Ronen, Algorithmic mechanism design (extended abstract), Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.129-140, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301287]
• 32: Christos Papadimitriou, Algorithms, games, and the internet, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.749-753, July 2001, Hersonissos, Greece [doi>10.1145/380752.380883]
• 33: C. H. Papadimitriou and M. Yannakakis. Optimization, Approximation and Complexity Classes. Journal of Computer and System Sciences, 43, 425--440, 1991.
• 34: P. Rusmevichientong. A Non-Parametric Approach to Multi-Product Pricing: Theory and Application. Ph.D. thesis, 2003.