RI: Small: Computational Techniques for Large Multi-Step Incomplete-Information Games

Carnegie Mellon University, Pittsburgh PA

Investigators

Abstract

Game-theoretic solution concepts provide a sound definition of how rational agents should act and update their beliefs in multiagent settings. The ability to compute such solutions in large incomplete-information games is a key capability in a myriad of applications, such as in negotiations, cybersecurity, physical security, medicine, and auctions. To achieve such strategically robust intelligence, the solution concepts must be accompanied by computational techniques for finding such solutions. Only then will the definitions be truly operational. The PI proposes a host of techniques for this. The proposed work will enable game theory to be an operational tool for analyzing large-scale settings. The methodology is application independent, so it has extremely broad applicability. To ensure scalability, the techniques will be benchmarked on very-large-scale games. This is on a path to a vision where software agents conduct commerce on behalf of humans and companies, or advise them. That leads to increased social welfare (or increase in other measures of desirability of outcomes) through better decision making. It also enables broader and fairer access because it helps put less experienced/educated people/companies on an equal footing with expert market participants. Broader access, in turn, increases the benefits of (electronic) commerce further, and the benefits get distributed more fairly across segments of society. The proposed algorithms can also help others in their research by 1) providing counter-examples to incorrect hypotheses (by rapidly generating and solving games within the class of interest, and observing properties of the equilibria) and 2) helping guide the formulation of new theorems by solving numerous cases. The proposed research has four high-level technical prongs: (1) The PI will leverage his recent breakthrough (with S. Singh) that enables game abstraction algorithms (which have to be lossy in order to create small enough models to solve) to create strategies that have bounds on exploitability. He proposes to broaden the framework to general sequential games, to develop better action and state abstraction algorithms, and to study abstraction both for scalability and modeling purposes. He also proposes algorithms that create imperfect-recall abstractions that have bounds, are potential-aware, support efficient distributed equilibrium finding, and have compact representations. In addition, he proposes techniques for optimal action abstraction and ways to do abstraction during equilibrium finding and during execution of the game strategy. (2) He proposes directions around the question of how opponents' actions should be mapped to the abstract model. He also plans to determine why making one's strategy less randomized can---surprisingly---be beneficial. (3) He proposes parallelization and sampling techniques for the counterfactual regret equilibrium-finding algorithm, and ways to solve imperfect-recall game abstractions. He also proposes techniques for effective, detailed endgame and midgame solving, as well as techniques that leverage endgame solving in finding an equilibrium for the entire game. He also proposes a new computationally feasible equilibrium refinement. (4) He proposes major scalability enhancements to algorithms that combine game-theoretic reasoning and opponent modeling. He proposes new directions based on a recent breakthrough (with S. Ganzfried) that shows that fully safe opponent exploitation is possible. He also proposes to study the three-way tradeoff among exploitation, exploitability, and exploration.