Optimization Online


Regret Minimization and Separation in Multi-Bidder Multi-Item Auctions

Cagil Kocyigit (cagil.kocyigit***at***epfl.ch)
Daniel Kuhn (daniel.kuhn***at***epfl.ch)
Napat Rujeerapaiboon (isenapa***at***nus.edu.sg)

Abstract: We study a robust auction design problem with a minimax regret objective, where a seller seeks a mechanism for selling multiple items to multiple anonymous bidders with additive values. The seller knows that the bidders' values range over a box uncertainty set but has no information about their probability distribution. This auction design problem can be viewed as a zero-sum game between the seller, who chooses a mechanism, and a fictitious adversary or `nature,' who chooses the bidders' values from within the uncertainty set with the aim to maximize the seller's regret. We characterize the Nash equilibrium of this game analytically. The Nash strategy of the seller is a mechanism that sells each item via a separate auction akin to a second price auction with a random reserve price. The Nash strategy of nature is mixed and constitutes a probability distribution on the uncertainty set under which each bidder's values for the items are comonotonic.

Keywords: auction, mechanism design, robust optimization

Category 1: Robust Optimization


Download: [PDF]

Entry Submitted: 06/26/2020
Entry Accepted: 06/26/2020
Entry Last Modified: 06/30/2020

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society