Optimal Auctions with Convex Perceived Payments

Amy Greenwald, Takehiro Oyakawa, Vasilis SyrgkanisarXiv 2016 · arXiv

Abstract

This paper generalizes Myerson’s classic optimal auction theory to environments where bidders perceive payments through a convex lens. This modeling choice captures real-world phenomena such as risk aversion or increasing marginal production costs (diseconomies of scale). While the standard "winner-takes-all" approach for revenue maximization fails under convex payments, the authors demonstrate that near-optimal revenue can be achieved through intuitive "proportional" allocation rules and efficient greedy heuristics.

Introduction: Beyond Quasi-Linearity

In 1981, Roger Myerson established that to maximize revenue, an auctioneer should maximize "virtual surplus," assuming bidders have quasi-linear utility ($u = v - p$). However, real-world bidders often face non-linear costs. For example, a power company bidding for subsidies may find the 100th megawatt significantly more expensive to produce than the first. In such cases, the perceived cost of a payment is a convex function, $q(p)$, leading to a utility function of $u = v \cdot x - q(p)$.

Standard linear utility model where perceived payment is linear.
Convex utility model where perceived payment is quadratic.

As shown in the figures above, the transition from linear to convex perceived payments changes the geometry of the bidder's utility surface from a flat plane to a curved manifold. This shift invalidates Myerson’s core theorem—that expected revenue equals expected virtual surplus—making the search for an optimal auction significantly more complex.

Methodology

The researchers address this complexity by distinguishing between two regimes: the Robust (Ex-post) regime, where constraints must hold for every outcome, and the Bayesian (Interim) regime, where constraints hold in expectation.

To solve for optimal mechanisms, the authors developed several key techniques:

  • Modified Myerson Payments: A derivation of payment formulas adapted for any convex perceived payment function.
  • Equi-marginal Principle: A greedy allocation approach based on Gossen’s Law, where units are allocated to bidders where the marginal increase in the objective function is highest.
  • Mathematical Programming: Revenue maximization is formulated as a quadratic program. To mitigate the "curse of dimensionality," the authors proved a simplification for the Bayesian case that reduces the number of payment variables to a polynomial amount.
  • Closed-Form Heuristics: The authors derived solutions for relaxed versions of the problem, suggesting a "proportional" allocation rule where goods are distributed to bidders in proportion to their virtual values.

Key Insights and Results

The study reveals several fundamental departures from standard auction theory:

  1. The Robust-Bayesian Gap: Unlike the linear case, Bayesian revenue can strictly exceed robust revenue when payments are convex.
  2. Pseudo-Surplus: The authors introduce "pseudo-surplus" as a tighter upper bound on revenue than standard bidder surplus.
  3. Spreading the Wealth: Convex costs favor fractional allocations. Instead of a single winner, the optimal strategy often involves multiple bidders winning portions of the prize.
  4. Randomization: Randomized auctions or fractional allocations can generate more revenue than deterministic ones in this setting.

Experimental evaluations using synthetic simulations (Categorical, Uniform, and Binomial distributions) showed that the proposed greedy heuristics perform remarkably close to the theoretical optimum. Furthermore, while standard solvers like IBM’s CPLEX struggled to scale with the number of bidders, the authors' closed-form heuristics remained nearly instantaneous.

Conclusion and Future Work

This research provides a robust framework for designing auctions when bidders exhibit non-linear payment perceptions. While the current experimental focus was on quadratic payments, the underlying theory is general. Future work may involve establishing formal theoretical approximation ratios and extending computational implementations to continuous type spaces.

Summary updated

Abstract

Myerson derived a simple and elegant solution to the single-parameter revenue-maximization 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), 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. 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. 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.
BibTeX
@misc{greenwald2016optimal,
  author = {Amy Greenwald and Takehiro Oyakawa and Vasilis Syrgkanis},
  title = {{Optimal Auctions with Convex Perceived Payments}},
  year = {2016},
  eprint = {1601.07163},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1601.07163},
}
Figure