We study two standard multi-unit auction formats for allocating multiple units of a single good to multi-demand bidders. The first one is the Discriminatory Auction, which charges every winner his winning bids. The second is the Uniform Price Auction, which determines a uniform price to be paid per unit. Variants of both formats find applications ranging from the allocation of state bonds to investors, to online sales over the internet. For these formats, we consider two bidding interfaces: (i) standard bidding, which is most prevalent in the scientific literature, and (ii) uniform bidding, which is more popular in practice. In this work, we evaluate the economic inefficiency of both multi-unit auction formats for both bidding interfaces, by means of upper and lower bounds on the Price of Anarchy for pure Nash equilibria and mixed Bayes-Nash equilibria. Our developments improve significantly upon bounds that have been obtained recently for submodular valuation functions. Also, for the first time, we consider bidders with subadditive valuation functions under these auction formats. Our results signify near-efficiency of these auctions, which provides further justification for their use in practice.
Additional Metadata
Keywords Auctions, Price of Anarchy, Game Theory
ACM Miscellaneous (acm F.2.m), PROBABILITY AND STATISTICS (acm G.3), SOCIAL AND BEHAVIORAL SCIENCES (acm J.4)
THEME Logistics (theme 3)
Editor H.L. Bodlaender , G.F. Italiano
Persistent URL dx.doi.org/10.1007/978-3-642-40450-4_33
Conference European Symposium on Algorithms
Citation
de Keijzer, B, Markakis, V, Schäfer, G, & Telelis, O. (2013). Inefficiency of Standard Multi-unit Auctions. In H.L Bodlaender & G.F Italiano (Eds.), . doi:10.1007/978-3-642-40450-4_33