On profit-maximizing envy-free pricing

ABSTRACT

We study the problem of pricing items for sale to consumers so as to maximize the seller's revenue. We assume that for each consumer, we know the maximum amount he would be willing to pay for each bundle of items, and want to find pricings of the items with corresponding allocations that maximize seller profit and at the same time are envy-free, which is a natural fairness criterion requiring that consumers are maximally happy with the outcome they receive given the pricing. We study this problem for two important classes of inputs: unit demand consumers, who want to buy at most one item from among a selection they are interested in, and single-minded consumers, who want to buy one particular subset, but only if they can afford it.We show that computing envy-free prices to maximize the seller's revenue is APX-hard in both of these cases, and give a logarithmic approximation algorithm for them. For several interesting special cases, we derive polynomial-time algorithms. Furthermore, we investigate some connections with the corresponding mechanism design problem, in which the consumer's preferences are private values: for this case, we give a log-competitive truthful mechanism.

REFERENCES

• 1: G. Aggarwal, T. Feder, R. Motwani, and A. Zhu. Algorithms for multi-product pricing. In Proc. of ICALP, 2004.
• 2: Paola Alimonti , Viggo Kann, Hardness of Approximating Problems on Cubic Graphs, Proceedings of the Third Italian Conference on Algorithms and Complexity, p.288-298, March 12-14, 1997
• 3: 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
• 4: Aaron Archer , Éva Tardos, Frugal path mechanisms, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.991-999, January 06-08, 2002, San Francisco, California
• 5: Avrim Blum , Vijay Kumar , Atri Rudra , Felix Wu, Online learning in online auctions, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 6: Avrim Blum , Tuomas Sandholm , Martin Zinkevich, Online algorithms for market clearing, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.971-980, January 06-08, 2002, San Francisco, California
• 7: J. Bulow and J. Roberts. The simple economics of optimal auctions. The Journal of Political Economy, 97:1060--90, 1989.
• 8: E. H. Clarke. Multipart pricing of public goods. Public Choice, 11:17--33, 1971.
• 9: Xiaotie Deng , Christos Papadimitriou , Shmuel Safra, On the complexity of equilibria, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509920]
• 10: Nikhil R. Devanur , Christos H. Papadimitriou , Amin Saberi , Vijay V. Vazirani, Market Equilibrium via a Primal-Dual-Type Algorithm, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.389-395, November 16-19, 2002
• 11: 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]
• 12: Andrew V. Goldberg , Jason D. Hartline, Competitive Auctions for Multiple Digital Goods, Proceedings of the 9th Annual European Symposium on Algorithms, p.416-427, August 28-31, 2001
• 13: 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
• 14: T. Groves. Incentives in teams. Econometrica, 41:617--631, 1973.
• 15: F. Gul and E. Stacchetti. Walrasian equilibrium with gross substitutes. Journal of Economic Theory, 87:95--124, 1999.
• 16: A. Hoffman and J. Kruskal. Integral boundary points of convex polyhedra. In H. Kuhn and A. Tucker, editors, Linear Inequalities and Related Systems. pages 223--246. Princeton University Press, 1956.
• 17: T. Koopmans and M. Beckmann. Assignment problems and the location of economic activities. Econometrica, 25:53--76, 1957.
• 18: 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
• 19: 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]
• 20: H. Leonard. Elicitation of honest preferences for the assignment of individuals to positions. Journal of Political Economy, 91:1--36, 1983.
• 21: R. Myerson. Optimal auction design. Mathematics of Operations Research, 6:58--73, 1981.
• 22: C. Papadimitriou and K. Steiglitz. Combinatorial Optimization. Dover, 1982.
• 23: W. Vickrey. Counterspeculation, auctions, and competitive sealed tenders. J. of Finance, 16:8--37, 1961.
• 24: L. Walras. Elements of Pure Economics. Allen and Unwin, 1954.