Scalable Virtual Valuations Combinatorial Auction Design by Combining
  Zeroth-Order and First-Order Optimization Method
Zhijian Duan Haoran Sun Yichong Xia Siqiang Wang Zhilin Zhang Chuan Yu Jian Xu Bo Zheng Xiaotie Deng
Automated auction design seeks to discover empirically high-revenue and
incentive-compatible mechanisms using machine learning. Ensuring dominant
strategy incentive compatibility (DSIC) is crucial, and the most effective
approach is to confine the mechanism to Affine Maximizer Auctions (AMAs).
Nevertheless, existing AMA-based approaches encounter challenges such as
scalability issues (arising from combinatorial candidate allocations) and the
non-differentiability of revenue. In this paper, to achieve a scalable
AMA-based method, we further restrict the auction mechanism to Virtual
Valuations Combinatorial Auctions (VVCAs), a subset of AMAs with significantly
fewer parameters. Initially, we employ a parallelizable dynamic programming
algorithm to compute the winning allocation of a VVCA. Subsequently, we propose
a novel optimization method that combines both zeroth-order and first-order
techniques to optimize the VVCA parameters. Extensive experiments demonstrate
the efficacy and scalability of our proposed approach, termed Zeroth-order and
First-order Optimization of VVCAs (ZFO-VVCA), particularly when applied to
large-scale auctions.