Raghavan DMS 9704951 Cooperative Games NSF Abstract The proposal addresses algorithmic problems of cooperative and noncooperative dynamic games. Cooperative Games: How should the common costs be allocated fairly among the benefeciaries of a joint enterprise is a basic problem widespread in both private firms and in public enterprises. While cost accountants and practitioners have stuck to a few cost allocation practises , these procedures are being questioned by researchers especially by game theorists who would like the procedures to be fair, equitable and reflective of the decision makers power and influence in steering the course of actions. Cooperative game theory addresses precisely these issues. Till recently game theorists have been proposing many solutions without any efficient solution technique to solve for them. Often many practical cost allocation problems and profit sharing problems can be modeled as games whose essential coalitions grow only polynomially with he size of the player set. The project is aimed at developing efficient algorithms that will solve for the nucleolus and the Shapley value for many models. Stochastic games: In the area of stochastic games the aim is to study non-zero sum games in limiting average payoffs for finite and arbitrary state spaces and to look for correlated and Nash equilibria. Unlike zero-sum games, non-zero sum structured stochastic games may not possess even epsilon -stationary Nash equilibria in limiting average payoff. Even more important is to develop allgorithms to locate Nash equilibria, at least for structured stochastic games. Increasingly industries and organizations and even federal funding agencies want to measure the contributions of joint efforts. In environmental problems accurately allocating costs or fines for industrial pollutions will be possible with cooperative game theoretic solutions. In civil law suits and in divorce law suits, the ad hoc but intuitively appealing decisions by judges based on the individual cases can be backed up by quantifiable approaches using cooperative game theoretic solutions. The strategic behavior of price wars by airlines, the tax evasion and auditing by tax offices, auto manufacturing competitions can all be analyzed using stochastic game theoretic methods and models. The solutions backed up by efficient algorithms for computation is essential for the applicability of Game Theory to real life problems.
