Repeated Dollar Auctions: A Multi-Armed Bandit Approach

We investigate the repeated version of Shubik's [34] dollar auctions, in which the type of the opponent and their level of rationality is not known in advance. We formulate the problem as an adversarial multi-armed bandit, and we show that a modified version of the ELP algorithm [25], tailored to our setting, can achieve Õ(|S0|T) performance loss (compared to the best fixed strategy), where |S0| is the cardinality of the set of available strategies and T is the number of (sequential) auctions. We also show that under some further conditions, these bound can be improved to Õ(|S0| 1/4 √ T) and Õ(√ T), respectively. Finally, we consider the case of spiteful players. We prove that when a non-spiteful player bids against a malicious one, the game converges in performance to a Nash equilibrium if both players apply our strategy to place their bids.