Real time issues for Internet auctions
MP Wellman and PR Wurman
First IEEE Workshop on Dependable and Real-Time E-Commerce Systems (DARE-98), Denver, CO, USA, June 1998.
Abstract
Designers of online auction mechanisms face many interesting choices related to the timing of…
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.