Strategie Kwantowe W Teorii Gier

Transcript

Gra w odwracanie monety (PQ penny flip) Podstawy klasycznej teorii gier Strategie kwantowe w Wojnie płci Kwantowy Paradoks więźnia Strategie kwantowe w teorii gier Adam Wyrzykowski Uniwersytet Jagielloński [email protected] 18 stycznia 2015 Adam Wyrzykowski Strategie kwantowe w teorii gier Gra w odwracanie monety (PQ penny flip) Podstawy klasycznej teorii gier Strategie kwantowe w Wojnie płci Kwantowy Paradoks więźnia Plan prezentacji 1 Gra w odwracanie monety (PQ penny flip) 2 Podstawy klasycznej teorii gier Wojna płci Definicje i pojęcia Równowagi Nasha w Wojnie płci 3 Strategie kwantowe w Wojnie płci Kwantowanie Wojny płci Kwantowa Wojna płci pod nieobecność splątania Wpływ splątania na kwantową Wojnę płci 4 Kwantowy Paradoks więźnia Adam Wyrzykowski Strategie kwantowe w teorii gier Gra w odwracanie monety (PQ penny flip) Podstawy klasycznej teorii gier Strategie kwantowe w Wojnie płci Kwantowy Paradoks więźnia Gra w odwracanie monety (PQ penny flip) Zasady gry Gracze Q i P nie znają bieżącej orientacji monety ani ruchów przeciwnika. Początkowo moneta jest ustawiona reszką do góry. Ruch każdego z graczy polega na odwróceniu monety lub pozostawieniu jej stanu bez zmian. Kolejność ruchów jest następująca: pierwszy ruch gracza Q, N F NN -1 1 NF 1 -1 FF -1 1 Tabela : Tabela wypłat gracza P ruch gracza P, kończący rozgrywkę ruch gracza Q. Jeżeli końcowy stan monety to reszka, wygrywa Q, jeżeli orzeł – wygrywa P. Adam Wyrzykowski FN 1 -1 Strategie kwantowe w teorii gier Gra w odwracanie monety (PQ penny flip) Podstawy klasycznej teorii gier Strategie kwantowe w Wojnie płci Kwantowy Paradoks więźnia Kwantowanie gry w odwracanie monety |ψ >= a|R > +b|O > aa∗ + bb ∗ = 1 ! 1 |R >↔ |O >↔ 0 Strategie klasyczne Liniowa kombinacja odwrócenia monety z prawdopodobieństwem p i pozostawienia jej stanu bez zmian z pr-stwem (1 − p): ! UP = p 0 1 1 0 + (1 − p) 1 0 0 1 ! Adam Wyrzykowski ! 0 1 Strategie kwantowe Operacje unitarne: UQ = c d ∗ d −c ∗ gdzie |c|2 + |d|2 = 1. Strategie kwantowe w teorii gier ! , Gra w odwracanie monety (PQ penny flip) Podstawy klasycznej teorii gier Strategie kwantowe w Wojnie płci Kwantowy Paradoks więźnia Przewaga strategii kwantowych ! |ψ1 >= UQ |R >= √1 2 1 1 1 −1 ! 1 0 = √1 2 1 1 ! = ! |ψ2 >= UP |ψ1 >= √1 2 0 1 1 0 p + (1 − p) 1 0 0 1 |ψ3 >= UQ |ψ2 >= √1 √1 2 2 Adam Wyrzykowski 1 1 1 −1 ! 1 1 √1 (|R 2 !! ! = 1 0 1 1 (1) > +|O >) ! ! = √1 2 1 1 (2) ! = |R > Strategie kwantowe w teorii gier (3) Gra w odwracanie monety (PQ penny flip) Podstawy klasycznej teorii gier Strategie kwantowe w Wojnie płci Kwantowy Paradoks więźnia Wojna płci Definicje i pojęcia Równowagi Nasha w Wojnie płci Wojna płci α>β>γ Rysunek : Macierz wypłat (źródło obrazka [2]). Adam Wyrzykowski Strategie kwantowe w teorii gier Gra w odwracanie monety (PQ penny flip) Podstawy klasycznej teorii gier Strategie kwantowe w Wojnie płci Kwantowy Paradoks więźnia Wojna płci Definicje i pojęcia Równowagi Nasha w Wojnie płci Definicje i pojęcia (cz. 1) Statyczna gra o pełnej informacji Każdy z graczy zna dostępne strategie innych i wynikające z nich wypłaty, ale poznają wybrane przez nich strategie dopiero wraz z końcem gry. Należy określić: liczbę graczy i = 1, 2, ..., N; zbiory strategii dla każdego gracza {siα }; funkcje wypłaty $i = $i (s1 , s2 , ..., sN ), które przypisują i−temu graczowi liczbę rzeczywistą (wypłatę) w zależności od strategii wybranych przez wszystkich graczy. W przypadku Wojny płci i = 2, zbiór strategii Alicji (Boba) to {O, T }, zaś funkcje wypłaty $1 (s1 , s2 ) oraz $2 (s1 , s2 ) są określone przez macierz wypłaty, np. $1 (O, O) = $2 (T , T ) = α. Adam Wyrzykowski Strategie kwantowe w teorii gier Gra w odwracanie monety (PQ penny flip) Podstawy klasycznej teorii gier Strategie kwantowe w Wojnie płci Kwantowy Paradoks więźnia Wojna płci Definicje i pojęcia Równowagi Nasha w Wojnie płci Definicje i pojęcia (cz. 2) Mocna dominacja strategii Strategię i−tego gracza si nazywamy ściśle zdominowaną przez strategię s˜i , jeżeli: $i (s1 , ..., si , ..., sN ) < $i (s1 , ..., s˜i , ..., sN ) dla każdego wyboru (s1 , ..., si−1 , si+1 , ..., sN ). Równowaga Nasha Zespół strategii (s1? , s2? , ..., sN? ) stanowi równowagę Nasha, jeżeli dla każdego gracza i zachodzi: ? ? ? ? $i (s1? , ..., si−1 , si? , si+1 , ..., sN? ) ­ $i (s1? , ..., si−1 , si , si+1 , ..., sN? ) dla każdej strategii si dostępnej dla i−tego gracza. Adam Wyrzykowski Strategie kwantowe w teorii gier Gra w odwracanie monety (PQ penny flip) Podstawy klasycznej teorii gier Strategie kwantowe w Wojnie płci Kwantowy Paradoks więźnia Wojna płci Definicje i pojęcia Równowagi Nasha w Wojnie płci Definicje i pojęcia (cz. 3) Strategie mieszane Strategia mieszana dla i−tego gracza to rozkład prawdopodobieństwa, który przypisuje pr-stwo piα każdej czystej strategii siα ze zbioru strategii i−tego gracza. Wówczas $i (s1 , s2 , ..., sN ) jest zastępowane przez funkcję oczekiwanej wypłaty: ¯ $i ({p1 }, {p2 }, ..., {pN }) = αN p1α1 p2α2 ...pN $i (s1α1 , s2α2 , ..., sNαN ) X α1 ,α2 ,...,αN Adam Wyrzykowski Strategie kwantowe w teorii gier Gra w odwracanie monety (PQ penny flip) Podstawy klasycznej teorii gier Strategie kwantowe w Wojnie płci Kwantowy Paradoks więźnia Wojna płci Definicje i pojęcia Równowagi Nasha w Wojnie płci Równowagi Nasha w Wojnie płci p−prawdopodobieństwo, że Alicja wybierze operę, p ∈ [0, 1] q−prawdopodobieństwo, że Bob wybierze operę, q ∈ [0, 1] ¯$A (p, q) = p[q(α − 2γ + β) + γ − β] + β + q(γ − β) (4) ¯$B (p, q) = q[p(α − 2γ + β) + γ − α] + α + p(γ − α) (5) ¯ $A (p ? , q ? ) − ¯$A (p, q ? ) = (p ? − p)[q ? (α + β − 2γ) − β + γ] ­ 0 ¯B (p ? , q ? ) − ¯$B (p ? , q) = (q ? − q)[p ? (α + β − 2γ) − α + γ] ­ 0 $ (6) ( ? ? p(1) = 1, q(1) =1 ? ? p(2) = 0, q(2) =0 ? = p(3) α−γ α+β−2γ ¯$A (1, 1) = α ¯ $A (0, 0) = β ? = q(3) β−γ α+β−2γ ¯$B (1, 1) = β ¯ $B (0, 0) = α ¯ $A = ¯$B = Adam Wyrzykowski Strategie kwantowe w teorii gier αβ−γ 2 α+β−2γ Gra w odwracanie monety (PQ penny flip) Podstawy klasycznej teorii gier Strategie kwantowe w Wojnie płci Kwantowy Paradoks więźnia Kwantowanie Wojny płci Kwantowa Wojna płci pod nieobecność splątania Wpływ splątania na kwantową Wojnę płci Kwantowanie gry (cz. 1) Reguła 1 Przestrzeń strategii Alicji SA (Boba SB ) jest dwuwymiarową przestrzenią Hilberta: |ψ >= a|O > +b|T >, |a|2 + |b|2 = 1 . Na początku gry ustala się dowolny początkowy stan |ψin > z przestrzeni S = SA ⊗ SB = (|OO >, |OT >, |TO >, |TT >). Reguła 2 Ruch Alicji (Boba) polega na wykonaniu operacji unitarnej A ∈ SA (B ∈ SB ) na jej (jego) kubicie stanu |ψin >. Końcowy stan wynosi |ψfin >= A ⊗ B|ψin >. Adam Wyrzykowski Strategie kwantowe w teorii gier Gra w odwracanie monety (PQ penny flip) Podstawy klasycznej teorii gier Strategie kwantowe w Wojnie płci Kwantowy Paradoks więźnia Kwantowanie Wojny płci Kwantowa Wojna płci pod nieobecność splątania Wpływ splątania na kwantową Wojnę płci Kwantowanie gry (cz. 2) Reguła 3 Wartości ¯$A i ¯$B znajduje się obliczając kwadraty modułów rzutów stanu |ψfin > na wektory bazowe |OO >, |OT >, |TO >, |TT >, a następnie dodając uzyskane liczby przemnożone przez odpowiednie współczynniki z macierzy wypłat. Reguła 4 Ostatecznie Alicja musi zagrać klasyczną strategię, która wynika z pomiaru na końcowym stanie kwantowym, tzn. z rzutowania |ψfin > na wektory bazowe SA . Podobnie Bob. Adam Wyrzykowski Strategie kwantowe w teorii gier Gra w odwracanie monety (PQ penny flip) Podstawy klasycznej teorii gier Strategie kwantowe w Wojnie płci Kwantowy Paradoks więźnia Kwantowanie Wojny płci Kwantowa Wojna płci pod nieobecność splątania Wpływ splątania na kwantową Wojnę płci Równowagi Nasha – faktoryzowalne stany |ψin > (cz. 1) Skoro |ψin > jest faktoryzowalny, można przyjąć bez straty ogólności |ψin >= |OO >. W bazie {|O >, |T >} operacje Alicji i Boba mają postać: A= a b ∗ −b a∗ ! B= c d ∗ −d c ∗ ! , gdzie |a|2 + |b|2 = |c|2 + |d|2 = 1. Stan końcowy wynosi zatem: |ψfin >= A ⊗ B|ψin >= = ac|OO > −ad ∗ |OT > −b ∗ c|TO > +b ∗ d ∗ |TT > Adam Wyrzykowski Strategie kwantowe w teorii gier Gra w odwracanie monety (PQ penny flip) Podstawy klasycznej teorii gier Strategie kwantowe w Wojnie płci Kwantowy Paradoks więźnia Kwantowanie Wojny płci Kwantowa Wojna płci pod nieobecność splątania Wpływ splątania na kwantową Wojnę płci Równowagi Nasha – faktoryzowalne stany |ψin > (cz. 2) Zgodnie z Regułą 3 znajdujemy więc: ¯$A = |a|2 [(α + β − 2γ)|c|2 − β + γ] + β + (γ − β)|c|2 ¯$B = |c|2 [(α + β − 2γ)|a|2 − α + γ] + α + (γ − α)|a|2 (7) (8) Wynik ten jest identyczny jak uzyskany w klasycznej teorii gier, jeżeli p = |a|2 oraz q = |c|2 . Równowagi Nasha: ¯$A = β ¯$B = α (|a|2 = 0, |c|2 = 0) |ψfin >= |TT > (|a|2 = 1, |c|2 = 1) |ψfin >= |OO > ¯ $A = α ¯$B = β α−γ β−γ αβ−γ 2 2 ¯ $A = ¯ $B = α+β−2γ α+β−2γ , |c| = α+β−2γ √ √ √ √ ( α−γ|O>− β−γ|T >)⊗( β−γ|O>− α−γ|T >) |ψfin >= α+β−2γ   |a|2 = Adam Wyrzykowski Strategie kwantowe w teorii gier Gra w odwracanie monety (PQ penny flip) Podstawy klasycznej teorii gier Strategie kwantowe w Wojnie płci Kwantowy Paradoks więźnia Kwantowanie Wojny płci Kwantowa Wojna płci pod nieobecność splątania Wpływ splątania na kwantową Wojnę płci Nowe równowagi Nasha – stany splątane |ψin >= a|OO > +b|TT >, |a|2 + |b|2 = 1 A(B) ρfin 1 A(B) † = pI ρin A(B) I +(1−p)C ρin C† ? = q? = 1 p(1) (1) ¯$A (1, 1) = α|a|2 + β|b|2 2 ¯ $B (1, 1) = β|a|2 + α|b|2 ? = q? = 0 p(2) (2) ¯$A (0, 0) = β|a|2 + α|b|2 3 (C |O >= T , C |T >= O) ? = p(3) (α−γ)|a|2 +(β−γ)|b|2 α+β−2γ ¯ $B (0, 0) = α|a|2 + β|b|2 ? = q(3) (α−γ)|b|2 +(β−γ)|a|2 α+β−2γ αβ + (α − β)2 |a|2 |b|2 − γ 2 ? ? ¯$A (p ? , q ? ) = ¯ $ (p , q ) = B (3) (3) (3) (3) α + β − 2γ Adam Wyrzykowski Strategie kwantowe w teorii gier Gra w odwracanie monety (PQ penny flip) Podstawy klasycznej teorii gier Strategie kwantowe w Wojnie płci Kwantowy Paradoks więźnia Kwantowanie Wojny płci Kwantowa Wojna płci pod nieobecność splątania Wpływ splątania na kwantową Wojnę płci Ostateczny kompromis 1. Brak samotnych wieczorów ¯$A (1, 1) + ¯$B (1, 1) = ¯ $A (0, 0) + ¯ $B (0, 0) = α + β 2. Równowagi Nasha 1 i 2 można ”połączyć” ( ¯ $A (1, 1) − ¯$A (0, 0) = (α − β)(|a|2 − |b|2 ) ¯ $B (1, 1) − ¯$B (0, 0) = (α − β)(|b|2 − |a|2 ) kompromis =⇒ |a| = |b| = 3. Najlepsza strategia 1 |ψin >= √ (|OO > +|TT >) = |ψfin > 2 α+β (p ? = 0, q ? = 0) albo (p ? = 1, q ? = 1) ⇒ ¯ $A = ¯$B = 2 Adam Wyrzykowski Strategie kwantowe w teorii gier √1 2 Gra w odwracanie monety (PQ penny flip) Podstawy klasycznej teorii gier Strategie kwantowe w Wojnie płci Kwantowy Paradoks więźnia Paradoks więźnia – klasyczne i kwantowe sformułowanie Alice: C Alice: D Bob: C (3,3) (5,0) Bob: D (0,5) (1,1) |ψf >= J † (UA ⊗ UB )J|CC > U(θ, φ) = U(0, 0) = C =  J = exp 1 0 0 1 e iφ cos θ/2 sin θ/2 −iφ − sin θ/2 e cos θ/2 ! U(π, 0) = D = iγD ⊗ D 2 0 1 −1 0 (9) ! (10) ! U 0, π2 = Q =
i 0 0 −i  γ ∈ [0, π/2] – wsp. splątania Adam Wyrzykowski Strategie kwantowe w teorii gier (11) ! Gra w odwracanie monety (PQ penny flip) Podstawy klasycznej teorii gier Strategie kwantowe w Wojnie płci Kwantowy Paradoks więźnia Paradoks więźnia - gra separowalna (γ = 0) Rysunek : Wypłata Alicji w grze separowalnej. Na wykresie wybrano specjalną parametryzację, w której UA i UB zależą tylko od jednego parametru t ∈ [−1, 1]: przyjmujemy UA = U(tπ, 0) dla t ∈ [0, 1] oraz UA = U(0, −tπ/2) dla t ∈ [−1, 0) (podobnie dla Boba). Zdrada D odpowiada t = 1, współpraca C to t = 0, a strategia Q jest reprezentowana przez t = −1 (źródło obrazka [3]). Adam Wyrzykowski Strategie kwantowe w teorii gier Gra w odwracanie monety (PQ penny flip) Podstawy klasycznej teorii gier Strategie kwantowe w Wojnie płci Kwantowy Paradoks więźnia Paradoks więźnia - maksymalne splątanie (γ = π/2) Rysunek : Wypłata Alicji w grze o maksymalnym splątaniu (źródło obrazka [3]). Adam Wyrzykowski Strategie kwantowe w teorii gier Gra w odwracanie monety (PQ penny flip) Podstawy klasycznej teorii gier Strategie kwantowe w Wojnie płci Kwantowy Paradoks więźnia Podsumowanie Poszerzenie przestrzeni dostępnych strategii o strategie kwantowe może prowadzić do powstawania nowych równowag Nasha i znikania dotychczasowych. Zastosowanie strategii kwantowych może prowadzić do rozwiązań korzystniejszych dla obu graczy, klasycznie niedostępnych. Szczególną rolę w grach kwantowych spełnia splątanie stanu, na krórym operacje mogą wykonywać gracze. Gracz dysponujący strategią kwantową grający przeciwko graczowi korzystającemu wyłącznie ze strategii klasycznych na ogół będzie posiadać przewagę. Adam Wyrzykowski Strategie kwantowe w teorii gier Gra w odwracanie monety (PQ penny flip) Podstawy klasycznej teorii gier Strategie kwantowe w Wojnie płci Kwantowy Paradoks więźnia Literatura [1] David A. Meyer (1999) Quantum strategies Physical Review Letters 82 (5), 1052–1055. [2] L. Marinatto, T. Weber (2000) A quantum approach to static games of complete information Physics Letters A 272, 291–303. [3] J. Eisert, M. Wilkens, M. Lewenstein (1999) Quantum games and quantum strategies Physical Review Letters 83 (15), 3077–3080. [4] http://mindyourdecisions.com/blog/2012/09/11/ quantum-coin-flipping-game-theory/ Adam Wyrzykowski Strategie kwantowe w teorii gier