Nash Q-learning for general-sum stochastic games

We extend Q-learning to a noncooperative multiagent context, using the framework of general-sum stochastic games. A learning agent maintains Q-functions over joint actions, and performs updates based on assuming Nash equilibrium behavior over the current Q-values. This learning protocol provably converges given certain restrictions on the stage games (defined by Q-values) that arise during learning. Experiments with a pair of two-player grid games suggest that such restrictions on the game structure are not necessarily required. Stage games encountered during learning in both grid environments violate the conditions. However, learning consistently converges in the first grid game, which has a unique equilibrium Q-function, but sometimes fails to converge in the second, which has three different equilibrium Q-functions. In a comparison of offline learning performance in both games, we find agents are more likely to reach a joint optimal path with Nash Q-learning than with a single-agent Q-learning method. When at least one agent adopts Nash Q-learning, the performance of both agents is better than using single-agent Q-learning. We have also implemented an online version of Nash Q-learning that balances exploration with exploitation, yielding improved performance.

On market-inspired approaches to propositional satisfiability

We describe three market-inspired approaches to propositional satisfiability. The first is based on a formulation of satisfiability as production on a supply chain, where producers of particular variable assignments must acquire licenses to fail to satisfy particular clauses. Experiments show that although this general supply-chain protocol can converge to market allocations corresponding to satisfiable truth assignments, it is impractically slow. We find that a simplified market structure and a variation on the pricing method can improve performance significantly. We compare the performance of the three market-based protocols with distributed breakout algorithm and GSAT on benchmark 3-SAT problems. We identify a tradeoff between performance and economic realism in the market protocols, and a tradeoff between performance and the degree of decentralization between the market protocols and distributed breakout. We also conduct informal and experimental analyses to gain insight into the operation of price-guided search.

Decentralized supply chain formation: A market protocol and competitive equilibrium analysis

Supply chain formation is the process of determining the structure and terms of exchange relationships to enable a multilevel, multiagent production activity. We present a simple model of supply chains, highlighting two characteristic features: hierarchical subtask decomposition, and resource contention. To decentralize the formation process, we introduce a market price system over the resources produced along the chain. In a competitive equilibrium for this system, agents choose locally optimal allocations with respect to prices, and outcomes are optimal overall. To determine prices, we define a market protocol based on distributed, progressive auctions, and myopic, non-strategic agent bidding policies. In the presence of resource contention, this protocol produces better solutions than the greedy protocols common in the artificial intelligence and multiagent systems literature. The protocol often converges to high-value supply chains, and when competitive equilibria exist, typically to approximate competitive equilibria. However, complementarities in agent production technologies can cause the protocol to wastefully allocate inputs to agents that do not produce their outputs. A subsequent decommitment phase recovers a significant fraction of the lost surplus.

The 2001 Trading Agent Competition

The 2001 Trading Agent Competition was the second in a series of events aiming to shed light on research issues in automating trading strategies. Based on a challenging market scenario in the domain of travel shopping, the competition presents agents with difficult issues in bidding strategy, market prediction, and resource allocation. Entrants in 2001 demonstrated substantial progress over the prior year, with the overall level of competence exhibited suggesting that trading in online markets is a viable domain for highly autonomous agents

Rule-Based Specification of Auction Mechanisms

Machine-readable specifications of auction mechanisms facilitate configurable implementation of computational markets, as well as standardization and formalization of the auction design space. We present an implemented rule-based scripting language for auctions, which provides constructs for specifying temporal control structure, while supporting orthogonal definition of mechanism policy parameters. Through a series of examples, we show how the language can capture much of the space of single-dimensional auctions, and can be extended to cover other novel designs.

Computing Best-Response Strategies in Infinite Games of Incomplete Information

We describe an algorithm for computing best-response strategies in a class of infinite games of incomplete information, defined by payoffs piecewise linear in agents' types and actions, conditional on linear comparisons of agents' actions. We show that this class includes several well-known games including a variety of auctions, a novel allocation game, and variations. In some cases, the best-response algorithm can be iterated to compute Bayes-Nash equilibria. We demonstrate the efficacy of our approach on existing and new games.

Bounding probabilistic relationships in Bayesian networks using qualitative influences: Methods and applications

We present conditions under which one can bound the probabilistic relationships between random variables in a Bayesian network by exploiting known or induced qualitative relationships. Generic strengthening and weakening operations produce bounds on cumulative distributions, and the directions of these bounds are maintained through qualitative influences. We show how to incorporate these operations in a state-space abstraction method, so that bounds provably tighten as an approximate network is refined. We apply these techniques to qualitative tradeoff resolution demonstrating an ability to identify qualitative relationships among random variables without exhaustively using the probabilistic information encoded in the given network. In an application to path planning, we present an anytime algorithm with run-time computable error bounds.

Online Marketplaces

Even before the advent of the world-wide web, it was widely recognized that emerging global communication networks offered the potential to revolutionize trading and commerce. The web explosion of the late 1990s was thus accompanied immediately by a frenzy of effort attempting to translate existing markets and introduce new ones to the Internet medium. Although many of these early marketplaces did not survive, quite a few important ones did, and there are many examples where the Internet has enabled fundamental change in the conduct of trade. Although we are still in early days, automating commerce via online markets has in many sectors already led to dramatic efficiency gains through reduction of transaction costs, improved matching of buyers and sellers, and broadening the scope of trading relationships. Of course, we could not hope to cover in this space the full range of interesting ways in which the Internet contributes to the automation of market activities. Instead, this chapter addresses a particular slice of electronic commerce, in which the Internet provides a new medium for marketplaces. Since the population of online marketplaces is in great flux, we focus on general concepts and organizing principles, illustrated by a few examples rather than attempting an exhaustive survey.

Value-Driven Procurement in a Supply Chain Game

The TAC supply-chain game presents automated trading agents with challenging decision problems, including procurement of supplies across multiple periods using multiattribute negotiation. The procurement process involves substantial uncertainty and competition among multiple agents. Our agent, Deep Maize, generates requests for components based on deviations from a reference inventory trajectory defined by estimated market conditions. It then selects among supplier offers by optimizing a value function over potential inventory profiles. This approach offered strategic flexibility and achieved competitive performance in the TAC-03 tournament.