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.

The Life Cycle of Corporate Venture Capital

This paper establishes the life-cycle dynamics of Corporate Venture Capital (CVC) to explore the information acquisition role of CVC investment in the process of corporate innovation. I exploit an identification strategy that allows me to isolate exogenous shocks to a firm's ability to innovate. Using this strategy, I first find that the CVC life cycle typically begins following a period of deteriorated corporate innovation and increasingly valuable external information, lending support to the hypothesis that firms conduct CVC investment to acquire information and innovation knowledge from startups. Building on this analysis, I show that CVCs acquire information by investing in companies with similar technological focus but have a different knowledge base. Following CVC investment, parent firms internalize the newly acquired knowledge into internal R&D and external acquisition decisions. Human capital renewal, such as hiring inventors who can integrate new innovation knowledge, is integral in this step. The CVC life cycle lasts about four years, terminating as innovation in the parent firm rebounds. These findings shed new light on discussions about firm boundaries, managing innovation, and corporate information choices.