Abstract
Bayesian equilibria of simultaneous auctions for individual items have been explored recently [Christodoulou et al. 2008; Bhawalkar and Roughgarden 2011; Hassidim et al. 2011; Feldman et al. 2013] as an alternative to the well-known complexity issues plaguing combinatorial auctions with incomplete information, and some strong positive results have been shown about their performance. We point out some very serious complexity obstacles to this approach: Computing a Bayesian equilibrium in such auctions is hard for PP — a complexity class between the polynomial hierarchy and PSPACE — and even finding an approximate such equilibrium is as hard as NP, for some small approximation ratio (additive or multiplicative); therefore, the assumption that such equilibria will be arrived at by rational agents is quite problematic. In fact, even recognizing a Bayesian Nash equilibrium is intractable. Furthermore, these results hold even if bidder valuations are quite benign: Only one bidder valuation in our construction is unit demand or monotone submodular, while all others are additive. We also explore the possibility of favorable price of anarchy results for no-regret dynamics of the Bayesian simultaneous auctions game, and identify complexity obstacles there as well.
