Market structure and multidimensional auction design for computational economies.

Abstract

Research in multiagent systems and electronic commerce applications often involves the task of designing a mechanism to allocate scarce resources among self-interested agents. Microeconomics has developed an extensive theory on the use of markets and auctions to solve such resource allocation problems. However, in many of the problems that arise in computer science applications, resources are discrete and the agents often realize positive synergies, or complementarities, between resource types. These problem features pose particular challenges to mechanism designers. This thesis supports the application of microeconomic theory to multiagent systems and electronic commerce problems in three ways. First, it defines a structural view of markets that allows clustering of resources into multidimensional auctions. This structural view facilitates the exploration of tradeoffs between communication, computation, and convergence properties when only a subset of resources exhibit complementarities. Second, this thesis provides a parametrized view of the space of auction designs. This parametrization adds considerable structure to the design problem, and provides a concise and consistent language with which to communicate the rules to participating agents. Finally, this thesis extends the state of the art in multidimensional auctions for both discrete and continuous resources. Perhaps most significantly, this dissertation introduces the Ascending <italic>k</italic>-Bundle Auctions, a family of single-sided auctions for discrete resources that associate payments with bundles. These auctions have a desirable equilibrium property---no agent prefers some other bundle at the posted payments to the one it is allocated by the mechanism.