Bundle pricing with comparable items
Grigoriev, Alexander and Loon, Joyce van and Sviridenko, Maxim and Uetz, Marc and Vredeveld, Tjark (2007) Bundle pricing with comparable items. In: 15th Annual European Symposium, ESA, 810 Oct 2007, Eilat, Israel (pp. pp. 475486).
PDF
Restricted to UT campus only : Request a copy 456kB 
Abstract:  We consider a revenue maximization problem where we are selling a set of items, each available in a certain quantity, to a set of bidders. Each bidder is interested in one or several bundles of items. We assume the bidders’ valuations for each of these bundles to be known. Whenever bundle prices are determined by the sum of single item prices, this algorithmic problem was recently shown to be inapproximable to within a semilogarithmic factor. We consider two scenarios for determining bundle prices that allow to break this inapproximability barrier. Both scenarios are motivated by problems where items are different, yet comparable. First, we consider classical single item prices with an additional monotonicity constraint, enforcing that larger bundles are at least as expensive as smaller ones. We show that the problem remains strongly NPhard, and we derive a PTAS. Second, motivated by reallife cases, we introduce the notion of affine price functions, and derive fixedparameter polynomial time algorithms.

Item Type:  Conference or Workshop Item 
Copyright:  © 2007 Springer 
Faculty:  Electrical Engineering, Mathematics and Computer Science (EEMCS) 
Research Group:  
Link to this item:  http://purl.utwente.nl/publications/62053 
Official URL:  http://dx.doi.org/10.1007/9783540755203_43 
Export this item as:  BibTeX EndNote HTML Citation Reference Manager 
Repository Staff Only: item control page
Metis ID: 245857