Mohammad Taghi Hajiaghayi

Associate Professor

Computing Equilibria of Blotto and Other Games

  Computer Engineering Department, Floor 4, Kharazmi Hall
  Wednesday, 30 December 2015
  10:30 - 11:30

Abstract

We study the problem of computing Nash equilibria of zero-sum games. Many natural zero-sum games have exponentially many strategies, but highly structured payoffs. For example, in the well-studied Colonel Blotto game (introduced by Borel in 1921), players must divide a pool of troops among a set of battle-fields with the goal of winning (i.e., having more troops in) a majority. The Colonel Blotto game is commonly used for analyzing a wide range of applications from the U.S presidential election, to innovative technology competitions, to advertisement, to sports. However, because of the size of the strategy space, standard methods for computing equilibria of zero-sum games fail to be computationally feasible. Indeed, despite its importance, only few solutions for special variants of the problem are known.

In this talk we show how to compute equilibria of Colonel Blotto games. Moreover, our approach takes the form of a general reduction: to find a Nash equilibrium of a zero-sum game, it suffices to design a separation oracle for the strategy polytope of any bilinear game that is payoff-equivalent. We then apply this technique to obtain the first polytime algorithms for a variety of games.

Bio

Mohammad T. Hajiaghayi is the Jack and Rita G. Minker Associate Professor of Computer Science in the Department of Computer Science.

In addition, he holds a Research Affiliate position in the MIT Computer Science and Artificial Intelligence Laboratory (CSAIL) and is a permanent member of the Center for Discrete Mathematics and Theoretical Computer Science (DIMACS) at Rutgers University.

Hajiaghayi’s research interests are algorithmic game theory and combinatorial auctions, network design, combinatorial optimizations and approximation algorithms, fixed-parameter algorithms, algorithmic graph theory, distributed and mobile computing, and computational geometry and embeddings. He has published more than 110 papers in top conferences and journals of computer science, won a few best paper awards, and served in program committees or editorial boards of several well-known international conferences and journals.

Hajiaghayi received a National Science Foundation (NSF) CAREER Award in 2010, a Google Faculty Research Award in 2010, an ONR Young Investigator Award in 2011, and the University of Maryland Research and Scholarship Award (RASA) in 2011. He won best paper awards at the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) 2010, the International Symposium on Algorithms and Computation (ISAAC) 2006, and the Robocup 2001 Conference.

Before joining the University of Maryland, he was a senior researcher in the Algorithms and Theoretical Computer Science group at AT&T Labs and still serves as a research consultant.

Prior to that, Hajiaghayi was a one-year postdoctoral fellow in the School of Computer Science at Carnegie Mellon University (with the ALADDIN project) and a one-year postdoctoral associate at MIT CSAIL, where he also earned his doctorate in applied mathematics in 2005. While earning his doctorate, he also spent some time at IBM Research centers and Microsoft Research centers. Hajiaghayi received his M.Sc. in computer science from the University of Waterloo in 2001 and his B.Sc. in computer engineering from Sharif University of Technology in 2000.