Bayesian Auctions with Efficient Queries (Extended Abstract)

Jing Chen, Bo Li, Yingkai Li, Pinyan Lu

Abstract

In classical Bayesian mechanism design, sellers are often assumed to possess complete knowledge of bidder value distributions. However, in practice, these distributions are often complex or unknown. This paper introduces the framework of query complexity to auction design, demonstrating that near-optimal revenue can be achieved using only a logarithmic number of targeted queries. This represents an exponential improvement over traditional sample-based learning methods, providing a robust theoretical foundation for practical auction mechanisms.

Introduction: The Information Gap in Auction Design

Traditional Bayesian auction theory relies on the "all-knowing" seller assumption: the seller knows the exact probability distribution of bidder valuations. In reality, distributions can be continuous, irregular, or have exponentially large supports, making full knowledge computationally and practically infeasible. While previous research has explored sample complexity—learning from random observations—this often requires a prohibitive number of samples to reach optimality.

This work shifts the focus to a more strategic interaction: if a seller can ask a limited number of specific questions about the distribution, how many are necessary to approximate optimal revenue?

Methodology: Value and Quantile Queries

The authors model the seller’s interaction through two types of oracle queries:

  1. Value Queries: Given a price $v$, the oracle returns the probability $q$ that a buyer's value is at least $v$.
  2. Quantile Queries: Given a probability $q$, the oracle returns the price $v$ such that exactly $q$ percent of buyers value the item at $v$ or higher.

The research focuses on designing Dominant-Strategy Incentive Compatible (DSIC) mechanisms across various settings, including single-item auctions and multi-item auctions (unit-demand and additive valuations).

The Strategic Advantage: Queries vs. Samples

A core insight of this research is that targeted queries provide an exponential speedup over passive sampling. While random sampling is subject to the variance of the distribution, queries allow the seller to probe the most profitable regions directly.

Comparison of sample complexity and approximation factors across different auction settings.

As shown in the comparison above, sample complexity typically scales polynomially with the range $H$ or the error $\epsilon$, whereas query complexity scales logarithmically ($\log H$). This efficiency makes query-based mechanisms far more practical for large-scale markets.

Main Results and Complexity Bounds

The authors establish both upper and lower bounds for query complexity, proving that a logarithmic number of queries is both sufficient and necessary for constant-factor approximations of optimal revenue.

Summary of query complexity results for various auction types and distribution classes.

Key findings include:

  • Single-Item Auctions: Achieved near-optimal $(1+\epsilon)$-approximation with $\Theta(n^{-1} \log H)$ queries.
  • Multi-Item Auctions: For unit-demand and additive valuations, the authors designed mechanisms providing constant-factor approximations (e.g., factors of 24 and 8, respectively) using logarithmic queries.
  • Robustness: The proposed mechanisms remain effective even in the presence of "noisy" oracle responses, ensuring applicability in imperfect real-world markets.

Discussion and Future Directions

While this work provides tight bounds for standard valuation models, it opens several avenues for future research. The current mechanisms for multi-item auctions involve constant factors that could potentially be tightened. Furthermore, extending these query-efficient frameworks to more complex buyer preferences, such as general subadditive valuations, remains an important open challenge in the field of algorithmic mechanism design.

Summary updated

Abstract

Designing dominant-strategy incentive compatible (DSIC) mechanisms for a seller to generate (approximately) optimal revenue by selling items to players is a fundamental problem in Bayesian mechanism design. However, most existing studies assume that the seller knows the entire distribution from which the players’ values are drawn. Unfortunately, this assumption may not hold in reality: for example, when the distributions have exponentially large supports or do not have succinct representations. In this work we consider, for the first time, the query complexityof Bayesian mechanisms. The seller only has limited oracle accesses to the players’ distributions, via quantile queriesand value queries. For single-item auctions, we design mechanisms with logarithmicnumber of value or quantile queries which achieve almost optimal revenue. We then prove logarithmic lower-bounds, i.e., logarithmic number of queries are necessary for any constant approximation DSIC mechanisms, even when randomized and adaptive queries are allowed. Thus our mechanisms are almost optimal regarding query complexity. Our lower-bounds can be extended to multi-item auctions with monotone subadditive valuations, and we complement this part with constant approximation mechanisms for unit-demand or additive valuation functions. Our results are robust even if the answers to the queries contain noises.
BibTeX
@inproceedings{chen2022bayesian,
  author = {Jing Chen and Bo Li and Yingkai Li and Pinyan Lu},
  title = {{Bayesian Auctions with Efficient Queries (Extended Abstract)}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.24963/ijcai.2022/795},
}
Figure