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

<p>Allocating resources optimally is a nontrivial task, especially when multiple</p><p>self-interested agents with conflicting goals are involved. This dissertation</p><p>uses techniques from game theory to study two classes of such problems:</p><p>allocating resources to catch agents that attempt to evade them, and allocating</p><p>payments to agents in a team in order to stabilize it. Besides discussing what</p><p>allocations are optimal from various game-theoretic perspectives, we also study</p><p>how to efficiently compute them, and if no such algorithms are found, what</p><p>computational hardness results can be proved.</p><p>The first class of problems is inspired by real-world applications such as the</p><p>TOEFL iBT test, course final exams, driver's license tests, and airport security</p><p>patrols. We call them test games and security games. This dissertation first</p><p>studies test games separately, and then proposes a framework of Catcher-Evader</p><p>games (CE games) that generalizes both test games and security games. We show</p><p>that the optimal test strategy can be efficiently computed for scored test</p><p>games, but it is hard to compute for many binary test games. Optimal Stackelberg</p><p>strategies are hard to compute for CE games, but we give an empirically</p><p>efficient algorithm for computing their Nash equilibria. We also prove that the</p><p>Nash equilibria of a CE game are interchangeable.</p><p>The second class of problems involves how to split a reward that is collectively</p><p>obtained by a team. For example, how should a startup distribute its shares, and</p><p>what salary should an enterprise pay to its employees. Several stability-based</p><p>solution concepts in cooperative game theory, such as the core, the least core,</p><p>and the nucleolus, are well suited to this purpose when the goal is to avoid</p><p>coalitions of agents breaking off. We show that some of these solution concepts</p><p>can be justified as the most stable payments under noise. Moreover, by adjusting</p><p>the noise models (to be arguably more realistic), we obtain new solution</p><p>concepts including the partial nucleolus, the multiplicative least core, and the</p><p>multiplicative nucleolus. We then study the computational complexity of those</p><p>solution concepts under the constraint of superadditivity. Our result is based</p><p>on what we call Small-Issues-Large-Team games and it applies to popular</p><p>representation schemes such as MC-nets.</p>

Dissertation