Description
Date depot: 30 mars 2024
Titre: Search Games with Untrusted Advice
Directeur de thèse:
Spyros ANGELOPOULOS (LIP6)
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Algorithmique, combinatoire
Resumé: Searching for a hidden target is an important computational problem, with a long standing history of research in Operations Research, Theoretical Computer Science, and AI. Motivated by recent advances in learning-augmented algorithms, in this project we focus on settings in which the searcher has some inherently imperfect advice (or prediction) concerning the placement of the hider in the search environment. We seek to bridge the large gap between the field of Search Games, that applies a game-theoretic approach with emphasis on randomized strategies and exact equilibria over a single criterion, and Algorithms with Predictions, where the analysis has focused mostly on multi-criteria analysis, deterministic algorithms and approximative performance guarantees. Specifically, we propose directions that involve consistency/robustness analysis in search games, randomized strategies for query-based predictions, as well as sampling-based techniques for enhancing the efficiency search and exploration.