Antonín Kučera, Professor of Computer Science from Faculty of Informatics, Masaryk University, Brno, Czech Republic will give talk on Thursday 2 July 2026 at 11:00 on "Algorithmic Strategy Synthesis for Long-Run Average Objectives in Multi-Agent Systems".
Abstract: Optimizing long-run average objectives such as mean-payoff, multiple mean-payoff, limit state/action frequencies, etc. in Markov decision processes are classical problems deeply studied in stochastic programming. The scenario assume one player (agent) responsible for resolving the non-deterministic choice. In the talk, we consider a more general setup where several agents operating on the same MDP strive to jointly achieve a given long-run average objective. We demonstrate that the complexity issues are quite different from the single agent case and present scalable algorithmic solutions. We also discuss issues specific to the multi-agent setting (resilience to agent failures, controlling physical proximity of the agents, etc.) and propose relevant measures that can be incorporated into objective functions. As a practical application, we present a tool for the design/execution/adaptation of patrolling strategies developed jointly with the Czech Army. The talk is based on the results published at AAAI 2025, IJCAI 2025, and AAAI 2024 conferences.
Meeting ID: 930 4496 2846
Passcode: 540432
Funded by the European Union under Grant Agreement No. 101087529.
