Invited Talk
Non-zero Sum Games and Nash Equilibria
Rupak Majumdar
UCLA
Abstract
The interaction of several agents is naturally modeled as
non-cooperative games.
The simplest, and most common interpretation of a non-cooperative game
is that there is a single interaction among the players
("one-shot"), after which the payoffs are decided and the game
ends.
However, many, strategic endeavors occur over time, and
in stateful manner.
That is, the games progress over time, and the current game is decided
based on the history of the interactions.
Infinite stochastic games form a natural and general model for such interactions.
A stochastic game is played over a finite state space, and is played in
rounds.
In each round, each player chooses an available action out of a finite
set of actions simultaneously
with and independently from all other players, and the game moves to a
new state under a possibly probabilistic transition relation based on
the current state and the joint actions.
For the verification and control of reactive systems, such games are
infinite: play continues for an infinite number of rounds, giving rise
to an infinite sequence of states, called the outcome of the
game. The payoff function maps each outcome to 0 or 1.
While infinite "zero sum" games (where two players have directly conflicting
objectives) have been studied extensively in verification and automata
theory, "non-zero sum" games (where each player has his/her own objective)
have not.
However, in many natural game formulations of compositional verification,
each component has its own objective, and the environment of the component
may not be malicious. In these cases, non-zero sum games are natural models.
We therefore study solution concepts for non-zero sum games.
For zero sum games, the fundamental solution concept is determinacy:
to show that the value of player 1 is one minus the value of player 2.
For non-zero sum games, the fundamental concept is a Nash equilibrium.
For zero sum games, a theorem of Martin shows determinacy for all Borel
objectives.
For non-zero sum games, Sudderth and Secchi showed the existence of Nash
equilibria in safety games, however, not much more is known.
We study non-zero sum reachability games and show the existence of
an epsilon-Nash equilibrium
in memoryless strategies, for every epsilon >0.
However, exact Nash equilibria need not exist.
We study the complexity of finding approximate equilibria, and show that
the payoff of some epsilon-Nash equilibrium can be approximated in NP.
In the important subclass of n-player turn-based probabilistic games,
where at each state atmost one player has a nontrivial choice of moves,
we show the existence of epsilon-Nash equilibria
in pure strategies for games with Borel objectives.
However, exact Nash equilibria may not exist.
For the special case of omega-regular objectives, we show exact Nash equilibria
exist, and can be computed in NP when the omega-regular objectives are
expressed as parity objectives.
Joint work with Krishnendu Chatterjee and Marcin Jurdzinski.
| gdv04@soe.ucsc.edu |
Last updated: June 3, 2004 |