No Cover Image

Conference Paper/Proceeding/Abstract 927 views 68 downloads

Beyond Admissibility: Dominance Between Chains of Strategies

Nicolas Basset, Ismael Jecker, Arno Pauly Orcid Logo, Jean-Francois Raskin, Marie van den Bogaard

Swansea University Author: Arno Pauly Orcid Logo

DOI (Published version): 10.4230/LIPIcs.CSL.2018.10

Abstract

Admissible strategies, i.e. those that are not dominated by any other strategy, are a typical rationality notion in game theory. In many classes of games this is justified by results showing that any strategy is admissible or dominated by an admissible strategy. However, in games played on finite gr...

Full description

Published: Computer Science Logic (CSL) 2018
URI: https://cronfa.swan.ac.uk/Record/cronfa43771
Tags: Add Tag
No Tags, Be the first to tag this record!
first_indexed 2018-09-12T04:00:28Z
last_indexed 2019-04-09T12:55:57Z
id cronfa43771
recordtype SURis
fullrecord <?xml version="1.0" encoding="utf-8"?><rfc1807 xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:xsd="http://www.w3.org/2001/XMLSchema"><bib-version>v2</bib-version><id>43771</id><entry>2018-09-11</entry><title>Beyond Admissibility: Dominance Between Chains of Strategies</title><swanseaauthors><author><sid>17a56a78ec04e7fc47b7fe18394d7245</sid><ORCID>0000-0002-0173-3295</ORCID><firstname>Arno</firstname><surname>Pauly</surname><name>Arno Pauly</name><active>true</active><ethesisStudent>false</ethesisStudent></author></swanseaauthors><date>2018-09-11</date><deptcode>SCS</deptcode><abstract>Admissible strategies, i.e. those that are not dominated by any other strategy, are a typical rationality notion in game theory. In many classes of games this is justified by results showing that any strategy is admissible or dominated by an admissible strategy. However, in games played on finite graphs with quantitative objectives (as used for reactive synthesis), this is not the case. We consider increasing chains of strategies instead to recover a satisfactory rationality notion based on dominance in such games. We start with some order-theoretic considerations establishing sufficient criteria for this to work. We then turn our attention to generalised safety/reachability games as a particular application. We propose the notion of maximal uniform chain as the desired dominance-based rationality concept in these games. Decidability of some fundamental questions about uniform chains is established.</abstract><type>Conference Paper/Proceeding/Abstract</type><journal/><volume/><journalNumber/><paginationStart/><paginationEnd/><publisher>Computer Science Logic (CSL)</publisher><placeOfPublication/><isbnPrint/><isbnElectronic/><issnPrint/><issnElectronic/><keywords/><publishedDay>29</publishedDay><publishedMonth>8</publishedMonth><publishedYear>2018</publishedYear><publishedDate>2018-08-29</publishedDate><doi>10.4230/LIPIcs.CSL.2018.10</doi><url/><notes/><college>COLLEGE NANME</college><department>Computer Science</department><CollegeCode>COLLEGE CODE</CollegeCode><DepartmentCode>SCS</DepartmentCode><institution>Swansea University</institution><apcterm/><funders/><projectreference/><lastEdited>2023-05-22T15:03:50.6381597</lastEdited><Created>2018-09-11T19:26:40.8282195</Created><path><level id="1">Faculty of Science and Engineering</level><level id="2">School of Mathematics and Computer Science - Computer Science</level></path><authors><author><firstname>Nicolas</firstname><surname>Basset</surname><order>1</order></author><author><firstname>Ismael</firstname><surname>Jecker</surname><order>2</order></author><author><firstname>Arno</firstname><surname>Pauly</surname><orcid>0000-0002-0173-3295</orcid><order>3</order></author><author><firstname>Jean-Francois</firstname><surname>Raskin</surname><order>4</order></author><author><firstname>Marie van den</firstname><surname>Bogaard</surname><order>5</order></author></authors><documents><document><filename>0043771-24092018133323.pdf</filename><originalFilename>43771.pdf</originalFilename><uploaded>2018-09-24T13:33:23.8570000</uploaded><type>Output</type><contentLength>603192</contentLength><contentType>application/pdf</contentType><version>Version of Record</version><cronfaStatus>true</cronfaStatus><embargoDate>2018-09-24T00:00:00.0000000</embargoDate><documentNotes>Licensed under Creative Commons License CC-BY</documentNotes><copyrightCorrect>true</copyrightCorrect><language>eng</language></document></documents><OutputDurs/></rfc1807>
spelling v2 43771 2018-09-11 Beyond Admissibility: Dominance Between Chains of Strategies 17a56a78ec04e7fc47b7fe18394d7245 0000-0002-0173-3295 Arno Pauly Arno Pauly true false 2018-09-11 SCS Admissible strategies, i.e. those that are not dominated by any other strategy, are a typical rationality notion in game theory. In many classes of games this is justified by results showing that any strategy is admissible or dominated by an admissible strategy. However, in games played on finite graphs with quantitative objectives (as used for reactive synthesis), this is not the case. We consider increasing chains of strategies instead to recover a satisfactory rationality notion based on dominance in such games. We start with some order-theoretic considerations establishing sufficient criteria for this to work. We then turn our attention to generalised safety/reachability games as a particular application. We propose the notion of maximal uniform chain as the desired dominance-based rationality concept in these games. Decidability of some fundamental questions about uniform chains is established. Conference Paper/Proceeding/Abstract Computer Science Logic (CSL) 29 8 2018 2018-08-29 10.4230/LIPIcs.CSL.2018.10 COLLEGE NANME Computer Science COLLEGE CODE SCS Swansea University 2023-05-22T15:03:50.6381597 2018-09-11T19:26:40.8282195 Faculty of Science and Engineering School of Mathematics and Computer Science - Computer Science Nicolas Basset 1 Ismael Jecker 2 Arno Pauly 0000-0002-0173-3295 3 Jean-Francois Raskin 4 Marie van den Bogaard 5 0043771-24092018133323.pdf 43771.pdf 2018-09-24T13:33:23.8570000 Output 603192 application/pdf Version of Record true 2018-09-24T00:00:00.0000000 Licensed under Creative Commons License CC-BY true eng
title Beyond Admissibility: Dominance Between Chains of Strategies
spellingShingle Beyond Admissibility: Dominance Between Chains of Strategies
Arno Pauly
title_short Beyond Admissibility: Dominance Between Chains of Strategies
title_full Beyond Admissibility: Dominance Between Chains of Strategies
title_fullStr Beyond Admissibility: Dominance Between Chains of Strategies
title_full_unstemmed Beyond Admissibility: Dominance Between Chains of Strategies
title_sort Beyond Admissibility: Dominance Between Chains of Strategies
author_id_str_mv 17a56a78ec04e7fc47b7fe18394d7245
author_id_fullname_str_mv 17a56a78ec04e7fc47b7fe18394d7245_***_Arno Pauly
author Arno Pauly
author2 Nicolas Basset
Ismael Jecker
Arno Pauly
Jean-Francois Raskin
Marie van den Bogaard
format Conference Paper/Proceeding/Abstract
publishDate 2018
institution Swansea University
doi_str_mv 10.4230/LIPIcs.CSL.2018.10
publisher Computer Science Logic (CSL)
college_str Faculty of Science and Engineering
hierarchytype
hierarchy_top_id facultyofscienceandengineering
hierarchy_top_title Faculty of Science and Engineering
hierarchy_parent_id facultyofscienceandengineering
hierarchy_parent_title Faculty of Science and Engineering
department_str School of Mathematics and Computer Science - Computer Science{{{_:::_}}}Faculty of Science and Engineering{{{_:::_}}}School of Mathematics and Computer Science - Computer Science
document_store_str 1
active_str 0
description Admissible strategies, i.e. those that are not dominated by any other strategy, are a typical rationality notion in game theory. In many classes of games this is justified by results showing that any strategy is admissible or dominated by an admissible strategy. However, in games played on finite graphs with quantitative objectives (as used for reactive synthesis), this is not the case. We consider increasing chains of strategies instead to recover a satisfactory rationality notion based on dominance in such games. We start with some order-theoretic considerations establishing sufficient criteria for this to work. We then turn our attention to generalised safety/reachability games as a particular application. We propose the notion of maximal uniform chain as the desired dominance-based rationality concept in these games. Decidability of some fundamental questions about uniform chains is established.
published_date 2018-08-29T15:03:48Z
_version_ 1766603336145960960
score 11.035634

Similar Items