Author name cluster

Patrick Jordan

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers

1 author row

AAAI Conference 2010 Conference Paper

Algorithms for Finding Approximate Formations in Games

Patrick Jordan
Michael Wellman

Many computational problems in game theory, such as finding Nash equilibria, are algorithmically hard to solve. This limitation forces analysts to limit attention to restricted subsets of the entire strategy space. We develop algorithms to identify rationally closed subsets of the strategy space under given size constraints. First, we modify an existing family of algorithms for rational closure in two-player games to compute a related rational closure concept, called formations, for n-player games. We then extend these algorithms to apply in cases where the utility function is partially specified, or there is a bound on the size of the restricted profile space. Finally, we evaluate the performance of these algorithms on a class of random games.

PDF Details

AAMAS Conference 2010 Conference Paper

Strategy Exploration in Empirical Games

Patrick Jordan
L. Julian Schvartzman
Michael Wellman

Empirical analyses of complex games necessarily focus ona 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 experimentallyevaluate an array of generic exploration policies on threegames: one infinite game with known analytic solution, andtwo relatively large empirical games generated by simulation. Policies based on iteratively finding a beneficial deviation or best response to the minimum-regret profile amongpreviously explored strategies perform generally well on theprofile-regret measure, although we find that some stochastic introduction of suboptimal responses can often lead tomore effective exploration in early stages of the process. Anovel formation-based policy performs well on all measuresby producing low-regret approximate formations earlier thanthe deviation-based policies.

PDF

AAMAS Conference 2008 Conference Paper

Searching for Approximate Equilibria in Empirical Games

Patrick Jordan
Yevgeniy Vorobeychik
Michael Wellman

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

PDF