Cost and complexity of harnessing games with payments (Q2907961)

The paper addresses the question of how to implement a strategy in a multi-player game to ensure the desired outcome at minimal cost. The underlying mathematical structure consists of a finite set of players, their strategies and payoff functions. The authors introduce formal notions of the (exact) worst-case and uniform implementation cost of a strategy profile. The uniform setting serves to model the case where the players only have partial knowledge and play with mixed strategies. Furthermore, the authors introduce various notions of the leverage (worst-case, malicious, uniform and malicious uniform). Intuitively, the purpose of these formal notions of leverage is to analyze which outcomes are worth implementing when taking the implementation cost into account.NEWLINENEWLINEThe paper first presents an algorithm for minimizing the worst-case implementation cost and provides arguments for the conjecture that the problem of finding optimal implementations is NP-hard. NP-hardness results are established for the uniform game model where non-dominated strategy profiles are played with equal probability. These results as well as a lower bound for the best approximation ratio of polynomial-time algorithms are obtained by reductions from SET COVER.NEWLINENEWLINEFor the leverage, the authors first address the problem of implementing a strategy profile with the best singleton leverage, and the dual problem where a malicious designer attempts to maximize the malicious leverage. For this problem and games where each player has two or more strategies a polynomially time-bounded algorithm is presented. For the general leverage problem, the authors propose an algorithm that computes a rectangular strategy profile set's exact leverage. For uniform models, the implementation cost are shown to be derivable from the leverage in polynomial time. This yields the NP-hardness of the leverage problem in uniform models. Furthermore, the authors show the impossibility of polynomially time-bounded approximation algorithms for the uniform leverage, unless P equals NP.