|
Published Articles >> Table of Contents >> Abstract
22nd Annual IEEE Symposium on Logic in Computer Science (LICS 2007)
pp. 99-108
Game Relations and Metrics
Luca de Alfaro, University of California, Santa Cruz, USA
Rupak Majumdar, University of California, Los Angeles, USA
Vishwanath Raman, University of California, Santa Cruz, USA
Mariëlle Stoelinga, University of Twente, the Netherlands
Full Article Text:
 
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/LICS.2007.22
Send link to a friend
| 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 (e.g., "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 ì-calculus. The quantitative ì-
calculus can express a large set of goals, including reachability,
safety, and ù-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.
|
 Additional Information
|
Citation:
Luca de Alfaro, Rupak Majumdar, Vishwanath Raman, Mariëlle Stoelinga,
"Game Relations and Metrics,"
lics,
pp. 99-108,
22nd Annual IEEE Symposium on Logic in Computer Science (LICS 2007),
2007
|
|
