Komplexität endlicher Teilinformationsspiele

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 ?$\epsilon$

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\}$$s_0$$s_a$$[-1,+1]$$s_b$$[+1,-1]$

$[\mbox{p1_info,p2_info,num_of_choices,player_to_move,next_state_table}]$ wobei:

• $\mbox{player_to_move} \in \{1,2\}$
• $\mbox{next_state_table}$ ist eine Funktion von$\{1,2,3,...,\mbox{num_of_choices}\} \to \{1,2,3,...,S\}$
• $\mbox{p1_info},\mbox{p2_info}, \mbox{num_of_choices} \geq 1$

Wenn sich die Maschine in diesem Zustand befindet:

• sendet an Player_1 und sendet an Player_2,$\mbox{p1_info}$$\mbox{p2_info}$
• sendet an den angegebenen Spieler, wartet auf ein Element von als Eingabe von diesem Spieler,$\mbox{num_of_choices}$$\{1,2,3,...,\mbox{num_of_choices}\}$
• geht dann in den Zustand, der durch$\mbox{next_state_table}$

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

• 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. $s_0 = 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.

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.$p$$p$

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.

$\epsilon$$0<\epsilon$

Eingabe: Ein Spiel wie in meiner Frage beschrieben
muss JA ausgeben, wenn: der Spielwert für Spieler 1 größer als 1 ist.$\hspace{.025 in}\epsilon$
$\epsilon$

Reste RE -hard auch wenn

player_to_move ist immer 1 (dh es wird nur 1 Spieler benötigt)
und
s ₀ ≠ 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)

.