| 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. |
