Synthesis of Controllable Nash Equilibria in Games with Quantitative Objectives. Almagor, S., Kupferman, O., & Perelli, G. In Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI 2018, July 13-19, 2018, Stockholm, Sweden., pages 35–41, 2018. ![Synthesis of Controllable Nash Equilibria in Games with Quantitative Objectives. [link]](https://bibbase.org/img/filetypes/link.svg "link")
Paper abstract bibtex In Rational Synthesis, we consider a multi-agent system in which some of the agents are controllable and some are not. All agents have objectives, and the goal is to synthesize strategies for the controllable agents so that their objectives are satisfied, assuming rationality of the uncontrollable agents. Previous work on rational synthesis considers objectives in LTL, namely ones that describe on-going behaviors, and in Objective-LTL, which allows ranking of LTL formulas. In this paper, we extend rational synthesis to LTL[F] – an extension of LTL by quality operators. The satisfaction value of an LTL[F] formula is a real value in [0,1], where the higher the value is, the higher is the quality in which the computation satisfies the specification. The extension significantly strengthens the framework of rational synthesis and enables a study its game- and social-choice theoretic aspects. In particular, we study the price of stability and price of anarchy of the rational-synthesis game and use them to explain the cooperative and non-cooperative settings of rational synthesis. Our algorithms make use of strategy logic and decision procedures for it. Thus, we are able to handle the richer quantitative setting using existing tools. In particular, we show that the cooperative and non-cooperative versions of quantitative rational synthesis are 2EXPTIME-complete and in 3EXPTIME, respectively – not harder than the complexity known for their Boolean analogues.
@inproceedings
{
C-AKP18,
author = {Shaull Almagor and Orna Kupferman and Giuseppe Perelli},
title = {Synthesis of Controllable Nash Equilibria in Games with Quantitative Objectives.},
abstract = {In Rational Synthesis, we consider a multi-agent system in which some of the agents are controllable and some are not. All agents have objectives, and the goal is to synthesize strategies for the controllable agents so that their objectives are satisfied, assuming rationality of the uncontrollable agents. Previous work on rational synthesis considers objectives in LTL, namely ones that describe on-going behaviors, and in Objective-LTL, which allows ranking of LTL formulas. In this paper, we extend rational synthesis to LTL[F] -- an extension of LTL by quality operators. The satisfaction value of an LTL[F] formula is a real value in [0,1], where the higher the value is, the higher is the quality in which the computation satisfies the specification. The extension significantly strengthens the framework of rational synthesis and enables a study its game- and social-choice theoretic aspects. In particular, we study the price of stability and price of anarchy of the rational-synthesis game and use them to explain the cooperative and non-cooperative settings of rational synthesis. Our algorithms make use of strategy logic and decision procedures for it. Thus, we are able to handle the richer quantitative setting using existing tools. In particular, we show that the cooperative and non-cooperative versions of quantitative rational synthesis are 2EXPTIME-complete and in 3EXPTIME, respectively -- not harder than the complexity known for their Boolean analogues.},
booktitle = {Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, {IJCAI} 2018, July 13-19, 2018, Stockholm, Sweden.},
pages = {35--41},
year = {2018},
url_paper = {https://www.ijcai.org/Proceedings/2018/5},
}
Downloads: 0
{"_id":"vDg6r5JXjr4zutYtB","bibbaseid":"almagor-kupferman-perelli-synthesisofcontrollablenashequilibriaingameswithquantitativeobjectives-2018","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":["Almagor, S.","Kupferman, O.","Perelli, G."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","author":[{"firstnames":["Shaull"],"propositions":[],"lastnames":["Almagor"],"suffixes":[]},{"firstnames":["Orna"],"propositions":[],"lastnames":["Kupferman"],"suffixes":[]},{"firstnames":["Giuseppe"],"propositions":[],"lastnames":["Perelli"],"suffixes":[]}],"title":"Synthesis of Controllable Nash Equilibria in Games with Quantitative Objectives.","abstract":"In Rational Synthesis, we consider a multi-agent system in which some of the agents are controllable and some are not. All agents have objectives, and the goal is to synthesize strategies for the controllable agents so that their objectives are satisfied, assuming rationality of the uncontrollable agents. Previous work on rational synthesis considers objectives in LTL, namely ones that describe on-going behaviors, and in Objective-LTL, which allows ranking of LTL formulas. In this paper, we extend rational synthesis to LTL[F] – an extension of LTL by quality operators. The satisfaction value of an LTL[F] formula is a real value in [0,1], where the higher the value is, the higher is the quality in which the computation satisfies the specification. The extension significantly strengthens the framework of rational synthesis and enables a study its game- and social-choice theoretic aspects. In particular, we study the price of stability and price of anarchy of the rational-synthesis game and use them to explain the cooperative and non-cooperative settings of rational synthesis. Our algorithms make use of strategy logic and decision procedures for it. Thus, we are able to handle the richer quantitative setting using existing tools. In particular, we show that the cooperative and non-cooperative versions of quantitative rational synthesis are 2EXPTIME-complete and in 3EXPTIME, respectively – not harder than the complexity known for their Boolean analogues.","booktitle":"Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI 2018, July 13-19, 2018, Stockholm, Sweden.","pages":"35–41","year":"2018","url_paper":"https://www.ijcai.org/Proceedings/2018/5","bibtex":"@inproceedings\n{\n\tC-AKP18,\n\tauthor\t\t\t\t=\t{Shaull Almagor and Orna Kupferman and Giuseppe Perelli},\n\ttitle\t\t\t\t\t=\t{Synthesis of Controllable Nash Equilibria in Games with Quantitative Objectives.},\n\tabstract\t\t\t=\t{In Rational Synthesis, we consider a multi-agent system in which some of the agents are controllable and some are not. All agents have objectives, and the goal is to synthesize strategies for the controllable agents so that their objectives are satisfied, assuming rationality of the uncontrollable agents. Previous work on rational synthesis considers objectives in LTL, namely ones that describe on-going behaviors, and in Objective-LTL, which allows ranking of LTL formulas. In this paper, we extend rational synthesis to LTL[F] -- an extension of LTL by quality operators. The satisfaction value of an LTL[F] formula is a real value in [0,1], where the higher the value is, the higher is the quality in which the computation satisfies the specification. The extension significantly strengthens the framework of rational synthesis and enables a study its game- and social-choice theoretic aspects. In particular, we study the price of stability and price of anarchy of the rational-synthesis game and use them to explain the cooperative and non-cooperative settings of rational synthesis. Our algorithms make use of strategy logic and decision procedures for it. Thus, we are able to handle the richer quantitative setting using existing tools. In particular, we show that the cooperative and non-cooperative versions of quantitative rational synthesis are 2EXPTIME-complete and in 3EXPTIME, respectively -- not harder than the complexity known for their Boolean analogues.},\n\tbooktitle\t\t\t= {Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, {IJCAI} 2018, July 13-19, 2018, Stockholm, Sweden.},\n\tpages \t\t= {35--41},\n\tyear \t\t= {2018},\n\turl_paper\t\t\t= {https://www.ijcai.org/Proceedings/2018/5},\n}\n\n","author_short":["Almagor, S.","Kupferman, O.","Perelli, G."],"key":"C-AKP18","id":"C-AKP18","bibbaseid":"almagor-kupferman-perelli-synthesisofcontrollablenashequilibriaingameswithquantitativeobjectives-2018","role":"author","urls":{" paper":"https://www.ijcai.org/Proceedings/2018/5"},"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.949Z","downloads":0,"keywords":[],"search_terms":["synthesis","controllable","nash","equilibria","games","quantitative","objectives","almagor","kupferman","perelli"],"title":"Synthesis of Controllable Nash Equilibria in Games with Quantitative Objectives.","year":2018,"dataSources":["Hsp4YyumSZ65qLatJ","P3TQkzzbYMHFrjwn4"]}