We study the price of anarchy (PoA) of simultaneous first-price auctions (FPAs) for buyers with submodular and subadditive valuations. The current best upper bounds for the Bayesian price of anarchy (BPoA) of these auctions are e/(e − 1) [Syrgkanis and Tardos 2013] and 2 [Feldman et al. 2013] , respectively. We provide matching lower bounds for both cases even for the case of full information and for mixed Nash equilibria via an explicit construction. We present an alternative proof of the upper bound of e/(e − 1) for FPAs with fractionally subadditive valuations that reveals the worst-case price distribution, which is used as a building block for the matching lower bound construction. We generalize our results to a general class of item bidding auctions that we call bid-dependent auctions (including FPAs and all-pay auctions) where the winner is always the highest bidder and each bidder's payment depends only on his own bid. Finally, we apply our techniques to discriminatory price multiunit auctions. We complement the results of de Keijzer et al. [2013] for the case of subadditive valuations by providing a matching lower bound of 2. For the case of submodular valuations, we provide a lower bound of 1.109. For the same class of valuations, we were able to reproduce the upper bound of e/(e − 1) using our nonsmooth approach. is to design a (truthful) mechanism that allocates the items in an efficient way in the equilibrium-for instance, so that it maximizes the social welfare, which is the sum of the valuations of the players for the received bundles. Although it is well known that this can be achieved optimally by the VCG mechanism [Vickrey 1961; Clarke 1971; Groves 1973] , unfortunately this might take exponential time in m and n [Nisan and Ronen 1999 Ronen , 2000 ] (unless P = NP). In practice, several simple nontruthful mechanisms are used. The most notable examples are generalized second-price (GSP) auctions used by AdWords [Edelman et al. 2007; Varian 2007] , simultaneous ascending price auctions for wireless spectrum allocation [Milgrom 2000 ], or independent second-price auction (SPAs) on eBay. Furthermore, in these auctions, the expressive power of the buyers is heavily restricted by the bidding language, so they are not able to represent their complex preferences precisely. In light of the preceding information, Christodoulou et al. [2008] proposed the study of simple, nontruthful auctions using the price of anarchy (PoA) [Koutsoupias and Papadimitriou 1999] as a measure of inefficiency of suchauctions. 1 1 In this setting, the PoA is defined as the worst-case ratio of the optimal social welfare over the social welfare obtained in a (Bayesian) Nash equilibrium. 2 Fractionally subadditive valuations are also known as XOS valuations. For definitions of these valuation functions, we refer the reader to Section 2.
Christodoulou et al. REF constructed tight lower bounds for first-price auctions and showed a tight price of anarchy bound of 2 for all-pay auctions with subadditive valuations.
Tight Bounds for the Price of Anarchy of Simultaneous First-Price Auctions
TEAC
Mathematics Computer Science