Compact securities markets for Pareto optimal reallocation of risk
The securities market is the fundamental theoretical framework in economics and finance for resource allocation under uncertainty. Securities serve both to reallocate risk and to disseminate probabilistic information. Complete securities markets—which contain one security for every possible state of nature—support Pareto optimal allocations of risk. Complete markets suffer from the same exponential dependence on the number of underlying events as do joint probability distributions. We examine whether markets can be structured and “compacted” in the same manner as Bayesian network representations of joint distributions. We show that, if all agents’ risk-neutral independencies agree with the independencies encoded in the market structure, then the market is operationally complete: risk is still Pareto optimally allocated, yet the number of securities can be exponentially smaller. For collections of agents of a certain type, agreement on Markov independencies is sufficient to admit compact and operationally complete markets.
AkBA: A progressive, anonymous-price combinatorial auction
The allocation of discrete, complementary resources is a fundamental problem in economics and of direct interest to e-commerce applications. Combinatorial auctions account for complementarities by optimizing over offers expressed in terms of bundles. Progressive versions of combinatorial auctions alleviate the burden on bidders of expressing offers for all bundles of interest by providing interim feedback based on partial sets of bids. Feedback in terms of hypothetical prices is particularly useful, as it directs bidders toward those bundles potentially yielding the greatest surplus. For a general class of discrete resource allocation problems with free disposal, we establish by construction the existence of competitive equilibrium prices on bundles that support the efficient allocation. We introduce AkBA, a family of progressive auctions that use these equilibrium bundle prices. We examine a particular instance of the family, called A1BA, and present some empirical data on its performance.
Combinatorial auctions for supply chain formation
Supply chain formation presents difficult coordination issues for distributed negotiation protocols. Agents must simulatenously negotiate production relationships at multiple levels, with important interdependencies among inputs and outputs at each level. Combinatorial auctions address this problem by global optimization over expressed offers to engage in compound exchanges. A one-shot combinatorial auction that optimizes the reported value of the bids results in optimal allocations with truthful bids. But autonomous self-interested agents have an incentive to bid strategically in an attempt to gain extra surplus. We investigate a particular combinatorial protocol consisting of a one-shot auction and a strategic bidding policy. We experimentally analyze the efficiency and producer surplus obtained in five networks, and compare this performance to that of a distributed, progressive auction protocol with non-strategic bidding. We find that producers can sometimes gain significantly by bidding strategically. However, when the available surplus is small relative to the consumers' values, the producers' strategic behavior may prevent the supply chain from forming at all, resulting in zero gains for all agents. We examine the robustness of the combinatorial protocol by investigating agent incentives to deviate, identifying quasi-equilibrium behavior for an example network.
Designing the Market Game for a Trading Agent Competition
The authors discuss the design and operation of a trading agent competition, focusing on the game structure and some of the key technical issues in running and playing the game.
Learning about other agents in a dynamic multiagent system
We analyze the problem of learning about other agents in a class of dynamic multiagent systems, where performance of the primary agent depends on behavior of the others. We consider an online version of the problem, where agents must learn models of the others in the course of continual interactions. Various levels of recursive models are implemented in a simulated double auction market. Our experiments show learning agents on average outperform non-learning agents who do not use information about others. Among learning agents, those with minimum recursion assumption generally perform better than the agents with more complicated, though often wrong assumptions.
Auction Protocols for Decentralized Scheduling
Decentralized scheduling is the problem of allocating resources to alternative possible uses over time, where competing uses are represented by autonomous agents. Market mechanisms use prices derived through distributing bidding protocols to determine schedules. We investigate the existence of equilibrium prices for some general classes of scheduling problems, the quality of equilibrium solutions, and the behavior of an ascending auction mechanism and bidding protocol. To remedy the potential nonexistence of price equilibria due to complementarities in preference, we introduce additional markets in combinations of basic goods. Finally, we consider direct revelation mechanisms and compare to the market-based approach.
A Parametrization of the Auction Design Space
We present an extensive breakdown of the auction design space that captures the essential similarities and differences of many auction mechanisms in a format more descriptive and useful than simple taxonomies. This parametrization serves as an organizational framework in which to classify work within the field and uncovers parameter combinations corresponding to novel mechanisms. The structured characterization of auction rules can be exploited for the modular design of configurable auction servers. It also facilitates the communication of auction rules to software agents, enabling the automation of flexible market-based negotiation.
Evaluation of Bayesian networks with flexible state-space abstraction methods
We investigate state-space abstraction methods for computing approximate probabilities with Bayesian networks. These methods approximate Bayesian networks by aggregating the states of variables. We implement an iterative approximation procedure based on this idea, and the procedure demonstrates the desirable anytime property in experiments. Further theoretical analysis reveals special properties of the approximations, and we exploit these properties to design heuristics for improving performance profiles of the iterative procedure.
Automated Negotiation from Declarative Contract Descriptions
Our approach for automating the negotiation of business contracts proceeds in three broad steps. First, determine the structure of the negotiation process by applying general knowledge about auctions and domain-specific knowledge about the contract subject along with preferences from potential buyers and sellers. Second, translate the determined negotiation structure into an operational specification for an auction platform. Third, after the negotiation has completed, map the negotiation results to a final contract.We have implemented a prototype which supports these steps by employing a declarative specification (in Courteous Logic Programs) of (1) high-level knowledge about alternative negotiation structures, (2) general-case rules about auction parameters, (3) rules to map the auction parameters to a specific auction platform, and (4) special-case rules for subject domains. We demonstrate the flexibility of this approach by automatically generating several alternative negotiation structures for the domain of travel shopping in a trading agent competition.
Trading Agents Competing: Performance, Progress, and Market Effectiveness
Since the year 2000, the annual trading agent competition has provided a forum for designers to evaluate programmed trading techniques in a challenging market scenario in competition with other design groups. After three years of apparent progress, we attempt to evaluate the trading competence of competition participants, in the 2002 tournament and over time. Although absolute measure of individual performance is difficult to assess, relative measures, and measures of the market performance overall are more amenable to direct analysis. We quantify the effectiveness of the TAC travel market in terms of allocative efficiency, finding improvement within and between tournaments. By comparison with alternative allocation benchmarks, we can calibrate this efficiency, and identify opportunities for further gain from trade.
