Andrew G. Gilpin

Interests: Artificial intelligence, computational game theory, equilibrium computation, linear and integer programming, convex optimization, auctions, exchanges, mechanism design, electronic commerce, computational finance

Equilibrium computation

Andrew Gilpin, Javier Peña, and Tuomas Sandholm. 2008. First-order algorithm with O(ln (1/ε)) convergence for ε-equilibrium in two-person zero-sum games. 23rd National Conference on Artificial Intelligence (AAAI'08), Chicago, IL.
Samid Hoda, Andrew Gilpin, and Javier Peña. 2008. Smoothing techniques for computing Nash equilibria of sequential games. Available on Optimization Online. [view abstract]
We develop first-order smoothing techniques for saddle-point problems that arise in the Nash equilibria computation of sequential games. The crux of our work is a construction of suitable prox-functions for a certain class of polytopes that encode the sequential nature of the games. An implementation based on our smoothing techniques computes approximate Nash equilibria for games that are four orders of magnitude larger than what conventional computational approaches can handle.
This is a substantially revised version of :
- Samid Hoda, Andrew Gilpin, and Javier Peña. 2007. A gradient-based approach for computing Nash equilibria of large sequential games. Available on Optimization Online.
Andrew Gilpin and Tuomas Sandholm. 2008. Solving two-person zero-sum repeated games of incomplete information. International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS'08), Estoril, Portugal. [view abstract]
In repeated games with incomplete information, rational agents must carefully weigh the tradeoffs of advantageously exploiting their information to achieve a short-term gain versus carefully concealing their information so as not to give up a long-term informed advantage. The theory of infinitely-repeated two-player zero-sum games with incomplete information has been carefully studied, beginning with the seminal work of Aumann and Maschler. While this theoretical work has produced a characterization of optimal strategies, algorithms for solving for optimal strategies have not yet been studied. For the case where one player is informed about the true state of the world and the other player is uninformed, we provide a non-convex mathematical programming formulation for computing the value of the game, as well as optimal strategies for the informed player. We then describe an efficient algorithm for solving this difficult optimization problem to within arbitrary accuracy. We also discuss how to efficiently compute optimal strategies for the uninformed player using the output of our algorithm.
Andrew Gilpin, Samid Hoda, Javier Peña, and Tuomas Sandholm. 2007. Gradient-based algorithms for finding Nash equilibria in extensive form games. 3rd International Workshop on Internet and Network Economics (WINE'07), San Diego, CA. [view abstract]
We present a computational approach to the saddle-point formulation for the Nash equilibria of two-person, zero-sum sequential games of imperfect information. The algorithm is a first-order gradient method based on modern smoothing techniques for non-smooth convex optimization. The algorithm requires O(1) iterations to compute an ε-equilibrium, and the work per iteration is extremely low. These features enable us to find approximate Nash equilibria for sequential games with a tree representation of about 10¹⁰ nodes. This is three orders of magnitude larger than what previous algorithms can handle. We present two heuristic improvements to the basic algorithm and demonstrate their efficacy on a range of real-world games. Furthermore, we demonstrate how the algorithm can be customized to a specific class of problems with enormous memory savings.
Tuomas Sandholm, Andrew Gilpin, and Vincent Conitzer. 2005. Mixed-integer programming methods for finding Nash equilibria. 20th National Conference on Artificial Intelligence (AAAI'05), pp. 495-501, Pittsburgh, PA. [view abstract]
We present, to our knowledge, the first mixed integer program (MIP) formulations for finding Nash equilibria in games (specifically, two-player normal form games). We study different design dimensions of search algorithms that are based on those formulations. Our MIP Nash algorithm outperforms Lemke-Howson but not Porter-Nudelman-Shoham (PNS) on GAMUT data. We argue why experiments should also be conducted on games with equilibria with medium-sized supports only, and present a methodology for generating such games. On such games MIP Nash drastically outperforms PNS but not Lemke-Howson. Certain MIP Nash formulations also yield anytime algorithms for $\epsilon$-equilibrium, with provable bounds. Another advantage of MIP Nash is that it can be used to find an optimal equilibrium (according to various objectives). The prior algorithms can be extended to that setting, but they are orders of magnitude slower.

Automated abstraction of imperfect information games, poker AI

Andrew Gilpin and Tuomas Sandholm. 2008. Expectation-based versus potential-aware automated abstraction in imperfect information games: An experimental comparison using poker. Short paper. 23rd National Conference on Artificial Intelligence (AAAI'08), Chicago, IL. [view abstract]
Automated abstraction algorithms for sequential imperfect information games have recently emerged as a key component in developing competitive game theory-based agents. The existing literature has not investigated the relative performance of different abstraction algorithms. Instead, agents whose construction has used automated abstraction have only been compared under confounding effects: different granularities of abstraction and equilibrium-finding algorithms that yield different accuracies when solving the abstracted game.
This paper provides the first systematic evaluation of abstraction algorithms. Two families of algorithms have been proposed. The distinguishing feature is the measure used to evaluate the strategic similarity between game states. One algorithm uses the probability of winning as the similarity measure. The other uses a potential-aware similarity measure based on probability distributions over future states. We conduct experiments on Rhode Island Hold.em poker. We compare the algorithms against each other, against optimal play, and against each agent's nemesis. We also compare them based on the resulting game's value. Interestingly, for very coarse abstractions the expectation-based algorithm is better, but for moderately coarse and fine abstractions the potentialaware approach is superior. Furthermore, agents constructed using the expectation-based approach are highly exploitable beyond what their performance against the game's optimal strategy would suggest.
Andrew Gilpin, Tuomas Sandholm, and Troels Bjerre Sørensen. 2008. A heads-up no-limit Texas Hold'em poker player: Discretized betting models and automatically generated equilibrium-finding programs. International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS'08), Estoril, Portugal. [view abstract]
We present Tartanian, a game theory-based player for heads-up no-limit Texas Hold'em poker. Tartanian is built from three components. First, to deal with the virtually infinite strategy space of no-limit poker, we develop a discretized betting model designed to capture the most important strategic choices in the game. Second, we employ potential-aware automated abstraction algorithms for identifying strategically similar situations in order to decrease the size of the game tree. Third, we develop a new technique for automatically generating the source code of an equilibrium-finding algorithm from an XML-based description of a game. This automatically generated program is more efficient than what would be possible with a general-purpose equilibrium-finding program. Finally, we present results from the AAAI-07 Computer Poker Competition, in which Tartanian placed second out of ten entries.
Andrew Gilpin and Tuomas Sandholm. 2007. Lossless abstraction of imperfect information games. Journal of the ACM, 54(5). [view abstract]
Finding an equilibrium of an extensive form game of imperfect information is a fundamental problem in computational game theory, but current techniques do not scale to large games. To address this, we introduce the ordered game isomorphism and the related ordered game isomorphic abstraction transformation. For a multi-player sequential game of imperfect information with observable actions and an ordered signal space, we prove that any Nash equilibrium in an abstracted smaller game, obtained by one or more applications of the transformation, can be easily converted into a Nash equilibrium in the original game. We present an algorithm, GameShrink, for abstracting the game using our isomorphism exhaustively. Its complexity is Õ(n²), where n is the number of nodes in a structure we call the signal tree. It is no larger than the game tree, and on nontrivial games it is drastically smaller, so GameShrink has time and space complexity sublinear in the size of the game tree. Using GameShrink, we find an equilibrium to a poker game with 3.1 billion nodes--over four orders of magnitude more than in the largest poker game solved previously. To address even larger games, we introduce approximation methods that do not preserve equilibrium, but nevertheless yield (ex post) provably close-to-optimal strategies.
Subsumes:
- Andrew Gilpin and Tuomas Sandholm. 2006. Finding equilibria in large sequential games of imperfect information. ACM Conference on Electronic Commerce (EC'06), Ann Arbor, MI.
- Andrew Gilpin and Tuomas Sandholm. 2005. Finding equilibria in large sequential games of imperfect information. Technical Report CMU-CS-05-158, Carnegie Mellon University, Pittsburgh, PA.
Andrew Gilpin, Tuomas Sandholm, and Troels Bjerre Sørensen. 2007. Potential-aware automated abstraction of sequential games, and holistic equilibrium analysis of Texas Hold'em poker. 22nd National Conference on Artificial Intelligence (AAAI'07), Vancouver, BC, Canada. [view abstract]
We present a new abstraction algorithm for sequential imperfect information games. While most prior abstraction algorithms employ a myopic expected-value computation as a similarity metric, our algorithm considers a higher-dimensional space consisting of histograms over abstracted classes of states from later stages of the game. This enables our bottom-up abstraction algorithm to automatically take into account potential: a hand can become relatively better (or worse) over time and the strength of different hands can get resolved earlier or later in the game. We further improve the abstraction quality by making multiple passes over the abstraction, enabling the algorithm to narrow the scope of analysis to information that is relevant given abstraction decisions made for earlier parts of the game. We also present a custom indexing scheme based on suit isomorphisms that enables one to work on significantly larger models than before.
We apply the techniques to heads-up limit Texas Hold'em poker. Whereas all prior game theory-based work for Texas Hold'em poker used generic off-the-shelf linear program solvers for the equilibrium analysis of the abstracted game, we make use of a recently developed algorithm based on the excessive gap technique from convex optimization. This paper is, to our knowledge, the first to abstract and game-theoretically analyze all four betting rounds in one run (rather than splitting the game into phases). The resulting player, GS3, beats BluffBot, GS2, Hyperborean, Monash-BPP, Sparbot, Teddy, and Vexbot, each with statistical significance. To our knowledge, those competitors are the best prior programs for the game.
Andrew Gilpin and Tuomas Sandholm. 2007. Better automated abstraction techniques for imperfect information games, with application to Texas Hold'em poker. Sixth International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS'07), Honolulu, HI. Finalist for Best Paper Award. [view abstract]
We present new approximation methods for computing game-theoretic strategies for sequential games of imperfect information. At a high level, we contribute two new ideas. First, we introduce a new state-space abstraction algorithm. In each round of the game, there is a limit to the number of strategically different situations that an equilibrium-finding algorithm can handle. Given this constraint, we use clustering to discover similar positions, and we compute the abstraction via an integer program that minimizes the expected error at each stage of the game. Second, we present a method for computing the leaf payoffs for a truncated version of the game by simulating the actions in the remaining portion of the game. This allows the equilibrium-finding algorithm to take into account the entire game tree while having to explicitly solve only a truncated version. Experiments show that each of our two new techniques improves performance dramatically in Texas Hold'em poker. The techniques lead to a drastic improvement over prior approaches for automatically generating agents, and our agent plays competitively even against the best agents overall.
Andrew Gilpin and Tuomas Sandholm. 2006. A competitive Texas Hold'em poker player via automated abstraction and real-time equilibrium computation. 21st National Conference on Artificial Intelligence (AAAI'06), Boston, MA. [view abstract]
We present a game theory-based heads-up Texas Hold'em poker player, GS1. To overcome the computational obstacles stemming from Texas Hold'em's gigantic game tree, the player employs our automated abstraction techniques to reduce the complexity of the strategy computations. Texas Hold'em consists of four betting rounds. Our player solves a large linear program (offline) to compute strategies for the abstracted first and second rounds. After the second betting round, our player updates the probability of each possible hand based on the observed betting actions in the first two rounds as well as the revealed cards. Using these updated probabilities, our player computes in real-time an equilibrium approximation for the last two abstracted rounds. We demonstrate that our player, which incorporates very little poker-specific knowledge, is competitive with leading poker-playing programs which incorporate extensive domain knowledge, as well as with advanced human players.

Software demonstrations

Andrew Gilpin, Tuomas Sandholm, and Troels Bjerre Sørensen. 2008. GS3 and Tartanian: Game theory-based heads-up limit and no-limit Texas Hold'em poker-playing programs. Seventh International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS'08), Estoril, Portugal. Demonstration Track. [view abstract]
We demonstrate two game theory-based programs for heads-up limit and no-limit Texas Hold'em poker. The first player, GS3, is designed for playing limit Texas Hold'em, in which all bets are a fixed amount. The second player, Tartanian, is designed for the no-limit variant of the game, in which the amount bet can be any amount up to the number of chips the player has. Both GS3 and Tartanian are based on our potential-aware automated abstraction algorithm for identifying strategically similar situations in order to decrease the size of the game tree. Tartanian, in order to deal with the virtually infinite strategy space of no-limit poker, in addition uses a discretized betting model designed to capture the most important strategic choices in the game. The strategies for both players are computed using our improved version of Nesterov's excessive gap technique specialized for poker.
In this demonstration, participants will be invited to play against both of the players, and to experience first-hand the sophisticated strategies employed by our players.
Andrew Gilpin and Tuomas Sandholm. 2006. A Texas Hold'em Poker player based on automated abstraction and real-time equilibrium computation. Fifth International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS'06), Hakodate, Japan. Demonstration Track. [view abstract]
We demonstrate our game theory-based Texas Hold'em poker player. To overcome the computational difficulties stemming from Texas Hold'em's gigantic game tree, our player uses automated abstraction and real-time equilibrium approximation. Our player solves the first two rounds of the game in a large off-line computation, and solves the last two rounds in a real-time equilibrium approximation. Participants in the demonstration will be able to compete against our opponent and experience first-hand the cognitive abilities of our player. Some of the techniques used by our player, which does not directly incorporate any poker-specific expert knowledge, include such poker techniques as bluffing, slow-playing, check-raising, and semi-bluffing, all techniques normally associated with human play.
Andrew Gilpin and Tuomas Sandholm. 2005. Optimal Rhode Island Hold'em Poker. 20th National Conference on Artificial Intelligence (AAAI'05), pp. 1684-1685, Pittsburgh, PA, 2005. Intelligent Systems Demonstration. [view abstract]
Rhode Island Hold'em is a poker card game that has been proposed as a testbed for AI research. This game features many characteristics present in full-scale poker (e.g., Texas Hold'em). Our research advances in equilibrium computation have enabled us to solve for the optimal (equilibrium) strategies for this game. Some features of the equilibrium include poker techniques such as bluffing, slow-playing, check-raising, and semi-bluffing. In this demonstration, participants will compete with our optimal opponent and will experience these strategies firsthand.
- Play against the optimal Rhode Island Hold'em Poker player

Auctions and exchanges

Tuomas Sandholm and Andrew Gilpin. 2006. Sequences of Take-It-or-Leave-It Offers: Near-Optimal Auctions Without Full Valuation Revelation. Fifth International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS'06), Hakodate, Japan. [view abstract]
We introduce take-it-or-leave-it auctions (TLAs) as an allocation mechanism that allows buyers to retain much of their private valuation information, yet generates close-to-optimal expected utility for the seller. We show that if each buyer receives at most one offer, each buyer's dominant strategy is to act truthfully. In more general TLAs, the buyers' optimal strategies are more intricate, and we derive the perfect Bayesian equilibrium for the game. We develop algorithms for finding the equilibrium and also for optimizing the offers so as to maximize the seller's expected utility. In several example settings we show that the seller's expected utility already is close to optimal for a small number of offers. As the number of buyers increases, the seller's expected utility increases, and becomes increasingly (but not monotonically) more competitive with Myerson's expected utility maximizing auction.
- Early version: AAMAS'03 5th Workshop on Agent Mediated Electronic Commerce (AMEC-V), Melbourne, Australia, 2003.
Andrew Gilpin and Tuomas Sandholm. 2004. Arbitrage in Combinatorial Exchanges. AAMAS'04 6th Workshop on Agent Mediated Electronic Commerce (AMEC-VI), New York, NY, 2004. [view abstract]
Combinatorial exchanges are trading mechanisms that allow agents to specify preferences over bundles of goods. When agents' preferences exhibit complementarity and/or substitutability, this additional expressiveness can lead to more efficient allocations than is possible using traditional exchanges. In the context of combinatorial exchanges, this paper examines arbitrage, a risk-free profit opportunity. We show that some combinatorial exchanges allow agents to perform arbitrage and thus extract a positive payment from the market while contributing nothing, something that is not possible in traditional exchanges (using a single trade). We analyze the extent to which arbitrage is possible and computationally feasible in combinatorial exchanges. We show that the surplus-maximizing combinatorial exchange with free disposal is resistant to arbitrage, but without free disposal arbitrage is possible. For unit-volume-maximizing and trade-volume-maximizing combinatorial exchanges, we show that arbitrage is sometimes possible and we propose an improved combinatorial exchange that achieves the same economic objective but eliminates a particularly undesirable form of arbitrage. We show that the computational complexity of detecting winning arbitraging bids is NP-complete and that the ability for an agent to submit arbitraging bids depends on the type of feedback in the exchange. We also show that a variant of combinatorial exchanges in which arbitrage is impossible becomes susceptible to arbitrage if certain side constraints are placed on the allocation or if an approximating clearing algorithm is used.

Winner determination and search

Andrew Gilpin and Tuomas Sandholm. 2007. Information-theoretic approaches to branching in search. International Joint Conference on Artificial Intelligence (IJCAI'07), Hyderabad, India. [view abstract]
Deciding what question to branch on at each node is a key element of search algorithms. We introduce the information-theoretic paradigm for branching question selection. The idea is to drive the search to reduce uncertainty (entropy) in the current subproblem. We present four families of methods that fall within this paradigm. In the first, a variable to branch on is selected based on lookahead. This method performs comparably to strong branching on MIPLIB, and better than strong branching on hard real-world procurement optimization instances on which CPLEX.s default strong branching outperforms CPLEX.s default branching strategy. The second family combines this idea with strong branching. The third family does not use lookahead, but instead exploits the tie between indicator variables and the other variables they govern. This significantly outperforms the state-of-the-art branching strategies. The fourth family is about branching using carefully constructed linear inequality constraints over sets of variables.
- Early version: AAMAS'06, Hakodate, Japan.
Tuomas Sandholm, Subhash Suri, Andrew Gilpin, and David Levine. 2005. CABOB: A Fast Optimal Algorithm for Winner Determination in Combinatorial Auctions. Management Science, Special Issue on Electronic Markets, 51(3):374--390. [view abstract]
Combinatorial auctions where bidders can bid on bundles of items can lead to more economically efficient allocations, but determining the winners is NP-complete and inapproximable. We present CABOB, a sophisticated optimal search algorithm for the problem. It uses decomposition techniques, upper and lower bounding (also across components), elaborate and dynamically chosen bid ordering heuristics, and a host of structural observations. CABOB attempts to capture structure in any instance without making assumptions about the instance distribution. Experiments against the fastest prior algorithm, CPLEX 8.0, show that CABOB is often faster, seldom drastically slower, and in many cases drastically faster---especially in cases with structure. CABOB's search runs in linear space and has significantly better anytime performance than CPLEX.
We also uncover interesting aspects of the problem itself. First, problems with short bids--that were hard for the first-generation of specialized algorithms--are easy. Second, almost all of the CATS distributions are easy, and the run-time is virtually unaffected by the number of goods. Third, we test several random restart strategies, showing that they do not help on this problem--the run-time distribution does not have a heavy tail.
- Early version: International Joint Conference on Artificial Intelligence (IJCAI'01), Seattle, WA, 2001.
Tuomas Sandholm, Subhash Suri, Andrew Gilpin, and David Levine. 2002. Winner Determination in Combinatorial Auction Generalizations. First International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS'02), pp. 69-76, Bologna, Italy. [view abstract]
Combinatorial markets where bids can be submitted on bundles of items can be economically desirable coordination mechanisms in multiagent systems where the items exhibit complementarity and substitutability. There has been a surge of research on winner determination in combinatorial auctions. In this paper we study a wider range of combinatorial market designs: auctions, reverse auctions, and exchanges, with one or multiple units of each item, with and without free disposal. We rst theoretically characterize the complexity of nding a feasible, approximate, or optimal solution. Reverse auctions with free disposal can be approximated (even in the multi-unit case), although auctions cannot. When XOR-constraints between bids are allowed (to express substitutability), the hardness turns the other way around: even nding a feasible solution for a reverse auction or exchanges is NP-complete, while in auctions that is trivial. Finally, in all of the cases without free disposal, even nding a feasible solution is NP-complete.
We then ran experiments on known benchmarks as well as ones which we introduced, to study the complexity of the market variants in practice. Cases with free disposal tended to be easier than ones without. On many distributions, reverse auctions with free disposal were easier than auctions with free disposal|as the approximability would suggest|but interestingly, on one of the most realistic distributions they were harder. Single-unit exchanges were easy, but multi-unit exchanges were extremely hard.
- Early version: AGENTS'01 Workshop on Agent-based Approaches to B2B, pp. 35-41, Montreal, Canada, May 28th, 2001.

Research

Selected publications:

Selected media appearances

Misc