Complexity and Algorithms of K-implementation

This paper settles the complexity of K-implementation, a ten-year open problem in AI. The problem is for a designer to modify an existing normal-form game, in a cost-optimal way, so as to ensure the solutions of the modified game fall into a given set of outcomes. We first prove that the problem is NP-complete for general games with respect to dominance by pure strategies, and then provide an alternative proof showing that the problem is NP-complete even for twoplayer games with respect to dominance by mixed strategies. We then consider a related but different objective, show its hardness and develop computationally efficient algorithms for a class of well-known games called supermodular games. For this objective, we are able to provide an optimal algorithm based on mixed-integer linear program. Interestingly, this algorithm also provides a lower-bound approximation guarantee for the original K-implementation problem and approximates the optimal solution well in experiments.