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