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

EAGER：用于计算有限状态平衡的决策理论和可扩展算法

• 批准号: 1346942
• 负责人: Prashant Doshi
• 金额: $ 15.02万
• 依托单位: University of Georgia Research Foundation Inc
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2013
• 资助国家: 美国
• 起止时间: 2013-08-01 至 2016-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1346942&HistoricalAwards=false
• 关键词: EAGER; Decision; Theoretic; Scalable; Algorithms

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.

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