Optimal Bundle Pricing for Homogeneous Items

We consider a revenue maximization problem where we are selling a set ofm 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 affine 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