No Cover Image

Journal article 1137 views 210 downloads

Extending finite-memory determinacy to multi-player games

Stéphane Le Roux, Arno Pauly Orcid Logo

Information and Computation, Volume: 261, Pages: 676 - 694

Swansea University Author: Arno Pauly Orcid Logo

  • 2017-pauly-leroux.pdf

    PDF | Accepted Manuscript

    Released under the terms of a Creative Commons Attribution Non-Commercial No Derivatives License (CC-BY-NC-ND).

    Download (315.66KB)

Check full text

DOI (Published version): 10.1016/j.ic.2018.02.024

Abstract

We show that under some general conditions the finite memory determinacy of a class of two-player win/lose games played on finite graphs implies the existence of a Nash equilibrium built from finite memory strategies for the corresponding class of multi-player multi-outcome games. This generalizes a...

Full description

Published in: Information and Computation
ISSN: 0890-5401
Published: Elsevier BV 2018
Online Access: Check full text

URI: https://cronfa.swan.ac.uk/Record/cronfa37648
Tags: Add Tag
No Tags, Be the first to tag this record!
first_indexed 2017-12-18T19:49:44Z
last_indexed 2023-01-11T14:13:05Z
id cronfa37648
recordtype SURis
fullrecord <?xml version="1.0"?><rfc1807><datestamp>2022-12-05T12:48:16.0694176</datestamp><bib-version>v2</bib-version><id>37648</id><entry>2017-12-18</entry><title>Extending finite-memory determinacy to multi-player games</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>2017-12-18</date><deptcode>SCS</deptcode><abstract>We show that under some general conditions the finite memory determinacy of a class of two-player win/lose games played on finite graphs implies the existence of a Nash equilibrium built from finite memory strategies for the corresponding class of multi-player multi-outcome games. This generalizes a previous result by Brihaye, De Pril and Schewe. We provide a number of example that separate the various criteria we explore.Our proofs are generally constructive, that is, provide upper bounds for the memory required, as well as algorithms to compute the relevant Nash equilibria.</abstract><type>Journal Article</type><journal>Information and Computation</journal><volume>261</volume><journalNumber/><paginationStart>676</paginationStart><paginationEnd>694</paginationEnd><publisher>Elsevier BV</publisher><placeOfPublication/><isbnPrint/><isbnElectronic/><issnPrint>0890-5401</issnPrint><issnElectronic/><keywords>Finite memory; Games played on finite graphs; Finite-memory determinacy; Nash equilibrium; Equilibrium transfer; Energy parity games</keywords><publishedDay>1</publishedDay><publishedMonth>8</publishedMonth><publishedYear>2018</publishedYear><publishedDate>2018-08-01</publishedDate><doi>10.1016/j.ic.2018.02.024</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>2022-12-05T12:48:16.0694176</lastEdited><Created>2017-12-18T15:58:33.1638915</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>St&#xE9;phane Le</firstname><surname>Roux</surname><order>1</order></author><author><firstname>Arno</firstname><surname>Pauly</surname><orcid>0000-0002-0173-3295</orcid><order>2</order></author></authors><documents><document><filename>0037648-18122017160101.pdf</filename><originalFilename>2017-pauly-leroux.pdf</originalFilename><uploaded>2017-12-18T16:01:01.9770000</uploaded><type>Output</type><contentLength>345931</contentLength><contentType>application/pdf</contentType><version>Accepted Manuscript</version><cronfaStatus>true</cronfaStatus><embargoDate>2019-03-02T00:00:00.0000000</embargoDate><documentNotes>Released under the terms of a Creative Commons Attribution Non-Commercial No Derivatives License (CC-BY-NC-ND).</documentNotes><copyrightCorrect>true</copyrightCorrect><language>eng</language></document></documents><OutputDurs/></rfc1807>
spelling 2022-12-05T12:48:16.0694176 v2 37648 2017-12-18 Extending finite-memory determinacy to multi-player games 17a56a78ec04e7fc47b7fe18394d7245 0000-0002-0173-3295 Arno Pauly Arno Pauly true false 2017-12-18 SCS We show that under some general conditions the finite memory determinacy of a class of two-player win/lose games played on finite graphs implies the existence of a Nash equilibrium built from finite memory strategies for the corresponding class of multi-player multi-outcome games. This generalizes a previous result by Brihaye, De Pril and Schewe. We provide a number of example that separate the various criteria we explore.Our proofs are generally constructive, that is, provide upper bounds for the memory required, as well as algorithms to compute the relevant Nash equilibria. Journal Article Information and Computation 261 676 694 Elsevier BV 0890-5401 Finite memory; Games played on finite graphs; Finite-memory determinacy; Nash equilibrium; Equilibrium transfer; Energy parity games 1 8 2018 2018-08-01 10.1016/j.ic.2018.02.024 COLLEGE NANME Computer Science COLLEGE CODE SCS Swansea University 2022-12-05T12:48:16.0694176 2017-12-18T15:58:33.1638915 Faculty of Science and Engineering School of Mathematics and Computer Science - Computer Science Stéphane Le Roux 1 Arno Pauly 0000-0002-0173-3295 2 0037648-18122017160101.pdf 2017-pauly-leroux.pdf 2017-12-18T16:01:01.9770000 Output 345931 application/pdf Accepted Manuscript true 2019-03-02T00:00:00.0000000 Released under the terms of a Creative Commons Attribution Non-Commercial No Derivatives License (CC-BY-NC-ND). true eng
title Extending finite-memory determinacy to multi-player games
spellingShingle Extending finite-memory determinacy to multi-player games
Arno Pauly
title_short Extending finite-memory determinacy to multi-player games
title_full Extending finite-memory determinacy to multi-player games
title_fullStr Extending finite-memory determinacy to multi-player games
title_full_unstemmed Extending finite-memory determinacy to multi-player games
title_sort Extending finite-memory determinacy to multi-player games
author_id_str_mv 17a56a78ec04e7fc47b7fe18394d7245
author_id_fullname_str_mv 17a56a78ec04e7fc47b7fe18394d7245_***_Arno Pauly
author Arno Pauly
author2 Stéphane Le Roux
Arno Pauly
format Journal article
container_title Information and Computation
container_volume 261
container_start_page 676
publishDate 2018
institution Swansea University
issn 0890-5401
doi_str_mv 10.1016/j.ic.2018.02.024
publisher Elsevier BV
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 We show that under some general conditions the finite memory determinacy of a class of two-player win/lose games played on finite graphs implies the existence of a Nash equilibrium built from finite memory strategies for the corresponding class of multi-player multi-outcome games. This generalizes a previous result by Brihaye, De Pril and Schewe. We provide a number of example that separate the various criteria we explore.Our proofs are generally constructive, that is, provide upper bounds for the memory required, as well as algorithms to compute the relevant Nash equilibria.
published_date 2018-08-01T03:47:27Z
_version_ 1763752277090238464
score 11.035634

Similar Items