Gry Warehouse Games (WHG) są inspirowane praktycznym scenariuszem ochrony magazynów. Rozgrywka toczona jest na nieskierowanym grafie \( G=(V,E) \), który reprezentuje korytarze i pomieszczenia budynku.

Zarówno Atakujący \((A)\), jak i Obrońca \((O)\) rozpoczynają grę w określonych wierzchołkach. W każdym z \(m\) kroków czasowych gracze mogą przemieścić się do dowolnego sąsiedniego wierzchołka lub pozostać w obecnym. Strategia prosta gracza \( g \in \{O,A\} \) jest więc zdefiniowana jako lista wierzchołków odwiedzanych w kolejnych krokach czasowych:

$$ \sigma^g = (v_1^g, v_2^g, ..., v_m^g) $$

W grafie wyróżniony jest podzbiór wierzchołków \( T \subseteq V \), które stanowią cele. Gra kończy się w momencie spełnienia jednego z poniższych warunków:

• Przechwycenie: Gracze znajdą się jednocześnie w tym samym wierzchołku. Matematycznie warunek ten wyraża się jako: $$ \exists_{i \in \{1,...,m\}} v_i^A = v_i^O $$ W takim przypadku Obrońca otrzymuje nagrodę \( U_{v_i}^{O+} > 0 \), a Atakujący karę \( U_{v_i}^{A-} < 0 \).
• Udany atak: Atakujący dotrze do celu \( v_i \in T \) i nie zostanie wcześniej złapany. Warunek ten zapisujemy jako: $$ \exists_{i \in \{1,...,m\}} v_i^A \in T \wedge \forall_{j < i} v_j^A \neq v_j^O $$ Wówczas Atakujący otrzymuje nagrodę \( U_{v_i}^{A+}> 0 \), a Obrońca karę \( U_{v_i}^{O-} < 0 \).
• Upływ czasu: Jeśli przez \( m \) kroków czasowych nie dojdzie ani do przechwycenia, ani do ataku na cel, gra kończy się wypłatą 0 dla obu graczy.

Gry Search Games (SEG) są rozwinięciem koncepcji gier na grafach. W odróżnieniu od Warehouse Games, rozgrywka toczy się na grafie skierowanym, a Obrońca dysponuje \( k \) jednostkami zasobów. Istotnym ograniczeniem jest to, że zasoby te nie mogą poruszać się po grafie dowolnie – każdy z nich ma przydzielony określony podzbiór wierzchołków, które może odwiedzać.

Częściowa obserwowalność i ślady

Kluczową cechą gier SEG jest częściowa obserwowalność obecności Atakującego. Atakujący, odwiedzając wierzchołek, pozostawia w nim "ślad". Ślad ten może zostać wykryty przez Obrońcę w dowolnym późniejszym kroku czasowym, jeśli jego zasób odwiedzi ten wierzchołek. Atakujący posiada jednak możliwość zatarcia śladów poprzez pozostanie w danym wierzchołku przez więcej niż jeden krok czasowy.

Strategia Obrońcy

Ze względu na mechanizm śladów, strategia Obrońcy jest bardziej złożona i musi definiować zachowanie zarówno w przypadku braku wykrycia śladów, jak i reakcję na ich znalezienie. Formalnie strategia prosta Obrońcy definiowana jest wzorem:

$$ D = \{\mathcal{L}_{vs}^u, u \in D_u, v \in \overline{V}, s \in \{1,...,m\}\} \cup \{\mathcal{L}_{\emptyset}^u, u \in D_u\} $$

Gdzie:

• \( \mathcal{L}_{\emptyset}^u \) – to domyślna lista wierzchołków odwiedzanych przez zasób \( u \) w przypadku braku wykrycia śladu.
• \( \mathcal{L}_{vs}^u \) – to lista wierzchołków odwiedzanych przez zasób \( u \) od momentu wykrycia śladu w wierzchołku \( v \) w kroku czasowym \( s \).

Obrońca realizuje strategię domyślną do momentu wykrycia pierwszego śladu, po czym przełącza się na odpowiednią strategię reakcji.

Warunki zakończenia gry

Zasady przyznawania wypłat i kończenia gry są analogiczne do gier Warehouse Games:

• Złapanie: Obrońca i Atakujący znajdują się w tym samym wierzchołku w tym samym czasie.
• Sukces ataku: Atakujący dociera do celu (niezauważony w tym samym kroku przez Obrońcę).
• Koniec czasu: Żadne z powyższych zdarzeń nie ma miejsca w limicie \( m \) kroków.

Gry FlipIt Games (FIG) powstały z inspiracji scenariuszami cyberbezpieczeństwa. Modelują one sytuację, w której Atakujący próbuje przejąć kontrolę nad elementami infrastruktury sieciowej (np. ruterami, serwerami), a Obrońca podejmuje działania mające na celu odzyskanie nad nimi panowania.

Przebieg rozgrywki

Gra toczy się na grafie skierowanym przez określoną liczbę kroków czasowych \( m \). W każdym kroku gracze wykonują akcję polegającą na wyborze jednego wierzchołka, nad którym próbują przejąć kontrolę (tzw. flip). Na początku gry wszystkie wierzchołki są kontrolowane przez Obrońcę, a Atakujący ma dostęp tylko do wybranych "wierzchołków wejściowych".

Zasady przejmowania kontroli

Mechanika przejmowania zasobów jest kluczowa dla tego typu gier:

• Operacja przejęcia kończy się sukcesem tylko wtedy, gdy gracz kontroluje już co najmniej jeden wierzchołek poprzedzający (z którego prowadzi krawędź do celu) lub atakowany jest wierzchołek wejściowy.
• Jeśli obaj gracze próbują przejąć ten sam wierzchołek w tym samym czasie, jego stan się nie zmienia (pozostaje pod kontrolą dotychczasowego właściciela).

Model wypłat

W przeciwieństwie do innych gier, tutaj wypłata jest liczona kumulatywnie. Każdemu wierzchołkowi \( v \) przypisana jest nagroda za posiadanie kontroli \( U_{v}^{+} > 0 \) oraz koszt wykonania akcji przejęcia \( U_{v}^{-} < 0 \). Całkowitą wypłatę gracza \( g \) wyraża wzór:

$$ U_{g} = \sum_{s \in \{1,...,m\}} \sum_{v \in R_{s}(g)} U_{v}^{+} + \sum_{s \in \{1,...,m\}} U_{v_{s}^{g}}^{-} $$

Gdzie:

• \( R_{s}(g) \) – zbiór wierzchołków kontrolowanych przez gracza \( g \) po kroku \( s \).
• \( v_{s}^{g} \) – wierzchołek, na którym gracz \( g \) wykonuje akcję w kroku \( s \).

Brak informacji (No-Info)

Istotnym aspektem gry jest brak pełnej wiedzy o stanie rozgrywki. Gracze nie wiedzą w trakcie gry, które wierzchołki faktycznie kontrolują. Swoją strategię (sekwencję ruchów na całą grę) muszą zaplanować na samym początku i nie mogą jej zmieniać w trakcie trwania rozgrywki.

Gry z sygnalizacją (ang. Security Games with Signaling) należą do rodziny gier Green Security Games i są inspirowane problemami ochrony środowiska naturalnego, takimi jak walka z kłusownictwem w parkach narodowych.

Zróżnicowane zasoby

Cechą wyróżniającą SGS jest podział zasobów Obrońcy na dwie kategorie o odmiennych funkcjach:

• Drony (\( k_d \)): Służą do monitorowania i wykrywania zagrożeń. Mogą wysyłać sygnały, ale nie mogą samodzielnie schwytać Atakującego.
• Strażnicy (\( k_s \)): Mogą przemieszczać się i dokonywać interwencji (schwytać Atakującego).

Przebieg rozgrywki i sygnalizacja

Gra składa się z kilku etapów. Po wyborze strategii przez obu graczy i ataku na wybrany cel, jeśli w wierzchołku znajduje się dron, może on wysłać jeden z dwóch sygnałów:

• Sygnał słaby (\( s_0 \)): Cicha informacja wysłana do strażników o wykrytym zagrożeniu (bez alarmowania Atakującego).
• Sygnał silny (\( s_1 \)): Uruchomienie sygnałów świetlnych i dźwiękowych w celu odstraszenia Atakującego (oprócz powiadomienia strażników).

Po otrzymaniu sygnału następuje faza realokacji, w której strażnicy z sąsiednich wierzchołków mogą przemieścić się do atakowanego celu, aby udaremnić atak.

Niepewność

Model SGS wprowadza dwa kluczowe rodzaje niepewności, które komplikują proces decyzyjny:

1. Niepewność wykrycia (\( \gamma \)): Systemy automatycznej detekcji w dronach są zawodne. Istnieje prawdopodobieństwo \( \gamma \), że dron obecny w atakowanym wierzchołku nie wykryje zagrożenia.
2. Niepewność obserwacji (\( \Omega \)): Atakujący może błędnie zinterpretować sytuację. Macierz \( \Omega \) określa prawdopodobieństwa warunkowe, z jakimi Atakujący zaobserwuje dany sygnał (lub jego brak), w zależności od tego, co faktycznie wysłał dron.

Strategie

Strategia Obrońcy jest w tym modelu złożona. Obejmuje nie tylko alokację dronów i strażników, ale także plan realokacji (reakcji na zgłoszenia) oraz plan sygnalizacji – czyli prawdopodobieństwa wysłania sygnałów \( s_0 \) lub \( s_1 \) w zależności od tego, czy dron wykrył atak, czy nie.