N-person game playing and artificial intelligence.

Game playing in artificial intelligence (AI) has produced effective algorithms enabling a computer to play two-person, non-cooperative, zero-sum and perfect information games such as checkers and chess. Game theory suggests solution sets for games, but does not shed much light on how to make moves in a game. This dissertation couples AI with game theory and determines ways for a computer to play multi-player games. The max$\\sp{\\rm n}$ algorithm is defined and analyzed for playing non-cooperative, n-person games. The max$\\sp{\\rm n}$ procedure finds an equilibrium point for a game and allows some pruning of calculated payoff values but not pruning of subtrees. An evaluation for representing a cooperative game is defined using the max$\\sp{\\rm n}$ procedure on all possible coalitions. This evaluation is used along with an earnings function in order to define the stability of a coalition and coalition structure. Finally, a solution algorithm is developed that is based on coalition stability for a computer to use in playing cooperative n-person games using look ahead, heuristic evaluation function, and back-up techniques. The solution algorithm gives a result that is sometimes in game-theoretic solution sets such as the core, stable set, kernel, and bargaining set. Potential applications for this work are in AI, conflict resolution, economics, mathematics, and social psychology.Ph.D.Computer scienceMathematicsArtificial intelligenceUniversity of Michiganhttp://deepblue.lib.umich.edu/bitstream/2027.42/162493/1/9013963.pd