Profit-maximization problems are pricing problems where a seller wants to set prices on items and/or allocate items (which are available in limited supply) to customers so as to maximize his profit. Different variants of the problem emerge depending on whether the customers decide which bundle of items they want to buy given the item-prices, or whether the seller has the flexibililty of allocating the items to customers. The former setting, is called the envy-free setting, and here the allocation is such that each customer receives a utility-maximizing subset of items. We first consider the important setting where each customer desires a single set of items, which is called the single-minded problem. Even special cases of this problem, where the underlying set system has a great deal of combinatorial structure (e.g., paths on a line), are NP-hard and surprisingly difficult, with no non-trivial approximation guarantees known. We present the first approximation algorithms for this class of problems. Our approximation bounds are obtained by comparing the profit of our solution against the optimal value of the corresponding social-welfare-maximization (SWM) problem, which is the problem of finding a "winner-set" of customers with maximum total value. We show that any LP-based \rho-approximation algorithm for the corresponding SWM problem can be used to obtain profit at least OPT/O(\rho\log u_max), where OPT is the optimal value of the SWM problem, and u_max is the maximum supply of an item. This immediately yields approximation algorithms for a host of single-minded envy-free profit-maximization problems. The analysis leverages LP duality theory in a novel way. Our results extend (with somewhat different guarantees) to various (non-envy-free) profit-maximization problems, where the customers are not necessarily single-minded but may have complicated set-based valuation functions.
The talk will be self-contained. Parts of this talk are joint work with Maurice Cheung, Cornell University.