| Summary: | <p>This thesis focuses on two aspects of Stackelberg games — decentralized leadership and follower
deception — that stem from reasoning about strategic interactions at a higher level in Stackelberg
games.</p>
<p>In the first part of the thesis, we study decentralized leadership in Stackelberg games. We focus
on a variant of Stackelberg security games that involves multiple leaders, in which the leaders
allocate their security resources to protect a set of targets against an attacker; the attacker acts as
the follower in the game, surveying the leaders’ strategies and responding rationally afterwards.
We aim to understand the game under decentralized leadership and explore ways to coordinate
the leaders. To this end, firstly, we propose a novel equilibrium concept to describe the outcome
of the game, and we analyze the existence of an equilibrium and the complexity of computing
it. Then, we take a mechanism design approach to coordinate the leaders, aiming to design a
coordination mechanism that satisfies several natural properties concerning efficiency, incentives,
strategyproofness, and stability of strategies it generates. We obtain impossibility results showing
that certain combinations of these properties cannot be achieved by any mechanism. On top of that
we also present mechanisms for property combinations that are not blocked by the impossibility
results.</p>
<p>The second part of the thesis is motivated by the finding that, in a Stackelberg game, the follower
can benefit from changing the leader’s belief about the game. This can typically happen when the
follower is able to tamper with the leader’s attempt of information gathering: for instance, when
the leader learns the follower’s type by interacting with the follower, the follower can imitate the
behavior of a different follower type, pretending that their payoffs are different than the actual ones.
A leader who ignores such strategic manipulation will then be misled into playing optimally against
the imitated follower type, which may correspond to a highly suboptimal strategy in the original
game. We study the strategic interactions resulting from this deceptive behavior, both from the
leader’s and the follower’s perspectives. From the leader’s perspective, we propose a policy-based
approach to mitigate potential losses due to follower deception and study the associated problem of
computing the optimal policy. From the follower’s perspective, we study the problem of computing
the optimal strategy to deceive the leader. Our results provide an almost complete picture of the
complexity landscape of these problems in various settings. It is shown that the problems facing the
leader are hard in general, whereby we derive inapproximability bounds and also design algorithms
that achieve matching approximation ratios; whereas the problems facing the follower are tractable,
whereby we design polynomial-time algorithms to compute optimal (or near-optimal) deception
strategies for the follower.</p>
<p>Our work sheds light on strategic interactions that may arise in Stackelberg games but are not
captured by existing solution concepts. It provides frameworks to study these interactions and
contributes to the understanding of them through the lens of computation.</p>
|
|---|