Vi studerar n-player turbaserade spel som spelas på en ändlig riktad graf. För varje spel måste spelarna betala en kostnad som de vill minimera. Istället för den välkända uppfattningen om Nash jämvikt (NE), fokuserar vi på begreppet subgame perfekt jämvikt (SPE), en förfining av NE väl lämpad inom ramen för spel som spelas på grafer. Vi studerar också naturliga varianter av SPE, namngivna svaga (resp. mycket svag) SPE, där spelare som avviker inte kan använda hela klassen av strategier utan bara en subklass med ett begränsat antal (sp. En unik avvikelsesteg. Våra resultat är trefaldiga. För det första karakteriserar vi i form av ett folkteorem uppsättningen av alla pjäser som är resultatet av ett svagt SPE. Vi etablerar också en svagare version av denna sats för SPE-bolag. För det andra, för klassen kvantitativa nåbarhet spel, vi bevisa förekomsten av en ändlig-minne SPE och tillhandahålla en algoritm för att beräkna det (bara existens var känd utan någon information om minnet). Dessutom visar vi att det finns ett begränsat SPE-bolag, dvs. en SPE sådan att varje spelare betalar en kostnad mindre än en given konstant, kan beslutas. Bevisen förlitar sig på vår Folksats för svaga SPE-bolag (som sammanfaller med SPE-bolag i fallet med kvantitativa tillgänglighetsspel) och på MSO-logikens decisionability på oändliga ord. Slutligen med liknande tekniker, vi ger en andra allmänna klass av spel för vilka förekomsten av en (konstruerad) svag SPE är decidable.
Kvantitativa tillgänglighetsmål undersöks i REF där det bevisas att det begränsade existensproblemet för svaga SPE-bolag och SPE-bolag är decimerbart, men dess exakta komplexitet lämnas öppen.
Weak Subgame Perfect Equilibria and their Application to Quantitative Reachability
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}