Several Combinatorial Optimization Algorithm Countermeasures Model

Cooperative game theory considers how to distribute income v(N) generatedby a group N to its members. There are several solution concepts with respectto di?erent rationality, such as core , nucleolus, etc. In this thesis, we focus ourdiscussion on the ?ow games, introduced by Kalai and Zemel (1982). We discussthe core stability of a ?ow game and study the algorithmic issues of finding thenucleolus of a ?ow game. We obtain the following results:? Based on the characterization of dummy arc (i.e., the arc which satisfiesthat deleting it does not change the value of maximum ?ow in the network), weprove that the ?ow game defined on a simple network has the stable core if andonly if there is no dummy arc in the network.? We show that in the ?ow game defined on a simple network, the core large-ness, the extendability and the exactness of ?ow games are equivalent conditions,which strictly imply the stability of the core.? We show that the nucleolus of the ?ow game defined on a simple networkcan be computed in polynomial time by a linear program duality approach.? We prove that the computation of the nucleolus is NP-hard for ?ow gameswith general capacity.In the last part of this thesis, we consider a decision-making model with lin-ear constraint. First, we give a su?cient and necessary condition of the existenceof Nash equilibria by applying linear programming and dual theory, which followsa polynomial time algorithm to find Nash equilibria. Second, based on the analy-sis of Nash equilibria, we introduce two concepts of strong equilibria, payo?-proofNash equilibria , and further discuss their characterization and existance.