|
Friday, September 19, 2008 |
|
|
|
|
Approximation algorithms for envy-free profit-maximization problems |
|
|
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. |