Glossar der Spieltheorie - Glossary of game theory

Die Spieltheorie ist der Zweig der Mathematik, in dem Spiele untersucht werden, dh Modelle, die menschliches Verhalten beschreiben. Dies ist ein Glossar einiger Begriffe des Themas.

Definitionen eines Spiels

Notationskonventionen

Reale Nummern

${\ displaystyle \ mathbb {R}}$ .

Die Gruppe der Spieler

${\ displaystyle \ mathrm {N}}$ .

Strategieraum

${\ displaystyle \ Sigma \ = \ prod _ {i \ in \ mathrm {N}} \ Sigma \ ^ {i}}$ , wo

Der Strategiebereich von Spieler i

${\ displaystyle \ Sigma \ ^ {i}}$ ist der Raum aller möglichen Wege , auf denen Spieler i das Spiel spielen kann.

Eine Strategie für Spieler i

${\ displaystyle \ sigma \ _ {i}}$ ist ein Element von . ${\ displaystyle \ Sigma \ ^ {i}}$

Ergänzungen

${\ displaystyle \ sigma \ _ {- i}}$ Ein Element von ist ein Tupel von Strategien für alle Spieler außer i . ${\ displaystyle \ Sigma \ ^ {- i} = \ prod _ {j \ in \ mathrm {N}, j \ neq i} \ Sigma \ ^ {j}}$

Ergebnisraum

${\ displaystyle \ Gamma}$ ist in den meisten Lehrbüchern identisch mit -

Auszahlungen

${\ displaystyle \ mathbb {R} ^ {\ mathrm {N}}}$ und beschreibt, wie viel Gewinn (Geld, Vergnügen usw.) den Spielern bis zum Ende des Spiels zugeteilt wird.

Normalformspiel

Ein Spiel in normaler Form ist eine Funktion:

${\ displaystyle \ pi \: \ prod _ {i \ in \ mathrm {N}} \ Sigma \ ^ {i} \ to \ mathbb {R} ^ {\ mathrm {N}}}$

Angesichts des von den Spielern gewählten Tupels von Strategien erhält man eine Zuweisung von Zahlungen (angegeben als reelle Zahlen).

Eine weitere Verallgemeinerung kann erreicht werden, indem das Spiel in zwei Funktionen aufgeteilt wird:

${\ displaystyle \ pi \: \ prod _ {i \ in \ mathrm {N}} \ Sigma \ ^ {i} \ to \ Gamma}$

die Ergebnisfunktion des Spiels (einige Autoren nennen diese Funktion "die Spielform") und:

${\ displaystyle \ nu \: \ Gamma \ \ to \ mathbb {R} ^ {\ mathrm {N}}}$

die Zuweisung von Auszahlungen (oder Präferenzen ) an die Spieler für jedes Ergebnis des Spiels.

Umfangreiches Formspiel

Dies wird durch einen Baum gegeben , bei dem an jedem Scheitelpunkt des Baumes ein anderer Spieler die Wahl hat, eine Kante zu wählen . Die Ergebnismenge eines umfangreichen Formspiels ist normalerweise die Menge der Baumblätter.

Kooperatives Spiel

Ein Spiel, in dem Spieler Koalitionen bilden dürfen (und Koalitionsdisziplin durchsetzen dürfen). Ein kooperatives Spiel wird gegeben, indem für jede Koalition ein Wert angegeben wird:

${\ displaystyle \ nu \: 2 ^ {\ mathbb {P} (N)} \ to \ mathbb {R}}$

Es wird immer davon ausgegangen, dass die leere Koalition Null gewinnt. Lösungskonzepte für kooperative Spiele setzen normalerweise voraus, dass die Spieler die große Koalition bilden , deren Wert dann unter den Spielern aufgeteilt wird, um eine Zuteilung zu geben. ${\ displaystyle N}$${\ displaystyle \ nu (N)}$

Einfaches Spiel

Ein einfaches Spiel ist eine vereinfachte Form eines kooperativen Spiels, bei dem der mögliche Gewinn entweder als '0' oder '1' angenommen wird. Ein einfaches Spiel ist ein Paar ( N , W ), wobei W die Liste der "gewinnenden" Koalitionen ist , die in der Lage sind, die Beute zu erhalten ('1'), und N die Gruppe von Spielern ist.

Glossar

Akzeptables Spiel

ist eine Spielform , bei der das Spiel für jedes mögliche Präferenzprofil reine Nash-Gleichgewichte aufweist , die alle paretoeffizient sind .

Zuteilung von Waren

ist eine Funktion . Die Zuteilung ist ein grundlegender Ansatz zur Bestimmung des Gutes (z. B. Geld), das den Spielern unter den verschiedenen Ergebnissen des Spiels gewährt wird. ${\ displaystyle \ nu \: \ Gamma \ \ to \ mathbb {R} ^ {\ mathrm {N}}}$

Beste Antwort

Die beste Antwort auf eine bestimmte Ergänzung ist eine Strategie , die die Bezahlung von Spieler i maximiert . Formal wollen wir : . ${\ displaystyle \ sigma \ _ {- i}}$${\ displaystyle \ tau \ _ {i}}$
${\ displaystyle \ forall \ sigma \ _ {i} \ in \ \ Sigma \ ^ {i} \ quad \ quad \ pi \ (\ sigma \ _ {i}, \ sigma \ _ {- i}) \ leq \ pi \ (\ tau \ _ {i}, \ sigma \ _ {- i})}$

Koalition

ist eine beliebige Teilmenge der Gruppe von Spielern : . ${\ displaystyle \ mathrm {S} \ subseteq \ mathrm {N}}$

Condorcet-Gewinner

Bei einer Präferenz ν im Ergebnisbereich ist ein Ergebnis a ein Condorcet-Gewinner, wenn alle Nicht-Dummy-Spieler a allen anderen Ergebnissen vorziehen .

Entscheidbarkeit

Bezieht sich in Bezug auf die Spieltheorie auf die Frage nach der Existenz eines Algorithmus, der eine Antwort darauf geben kann und wird, ob ein Spiel gelöst werden kann oder nicht.

Bestimmtheit

Ein Teilgebiet der Mengenlehre, das die Bedingungen untersucht, unter denen der eine oder andere Spieler eines Spiels eine Gewinnstrategie hat, und die Konsequenzen der Existenz solcher Strategien. In der Mengenlehre untersuchte Spiele sind Gale-Stewart-Spiele - Zwei-Spieler-Spiele mit perfekter Information, bei denen die Spieler eine unendliche Folge von Zügen ausführen und es keine Unentschieden gibt.

Bestimmtes Spiel (oder streng bestimmtes Spiel )

In der Spieltheorie ist ein streng bestimmtes Spiel ein Nullsummenspiel für zwei Spieler , das mindestens ein Nash-Gleichgewicht aufweist, wobei beide Spieler reine Strategien anwenden .

Diktator

Ein Spieler ist ein starker Diktator, wenn er unabhängig von den anderen Spielern ein Ergebnis garantieren kann. ist ein schwacher Diktator, wenn er ein Ergebnis garantieren kann, aber seine Strategien dafür könnten vom Komplement-Strategievektor abhängen. Natürlich ist jeder starke Diktator ein schwacher Diktator. Formal: m ist ein starker Diktator, wenn: m ein schwacher Diktator ist, wenn: ${\ displaystyle m \ in \ mathbb {N}}$

${\ displaystyle \ forall a \ in \ mathrm {A}, \; \ existiert \ sigma \ _ {n} \ in \ Sigma \ ^ {n} \; st \; \ forall \ sigma \ _ {- n} \ in \ Sigma \ ^ {- n}: \; \ Gamma \ (\ sigma \ _ {- n}, \ sigma \ _ {n}) = a}$

${\ displaystyle \ forall a \ in \ mathrm {A}, \; \ forall \ sigma \ _ {- n} \ in \ Sigma \ ^ {- n} \; \ existiert \ sigma \ _ {n} \ in \ Sigma \ ^ {n} \; st \; \ Gamma \ (\ sigma \ _ {- n}, \ sigma \ _ {n}) = a}$

Ein anderer Weg, um es auszudrücken, ist:

Ein schwacher Diktator ist für jedes mögliche Ergebnis wirksam. ${\ displaystyle \ alpha}$

Ein starker Diktator ist für jedes mögliche Ergebnis wirksam. ${\ displaystyle \ beta}$

Ein Spiel kann nicht mehr als einen starken Diktator haben . Einige Spiele haben mehrere schwache Diktatoren (bei Stein-Papier-Scheren sind beide Spieler schwache Diktatoren, aber keiner ist ein starker Diktator ).

Siehe auch Wirksamkeit . Antonym: Dummy .

Dominiertes Ergebnis

Bei einer Präferenz ν im Ergebnisraum sagen wir, dass ein Ergebnis a von Ergebnis b dominiert wird (daher ist b die dominierende Strategie), wenn es von allen Spielern bevorzugt wird. Wenn darüber hinaus streng einige Spieler zieht b über ein , dann sagen wir , dass eine ist streng dominiert . Formal: zur Herrschaft und zur strengen Herrschaft. Ein Ergebnis a wird (streng) dominiert, wenn es (streng) von einem anderen Ergebnis dominiert wird . Ein Ergebnis a wird für eine Koalition S dominiert, wenn alle Spieler in S ein anderes Ergebnis a vorziehen . Siehe auch Condorcet-Gewinner .
${\ displaystyle \ forall j \ in \ mathrm {N} \; \ quad \ nu \ _ {j} (a) \ leq \ \ nu \ _ {j} (b)}$
${\ displaystyle \ existiert i \ in \ mathrm {N} \; st \; \ nu \ _ {i} (a) <\ nu \ _ {i} (b)}$

Dominierte Strategie

Wir sagen, dass die Strategie (stark) von der Strategie dominiert wird, wenn für ein Tupel mit Komplementstrategien der Spieler i durch das Spielen profitiert . Formal: und . Eine Strategie σ wird (streng) dominiert, wenn sie (streng) von einer anderen Strategie dominiert wird . ${\ displaystyle \ tau \ _ {i}}$${\ displaystyle \ sigma \ _ {- i}}$${\ displaystyle \ tau \ _ {i}}$
${\ displaystyle \ forall \ sigma \ _ {- i} \ in \ \ Sigma \ ^ {- i} \ quad \ quad \ pi \ (\ sigma \ _ {i}, \ sigma \ _ {- i}) \ leq \ pi \ (\ tau \ _ {i}, \ sigma \ _ {- i})}$
${\ displaystyle \ existiert \ sigma \ _ {- i} \ in \ \ Sigma \ ^ {- i} \ quad st \ quad \ pi \ (\ sigma \ _ {i}, \ sigma \ _ {- i}) <\ pi \ (\ tau \ _ {i}, \ sigma \ _ {- i})}$

Dummy

Ein Spieler i ist ein Dummy, wenn er keinen Einfluss auf das Ergebnis des Spiels hat. Dh wenn das Ergebnis des Spiels unempfindlich gegenüber der Strategie von Spieler i ist .

Antonyme: sagen wir , Veto , Diktator .

Wirksamkeit

Eine Koalition (oder ein einzelner Spieler) S ist wirksam für ein , wenn sie zwingen kann ein das Ergebnis des Spiels. S ist α-wirksam , wenn die Mitglieder der S - Strategien st haben , egal was das Komplement von S der Fall ist, wird das Ergebnis sein , ein .

S ist β-wirksam, wenn die Mitglieder von S für Strategien des Komplements von S mit Strategien antworten können, die das Ergebnis a sicherstellen .

Endliches Spiel

ist ein Spiel mit endlich vielen Spielern, von denen jeder eine endliche Reihe von Strategien hat .

Große Koalition

bezieht sich auf die Koalition mit allen Spielern. In kooperativen Spielen wird oft angenommen, dass sich die große Koalition bildet und der Zweck des Spiels darin besteht, stabile Zuschreibungen zu finden.

Gemischte Strategie

für Spieler i ist eine Wahrscheinlichkeitsverteilung P auf . Es versteht sich, dass Spieler i eine Strategie zufällig nach P wählt . ${\ displaystyle \ Sigma \ ^ {i}}$

Gemischtes Nash-Gleichgewicht

Gleich wie Pure Nash Equilibrium , definiert im Raum gemischter Strategien . Jedes endliche Spiel hat gemischte Nash-Gleichgewichte .

Pareto-Effizienz

Ein Ergebnis eines von Spielform π ist (stark) Pareto - effizient , wenn es zulässiger unter allen Präferenzprofilen .

Präferenzprofil

ist eine Funktion . Dies ist der ordinale Ansatz zur Beschreibung des Spielergebnisses. Die Präferenz beschreibt, wie zufrieden die Spieler mit den möglichen Ergebnissen des Spiels sind. Siehe Warenverteilung . ${\ displaystyle \ nu \: \ Gamma \ \ to \ mathbb {R} ^ {\ mathrm {N}}}$

Reines Nash-Gleichgewicht

Ein Element des Strategieraums eines Spiels ist ein reiner Nash-Gleichgewichtspunkt, wenn kein Spieler, von dem ich profitieren kann, von seiner Strategie abweichen kann , da die anderen Spieler mitspielen . Formal : . Es wird kein Gleichgewichtspunkt dominiert. ${\ displaystyle \ sigma \ = (\ sigma \ _ {i}) _ {i \ in \ mathrm {N}}}$${\ displaystyle \ sigma \ _ {i}}$${\ displaystyle \ sigma}$
${\ displaystyle \ forall i \ in \ mathrm {N} \ quad \ forall \ tau \ _ {i} \ in \ \ Sigma \ ^ {i} \ quad \ pi \ (\ tau \, \ sigma \ _ {- i}) \ leq \ pi \ (\ sigma \)}$

Sagen

Ein Spieler i hat einen Sprich , wenn er sich nicht um eine Dummy , das heißt , wenn es einige Tupel von Komplement Strategien st π (σ_i) ist nicht eine konstante Funktion.

Antonym: Dummy .

Shannon Nummer

Eine konservative Untergrenze der Spielbaumkomplexität des Schachs (10 ¹²⁰ ).

Gelöstes Spiel

Ein Spiel, dessen Ergebnis (Gewinn, Verlust oder Unentschieden) korrekt vorhergesagt werden kann, vorausgesetzt, dass alle Spieler perfekt spielen.

Wert

Ein Wert eines Spiels ist ein rational erwartetes Ergebnis . Es gibt mehr als ein paar Definitionen von Wert , beschreibt verschiedene Verfahren zur Herstellung einer Lösung , um das Spiel zu erhalten.

Einspruch

Ein Veto bezeichnet die Fähigkeit (oder das Recht) eines Spielers, zu verhindern, dass eine bestimmte Alternative das Ergebnis des Spiels ist. Ein Spieler mit dieser Fähigkeit wird als Vetospieler bezeichnet .

Antonym: Dummy .

Schwach akzeptables Spiel

ist ein Spiel mit reinen Nash-Gleichgewichten, von denen einige paretoeffizient sind .

Nullsummenspiel

ist ein Spiel, bei dem die Zuordnung über verschiedene Ergebnisse konstant ist . Formal: wlg können wir annehmen, dass diese Konstante Null ist. In einem Nullsummenspiel ist der Gewinn eines Spielers der Verlust eines anderen Spielers. Die meisten klassischen Brettspiele (z. B. Schach , Dame ) sind Nullsummen .
${\ displaystyle \ forall \ gamma \ \ in \ Gamma \ \ sum _ {i \ in \ mathrm {N}} \ nu \ _ {i} (\ gamma \) = const.}$

Verweise