Information as a Double-Edged Sword in Strategic Interactions

Abstract:

This thesis considers the following question: in systems with self-interested agents (a.k.a.,
games), how does information — i.e., what each agent knows about their environment and other
agents’ preferences — affect their decision making? The study of the role of information in
games has a rich history, and in fact forms the celebrated field of information economics. However, different from previous descriptive study, this thesis takes a prescriptive approach and examines computational questions pertaining to the role of information. In particular, it illustrates
the double-edged role of information through two threads of research: (1) how to utilize information to one’s own advantage in strategic interactions; (2) how to mitigate losses resulting from
information leakage to an adversary. In each part, we study the algorithmic foundation of basic
models and also develop efficient solutions to real-world problems arising from physical security
domains. Besides pushing the research frontier, the work of this thesis is also directly impacting
several real-world applications, resulting in delivered software for improving the scheduling of
US federal air marshals and the design of patrolling routes for wildlife conservation.
More concretely, the first part of this thesis studies an intrinsic phenomenon in human endeavors termed persuasion — i.e., the act of exploiting an informational advantage in order to
influence the decisions of others. We start with two real-world motivating examples, illustrating
how security agencies can utilize an informational advantage to influence adversaries’ decisions
and deter potential attacks. Afterwards, we provide a systematic algorithmic study for the foundational economic models underlying these examples. Our analysis not only fully resolves the
complexity of these models, but also leads to new economic insights. We then leverage the insights and algorithmic ideas from our theoretical analysis to develop new models and solutions
for concrete real-world security problems.
The second part of this thesis studies the other side of the double-edged sword, namely, how
to deal with disadvantages due to information leakage. We also start with real-world motivating
examples to illustrate how classified information about security measures may leak to the adversary and cause significant loss to security agencies. We then propose different models to capture
information leakage based on how much the security agency is aware of the leakage situation,
and provide thorough algorithmic analysis for these models. Finally, we return to the real-world
problems and design computationally efficient algorithms tailored to each security domain.