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.

Selecting Strategies using Empirical Game Models: An Experimental Analysis of Meta-Strategies

In many complex multi-agent domains it is impractical to compute exact analytic solutions. An alternate means of analysis applies computational tools to derive and analyze empirical game models. These models are noisy approximations, which raises questions about how to account for uncertainty when analyzing the model. We develop a novel experimental framework and apply it to benchmark meta-strategies – general algorithms for selecting strategies based on empirical game models. We demonstrate that modeling noise is important; a naïve approach that disregards noise and plays according to Nash equilibrium yields poor choices. We introduce three parameterized algorithms that factor noise into the analysis by predicting distributions of opponent play. As observation noise increases, rational players generally make less specific outcome predictions. Our comparison of the algorithms identifies logit equilibrium as the best method for making these predictions. Logit equilibrium incorporates a form of noisy decision-making by players. Our evidence shows that this is a robust method for approximating the effects of uncertainty in many contexts. This result has practical relevance for guiding analysis of empirical game models. It also offers an intriguing rationale for behavioral findings that logit equilibrium is a better predictor of human behavior than Nash equilibrium.

Searching for Approximate Equilibria in Empirical Games

When exploring a game over a large strategy space, it may not be feasible or cost-effective to evaluate the payoff of every relevant strategy profile. For example, determining a profile payoff for a procedurally defined game may require Monte Carlo simulation or other costly computation. Analyzing such games poses a search problem, with the goal of identifying equilibrium profiles by evaluating payoffs of candidate solutions and potential deviations from those candidates. We propose two algorithms, applicable to distinct models of the search process. In the revealed-payoff model, each search step determines the exact payoff for a designated pure-strategy profile. In the noisy-payoff model, a step draws a stochastic sample corresponding to such a payoff. We compare our algorithms to previous proposals from the literature for these two models, and demonstrate performance advantages.

Bidding Strategies for Simultaneous Ascending Auctions

Simultaneous ascending auctions present agents with various strategic problems, depending on preference structure. As long as bids represent non-repudiable offers, submitting non-contingent bids to separate auctions entails an exposure problem: bidding to acquire a bundle risks the possibility of obtaining an undesired subset of the goods. With multiple goods (or units of a homogeneous good) bidders also need to account for their own effects on prices. Auction theory does not provide analytic solutions for optimal bidding strategies in the face of these problems. We present a new family of decision-theoretic bidding strategies that use probabilistic predictions of final prices: self-confirming distribution-prediction strategies. Bidding based on these is provably not optimal in general. But evidence using empirical game-theoretic methods we developed indicates the strategy is quite effective compared to other known methods when preferences exhibit complementarities. When preferences exhibit substitutability, simpler demand-reduction strategies address the own price effect problem more directly and perform better.

Stronger CDA Strategies through Empirical Game-Theoretic Analysis and Reinforcement Learning

We present a general methodology to automate the search for equilibrium strategies in games derived from computational experimentation. Our approach interleaves empirical game-theoretic analysis with reinforcement learning. We apply this methodology to the classic Continuous Double Auction game, conducting the most comprehensive CDA strategic study published to date. Empirical game analysis confirms prior findings about the relative performance of known strategies. Reinforcement learning derives new bidding strategies from the empirical equilibrium environment. Iterative application of this approach yields strategies stronger than any other published CDA bidding policy, culminating in a new Nash equilibrium supported exclusively by our learned strategies.

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…

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.