On the Inefficiency of Standard Multi-unit Auction Formats
In this work, Prof. Vangelis Markakis studies two standard multi-unit auction formats for allocating multiple units of a single good to multi-demand bidders. The first one is the Discriminatory Price 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 bonds to investors, to online sales over the internet, facilitated by popular online brokers.
For these formats, Dr. Markakis and his collaborators consider two bidding interfaces: (i) standard bidding, which is most prevalent in the scientific literature, and (ii) uniform bidding, which is the most widely used interface in practice. The research team evaluates the economic inefficiency of the two formats for both bidding interfaces, by means of upper and lower bounds on the Price of Anarchy for pure equilibria and mixed Bayes-Nash equilibria. Their results for bidders with submodular valuations show that the efficiency loss (i.e., the loss in social welfare attained at an equilibrium) in these auction formats is bounded by a small constant, improving upon bounds that have been obtained in the literature.
Moreover, the researchers also consider bidders with subadditive valuation functions and obtain constant upper bounds there as well.
This is based on joint works with Bart de Keijzer, Guido Schaefer and Orestis Telelis.
Speaker
Vangelis Markakis is an Assistant Professor in the Department of Informatics and a member of the Theory Group at the Athens University of Economics and Business in Athens, Greece. He received a Bachelor's degree from the National Technical University of Athens in 2000 and received his Ph.D. in Theoretical Computer Science from Georgia Tech in 2005. After graduation, Prof. Markakis completed postdoc positions at the University of Toronto and CWI, the national research center for math and computer science in Amsterdam. He has been with Athens University since 2009.
Prof. Markakis' research interests lie in the areas of analysis of algorithms, approximation algorithms, game theory, mechanism design and social networks. Over the last few years, his work has focused on algorithmic questions in the context of game theory and economics, such as the computation of equilibria and other solution concepts in cooperative and noncooperative games, as well as on resource allocation and related optimization problems such as allocations of indivisible goods in auctions or fair division contexts.