Single-minded unlimited supply pricing on sparse instances

ABSTRACT

We deal with the problem of finding profit-maximizing prices for a finite number of distinct goods, assuming that of each good an unlimited number of copies is available, or that goods can be reproduced at no cost (e.g., digital goods). Consumers specify subsets of the goods and the maximum prices they are willing to pay. In the considered single-minded case every consumer is interested in precisely one such subset. If the goods are the edges of a graph and consumers are requesting to purchase paths in this graph, then we can think of the problem as pricing computer network connections or transportation links.We start by showing weak NP-hardness of the very restricted case in which the requested subsets are nested, i.e., contained inside each other or non-intersecting, thereby resolving the previously open question whether the problem remains NP-hard when the underlying graph is simply a line. Using a reduction inspired by this result we present an approximation preserving reduction that proves APX-hardness even for very sparse instances defined on general graphs, where the number of requests per edge is bounded by a constant B and no path is longer than some constant l. On the algorithmic side we first present an O(log l + log B)-approximation algorithm that (almost) matches the previously best known approximation guarantee in the general case, but is especially well suited for sparse problem instances. Using a new upper bounding technique we then give an O(l²)-approximation, which is the first algorithm for the general problem with an approximation ratio that does not depend on B.

REFERENCES

• 1: G. Aggarwal, T. Feder, R. Motwani and A. Zhu. Algorithms for multi-product pricing. In Proc. of 31st ICALP, 2004.
• 2: 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
• 3: 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
• 4: N. Balcan and A. Blum. Approximation Algorithms for Item Pricing. Technical Report CMU-CS-05-176, 2005.
• 5: 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]
• 6: M. Bouhtou, A. Grigoriev, S. van Hoesel, A. van der Kraaij, M. Uetz and F. Spieksma. Pricing Bridges to Cross a River. Submitted. An extended abstract appeared as Pricing Network Edges to Cross a River in Proc. of 2nd WAOA, 2004.
• 7: 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]
• 8: 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]
• 9: 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
• 10: 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
• 11: 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
• 12: J. Hartline and V. Koltun. Near-Optimal Pricing in Near-Linear Time. In Proc. of WADS, 2005.
• 13: 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]
• 14: 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]
• 15: P. Rusmevichientong, B. Van Roy and P. Glynn. A Non-Parametric Approach to Multi-Product Pricing. To appear in Operations Research.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations in finite fields
      F.2.2 Nonnumerical Algorithms and Problems

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

General Terms:
Algorithms, Theory