Algorithms and Existence Theorems for Cooperative and Dynamic Games

University Of Illinois At Chicago, Chicago IL

Investigators

Abstract

Theorems and algorithms for Cooperative and Dynamic Games: T.E.S. Raghavan, University of Illinois at Chicago One of the main problems of the proposal in cooperative game theory is to find efficient algorithms to solve for the nucleolus of combinatorial TU games, based on the successful algorithms for assignment and interval games. A second problem is to study games with stable cores. In particular to study core stability for combinatorial games such as assignment games. In coalitional bargaining we will look for subgame perfect stationary Nash equilibria of perfect information games which approximate in its payoff the nucleolus payoff. In the area of dynamic games, we would like to extend the policy improvement algorithm for undiscounted stochastic games of perfect information. We would formulate models of tax evasion as dynamic games and study their equilibria. The problems in cooperative games posed above are physically motivated by the following questions. Federal and state governments undertake costly construction facilities like bridges, freeways, water and sewer pipes, railroads and airports. Often the critical decision facing the government is to distribute the total cost among the users in an equitable way. The algorithms to be developed will help to arrive at such equitable costs after properly modeling the problems as cooperative games. Tax offices are flooded with tax returns; Indutrial corporations are flooded with vouchers for payment approval; automobile manufacturers are supplied with large consignment of automobile parts for quick acceptance. Auditors are few in number to audit all tax returns; accountants are few to check all vouchers; laborataries and manpower are limited to test for all defective items. One can classify the tax returns or vouchers or suppliers into various categories and make decisions on which items in the tax return or voucher to audit; what percent of defective items in a sample require acceptance or more testing. Depending on the outcome of auditing, or sequential sampling one can make new decisions on how frequently one should audit the future returns and vouchers from the specific class of violators. In polluting the environment, the violators are often big manufacturers. If the pollutants are distinct, then polluters are some what identifiable and the cost of cleaning can be decentralized. If the pollutants are of a few type, then one knows roughly which groups of polluters could have contributed to which type. The levels of violation would require sporadic or systematic inspection. In a way the total cost has to be collected by suitable taxing policies that could vary depending on the levels of pollution. For an ordinary home owner sewer charges are simply tied to the water usage. When the polluters are confounded one has to identify polluters by sending inspectors now and then to make spot check for environmental violations and punish violators by various penalties. In such problems the algorithms to be developed will show the formal ways of arriving at cost figures or inspection strategies that are both intuitively and scientifically defendable.