Gra na kilku wykresach

Rozważ następującą grę na ukierunkowanym wykresie ważonym $G$ z chipem w pewnym węźle.

Wszystkie węzły $G$ oznaczone są literą A lub B.

Jest dwóch graczy Alice i Bob. Celem Alicji (Bob) jest przesunięcie czipa do węzła oznaczonego literą A (B).

Początkowo Alice i Bob mają odpowiednio $m_A$ i $m_B$ dolarów.

Jeśli gracz znajduje się na pozycji przegrywającej (tzn. Bieżąca pozycja żetonu jest oznaczona przeciwną literą), może on przenieść żeton do sąsiedniego węzła. Taki ruch kosztuje kilka dolarów (waga odpowiedniej krawędzi).

Gracz przegrywa, jeśli znajduje się na przegranej pozycji i nie ma pieniędzy, aby to naprawić.

Rozważmy teraz GRA językowa, która składa się ze wszystkich ukierunkowanych ważonych wykresów $G$ (wszystkie wagi są dodatnimi liczbami całkowitymi), początkowej pozycji układu oraz literami Alicji i Boba, które są podane w jednostkowej reprezentacji

tak, że Alice ma zwycięską strategię w tej grze.

GAME język należący do P . Rzeczywiście, obecna pozycja gry jest określona przez pozycję chipa i bieżące stolice Alicji i Boba, więc programowanie dynamiczne działa (tutaj ważne jest, aby początkowe kapitały były podawane w postaci jednoargumentowej).

Teraz rozważ następujące uogólnienie tej gry. Rozważyć kilka skierowanych ważone wykresy $G_1, \ldots G_n$ w układ na każdym wykresie. Wszystkie węzły wszystkich wykresów są oznaczone A i B. Teraz Bob wygrywa, jeśli wszystkie żetony są oznaczone B, a Alice wygrywa, jeśli co najmniej jeden żeton jest oznaczony A.

Rozważmy wielu języków grze, który składa się ze wszystkich wykresach $G_1, \ldots, G_n$ początkowe położenie i literami $m_A$ i $m_B$ (w jednoargumentowy reprezentacji) tak, Alicja wygrywa odpowiedniego gry. Ważne jest, aby wielkie litery były wspólne dla wszystkich grafów, więc nie jest to tylko kilka niezależnych GRA.

Pytanie Jaka jest złożoność języka MULTI-GAMES? (Czy to też należy do P, czy jest jakiś powód, aby sądzić, że ten problem jest trudny?)

UPD1 Neal Young zaproponował wykorzystanie teorii Conwaya. Nie wiem jednak, czy można zastosować tę teorię do kilku gier ze wspólnym kapitałem.

UPD2 Chcę pokazać przykład, który pokazuje, że MULTI-GAME nie jest bardzo prosta. Niech Alice podzieli swój kapitał $m_A$ na niektóre $n$ składników $m_A = a_1 + a_2 + \ldots a_n$ (Ona ma zamiar użyć $a_i$ dolary dla $i$ -tej wykresie). Zdefiniuj $b_i$ jako minimalnej liczby taki, że w $i$ -ty gry Bob wygrywa, jeśli Alicja i Bob mają ja i b i dolarów odpowiednio. Jeśli b 1 + … b$a_i$$b_i$$b_1 + \ldots b_n > m_B$ (dla niektórych podziałów$m_A = a_1 + a_2 + \ldots a_n$ ) wtedy Alice wygrywa. Jednak przeciwieństwo nie jest prawdą. Rozważ dwie kopie poniższego wykresu (początkowo układ znajduje się po lewej stronie A):

Dla jednego wykresu wygrywa Bob, jeśli $m_A=0$ i $m_B=2$ lub jeśli $m_A=1$ i $m_B=3$ . Jednak w grze z dwiema kopiami tego wykresu Bob przegrywa, jeśli $m_A=1$ i $m_B=5$ . Rzeczywiście, Bob musiał spędzić $4$ lub $5$ dolarów, aby przesunąć oba chipy do węzła naznaczonym $B$ . Następnie Alice może przenieść co najmniej jeden żeton do węzła oznaczonego literą A. Po tym Bob nie ma pieniędzy, aby zapisać swoją pozycję.

UPD3 Ponieważ pytanie o dowolne wykresy wydaje się trudne, rozważ konkretne wykresy. Oznacz węzły niektórych wykresów $G_i$ jako $1, \ldots k$ . Moje ograniczenie jest następujące: dla każdej pary $i<j$ istnieje krawędź od $i$ do $j$ i nie ma odwrotnej krawędzi. Istnieje również ograniczenie kosztów krawędzi: dla $i<j<k$ krawędź $j$ do $k$ nie jest większa niż od $i$ do $k$ .

Ponieważ odpowiedź Stevena Stadnickiego nie wydaje się być zaakceptowana przez pytającego, doszedłem do wniosku, że nadal przydatne może być dostarczenie aktualizacji: mam redukcję z 3SAT do MULTI-GAME. Nie przyjrzałem się uważnie odpowiedzi Stevena ani nie podążyłem za linkiem, który podał, ale na podstawie poniższej redukcji nie zdziwię się, jeśli MULTI-GAME jest rzeczywiście ukończony na PSPACE. Jednak nie zawracam sobie głowy przedłużeniem tego wyniku poza twardość NP.

Instancja 3SAT składa się z klauzul $C_1, \dots, C_m$ , przy czym każda klauzula ma postać $C_i = L_{i1} \vee L_{i2} \vee L_{i3}$ gdzie każda $L_{ik}$ jest jedną ze zmiennych $x_1, \dots, x_n$ lub negacja jednej ze zmiennych.

Biorąc pod uwagę taką instancję 3SAT, redukcja tworzy instancję MULTI-GAME składającą się z $n + 1$ gier - jednej dla każdej zmiennej i innej gry wykorzystywanej jako ujście nadwyżki kapitału. Najpierw zdefiniujemy strukturę wykresów dla każdej gry, następnie popatrzymy na przykład i omówimy podstawową ideę, a następnie ustalimy, jakie dokładne koszty przypisać do krawędzi, aby utrzymać mocne ograniczenie.

Po pierwsze, zmienny wykres gry $G_j$ dla każdej zmiennej $x_j$ :

1. Utwórz wierzchołek oznaczony $x_j$ oznaczonyA (tj. Zwycięski wierzchołek dla Alicji). Chip dla$G_j$ zaczyna się na wierzchołku$x_j$ .
2. Utwórz wierzchołek oznaczony $T$ i wierzchołek oznaczony $F$ , każdy oznaczony B (tzn. Oba wygrywają pozycje dla Boba). Utwórz skierowane krawędzie od $x_j$ do $T$ i $F$ , oba z kosztem $1$ .

3. Dla każdego literału $L_{ik}$ klauzuli $C_i$ , jeśli $L_{ik} = x_j$ lub $L_{ik} = \neg x_j$ , utwórz wierzchołki oznaczone $C_iTA$ i $C_iFA$ oznaczone A i wierzchołki oznaczone $C_iTB$ i $C_iFB$ oznaczone B. Dodaj krawędzie $(T, C_iTA)$ i$(F, C_iFA)$ z kosztami ustawionymi na$l_{ik}$ . (Będziemy określić$l_{ik}$ później).

   Dodaj krawędzie $(C_iTA, C_iTB)$ i $(C_iTA, C_iTB)$ . Jeśli $L_{ik} = x_j$ , to ustaw $(C_iTA, C_iTB)$ na $l_{ik} - 1$i( C i TA, C i T B ) na l i k . W innym przypadku ( C i$(C_iTA, C_iTB)$$l_{ik}$$(C_iTA, C_iTB)$koszt T A , C i T B ) na$l_{ik}$ orazkoszt$(C_iTA, C_iTB)$ na$l_{ik} - 1$ .

Gra w zlew kapitału:

1. Utwórz wierzchołek oznaczony literą $C$ , oznaczony literą B.
2. Dla każdego punktu $C_i$ , tworzyć wierzchołek oznaczony $C_iA$ oznaczone A, a wierzchołek oznaczony $C_iB$ oznaczony B. Tworzenie krawędzi $(C, C_iA)$ z kosztami krawędzi $c_i$ (ponownie określane poniżej) oraz krawędź $(C_iA, C_iB)$ również o koszcie krawędzi$c_i$ .

Jest to wiele do zrobienia, więc mam nadzieję, że przykład sprawi, że będzie to trochę łatwiejsze do strawienia. Nasza instancja 3SAT wygląda następująco:

$C_1 = x_1 \vee x_2 \vee \neg x_3$

$C_2 = x_2 \vee x_3 \vee \neg x_4$

$C_3 = \neg x_1 \vee \neg x_3 \vee x_4$

Redukcja zamienia to wystąpienie w 4 zmienne wykresy gier i 1 wykres ujścia kapitału. Na poniższych schematach czerwone wierzchołki są oznaczone literą A (tj. Wygrywające pozycje dla Alicji), a cyjanowe wierzchołki są oznaczone literą B (wygrywające pozycje dla Boba).

Wykres dla $x_1$ :

Wykres dla $x_2$ :

$x_3$

$x_4$

Wykres dla ujścia kapitału:

Pomysł jest następujący:

Bob jest zmuszony zrobić pierwszy $n$$n$

Alice będzie miała wystarczającą ilość kapitału, aby wykonać dokładnie 4 ruchy, z których każdy będzie musiał mieć wystarczającą ilość kapitału, aby mógł wygrać. Wartości $c_i$ a $l_{ik}$$C_i$

$C_i$$C_i = L_{i1} \vee L_{i2} \vee L_{i3}$$k \in \{1, 2, 3\}$$L_{ik} = x_j$$\neg x_j$$C_i?A$$x_j$$C_iA$

$C_i?A$$C_iTA$$C_iFA$

$C_i$$C_i$$l_{i1} + l_{i2} + l_{i3} + c_i$$C_i$$1$$c_i$$l_{ik}$ wartości, a początkowymi literami Alicji i Boba jest upewnienie się, że wspomniany rabat jest decydującym czynnikiem decydującym o tym, czy Alice lub Bob wygra.

$b = m + 1$

$l_{ik} = 2b^{10} + ib^{2k}$$k \in \{1, 2, 3\}$

$c_i = 3b^{10} + b^8 - \sum_{k=1}^3 ib^{2k}$

$9b^{10} + b^8$

$9b^{10} + b^8 + n - 1.$

$m$

$C_i$$l_{i1} + l_{i2} + l_{i3} + c_i = 9b^{10} + b^8$$1$$n$

$C_i$$C_i$

Jeśli otwarcie Boba spełnia wszystkie klauzule, możemy argumentować ograniczenia opcji Alice, które wykluczają jakąkolwiek inną możliwość wygranej Alice. Zauważ, że kolejność, w jakiej Alice wykonuje swoje ruchy, jest nieistotna, ponieważ odpowiedzi Boba są wymuszone, a całkowity kapitał, którego będzie potrzebował Bob, aby zareagować na ruchy Alice, nie jest zmieniany przez kolejność ruchów Alice.

• $\ge 5b^{10}$
• $\ge 9b^{10} + 3b^8 - 3b^7 > 9b^{10} + 2b^8$$\le 8b^{10} + 2b^8 + b^7$
• $\le 8b^{10} + 4b^7$

$b^{10}$$b^8$$9b^{10} + b^8$$C_iA$$b^{10}$$b^8$$\sum_{k=1}^3 ib^{2k}$$1$

• $l_{j3}$$C_j$$\le 3b^5$
• $l_{j3}$$l_{i3}$$l_{j3}$$j > i$$\ge (i+1)b^6$$l_{j3}$$j < i$$l_{(i - j)3}$$b^6$$b^2$$b^2$

$l_{i2}$$l_{i1}$$C_i$$l_{ik}$$1$

Uwaga do mojej poprzedniej odpowiedzi: z perspektywy czasu jest oczywiste, że dla wariantu MULTI-GAME TABELA zdefiniowanego w komentarzach do tej odpowiedzi, DP w stylu plecaka wystarcza, aby ustalić, który gracz ma strategię wygrywającą. Możesz argumentować, że najlepszą strategią Boba jest zawsze reagowanie na przegrany stan przy danym stole gry przy minimalnej możliwej inwestycji (nie może to odciąć kolejnego ruchu dla Boba, który miałby w przeciwnym razie), a stamtąd zamówienie ruchów Alice nie ma znaczenia. Następnie staje się kwestią wyboru podziału kapitału Alicji między gry, tak aby suma minimalnych wygranych odpowiedzi Boba w stosunku do tych gier przekroczyła jego budżet, który można zmienić jako problem typu plecakowego, który ma DP w czasie wielomianowym do jednolitej reprezentacji kosztów. (Moje ponowne wystąpienie faktycznie „

$n$

Nie myślałem dużo o twoim specjalnym przypadku z UPD3 . Podejrzewam, że jest to trudne NP, z tego powodu, że moje zmienne gadżety wydają się na pierwszy rzut oka, jakby można je było dostosować do tych ograniczeń, ale prawdopodobnie nie przyjrzę się temu dalej.

Aktualizacja: prawdopodobnie niepoprawna, na razie pozostawiająca jako dowód na zbadanie alei. Zobacz komentarze.

Aktualizacja 2: zdecydowanie niepoprawna.

$G = (V, E)$$V = \{1, 2, 3\}$$E = \{(1, 2), (2, 3)\}$ , wierzchołki 1, 2, 3 są oznaczone odpowiednio B, A, B, a wszystkim krawędziom przypisane są koszty 1.

$m_A = m_B = 2$$G_1 = G_2 = G_3 = G$ , przy czym wszystkie trzy gry rozpoczynają się od wierzchołka 1. Najwyraźniej Alice nie może wygrać tej gry.

$M[3,2,2]$$2-u, u$$v, 2 - v$$M[2, 2 - u, 2 - v] = B$$W[3, u, v] = B$$u = 1$$u = 2$$M[2, 2 - u, 2] = A$$u = 0$$W[3, u, 2] = A$

$u$$v$

$m_A, m_B, G_1, \dots, G_n,$

Wstępnie obliczone

$W[k, x, y] = \begin{cases}A & \text{if Alice wins GAME on $G_k$ with initial funds $x$ for Alice and $y$ for Bob,} \\ B & \text{otherwise}\end{cases}$

$x \le m_A$$y \le m_B$

$M[k, x, y]$$k$$x \le m_A$$y \le m_B$$M[k, x, y] = B$$A$

$M[1, x, y] = W[1, x, y]$

i

$M[k+1, x, y] = B \quad\text{if and only if}\quad \exists v \forall u, W[k+1, u, v] = B \:\:\text{and}\:\: M[k, x-u, y-v] = B.$

$M[n, m_A, m_B] = A$

$[n]$$n+1$$n\ldots 0$$i+1$$i$$0\leq i\lt n$$0$$0$$n$$[n]$$\geq n$$0$$0$

$G$$\alpha$$\beta$$\alpha$$[i]$$\beta$$\beta$$[j]$$[k]$$j\lt k$$\alpha$$\beta$$\beta$$[j]$$[k]$$[k]$$[i]$$\{i\mid\{j\mid k\}\}$