### Abstract

Original language | Undefined |
---|---|

Title of host publication | Twenty-Second Annual IEEE Symposium on LOGIC IN COMPUTER SCIENCE (LICS 2007) |

Place of Publication | Los Alamitos |

Publisher | IEEE Computer Society |

Pages | 99-108 |

Number of pages | 10 |

ISBN (Print) | 0-7695-2908-9 |

DOIs | |

Publication status | Published - Jul 2007 |

Event | 22nd Annual IEEE Symposium on Logic in Computer Science, LICS 2007 - University of Wroclaw, Wroclav, Poland Duration: 10 Jul 2007 → 14 Jul 2007 Conference number: 22 |

### Publication series

Name | |
---|---|

Publisher | IEEE Computer Society Press |

Number | 1 |

Volume | 22 |

ISSN (Print) | 1055-0143 |

### Conference

Conference | 22nd Annual IEEE Symposium on Logic in Computer Science, LICS 2007 |
---|---|

Abbreviated title | LICS |

Country | Poland |

City | Wroclav |

Period | 10/07/07 → 14/07/07 |

### Keywords

- EWI-11579
- IR-62057
- METIS-245863

### Cite this

*Twenty-Second Annual IEEE Symposium on LOGIC IN COMPUTER SCIENCE (LICS 2007)*(pp. 99-108). [10.1109/LICS.2007.22] Los Alamitos: IEEE Computer Society. https://doi.org/10.1109/LICS.2007.22

}

*Twenty-Second Annual IEEE Symposium on LOGIC IN COMPUTER SCIENCE (LICS 2007).*, 10.1109/LICS.2007.22, IEEE Computer Society, Los Alamitos, pp. 99-108, 22nd Annual IEEE Symposium on Logic in Computer Science, LICS 2007, Wroclav, Poland, 10/07/07. https://doi.org/10.1109/LICS.2007.22

**Game Relations and Metrics.** / de Alfaro, Luca; Majumdar, Rupak; Raman, Viswanath; Stoelinga, Mariëlle Ida Antoinette.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Game Relations and Metrics

AU - de Alfaro, Luca

AU - Majumdar, Rupak

AU - Raman, Viswanath

AU - Stoelinga, Mariëlle Ida Antoinette

N1 - 10.1109/LICS.2007.22

PY - 2007/7

Y1 - 2007/7

N2 - 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.

AB - 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.

KW - EWI-11579

KW - IR-62057

KW - METIS-245863

U2 - 10.1109/LICS.2007.22

DO - 10.1109/LICS.2007.22

M3 - Conference contribution

SN - 0-7695-2908-9

SP - 99

EP - 108

BT - Twenty-Second Annual IEEE Symposium on LOGIC IN COMPUTER SCIENCE (LICS 2007)

PB - IEEE Computer Society

CY - Los Alamitos

ER -