In this line of work, we study the problem of computing a Nash equilibrium in large-scale two-player zero-sum extensive-form games. While this problem can be solved in polynomial time, first-order or regret-based methods are usually preferred for large games. Regret-based methods have largely been favored in practice, in spite of their inferior convergence rates. We investigate the acceleration of first-order methods both theoretically and experimentally. An important component of many first-order methods is a distance-generating function. Motivated by this, we investigate a specific distance-generating function, namely the dilated entropy function, over treeplexes, which are convex polytopes that encompass the strategy spaces of perfect-recall extensive-form games. We develop significantly stronger bounds on the associated strong convexity parameter. In terms of extensive-form game solving, this significantly improves the convergence rate of several first-order methods. Experimentally, we investigate the performance of three first-order methods (the excessive gap technique, mirror prox, and stochastic mirror prox) and compare their performance to the regret-based algorithms. In order to instantiate stochastic mirror prox, we develop a class of gradient sampling schemes for game trees. Equipped with our distance-generating function and sampling scheme, we find that mirror prox and the excessive gap technique outperform the prior regret-based methods for finding medium accuracy solution. Read more about this work here.
Extensive-form games are a broad class of games that can be used to model many strategic scenarios. For two-player, zero-sum games, polynomial time algorithms are known for computing Nash equilibria. However, even in these games with polynomial time algorithms, practical problems are often so large that they don't even fit in memory. Thus, abstraction has emerged as a key component in solving large-scale extensive-form games. Lossless abstraction is preferred, but often, even these are too large to solve, so lossy abstraction is needed. In this work, we are developing the first theoretical framework that can give bounds on solution quality when equilibria computed in the abstract game are implemented in the original game. Read more about this work here (perfect-recall games) and here (imperfect-recall games).
Some practical games have continuous action spaces, while equilibrium-finding algorithms usually require a finite discrete game. Using the theoretical results from my EC14 paper, we have developed a framework for obtaining bounds on solution quality when discretizing extensive-form games with continuous action spaces. Read more about this here
Revenue maximization in combinatorial auctions (and other multidimensional selling settings) is an important and elusive problem. The optimal design is unknown, and is known to include features that are not acceptable in many applications, such as favoring some bidders over others and randomization. In our work, we study practical revenue maximization techniques, that avoid these features. In our initial work, we studied the technique of bundling in the context of Vickrey-Clarke-Groves (VCG) mechanisms. We showed that computing the optimal bundling is NP-hard, even for a setting where computing the social welfare maximizing allocation is trivial. We then developed a custom branch-and-bound algorithm for computing the optimal bundling. This involved introducing several techniques for branching, upper bounding, and lower bounding intermediate solutions. Read more about this work here.
Efficient containerized shipping is essential for the global economy, and relies on high-quality stowage plans that maximize cargo yield while reducing sailing speed and port fees by minimizing port stays. In this work, we investigated how to apply tools from artificial intelligence and optimization to two problems in this realm.
In one line of work, we developed three different optimization approaches for computing optimal or near-optimal shipping network redesigns when new routes are introduced in a global shipping network. Read more about this in our ICAPS 2012 paper.
In a second line of work, we investigated how to apply SAT, SMT, and BDD-based solvers to interactive stowage configuration. In practical stowage planning, unforeseen constraints often arise. In such cases, stowage planners manually redesign the stowage plan. In this work, we developed tools to help guide the stowage planner towards optimal solutions, by only ever presenting the user with valid steps in the stowage redesign process. In order to do this, we must solve a series of hard combinatorial configuration problems. A GUI prototype is shown to the right. A journal article based on this work was recently accepted for publication in Computational Intelligence. You can also read more about it in my Master's thesis.
One interesting observation from our stowage redesign work, was that BDD-based solving performed much better than SAT-based solving. This is contrary to much work in the very similar realm of verification, where SAT-based solving has reigned supreme in recent years. We hypothesize that this is because we solve a series of configuration problems, that all differ by a small amount. This is somewhat akin to taking a random walk around the space of the original SAT instance, making small tweaks to the formula. In our experiments, we saw that the SAT-based approach was almost always much faster than the BDD-based approach for any single instance. But across the many different perturbations of the problem (representing iteratively assigning containers), the SAT solver would eventually encounter an instance it timed out on. This begs the more general question of whether such behavior can be oberved across other types of combinatorial problems. If this problem stokes your interest, I would be happy to hear from you, and discuss a possible joint investigation. My Master's thesis contains a fairly comprehensive investigation of this issue for container stowage.