Envy-free pricing in large markets: approximating revenue and welfare
From MaRDI portal
Publication:3448773
DOI10.1007/978-3-662-47672-7_5zbMATH Open1440.91020arXiv1503.00340OpenAlexW2752469958MaRDI QIDQ3448773FDOQ3448773
Authors: Elliot Anshelevich, Koushik Kar, Shreyas Sekar 
Publication date: 27 October 2015
Published in: Automata, Languages, and Programming (Search for Journal in Brave)
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 paper 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, i.e., 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.
Full work available at URL: https://arxiv.org/abs/1503.00340
Recommendations
Cites Work
- On revenue maximization with sharp multi-unit demands
- On profit-maximizing envy-free pricing
- Optimal envy-free pricing with metric substitutability
- Envy-free pricing in multi-item markets
- Log-concave probability and its applications
- Multi-parameter mechanism design and sequential posted pricing
- Improved Hardness Results for Profit Maximization Pricing Problems with Unlimited Supply
- Walrasian equilibrium in large, quasilinear markets
- Walrasian equilibrium: Hardness, approximations and tractable instances
- Combinatorial Auctions via Posted Prices
- Combinatorial walrasian equilibrium
- Envy-free pricing with general supply constraints for unit demand consumers
- Buying cheap is expensive: approximability of combinatorial pricing problems
Cited In (10)
- The envy-free pricing problem, unit-demand markets and connections with the network pricing problem
- Designing cost-sharing methods for Bayesian games
- Pricing to Maximize Revenue and Welfare Simultaneously in Large Markets
- On envy-free Pareto efficient pricing
- Envy-Free Pricing in Multi-item Markets
- Recent studies of agent incentives in Internet resource allocation and pricing
- A QPTAS for -Envy-Free Profit-Maximizing Pricing on Line Graphs
- Optimal revenue guarantees for pricing in large markets
- Recent studies of agent incentives in internet resource allocation and pricing
- Title not available (Why is that?)
This page was built for publication: Envy-free pricing in large markets: approximating revenue and welfare
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3448773)
