Abstract: In many settings, most notably two-person zero-sum games, game theory provides particularly robust solution concepts. However, in most interesting AI applications, it has been prohibitively complex to find such solutions because the state space is extremely large. In this talk I will discuss our work on taming the complexity over the last three years, focusing on sequential incomplete-information games. First, I introduce automated abstraction algorithms. I will cover lossless (i.e., equilibrium-preserving) algorithms, as well as algorithms that are lossy, but which yield much smaller games that retain the most important features of the original game. Second, I present algorithms for finding approximate equilibria. They are based on recent theoretical advances in non-smooth convex optimization, and provide drastic improvements over prior (linear programming-based) algorithms for finding approximate equilibria. Combining these two streams, we enable the application of game theory to games that are many orders of magnitude larger than previously solvable. In particular, we find near-optimal solutions for a full four-round model of (Heads'Up Limit) Texas Hold'em poker, and demonstrate that the resulting player beats prior computer poker players.

This is joint work with Andrew Gilpin, and parts are also joint with Troels Bjerre Sørensen, Javier Pena, and Samid Hoda.

Short Bio: Tuomas Sandholm is Professor in the Computer Science Department at Carnegie Mellon University. He received the Ph.D. and M.S. degrees in computer science from the University of Massachusetts at Amherst in 1996 and 1994. He earned an M.S. (B.S. included) with distinction in Industrial Engineering and Management Science from the Helsinki University of Technology, Finland, in 1991. He has published over 250 technical papers on electronic commerce; game theory; artificial intelligence; multiagent systems; auctions and exchanges; automated negotiation and contracting; coalition formation; voting; safe exchange; normative models of bounded rationality; resource-bounded reasoning; machine learning; networks; and combinatorial optimization. He has 17 years of experience building optimization-based electronic marketplaces, and several of his systems have been commercially fielded. He is also Founder, Chairman, and Chief Scientist of CombineNet, Inc., which has fielded over 400 large-scale generalized combinatorial auctions, with over $25 billion in total spend and over $3.2 billion in generated savings. He received the National Science Foundation Career Award in 1997, the inaugural ACM Autonomous Agents Research Award in 2001, the Alfred P. Sloan Foundation Fellowship in 2003, and the IJCAI Computers and Thought Award in 2003.