Pricing of partially compatible products

ABSTRACT

In this paper, we examine a duopolistic market where the two firms compete to sell a system of components. Components are digital (firms haveunlimited supply at no marginal cost), and customers are homogeneous in their component preferences. Each customer will assemble a utility maximizing system by purchasing each necessary component from one of the two firms. While components from the same firm are always compatible, pairwise compatibility of components from rival firms may vary; in addition to utility due to the quality of the system purchased, customers have negative utility for purchasing incompatible parts. We investigate algorithms and hardness results for profit-maximizing decisions of the firms with regards to their price-setting, component value-enhancing and compatibility-enabling strategies. The users' behavior can be modeled as a minimum cut computation, and the company's strategies require addressing novel and interesting questions about graph cuts and flows. We develop a polynomial-time algorithm for finding profit-maximizing prices if the qualities and compatibilities are fixed. On the other hand, we show that finding profit-maximizing quality improvements is equivalent to the Maximum Size Bounded Capacity Cut problem, and thus NP-complete. Finally, for the problem of improving compatibilities to maximize the price, we give polynomial approximation hardness results even in very restricted cases, but show that if all components have uniform prices, and quality differences are small, then an approximation can be found in polynomial time.

REFERENCES

• 1: G. Aggarwal, T. Feder, R. Motwani, and A. Zhu. Algorithms for multi-product pricing. In Proc. 31st Intl. Colloq. on Automata, Languages and Programming, 2004.
• 2: Ravindra K. Ahuja , James B. Orlin, Inverse Optimization, Operations Research, v.49 n.5, p.771-783, September 2001 [doi>10.1287/opre.49.5.771.10607]
• 3: A. Archer , É. Tardos, Truthful Mechanisms for One-Parameter Agents, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.482, October 14-17, 2001
• 4: 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]
• 5: Chandra Chekuri , Sanjeev Khanna , Joseph Naor , Leonid Zosin, Approximation algorithms for the metric labeling problem via a new linear programming formulation, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.109-118, January 07-09, 2001, Washington, D.C., United States
• 6: N. Economides. Desirability of compatibility in the absence of network externalities. American Economic Review, 79:1165--1181, 1989.
• 7: J. Farrell and G. Saloner. Standardization, compatibility, and innovation. Rand Journal of Economics, 16:70--83, 1985.
• 8: J. Farrell and G. Saloner. Converters, compatibility, and control of interfaces. Journal of Industrial Economics, 40:9--36, 1992.
• 9: Uriel Feige , Robert Krauthgamer, A Polylogarithmic Approximation of the Minimum Bisection, SIAM Journal on Computing, v.31 n.4, p.1090-1118, 2002 [doi>10.1137/S0097539701387660]
• 10: 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]
• 11: 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
• 12: 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
• 13: O. Hanseth. Information Technology as Infrastructure. PhD thesis, Gothenburg University, 1996.
• 14: J. Håstad. Clique is hard to approximate within Acta Mathematica, 182:105--142, 1999.
• 15: A. Hayrapetyan, D. Kempe, M. Pál, and Z. Svitkina. Unbalanced graph cuts. In Proc. 13th European Symp. on Algorithms, 2005.
• 16: Nicole Immorlica , David Karger , Evdokia Nikolova , Rahul Sami, First-price path auctions, Proceedings of the 6th ACM conference on Electronic commerce, p.203-212, June 05-08, 2005, Vancouver, BC, Canada [doi>10.1145/1064009.1064031]
• 17: Anna R. Karlin , David Kempe , Tami Tamir, Beyond VCG: Frugality of Truthful Mechanisms, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.615-626, October 23-25, 2005 [doi>10.1109/SFCS.2005.25]
• 18: M. Katz and C. Shapiro. Network externalities, competition, and compatibility. American Economic Review, 73:424--440, 1985.
• 19: Jon Kleinberg , Eva Tardos, Approximation Algorithms for Classification Problems with Pairwise Relationships: Metric Labeling and Markov Random Fields, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.14, October 17-18, 1999
• 20: P. Klemperer. Auction theory: A guide to the literature. Journal of Economic Surveys, 13:227--286, 1999.
• 21: 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
• 22: C. Matutes and P. Regibeau. "Mix and Match": Product compatibility without network externalities. The RAND Journal of Economics, 19:221--234, 1988.
• 23: C. Matutes and P. Regibeau. Compatibility and bundling of complementary goods in a duopoly. The Journal of Industrical Economics, 40:37--54, 1992.
• 24: Z. Svitkina and E. Tardos. Min-max multiway cut. In Proc. 7th Intl. Workshop on Approximation Algorithms for Combinatorial Optimization Problems, 2004.
• 25: Kunal Talwar, The Price of Truth: Frugality in Truthful Mechanisms, Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science, p.608-619, February 27-March 01, 2003
• 26: J. Zhang and M. Cai. Inverse problem of minimum cuts. ZOR Mathematical Methods of Operations Research, 48:51--88, 1998.

INDEX TERMS

Primary Classification:
  K. Computing Milieux
  K.4 COMPUTERS AND SOCIETY
      K.4.4 Electronic Commerce

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms, Economics, Theory

Keywords:
compatibility, cut, duopoly, graph, pricing