CS 789 THEORY SEMINAR [home]

Speaker:    Jason Hartline
Affiliation:  Microsoft Research
Date:         February 9, 2004
Title:         On Seller Optimal Envy-Free Pricing

Abstract:

We consider the computational problem a monopolistic store owner faces when setting prices for the items for sale. Given the true combinatorial valuations of a set of consumers for the sale items, we look for pricings for the individual items such that a) there is no squabbling between consumers (when they are all in the store at once). I.e, the pricing induces an envy-free allocation in which every consumer can obtain their utility maximizing allocation of items as if they were the only shopper in the store.  b) the seller's profit is optimized.

We consider the unit demand special case of this problem in which each consumer is assumed to want at most one item (e.g., sale of houses, or movies on airline flights). We review some pricing techniques from game-theory and use them to get a log-approximation. We show that a special case of this unit demand problem is APX-hard.  Finally, we consider the mechanism design problem of actually selling the items when the demands of the consumers are not publicly known in advance (and give a log approximation).

This is joint work with Anna Karlin and Claire Kenyon