Optimal Auctions with Convex Perceived Payments

Myerson derived a simple and elegant solution to the single-parameter revenuemaximization problem in his seminal work on optimal auction design assuming the usual model of quasi-linear utilities. In this paper, we consider a slight generalization of this usual model—from linear to convex “perceived” payments. This more general problem does not appear to admit a solution as simple and elegant as Myerson’s. While some of Myerson’s results extend to our setting, like his payment formula (suitably adjusted), and the observation that “the mechanism is incentive compatible only if the allocation rule is monotonic,” others do not. For example, we observe that the solutions to the Bayesian and the robust (i.e., non-Bayesian) optimal auction design problems in the convex perceived payment setting do not coincide like they do in the case of linear payments. We therefore study the two problems in turn. Myerson finds an optimal robust (and Bayesian) auction by solving pointwise: for each vector of virtual values, he finds an optimal, ex-post feasible auction; then he plugs the resulting allocation, which he first verifies is monotonic, into his payment formula. This strategy relies on a key theorem, that expected revenue equals expected virtual surplus, which does not hold in our setting. Still, we derive an upper and a heuristic lower bound on expected revenue in our setting. These bounds are easily computed pointwise, and yield monotonic allocation rules, so can be supported by Myerson payments (suitably adjusted). In this way, our bounds yield heuristics that approximate the optimal robust auction, assuming convex perceived payments. In tackling the Bayesian problem, we derive a mathematical program that improves upon the default formulation in that it has only polynomially-many payment variables; however, it still has exponentially-many allocation variables and ex-post feasibility constraints. To address this latter issue, we also study the ex-ante relaxation, which requires only polynomially-many constraints, in all. Specifically, we present a closedform solution to a straightforward relaxation of this relaxation. Then, following similar logic, we present a closed-form upper bound and a heuristic lower bound on the solution to the (ex-post) robust problem. As above, the resulting allocation rules can then be supported by Myerson payment rules, yielding faster heuristics than the greedy ones for approximating the optimal robust auction. Interestingly, all our closed-form solutions are rather intuitive: they allocate in proportion to values (or virtual values). We close with experiments, the final set of which massages the output of one of the closed-form heuristics for the robust problem into an extremely fast, near-optimal heuristic solution to the Bayesian optimal auction design problem.