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



(2015) Structure in the Value Function of Zero-Sum Games of Incomplete Information. In: The Tenth AAMAS Workshop on Multi-Agent Sequential Decision Making in Uncertain Domains (MSDM), Istanbul, Turkey. (Submitted)

WarningThere is a more recent version of this item available.
[img] Text
Wiggers15MSDM.pdf

Download (303kB)

Abstract

In this paper, we introduce plan-time sufficient statistics, rep- resenting 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 re- sult 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.

Item Type: Conference or Workshop Item (Paper)
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Depositing User: Symplectic Admin
Date Deposited: 20 Oct 2015 07:37
Last Modified: 31 Mar 2016 12:09
URI: http://livrepository.liverpool.ac.uk/id/eprint/2032362

Available Versions of this Item

Repository Staff Access