Notes on equilibria in symmetric games

Decision makers on supply chains face an uncertain, dynamic, and strategic multiagent environment. We report on Deep Maize, an agent we designed to participate in the 2003 Trading Agent Competition, Supply Chain Management (TAC/SCM) game. Our design employs an idealized equilibrium analysis of the SCM game to factor out the strategic aspects of the environment, and to define an expected profitable zone of operation. Deep Maize applies distributed feedback control to coordinate its separate functional modules and maintain its environment in the desired zone, despite the uncertainty and dynamism. We evaluate our design with results from the TAC/SCM tournament as well as from controlled experiments conducted after the competition.

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.

Price Prediction Strategies for Market-Based Scheduling

In a market-based scheduling mechanism, the allocation of time-specific resources to tasks is governed by a competitive bidding process. Agents bidding for multiple, separately allocated time slots face the risk that they will succeed in obtaining only part of their requirement, incurring expenses for potentially worthless slots. We investigate the use of price prediction strategies to manage such risk. Given an uncertain price forecast, agents follow simple rules for choosing whether and on which time slots to bid. We find that employing price predictions can indeed improve performance over a straightforward baseline in some settings. Using an empirical game-theoretic methodology, we establish Nash equilibrium profiles for restricted strategy sets. This allows us to confirm the stability of price-predicting strategies, and measure overall efficiency. We further experiment with variant strategies to analyze the source of prediction's power, demonstrate the existence of self-confirming predictions, and compare the performance of alternative prediction methods.

Price Prediction in a Trading Agent Competition

The 2002 Trading Agent Competition (TAC) presented agents with a challenging market game in the domain of travel shopping. One of the pivotal issues in this domain is uncertainty about hotel prices, which have a significant influence on the relative cost of alternative trip schedules. Thus, virtually all participating agents employ some method for predicting hotel prices. We survey approaches employed in the tournament, finding that agents apply an interesting diversity of techniques, taking into account differing sources of evidence bearing on prices. Based on data provided by entrants on their agents' actual predictions in the TAC-02 finals and semifinals, we analyze the relative efficacy of these approaches. Employing a new measure of prediction quality, we relate absolute accuracy to bottom-line performance in the game.

Distributed feedback control for decision making on supply chains

Decision makers on supply chains face an uncertain, dynamic, and strategic multiagent environment. We report on Deep Maize, an agent we designed to participate in the 2003 Trading Agent Competition, Supply Chain Management (TAC/SCM) game. Our design employs an idealized equilibrium analysis of the SCM game to factor out the strategic aspects of the environment, and to define an expected profitable zone of operation. Deep Maize applies distributed feedback control to coordinate its separate functional modules and maintain its environment in the desired zone, despite the uncertainty and dynamism. We evaluate our design with results from the TAC/SCM tournament as well as from controlled experiments conducted after the competition.