Które gry 2P1R są potencjalnie ostre?

Dwukomorowe gry na jedną rundę (2P1R) są niezbędnym narzędziem do uzyskania stopnia zbliżenia. Konkretnie, równoległe powtarzanie dwóch rundowych gier z dwiema proverami pozwala zwiększyć rozmiar luki w decyzyjnej wersji problemu aproksymacji. Zobacz wywiad ankiety Ran Raz na CCC 2010, aby uzyskać przegląd tego tematu.

Równoległe powtarzanie gry ma zadziwiającą właściwość polegającą na tym, że podczas gdy randomizowany weryfikator działa niezależnie, obaj gracze mogą grać w gry w sposób niezależny, aby osiągnąć lepszy sukces niż rozegrać każdą grę z osobna. Wielkość sukcesu jest ograniczona powyżej twierdzeniem Raz o równoległych powtórzeniach:

Twierdzenie : Istnieje uniwersalna stała $c$ więc dla każdej gry 2P1R $G$ o wartości $1-\epsilon$ i rozmiarze odpowiedzi $s$ wartość równoległej gry $G^n$ wynosi co najwyżej $(1-\epsilon^c)^{\Omega(n/s)}$ .

Oto zarys pracy nad identyfikacją tej stałej $c$ :

• Oryginalny papier Raza wykazuje $c \leq 32$ .
• Holenstein poprawił to do $c \leq 3$ .
• Rao wykazał, że $c' \leq 2$ wystarcza (i usunięto zależność od $s$ ) dla specjalnego przypadku gier projekcyjnych.
• Raz podał strategię gry w nieparzystym cyklu, która pokazała, że ​​wynik Rao jest ostry w grach projekcyjnych.

Z tego zakresu pracy wiemy, że $2 \leq c\leq 3$ . Moje dwa pytania są następujące:

Pytanie 1: Czy eksperci w tej dziedzinie są zgodni co do dokładnej wartości $c$ ?

Jeśli uważa się, że $c > 2$ , istnieją określone gry, które nie są projekcyjne, ale również w szczególny sposób naruszają dodatkowe właściwości gier projekcyjnych, których wymaga dowód Rao.

Pytanie 2: Jeśli , które ciekawe gry naruszają strategię Rao i mogą stanowić ostry przykład?$c > 2$

Z mojego własnego czytania wynika, że ​​najważniejszą właściwością gier projekcyjnych, z których korzysta Rao, jest to, że dobra strategia równoległego powtarzania nie wykorzystałaby wielu możliwych odpowiedzi na niektóre pytania. Jest to w jakiś sposób związane z lokalizacją gier projekcyjnych.

Uważam, że c = 3 jest właściwą odpowiedzią na ogólny przypadek i że powinno być możliwe podanie przykładu. Będę musiał się nad tym zastanowić, aby się upewnić. To dobre pytanie i nie znam istniejących prac na ten temat.

Badania skupiły się ostatnio na tym, które typy gier mają (najlepiej możliwe) c = 1, głównie ze względu na możliwe zastosowania do wzmocnienia unikalnych gier.

• Barak i wsp. Uogólnili kontrprzykład Raz na wszystkie unikalne gry z lukami SDP.
• Raz i Rosen wykazali, że dla rozszerzania gier projekcyjnych c = 1. Istnieją również poprzednie wyniki supersetu autorów bezpłatnych gier.

Aby przyspieszyć, mam potencjalną grę i chciałbym uzyskać informacje zwrotne.

$k \geq 2$$m$$3k+1$C k m k + 1 C k m m m k k + $m \not\equiv 0 {\pmod {k+1}}$$C_{m}^k$$k+1$$C_m^k$$m$$m$$k$$k+1$ { 1 , … , k } { 0 , … , m - 1 } k + 1 { 0 , … , m - 1 } m k + $C_m^{k}$$\{1,\dots,k\}$i kolorowanie liczb w tej kolejności, ponieważ każdy zestaw kolejnych liczb całkowitych w tworzy klikę. Ponieważ nie jest wielokrotnością , w pewnym momencie zabarwienie to się nie powiedzie.$\{0,\dots,m-1\}$$k+1$$\{0,\dots,m-1\}$$m$$k+1$

Weryfikator albo prosi o jeden wierzchołek od obu graczy, aby sprawdzić, czy kolory pasują, lub prosi o krawędź, aby sprawdzić, czy kolory są różne.

Uważam, że to dobry przykład z dwóch powodów:

1. Jest wystarczająco podobny do gry w nieparzystym cyklu, że można zbudować strategię podobną do dolnej granicy Raz. Ważną częścią tej strategii jest losowy wybór kolorów w powtórzeniach przy użyciu wspólnej losowości.

2. Przez losowe permutacje stosowane w losowo generowanych kolorach liczba odpowiedzi podanych w każdym wierzchołku obejmuje cały zestaw odpowiedzi w jednolity sposób, atakując strategię Rao.

Czy ta gra została już rozpatrzona / rozwiązana?