---
_id: '3499'
abstract:
- lang: eng
text: 'We study infinite stochastic games played by n-players on a finite graph
with goals specified by sets of infinite traces. The games are concurrent (each
player simultaneously and independently chooses an action at each round), stochastic
(the next state is determined by a probability distribution depending on the current
state and the chosen actions), infinite (the game continues for an infinite number
of rounds), nonzero-sum (the players’ goals are not necessarily conflicting),
and undiscounted. We show that if each player has an upward-closed objective,
then there exists an ε-Nash equilibrium in memoryless strategies, for every ε>0;
and exact Nash equilibria need not exist. Upward-closure of an objective means
that if a set Z of infinitely repeating states is winning, then all supersets
of Z of infinitely repeating states are also winning. Memoryless strategies are
strategies that are independent of history of plays and depend only on the current
state. We also study the complexity of finding values (payoff profile) of an ε-Nash
equilibrium. We show that the values of an ε-Nash equilibrium in nonzero-sum concurrent
games with upward-closed objectives for all players can be computed by computing
ε-Nash equilibrium values of nonzero-sum concurrent games with reachability objectives
for all players and a polynomial procedure. As a consequence we establish that
values of an ε-Nash equilibrium can be computed in TFNP (total functional NP),
and hence in EXPTIME. '
acknowledgement: This research was supported in part by the NSF grants CCR-0225610
and CCR- 0234690, and by the SNSF under the Indo-Swiss Joint Research Programme.
alternative_title:
- 'LNCS '
author:
- first_name: Krishnendu
full_name: Krishnendu Chatterjee
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
citation:
ama: 'Chatterjee K. Nash equilibrium for upward-closed objectives. In: Vol 4207.
Springer; 2006:271-286. doi:10.1007/11874683_18'
apa: 'Chatterjee, K. (2006). Nash equilibrium for upward-closed objectives (Vol.
4207, pp. 271–286). Presented at the CSL: Computer Science Logic, Springer. https://doi.org/10.1007/11874683_18'
chicago: Chatterjee, Krishnendu. “Nash Equilibrium for Upward-Closed Objectives,”
4207:271–86. Springer, 2006. https://doi.org/10.1007/11874683_18.
ieee: 'K. Chatterjee, “Nash equilibrium for upward-closed objectives,” presented
at the CSL: Computer Science Logic, 2006, vol. 4207, pp. 271–286.'
ista: 'Chatterjee K. 2006. Nash equilibrium for upward-closed objectives. CSL: Computer
Science Logic, LNCS , vol. 4207, 271–286.'
mla: Chatterjee, Krishnendu. Nash Equilibrium for Upward-Closed Objectives.
Vol. 4207, Springer, 2006, pp. 271–86, doi:10.1007/11874683_18.
short: K. Chatterjee, in:, Springer, 2006, pp. 271–286.
conference:
name: 'CSL: Computer Science Logic'
date_created: 2018-12-11T12:03:39Z
date_published: 2006-09-28T00:00:00Z
date_updated: 2021-01-12T07:43:52Z
day: '28'
doi: 10.1007/11874683_18
extern: 1
intvolume: ' 4207'
month: '09'
page: 271 - 286
publication_status: published
publisher: Springer
publist_id: '2888'
quality_controlled: 0
status: public
title: Nash equilibrium for upward-closed objectives
type: conference
volume: 4207
year: '2006'
...