Pricing ordered items

We study the revenue guarantees and approximability of item pricing. Recent work shows that with n heterogeneous items, item-pricing guarantees an O (log n ) 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 unit-demand valuations, it is NP-hard to find item prices that approximate the revenue of the optimal item pricing better than O (√ n ).

Authors

• Shuchi Chawla 0001
• Rojin Rezvan
• Yifeng Teng
• Christos Tzamos

Keywords

• buy-many mechanisms
• item pricing
• ordered item values
• revenue maximization