Contributions to game-theoretic aspects of multi-agent systems

In many multi-agent domains, the assumption of cooperative agents is invalid, and agents are better modeled as being self-interested. Game theory provides a formal means for reasoning about the incentives facing self-interested agents. As a result, much of the recent work in multi-agent systems lies at the intersection of computer science and game theory. However, the space is large and remains mostly unexplored. In this thesis, we contribute to the understanding of this space by exploring several new points within it.; Mechanism design, the science of crafting protocols for self-interested agents, provides the game-theoretic component of the majority of this work. Indeed, the first five contributions lie at the intersection of computer science and mechanism design: (1) A solution to a mechanism-design problem in an online scheduling domain that simultaneously addresses both computer science and game-theoretic aspects of the problem. (2) Tight upper and lower bounds on the level of fairness that a mechanism can achieve in a novel task allocation setting. (3) Possibility and impossibility results for several variants of a mechanism-design problem in a task allocation setting in which agents may fail to complete their assigned tasks. (4) For a cryptographic setting, a characterization of the Boolean functions that self-interested agents can jointly compute. (5) Four different mechanisms for smoothing out focused demand for network resources.; The well-studied topics of auctions and Nash equilibria provide the game-theoretic components of the final two contributions of this thesis: (6) An analysis of two forms of cheating in sealed-bid auctions, which provides insights into sealed-bid auctions even in the absence of cheating. (7) Artificial Intelligence techniques that perform well in practice on the game-theoretic problem of finding a sample Nash equilibrium in a normal form game.