Wednesday, April 02, 2014, 11:00am
Grad Student, Computer Science Dept, Cornell University
"Efficiency of Simple Mechanisms in Complex Markets"
Abstract: Modern electronic markets, such as auction marketplaces, are complex economic systems that raise many design challenges. The classical computer science approach of designing algorithms for the efficient allocation of resources in such markets is insufficient to capture the incentive issues that arise by the selfish behavior of the entities involved. Addressing such issues requires the blending of techniques from game theory and algorithms to design mechanisms with robust efficiency guarantees under selfish behavior. Such guarantees should be robust to informational and behavioral assumptions and should be valid even in a complex marketplace where many mechanisms are run at the same time and participants have many opportunities to satisfy their resource needs.
In this talk I will present a framework for designing and analyzing simple mechanisms with robust efficiency guarantees. Most importantly guarantees proven via the framework for a single mechanism in isolation directly imply global efficiency guarantees in a market that is composed of many mechanisms running in parallel. Therefore it is a good fit for designing and analyzing distributed resource allocation markets. Furthermore, these guarantees hold even when players have probabilistic beliefs about the competition that they are facing and even if they use adaptive rules to learn how to play, which are realistic assumptions in electronic markets. We show that the analysis of the efficiency of several mechanisms used in practice and analyzed in the theoretical literature fall into our framework, in settings such as combinatorial auctions, multi-unit auctions, bandwidth sharing and position auctions.
Bio: Vasilis Syrgkanis is a PhD student in Computer Science at Cornell University, working under the supervision of Prof. Eva Tardos. His research interests lie at the intersection of Computer Science and Game Theory and more specifically at the algorithmic and game theoretic foundations of electronic markets. He spent the last three summers as an intern at the Microsoft Research labs. He is the recipient of the Simons Foundation fellowship for graduate students in Theoretical Computer Science.
Hosted by: EECS Theoretical Computer Science (TCS) Search Committee