Algorithms and Existence Theorems for Cooperative and Dynamic Games

合作博弈和动态博弈的定理和算法：T.E.S.Raghavan，芝加哥伊利诺伊大学合作博弈理论建议的主要问题之一是在分配和区间博弈的成功算法的基础上，找到求解组合TU博弈的核仁的有效算法。第二个问题是研究具有稳定核心的博弈。特别是研究指派对策等组合对策的核心稳定性。在联盟讨价还价中，我们将寻找完全信息博弈的子博弈完美平稳纳什均衡，其收益近似于核仁收益。在动态对策方面，我们推广了完全信息非折扣随机对策的策略改进算法。我们将逃税模型描述为动态博弈，并研究它们的均衡。上述合作博弈中的问题是由以下问题引起的。联邦和州政府承担昂贵的建设设施，如桥梁、高速公路、给水和下水道管道、铁路和机场。通常，政府面临的关键决策是以公平的方式在用户之间分配总成本。待开发的算法将有助于在对合作博弈等问题进行适当建模后，达到这样的公平成本。税务办公室里充斥着纳税申报单；工业企业里充斥着付款审批的凭证；汽车制造商得到了大量汽车零部件的寄售，以便快速验收。审计人员很少，审计所有的纳税申报单的人很少；会计师很少，检查所有的凭证；实验室和人力有限，只能测试所有有缺陷的项目。人们可以将纳税申报单或凭单或供应商分类，并决定对纳税申报单或凭单中的哪些项目进行审计；样本中有多大比例的不合格项目需要接受或进行更多测试。根据审计或顺序抽样的结果，人们可以就应该多久审计一次特定类别违规者的未来申报单和凭证做出新的决定。在污染环境方面，违规者往往是大制造商。如果污染物是不同的，那么污染者就是一些可以识别的，清洁成本可以分散。如果污染物属于几种类型，那么人们就大致知道哪些污染者群体可能对哪种类型的污染做出了贡献。违规的程度将需要零星或系统的检查。在某种程度上，总成本必须通过适当的征税政策来收取，这些政策可能会根据污染程度的不同而有所不同。对于普通的家庭业主来说，下水道费用只是与用水量挂钩。当污染者感到困惑时，人们不得不不时派出检查员来确定污染者，抽查违反环境的行为，并对违规者进行各种处罚。在这类问题中，将要开发的算法将显示得出成本数字或检查策略的正式方法，这些方法既直观又科学地加以预防。

Theorems and algorithms for Cooperative and Dynamic Games:T.E.S. Raghavan, University of Illinois at ChicagoOne 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.