A mixed-integer programming approach to the determination of proper equilibria

Abstract

The basic noncooperative concept of the Nash equilibrium suffers from severe drawbacks, that have aroused increasing concern from game theorists. As a consequence, a multitude of alternative solution concepts and refinements have been introduced to alleviate the Nash equilibrium's deficiencies. However, even though some of these refinements and solution concepts perform better than the Nash equilibrium, they are rarely used in practice due to a lack of analytical and numerical tools. Therefore, an endeavor will be made in this thesis towards the determinations of some the notable equilibrium concepts. As a strict refinement of the Nash equilibrium concept, Myerson's proper equilibrium plays a prominent role among these refinements. Chapters 3 and 4 develop effective algorithms to identify the proper equilibria of games in normal form. A mixed-integer linear program is constructed to directly derive proper equilibria based on definitions. The advantage of this formulation is that it allows a particular proper equilibrium to be selected over the equilibria space, and minimizes the effect of computational instability on the precision of the underlying solver. In Chapter 4, this approach is generalized to the determine the proper equilibria of three-player games in normal form. The practical mixed-integer quadratic programming approach proposed by Belhaiza (2012) for obtaining several proper equilibria for a bimatrix game is improved by introducing a piece-wise approximation to transform a mixed-integer quadratic program into a mixed-integer linear program, alleviating the computation burden. The existence of proper equilibria as solutions to the programs is guaranteed. Analytical and numerical results showing the effectiveness for this mixed-integer linear programming approach for the determination of proper equilibria of games in normal form are presented. The exponentially small e in the size of the game, from the definition of a proper equilibrium, causes a deficiency. In response, Dang (2013) proposed the concept of perfect d-proper equilibrium to simplify the computation of proper equilibria and maintain the desirable elimination of unreasonable perfect equilibria. A mixed-integer programming approach using this refinement is formulated in Chapters 5 and 6. The effectiveness of the approach is shown in numerical experiments. A set of solution concepts for boundedly rational players other than the Nash equilibrium are provided in the literature on quantal response equilibria. Rosenthal's (1989) t-solutions concern the degree of limitation of the rationality of each player and has attracted some attention. Due to the strong link between the quantal response equilibrium and experimental data, predicting the effects of different experimental treatments depends on the determination of the concepts under a quantal response equilibrium. Chapter 7 focuses on numerically obtaining the subsequence of the path of t-solutions using a mixed-integer program.

Date of Award	3 Oct 2014
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Chuangyin DANG (Supervisor)