Worst-case analysis for a leader–follower partially observable stochastic game

Yanling Chang and Chelsea C. White

IISE Transactions, 2022, vol. 54, issue 4, 376-389

Abstract: Although Partially Observable Stochastic Games (POSGs) provide a powerful mathematical paradigm for modeling multi-agent dynamic decision making under uncertainty and partial information, they are notoriously hard to solve (e.g., the common-payoff POSGs are NEXP-complete) and have an extensive data requirement on each agent. The latter may represent a serious challenge to a defending agent if he/she has limited knowledge of its adversary. A worst-case analysis can significantly reduce both model computational complexity and data requirements regarding the adversary; further, a (near) optimal worst-case policy may represent a useful guide for action selection for risk-averse defenders (e.g., benchmarks). This article introduces a worst-case analysis to a leader–follower POSG where: (i) the defending leader has little knowledge of the adversarial follower’s reward structure, level of rationality, and process for gathering and transmitting data relevant for decision making; (ii) the objective is to determine a best worst-case value function and a control strategy for the leader. We show that the worst-case assumption transforms this POSG into a more computationally tractable single-agent problem with a simple sufficient statistic. However, the value function can be non-convex, in contrast with the value function of a partially observable Markov decision process. We design an iterative solution procedure for computing a lower bound of the leader’s value function and its control policy for the finite horizon case. This approach was numerically illustrated to support decision making in a security example.

Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1080/24725854.2021.1955167 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:taf:uiiexx:v:54:y:2022:i:4:p:376-389

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/uiie20

DOI: 10.1080/24725854.2021.1955167

Access Statistics for this article

IISE Transactions is currently edited by Jianjun Shi

More articles in IISE Transactions from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().