Scaling simulation-based game analysis through deviation-preserving reduction

B Wiedenbeck and MP Wellman Eleventh International Conference on Autonomous Agents and Multiagent Systems, June 2012. Abstract Multiagent simulation extends the reach of game-theoretic analysis to scenarios where payoff functions can be computed…

Trading Agents

MP Wellman Morgan & Claypool Publishers, Synthesis Lectures on Artificial Intelligence and Machine Learning Abstract Automated trading in electronic markets is one of the most common and consequential applications of autonomous software…

Access Point Selection under Emerging Wireless Technologies

B-A Cassell, T Alperovich, MP Wellman, and B Noble Sixth Workshop on the Economics of Networks, Systems, and Computation (NetEcon), June 2011. Abstract Users of wireless networks increasingly face a choice among multiple available access…

Asset pricing under ambiguous information: An empirical game-theoretic analysis

B-A Cassell and MP Wellman Computational and Mathematical Organization Theory 18:445–462, 2012 preliminary version presented at SpringSim Agent-Directed Simulation Symposium, April 2011. Abstract In a representative agent model, the…

Incentivizing responsible networking via introduction-based routing

G Frazier, Q Duong, MP Wellman, and E Petersen Fourth International Conference on Trust and Trustworthy Computing, June 2011. Proceedings published as McCune et al. (eds.), Lecture Notes in Computer Science #6740, Springer. Abstract The…

Strategy exploration in empirical games

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.

Strategy and Mechanism Lessons from the First Ad Auctions Trading Agent Competition

PR Jordan, MP Wellman, and G Balakrishnan Proceedings of the 11th ACM Conference on Electronic Commerce, pages 287–296, July 2010. Abstract The inaugural tournament for the Trading Agent Competition Ad Auctions game was held in July 2009.…

Algorithms for Finding Approximate Formations in Games

PR Jordan and MP Wellman Twenty-Fourth AAAI Conference on Artificial Intelligence, pages 798–804, July 2010. Copyright © 2010, AAAI. Abstract Many computational problems in game theory, such as finding Nash equilibria, are algorithmically…

Constrained automated mechanism design for infinite games of incomplete information

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.

Stochastic Search Methods for Nash Equilibrium Approximation in Simulation-Based Games

We define the class of games called simulation-based games, in which the payoffs are available as an output of an oracle (simulator), rather than specified analytically or using a payoff matrix. We then describe a convergent algorithm based on a hierarchical application of simulated annealing for estimating Nash equilibria in simulation-based games with finite-dimensional strategy sets. Additionally, we present alternative algorithms for best response and Nash equilibrium estimation, with a particular focus on one-shot infinite games of incomplete information. Our experimental results demonstrate that all the approaches we introduce are efficacious, albeit some more so than others. We show, for example, that while iterative best response dynamics has relatively weak convergence guarantees, it outperforms our convergent method experimentally. Additionally, we provide considerable evidence that a method based on random search outperforms gradient descent in our setting.