Publications• Sorted by Date • Classified by Publication Type • Classified by Research Category • Structure in the Value Function of Zero-Sum Games of Incomplete InformationAuke J. Wiggers, Frans A. Oliehoek, and Diederik M. Roijers. Structure in the Value Function of Zero-Sum Games of Incomplete Information. In Proceedings of the Tenth AAMAS Workshop on Multi-Agent Sequential Decision Making in Uncertain Domains (MSDM), May 2015. DownloadAbstractIn this paper, we introduce plan-time sufficient statistics, representing probability distributions over joint sets of private information, for zero-sum games of incomplete information. We define a family of zero-sum Bayesian Games (zs-BGs), of which the members share all elements but the plan-time statistic. Using the fact that the statistic can be decomposed into a marginal and a conditional term, we prove that the value function of the family of zs-BGs exhibits concavity in marginal-space of the maximizing agent and convexity in marginal-space of the minimizing agent. We extend this result to sequential settings with a dynamic state, i.e., zero-sum Partially Observable Stochastic Games (zs-POSGs), in which the statistic is a probability distribution over joint action- observation histories. First, we show that the final stage of a zs-POSG corresponds to a family of zs-BGs. Then, we show by induction that the convexity and concavity properties can be extended to every time-step of the zs-POSG. BibTeX Entry@inproceedings{Wiggers15MSDM, title = {Structure in the Value Function of Zero-Sum Games of Incomplete Information}, author = {Auke J. Wiggers and Frans A. Oliehoek and Diederik M. Roijers}, booktitle = MSDM15, year = 2015, month = may, keywords = {workshop}, abstract = { In this paper, we introduce plan-time sufficient statistics, representing probability distributions over joint sets of private information, for zero-sum games of incomplete information. We define a family of zero-sum Bayesian Games (zs-BGs), of which the members share all elements but the plan-time statistic. Using the fact that the statistic can be decomposed into a marginal and a conditional term, we prove that the value function of the family of zs-BGs exhibits concavity in marginal-space of the maximizing agent and convexity in marginal-space of the minimizing agent. We extend this result to sequential settings with a dynamic state, i.e., zero-sum Partially Observable Stochastic Games (zs-POSGs), in which the statistic is a probability distribution over joint action- observation histories. First, we show that the final stage of a zs-POSG corresponds to a family of zs-BGs. Then, we show by induction that the convexity and concavity properties can be extended to every time-step of the zs-POSG. } }
Generated by
bib2html.pl
(written by Patrick Riley) on
Wed Sep 18, 2024 14:30:51 UTC |