Learning Tree Structured Potential Games
Many real phenomena, including behaviors, involve strategic interactions that can be learned from data. We focus on learning tree structured potential games where equilibria are represented by local maxima of an underlying potential function. We cast the learning problem within a max margin setting and show that the problem is NP-hard even when the strategic interactions form a tree. We develop a variant of dual decomposition to estimate the underlying game and demonstrate with synthetic and real decision/voting data that the game theoretic perspective (carving out local maxima) enables meaningful recovery.
This paper introduces a max margin framework for learning potential games where the underlying interactions have a tree structure. A hardness result is presented first, followed by a dual decomposition algorithm for learning the tree structure and parameters of the game. Lastly, experimental results on synthetic and real datasets show that the algorithm recovers reasonable results.
I like the underlying idea of this paper, that of applying max margin learning to potential games. This works well with viewing observed behavior as local equilibria of the potential function. However, I have a couple serious concerns about the execution and technical content.  My major concern is that the paper very quickly glosses over the issue of learning N_i, the set of neighbors of each node. This appears to be the key part of the inference: as the authors point out, finding the optimal parameters with the tree structure fixed is just a quadratic program. It is claimed that special properties like submodularity could be used, but no such cases are explored in the paper. This leaves brute force, which is clearly not sufficient to tackle realistically sized problems. Also, it is never mentioned which method is used in the experiments.   Next, it would be helpful to see more detailed experiments. The synthetic and real datasets are good for illustrating that the algorithm is on some level reasonable, but two dimensions are somewhat lacking. First, all of the datasets considered are very small (and no runtime results are shown). So, it's hard to know how the algorithm scales, or whether it gives good results outside of small, clearly structured examples. Second, there is no comparison to other techniques for learning games. I'm not able to give a comprehensive list of recommendations, but a couple of papers which tackle similar problems are  Quang Duong, Yevgeniy Vorobeychik, Satinder Singh, Michael P. Wellman. "Learning Graphical Game Models". IJCAI 2009.  Jean Honorio, Luis Ortiz. "Learning the Structure and Parameters of Large-Population Graphical Games from Behavioral Data". UAI 2012.   Some comparison to alternative ways of learning graphical games would be serve to validate the overall max margin approach.  A few smaller issues:  1) It's not clear where the assumed tree structure makes the inference easier. I assume that it simplifies learning the parameters, but this should be explicitly discussed somewhere.  2) The meaning of the "context" is not clear. What was the context in the two real world datasets?  3) In the equation just before line 59, "y" is undefined.  4) In the Lagrangian (just after line 118), is delta_ij the Kronecker delta? If so, isn't the summation identically zero?