A study of compact reserve pricing languages

Motivated by ad auctions we study the multiplicative reserve price system (MRPS). MRPS is a compact way to set reserve prices on several auctions simultaneously. In this paper first we consider the problem of finding the best way of assigning reserve prices in this system. We show that this problem is NP-hard. Next, by characterizing the the properties of an optimum solution we design an approximation algorithm for this problem. Interestingly, our experiments show that our algorithm achieves 90–98% of the optimum solution that sets the reserve price of each auction independently (i.e., the optimum set of reserve prices). We show that in the adversarial setting we lose at most a logarithmic factor compare to the optimum set of reserve prices. To show the tightness of our results in the adversarial setting, we show that there is no compact pricing system (i.e. a pricing system that uses O(n^{1−ε}) bits to set n reserve prices) that loses less than a logarithmic factor compare to the optimum set of reserve prices, in the worst case. Notice that, interestingly, this hardness result holds for any pricing system and not only MRPS.

• Algorithms and Theory

• Economics and Electronic Commerce