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.

Market-Based Allocation with Indivisible Bids

We study multi-unit double auctions accepting bids with indivisibility constraints. Modeling the auction problem as a Multiple Choice Knapsack Problem and using dynamic programming, we show that incremental computations during bid processing can speed the handling of key auction operations such as clearing and quoting. We propose different price-quote policies and study their influence on the efficiency of market-based allocation. Using a reconfigurable manufacturing scenario where agents trade large quantities of multiple goods, we demonstrate potential benefits of supporting indivisibility constraints in bidding. These benefits are highly sensitive to the form of price quote provided, indicating interesting tradeoffs in communication and allocation efficiency.

Learning Payoff Functions in Infinite Games

We consider a class of games with real-valued strategies and payoff information available only in the form of data from a given sample of strategy profiles. Solving such games with respect to the underlying strategy space requires generalizing from the data to a complete payoff-function representation. We address payoff-function learning as a standard regression problem, with provision for capturing known structure (e.g., symmetry) in the multiagent environment. To measure learning performance, we consider the relative utility of prescribed strategies, rather than the accuracy of payoff functions per se. We demonstrate our approach and evaluate its effectiveness on two examples: a two-player version of the first-price sealed-bid auction (with known analytical form), and a five-player market-based scheduling game (with no known solution). Additionally, we explore the efficacy of using relative utility of strategies as a target of supervised learning and as a learning model selector. Our experiments demonstrate its effectiveness in the former case, though not in the latter.

Iterated Weaker-than-Weak Dominance

We introduce a weakening of standard game-theoretic dominance conditions, called delta-dominance, which enables more aggressive pruning of candidate strategies at the cost of solution accuracy. Equilibria of a game obtained by eliminating a delta-dominated strategy are guaranteed to be approximate equilibria of the original game, with degree of approximation bounded by the dominance parameter, delta. We can apply elimination of delta-dominated strategies iteratively, but the delta for which a strategy may be eliminated depends on prior eliminations. We discuss implications of this order independence, and propose greedy heuristics for determining a sequence of eliminations to reduce the game as far as possible while keeping down costs. A case study analysis of an empirical 2-player game serves to illustrate the technique, and demonstrate the utility of weaker-than-weak dominance pruning.

Generalized Value Decomposition and Structured Multiattribute Auctions

Multiattribute auction mechanisms generally either remain agnostic about traders’ preferences, or presume highly restrictive forms, such as full additivity. Real preferences often exhibit dependencies among attributes, yet may possess some structure that can be usefully exploited to streamline communication and simplify operation of a multiattribute auction. We develop such a structure using the theory of measurable value functions, a cardinal utility representation based on an underlying order over preference differences. A set of local conditional independence relations over such differences supports a generalized additive preference representation, which decomposes utility across overlapping clusters of related attributes. We introduce an iterative auction mechanism that maintains prices on local clusters of attributes rather than the full space of joint configurations. When traders’ preferences are consistent with the auction’s generalized additive structure, the mechanism produces approximately optimal allocations, at approximate VCG prices.

Empirical Game-Theoretic Analysis of the TAC Supply Chain Game

The TAC Supply Chain Management (TAC/SCM) game presents a challenging dynamic environment for autonomous decision-making in a salient application domain. Strategic interactions complicate the analysis of games such as TAC/SCM, since the effectiveness of a given strategy depends on the strategies played by other agents on the supply chain. The TAC tournament generates results from one particular path of combinations, and success in the tournament is rightly regarded as evidence for agent quality. Such results along with post-competition controlled experiments provide useful evaluations of novel techniques employed in the game. We argue that a broader game-theoretic analysis framework can provide a firmer foundation for choice of experimental contexts. Exploiting a repository of agents from the 2005 and 2006 TAC/SCM tournaments, we demonstrate an empirical game-theoretic methodology based on extensive simulation and careful measurement. Our analysis of agents from TAC-05 reveals interesting interactions not seen in the tournament. Extending the analysis to TAC-06 enables us to measure progress from year-to-year, and generates a candidate empirical equilibrium among the best known strategies. We use this equilibrium as a stable background population for comparing relative performance of the 2006 agents, yielding insights complementing the tournament results.