Quantitative Verification in Rational Environments

Gupta, Anshul and Schewe, Sven ORCID: 0000-0002-9093-9518 (2014) Quantitative Verification in Rational Environments. In: 2014 21st International Symposium on Temporal Representation and Reasoning. IEEE, pp. 123-131. ISBN 9781479942275

Text PID3281427.pdf - Unspecified Download (353kB)

Abstract

We study optimal equilibrium in turn based multiplayer mean-payoff games. Nash equilibrium are a standard way to define rational behaviour of different players in multi-player games. These equilibrium treat all players equally. We study settings where a leader has additional power over the game: she has the power to assign strategies to all participating players, including herself. We argue that a leader who assign the strategies, may not want to comply with the common restrictions imposed by Nash equilibrium. This setting provides the basis for the quantitative analysis of the distributed systems, where the leader can take the role of a controller or an adversary, while the other players form a rational environment. We show that the leader always has an optimal strategy in this setting, and that no Nash equilibrium can be superior to it. Finding this equilibrium is NP-complete and, for a fixed number of players, there is a polynomial time reduction to solving two player mean-payoff games.

Item Type:	Book Section
Depositing User:	Symplectic Admin
Date Deposited:	01 Feb 2017 11:38
Last Modified:	19 Jan 2023 07:19
DOI:	10.1109/TIME.2014.9
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3005479