The computational complexity of computing refunds

We study a mechanism design setting where a seller offers an item to a buyer who is uncertain about her own valuation. Rather than using a simple take-it-or-leave-it price, the seller can extract significantly more revenue by offering refund options at different price levels. This setup, known as Sequential Screening, models a class of dynamic decision-making problems under uncertainty with applications ranging from airline ticket pricing to online education and healthcare diagnostics, where agents pay for flexible options under ambiguity. We investigate the power of deterministic mechanisms in this context and view them as a form of semi-adaptive preference elicitation, where the seller leverages knowledge of the buyer's value distribution to design refund-based menus that screen types indirectly. We show that the revenue gap between the optimal deterministic mechanism and simpler menus with bounded (possibly randomized) options can be arbitrarily large. We further establish that computing the revenue-optimal mechanism is NP-hard, and complement this result with a PTAS that computes approximately optimal refund schedules.