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

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

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.