Learning Graphical Game Models

Graphical games provide compact representation of a multiagent interaction when agents' payoffs depend only on actions of agents in their local neighborhood. We formally describe the problem of learning a graphical game model from limited observation of the payoff function, define three performance metrics for evaluating learned games, and investigate several learning algorithms based on minimizing empirical loss. Our first algorithm is a branch-and-bound search, which takes advantage of the structure of the empirical loss function to derive upper and lower bounds on loss at every node of the search tree. We also examine a greedy heuristic and local search algorithms. Our experiments with directed graphical games show that (i) when only a small sample of profile payoffs is available, branch-and-bound significantly outperforms other methods, and has competitive running time, but (ii) when many profiles are observed, greedy is nearly optimal and considerably better than other methods, at a fraction of branch-and-bound's running time. The results are comparable for undirected graphical games and when payoffs are sampled with noise.

Information Feedback and Efficiency in Multiattribute Double Auctions

We investigate tradeoffs among expressiveness, operational cost, and economic efficiency for a class of multiattribute double-auction markets. To enable polynomial-time clearing and information feedback operations, we restrict the bidding language to a form of multiattribute OR-of-XOR expressions. We then consider implications of this restriction in environments where bidders' preferences lie within a strictly larger class, that of complement-free valuations. Using valuations derived from a supply chain scenario, we show that an iterative bidding protocol can overcome the limitations of this language restriction. We further introduce a metric characterizing the degree to which valuations violate the substitutes condition, theoretically known to guarantee efficiency, and present experimental evidence that the actual efficiency loss is proportional to this metric.

Generalization Risk Minimization in Empirical Game Models

Experimental analysis of agent strategies in multiagent systems presents a tradeoff between granularity and statistical confidence. Collecting a large amount of data about each strategy profile improves confidence, but restricts the range of strategies and profiles that can be explored. We propose a flexible approach, where multiple game-theoretic formulations can be constructed to model the same underlying scenario (observation dataset). The prospect of incorrectly selecting an empirical model is termed generalization risk, and the generalization risk framework we describe provides a general criterion for empirical modeling choices, such as adoption of factored strategies or other structured representations of a game model. We propose a principled method of managing generalization risk to derive the optimal game-theoretic model for the observed data in a restricted class of models. Application to a large dataset generated from a trading agent scenario validates the method.

Forecasting Market Prices in a Supply Chain Game

Predicting the uncertain and dynamic future of market conditions on the supply chain, as reflected in prices, is an essential component of effective operational decision-making. We present and evaluate methods used by our agent, Deep Maize, to forecast market prices in the trading agent competition supply chain management game (TAC/SCM). We employ a variety of machine learning and representational techniques to exploit as many types of information as possible, integrating well-known methods in novel ways. We evaluate these techniques through controlled experiments as well as performance in both the main TAC/SCM tournament and supplementary Prediction Challenge. Our prediction methods demonstrate strong performance in controlled experiments and achieved the best overall score in the Prediction Challenge.

Designing the Ad Auctions Game for the Trading Agent Competition

We introduce the TAC Ad Auctions game (TAC/AA), a new game for the Trading Agent Competition. The Ad Auctions game investigates complex strategic issues found in real sponsored search auctions that are not captured in current analytical models. We provide an overview of TAC/AA, introducing its key features and design rationale. TAC/AA will debut in summer 2009, with the final tournament commencing in conjunction with the TADA-09 workshop.