Finding a Nash equilibrium in spatial games is an NP-complete problem

Summary. We consider the class of (finite) spatial games. We show that the problem of determining whether there exists a Nash equilibrium in which each player has a payoff of at least k is NP-complete as a function of the number of players.Received: 15 September 2002, Revised: 9 March 2003, JEL Classification Numbers: C72.Correspondence to: H. HallerWe thank a referee for helpful comments. The hospitality of the Institute of Economics, University of Copenhagen, and the Institute for Advanced Studies, Vienna, is gratefully acknowledged by the third author.     

Trees and decisions

Summary. The traditional model of sequential decision making, for instance, in extensive form games, is a tree. Most texts define a tree as a connected directed graph without loops and a distinguished node, called the root. But an abstract graph is not a domain for decision theory. Decision theory perceives of acts as functions from states to consequences. Sequential decisions, accordingly, get conceptualized by mappings from sets of states to sets of consequences. Thus, the question arises whether a natural definition of a tree can be given, where nodes are sets of states. We show that, indeed, trees can be defined as specific collections of sets. Without loss of generality the elements of these sets can be interpreted as representing plays. Therefore, the elements can serve as states and consequences at the same time.Received: 23 January 2003, Revised: 2 November 2003, JEL Classification Numbers: C72, D70. Correspondence to: Klaus RitzbergerWe are grateful to Larry Blume, Ariel Rubinstein, Jörgen Weibull, an anonymous referee, and seminar participants at the universities of Vienna, Salamanca, and Heidelberg for helpful comments. Financial support from the Austrian Science Fund (FWF) under project P15281 is also gratefully acknowledged.     

Absorbing Team Games

A team is a group of people having the same motives but possibly different available actions. A team game is a game where two teams face each other. An absorbing game is a repeated game where some of the entries are absorbing, in the sense that once they are chosen the play terminates, and all future payoffs are equal to the payoff at the stage of termination. We prove that every absorbing team game has an equilibrium payoff and that there are -equilibrium profiles with cyclic structure. Journal of Economic Literature Classification Numbers: C72, C73.     

Extensive-form games and strategic complementarities

I prove the subgame-perfect equivalent of the basic result for Nash equilibria in normal-form games of strategic complements: the set of subgame-perfect equilibria is a nonempty, complete lattice—in particular, subgame-perfect Nash equilibria exist. For this purpose I introduce a device that allows the study of the set of subgame-perfect equilibria as the set of fixed points of a correspondence. My results are limited because extensive-form games of strategic complementarities turn out—surprisingly—to be a very restrictive class of games.     

Communication equilibrium payoffs in repeated games with imperfect monitoring

We characterize the set of communication equilibrium payoffs of any undiscounted repeated matrix-game with imperfect monitoring and complete information. For two-player games, a characterization is provided by Mertens, Sorin, and Zamir (Repeated games, Part A (1994) CORE DP 9420), mainly using Lehrer's (Math. Operations Res. (1992) 175) result for correlated equilibria. The main result of this paper is to extend this characterization to the n-player case. The proof of the characterization relies on an analogy with an auxiliary 2-player repeated game with incomplete information and imperfect monitoring. We use Kohlberg's (Int. J. Game Theory (1975) 7) result to construct explicitly a canonical communication device for each communication equilibrium payoff.     

制度、人力资本与乡村劳动力迁移

本文构建制度框架下政府与乡村迁移者博弈模型说明政府政策选择机制形成与迁移者决策过程。在不同经济发展阶段,经济发展目标决定迁移者迁移策略,城市发展能否从迁移中获得利益决定政府对迁移的管制程度,农业发展能否为迁移提供支持决定迁移者的迁移决策。迁移者的人力资本水平是影响政府策略与迁移者策略选择的关键因素。改善乡村劳动力人力资本积累条件有助于加速迁移进程,减少城市劳动力市场对迁移者的歧视,提高城市化质量。     

夏利与吉利的价格博弈论分析

以战略管理中的动态竞争思想为主线,利用博弈论工具对吉利汽车进入市场、通过与夏利进行价格战而占得一席之地这一互动过程进行了分析,从在位者角度指出了夏利汽车在战略上的不当之处,为企业进行战略决策提供参考。     

企业技术创新战略选择机制问题的研究

技术创新战略的选择对企业有着深远影响,甚至关系到企业的生存。如何建立有效的技术创新战略选择机制一直是困扰企业的难题。把企业技术创新战略选择机制的重点放在企业比较容易测度、使用的方法上来,对企业技术创新进行较为细致的风险估计、战略选择的博弈分析,并介绍了Logistic生长模型,为企业选择技术创新战略提供了便利的分析工具。     

人员工作分配的定量优化方法研究

近年来资源优化问题受到各方面的普遍关注,作为生产要素中最具有活力的人才资源也存在资源优化分配的问题。文章以残奥会工作人员的工作岗位科学分配为例,采用模糊数学方法进行数据处理,运用运筹学方法进行优化,取得了良好的效果,达到了科学优化、节约成本的目的,为组织决策者提供了一种可供参考的方法。     

SPATIAL DISCRIMINATION,PRODUCT SUBSTITUTABILITY AND WELFARE

The paper examines a quantity–location duopoly game in a spatial discrimination model in which the delivered goods are assumed to be imperfect substitutes or complements. By extending the range of the unit transportation cost analysed in the existing literature, it is shown that a dispersed equilibrium arises in which the choice of the optimal locations is affected by the degree of product substitutability. The interaction between the latter and the size of the transportation cost is also discussed in order to verify its welfare implications. In particular, it is shown that in this spatial framework imperfect substitutability may increase welfare.