Elliot Anshelevich
Abstract
We study the classic setting of envy-free pricing, in which a single seller chooses prices for its many items, with the goal of maximizing revenue once the items are allocated. Despite the large body of work addressing such settings, most versions of this problem have resisted good approximation factors for maximizing revenue; this is true even for the classic unit-demand case. In this article, we study envy-free pricing with unit-demand buyers, but unlike previous work we focus on large markets: ones in which the demand of each buyer is infinitesimally small compared to the size of the overall market. We assume that the buyer valuations for the items they desire have a nice (although reasonable) structure, that is, that the aggregate buyer demand has a monotone hazard rate and that the values of every buyer type come from the same support.
For such large markets, our main contribution is a 1.88-approximation algorithm for maximizing revenue, showing that good pricing schemes can be computed when the number of buyers is large. We also give a (e,2)-bicriteria algorithm that simultaneously approximates both maximum revenue and welfare, thus showing that it is possible to obtain both good revenue and welfare at the same time. We further generalize our results by relaxing some of our assumptions and quantify the necessary tradeoffs between revenue and welfare in our setting. Our results are the first known approximations for large markets and crucially rely on new lower bounds, which we prove for the revenue-maximizing prices.
Supplemental Material
Available for Download
Supplemental movie, appendix, image and software files for, Envy-Free Pricing in Large Markets: Approximating Revenue and Welfare
- Rabah Amir. 1996. Cournot oligopoly and the theory of supermodular games. Games Econ. Behav. 15, 2 (1996), 132--148. Google Scholar
Cross Ref
- Elliot Anshelevich, Koushik Kar, and Shreyas Sekar. 2015. Envy-free pricing in large markets: Approximating revenue and welfare. In Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP’15).Google ScholarCross Ref
- Elliot Anshelevich, Koushik Kar, and Shreyas Sekar. 2016. Pricing to maximize revenue and welfare simultaneously in large markets. In Proceedings of the 12th International Conference on Web and Internet Economics (WINE’16). Google ScholarDigital Library
- Elliot Anshelevich and Shreyas Sekar. 2015. Price competition in networked markets: How do monopolies impact social welfare? In Proceedings of the 11th International Conference on Web and Internet Economics (WINE’15). 16--30.Google ScholarDigital Library
- Eduardo M. Azevedo, E. Glen Weyl, and Alexander White. 2013. Walrasian equilibrium in large, quasilinear markets. Theoret. Econ. 8, 2 (2013), 281--290. Google ScholarCross Ref
- Mark Bagnoli and Ted Bergstrom. 2005. Log-concave probability and its applications. Econ. Theory 26, 2 (2005), 445--469. Google ScholarCross Ref
- Tim Baldenius and Stefan Reichelstein. 2000. Comparative statics of monopoly pricing. Econ. Theory 16, 2 (2000), 465--469.Google Scholar
- Nikhil Bansal, Ning Chen, Neva Cherniavsky, Atri Rudra, Baruch Schieber, and Maxim Sviridenko. 2010. Dynamic pricing for impatient bidders. ACM Trans. Algor. 6, 2 (2010). DOI:http://dx.doi.org/10.1145/1721837.1721851 Google ScholarDigital Library
- Paul Belleflamme and Martin Peitz. 2015. Industrial Organization: Markets and Strategies. Cambridge University Press.Google ScholarCross Ref
- Patrick Briest and Piotr Krysta. 2011. Buying cheap is expensive: Approximability of combinatorial pricing problems. SIAM J. Comput. 40, 6 (2011), 1554--1586. DOI:http://dx.doi.org/10.1137/090752353 Google ScholarDigital Library
- Jeremy I. Bulow and Paul Pfleiderer. 1983. A note on the effect of cost changes on prices. J. Polit. Econ. (1983), 182--185. Google ScholarCross Ref
- Parinya Chalermsook, Julia Chuzhoy, Sampath Kannan, and Sanjeev Khanna. 2012. Improved hardness results for profit maximization pricing problems with unlimited supply. In Proceedings of the International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX’12). Google ScholarCross Ref
- Shuchi Chawla, Jason D. Hartline, and Robert D. Kleinberg. 2007. Algorithmic pricing via virtual valuations. In Proceedings of the 8th ACM Conference on Electronic Commerce (EC’07). 243--251. Google ScholarDigital Library
- Shuchi Chawla, Jason D. Hartline, David L. Malec, and Balasubramanian Sivan. 2010. Multi-parameter mechanism design and sequential posted pricing. In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC’10). 311--320. Google ScholarDigital Library
- Ning Chen and Xiaotie Deng. 2014. Envy-free pricing in multi-item markets. ACM Trans. Algor. 10, 2 (2014), 7. DOI:http://dx.doi.org/10.1145/2567923 Google ScholarDigital Library
- Ning Chen, Xiaotie Deng, Paul W. Goldberg, and Jinshan Zhang. 2014. On revenue maximization with sharp multi-unit demands. J. Combinat. Optim. (2014), 1--32.Google Scholar
- Ning Chen, Arpita Ghosh, and Sergei Vassilvitskii. 2011. Optimal envy-free pricing with metric substitutability. SIAM J. Comput. 40, 3 (2011), 623--645. DOI:http://dx.doi.org/10.1137/080740970 Google ScholarDigital Library
- Ning Chen and Atri Rudra. 2008. Walrasian equilibrium: Hardness, approximations and tractable instances. Algorithmica 52, 1 (2008), 44--64. Google ScholarDigital Library
- Maurice Cheung and Chaitanya Swamy. 2008. Approximation algorithms for single-minded envy-free profit-maximization problems with limited supply. In Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS’08). 35--44. Google ScholarDigital Library
- Gabrielle Demange, David Gale, and Marilda Sotomayor. 1986. Multi-item auctions. J. Polit. Econ. (1986), 863--872. Google ScholarCross Ref
- Michal Feldman, Amos Fiat, Stefano Leonardi, and Piotr Sankowski. 2012. Revenue maximizing envy-free multi-unit auctions with budgets. In Proceedings of the 13th ACM Conference on Electronic Commerce (EC’12). 532--549. Google ScholarDigital Library
- Michal Feldman, Nick Gravin, and Brendan Lucier. 2015. Combinatorial auctions via posted prices. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’15). 123--135. Google ScholarCross Ref
- Michal Feldman, Nick Gravin, and Brendan Lucier. 2016. Combinatorial walrasian equilibrium. SIAM J. Comput. 45, 1 (2016), 29--48. Google ScholarCross Ref
- Venkatesan Guruswami, Jason D. Hartline, Anna R. Karlin, David Kempe, Claire Kenyon, and Frank McSherry. 2005. On profit-maximizing envy-free pricing. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’05). 1164--1173.Google ScholarDigital Library
- Dorit S. Hochbaum and J. George Shanthikumar. 1990. Convex separable optimization is not much harder than linear optimization. J. ACM 37, 4 (1990), 843--862. Google ScholarDigital Library
- Sungjin Im, Pinyan Lu, and Yayun Wang. 2012. Envy-free pricing with general supply constraints for unit demand consumers. J. Comput. Sci. Technol. 27, 4 (2012), 702--709. DOI:http://dx.doi.org/10.1007/s11390-012-1256-6 Google ScholarCross Ref
- Tian-Liang Liu, Jian Chen, and Hai-Jun Huang. 2011. Existence and efficiency of oligopoly equilibrium under toll and capacity competition. Transport. Res. Part E: Logist. Transport. Rev. 47, 6 (2011), 908--919. Google ScholarCross Ref
- Brendan Lucier, Renato Paes Leme, and Éva Tardos. 2012. On revenue in the generalized second price auction. In Proceedings of the 21st World Wide Web Conference (WWW’12). 361--370.Google ScholarDigital Library
- Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V. Vazirani. 2007. Algorithmic Game Theory. Vol. 1. Cambridge University Press Cambridge. Google ScholarCross Ref
- Wayes Tushar, Walid Saad, H. Vincent Poor, and David B. Smith. 2012. Economics of electric vehicle charging: A game theoretic approach. IEEE Trans. Smart Grid 3, 4 (2012), 1767--1778. Google ScholarCross Ref
Index Terms
- Envy-Free Pricing in Large Markets: Approximating Revenue and Welfare
Recommendations
Envy-free pricing in multi-item markets
In this article, we study revenue maximizing envy-free pricing in multi-item markets: There are m indivisible items with unit supply each and n potential buyers where each buyer is interested in acquiring one item. The goal is to determine allocations (...
Walrasian pricing in multi-unit auctions
AbstractMulti-unit auctions are a paradigmatic model of resource allocation, where a seller brings multiple units of a good to a set of buyers equipped with monetary budgets. It is well known that Walrasian equilibria do not always exist in ...
Highlights- We consider multi-unit auctions with budgets and design a best possible envy-free and prior-free mechanism.
Revenue maximizing envy-free multi-unit auctions with budgets
EC '12: Proceedings of the 13th ACM Conference on Electronic CommerceWe study envy-free (EF) mechanisms for multi-unit auctions with budgeted agents that approximately maximize revenue. In an EF auction, prices are set so that every bidder receives a bundle that maximizes her utility amongst all bundles; We show that the ...
Comments