Timeability of Extensive-Form Games

Speaker:Vince Conitzer
Date: Tuesday, October 4, 2016
Time: 11:45am - 1:00pm
Location: Soc Sci Building 113, Duke
Lunch will be served prior to the talk.


Extensive-form games constitute the standard representa- tion scheme for games with a temporal component. But do all extensive-form games correspond to protocols that we can implement in the real world? We often rule out games with imperfect recall, which prescribe that an agent forget something that she knew before. In this paper, we show that even some games with perfect recall can be problem- atic to implement. Specifically, we show that if the agents have a sense of time passing (say, access to a clock), then some extensive-form games can no longer be implemented; no matter how we attempt to time the game, some informa- tion will leak to the agents that they are not supposed to have. We say such a game is not exactly timeable. We pro- vide easy-to-check necessary and sufficient conditions for a game to be exactly timeable. Most of the technical depth of the paper concerns how to approximately time games, which we show can always be done, though it may require large amounts of time. Specifically, we show that some games require time proportional to the power tower of height pro- portional to the number of players, which in practice would make them untimeable. We hope to convince the reader that timeability should be a standard assumption, just as perfect recall is today. Besides the conceptual contribution to game theory, we show that timeability has implications for onion routing protocols.


Vincent Conitzer is the Kimberly J. Jenkins University Professor of New Technologies and Professor of Computer Science, Professor of Economics, and Professor of Philosophy at Duke University. He received Ph.D. (2006) and M.S. (2003) degrees in Computer Science from Carnegie Mellon University, and an A.B. (2001) degree in Applied Mathematics from Harvard University. Most of his research is on artificial intelligence (especially multiagent systems) and economic theory (especially game theory, social choice, and mechanism design). Conitzer has received the Social Choice and Welfare Prize (2014), a Presidential Early Career Award for Scientists and Engineers (PECASE), the IJCAI Computers and Thought Award, an NSF CAREER award, the inaugural Victor Lesser dissertation award, an honorable mention for the ACM dissertation award, and several awards for papers and service at the AAAI and AAMAS conferences. He has also been named a Guggenheim Fellow, a Kavli Fellow, a Bass Fellow, a Sloan Fellow, and one of AI's Ten to Watch. Conitzer and Preston McAfee are the founding Editors-in-Chief of the ACM Transactions on Economics and Computation (TEAC).