Beyond Worst-Case Analysis in Mechanism Design: Smoothed Analysis and Optimal Transport
- Prof. Jie Zhang, University of Bath
- Time: 2024-05-23 11:00
- Host: Dr. Shaofeng Jiang
- Venue: Room 204, Courtyard No.5, Jingyuan
Abstract
Algorithmic game theory aims to design efficient algorithms to solve complex games, analyze their equilibria, and compare the advantages and disadvantages of different equilibria. Mechanism design focuses on creating incentive-compatible mechanisms that ensure participants reveal their true preferences and information. This report will summarize some recent advancements made by my collaborators and me, covering issues such as matching, facility location, and voting. The emphasis will be on the differences in approximation ratios of various mechanisms under average-case and Bayesian analysis compared to worst-case scenarios, using methods such as smoothed analysis and optimal transport.
Biography
Dr. Jie Zhang is currently an Associate Professor in the Department of Computer Science at the University of Bath, UK. His main research areas include algorithmic game theory, network economics, blockchain protocols, and multi-agent systems. Dr. Zhang is managing research projects funded by the UK's Engineering and Physical Sciences Research Council (EPSRC) and The Leverhulme Trust, and he supervises two postdoctoral researchers and multiple PhD students. He previously served as an Assistant Professor at the University of Southampton, a Research Fellow at the University of Oxford, and a Postdoctoral Researcher at Aarhus University in Denmark. He studied at City University of Hong Kong and was a visiting scholar at Harvard University.