The VI AMMCS International Conference
Waterloo, Ontario, Canada | August 14-18, 2023
AMMCS 2023 Plenary Talk
The State of Representing and Solving Games
Tuomas Sandholm (Carnegie Mellon University)
Game-theoretic solution concepts provide meticulous definitions of how rational parties should act. That has enabled humans to think rigorously about strategic interactions, leading to game theory revolutionizing many fields such as economics, political science, and biology. So far, game theory has mainly been used for reasoning by humans. The models have therefore been quite stylized and coarse: small enough for humans to solve in their heads or by paper and pen. The goal has been to draw insights from such models, which humans then judiciously apply to the drastically more complicated real world. The boundaries of game theory have thus been defined by the limits of humans. However, many - arguably most - important game classes lie beyond those boundaries. There is now another, more nascent, use of game theory that goes beyond human intelligence. The game is computationally solved in its full detail - or else in a large, faithful abstraction thereof - as opposed to solving a small, stylized version to obtain insights for humans. Novel approaches, game representations, and algorithms from the last 18 years have enabled game theory to advance significantly beyond its traditional boundaries. I will discuss that state of the art. The talk is based on my presentation at the December 2021 Nobel Symposium: 100 Years of Game Theory, and also includes brand new results.
Tuomas Sandholm is Angel Jordan University Professor of Computer Science at Carnegie Mellon University and a serial entrepreneur. His research focuses on the convergence of artificial intelligence, economics, and operations research. He is Co-Director of CMU AI, and Founder and Director of the Electronic Marketplaces Laboratory. In parallel with his academic career, he was Founder, Chairman, first CEO, and CTO/Chief Scientist of CombineNet, Inc. from 1997 until its acquisition in 2010. During this period the company commercialized over 800 of the world's largest-scale generalized combinatorial multi-attribute auctions, with over $60 billion in total spend and over $6 billion in generated savings. Since 2010, his algorithms have been running the national kidney exchange for the United Network for Organ Sharing, where they autonomously make the kidney exchange transplant plan for 80% of U.S. transplant centers together each week. He also co-invented never-ending altruist-donor-initiated chains and his algorithms created the first such chain. Such chains have become the main modality of kidney exchange worldwide and have led to around 10,000 life-saving transplants.
He invented liver lobe and multi-organ exchanges, and the first liver-kidney swap took place in 2019. Sandholm has developed the leading algorithms for several general classes of game. The team that he leads is the multi-time world champion in computer heads-up no-limit Texas hold'em, which is the main benchmark and decades-open challenge problem for testing application-independent algorithms for solving imperfect-information games. Their AI Libratus became the first and only AI to beat top humans at that game. Then their AI Pluribus became the first and only AI to beat top humans at the multi-player game. That is the first superhuman milestone in any game beyond two-player zero-sum games. He is Founder and CEO of Strategic Machine, Inc., which provides solutions for strategic reasoning under imperfect information in a broad set of applications ranging from poker to other recreational games to business strategy, negotiation, strategic pricing, finance, cybersecurity, physical security, auctions, political campaigns, and medical treatment planning. He is also Founder and CEO of Strategy Robot, Inc., which focuses on defense applications.
He is also Founder and CEO of Optimized Markets, Inc., which is bringing a new optimization-powered paradigm to advertising campaign sales, pricing, and scheduling. He holds a Ph.D. and M.S. in computer science and a Dipl. Eng. (M.S. with B.S. included) with distinction in Industrial Engineering and Management Science. Among his many honors are the AAAI Award for AI for the Benefit of Humanity, Minsky Medal, IJCAI McCarthy Award, AAAI/IAAI Engelmore Award, IJCAI Computers and Thought Award, inaugural ACM Autonomous Agents Research Award, CMU's Allen Newell Award for Research Excellence, Sloan Fellowship, NSF Career Award, Carnegie Science Center Award for Excellence, and Edelman Laureateship. He is Fellow of the ACM, AAAI, INFORMS, and AAAS. He holds an honorary doctorate from the University of Zurich.
He invented liver lobe and multi-organ exchanges, and the first liver-kidney swap took place in 2019. Sandholm has developed the leading algorithms for several general classes of game. The team that he leads is the multi-time world champion in computer heads-up no-limit Texas hold'em, which is the main benchmark and decades-open challenge problem for testing application-independent algorithms for solving imperfect-information games. Their AI Libratus became the first and only AI to beat top humans at that game. Then their AI Pluribus became the first and only AI to beat top humans at the multi-player game. That is the first superhuman milestone in any game beyond two-player zero-sum games. He is Founder and CEO of Strategic Machine, Inc., which provides solutions for strategic reasoning under imperfect information in a broad set of applications ranging from poker to other recreational games to business strategy, negotiation, strategic pricing, finance, cybersecurity, physical security, auctions, political campaigns, and medical treatment planning. He is also Founder and CEO of Strategy Robot, Inc., which focuses on defense applications.
He is also Founder and CEO of Optimized Markets, Inc., which is bringing a new optimization-powered paradigm to advertising campaign sales, pricing, and scheduling. He holds a Ph.D. and M.S. in computer science and a Dipl. Eng. (M.S. with B.S. included) with distinction in Industrial Engineering and Management Science. Among his many honors are the AAAI Award for AI for the Benefit of Humanity, Minsky Medal, IJCAI McCarthy Award, AAAI/IAAI Engelmore Award, IJCAI Computers and Thought Award, inaugural ACM Autonomous Agents Research Award, CMU's Allen Newell Award for Research Excellence, Sloan Fellowship, NSF Career Award, Carnegie Science Center Award for Excellence, and Edelman Laureateship. He is Fellow of the ACM, AAAI, INFORMS, and AAAS. He holds an honorary doctorate from the University of Zurich.