Integer Programming Approach To Computing Nash Equilibrium In Normal Form And Distributed Implementation Of Fixed-Point Method

A primary concern in applications of game theory is how to effectively select a Nash equilibrium, especially, a Nash equilibrium for a finite n-person game in normal form. This selection process often requires the computation of all Nash equilibria. It is well known that determining whether a finite game has a Nash equilibrium is an NP-hard problem and it is difficult to solve by naive enumeration algorithm. By exploiting the properties of pure strategy and multilinear terms in the payoff functions, this thesis begins by formulating a new mixed0-1linear program for computing all pure-strategy Nash equilibrium of finite n-person game in normal form. To our knowledge, it is the first method to formulate a mixed0-1linear programming for pure-strategy Nash equilibria and it may work well for other similar problems. Numerical results show that the approach is effective and this method can be easily distributed. For the mixed-strategy Nash equilibrium of a finite n-person game in normal form, multilinear terms appears in the payoff functions too. However, it is more difficult than the pure-strategy problem since the variables are0or1in pure-strategy cases and0to1in mixed-strategy cases. A good approximation of multilinear terms is introduced to fix this problem. Based on this approximation and the properties of mixed-strategy Nash equilibria, a mixed integer linear programming is obtained to find all mixed-strategy Nash equilibria of a finite n-person game in normal form.In order to solve the integer programming effectively, a distributed implemen-tation of Dang and Ye’s distributed fixed-point iterative method, which is a new al-ternative algorithm for integer programming, is also developed in this thesis. This fixed-point algorithm is derived from an increasing mapping which satisfies certain properties. Three classical problems, the problem of finding the pure-strategy Nash equilibria, the market split problem and the knapsack feasibility problem, are solved by this distributed implementation which is demonstrated by numerical results to be effective, with the potential for extension to other integer problems.