| |
VOLUME 4, ISSUE 3, PAPER 7
|
Game Refinement Relations and Metrics
|
©Luca de Alfaro, University of California, Santa Cruz
©Rupak Majumdar, University of California, Los Angeles
©Vishwanath Raman, University of California, Santa Cruz
©Mariëlle Stoelinga, University of Twente, The Netherlands
|
Abstract
We consider two-player games played over finite state spaces for an infinite
number of rounds. At each state, the players simultaneously choose moves; the
moves determine a successor state. It is often advantageous for players to
choose probability distributions over moves, rather than single moves. Given a
goal, for example, reach a target state, the question of winning is thus a
probabilistic one: what is the maximal probability of winning from a given
state?
On these game structures, two fundamental notions are those of equivalences
and metrics. Given a set of winning conditions, two states are equivalent if
the players can win the same games with the same probability from both states.
Metrics provide a bound on the difference in the probabilities of winning
across states, capturing a quantitative notion of state similarity.
We introduce equivalences and metrics for two-player game structures, and we
show that they characterize the difference in probability of winning games
whose goals are expressed in the quantitative mu-calculus. The quantitative
mu-calculus can express a large set of goals, including reachability, safety,
and omega-regular properties. Thus, we claim that our relations and metrics
provide the canonical extensions to games, of the classical notion of
bisimulation for transition systems. We develop our results both for
equivalences and metrics, which generalize bisimulation, and for asymmetrical
versions, which generalize simulation.
|
Publication date: September 11, 2008
Full Text: PDF | PostScript
DOI: 10.2168/LMCS-4(3:7)2008
Hit Counts: 2374 |
 Creative Commons | |
