Game-Theoretically Allocating Resources to Catch Evaders and Payments to Stabilize Teams

Allocating resources optimally is a nontrivial task, especially when multiple

self-interested agents with conflicting goals are involved. This dissertation

uses techniques from game theory to study two classes of such problems:

allocating resources to catch agents that attempt to evade them, and allocating

payments to agents in a team in order to stabilize it. Besides discussing what

allocations are optimal from various game-theoretic perspectives, we also study

how to efficiently compute them, and if no such algorithms are found, what

computational hardness results can be proved.

The first class of problems is inspired by real-world applications such as the

TOEFL iBT test, course final exams, driver's license tests, and airport security

patrols. We call them test games and security games. This dissertation first

studies test games separately, and then proposes a framework of Catcher-Evader

games (CE games) that generalizes both test games and security games. We show

that the optimal test strategy can be efficiently computed for scored test

games, but it is hard to compute for many binary test games. Optimal Stackelberg

strategies are hard to compute for CE games, but we give an empirically

efficient algorithm for computing their Nash equilibria. We also prove that the

Nash equilibria of a CE game are interchangeable.

The second class of problems involves how to split a reward that is collectively

obtained by a team. For example, how should a startup distribute its shares, and

what salary should an enterprise pay to its employees. Several stability-based

solution concepts in cooperative game theory, such as the core, the least core,

and the nucleolus, are well suited to this purpose when the goal is to avoid

coalitions of agents breaking off. We show that some of these solution concepts

can be justified as the most stable payments under noise. Moreover, by adjusting

the noise models (to be arguably more realistic), we obtain new solution

concepts including the partial nucleolus, the multiplicative least core, and the

multiplicative nucleolus. We then study the computational complexity of those

solution concepts under the constraint of superadditivity. Our result is based

on what we call Small-Issues-Large-Team games and it applies to popular

representation schemes such as MC-nets.

King Democracy: Do Democratic Nations Mitigate Conflict Over Transboundary Freshwater Resources Better Than Other Nations?

The prospect of water wars and conflict over water are ideas that are frequently dramatized in media and also studied by scholars. It is well-established that bona fide wars are not started over water resources, but conflict over water does exist and is not well understood. One would suppose, as scholars often do, that dyads composed of two democratic nations would be the best at mitigating conflict and promoting cooperation over freshwater resources. General conflict research supports that supposition, as does the argument that democracies must be best at avoiding conflicts over resources because they excel at distributing public goods. This study provides empirical evidence showing how interstate dyads composed of various governance types conflict and cooperate over general water and water quantity issues relative to each other. After evaluating the water conflict mitigating ability of democratic-democratic, democratic-autocratic, and autocratic-autocratic dyads, this study found that democracy-autocracy dyads are less likely to cooperate over general water issues and water quantity issues than the other two dyad types. Nothing certain can be said about how the three dyad types compare to each other in terms of likelihood to conflict over water quantity issues. However, two-autocracy dyads seem to be most likely to cooperate over water quantity issues. These findings support the established belief that democratic-autocratic pairs struggle to cooperate while also encouraging greater scrutiny of the belief that democracies must be best at cooperating over water resources.