Optimal Bundle Pricing for Homogeneous Items
AbstractWe consider a revenue maximization problem where we are selling a set of m items, each of which available in a certain quantity (possibly unlimited) to a set of n bidders. Bidders are single minded, that is, each bidder requests exactly one subset, or bundle of items. Each bidder has a valuation for the requested bundle that we assume to be known to the seller. The task is to find an envy-free pricing such as to maximize the revenue of the seller. We derive several complexity results and algorithms for several variants of this pricing problem. In fact, the settings that we consider address problems where the different items are `homogeneous'' in some sense. First, we introduce the notion of affne price functions that can be used to model situations much more general than the usual combinatorial pricing model that is mostly addressed in the literature. We derive fixed-parameter polynomial time algorithms as well as inapproximability results. Second, we consider the special case of combinatorial pricing, and introduce a monotonicity constraint that can also be seen as `global'' envy-freeness condition. We show that the problem remains strongly NP-hard, and we derive a PTAS - thus breaking the inapproximability barrier known for the general case. As a special case, we finally address the notorious highway pricing problem under the global envy-freeness condition.
Download InfoIf you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
Bibliographic InfoPaper provided by Maastricht : METEOR, Maastricht Research School of Economics of Technology and Organization in its series Research Memoranda with number 050.
Date of creation: 2006
Date of revision:
Contact details of provider:
Web page: http://www.maastrichtuniversity.nl/web/UMPublications.htm
operations research and management science;
This paper has been announced in the following NEP Reports:
- NEP-ALL-2006-12-16 (All new papers)
- NEP-MIC-2006-12-16 (Microeconomics)
- NEP-MKT-2006-12-16 (Marketing)
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Grigoriev Alexander & Loon, Joyce van & Sitters, René & Uetz, Marc, 2006. "How to Sell a Graph: Guidelines for Graph Retailers," Research Memoranda 001, Maastricht : METEOR, Maastricht Research School of Economics of Technology and Organization.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Charles Bollen).
If references are entirely missing, you can add them using this form.