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.

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.

Strategic Analysis with Simulation-Based Games

Y Vorobeychik and MP Wellman