EAGER: Decision-Theoretic and Scalable Algorithms for Computing Finite State Equilibrium

这个项目正在探索计算处于精确和近似均衡的多智能体策略的算法。这一背景涉及代理人反复玩的经济游戏，每个代理人私下里都会观察到关于其他玩家行为的嘈杂信号。直到最近还没有对这类博弈的均衡进行完整的刻画，引入了有限状态均衡的概念，其中每个参与者的策略都被表示为有限状态自动机。通过求解一个部分可观测的马尔可夫决策过程，验证了玩家的策略是均衡的。这项研究是建立在这一令人惊讶的决策理论对实用博弈类中的均衡分析的深入应用上的，这为决策和博弈论之间提供了一座大胆而创新的桥梁。它正在设计新的算法，利用部分可观测的马尔可夫决策过程的近似解和误差有界解来计算增加维度的博弈的近似有限状态均衡。这项研究为更广泛的博弈类别，如具有噪声信号的随机博弈提供了见解。这项研究的跨学科成果正在被纳入关于多主体决策的课程和会议教程，以供传播。与日本著名的多智能体研究人员建立了新的国际研究合作。这项研究将决策和博弈论的学科结合在一起，互惠互利。关键成果包括用于解决高度复杂游戏的可扩展算法，从而有助于理解不确定条件下的复杂交互。应用包括分析不公开信息的拍卖，公司之间的秘密价格战，以及管理资源拥堵。

This project is exploring algorithms for computing multiagent strategies that are in exact and approximate equilibrium. The context involves economic games that are played repeatedly by agents each of whom privately observes noisy signals about other players' actions. A complete characterization of equilibria for such games, missing until recently, introduces the concept of a finite state equilibrium in which each player's strategy is represented as a finite state automaton. Players' strategies are verified to be in equilibrium by solving a partially observable Markov decision process. The research is building on this surprising and deep application of decision theory toward equilibrium analysis in a pragmatic class of games, which provides a bold and innovative bridge between decision and game theories. It is designing novel algorithms that utilize approximate and error-bounded solutions of partially observable Markov decision processes for computing approximate finite state equilibrium in games with increasing dimensions.This research is contributing insights for broader classes of games such as stochastic games with noisy signals. The interdisciplinary outcomes of this research are being integrated into courses and conference tutorials on multiagent decision making for dissemination. New international research collaborations with eminent multiagent researchers in Japan are being established.This research is bringing together the disciplines of decision and game theories with mutual benefit. Key outcomes include scalable algorithms for solving highly complex games thereby contributing to the understanding of sophisticated interactions under uncertainty. Applications include analyzing auctions without release of public information, covert price wars between firms, and managing resource congestion.