Zhiqi Wang

News

Dec 10, 2024	My paper “Optimal Auction Design for Mixed Bidders” is accepted to AAAI 2025
Jun 23, 2024	My paper “On Robustness to k-wise Independence of Optimal Bayesian Mechanisms” is accepted to FOCS 2024

Selected Publications by Topics:

• Algorithmic Game Theory

  1. AAAI 2025

     Optimal Auction Design for Mixed Bidders

     Xiaohui Bei, Pinyan Lu, Zhiqi Wang, Xiang Yan, and Tao Xiao

     In Proceedings of the AAAI Conference on Artificial Intelligence, 2025

     Abs PDF

     The predominant setting in classic auction theory considers bidders as utility maximizers (UMs), who aim to maximize quasi-linear utility functions. Recent autobidding strategies in online advertising have sparked interest in auction design with value maximizers (VMs), who aim to maximize the total value obtained. In this work, we investigate revenue-maximizing auction design for selling a single item to a mix of UMs and VMs. Crucially, we assume the UM/VM type is private information of a bidder. This shift to a multi-parameter domain complicates the design of incentive compatible mechanisms. Under this setting, we first characterize the optimal auction structure for auctions with a single bidder. We observe that the optimal auction moves gradually from a first-price auction to a Myerson auction as the probability of the bidder being a UM increases from 0 to 1. We also extend our study to multi-bidder setting and present an algorithm for deriving the optimal lookahead auction with multiple mixed types of bidders.

  2. FOCS 2024

     On Robustness to k-wise Independence of Optimal Bayesian Mechanisms

     Nick Gravin, and Zhiqi Wang

     In 2024 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), 2024

     Abs arXiv PDF

     This paper reexamines the classic problem of revenue maximization in single-item auctions with n buyers under the lens of the robust optimization framework. The celebrated Myerson’s mechanism is the format that maximizes the seller’s revenue under the prior distribution, which is mutually independent across all n buyers. As argued in a recent line of work (Caragiannis et al. 22), (Dughmi et al. 24), mutual independence is a strong assumption that is extremely hard to verify statistically, thus it is important to relax the assumption.

     While optimal under mutual independent prior, we find that Myerson’s mechanism may lose almost all of its revenue when the independence assumption is relaxed to pairwise independence, i.e., Myerson’s mechanism is not pairwise-robust. The mechanism regains robustness when the prior is assumed to be 3-wise independent. In contrast, we show that second-price auctions with anonymous reserve, including optimal auctions under i.i.d. priors, lose at most a constant fraction of their revenues on any regular pairwise independent prior. Our findings draw a comprehensive picture of robustness to k-wise independence in single-item auction settings.

  1. MOTOR 2024

     A Unified Framework of Multi-stage Multi-winner Voting: An Axiomatic Exploration

     Shengjie Gong, Lingxiao Huang , Shuangping Huang, Yuyi Wang, Zhiqi Wang, Tao Xiao, Xiang Yan, and Chunxue Yang

     In International Conference on Mathematical Optimization Theory and Operations Research, 2024

     Abs arXiv PDF

     Multi-winner voting plays a crucial role in selecting representative committees based on voter preferences. Previous research has predominantly focused on single-stage voting rules, which are susceptible to manipulation during preference collection. In order to mitigate manipulation and increase the cost associated with it, we propose the introduction of multiple stages in the voting procedure, leading to the development of a unified framework of multi-stage multi-winner voting rules. To shed light on this framework of voting methods, we conduct an axiomatic study, establishing provable conditions for achieving desired axioms within our model. Our theoretical findings can serve as a guide for the selection of appropriate multi-stage multi-winner voting rules.

  See More



• Smart Grid

  1. TSG

     On the Sample Complexity of Storage Control

     Zhiqi Wang, Zeren Tan, and Yang Yu

     IEEE Transactions on Smart Grid, 2023

     Abs PDF

     Understanding the data value for energy-storage control is critical. The performance of the control policy is highly related to the quality of demand information. An accurate prediction about future demand can better the performance of energy storage control. Thus, the storage control asks for sufficient data-sample collection for qualified prediction. However, the lack of a theory to quantify the data sufficiency for the energy-storage control problem. Meanwhile, demand data samples include privacy information while the storage managers have to procure the data from data owners. Thus, it is necessary to determine the relationship between the data size and the storage-control performance. In addition, a growing number of studies have proposed many storage-control policies. However, we are unknown how to theoretically verify their data-use efficiency. Here, we develop the sample complexity theory of storage-control problem, which enables us to theoretically measure the data-use efficiency of the control strategy and assess the data value. We proposed the sample-based dynamic programming (SDP) algorithm that is both cost-minimization and data-use efficient. Based on the SDP and the sample complexity theory, we manifest the trade-off between data size, computational load, and storage-control performances. Finally, we used real-world data to conduct numerical experiments to validate the effectiveness of the proposed method.