On the Existence of Undominated Nash Equilibria in Normal Form Games

In this paper the existence problem of undominated Nash equilibrium in normal form games is analyzed. It is shown that an undominated Nash equilibrium exists, if (a) strategy sets are convex polytopes inRⁿand (b) utility functions are affine with respect to each player's own strategy. It is shown by counterexamples that, first, it is not sufficient to have concave utility functions instead of affine under condition (b) even when condition (a) is satisfied, and, second, it is not sufficient to have just compact and convex strategy sets instead of polytopes in condition (a) even when condition (b) is satisfied.     

Undominated Nash Implementation with Collusion and Renegotiation

This article looks at implementation in economic environments when agents have perfect information about the state of the world, but cannot commit not to renegotiate bad outcomes or to collude against each other. If renegotiation satisfies a weak condition of disagreement point monotonicity, then any Pareto-efficient social choice function can be implemented if there are at least three agents who play undominated Nash equilibria. The mechanism does not use modulo or integer games, has no bad mixed strategy equilibria, and is “bounded.”Journal of Economic LiteratureClassification Number: D71.     

Dominant strategy implementation in economic environments

We study dominant strategy implementation especially in economic environments. We first show that in general environments, strategy-proofness and quasi-strong-non-bossiness together are necessary and sufficient for dominant strategy implementation via the associated direct revelation mechanism. We next prove that in weak separable environments, strategy-proofness is sufficient for dominant strategy implementation, by using an augmented revelation mechanism similar to the one devised by Jackson, Palfrey, and Srivastava [Jackson, M.O., Palfrey, T.R., Srivastava, S., 1994. Undominated Nash implementation in bounded mechanisms. Games Econ. Behav. 6, 474–501]. Moreover, we focus on pure exchange economies without free disposal, and try to construct another augmented revelation mechanism that satisfies balancedness in and out of equilibrium, and which implements all strategy-proof social choice functions in dominant strategy equilibria.     

Implementing efficient graphs in connection networks

We consider the problem of sharing the cost of a network that meets the connection demands of a set of agents. The agents simultaneously choose paths in the network connecting their demand nodes. A mechanism splits the total cost of the network formed among the participants. We introduce two new properties of implementation. The first property, Pareto Nash implementation (PNI), requires that the efficient outcome always be implemented in a Nash equilibrium and that the efficient outcome Pareto dominates any other Nash equilibrium. The average cost mechanism and other asymmetric variations are the only mechanisms that meet PNI. These mechanisms are also characterized under strong Nash implementation. The second property, weakly Pareto Nash implementation (WPNI), requires that the least inefficient equilibrium Pareto dominates any other equilibrium. The egalitarian mechanism (EG) and other asymmetric variations are the only mechanisms that meet WPNI and individual rationality. EG minimizes the price of stability across all individually rational mechanisms.     

CORRELATED EQUILIBRIA,GOOD AND BAD: AN EXPERIMENTAL STUDY*

We report results from an experiment that explores the empirical validity of correlated equilibrium, an important generalization of Nash equilibrium. Specifically, we examine the conditions under which subjects playing the game of Chicken will condition their behavior on private third‐party recommendations drawn from publicly announced distributions. We find that when recommendations are given, behavior differs from both a mixed‐strategy Nash equilibrium and behavior without recommendations. In particular, subjects typically follow recommendations if and only if (1) those recommendations derive from a correlated equilibrium and (2) that correlated equilibrium is payoff‐enhancing relative to the available Nash equilibria.     

A near Pareto optimal auction with budget constraints

In a setup where a divisible good is to be allocated to a set of bidders with budget constraints, we introduce a mechanism in the spirit of the Vickrey auction. In the mechanism we propose, understating budgets or values is weakly dominated. Since the revenue is increasing in budgets and values, all kinds of equilibrium deviations from true valuations turn out to be beneficial to the auctioneer. We also show that ex-post Nash equilibrium of our mechanism is near Pareto optimal in the sense that all full winners? values are above all full losers? values.     

EQUILIBRIUM SELECTION IN THE YANO MODEL OF PRICE LEADERSHIP

Abstract. A number of studies have provided a theoretical explanation for the fact that the technologically superior firm becomes a price leader in a duopoly market for a homogeneous product. While previous studies show that the state in which the technologically superior firm becomes a price leader is a Nash equilibrium (superior leader equilibrium), they do not eliminate the possibility that the state in which the technologically inferior firm becomes a price leader is also a Nash equilibrium (inferior leader equilibrium). We demonstrate that an inferior leader equilibrium can be eliminated by the iterative elimination of weakly dominated strategies.     

Implementation,Elimination of Weakly Dominated Strategies and Evolutionary Dynamics

This paper studies convergence and stability properties of T. Sjöström's (1994, Games Econom. Behav.6, 502–511) mechanism, under the assumption that boundedly rational players find their way to equilibrium using monotonic evolutionary dynamics and best-reply dynamics. This mechanism implements most social choice functions in economic environments using as a solution concept one round of deletion of weakly dominated strategies and one round of deletion of strictly dominated strategies. However, there are other sets of Nash equilibria, whose payoffs may be very different from those desired by the social choice function. With monotonic dynamics, all these sets of equilibria contain limit points of the evolutionary dynamics. Furthermore, even if the dynamics converge to the “right” set of equilibria (i.e., the one which contains the solution of the mechanism), it may converge to an equilibrium which is worse in welfare terms. In contrast with this result, any interior solution of the best-reply dynamics converges to the equilibrium whose outcome the planner desires. Journal of Economic Literature Classification Numbers: C72, D70, D78.     

Nash equilibrium and party polarization in an electoral model with mixed motivations

We study the existence problem of Nash equilibrium as well as the patterns of equilibrium policy outcomes in an electoral competition model with mixed motivations. Each party maximizes a sum of party members’ expected utility and office rent. The inclusion of office rent renders the payoff of each party discontinuous. This makes it difficult to apply usually fixed point arguments to prove the existence of Nash equilibria. By using a recently developed concept, multiple restrictional security (MR‐security) we provide conditions under which a pure‐strategy Nash equilibrium exists within fairly general settings, and further the analysis by presenting conditions under which various patterns of policy choices, including polarization, arise in equilibrium.     

Individual and Aggregate Real Balances in a Random-Matching Model

This article investigates the characteristics of stationary single-price equilibrium in a monetary random-matching model where agents can hold an arbitrary amount of divisible money and where production is costly. At such an equilibrium, agents' money holdings are endogenously determined and uniformly bounded. A refinement of weakly undominated strategies is argued to be necessary. It is shown that a continuum of single-price equilibria indexed by the aggregate real-money balance exists if one such equilibrium exists. Equilibria with different money-holdings upper bounds, hence different distributions, but with identical aggregate real-money balances can coexist.     

Adaptive Learning and Iterated Weak Dominance

This article addresses the idea that rational players should not play iteratively weakly dominated strategies by showing that when a particular type of adaptive learning process converges, then players must have learned to play strategy profiles equivalent to those that survive iterated nice weak dominance and, for certain games, equivalent to those that survive iterated weak dominance. For games satisfying the weak single crossing condition, the set of strategies that survive iterated weak dominance is small in that its bounds are pure strategy Nash equilibria. The results hold regardless of the order in which dominated strategies are eliminated.Journal of Economic LiteratureClassification Number: C72.     

Assignment maximization

We evaluate the goal of maximizing the number of individuals matched to acceptable outcomes. We present two mechanisms that maximize assignments. The first is Pareto efficient and undominated—in terms of the number of assignments—in equilibrium. The second is fair for unassigned agents and assigns weakly more agents than any stable mechanism in equilibrium.     

Equilibrium play in matches: Binary Markov games

We study two-person extensive form games, or “matches,” in which the only possible outcomes (if the game terminates) are that one player or the other is declared the winner. The winner of the match is determined by the winning of points, in “point games.” We call these matches binary Markov games. We show that if a simple monotonicity condition is satisfied, then (a) it is a Nash equilibrium of the match for the players, at each point, to play a Nash equilibrium of the point game; (b) it is a minimax behavior strategy in the match for a player to play minimax in each point game; and (c) when the point games all have unique Nash equilibria, the only Nash equilibrium of the binary Markov game consists of minimax play at each point. An application to tennis is provided.     

Strong Equilibrium in Congestion Games

[6]introduced the class of congestion games and proved that they always possess a Nash equilibrium in pure strategies. Here we obtain conditions for the existence of a strong equilibrium in this class of games, as well as for the equivalence of Nash and strong equilibria. We also give conditions for uniqueness and for Pareto optimality of the Nash equilibrium. Except for a natural monotonicity assumption on the utilities, the conditions are expressed only in terms of the underlying congestion game form. It turns out that avoiding a certain type of bad configuration in the strategy spaces is essential to positive results.Journal of Economic LiteratureClassification Numbers: C71, C72, D62.     

Iterated strict dominance in general games

We offer a definition of iterated elimination of strictly dominated strategies (IESDS^*) for games with (in)finite players, (non)compact strategy sets, and (dis)continuous payoff functions. IESDS^* is always a well-defined order independent procedure that can be used to solve Nash equilibrium in dominance-solvable games. We characterize IESDS^* by means of a “stability” criterion, and offer a sufficient and necessary epistemic condition for IESDS^*. We show by an example that IESDS^* may generate spurious Nash equilibria in the class of Reny's better-reply secure games. We provide sufficient/necessary conditions under which IESDS^* preserves the set of Nash equilibria.     

Iterated strict dominance in general games

We offer a definition of iterated elimination of strictly dominated strategies (IESDS^*) for games with (in)finite players, (non)compact strategy sets, and (dis)continuous payoff functions. IESDS^* is always a well-defined order independent procedure that can be used to solve Nash equilibrium in dominance-solvable games. We characterize IESDS^* by means of a “stability” criterion, and offer a sufficient and necessary epistemic condition for IESDS^*. We show by an example that IESDS^* may generate spurious Nash equilibria in the class of Reny's better-reply secure games. We provide sufficient/necessary conditions under which IESDS^* preserves the set of Nash equilibria.     

Congestion games with load-dependent failures: Identical resources

We define a new class of games, congestion games with load-dependent failures (CGLFs). In a CGLF each player can choose a subset of a set of available resources in order to try and perform his task. We assume that the resources are identical but that players' benefits from successful completion of their tasks may differ. Each resource is associated with a cost of use and a failure probability which are load-dependent. Although CGLFs in general do not have a pure strategy Nash equilibrium, we prove the existence of a pure strategy Nash equilibrium in every CGLF with nondecreasing cost functions. Moreover, we present a polynomial time algorithm for computing such an equilibrium.     

Secure implementation experiments: Do strategy-proof mechanisms really work?

Strategy-proofness, requiring that truth-telling is a dominant strategy, is a standard concept used in social choice theory. Saijo, Sjöström and Yamato [Saijo, T., Sjöström, T., Yamato, T., 2003. Secure implementation: Strategy-proof mechanisms reconsidered. Working paper 4-03-1. Department of Economics, Pennsylvania State University] argue that this concept has serious drawbacks. In particular, many strategy-proof mechanisms have a continuum of Nash equilibria, including equilibria other than dominant strategy equilibria. For only a subset of strategy-proof mechanisms do the set of Nash equilibria and the set of dominant strategy equilibria coincide. For example, this double coincidence occurs in the Groves mechanism when preferences are single-peaked. We report experiments using two strategy-proof mechanisms. One of them has a large number of Nash equilibria, but the other has a unique Nash equilibrium. We found clear differences in the rate of dominant strategy play between the two.     

A note on undominated Bertrand equilibria

This note shows that the conventional outcome associated with Bertrand competition with homogenous products and different marginal costs is obtained in every Nash equilibrium in which firms use undominated strategies. This strengthens an existence result due to Blume (2003).     

Search theory,competitive equilibrium,and the Nash bargaining solution

We investigate a canonical search-theoretic model without entry. Two agents are randomly matched with a long side being rationed. The matched agents face a pair of randomly drawn non-transferable payoffs, and then choose whether or not to form a partnership subject to a small probability of exogenous break down. As this probability and friction vanish, the Nash bargaining solution emerges as the unique undominated strategy equilibrium outcome if the mass of each party is the same. If the size of one party is larger than the other, the short side extracts the entire surplus, a sharp contrast to Rubinstein and Wolinsky (1985) [16].