"Finding the optimal mixed strategy to commit to"

Speaker: Vincent Conitzer, Duke University
Date: Wednesday, 20 May 2009
Time: 3pm
Place: Ross 201

Abstract:

Much recent work has focused on the problem of computing Nash
equilibria of normal-form games, which has been shown to be
computationally hard.  The use of Nash equilibrium has other
downsides, such as the equilibrium selection problem and somewhat
tenuous notions of approximation.  In some settings, however, one of
the players can commit to a (possibly mixed) strategy and credibly
communicate this to the other player before the latter makes any
decisions.  While this modified game can of course be modeled as an
extensive-form game, doing so is impractical from a computational
viewpoint.

In this talk, I will discuss results on computing an optimal mixed
strategy to commit to (this can be done in polynomial time in
two-player normal-form games, unlike Nash equilibrium, though it
becomes hard in more general settings) and learning an optimal mixed
strategy to commit to when there is initial uncertainty about the
second player's payoffs.  I will also briefly discuss some real-world
applications in security domains.

Joint work with Joshua Letchford, Kamesh Munagala, and Tuomas Sandholm
(time permitting, I may briefly discuss some new results with Dmytro
Korzhyk and Ronald Parr).  Additional thanks to Milind Tambe and the
USC TEAMCORE group.

Bio:

Vincent Conitzer is an Assistant Professor of Computer Science and
Economics 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. His
research focuses on computational aspects of microeconomics, in
particular game theory, mechanism design, voting/social choice, and
auctions. This work uses techniques from, and includes applications
to, artificial intelligence and multiagent systems. Conitzer received
an Alfred P. Sloan Research Fellowship (2008), an Honorable Mention
for the 2007 ACM Doctoral Dissertation Award, the 2006 IFAAMAS Victor
Lesser Distinguished Dissertation Award, the AAMAS Best Program
Committee Member Award (2006), and an IBM Ph.D. Fellowship (2005). He
is a co-author on papers that received a AAAI-08 Outstanding Paper
Award and the AAMAS-08 Pragnesh Jay Modi Best Student Paper Award.