Iterativ eliminering af strengt dominerede strategier

Den iterative eliminering af strengt dominerede strategier også iterativ eliminering af strengt dominerede strategier eller iterativ eliminering af strengt dominerede strategier er en iterativ metode i spilteori til bestemmelse af Nash-ligevægter i spil i normal form .

Grundlæggende

For at forstå begrebet iterativ eliminering af de strengt dominerede strategier, skal arten af ​​en domineret strategi først forklares. En domineret strategi er en strategi, der ikke er til nogen fordel for spilleren og derfor ikke er det bedste svar på en modstanders strategi. Det er domineret af en såkaldt dominerende strategi . Formelt kan streng dominans repræsenteres som følger:

Vær et to-personers spil med udbetalingsfunktionerne for spiller 1 og 2 og strategirum og spiller 1 og 2. Fortsæt med at være og mulige strategier for spiller 1 (dvs. ). ${\ displaystyle G = \ {S_ {1}, S_ {2}; u_ {1}, u_ {2} \}}$${\ displaystyle u_ {1}, u_ {2}}$${\ displaystyle S_ {1}}$${\ displaystyle S_ {2}}$${\ displaystyle s_ {1} '}$${\ displaystyle s_ {1} ''}$${\ displaystyle s_ {1} ', s_ {1}' '\ i S_ {1}}$

Derefter er det strengt domineret af hvis: ${\ displaystyle s_ {1} '}$${\ displaystyle s_ {1} ''}$

${\ displaystyle u_ {1} (s_ {1} ', s_ {2}) <u_ {1} (s_ {1}' ', s_ {2})}$

for hver strategi for den anden spiller. ${\ displaystyle s_ {2} \ i S_ {2}}$

Proceduren

Den iterative eliminering af strengt dominerede strategier beskriver den successive eliminering af dominerede strategier, indtil der ikke er flere dominerede strategier. Denne procedure gør det muligt at forenkle spil til deres mulige realiseringer, ideelt set i det omfang der kun er én strategikombination tilbage. På denne måde kan Nash-ligevægte findes i bimatriser. I modsætning til iterativ eliminering af svagt dominerede strategier er resultatet af iterativ eliminering utvetydig med streng dominans (uanset rækkefølgen af ​​eliminering). Generelt kaldes strategier, der overlever denne eliminering, rationaliserbare strategier.

Ansøgning

Den iterative eliminering af strengt dominerede strategier bruges hovedsageligt i komplekse matrixspil. Ved at fremhæve irrelevante eller ringere strategier forenkles matrixens dimension, så spillet lettere kan håndteres.

eksempel

Følgende bimatrix er givet

	${\ displaystyle y_ {1}}$	${\ displaystyle y_ {2}}$
${\ displaystyle x_ {1}}$	${\ displaystyle 5}$ ${\ displaystyle 3}$	${\ displaystyle 6}$ ${\ displaystyle 6}$
${\ displaystyle x_ {2}}$	${\ displaystyle 4}$ ${\ displaystyle 2}$	${\ displaystyle 5}$ ${\ displaystyle 4}$

, Hvor , repræsentere spiller 1s strategier og , repræsenterer spiller 2 strategier. Vi starter med spiller 1. For spiller 1 er strategien strengt domineret af strategien ( er den dominerende strategi ). Af denne grund kan strategien slettes, og bimatrixen reduceres til: ${\ displaystyle x_ {1}}$${\ displaystyle x_ {2}}$${\ displaystyle y_ {1}}$${\ displaystyle y_ {2}}$${\ displaystyle x_ {2}}$${\ displaystyle x_ {1}}$${\ displaystyle x_ {1}}$${\ displaystyle x_ {2}}$

	${\ displaystyle y_ {1}}$	${\ displaystyle y_ {2}}$
${\ displaystyle x_ {1}}$	${\ displaystyle 5}$ ${\ displaystyle 3}$	${\ displaystyle 6}$ ${\ displaystyle 6}$

Vi fortsætter med spiller 2. Fra spiller 2's perspektiv er det strengt domineret af og kan derfor slettes. Følgende Nash-ligevægt forbliver: ${\ displaystyle y_ {1}}$${\ displaystyle y_ {2}}$

	${\ displaystyle y_ {2}}$
${\ displaystyle x_ {1}}$	${\ displaystyle 6}$ ${\ displaystyle 6}$

Ved således successivt at eliminere de dominerede strategier blev Nash-ligevægten fundet. Med denne metode kan selv komplekse bimatricer reduceres til deres realisering. ${\ displaystyle NGG: (x_ {1}, y_ {2})}$

Individuelle beviser

1. F Manfred J. Holler, Gerhard Illing: Introduktion til spilteori, s.105
2. ↑ Florian Bartholomae, Marcus Wiens: Spilteori: En applikationsorienteret lærebog s.71

Se også

• Løsningskoncept