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)$.
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:
- The Robust-Bayesian Gap: Unlike the linear case, Bayesian revenue can strictly exceed robust revenue when payments are convex.
- Pseudo-Surplus: The authors introduce "pseudo-surplus" as a tighter upper bound on revenue than standard bidder surplus.
- 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.
- 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