The Role of Transparency in Repeated First-Price Auctions with Unknown Valuations

Nicolo Cesa-Bianchi; Tommaso Cesari; Roberto Colomboni; Federico Fusco; Stefano Leonardi

doi:10.1145/3618260.3649658

The Role of Transparency in Repeated First-Price Auctions with Unknown Valuations

Nicolo Cesa-Bianchi, Tommaso Cesari, Roberto Colomboni, Federico Fusco, Stefano Leonardi

School of Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Conference Contribution (Conference Proceeding)

6 Citations (Scopus)

Abstract

We study the problem of regret minimization for a single bidder in a sequence of first-price auctions where the bidder discovers the item's value only if the auction is won. Our main contribution is a complete characterization, up to logarithmic factors, of the minimax regret in terms of the auction's transparency, which controls the amount of information on competing bids disclosed by the auctioneer at the end of each auction. Our results hold under different assumptions (stochastic, adversarial, and their smoothed variants) on the environment generating the bidder's valuations and competing bids. These minimax rates reveal how the interplay between transparency and the nature of the environment affects how fast one can learn to bid optimally in first-price auctions.

Original language	English
Title of host publication	STOC 2024 - Proceedings of the 56th Annual ACM Symposium on Theory of Computing
Editors	Bojan Mohar, Igor Shinkar, Ryan O'Donnell
Publisher	Association for Computing Machinery
Pages	225-236
Number of pages	12
ISBN (Electronic)	9798400703836
DOIs	https://doi.org/10.1145/3618260.3649658
Publication status	Published - 11 Jun 2024
Event	56th Annual ACM Symposium on Theory of Computing, STOC 2024 - Vancouver, Canada Duration: 24 Jun 2024 → 28 Jun 2024

Publication series

Name	Proceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)	0737-8017

Conference

Conference	56th Annual ACM Symposium on Theory of Computing, STOC 2024
Country/Territory	Canada
City	Vancouver
Period	24/06/24 → 28/06/24

Bibliographical note

Publisher Copyright:
© 2024 Owner/Author.

Keywords

First-Price Auction
Online Learning
Transparency

Access to Document

10.1145/3618260.3649658Licence: CC BY

Handle.net

Persistent link

Cite this

Cesa-Bianchi, N., Cesari, T., Colomboni, R., Fusco, F., & Leonardi, S. (2024). The Role of Transparency in Repeated First-Price Auctions with Unknown Valuations. In B. Mohar, I. Shinkar, & R. O'Donnell (Eds.), STOC 2024 - Proceedings of the 56th Annual ACM Symposium on Theory of Computing (pp. 225-236). (Proceedings of the Annual ACM Symposium on Theory of Computing). Association for Computing Machinery. https://doi.org/10.1145/3618260.3649658

Cesa-Bianchi, Nicolo ; Cesari, Tommaso ; Colomboni, Roberto et al. / The Role of Transparency in Repeated First-Price Auctions with Unknown Valuations. STOC 2024 - Proceedings of the 56th Annual ACM Symposium on Theory of Computing. editor / Bojan Mohar ; Igor Shinkar ; Ryan O'Donnell. Association for Computing Machinery, 2024. pp. 225-236 (Proceedings of the Annual ACM Symposium on Theory of Computing).

@inproceedings{f0ffbd94cac24f20a4b4c4a5d614941c,

title = "The Role of Transparency in Repeated First-Price Auctions with Unknown Valuations",

abstract = "We study the problem of regret minimization for a single bidder in a sequence of first-price auctions where the bidder discovers the item's value only if the auction is won. Our main contribution is a complete characterization, up to logarithmic factors, of the minimax regret in terms of the auction's transparency, which controls the amount of information on competing bids disclosed by the auctioneer at the end of each auction. Our results hold under different assumptions (stochastic, adversarial, and their smoothed variants) on the environment generating the bidder's valuations and competing bids. These minimax rates reveal how the interplay between transparency and the nature of the environment affects how fast one can learn to bid optimally in first-price auctions.",

keywords = "First-Price Auction, Online Learning, Transparency",

author = "Nicolo Cesa-Bianchi and Tommaso Cesari and Roberto Colomboni and Federico Fusco and Stefano Leonardi",

note = "Publisher Copyright: {\textcopyright} 2024 Owner/Author.; 56th Annual ACM Symposium on Theory of Computing, STOC 2024 ; Conference date: 24-06-2024 Through 28-06-2024",

year = "2024",

month = jun,

day = "11",

doi = "10.1145/3618260.3649658",

language = "English",

series = "Proceedings of the Annual ACM Symposium on Theory of Computing",

publisher = "Association for Computing Machinery",

pages = "225--236",

editor = "Bojan Mohar and Igor Shinkar and Ryan O'Donnell",

booktitle = "STOC 2024 - Proceedings of the 56th Annual ACM Symposium on Theory of Computing",

address = "United States",

}

Cesa-Bianchi, N, Cesari, T, Colomboni, R, Fusco, F & Leonardi, S 2024, The Role of Transparency in Repeated First-Price Auctions with Unknown Valuations. in B Mohar, I Shinkar & R O'Donnell (eds), STOC 2024 - Proceedings of the 56th Annual ACM Symposium on Theory of Computing. Proceedings of the Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, pp. 225-236, 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, Canada, 24/06/24. https://doi.org/10.1145/3618260.3649658

The Role of Transparency in Repeated First-Price Auctions with Unknown Valuations. / Cesa-Bianchi, Nicolo; Cesari, Tommaso; Colomboni, Roberto et al.
STOC 2024 - Proceedings of the 56th Annual ACM Symposium on Theory of Computing. ed. / Bojan Mohar; Igor Shinkar; Ryan O'Donnell. Association for Computing Machinery, 2024. p. 225-236 (Proceedings of the Annual ACM Symposium on Theory of Computing).

Research output: Chapter in Book/Report/Conference proceeding › Conference Contribution (Conference Proceeding)

TY - GEN

T1 - The Role of Transparency in Repeated First-Price Auctions with Unknown Valuations

AU - Cesa-Bianchi, Nicolo

AU - Cesari, Tommaso

AU - Colomboni, Roberto

AU - Fusco, Federico

AU - Leonardi, Stefano

PY - 2024/6/11

Y1 - 2024/6/11

N2 - We study the problem of regret minimization for a single bidder in a sequence of first-price auctions where the bidder discovers the item's value only if the auction is won. Our main contribution is a complete characterization, up to logarithmic factors, of the minimax regret in terms of the auction's transparency, which controls the amount of information on competing bids disclosed by the auctioneer at the end of each auction. Our results hold under different assumptions (stochastic, adversarial, and their smoothed variants) on the environment generating the bidder's valuations and competing bids. These minimax rates reveal how the interplay between transparency and the nature of the environment affects how fast one can learn to bid optimally in first-price auctions.

AB - We study the problem of regret minimization for a single bidder in a sequence of first-price auctions where the bidder discovers the item's value only if the auction is won. Our main contribution is a complete characterization, up to logarithmic factors, of the minimax regret in terms of the auction's transparency, which controls the amount of information on competing bids disclosed by the auctioneer at the end of each auction. Our results hold under different assumptions (stochastic, adversarial, and their smoothed variants) on the environment generating the bidder's valuations and competing bids. These minimax rates reveal how the interplay between transparency and the nature of the environment affects how fast one can learn to bid optimally in first-price auctions.

KW - First-Price Auction

KW - Online Learning

KW - Transparency

U2 - 10.1145/3618260.3649658

DO - 10.1145/3618260.3649658

M3 - Conference Contribution (Conference Proceeding)

AN - SCOPUS:85191275988

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 225

EP - 236

BT - STOC 2024 - Proceedings of the 56th Annual ACM Symposium on Theory of Computing

A2 - Mohar, Bojan

A2 - Shinkar, Igor

A2 - O'Donnell, Ryan

PB - Association for Computing Machinery

T2 - 56th Annual ACM Symposium on Theory of Computing, STOC 2024

Y2 - 24 June 2024 through 28 June 2024

ER -

Cesa-Bianchi N, Cesari T, Colomboni R, Fusco F, Leonardi S. The Role of Transparency in Repeated First-Price Auctions with Unknown Valuations. In Mohar B, Shinkar I, O'Donnell R, editors, STOC 2024 - Proceedings of the 56th Annual ACM Symposium on Theory of Computing. Association for Computing Machinery. 2024. p. 225-236. (Proceedings of the Annual ACM Symposium on Theory of Computing). doi: 10.1145/3618260.3649658

The Role of Transparency in Repeated First-Price Auctions with Unknown Valuations

Abstract

Publication series

Conference

Bibliographical note

Keywords

Access to Document

Handle.net

Fingerprint

Cite this