Komplexität endlicher Teilinformationsspiele

12

Welche Komplexität besteht bei einem deterministischen Teilinformations-Nullsummenspiel mit nur endlich vielen Zuständen,
deren mögliche Ergebnisse [Verlieren, Unentschieden, Gewinnen] mit Werten [-1,0, + 1] sind, in
der Annäherung an den Wert solcher Zustände ein Spiel additiv innerhalb von ?ϵ

Insbesondere kann ich keinen Algorithmus dafür finden .
Der Rest dieses Beitrags ist ausschließlich der genaueren Beschreibung
des Problems gewidmet. Wenn Sie also bereits herausfinden können, was die Frage oben
in diesem Beitrag bedeutet, besteht für Sie kein Grund, den Rest dieses Beitrags zu lesen.

Bei einer Schiedsrichter-Maschine mit den Zuständen mit einem bestimmten Anfangszustand , einem Zustand dessen Bewertungspaar , einem Zustand dessen Bewertungspaar ist und Zustände des Formularss 0 s a [ - 1 , + 1 ] s b [ + 1 , - 1 ]{1,2,3,...,S}s0sein[-1,+1]sb[+1,-1]

[p1_info, p2_info, num_of_choices, player_to_move, next_state_table] wobei:

  • player_to_move{1,2}
  • next_state_table ist eine Funktion von{1,2,3,...,Anzahl_der_Wahlen}{1,2,3,...,S}
  • p1_info,p2_info,Anzahl_der_Wahlen1

Wenn sich die Maschine in diesem Zustand befindet:

  • sendet an Player_1 und sendet an Player_2,p1_infop2_info
  • sendet an den angegebenen Spieler, wartet auf ein Element von als Eingabe von diesem Spieler,Anzahl_der_Wahlen{1,2,3,...,Anzahl_der_Wahlen}
  • geht dann in den Zustand, der durchnext_state_table

Wenn die Maschine in einen der beiden anderen Zustände oder s b wechselt ,seinsb

  • stoppt mit dem Score-Paar dieses Zustands als Ausgabe

Es gibt ein natürliches Zwei-Spieler - Spiel: Der Schiedsrichter Maschine beginnt im Zustand , bieten die Spieler die Eingänge , dass der Schiedsrichter Maschine wartet, wenn die Schiedsrichter Maschine stoppt dann Partituren Spieler 1 der erste Wert des Ausgangspaares der Maschine und Spieler 2 erzielt den zweiten Wert des Ausgangspaares der Maschine, ansonsten erhalten beide Spieler den Wert 0. s0=1





Was ist die Komplexität des folgenden Problems?
Bei einem solchen Schiedsrichterautomaten und einer positiven Ganzzahl N geben Sie eine rationale Zahl aus
, die (additiv) innerhalb von 1 / N des Werts des natürlichen Spiels für Spieler 1 liegt.

Wie weiter oben in dieser Frage erwähnt, kann ich mir
keinen Algorithmus dafür ausdenken.

Marzio De Biasi
quelle
Kennen die Spieler die interne Struktur? Was ist der Vorteil von zusätzlichen Informationen, es gibt mehr mögliche Züge?
Domotorp
Ja. Es gibt ihnen eine bessere Vorstellung davon, wie der aktuelle Zustand ist.
Entschuldigung, aber ich verstehe es immer noch nicht. Dann kennen sie die interne Struktur, wissen aber nicht, wo sie sich gerade befinden? Machen Sie bitte die Beschreibung klar, ich bin sicher, dass ich nicht der einzige bin, der das Problem nicht verstehen kann.
Domotorp
3
Ist Ihr Modell dasselbe wie ein "rundenbasiertes stochastisches Nullsummenspiel mit Teilinformationen"?
Kristoffer Arnsfelt Hansen
1
@Kristoffer: Es ist nicht offensichtlich (zumindest für mich), dass mein Modell die Codierung zulässt irrationale Wahrscheinlichkeiten, obwohl mein Modell ansonsten diesem äquivalent ist.

Antworten:

6

HINWEIS: Mein angeblicher Algorithmus war falsch. Ich habe es gelöscht.

Eine Sache zu erkennen ist, dass es egal ist, ob das Spiel deterministisch ist oder nicht. Zum Randomisieren kann der Schiedsrichter jeden Spieler auffordern, eine Zufallszahl mod beizusteuern und diese dann hinzuzufügen. Es ist leicht zu zeigen , dass , wenn die Spieler ihre optimale Strategie zu verwenden, wobei die Summe eine Zufallszahl mod p , die der Schiedsrichter dann seine Strategie randomisieren nutzen kann. Dies erhöht die Anzahl der Zustände im Spiel nicht wesentlich.pp

Für eine untere Grenze der Komplexität ist nicht bekannt, dass die Frage der Approximation des Werts eines einfachen stochastischen Spiels in P enthalten ist . Mit dem oben genannten Randomisierungstrick ist es einfach, ein einfaches stochastisches Spiel als Schiedsrichterspiel mit einer polynomgroßen Nachschlagetabelle zu schreiben.

Peter Shor
quelle
Diese Randomisierungsidee (zumindest, wie Sie sie beschrieben haben) kann nur rationale Wahrscheinlichkeiten liefern. Außerdem implizieren die Definitionen, die in den ersten beiden von Ihnen verlinkten Artikeln verwendet wurden, dass ihre Spiele einen endlichen Spielbaum haben, wohingegen ich nur einen endlichen Zustandsraum benötige (wobei "state" nicht die Geschichte des Spiels beinhaltet).
Du hast recht ... der erste Teil meiner Antwort ist falsch. Lass es mich löschen. Ich bin mir ziemlich sicher, dass die Annäherung an den Wert einfacher stochastischer Spiele nicht in P liegt, selbst wenn alle Münzwürfe die Wahrscheinlichkeit 1/2 haben.
Peter Shor
1


ϵ0<ϵ

Eingabe: Ein Spiel wie in meiner Frage beschrieben
muss JA ausgeben, wenn: der Spielwert für Spieler 1 größer als 1 ist.ϵ
ϵ

Reste RE -hard auch wenn

player_to_move ist immer 1 (dh es wird nur 1 Spieler benötigt)
und
s 0 ≠ s a und s a sind nicht in Reichweite (next_state_table)
(dh der Spieler kann buchstäblich nicht verlieren)
und
p1_info und p2_info und number_of_choices sind unabhängig vom Staat
(dh die einzige Rückmeldung des Spielers ist, ob er gerade gewonnen hat oder nicht)

.


quelle