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.

这个项目是探索算法计算多智能体的战略，在精确和近似平衡。背景涉及经济游戏，这些游戏由代理人重复进行，每个代理人都私下观察其他参与者行为的噪音信号。一个完整的表征均衡的这种游戏，失踪，直到最近，介绍了一个有限状态均衡的概念，其中每个球员的战略表示为一个有限状态自动机。通过求解一个部分可观测的马尔可夫决策过程，验证了局中人的策略处于均衡状态。这项研究是建立在这个令人惊讶的和深入的应用决策理论对均衡分析在一个务实的游戏类，这提供了一个大胆的和创新的桥梁决策和博弈理论。它正在设计新的算法，利用部分可观察马尔可夫决策过程的近似和误差有界的解决方案，计算近似有限状态均衡的游戏与increasing dimensions.This research is contributing insights for broader class of games，如随机游戏噪声信号。这项研究的跨学科成果正在被整合到多智能体决策的课程和会议教程中进行传播。正在与日本著名的多智能体研究人员建立新的国际研究合作关系。这项研究正在将决策和博弈论的学科结合起来，实现互利共赢。主要成果包括解决高度复杂游戏的可扩展算法，从而有助于理解不确定性下的复杂交互。应用程序包括分析拍卖没有公开信息发布，公司之间的隐蔽价格战，管理资源拥塞。