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.…

Multiattribute auctions based on generalized additive independence

We develop multiattribute auctions that accommodate generalized additive independent (GAI) preferences. We propose an iterative auction mechanism that maintains prices on potentially overlapping GAI clusters of attributes, thus decreases elicitation and computational burden, and creates an open competition among suppliers over a multidimensional domain. Most significantly, the auction is guaranteed to achieve surplus which approximates optimal welfare up to a small additive factor, under reasonable equilibrium strategies of traders. The main departure of GAI auctions from previous literature is to accommodate non-additive trader preferences, hence allowing traders to condition their evaluation of specific attributes on the value of other attributes. At the same time, the GAI structure supports a compact representation of prices, enabling a tractable auction process. We perform a simulation study, demonstrating and quantifying the significant efficiency advantage of more expressive preference modeling. We draw random GAI-structured utility functions with various internal structures, generate additive functions that approximate the GAI utility, and compare the performance of the auctions using the two representations. We find that allowing traders to express existing dependencies among attributes improves the economic efficiency of multiattribute auctions.

History-Dependent Graphical Multiagent Models

A dynamic model of a multiagent system defines a probability distribution over possible system behaviors over time. Alternative representations for such models present tradeoffs in expressive power, and accuracy and cost for inferential tasks of interest. In a history-dependent representation, behavior at a given time is specified as a probabilistic function of some portion of system history. Models may be further distinguished based on whether they specify individual or joint behavior. Joint behavior models are more expressive, but in general grow exponentially in number of agents. Graphical multiagent models (GMMs) provide a more compact representation of joint behavior, when agent interactions exhibit some local structure. We extend GMMs to condition on history, thus supporting inference about system dynamics. To evaluate this hGMM representation we study a voting consensus scenario, where agents on a network attempt to reach a preferred unanimous vote through a process of smooth fictitious play. We induce hGMMs and individual behavior models from example traces, showing that the former provide better predictions, given limited history information. These hGMMs also provide advantages for answering general inference queries compared to sampling the true generative model.

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…

A categorization of KR&R methods for requirement analysis of a query answering knowledge base

VK Chaudhri, B Bredeweg, R Fikes, S McIlraith, and MP Wellman Sixth International Conference on Formal Ontology in Information Systems, pages 158–171, May 2010. Abstract Our long-term goal is to build a query answering system that can…

Strategic Modeling of Information Sharing Among Data Privacy Attackers

Q Duong, K LeFevre, and MP Wellman Informatica 34:151-158, 2010. Original version presented at the IJCAI-09 Workshop on Quantitative Risk Analysis for Security Applications. Abstract Research in privacy-preserving data publishing has revealed…