Nash Equilibrium and Bisimulation Invariance. Gutierrez, J., Harrenstein, P., Perelli, G., & Wooldridge, M. In 28th International Conference on Concurrency Theory, CONCUR 2017, September 5-8, 2017, Berlin, Germany, pages 17:1–17:16, 2017. ![Nash Equilibrium and Bisimulation Invariance. [link]](https://bibbase.org/img/filetypes/link.svg "link")
Paper abstract bibtex Game theory provides a well-established framework for the analysis of concurrent and multi-agent systems. The basic idea is that concurrent processes (agents) can be understood as corresponding to players in a game; plays represent the possible computation runs of the system; and strategies define the behaviour of agents. Typically, strategies are modelled as functions from sequences of system states to player actions. Analysing a system in such a way involves computing the set of (Nash) equilibria in the game. However, we show that, with respect to the above model of strategies—the standard model in the literature—bisimilarity does not preserve the existence of Nash equilibria. Thus, two concurrent games which are behaviourally equivalent from a semantic perspective, and which from a logical perspective satisfy the same temporal formulae, nevertheless have fundamentally different properties from a game theoretic perspective. In this paper we explore the issues raised by this discovery, and investigate three models of strategies with respect to which the existence of Nash equilibria is preserved under bisimilarity. We also use some of these models of strategies to provide new semantic foundations for logics for strategic reasoning, and investigate restricted scenarios where bisimilarity can be shown to preserve the existence of Nash equilibria with respect to the conventional model of strategies in the literature.
@inproceedings
{
C-GHPW17,
author = {Julian Gutierrez and Paul Harrenstein and Giuseppe Perelli and Michael Wooldridge},
title = {Nash Equilibrium and Bisimulation Invariance.},
abstract = {Game theory provides a well-established framework for the analysis of concurrent and multi-agent systems. The basic idea is that concurrent processes (agents) can be understood as corresponding to players in a game; plays represent the possible computation runs of the system; and strategies define the behaviour of agents. Typically, strategies are modelled as functions from sequences of system states to player actions. Analysing a system in such a way involves computing the set of (Nash) equilibria in the game. However, we show that, with respect to the above model of strategies---the standard model in the literature---bisimilarity does not preserve the existence of Nash equilibria. Thus, two concurrent games which are behaviourally equivalent from a semantic perspective, and which from a logical perspective satisfy the same temporal formulae, nevertheless have fundamentally different properties from a game theoretic perspective. In this paper we explore the issues raised by this discovery, and investigate three models of strategies with respect to which the existence of Nash equilibria is preserved under bisimilarity. We also use some of these models of strategies to provide new semantic foundations for logics for strategic reasoning, and investigate restricted scenarios where bisimilarity can be shown to preserve the existence of Nash equilibria with respect to the conventional model of strategies in the literature.},
booktitle = {28th International Conference on Concurrency Theory, {CONCUR} 2017, September 5-8, 2017, Berlin, Germany},
pages = {17:1--17:16},
year = {2017},
url_paper = {https://dblp.uni-trier.de/pers/p/Perelli:Giuseppe.html},
}
Downloads: 0
{"_id":"mnjzntqsNvjaKJwHu","bibbaseid":"gutierrez-harrenstein-perelli-wooldridge-nashequilibriumandbisimulationinvariance-2017","authorIDs":["27AAjNDH3eGyX3kAG","5e5fa91819c3fade010000c4","5e610d2131c7d3de0100025f","5e65076e9eed46de0100004a","5e6aaadaf216f6de01000129","62BzuGuQtetH6F3cf","73Rh8BSJgqcii5cD3","7aQ2zeLMoyj6CHpBu","8QYqvnERKkScTLpXt","939RNK33yrPF4hHck","9QZmYec3ABqZqB9ed","9R3rFYeegwqLCtFQ7","9y2sud2AwvG4Tfdrm","Am2578MapgxQHtFf4","AqbTCnnCr8sLjTmdv","Ax9iPx6jhgbzjgAsq","C4ESoeg7imBRZM8Wr","DCAwSuxCjnszReHdG","FSKJKgCA2iK6ike3h","G2yqkXwcYagjLqEat","Gj4YRNsBu7wtb4vXY","HcptFeK4rg5nYWiFa","HfSGhTtE2kahBfnm8","HuLSgG4PJuPLGpoMZ","JYgujoQ6Yr9gf5vNm","JqvuFYYZoqT3y5hMJ","JsDz5ZfswX5PojvGF","L9SALwZHK7h4cnemm","M8ugQbFqc7J2SZZkb","MFXN3rfY97dER4uaF","MZzQLYonZyupKJJTW","Mj26qo7ejPRPakyYe","P7Rrykvikzyq7PH8F","SJHQwhWmEBwe2BkD3","TXDn8che9rTzjmrA5","W7Y9wsvLY9xYhYm7h","WrDgnRcn4BB4Pa2dL","XFeNGvuLa7vugKn8p","b932A83vqaao9vcAc","g5b8qR96euxXJQuwo","kWEPDQzitMRJ7Zfhd","kZpNRST28n9ZjkEjH","n5xPfBLskvCDRBk9A","pJotjgR9RGRzfaYDG","phZeTXoR5izbbuka9","qNnrc72DLfCFyCBuC","qWWZLuDKbdrQDYuXX","uiiEzMohLiEYpDQLf","uj2FY3LBd7XX9c4LZ","wGdyWcm2XzfxzJTEK","xPnSDmeSsJoXtiWXX","xWfKBfkZej5XRKp8G"],"author_short":["Gutierrez, J.","Harrenstein, P.","Perelli, G.","Wooldridge, M."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","author":[{"firstnames":["Julian"],"propositions":[],"lastnames":["Gutierrez"],"suffixes":[]},{"firstnames":["Paul"],"propositions":[],"lastnames":["Harrenstein"],"suffixes":[]},{"firstnames":["Giuseppe"],"propositions":[],"lastnames":["Perelli"],"suffixes":[]},{"firstnames":["Michael"],"propositions":[],"lastnames":["Wooldridge"],"suffixes":[]}],"title":"Nash Equilibrium and Bisimulation Invariance.","abstract":"Game theory provides a well-established framework for the analysis of concurrent and multi-agent systems. The basic idea is that concurrent processes (agents) can be understood as corresponding to players in a game; plays represent the possible computation runs of the system; and strategies define the behaviour of agents. Typically, strategies are modelled as functions from sequences of system states to player actions. Analysing a system in such a way involves computing the set of (Nash) equilibria in the game. However, we show that, with respect to the above model of strategies—the standard model in the literature—bisimilarity does not preserve the existence of Nash equilibria. Thus, two concurrent games which are behaviourally equivalent from a semantic perspective, and which from a logical perspective satisfy the same temporal formulae, nevertheless have fundamentally different properties from a game theoretic perspective. In this paper we explore the issues raised by this discovery, and investigate three models of strategies with respect to which the existence of Nash equilibria is preserved under bisimilarity. We also use some of these models of strategies to provide new semantic foundations for logics for strategic reasoning, and investigate restricted scenarios where bisimilarity can be shown to preserve the existence of Nash equilibria with respect to the conventional model of strategies in the literature.","booktitle":"28th International Conference on Concurrency Theory, CONCUR 2017, September 5-8, 2017, Berlin, Germany","pages":"17:1–17:16","year":"2017","url_paper":"https://dblp.uni-trier.de/pers/p/Perelli:Giuseppe.html","bibtex":"@inproceedings\n{\n\tC-GHPW17,\n\tauthor\t\t\t\t=\t{Julian Gutierrez and Paul Harrenstein and Giuseppe Perelli and Michael Wooldridge},\n\ttitle\t\t\t\t\t=\t{Nash Equilibrium and Bisimulation Invariance.},\n\tabstract\t\t\t=\t{Game theory provides a well-established framework for the analysis of concurrent and multi-agent systems. The basic idea is that concurrent processes (agents) can be understood as corresponding to players in a game; plays represent the possible computation runs of the system; and strategies define the behaviour of agents. Typically, strategies are modelled as functions from sequences of system states to player actions. Analysing a system in such a way involves computing the set of (Nash) equilibria in the game. However, we show that, with respect to the above model of strategies---the standard model in the literature---bisimilarity does not preserve the existence of Nash equilibria. Thus, two concurrent games which are behaviourally equivalent from a semantic perspective, and which from a logical perspective satisfy the same temporal formulae, nevertheless have fundamentally different properties from a game theoretic perspective. In this paper we explore the issues raised by this discovery, and investigate three models of strategies with respect to which the existence of Nash equilibria is preserved under bisimilarity. We also use some of these models of strategies to provide new semantic foundations for logics for strategic reasoning, and investigate restricted scenarios where bisimilarity can be shown to preserve the existence of Nash equilibria with respect to the conventional model of strategies in the literature.},\n\tbooktitle \t\t= {28th International Conference on Concurrency Theory, {CONCUR} 2017, September 5-8, 2017, Berlin, Germany},\n\tpages \t\t= {17:1--17:16},\n\tyear \t\t= {2017},\n\turl_paper \t\t= {https://dblp.uni-trier.de/pers/p/Perelli:Giuseppe.html},\n}\n\n","author_short":["Gutierrez, J.","Harrenstein, P.","Perelli, G.","Wooldridge, M."],"key":"C-GHPW17","id":"C-GHPW17","bibbaseid":"gutierrez-harrenstein-perelli-wooldridge-nashequilibriumandbisimulationinvariance-2017","role":"author","urls":{" paper":"https://dblp.uni-trier.de/pers/p/Perelli:Giuseppe.html"},"metadata":{"authorlinks":{"perelli, g":"https://giuseppeperelli.github.io/oldsite/"}}},"bibtype":"inproceedings","biburl":"https://raw.githubusercontent.com/giuseppeperelli/giuseppeperelli.github.io/master/Publications.bib","creationDate":"2020-02-29T21:07:14.950Z","downloads":0,"keywords":[],"search_terms":["nash","equilibrium","bisimulation","invariance","gutierrez","harrenstein","perelli","wooldridge"],"title":"Nash Equilibrium and Bisimulation Invariance.","year":2017,"dataSources":["Hsp4YyumSZ65qLatJ","kSN38gKTSZ2dArL6M","P3TQkzzbYMHFrjwn4"]}