On the Existence of Pure and Mixed Strategy Nash Equilibria in Discontinuous Games

A game is better-reply secure if for every nonequilibrium strategy x^* and every payoff vector limit u^* resulting from strategies approaching x^*, some player i has a strategy yielding a payoff strictly above u_i^* even if the others deviate slightly from x^*. If strategy spaces are compact and convex, payoffs are quasiconcave in the owner's strategy, and the game is better-reply secure, then a pure strategy Nash equilibrium exists. Better-reply security holds in many economic games. It also permits new results on the existence of symmetric and mixed strategy Nash equilibria.     

Competition for a Majority

We define the class of two‐player zero‐sum games with payoffs having mild discontinuities, which in applications typically stem from how ties are resolved. For such games, we establish sufficient conditions for existence of a value of the game, maximin and minimax strategies for the players, and a Nash equilibrium. If all discontinuities favor one player, then a value exists and that player has a maximin strategy. A property called payoff approachability implies existence of an equilibrium, and that the resulting value is invariant: games with the same payoffs at points of continuity have the same value and ɛ‐equilibria. For voting games in which two candidates propose policies and a candidate wins election if a weighted majority of voters prefer his proposed policy, we provide tie‐breaking rules and assumptions about voters' preferences sufficient to imply payoff approachability. These assumptions are satisfied by generic preferences if the dimension of the space of policies exceeds the number of voters; or with no dimensional restriction, if the electorate is sufficiently large. Each Colonel Blotto game is a special case in which each candidate allocates a resource among several constituencies and a candidate gets votes from those allocated more than his opponent offers; in this case, for simple‐majority rule we prove existence of an equilibrium with zero probability of ties.     

Tenable Strategy Blocks and Settled Equilibria

When people interact in familiar settings, social conventions usually develop so that people tend to disregard alternatives outside the convention. For rational players to usually restrict attention to a block of conventional strategies, no player should prefer to deviate from the block when others are likely to act conventionally and rationally inside the block. We explore two set‐valued concepts, coarsely and finely tenable blocks, that formalize this notion for finite normal‐form games. We then identify settled equilibria, which are Nash equilibria with support in minimal tenable blocks. For a generic class of normal‐form games, our coarse and fine concepts are equivalent, and yet they differ from standard solution concepts on open sets of games. We demonstrate the nature and power of the solutions by way of examples. Settled equilibria are closely related to persistent equilibria but are strictly more selective on an open set of games. With fine tenability, we obtain invariance under the insertion of a subgame with a unique totally mixed payoff‐equivalent equilibrium, a property that other related concepts have not satisfied.     

Identification and Estimation of a Discrete Game of Complete Information

We discuss the identification and estimation of discrete games of complete information. Following Bresnahan and Reiss (1990, 1991), a discrete game is a generalization of a standard discrete choice model where utility depends on the actions of other players. Using recent algorithms to compute all of the Nash equilibria to a game, we propose simulation‐based estimators for static, discrete games. We demonstrate that the model is identified under weak functional form assumptions using exclusion restrictions and an identification at infinity approach. Monte Carlo evidence demonstrates that the estimator can perform well in moderately sized samples. As an application, we study entry decisions by construction contractors to bid on highway projects in California. We find that an equilibrium is more likely to be observed if it maximizes joint profits, has a higher Nash product, uses mixed strategies, and is not Pareto dominated by another equilibrium.     

Complexity and Competition

Extensive‐form market games typically have a large number of noncompetitive equilibria. In this paper, we argue that the complexity of noncompetitive behavior provides a justification for competitive equilibrium in the sense that if rational agents have an aversion to complexity (at the margin), then maximizing behavior will result in simple behavioral rules and hence in a competitive outcome. For this purpose, we use a class of extensive‐form dynamic matching and bargaining games with a finite number of agents. In particular, we consider markets with heterogeneous buyers and sellers and deterministic, exogenous, sequential matching rules, although the results can be extended to other matching processes. If the complexity costs of implementing strategies enter players’ preferences lexicographically with the standard payoff, then every equilibrium strategy profile induces a competitive outcome.     

The Theory of Global Games on Test: Experimental Analysis of Coordination Games with Public and Private Information

The theory of global games has shown that coordination games with multiple equilibria may have a unique equilibrium if certain parameters of the payoff function are private information instead of common knowledge. We report the results of an experiment designed to test the predictions of this theory. Comparing sessions with common and private information, we observe only small differences in behavior. For common information, subjects coordinate on threshold strategies that deviate from the global game solution towards the payoff‐dominant equilibrium. For private information, thresholds are closer to the global game solution than for common information. Variations in the payoff function affect behavior as predicted by comparative statics of the global game solution. Predictability of coordination points is about the same for both information conditions.     

Repeated Games Where the Payoffs and Monitoring Structure Are Unknown

This paper studies repeated games with imperfect public monitoring where the players are uncertain both about the payoff functions and about the relationship between the distribution of signals and the actions played. We introduce the concept of perfect public ex post equilibrium (PPXE), and show that it can be characterized with an extension of the techniques used to study perfect public equilibria. We develop identifiability conditions that are sufficient for a folk theorem; these conditions imply that there are PPXE in which the payoffs are approximately the same as if the monitoring structure and payoff functions were known. Finally, we define perfect type‐contingently public ex post equilibria (PTXE), which allows players to condition their actions on their initial private information, and we provide its linear programming characterization.     

The Expected Number of Nash Equilibria of a Normal Form Game

Fix finite pure strategy sets _S1,…,_Sn , and let S=_S1×⋯×_Sn . In our model of a random game the agents' payoffs are statistically independent, with each agent's payoff uniformly distributed on the unit sphere in ℝ^S. For given nonempty _T1⊂_S1,…,_Tn⊂_Sn we give a computationally implementable formula for the mean number of Nash equilibria in which each agent i's mixed strategy has support T_i. The formula is the product of two expressions. The first is the expected number of totally mixed equilibria for the truncated game obtained by eliminating pure strategies outside the sets T_i. The second may be construed as the “probability” that such an equilibrium remains an equilibrium when the strategies in the sets _Si∖_Ti become available.     

The Democratic Political Economy of Progressive Income Taxation

Why do both left and right political parties typically propose progressive income taxation schemes in political competition? Analysis of this problem has been hindered by the two-dimensionality of the issue space. To give parties a choice over a domain that contains both progressive and regressive income tax policies requires an issue space that is at least two-dimensional. Nash equilibrium in pure strategies of the standard two-party game, whose players have complete preferences over a two-dimensional policy space, generically fails to exist. I introduce a new equilibrium concept for political games, based on the fact of factional conflict within parties. Each party is supposed to consist of reformists, militants, and opportunists: each faction has a complete preference order on policy space, but together they can only agree on a partial order. Nash equilibria of the two-party game, where the policy space consists of all quadratic income tax functions, and each party is represented by its partial order, exist, and it is shown that, in such equilibria, both parties propose progressive income taxation.     

Berk–Nash Equilibrium: A Framework for Modeling Agents With Misspecified Models

We develop an equilibrium framework that relaxes the standard assumption that people have a correctly specified view of their environment. Each player is characterized by a (possibly misspecified) subjective model, which describes the set of feasible beliefs over payoff‐relevant consequences as a function of actions. We introduce the notion of a Berk–Nash equilibrium: Each player follows a strategy that is optimal given her belief, and her belief is restricted to be the best fit among the set of beliefs she considers possible. The notion of best fit is formalized in terms of minimizing the Kullback–Leibler divergence, which is endogenous and depends on the equilibrium strategy profile. Standard solution concepts such as Nash equilibrium and self‐confirming equilibrium constitute special cases where players have correctly specified models. We provide a learning foundation for Berk–Nash equilibrium by extending and combining results from the statistics literature on misspecified learning and the economics literature on learning in games.     

Belief‐Free Equilibria in Games With Incomplete Information

We define belief‐free equilibria in two‐player games with incomplete information as sequential equilibria for which players' continuation strategies are best replies after every history, independently of their beliefs about the state of nature. We characterize a set of payoffs that includes all belief‐free equilibrium payoffs. Conversely, any payoff in the interior of this set is a belief‐free equilibrium payoff. The characterization is applied to the analysis of reputations.     

Stochastic Learning Dynamics and Speed of Convergence in Population Games

We study how long it takes for large populations of interacting agents to come close to Nash equilibrium when they adapt their behavior using a stochastic better reply dynamic. Prior work considers this question mainly for 2 × 2 games and potential games; here we characterize convergence times for general weakly acyclic games, including coordination games, dominance solvable games, games with strategic complementarities, potential games, and many others with applications in economics, biology, and distributed control. If players' better replies are governed by idiosyncratic shocks, the convergence time can grow exponentially in the population size; moreover, this is true even in games with very simple payoff structures. However, if their responses are sufficiently correlated due to aggregate shocks, the convergence time is greatly accelerated; in fact, it is bounded for all sufficiently large populations. We provide explicit bounds on the speed of convergence as a function of key structural parameters including the number of strategies, the length of the better reply paths, the extent to which players can influence the payoffs of others, and the desired degree of approximation to Nash equilibrium.     

On the performances of Nash equilibria in isolation games

We study the performances of Nash equilibria in isolation games, a class of competitive location games recently introduced in Zhao et al. (Proc. of the 19th International Symposium on Algorithms and Computation (ISAAC), pp. 148–159, 2008). For all the cases in which the existence of Nash equilibria has been shown, we give tight or asymptotically tight bounds on the prices of anarchy and stability under the two classical social functions mostly investigated in the scientific literature, namely, the minimum utility per player and the sum of the players’ utilities. Moreover, we prove that the convergence to Nash equilibria is not guaranteed in some of the not yet analyzed cases.     

Who's Who in Networks. Wanted: The Key Player

Finite population noncooperative games with linear‐quadratic utilities, where each player decides how much action she exerts, can be interpreted as a network game with local payoff complementarities, together with a globally uniform payoff substitutability component and an own‐concavity effect. For these games, the Nash equilibrium action of each player is proportional to her Bonacich centrality in the network of local complementarities, thus establishing a bridge with the sociology literature on social networks. This Bonacich–Nash linkage implies that aggregate equilibrium increases with network size and density. We then analyze a policy that consists of targeting the key player, that is, the player who, once removed, leads to the optimal change in aggregate activity. We provide a geometric characterization of the key player identified with an intercentrality measure, which takes into account both a player's centrality and her contribution to the centrality of the others.     

Truthful Equilibria in Dynamic Bayesian Games

This paper characterizes an equilibrium payoff subset for dynamic Bayesian games as discounting vanishes. Monitoring is imperfect, transitions may depend on actions, types may be correlated, and values may be interdependent. The focus is on equilibria in which players report truthfully. The characterization generalizes that for repeated games, reducing the analysis to static Bayesian games with transfers. With independent private values, the restriction to truthful equilibria is without loss, except for the punishment level: if players withhold their information during punishment‐like phases, a folk theorem obtains.     

基于共识程度的双体博弈纳什均衡拓展研究

首先对一般双体博弈的策略进行拓展,提出共识纳什均衡的概念,并证明其存在性;根据共识程度的降低提出其他3种拓展形式——近似共识纳什均衡、局部共识纳什均衡和局部近似共识纳什均衡,并举例进行说明;然后,对各种均衡形式下的合作效率进行分析和比较。研究表明,共识纳什均衡的利益分配是基于信息本身——竞争环境的特殊形式,它是具有效率的。其他3种形式均衡的效率低于共识纳什均衡,但仍高于双体博弈纳什均衡。共识纳什均衡和其他3种形式的均衡为参与人组织更具效率的合作提供了渠道和理论解释。     

Uniqueness of equilibria in atomic splittable polymatroid congestion games

We study uniqueness of Nash equilibria in atomic splittable congestion games and derive a uniqueness result based on polymatroid theory: when the strategy space of every player is a bidirectional flow polymatroid, then equilibria are unique. Bidirectional flow polymatroids are introduced as a subclass of polymatroids possessing certain exchange properties. We show that important cases such as base orderable matroids can be recovered as a special case of bidirectional flow polymatroids. On the other hand we show that matroidal set systems are in some sense necessary to guarantee uniqueness of equilibria: for every atomic splittable congestion game with at least three players and non-matroidal set systems per player, there is an isomorphic game having multiple equilibria. Our results leave a gap between base orderable matroids and general matroids for which we do not know whether equilibria are unique.     

Congestion games with mixed objectives

We study a new class of games which generalizes congestion games and its bottleneck variant. We introduce congestion games with mixed objectives to model network scenarios in which players seek to optimize for latency and bandwidths alike. We characterize the (non-)existence of pure Nash equilibria (PNE), the convergence of improvement dynamics, the quality of equilibria and show the complexity of the decision problem. For games that do not possess PNE we give bounds on the approximation ratio of approximate pure Nash equilibria.     

Single Crossing Properties and the Existence of Pure Strategy Equilibria in Games of Incomplete Information

This paper analyzes a class of games of incomplete information where each agent has private information about her own type, and the types are drawn from an atomless joint probability distribution. The main result establishes existence of pure strategy Nash equilibria (PSNE) under a condition we call the single crossing condition (SCC), roughly described as follows: whenever each opponent uses a nondecreasing strategy (in the sense that higher types choose higher actions), a player's best response strategy is also nondecreasing. When the SCC holds, a PSNE exists in every finite‐action game. Further, for games with continuous payoffs and a continuum of actions, there exists a sequence of PSNE to finite‐action games that converges to a PSNE of the continuum‐action game. These convergence and existence results also extend to some classes of games with discontinuous payoffs, such as first‐price auctions, where bidders may be heterogeneous and reserve prices are permitted. Finally, the paper characterizes the SCC based on properties of utility functions and probability distributions over types. Applications include first‐price, multi‐unit, and all‐pay auctions; pricing games with incomplete information about costs; and noisy signaling games.     

广义不确定性下广义博弈中NS均衡的存在性

把不确定性引入广义博弈的研究之中,在此博弈中,局中人策略之间存在相互影响,局中人的策略可以改变不确定参数的变化范围,而且局中人的支付函数和策略可行反应映射都受到不确定参数的作用,此类型博弈定义为广义不确定性下的广义博弈问题。进一步定义出此类型博弈中的NS均衡,并且凭借Fan-Glicksberg不动点定理,证明此均衡点的存在性。最后给出算例验证其可行性。