Stackelberg ekvilibria har blivit allt viktigare som lösningskoncept i beräkningsspelsteorin, till stor del inspirerat av praktiska problem som säkerhetsinställningar. I praktiken är det dock typiskt osäkert vad gäller modellen om motståndaren. Denna uppsats är, såvitt vi vet, den första att undersöka Stackelberg equilibria under osäkerhet i omfattande-form spel, en av de bredaste klasserna av spel. Vi introducerar robust Stackelberg equilibria, där osäkerheten handlar om motståndarens belöningar, samt de där motståndaren har begränsad lookahead och osäkerheten handlar om motståndarens nodutvärderingsfunktion. Vi utvecklar en ny mixed-integer program för deterministiska limited-lookahead inställning. Vi utökar sedan programmet till den robusta inställningen för Stackelberg jämvikt under obegränsad och under begränsad lookahead av motståndaren. Vi visar att för det specifika fallet av intervall osäkerhet om motståndarens utbetalningar (eller om motståndarens nod utvärderingar i fallet med begränsad lookahead), robust Stackelberg equilibria kan beräknas med en blandad-integer program som är av samma asymptotiska storlek som för den deterministiska inställningen. I en Stackelberg jämvikt, en ledare förbinder sig till en strategi först, och sedan en följare väljer en strategi för sig själv. Modellen infördes först i samband med konkurrens mellan företag där ledaren väljer en mängd att leverera, och sedan väljer följaren en mängd att leverera (von Stackelberg 1934). Stackelberg equilibria har blivit viktigt som lösningskoncept i beräkningsteorin, till stor del inspirerat av praktiska problem som säkerhetsinställningar, där ledaren är en försvarare som väljer en blandad (dvs potentiellt randomiserad) strategi först, och sedan den följare som är angriparen bestämmer var man ska attackera, om alls. De flesta arbeten på Stackelberg Equilibria har fokuserat på normal form (alias. matris-form) spel. Conitzer och Sandholm (2006) studerade problemet med att beräkna en optimal strategi för att engagera sig i normala spel. Denna typ av arbete har utvidgats till många säkerhets-spel program. I praktiken är det typiskt osäkert om motståndarens belöningar. I normala-form spel har detta studerats som Bayesian Stackelberg spel där spelarna har privat information om sina egna utbetalningar, och det finns allmän kunskap om den tidigare fördelningen över pay-Extensive-form spel (EFGs)-dvs., trädform spel är ett mycket allmänt spel representationsspråk. EFGs är exponentiellt mer kompakta och också mer uttrycksfulla än normala-form spel. Letchford och Conitzer (2010) studerar hur man kan beräkna en optimal strategi för att engagera sig i EFGs och bevisa hårdhet resultat under flera antaganden om spelets struktur. Bošansk och al. (2015) ge ytterligare resultat särskilt för perfekt information EFG. Bosansky och Cermak (2015) utvecklar ett mixed-integer program (MIP) för att beräkna en Stackelberg strategi, och Cermak et al. (2016) utveckla ett iterativt tillvägagångssätt baserat på upperbounding lösningar från omfattande-form korrelerade Stackelberg equilibria. Till vår kännedom är vi de första att överväga osäkerhet om motståndaren i Stackelberg strategier för EFGs. Detta är viktigt eftersom EFGs är ett kraftfullt representationsspråk och eftersom det i praktiken finns typiskt osäkerhet om motståndaren. Vi har en kraftfull strategi för att modellera denna osäkerhet. Vi introducerar robust Stackelberg equilibria för EFGs, där osäkerheten handlar om motståndarens belöningar, samt de där motståndaren har begränsad lookahead och osäkerheten handlar om motståndarens nodutvärderingsfunktion. Vi utvecklar ett nytt minimiimportpris för den deterministiska limitedlookahead-inställningen. Vi utökar sedan MIM till den robusta inställningen för Stackelberg jämvikt under obegränsad och under begränsad lookahead av motståndaren. Vi visar att för det specifika fallet av intervall osäkerhet om motståndarens utbetalningar (eller om motståndarens nod utvärderingar i fallet med begränsad lookahead), robust Stackelberg equilibria kan beräknas med en MIM som är av samma asymptotiska storlek som för den deterministiska inställningen. Våra resultat för robust Stackelberg jämvikt i EFGs är relevanta för säkerhets-spel inställningar med sekventiella interaktioner, där EFG modeller kan mer kompakt representera vissa spel, jämfört med en normal-form representation (Bosansky och Cermak 2015). Robusta modeller är viktiga i säkerhetsspel, där motståndare modeller ofta har osäkerhet, både i standard säkerhetsspel (KiekarXiv:1711.08080v1 [cs.GT]
Även, medan lärande i samband med säkerhetsspel har dykt upp i litteraturen (Balcan et al. 2015; REF, detta dokument inför en RL-baserad strategi för hotscreening för första gången.
Robust Stackelberg Equilibria in Extensive-Form Games and Extension to Limited Lookahead
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}