Empirical analyses of complex games necessarily focus on a restricted set of strategies, and thus the value of empirical game models depends on effective methods for selectively exploring a space of strategies. We formulate an iterative framework for strategy exploration, and experimentally evaluate an array of generic exploration policies on three games: one infinite game with known analytic solution, and two relatively large empirical games generated by simulation. Policies based on iteratively finding a beneficial deviation or best response to the minimum-regret profile among previously explored strategies perform generally well on the profile-regret measure, although we find that some stochastic introduction of suboptimal responses can often lead to more effective exploration in early stages of the process. A novel formation-based policy performs well on all measures by producing low-regret approximate formations earlier than the deviation-based policies.

In this talk, I describe my recent research on Internet ad auctions, in particular, determining which is more valuable: an optimal ad auction mechanism engineered by scientists or an additional advertiser supplied by salesmen. My approach is empirical, using the TAC Ad Auction game as a testbed for experimentation. The Ad Auction game is a high-fidelity model of a sponsored search market that allows participants to simulate campaign management. Using strategies from the TAC 2009 tournament, I derive equilibria of the empirical game under various publisher (search engine) mechanisms -- foremost, under different reserve settings. I find that the optimal reserve score increases the publisher's revenue by over 300 percent, when compared to the base mechanism with low reserves. In addition, I find that the publisher is willing to lose 62 percent of the advertisers, in exchange for the optimal reserves.

The University of Michigan TAC Ad Auctions development team is pleased to announce the release the source code for the 2009 game. Please visit the software page on the TAC/AA website for more information.

I describe a research effort for developing empirical methods to analyze market scenarios involving trading agents. In cases where exact analytical models of a game cannot be constructed, empirical game-theoretic models often provide a viable alternative. I address three basic problems of interest within empirical game theory. First, given an empirical model of the game, how should strategies be evaluated? Second, given a set of heuristic strategies and a computational budget for simulating agent play, how should modelers optimally select profiles to be simulated? Finally, given observations of agent play, what game model best predicts payoffs resulting from agent play?

Our overall goal is to try to estimate a statistical parameter that is the mean payoff for each agent in a TAC/AA profile. Unfortunately this requires a large amount of data for each profile. In lieu of this, we try to estimate a statistical parameter that is the mean payoff for each given agent with the same adjustment for “luck” across all agents. In this method, we use an agent identifier as an additional factor in the regression. The intuition this method is that, in general, agents are likely to score differently on average due to some inherent difference in strategic quality. If we do not account for this, the regression will use correlations in the control variables to “explain” the variance in scores. In some cases, the agents condition their strategy on these variables. This makes the regression heavily dependent on the mixture of the agents played and how those agents condition on the control variables. By adding an agent indicator in the regression we reduce, but not eliminate, this effect.