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

Wiggers, Auke J, Oliehoek, Frans A ORCID: 0000-0003-4372-5055 and Roijers, Diederik M (2016) Structure in the Value Function of Two-Player Zero-Sum Games of Incomplete Information. In: The Tenth AAMAS Workshop on Multi-Agent Sequential Decision Making in Uncertain Domains (MSDM), Istanbul, Turkey. (Submitted)

Text Wiggers15MSDM.pdf - Unspecified 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:	?? QA75 ??
Depositing User:	Symplectic Admin
Date Deposited:	20 Oct 2015 07:37
Last Modified:	17 Dec 2022 03:15
Related URLs:	Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/2032362

Available Versions of this Item

• Structure in the Value Function of Two-Player Zero-Sum Games of Incomplete Information. (deposited 20 Oct 2015 07:37) [Currently Displayed]
  • Structure in the Value Function of Two-Player Zero-Sum Games of Incomplete Information. (deposited 26 Nov 2015 09:16)