Optimal envy-free pricing with metric substitutability

ABSTRACT

We study the envy-free pricing problem faced by a profit maximizing seller when there is metric substitutability among the items --- consumer i's value for item j is v_i -- c_i,j, and the substitution costs, {c_i,j}, form a metric. Our model is motivated from the observation that sellers often sell the same product at different prices in different locations, and rational consumers optimize the tradeoff between prices and substitution costs. While the general envy-free pricing problem is hard to approximate, the addition of metric substitutability constraints allows us to solve the problem exactly in polynomial time by reducing it to an instance of weighted independent set on a perfect graph.

When the substitution costs do not form a metric, even in cases when a (1+ε)--approximate triangle inequality holds, the problem becomes NP-hard. Our results show that triangle inequality is the exact sharp threshold for the problem of going from "tractable" to "hard".

We then turn our attention to the multi-unit demand case, where consumers request multiple copies of the item. This problem has an interesting paradoxical non-monotonicity: The optimal revenue the seller can extract can actually decrease when consumers' demands increase. We show that in this case the revenue maximization problem becomes APX-hard and give an O(log D) approximation algorithm, where D is the ratio of the largest to smallest demand. We extend these techniques to the more general case of arbitrary non-decreasing value functions, and give an O(log³ D) approximation algorithm.

REFERENCES

• 1: Aggarwal, T. Feder, R. Motwani, A. Zhu, Algorithms for Multi-Product Pricing, ICALP 2004, 72--83.
• 2: 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]
• 3: Briest, Towards Hardness of Envy-Free Pricing, ECCC, 2006.
• 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: Patrick Briest , Piotr Krysta, Buying cheap is expensive: hardness of non-parametric multi-product pricing, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.716-725, January 07-09, 2007, New Orleans, Louisiana
• 6: Shuchi Chawla , Jason D. Hartline , Robert Kleinberg, Algorithmic pricing via virtual valuations, Proceedings of the 8th ACM conference on Electronic commerce, June 11-15, 2007, San Diego, California, USA [doi>10.1145/1250910.1250946]
• 7: Ning Chen , Anna R. Karlin, Cheap labor can be expensive, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.707-715, January 07-09, 2007, New Orleans, Louisiana
• 8: Chudnovsky, N. Robertson, P. Seymour, R. Thomas, The Strong Perfect Graph Theorem, Annals of Mathematics, V.164, 51--229, 2006.
• 9: 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]
• 10: Xiaotie Deng , Christos Papadimitriou , Shmuel Safra, On the complexity of price equilibria, Journal of Computer and System Sciences, v.67 n.2, p.311-324, September 2003 [doi>10.1016/S0022-0000(03)00011-4]
• 11: R. Devanur, C. H. Papadimitriou, A. Saberi, V. V. Vazirani, Market Equilibrium via a Primal-Dual-Type Algorithm, to appear in JACM.
• 12: Grötschel, L. Lovász, A. Schrijver, The Ellipsoid Method and its Consequences in Combinatorial Optimization, Combinatorica, V.1, 169--197, 1981.
• 13: 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
• 14: Tim Roughgarden , Éva Tardos, How bad is selfish routing?, Journal of the ACM (JACM), v.49 n.2, p.236-259, March 2002 [doi>10.1145/506147.506153]
• 15: 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]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.m MISCELLANEOUS

General Terms:
Algorithms, Theory

Keywords:
algorithms, envy-free pricing