W problemach praktycznych nierzadko musimy zmierzyć się z niepewnością danych. Jednym z podejść do modelowania tego typu problemów jest przedstawienie ich jako gry dwuosobowej, gdzie jeden gracz stara się rozwiązać problem, a drugi zaburza dane, symulując ich niepewność. W trakcie referatu skupimy się na grze typu min-max "Shortest Path under the Attacks", granej na ważonym grafie pomiędzy dwoma graczami - Ścieżkowcem (Pather), który chce wybrać możliwie najtańszą ścieżkę pomiędzy dwoma ustalonymi wierzchołkami i Atakującym (Attacker), który dysponuje budżetem, który może rozdzielić na krawędzie grafu, zwiększając przy tym wagi niektórych z nich.

Szczegółowo skupimy się na wariancie mieszanym tej gry, gdzie gracze szukają optymalnych rozkładów prawdopodobieństwa na przestrzeni swoich ruchów, aby uzyskać optymalny średni wynik gry. Pokażemy, że w pewnych szczególnych przypadkach tej gry optymalne rozkłady można znaleźć w czasie wielomianowym. Ponadto przedstawimy wyniki probabilistyczne dotyczące struktury optymalnych rozkładów dla Ścieżkowca.

Współautorzy: Armin Fügenschuh, Konstanty Junosza-Szaniawski