Searching for Walverine 2005

We systematically explore a range of variations of our TAC travel-shopping agent, Walverine. The space of strategies is defined by settings to behavioral parameter values. Our empirical game-theoretic analysis is facilitated by approximating games through hierarchical reduction methods. This approach generated a small set of candidates for the version to run in the TAC-05 tournament. We selected among these based on performance in preliminary rounds, ultimately identifying a successful strategy for Walverine 2005.

Methods for Empirical Game-Theoretic Analysis (Extended Abstract)

An emerging empirical methodology bridges the gap between game theory and simulation for practical strategic reasoning.

Mechanism Design Based on Beliefs about Responsive Play (position paper)

In general, identifying a solution concept only incompletely specifies a mechanism design problem. The designer must consider which among a multiplicity of solutions is likely to be played, as well as the possibility that actual play will not correspond to any solution. Given that actual play is the ultimate determiner of a mechanism's success, we advocate that designers embrace the corresponding forecasting problem and evaluate candidate mechanisms with respect to belief distributions over players' response. Solution concepts can play a useful role in delimiting and structuring belief distributions. We propose that membership of prospective strategy profiles in various solution classes be treated as evidence bearing on their likelihood of play. Flexible solution classes, for example based on approximate equilibrium, degree of dominance, or safety level, provide natural measures (e.g., distance from equilibrium) that can be employed in defining belief distributions.

Market Efficiency, Sales Competition, and the Bullwhip Effect in the TAC SCM Tournaments

The TAC SCM tournament is moving into its fourth year. In an effort to track agent progress, we present a benchmark market efficiency comparison for the tournament, in addition to prior measures of agent competency through customer bidding. Using these benchmarks we find statistically significant increases in intratournament market efficiency, whereas agents are generally decreasing in manufacturer market power. We find that agent market share and bid efficiency have increased while the variance of average sales prices has been significantly reduced. Additionally, we test for a statistical relationship between agent profits and the bullwhip effect.

Empirical mechanism design: Methods, with application to a supply chain scenario

Our proposed methods employ learning and search techniques to estimate outcome features of interest as a function of mechanism parameter settings. We illustrate our approach with a design task from a supply-chain trading competition. Designers adopted several rule changes in order to deter particular procurement behavior, but the measures proved insufficient. Our empirical mechanism analysis models the relation between a key design parameter and outcomes, confirming the observed behavior and indicating that no reasonable parameter settings would have been likely to achieve the desired effect. More generally, we show that under certain conditions, the estimator of optimal mechanism parameter setting based on empirical data is consistent.

Empirical Game-Theoretic Analysis of Chaturanga

We analyze 4-player chaturanga (an ancient variant of chess) using the methods of empirical game theory. Like chess, this game is computationally challenging due to an extremely large strategy space. From the perspective of game theory, it is more interesting than chess because it has more than 2 players. Removing the 2-player restriction allows multiple equilibria and other complex strategic interactions that require the full tool set of game theory. The major challenge for applying game theoretic methods to such a large game is to identify a tractable subset of the game for detailed analysis that captures the essence of the strategic interactions. We argue that the notion of strategic independence holds significant promise for scaling game theory to large games. We present preliminary results based on data from two sets of strategies for chaturanga. These results suggest that strategic independence is present in chaturanga, and demonstrate some possible ways to exploit it.

Controlling a supply chain agent using value-based decomposition

We present and evaluate the design of Deep Maize, our entry in the 2005 Trading Agent Competition Supply Chain Management scenario. The central idea is to decompose the problem by estimating the value of key resources in the game. We first create a high-level production schedule that considers cross-cutting constraints and future decisions, but abstracts aways from the details of sales and purchasing. We then make specific sales and purchasing decisions separately, coordinating these decisions with the high-level schedule using resource values derived from the schedule. All of these decisions are made using approximate optimization techniques and make use of explicit predictions about market conditions. Deep Maize was one of the most successful agents in the 2005 tournament, both in overall performance and on specific measures that emphasize coordination.

Bid Expressiveness and Clearing Algorithms in Multiattribute Double Auctions

We investigate the space of two-sided multiattribute auctions, focusing on the relationship between constraints on the offers traders can express through bids, and the resulting computational problem of determining an optimal set of trades. We develop a formal semantic framework for characterizing expressible offers, and show conditions under which the allocation problem can be separated into first identifying optimal pairwise trades and subsequently optimizing combinations of those trades. We analyze the bilateral matching problem while taking into consideration relevant results from multiattribute utility theory. Network flow models we develop for computing global allocations facilitate classification of the problem space by computational complexity, and provide guidance for developing solution algorithms. Experimental trials help distinguish tractable problem classes for proposed solution techniques.

Automated Markets and Trading Agents

Computer automation has the potential, just starting to be realized, of transforming the design and operation of markets, and the behaviors of agents trading in them. We discuss the possibilities for automating markets, presenting a broad conceptual framework covering resource allocation as well as enabling marketplace services such as search and transaction execution. One of the most intriguing opportunities is provided by markets implementing computationally sophisticated negotiation mechanisms, for example combinatorial auctions. An important theme that emerges from the literature is the centrality of design decisions about matching the domain of goods over which a mechanism operates to the domain over which agents have preferences. When the match is imperfect (as is almost inevitable), the market game induced by the mechanism is analytically intractable, and the literature provides an incomplete characterization of rational bidding policies. A review of the literature suggests that much of our existing knowledge comes from computational simulations, including controlled studies of abstract market designs (e.g., simultaneous ascending auctions), and research tournaments comparing agent strategies in a variety of market scenarios. An empirical game-theoretic methodology combines the advantages of simulation, agent-based modeling, and statistical and game-theoretic analysis.

An Analysis of the 2004 Supply Chain Management Trading Agent Competition

We present and analyze results from the 2004 Trading Agent Competition supply chain management scenario. We identify behavioral differences between the agents that contributed to their performance in the competition. In the market for components, strategic early procurement remained an important factor despite rule changes from the previous year. We present a new experimental analysis of the impact of the rule changes on incentives for early procurement. In the finals, a novel strategy designed to block other agent's access to suppliers at the start of the game was pivotal. Some agents did not respond effectively to this strategy and were badly hurt by their inability to get crucial components. Among the top three agents, average selling prices in the market for finished goods were the decisive difference. Our analysis shows that supply and demand were key factors in determining overall market prices, and that some agents were more adept than others at exploiting advantageous market conditions.