Volltext-Downloads (blau) und Frontdoor-Views (grau)

Foundations of multi-agent systems

  • Abstract: The subject of multi-agent systems is relevant to both economic theory and artificial intelligence. Yet, very little work so far has tried to bridge the gap between the different formalisms, and provide a unified treatment. In this thesis, we approach the subject of multi-agent systems from first principles, and develop a new approach which enjoys foundational as well as computational advantages with respect to other existing treatments. First we develop a revealed-preference decision theory for many agents. Our theory has several advantageous features, including the ability to represent small worlds, conditional and counterfactual preferences and beliefs, and higher-order utilities and probabilities. Next, we introduce a novel representation for single-agent decision problems, Expected Utility Networks (EU nets). EU nets generalize probabilistic networks from the AI literature, and provide a modular and compact framework for strategic inference. The representation relies on a novel notion of utility independence, closely related to its probabilistic counterpart, which we present and discuss in the context of other existing notions. Together, probability and utility independence are shown to imply expected utility (EU) independence. Finally, we argue that expected utility independence can be used to decentralize complex single-agent decision problems, in that conditionally EU independent sub-tasks can be allocated to simpler, conditionally independent sub-agents. We then extend the EU nets formalism to multi-agent decision problems, and introduce a new class of representations, Game Networks (G nets). G nets constitute an alternative to existing game-theoretic representation, with distinctive advantages. In particular, G nets are more structured and compact than extensive forms, as both probabilities and utilities enjoy a modular representation. Next, we discuss strategic equilibrium in game networks. Existence and coergence results are presented, for the special case of simultaneous networks. Although we do not explicitly consider the general case, the proof technique and the main results should carry over to general G nets. As a concrete application of G nets, we then show how G nets can be used to formally represent a second-price auction and solve for the equilibrium. We also show how G nets can be used to reduce the computational complexity of finding an optimal allocation and the corresponding payments in Generalized Vickrey Auctions. In general, the problem is NP-hard; yet, we show that for an important class of problems the solution can be obtained in linear time. Our notion of utility independence can be given an alternative justification, based on the notion of maximum entropy. We present a novel entropy method, which allows for the characterization of “typical” preference structures in the face of observed constraints (revealed preferences). We discuss potential applications of the method, and provide an axiomatic justification.

Export metadata

Additional Services

Search Google Scholar


Document Type:Other
Author:Pierfrancesco La MuraORCiD
Chairs and Professorships:Chair of Economics and Information Systems
Year of Completion:1999
Ph.D. dissertation, Graduate School of Business, Stanford University, 1999