Pricing ordered items

We study the revenue guarantees and approximability of item pricing. Recent work shows that with heterogeneous items, itempricing guarantees an (log ) approximation to the optimal revenue achievable by any (buy-many) mechanism, even when buyers have arbitrarily combinatorial valuations. However, finding good item prices is challenging it is known that even under unitdemand valuations, it is NP-hard to find item prices that approximate the revenue of the optimal item pricing better than ( ). Our work provides a more fine-grained analysis of the revenue guarantees and computational complexity in terms of the number of item categories which may be significantly fewer than . We assume the items are partitioned in categories so that items within a category are totally-ordered and a buyer's value for a bundle depends only on the best item contained from every category.