Publications

• Sorted by Date • Classified by Publication Type • Classified by Research Category •

Structure in the Value Function of Zero-Sum Games of Incomplete Information

Auke 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.

Download

pdf [296.2kB]  

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.

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 Tue Nov 05, 2024 16:13:37 UTC