Algorithms and Existence Theorems for Cooperative and Dynamic Games

合作和动态博弈的算法和存在定理

• 批准号: 0072678
• 负责人: T.E.S. Raghavan
• 金额: $ 9万
• 依托单位: University of Illinois at Chicago
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2000
• 资助国家: 美国
• 起止时间: 2000-08-15 至 2005-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0072678&HistoricalAwards=false
• 关键词: Algorithms; Existence; Theorems; Cooperative; Dynamic

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.

合作与动态博弈的定理与算法。Raghavan，伊利诺伊大学芝加哥分校合作博弈论中的建议的主要问题之一是找到有效的算法来解决组合TU游戏的核仁，基于分配和区间游戏的成功算法。 第二个问题是研究具有稳定核心的博弈。特别是研究分配博弈等组合博弈的核心稳定性。在联盟谈判中，我们将寻找完全信息博弈的子博弈完美静态纳什均衡，其支付近似于核仁支付。 在动态博弈领域，我们想扩展的政策改进算法的完全信息的无折扣随机博弈。我们将把逃税行为建立为动态博弈模型，并研究其均衡。上述合作博弈中的问题是由以下问题物理驱动的。联邦和州政府承担昂贵的建设设施，如桥梁，高速公路，供水和下水道管道，铁路和机场。 经常 政府所面对的关键决定，是如何将总成本公平地分配给使用者。 待开发的算法将有助于在适当地将问题建模为合作博弈之后达到这种公平的成本。 税务局里堆满了纳税申报单;工业公司里堆满了付款批准凭证;汽车制造商们收到了大量的汽车零部件，以便迅速验收。审计员的数量很少，无法审计所有的纳税申报表;会计师的数量很少，无法检查所有的凭证;实验室和人力有限，无法测试所有有缺陷的项目。 人们可以将纳税申报表或凭证或供应商分为不同的类别，并决定纳税申报表或凭证中的哪些项目需要审计;样品中有多少百分比的缺陷项目需要验收或更多的测试。根据审计或连续抽样的结果，人们可以就审计特定类别违规者的未来回报和凭证的频率做出新的决定。 在污染环境方面，违法者往往是大制造商。如果污染物是不同的，那么污染者是可以识别的，清洁的成本可以分散。如果污染物属于几种类型，那么人们就可以大致知道哪些污染物可能造成了哪种类型。违反行为的程度需要进行零星或系统的检查。 在某种程度上，总成本必须通过适当的税收政策来收取，而税收政策可能会根据污染程度而有所不同。对于一个普通的家庭业主下水道收费只是绑在水的使用。 当污染者感到困惑时，必须通过不时派遣检查员来确定污染者，对环境违法行为进行抽查，并通过各种处罚来惩罚违法者。 在这样的问题中，要开发的算法将显示出达到成本数字或检查策略的正式方式，这些方式既直观又科学。