|MARCHESI ALBERTO||Cycle: XXXII |
Section: Computer Science and Engineering
Tutor: ALIPPI CESARE Major Research topic
Advisor: GATTI NICOLAAbstract:
In recent years, leader-follower games have received a growing interest from the Artificial Intelligence community. These games model strategic interactions involving two groups of rational agents, the leaders and the followers, where the former commit to playing some strategies, and the latter, after observing the commitment, decide how to play. This model perfectly fits many real-world scenarios. For instance, in the security domain, a defender, acting as leader, has to allocate scarce resources to protect some valuable targets from an attacker, who plays as follower, since she can observe the leader’s defensive strategy. We study the, yet unexplored, leader-follower games, with single leader and multiple followers, where the latter are assumed to play simultaneously and noncooperatively, thus reaching a Nash equilibrium of the normal-form game resulting from the leader’s commitment. We prove that the problem is hard, and provide algorithms to solve it, both exactly and approximately. Then, we restrict out attention to a particular class of games, called congestion games, which are always guaranteed to admit a pure-strategy Nash equilibrium, and, thus, allow for an easier solution to the problem.