Making the Best of Limited Memory in Multi-Player Discounted Sum Games

Gupta, Anshul, Schewe, Sven ORCID: 0000-0002-9093-9518 and Wojtczak, Dominik ORCID: 0000-0001-5560-0546 (2015) Making the Best of Limited Memory in Multi-Player Discounted Sum Games. In: 6th International Symposium on Games, Automata, Logics and Formal Verification (GandALF).

Text paper123.pdf - Unspecified Download (158kB)

Abstract

In this paper, we establish the existence of optimal bounded memory strategy profiles in multi-player discounted sum games. We introduce a non-deterministic approach to compute optimal strategy profiles with bounded memory. Our approach can be used to obtain optimal rewards in a setting where a powerful player selects the strategies of all players for Nash and leader equilibria, where in leader equilibria the Nash condition is waived for the strategy of this powerful player. The resulting strategy profiles are optimal for this player among all strategy profiles that respect the given memory bound, and the related decision problem is NP-complete. We also provide simple examples, which show that having more memory will improve the optimal strategy profile, and that sufficient memory to obtain optimal strategy profiles cannot be inferred from the structure of the game.

Item Type:	Conference or Workshop Item (Unspecified)
Additional Information:	In Proceedings GandALF 2015, arXiv:1509.06858
Uncontrolled Keywords:	cs.GT, cs.GT
Depositing User:	Symplectic Admin
Date Deposited:	01 Dec 2015 16:57
Last Modified:	17 Dec 2022 01:27
DOI:	10.4204/EPTCS.193.2
Publisher's Statement :	© A. Gupta, S. Schewe, and D. Wojtczak This work is licensed under the Creative Commons Attribution License.
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/2040087