License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2023.75
URN: urn:nbn:de:0030-drops-175780
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17578/
Go to the corresponding LIPIcs Volume Portal

Jin, Yaonan ; Lu, Pinyan ; Xiao, Tao

Learning Reserve Prices in Second-Price Auctions

pdf-format:
LIPIcs-ITCS-2023-75.pdf (1.0 MB)

Abstract

This paper proves the tight sample complexity of Second-Price Auction with Anonymous Reserve, up to a logarithmic factor, for each of all the value distribution families studied in the literature: [0,1]-bounded, [1,H]-bounded, regular, and monotone hazard rate (MHR). Remarkably, the setting-specific tight sample complexity poly(ε^{-1}) depends on the precision ε ∈ (0, 1), but not on the number of bidders n ≥ 1. Further, in the two bounded-support settings, our learning algorithm allows correlated value distributions.
In contrast, the tight sample complexity Θ̃(n) ⋅ poly(ε^{-1}) of Myerson Auction proved by Guo, Huang and Zhang (STOC 2019) has a nearly-linear dependence on n ≥ 1, and holds only for independent value distributions in every setting.
We follow a similar framework as the Guo-Huang-Zhang work, but replace their information theoretical arguments with a direct proof.

BibTeX - Entry

@InProceedings{jin_et_al:LIPIcs.ITCS.2023.75,
  author =	{Jin, Yaonan and Lu, Pinyan and Xiao, Tao},
  title =	{{Learning Reserve Prices in Second-Price Auctions}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{75:1--75:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/17578},
  URN =		{urn:nbn:de:0030-drops-175780},
  doi =		{10.4230/LIPIcs.ITCS.2023.75},
  annote =	{Keywords: Revenue Maximization, Sample Complexity, Anonymous Reserve}
}

Keywords: Revenue Maximization, Sample Complexity, Anonymous Reserve
Collection: 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Issue Date: 2023
Date of publication: 01.02.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI