Representing aggregate belief through the competitive equilibrium of a securities market
We consider the problem of belief aggregation: given a group of individual agents with probabilistic beliefs over a set of uncertain events, formulate a sensible consensus or aggregate probability distribution over these events. Researchers have proposed many aggregation methods, although on the question of which is best the general consensus is that there is no consensus. We develop a market-based approach to this problem, where agents bet on uncertain events by buying or selling securities contingent on their outcomes. Each agent acts in the market so as to maximize expected utility at given securities prices, limited in its activity only by its own risk aversion. The equilibrium prices of goods in this market represent aggregate beliefs. For agents with constant risk aversion, we demonstrate that the aggregate probability exhibits several desirable properties, and is related to independently motivated techniques. We argue that the market-based approach provides a plausible mechanism for belief aggregation in multiagent systems, as it directly addresses self-motivated agent incentives for participation and for truthfulness, and can provide a decision-theoretic foundation for the �expert weights� often employed in centralized pooling techniques.
Generalized Queries on Probabilistic Context-Free Grammars
Probabilistic context-free grammars (PCFGs) provide a simple way to represent a particular class of distributions over sentences in a context-free language. Efficient parsing algorithms for answering particular queries about a PCFG (i.e., calculating the probability of a given sentence, or finding the most likely parse) have been developed and applied to a variety of pattern-recognition problems. We extend the class of queries that can be answered in several ways: (1) allowing missing tokens in a sentence or sentence fragment, (2) supporting queries about intermediate structure, such as the presence of particular nonterminals, and (3) flexible conditioning on a variety of types of evidence. Our method works by constructing a Bayesian network to represent the distribution of parse trees induced by a given PCFG. The network structure mirrors that of the chart in a standard parser, and is generated using a similar dynamic programming approach. We present an algorithm for constructing Bayesian networks from PCFGs, and show how queries or patterns of queries on the network correspond to interesting queries on PCFGs. The network formalism also supports extensions to encode various context sensitivities within the probabilistic dependency structure.
Conjectural equilibrium in multiagent learning
Learning in a multiagent environment is complicated by the fact that as other agents learn, the environment effectively changes. Moreover, other agents‘ actions are often not directly observable, and the actions taken by the learning agent can strongly bias which range of behaviors are encountered. We define the concept of a conjectural equilibrium, where all agents‘ expectations are realized, and each agent responds optimally to its expectations. We present a generic multiagent exchange situation, in which competitive behavior constitutes a conjectural equilibrium. We then introduce an agent that executes a more sophisticated strategic learning strategy, building a model of the response of other agents. We find that the system reliably converges to a conjectural equilibrium, but that the final result achieved is highly sensitive to initial belief. In essence, the strategic learner‘s actions tend to fulfill its expectations. Depending on the starting point, the agent may be better or worse off than had it not attempted to learn a model of the other agents at all.
Flexible double auctions for electronic commerce: Theory and implementation
We consider a general family of auction mechanisms that admit multiple buyers and sellers, and determine market-clearing prices. We analyze the economic incentives facing participants in such auctions, demonstrating that, under some conditions, it is possible to induce truthful revelation of values by buyers or sellers, but not both, and for single- but not multi-unit bids. We also perform a computational analysis of the auctioneer's task, exhibiting efficient algorithms for processing bids and calculating allocations.
The Michigan Internet AuctionBot: A configurable auction server for human and software agents
Market mechanisms, such as auctions, will likely represent a common interaction medium for agents on the Internet. The Michigan Internet AuctionBot is a flexible, scalable, and robust auction server that supports both software and human agents. The server manages many simultaneous auctions by separating the interface from the core auction procedures. This design provides a responsive interface and tolerates system and network disruptions, but necessitates careful timekeeping procedures to ensure temporal accuracy. The AuctionBot has been used extensively in classroom exercises, and is available to the general Internet population. Its flexible specification of auctions in terms of orthogonal parameters makes it a useful device for agent researchers exploring the design space of auction mechanisms.
The WALRAS Algorithm: A convergent distributed implementation of general equilibrium outcomes
The WALRAS algorithm calculates competitive equilibria via a distributed tatonnement-like process, in which agents submit single-good demand functions to market-clearing auctions. The algorithm is asynchronous and decentralized with respect to both agents and markets, making it suitable for distributed implementation. We present a formal description of this algorithm, and prove that it converges under the standard assumption of gross substitutability. We relate our results to the literature on general equilibrium stability and some more recent work on decentralized algorithms. We present some experimental results as well, particularly for cases where the assumptions required to guarantee convergence do not hold. Finally, we consider some extensions and generalizations to the WALRAS algorithm.
Market-Aware Agents for a Multiagent World
A computational market is any collection of software agents interacting through a price system. Markets can provide effective allocation of resources for a variety of distributed environments, and economic analysis a powerful design tool for interaction mechanisms. The spread of computational markets puts a premium on market-aware agents, and presents a case for market awareness on the part of agent developers and AI researchers as well.
Graphical representations of consensus belief
Graphical models based on conditional independence support concise encodings of the subjective belief of a single agent. A natural question is whether the consensus belief of a group of agents can be represented with equal parsimony. We prove, under relatively mild assumptions, that even if everyone agrees on a common graph topology, no method of combining beliefs can maintain that structure. Even weaker conditions rule out local aggregation within conditional probability tables. On a more positive note, we show that if probabilities are combined with the logarithmic opinion pool (LogOP), then commonly held Markov independencies are maintained. This suggests a straightforward procedure for constructing a consensus Markov network. We describe an algorithm for computing the LogOP with time complexity comparable to that of exact Bayesian inference.
Distributed quiescence detection in multiagent negotiation
In a distributed multiagent negotiation involving multiple issues, it is often desirable to finalize deals only when all related issues are resolved. However, detecting that a multiagent negotiation has reached a globally quiescent state can be a nontrivial task in a distributed, asynchronous system. We present a quiescence detection protocol based on the Dijkstra-Scholten algorithm for distributed termination detection. The protocol operates as a layer on top of an underlying mediated negotiation protocol. If agents conform to the detection protocol, the detection process terminates iff the negotiation is quiescent. We discuss agent incentives to deviate from the protocol, and describe extensions that enforce adherence with respect to the most significant potential deviations.
Probabilistic state-dependent grammars for plan recognition
Techniques for plan recognition under uncertainty require a stochastic model of the plan-generation process. We introduce Probabilistic State-Dependent Grammars (PSDGs) to represent an agent's plan-generation process. The PSDG language model extends probabilistic context-free grammars (PCFGs) by allowing production probabilities to depend on an explicit model of the planning agent's internal and external state. Given a PSDG description of the plan-generation process, we can then use inference algorithms that exploit the particular independence properties of the PSDG language to efficiently answer plan-recognition queries. The combination of the PSDG language model and inference algorithms extends the range of plan-recognition domains for which practical probabilistic inference is possible, as illustrated by applications in traffic monitoring and air combat.
