Abstract
No (external) regret is the standard performance guarantee in online learning. It ensures that, in hindsight, a learner performs nearly as well as the best fixed action. However, in strategic environments such as repeated auctions, this guarantee can be fragile: a strategic auctioneer can manipulate many widely adopted no-regret learning algorithms and extract the full welfare of a bidder who uses them, despite the bidder satisfying no regret. This vulnerability raises two central questions: which learning guarantees remain meaningful in strategic settings, and how can we design algorithms that are robust to strategic manipulation? In this talk, I present two results that contribute to our understanding of these questions. First, I characterize game-agnostic, non-manipulable algorithms in general repeated Bayesian games. Second, I develop a meta-algorithm that transforms any no-regret learning algorithm into a non-manipulable bidding algorithm for repeated auctions while preserving no-regret guarantees.
Time
Tuesday, Mar.10, 14:00--15:00
Speaker
Junyao Zhao
Room
Room 602