Seminar Details
A Multi-Dimensional Online Contention Resolution Scheme for Revenue Maximization
- Start Date: March 26, 2025
- Event Start Time: 11:00 AM
- Event End Time: 12:00 PM
- Seminar Series: Theoretical Computer Science Seminar
- Presenter(s): Gregory Kehne - Washington University, St. Louis
- Event Location: Conference Room 301 | Rutgers University | CoRE Building | 96 Frelinghuysen Road
- Event Additional Info: <p>See: <a href="https://theory.cs.rutgers.edu/theory_seminar">https://theory.cs.rutgers.edu/theory_seminar</a></p>
- Presentation Type: Stand Alone Presentation
- Abstract:
We study multi-buyer multi-item sequential item pricing mechanisms for revenue maximization with the goal of approximating a natural fractional relaxation -- the ex ante optimal revenue. We assume that buyers' values are subadditive but make no assumptions on the value distributions. While the optimal revenue, and therefore also the ex ante benchmark, is inapproximable by any simple mechanism in this context, previous work has shown that a weaker benchmark that optimizes over so-called \`\`buy-many" mechanisms can be approximable. Approximations are known, in particular, for settings with either a single buyer or many unit-demand buyers. We extend these results to the much broader setting of many subadditive buyers. We show that the ex ante buy-many revenue can be approximated via sequential item pricings to within an O(log^2 m) factor, where m is the number of items. We also show that a logarithmic dependence on m is necessary.
This is joint work with Shuchi Chawla, Dimitris Christou, Trung Dang, Zhiyi Huang, and Rojin Rezvan, and appeared at SODA 2025.