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

Çağıl Koçyiğit (), Daniel Kuhn () and Napat Rujeerapaiboon ()
Additional contact information
Çağıl Koçyiğit: Luxembourg Centre for Logistics and Supply Chain Management, University of Luxembourg, L-1359 Luxembourg, Luxembourg
Daniel Kuhn: Risk Analytics and Optimization Chair, École Polytechnique Fédérale de Lausanne, 1015 Lausanne, Switzerland
Napat Rujeerapaiboon: Department of Industrial Systems Engineering and Management, National University of Singapore, Singapore 119077, Singapore

INFORMS Journal on Computing, 2024, vol. 36, issue 6, 1543-1561

Abstract: We study a robust auction design problem with a minimax regret objective, in which a seller seeks a mechanism for selling multiple items to multiple bidders with additive values. The seller knows that the bidders’ values range over a box uncertainty set but has no information on their probability distribution. The robust auction design model we study requires no distributional information except for upper bounds on the bidders’ values for each item. This model is relevant if there is no trustworthy distributional information or if any distributional information is costly or time-consuming to acquire. We propose a mechanism that sells each item separately via a second price auction with a random reserve price and prove that this mechanism is optimal using duality techniques from robust optimization. We then interpret the auction design problem 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 when the bidders are symmetric. The Nash strategy of the seller coincides with the optimal separable second price auction, whereas 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. We also study a restricted auction design problem over deterministic mechanisms. In this setting, we characterize the suboptimality of a separable second price auction with deterministic reserve prices and show that this auction becomes optimal if the bidders are symmetric. The optimal mechanism is derived in closed form and can easily be implemented by practitioners.

Keywords: multi-item auctions; robust auctions; mechanism design; minimax regret; robust optimization (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2022.0275 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:36:y:2024:i:6:p:1543-1561

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().