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

博弈论解决方案的概念提供了一个合理的定义，理性的代理应该如何行动，并在多代理设置更新他们的信念。在大型不完全信息博弈中计算此类解决方案的能力是众多应用程序（如谈判、网络安全、物理安全、医学和拍卖）中的关键能力。为了实现这种战略上的健壮性智能，解决方案概念必须伴随着寻找此类解决方案的计算技术。只有这样，这些定义才真正具有可操作性。PI为此提出了一系列技术。所提出的工作将使博弈论成为分析大规模设置的操作工具。该方法与应用无关，因此具有极其广泛的适用性。为了确保可扩展性，这些技术将在非常大规模的游戏中进行基准测试。这是通往软件代理代表人类和公司进行商业活动，或为他们提供建议的道路。这可以通过更好的决策来增加社会福利（或增加其他衡量结果可取性的指标）。它还有助于实现更广泛和更公平的准入，因为它有助于将经验不足/受教育程度较低的人/公司与专业市场参与者置于平等地位。更广泛的访问反过来又进一步增加了（电子）商务的好处，并且这些好处在社会各阶层之间得到更公平的分配。所提出的算法还可以通过以下方式帮助其他人进行研究：1)为不正确的假设提供反例（通过快速生成和解决感兴趣的类中的游戏，并观察均衡的属性）；2)通过解决大量案例帮助指导新定理的制定。提议的研究有四个高级技术方面：(1)PI将利用他最近的突破（与S. Singh），使游戏抽象算法（必须是有损的，以便创建足够小的模型来解决）创建具有可利用性界限的策略。他建议将框架扩展到一般的顺序游戏，开发更好的动作和状态抽象算法，并研究可扩展性和建模目的的抽象。他还提出了创建不完美召回抽象的算法，这些抽象具有边界，具有潜在意识，支持有效的分布式均衡发现，并且具有紧凑的表示。此外，他还提出了最佳行动抽象技术，以及在均衡发现和博弈策略执行过程中进行抽象的方法。(2)他提出了如何将对手的行为映射到抽象模型的方向。他还计划确定为什么让一个人的策略不那么随机化——令人惊讶的是——是有益的。(3)他提出了反事实后悔均衡寻找算法的并行化和采样技术，以及解决不完美回忆博弈抽象的方法。他还提出了有效、详细的终局和中局解决技巧，以及利用终局解决找到整个游戏平衡的技巧。他还提出了一种新的计算可行的平衡细化方法。(4)他提出了结合博弈论推理和对手建模的算法的主要可扩展性增强。他根据最近的突破（与S. Ganzfried合作）提出了新的方向，该突破表明完全安全的对手利用是可能的。他还建议研究开发、利用和探索之间的三方权衡。

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.