Tutte seminar - Chaitanya Swamy

Approximation algorithms for envy-free profit-maximization problems

Abstract:

We consider a class of pricing problems, called envy-free profit-maximization problems, wherein a seller wants to set prices on items and allocate items (which are available in limited supply) to customers so as to maximize his profit, with the constraint that each customer receives a utility-maximizing subset of items. We 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 tree), 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. 
The talk will be self-contained.

Joint work with Maurice Cheung.