On the Tradeoff between Efficiency and Strategyproofness
Department of Computer Science and Mathematics
Technische Universitat Munche
COM1 Level 2
Video Conference Room, COM1-02-13
Abstract:
Two fundamental notions in microeconomic theory are efficiency--no agent can be made better off without making another one worse off--and strategyproofness--no agent can obtain a more preferred outcome by misrepresenting his preferences. The conflict between these two notions is already apparent in Gibbard and Satterthwaite's seminal theorem, which states that the only single-valued social choice functions that satisfy non-imposition--a weakening of efficiency--and strategyproofness are dictatorships. This talk will be concerned with efficiency and strategyproofness in the context of social decision schemes, i.e., functions that map a preference profile to a probability distribution (or lottery) over a fixed set of alternatives. Depending on how preferences over alternatives are extended to preferences over lotteries, there are varying degrees of efficiency and strategyproofness. I will discuss positive results for random serial dictatorship and maximal lotteries as well as a number of impossibility theorems, one of which was recently shown using computer-aided solving techniques.
Biodata:
Felix Brandt is a professor of computer science and mathematics at Technische Universitat Munchen, where he received his PhD in 2003. Prior to this appointment, he spent two years as a post-doc at Carnegie Mellon University and Stanford University and five years as an assistant professor at Ludwig-Maximilians-Universitat Munchen. He has received a DFG Heisenberg fellowship (2010) and a DFG Emmy-Noether fellowship (2005). Felix is an elected member of the Council of the Society for Social Choice and Welfare and serves on the editorial boards of the ACM Transactions on Economics and Computation (TEAC), the Journal of Artificial Intelligence Research (JAIR), the Journal of Autonomous Agents and Multiagent Systems (JAAMAS), and Social Choice and Welfare (SCW). In 2016, he co-edited the Handbook of Computational Social Choice with Vincent Conitzer, Ulle Endriss, Jerome Lang, and Ariel Procaccia. His research interests include various topics in computational (and non-computational) social choice and game theory.