Beste Antwort

Aus Wikiludia
(Unterschied zwischen Versionen)
Wechseln zu: Navigation, Suche
(Beste Antwort: Bezeichnungen)
 
(4 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt)
Zeile 1: Zeile 1:
Die Menge der sogenannten besten Antworten hat in der Spieltheorie eine große Bedeutung insbesondere für die Analyse eines Spiels sowie für die Suche und dem Nachweis von [[Nash-Gleichgewicht]]en. Die '''beste Antwort''' wird dabei durch die Fragestellung charakterisiert, welche Strategie sich am besten eignet, um seinen eigenen Nutzen unter Berücksichtigung der möglichen Strategien anderer Spieler zu maximieren.
+
Die Menge der besten Antworten hat in der Spieltheorie eine große Bedeutung für die Analyse eines Spiels in Normalform sowie für die Bestimmung von [[Nash-Gleichgewicht]]en. Die '''beste Antwort''' wird dabei durch die Fragestellung charakterisiert, welche Strategie sich am besten eignet, um seinen eigenen Nutzen unter Berücksichtigung einer vorgegebenen Strategiekombination der andere Spieler zu maximieren.
 
+
 
+
 
== Definitionen ==
 
== Definitionen ==
  
=== Definition: Beste Antwort ===
+
=== Beste Antwort ===
 
{|
 
{|
 
|width="5%" style="vertical-align:top" |
 
|width="5%" style="vertical-align:top" |
Zeile 10: Zeile 9:
 
<div style="margin: 0; margin-right:10px; padding: 0 1em 1em 1em; background-color:#DDFFFF; align:right;">
 
<div style="margin: 0; margin-right:10px; padding: 0 1em 1em 1em; background-color:#DDFFFF; align:right;">
 
<br>
 
<br>
In einem Normalformenspiel heißt eine Strategiekombination <math>\quad \hat s_i \in S_i</math> für Spieler <math>i \in M=\{1,\ldots ,N\}</math>  
+
In einem [[Normalform|Normalformenspiel]] (M,S,u) heißt eine Strategie <math>\quad \hat s_i \in S_i</math> des Spielers <math>i \in M=\{1,\ldots ,N\}</math> genau dann eine
'''beste Antwort''' auf <math>s_{-i} \in S_{-i}</math>, genau dann wenn <math>\forall s_i \in S_{i}: \quad u_i(\hat s_i,s_{-i}) \ge u_i(s_i,s_{-i})</math>. <br><br>
+
''beste Antwort'' auf <math>s_{-i} \in S_{-i}</math>, wenn  
Anders geschrieben: <math> \hat s_i</math> ist beste Antwort auf <math>s_{-i} \in S_{-i}</math> genau dann wenn <math> u_i(\hat s_i,s_{-i}) = max\{u_i(s_i,s_{-i}): s_i \in S_i\} </math>.
+
:<math>\forall s_i \in S_{i}: \quad u_i(\hat s_i,s_{-i}) \ge u_i(s_i,s_{-i})</math>. <br>
 +
Anders geschrieben: <math> \hat s_i</math> ist genau dann beste Antwort auf <math>s_{-i} \in S_{-i}\,,</math> wenn  
 +
:<math> u_i(\hat s_i,s_{-i}) = \max\{u_i(s_i,s_{-i}): s_i \in S_i\} </math>.
 
|
 
|
 
|}
 
|}
 +
;Notationen:
 +
Dabei wird für einen Spieler <math> i \in M </math> und für ein Strategieprofil <math> s=(s_1, \ldots ,s_N) \in S=S_1\times \ldots \times S_N</math> mit <math> s_{-i} </math> das N-1 - Tupel
 +
:<math> s_{-i} = (s_1, \ldots ,s_{i-1},s_{i+1}, \ldots ,s_N) </math>
 +
bezeichnet, also das Tupel, das entsteht, wenn bei s die Komponente <math> s_i</math> weggelassen wird. Mit <math> S_{-i} </math> wird entsprechend die Menge aller dieser <math> s_{-i} </math> bezeichnet:
 +
:<math> S_{-i} = \prod_{k=1, k\neq i}^N S_k \,.</math>
 +
Schließlich steht <math> (s_i,s_{-i}) </math> für s, und <math> (\hat s_i,s_{-i})</math> für <math> (\hat s_i,s_{-i}) = (s_1, \ldots ,s_{i-1},\hat s_i,s_ {i+1}, \ldots , s_N) \,.</math>
  
 +
=== Korrespondenz der besten Antworten ===
  
=== Definition: Abbildung der besten Antwort ===
+
{|
 +
|width="5%" style="vertical-align:top" |
 +
|width="90%" style="vertical-align:top"|
 +
<div style="margin: 0; margin-right:10px; padding: 0 1em 1em 1em; align:right;">
 +
<br>
 +
Die mengenwertige Abbildung <math> b_i : S_{-i} \rightarrow \mathfrak {P}(S_i) </math>  mit
 +
:<math> b_i (s_{-i}) := \{ \hat s_i \in S_i: u_i(\hat s_i,s_{-i}) = \max\{u_i(s_i,s_{-i}): s_i \in S_i\} \}\subset S_i </math>
 +
heißt ''Korrespondenz der besten Antworten für den Spieler i''.
 +
<br>
 +
Die mengenwertige Abbildung
 +
<math> b : S \rightarrow \prod_{i=1}^N \mathfrak {P}(S_i) </math> mit 
 +
:<math>s=(s_1, \ldots ,s_N) \mapsto b(s) := b_1(s_{-1})\times b_2(s_{-2}) \times \ldots \times b_N (s_{-N}) </math>
 +
heißt ''Korrespondenz der besten Antworten'' oder ''Beste-Antwort-Korrespondenz''.
 +
|
 +
|}
  
 +
== Existenz und Zusammenhang mit Nash-Gleichgewichten ==
  
; Definition 1
+
;Existenz:
:Eine mengenwertige Abbildung <math> r_i : S_{-i} \rightarrow \mathfrak {P}(S_i) </math> mit den Funktionswerten <math> r_i (s_{-i}) </math> := {<math> u_i(\hat s_i,s_{-i}) = max\{u_i(s_i,s_{-i}): s_i \in S_i\} </math>} heißt '''Abbildung <math> r_i </math> der besten Antwort''' für den Spieler i.
+
:In jedem Normalformenspiel existiert die Beste-Antwort-Korrespondenz. Für endliche Spiele ist <math> b_k(s_{-k}) \neq \emptyset</math> für alle <math> k \in M</math> und alle <math> s_{-k}\in S_{-k}\,,</math> weil das Maximum einer Funktion (hier <math> s_k \mapsto u_k(s_k,s_{-k}) \,</math>) über einer endlichen Menge stets existiert. Dasselbe gilt für den Fall, dass alle Strategiemengen <math> S_k</math> kompakte Räume und die Nutzenfunktionen  <math> u_k : S \to \mathbb R</math> stetige Funktionen sind.  
  
 
+
;Beste-Antwort-Funktion:
;Definition 2
+
Es sei <math> b_i (s_{-i}) \not= \emptyset </math> für alle Spieler i und für alle Strategiekombinationen <math> s_{-i} \in S_{-i} </math>. Dann kann man (unter Ausnutzung des Auswahlaxioms)  <math> r_i (s_{-i}) \in b_i (s_{-i}) </math> auswählen. Die Funktion <math> r_i : S_{-i} \rightarrow S_{i} </math> ist dann eine feste ''Beste-Antwort-Funktion'' und es gilt <math> r_i(s_{-i})\in b_i(s_{-i})\,.</math>
:Eine mengenwertige Funktion, deren Funktionswert das kartesische Produkt der Funktionswerte der <math> r_i </math> aus Definition 1, i = 1, ... , m, 
+
:<math> r : S \rightarrow \prod_{i=1}^m \mathfrak {P}(S_i) </math> mit den Funktionswerten <math> r(s) := (r_1(s_{-1}), \ldots, r_m (s_{-m}) </math> heißt '''Abbildung r der besten Antwort'''.
+
 
+
 
+
== Existenz und Zusammenhang mit Nash-Gleichgewichten ==
+
  
 
;Satz:
 
;Satz:
:Eine Strategiekombination  <math> s' \in  S  </math> ist genau dann ein Nash-Gleichgewicht, wenn <math> s' \in  r (s') </math>.
+
:Eine Strategiekombination  <math> s' \in  S  </math> ist genau dann ein Nash-Gleichgewicht, wenn <math> s' \in  b (s') </math>.
  
 
;Beweis:
 
;Beweis:
:Sei <math> s' \in  r (s') </math>, das heißt, es gelte <math> \forall i: s'_i \in  r_i (s'_{-i}) </math>. Dann folgt aus der Definition <math> u_i(s') = max\ u_i(s^*_i,s_{-i}) </math>, also <math> u_i(s') \ge u_i(s_i,s_{-i}) \forall s_i \in S_{i}, \forall s_i </math>, die Definition des [[Nash-Gleichgewicht]]s.
+
Sei <math> s' = (s'_1, \ldots ,s'_N) \in  b (s') </math>. Das heißt, es gilt: <math> \forall i: s'_i \in  b_i (s'_{-i}) </math>. Daher ist nach Definition <math> u_i(s') = \max_{s_i \in S_i}\ u_i(s_i,s'_{-i}) </math>, also ist die Definition des [[Nash-Gleichgewicht]]s
: Sei s' ein [[Nash-Gleichgewicht]]. Dann gilt <math> u_i(s') \ge u_i(s_i,s_{-i}) \forall s_i \in S_{i}, \forall s_i </math>, also <math> \forall i: s'_i \in  r_i (s'_{-i}) </math>, woraus nach Definition natürlich  <math> s' \in  r (s') </math> folgt.
+
:<math> \forall i\in M\,\, \forall s_i \in S_{i}\,\,  u_i(s') \ge u_i(s_i,s'_{-i}) </math>
 
+
erfüllt.<br>
;Folgerung:
+
Sei umgekehrt s' ein [[Nash-Gleichgewicht]]. Dann gilt <math> \forall i\in M\,\, \forall s_i \in S_{i}\,\,  u_i(s') \ge u_i(s_i,s'_{-i}) </math>, also <math> \forall i\in M: s'_i \in  b_i (s'_{-i}) </math>, also <math> s' \in  b (s') \,.</math>  
:Da nach dem [[Existenz von Nash-Gleichgewichten|Satz von Nash]] in jedem endlichen Spiel in Normalform ein [[Nash-Gleichgewicht]] in gemischten Strategien existiert, folgert aus diesem Satz, dass auch in jedem endlichen Spiel in Normalform eine beste Antwort existiert.
+
 
+
  
 
== Beispiele ==
 
== Beispiele ==
Zeile 48: Zeile 64:
 
#:* <math> u_1 </math> (A, S) = 0 > -3 = <math>u_1</math> (S, S)
 
#:* <math> u_1 </math> (A, S) = 0 > -3 = <math>u_1</math> (S, S)
 
#:* <math> u_1 </math> (A, A) = -8 > -10 = <math> u_1</math> (S, A)
 
#:* <math> u_1 </math> (A, A) = -8 > -10 = <math> u_1</math> (S, A)
#: (Die Haftstrafen wurden als negative Konsequenz zum leichteren Verständnis mit negativen Jahresangaben versehen; für Spieler 2 analog)
+
#:(Die Haftstrafen wurden als negative Konsequenz zum leichteren Verständnis mit negativen Jahresangaben versehen; für Spieler 2 analog)
# Wie viele Lösungen basiert auch die Lösung im [[Oligopole:Cournot-Duopol|Cournot-Duopol]] auf dem Prinzip der besten Antwort.
+
# Auch die Lösung im [[Oligopole:Cournot-Duopol|Cournot-Duopol]] beruht auf der Bestimmung der besten Antworten.
 
# Bei der [[Rückwärtsinduktion]] wird in jedem Schritt das Prinzip der besten Antwort angewendet.
 
# Bei der [[Rückwärtsinduktion]] wird in jedem Schritt das Prinzip der besten Antwort angewendet.
# Sei <math> b_i (s_i) \not= \emptyset \quad \forall s_i \in S_{i} </math> und <math> \forall i </math>. Hier kann man <math> r_i (s_{-i}) \in b_i (s_{-k}) </math> auswählen. Die Funktion <math> r_i : S_{-i} \rightarrow S_{i} </math> ist dann eine feste beste Antwort Funktion.
+
# Für die beste Antwort existiert eine beste-Antwort Äquivalenz, die im Artikel [[Äquivalenz in Spielen]] näher beschrieben wird.
 
+
  
 
== Strikt und schwach beste Antwort ==
 
== Strikt und schwach beste Antwort ==
Zeile 58: Zeile 73:
 
Vergleichbar mit der Unterscheidung von strikter und schwacher Dominanz kann man auch die Menge der besten Antworten in strikt oder streng beste Antworten und schwach beste Antworten unterscheiden:
 
Vergleichbar mit der Unterscheidung von strikter und schwacher Dominanz kann man auch die Menge der besten Antworten in strikt oder streng beste Antworten und schwach beste Antworten unterscheiden:
  
;Definition  
+
;Definition '''Strikt beste Antwort'''
:'''Strikt beste Antwort'''
+
:Eine Strategie <math> s_i^* </math> heißt strikt beste Antwort auf eine Strategie <math> s_{-i} </math> genau dann, wenn gilt: <math> u_i (s_i^*, s_{-i}) > u_i(s_i,s_{-i})  \quad \forall s_i \in S_{i} \setminus \{s_i^*\}</math>.
:Eine Strategie <math> s_i^* </math> heißt strikt beste Antwort auf eine Strategie <math> s_{-i} </math> genau dann, wenn gilt: <math> u_i (s_i^*, s_{-i}) > u_i(s_i,s_{-i})  \quad \forall s_i \in S_{i} \setminus s_i^*</math>.
+
  
;Definition
+
;Definition '''Schwach beste Antwort'''
:'''Schwach beste Antwort'''
+
 
:Eine Strategie <math> s_i^* </math> heißt schwach beste Antwort auf eine Strategie <math> s_{-i} </math> genau dann, wenn gilt: <math> u_i (s_i^*, s_{-i}) \ge u_i(s_i,s_{-i})  \quad \forall s_i \in S_{i} </math> und  
 
:Eine Strategie <math> s_i^* </math> heißt schwach beste Antwort auf eine Strategie <math> s_{-i} </math> genau dann, wenn gilt: <math> u_i (s_i^*, s_{-i}) \ge u_i(s_i,s_{-i})  \quad \forall s_i \in S_{i} </math> und  
 
:<math> \exists  \hat s_i \in S_i \setminus s_i^* </math> mit <math> u_i (\hat s_i, s_{-i}) = u_i(s_i^*,s_{-i}) </math>.
 
:<math> \exists  \hat s_i \in S_i \setminus s_i^* </math> mit <math> u_i (\hat s_i, s_{-i}) = u_i(s_i^*,s_{-i}) </math>.
  
 
+
Es ist leicht zu sehen, dass es anders als bei schwach besten Antworten nicht zwei verschiedene strikt beste Antworten geben kann.<br>
Es ist leicht zu sehen, dass es im Gegensatz zu schwach besten Antworten nicht zwei konkurrierende strikt beste Antworten geben kann.
+
Außerdem beachte man: ''schwach beste Antwort'' ist formal stärker als ''beste Antwort''.
 
+
  
 
== Quellen ==
 
== Quellen ==
 
* Riechmann, Thomas: Spieltheorie, Vahlen, München, 2., vollst. überarb. Aufl. 2007, ISBN 978-3-800-63505-4
 
* Riechmann, Thomas: Spieltheorie, Vahlen, München, 2., vollst. überarb. Aufl. 2007, ISBN 978-3-800-63505-4
 
* Schlee, Walter: Einführung in die Spieltheorie, Vieweg, Wiesbaden, 1. Aufl. 2004, ISBN 3-528-03214-6
 
* Schlee, Walter: Einführung in die Spieltheorie, Vieweg, Wiesbaden, 1. Aufl. 2004, ISBN 3-528-03214-6

Aktuelle Version vom 11. Februar 2009, 12:51 Uhr

Die Menge der besten Antworten hat in der Spieltheorie eine große Bedeutung für die Analyse eines Spiels in Normalform sowie für die Bestimmung von Nash-Gleichgewichten. Die beste Antwort wird dabei durch die Fragestellung charakterisiert, welche Strategie sich am besten eignet, um seinen eigenen Nutzen unter Berücksichtigung einer vorgegebenen Strategiekombination der andere Spieler zu maximieren.

Inhaltsverzeichnis

Definitionen

Beste Antwort


In einem Normalformenspiel (M,S,u) heißt eine Strategie \quad \hat s_i \in S_i des Spielers i \in M=\{1,\ldots ,N\} genau dann eine beste Antwort auf s_{-i} \in S_{-i}, wenn

\forall s_i \in S_{i}: \quad u_i(\hat s_i,s_{-i}) \ge u_i(s_i,s_{-i}).

Anders geschrieben:  \hat s_i ist genau dann beste Antwort auf s_{-i} \in S_{-i}\,, wenn

 u_i(\hat s_i,s_{-i}) = \max\{u_i(s_i,s_{-i}): s_i \in S_i\} .
Notationen

Dabei wird für einen Spieler  i \in M und für ein Strategieprofil  s=(s_1, \ldots ,s_N) \in S=S_1\times \ldots \times S_N mit si das N-1 - Tupel

 s_{-i} = (s_1, \ldots ,s_{i-1},s_{i+1}, \ldots ,s_N)

bezeichnet, also das Tupel, das entsteht, wenn bei s die Komponente si weggelassen wird. Mit Si wird entsprechend die Menge aller dieser si bezeichnet:

 S_{-i} = \prod_{k=1, k\neq i}^N S_k \,.

Schließlich steht (si,si) für s, und  (\hat s_i,s_{-i}) für  (\hat s_i,s_{-i}) = (s_1, \ldots ,s_{i-1},\hat s_i,s_ {i+1}, \ldots , s_N) \,.

Korrespondenz der besten Antworten


Die mengenwertige Abbildung  b_i : S_{-i} \rightarrow \mathfrak {P}(S_i) mit

 b_i (s_{-i}) := \{ \hat s_i \in S_i: u_i(\hat s_i,s_{-i}) = \max\{u_i(s_i,s_{-i}): s_i \in S_i\} \}\subset S_i

heißt Korrespondenz der besten Antworten für den Spieler i.
Die mengenwertige Abbildung  b : S \rightarrow \prod_{i=1}^N \mathfrak {P}(S_i) mit

s=(s_1, \ldots ,s_N) \mapsto b(s) := b_1(s_{-1})\times b_2(s_{-2}) \times \ldots \times b_N (s_{-N})

heißt Korrespondenz der besten Antworten oder Beste-Antwort-Korrespondenz.

Existenz und Zusammenhang mit Nash-Gleichgewichten

Existenz
In jedem Normalformenspiel existiert die Beste-Antwort-Korrespondenz. Für endliche Spiele ist  b_k(s_{-k}) \neq \emptyset für alle  k \in M und alle  s_{-k}\in S_{-k}\,, weil das Maximum einer Funktion (hier  s_k \mapsto u_k(s_k,s_{-k}) \,) über einer endlichen Menge stets existiert. Dasselbe gilt für den Fall, dass alle Strategiemengen Sk kompakte Räume und die Nutzenfunktionen  u_k : S \to \mathbb R stetige Funktionen sind.
Beste-Antwort-Funktion

Es sei  b_i (s_{-i}) \not= \emptyset für alle Spieler i und für alle Strategiekombinationen   s_{-i} \in S_{-i} . Dann kann man (unter Ausnutzung des Auswahlaxioms)  r_i (s_{-i}) \in b_i (s_{-i}) auswählen. Die Funktion  r_i : S_{-i} \rightarrow S_{i} ist dann eine feste Beste-Antwort-Funktion und es gilt  r_i(s_{-i})\in b_i(s_{-i})\,.

Satz
Eine Strategiekombination  s' \in  S  ist genau dann ein Nash-Gleichgewicht, wenn  s' \in  b (s') .
Beweis

Sei  s' = (s'_1, \ldots ,s'_N) \in  b (s') . Das heißt, es gilt:  \forall i: s'_i \in  b_i (s'_{-i}) . Daher ist nach Definition  u_i(s') = \max_{s_i \in S_i}\ u_i(s_i,s'_{-i}) , also ist die Definition des Nash-Gleichgewichts

 \forall i\in M\,\, \forall s_i \in S_{i}\,\,  u_i(s') \ge u_i(s_i,s'_{-i})

erfüllt.
Sei umgekehrt s' ein Nash-Gleichgewicht. Dann gilt  \forall i\in M\,\, \forall s_i \in S_{i}\,\,  u_i(s') \ge u_i(s_i,s'_{-i}) , also  \forall i\in M: s'_i \in  b_i (s'_{-i}) , also  s' \in  b (s') \,.

Beispiele

  1. Im Fall uj = 0 sind alle Strategien beste Antworten, da trivialerweise \forall s_i \in S_{i}: u_i(\hat s_i,s_{-i}) \ge u_i(s_i,s_{-i}) für alle Strategien erfüllt ist.
  2. Im Gefangenendilemma ist für beide Spieler A (Aussagen) die jeweils beste Antwort sowohl auf S (Schweigen) als auch auf A:
    • u1 (A, S) = 0 > -3 = u1 (S, S)
    • u1 (A, A) = -8 > -10 = u1 (S, A)
    (Die Haftstrafen wurden als negative Konsequenz zum leichteren Verständnis mit negativen Jahresangaben versehen; für Spieler 2 analog)
  3. Auch die Lösung im Cournot-Duopol beruht auf der Bestimmung der besten Antworten.
  4. Bei der Rückwärtsinduktion wird in jedem Schritt das Prinzip der besten Antwort angewendet.
  5. Für die beste Antwort existiert eine beste-Antwort Äquivalenz, die im Artikel Äquivalenz in Spielen näher beschrieben wird.

Strikt und schwach beste Antwort

Vergleichbar mit der Unterscheidung von strikter und schwacher Dominanz kann man auch die Menge der besten Antworten in strikt oder streng beste Antworten und schwach beste Antworten unterscheiden:

Definition Strikt beste Antwort
Eine Strategie  s_i^* heißt strikt beste Antwort auf eine Strategie si genau dann, wenn gilt:  u_i (s_i^*, s_{-i}) > u_i(s_i,s_{-i})  \quad \forall s_i \in S_{i} \setminus \{s_i^*\}.
Definition Schwach beste Antwort
Eine Strategie  s_i^* heißt schwach beste Antwort auf eine Strategie si genau dann, wenn gilt:  u_i (s_i^*, s_{-i}) \ge u_i(s_i,s_{-i})  \quad \forall s_i \in S_{i} und
 \exists  \hat s_i \in S_i \setminus s_i^* mit  u_i (\hat s_i, s_{-i}) = u_i(s_i^*,s_{-i}) .

Es ist leicht zu sehen, dass es anders als bei schwach besten Antworten nicht zwei verschiedene strikt beste Antworten geben kann.
Außerdem beachte man: schwach beste Antwort ist formal stärker als beste Antwort.

Quellen

  • Riechmann, Thomas: Spieltheorie, Vahlen, München, 2., vollst. überarb. Aufl. 2007, ISBN 978-3-800-63505-4
  • Schlee, Walter: Einführung in die Spieltheorie, Vieweg, Wiesbaden, 1. Aufl. 2004, ISBN 3-528-03214-6
Ansichten
Meine Werkzeuge
Navigation
Werkzeuge