Resource allocation in competitive multiagent systems

In systems involving multiple autonomous agents, it is often necessary to decide how scarce resources should be allocated. When agents have competing interests, they may have incentive to deviate from protocols or to lie to other agents about their preferences. Due to the strategic nature of such interactions, there has been a recent surge of interest in addressing problems in competitive multiagent systems by bringing together techniques from computer science and game-theoretic economics. In some cases, the interesting issue is the application of ideas from computer science to make existing economic mechanisms practical. In other cases, selfish agents' conflicting demands of a computer system can best be understood and/or managed through game-theoretic analysis. This thesis addresses problems that fall into both cases.; The first part of this work considers game-theoretic issues in multiagent resource allocation: (1) using incentives to diffuse temporally-focused usage of a resource on a computer network at the lowest possible cost; (2) identifying a protocol to allow agents to cooperate in (single-good) first-price auctions, and showing that in equilibrium such collusion benefits both colluding and non-colluding agents at the auctioneer's expense; (3) compactly representing strategic multiagent situations as local-effect games, a novel class of multi-player general-sum games for which pure-strategy Nash equilibria can often be proven to exist and be computed efficiently.; The second part considers computational issues in multiagent resource allocation, concentrating on the winner determination problem (WDP) in combinatorial auctions: (1) solving several variants of the WDP using heuristic branch-and-bound search algorithms; (2) building a benchmark suite for WDP algorithms by modeling real-world valuations described in the economics literature; (3) modeling the (empirical) computational hardness of the WDP, analyzing these models, and applying them to construct algorithm portfolios and to generate harder problem instances.