Enhancing Affine Maximizer Auctions with Correlation-Aware Payment

Affine Maximizer Auctions (AMAs), a generalized mechanism family from VCG, are widely used in automated mechanism design due to their inherent dominant-strategy incentive compatibility (DSIC) and individual rationality (IR). However, as the payment form is fixed, AMA's expressiveness is restricted, especially in distributions where bidders' valuations are correlated. In this paper, we propose Correlation-Aware AMA (CA-AMA), a novel framework that augments AMA with a new correlation-aware payment. We show that any CA-AMA preserves the DSIC property and formalize finding optimal CA-AMA as a constraint optimization problem subject to the IR constraint. Then, we theoretically characterize scenarios where classic AMAs can perform arbitrarily poorly compared to the optimal revenue, while the CA-AMA can reach the optimal revenue. For optimizing CA-AMA, we design a practical two-stage training algorithm. We derive that the target function's continuity and the generalization bound on the degree of deviation from strict IR. Finally, extensive experiments showcase that our algorithm can find an approximate optimal CA-AMA in various distributions with improved revenue and a low degree of violation of IR.

Many automated markets, such as auctions for online resources, rely on rules that encourage bidders to report their values honestly. A popular family of such rules, called Affine Maximizer Auctions, has strong truthfulness guarantees, but its payment rule can be too rigid when bidders’ values are correlated. For example, if one bidder tends to value an item highly exactly when another bidder values it poorly, existing rules may fail to charge prices that reflect this relationship and can lose substantial revenue. We propose Correlation-Aware Affine Maximizer Auctions, or CA-AMA, which adds an extra payment term based only on the other bidders’ reported values. Because this extra term does not depend on a bidder’s own report, truthful bidding remains the best strategy. We also design a two-stage learning algorithm to optimize these auctions while controlling whether bidders still benefit from participating. Our theory shows that CA-AMA can achieve optimal revenue in correlated settings where standard AMA can perform arbitrarily poorly. Experiments on single-item and multi-item auctions show higher revenue with little added computational cost.