Zhiqi Wang

News

Sep 10, 2026	My paper “Optimal Posted Pricing with Unknown Demand under Uniform Arrivals” is accepted to WINE 2026
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. WINE 2026

     Optimal Posted Pricing with Unknown Demand under Uniform Arrivals

     Nick Gravin, Hao Li, and Zhiqi Wang

     In Proceedings of the 22nd Conference on Web and Internet Economics (WINE), 2026

     Abs PDF

     We consider the classic problem of selling a single item to a stream of buyers with private values, which is a well-studied setting of single-choice i.i.d. prophet inequality. The optimal online policy and uniform pricing are crucially dependent on demand n, i.e., the number of buyers in the stream. In practice, such as online commerce applications, the demand is often hard to predict and estimate in advance. To address this unpredictability of the demand, we propose a natural online learning setting in which an adversary chooses n and the algorithm learns the demand by observing the arrival times of the buyers. We assume that customers in the stream arrive independently at random times drawn from a known distribution. This model is equivalent to uniform i.i.d. arrivals in the [0,1] time interval. We evaluate the online algorithm in the worst case over the demand n against two standard benchmarks: the offline prophet OFF(n) and the optimal online policy ON(n) with known demand n. We analyze single-threshold strategies that use the first arrival time t1 as a one-point estimator of demand and then commit to a uniform price. We first show that a simple rule is 1/2-competitive with respect to the OFF benchmark and find a more sophisticated rule that achieves a ln 3/2 ≈ 0.549 competitive ratio. Finally, we develop fully polynomial-time approximation schemes (FPTAS) to compute near-optimal unknown-demand policies against both benchmarks. The core of our approach is a no-regret learning procedure that computes a Nash equilibrium in a zero-sum game between the algorithm and an adversary who chooses n. As an application, we implement our FPTAS and identify instances showing a separation in approximation ratio between our unknown-demand model and the classical known-demand i.i.d. prophet inequality.

  2. 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.

  3. 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.




• 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.