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.     

Learning to Learn, Pattern Recognition, and Nash Equilibrium

The paper studies a large class of bounded-rationality, probabilistic learning models on strategic-form games. The main assumption is that players “recognize” cyclic patterns in the observed history of play. The main result is convergence with probability one to a fixed pattern of pure strategy Nash equilibria, in a large class of “simple games” in which the pure equilibria are nicely spread along the lattice of the game. We also prove that a necessary condition for convergence of behavior to a mixed strategy Nash equilibrium is that the players consider arbitrarily long histories when forming their predictions.Journal of Economic LiteratureClassification Numbers: C72, D83.     

On the Least Core and the Mas-Colell Bargaining Set

We show that the least core of a TU coalitional game with a finite set of players is contained in the Mas-Colell bargaining set. This result is extended to games with a measurable space of players in which the worth of the grand coalition is at least that of any other coalition in the game. As a consequence, we obtain an existence theorem for the Mas-Colell bargaining set in TU games with a measurable space of players. Journal of Economic Literature Classification Number: C71.     

Stable governments and the semistrict core

We consider the class of proper monotonic simple games and study coalition formation when an exogenous weight vector and a solution concept are combined to guide the distribution of power within winning coalitions. These distributions induce players' preferences over coalitions in a hedonic game. We formalize the notion of semistrict core stability, which is stronger than the standard core concept but weaker than the strict core notion and derive two characterization results for the semistrict core, depending on conditions we impose on the solution concept. A bounded power condition, which connects exogenous weights and the solution, turns out to be crucial. It generalizes a condition termed “absence of the paradox of smaller coalitions” that was previously used to derive core existence results.     

The Core of Large Differentiable TU Games

For suitable non-atomic TU games ν, the core can be determined by computing appropriate derivatives of ν, yielding one of two stark conclusions: either core(ν) is empty or it consists of a single measure that can be expressed explicitly in terms of derivatives of ν. In this sense, core theory for a class of games may be reduced to calculus. Journal of Economic Literature Classification Number: C71.     

On core stability, vital coalitions, and extendability

If a TU game is extendable, then its core is a stable set. However, there are many TU games with a stable core that are not extendable. A coalition is vital if there exists some core element x such that none of the proper subcoalitions is effective for x. It is exact if it is effective for some core element. If all coalitions that are vital and exact are extendable, then the game has a stable core. It is shown that the contrary is also valid for matching games, for simple flow games, and for minimum coloring games.     

The bargaining set of a large game

We study the equivalence between the Mas-Colell bargaining set and the core in the general context of TU games with a measurable space of players. In the first part of the paper, we study the problem without imposing any restriction on the class of games we consider. In the second part, we first introduce a new class of exact games, which we call thin games. For these games, we show not only that the Mas-Colell bargaining set is equal to the core, but also that it is the unique stable set in the sense of von Neumann and Morgenstern. We then study the relation between thin games, exact non-atomic market games and non-atomic convex games. Finally, by further developing “thinness” related ideas, we prove new equivalence results for a class of non-exact market games as well as a class of non-exact, non-market games.     

Best response equivalence

Two games are best-response equivalent if they have the same best-response correspondence. We provide a characterization of when two games are best-response equivalent. The characterizations exploit a dual relationship between payoff differences and beliefs. Some “potential game” arguments [Games Econ. Behav. 14 (1996) 124] rely only on the property that potential games are best-response equivalent to identical interest games. Our results show that a large class of games are best-response equivalent to identical interest games, but are not potential games. Thus we show how some existing potential game arguments can be extended.     

On the Existence of Stable Roommate Matchings

This paper identifies a condition called “no odd rings” that is sufficient for the existence of stable roommate matchings in the weak preferences case. It shows that the process of allowing randomly chosen blocking pairs to match converges to a stable roommate matching with probability one as long as there are no odd rings. This random-paths-to-stability result generalizes that of Roth and Vande Vate (1990, Econometrica58, 1475–1480) and may not hold if there are odd rings. The “no odd rings” condition can also be used to prove a number of other sufficient conditions that are more economically interpretable. Journal of Economic Literature Classification Numbers: C78, D71.     

Outside options,component efficiency,and stability

In this paper, we introduce a component efficient value for TU games with a coalition structure which reflects the outside options of players within the same structural coalition. It is based on the idea that splitting a coalition should affect players who stay together in the same way. We show that for all TU games there is a coalition structure that is stable with respect to this value.     

Consistent solutions for cooperative games with externalities

In order to calculate the worth of a coalition of players, the coalition needs to predict the actions of outsiders. We propose that, for a given solution concept, such predictions should be made by applying the solution concept to the “reduced society” consisting of the non-members. We illustrate by computing the r-core for the case of Bertrand competition with differentiated commodities.     

The Statistical Mechanics of Best-Response Strategy Revision

This paper compares local and global strategic interaction when players update using the (myopic) best-response rule. I show that randomizing the order in which players update their strategic choice suffices to achieve coordination on the risk-dominant strategy in symmetric 2 × 2 coordination games. The "persistant randomness" which is necessary to achieve similar coordination with global interaction is replaced under local interaction by spatial variation in the initial condition. An extension of the risk-dominance idea gives the same convergence result for K × K games with strategic complementarities. Similar results for K × K pure coordination games and potential games are also presented. Journal of Economic Literature Classification Number: C78.     

Perfect and Proper Equilibria of Large Games

This paper deals with the existence and other related issues of perfect and proper equilibria of games with a continuum of players. A sufficient condition for the existence of a perfect (proper) equilibrium as an almost everywhere limit of a sequence of ε-perfect (ε-proper) equilibria is given. An example shows that almost everywhere convergence need not obtain if the condition is violated. Extension to the case where the set of actions available to the players can differ is discussed.Journal of Economic LiteratureClassification Number: C79.     

Bounding the inefficiency of equilibria in nonatomic congestion games

Equilibria in noncooperative games are typically inefficient, as illustrated by the Prisoner's Dilemma. In this paper, we quantify this inefficiency by comparing the payoffs of equilibria to the payoffs of a “best possible” outcome. We study a nonatomic version of the congestion games defined by Rosenthal [Int. J. Game Theory 2 (1973) 65], and identify games in which equilibria are approximately optimal in the sense that no other outcome achieves a significantly larger total payoff to the players—games in which optimization by individuals approximately optimizes the social good, in spite of the lack of coordination between players. Our results extend previous work on traffic routing games.     

Quasi-weightings, Trading, and Desirability Relations in Simple Games

We investigate the problem of simultaneously characterizing various classes of simple games in three different ways: (i) the existence of “quasi-weightings” in which smaller numerical values are assigned to losing coalitions than are assigned to winning ones, (ii) the robustness of “winningness” with respect to trades involving groups of players, and (iii) the acyclicity of certain strict “orderings” that intuitively correspond to the idea of one player being more desirable than another.Journal of Economic LiteratureClassification Number: C71.     

Convex Games and Stable Sets

It is well known that the core of a convex coalitional game with a finite set of players is the unique von Neumann–Morgenstern stable set of the game. We extend the definition of a stable set to coalitional games with an infinite set of players and give an example of a convex simple game with a countable set of players which does not have a stable set. But if a convex game with a countable set of players is continuous at the grand coalition, we prove that its core is the unique von Neumann–Morgenstern stable set. We also show that a game with a countable (possibly finite) set of players which is inner continuous is convex iff the core of each of its subgames is a stable set.Journal of Economic LiteratureClassification Numbers: C70, C71.     

Better-reply dynamics and global convergence to Nash equilibrium in aggregative games

We consider n-person games with quasi-concave payoffs that depend on a player's own action and the sum of all players' actions. We show that a discrete-time, stochastic process in which players move towards better replies—the better-reply dynamics—converges globally to a Nash equilibrium if actions are either strategic substitutes or strategic complements for all players around each Nash equilibrium that is asymptotically stable under a deterministic, adjusted best-reply dynamics. We present an example of a 2-person game with a unique equilibrium where the derivatives of the best-reply functions have different signs and the better-reply dynamics does not converge.     

On the stability of coalition structures

We resolve a seeming conflict between a non-existence result on solutions to coalition formation in hedonic games [Barberà, S., Gerber, A., 2007. A note on the impossibility of a satisfactory concept of stability for coalition formation games. Economics Letters 95, 85–90] and the universal existence of stable coalition structures in TU games under the χ-value [Casajus, A., 2008. Outside options, component efficiency, and stability, Games and Economic Behavior (forthcoming). doi: 10.1016/j.geb.2007.04.003].     

Anonymous yes–no voting with abstention and multiple levels of approval

Symmetric (3,2) simple games serve as models for anonymous voting systems in which each voter may vote “yes,” abstain, or vote “no,” the outcome is “yes” or “no,” and all voters play interchangeable roles. The extension to symmetric (j,2) simple games, in which each voter chooses from among j ordered levels of approval, also models some natural decision rules, such as pass–fail grading systems. Each such game is determined by the set of (anonymous) minimal winning profiles. This makes it possible to count the possible systems, and the counts suggest some interesting patterns. In the (3,2) case, the approach yields a version of May's Theorem, classifying all possible anonymous voting rules with abstention in terms of quota functions. In contrast to the situation for ordinary simple games these results reveal that the class of simple games with 3 or more levels of approval remains large and varied, even after the imposition of symmetry.     

On core stability,vital coalitions,and extendability

If a TU game is extendable, then its core is a stable set. However, there are many TU games with a stable core that are not extendable. A coalition is vital if there exists some core element x such that none of the proper subcoalitions is effective for x. It is exact if it is effective for some core element. If all coalitions that are vital and exact are extendable, then the game has a stable core. It is shown that the contrary is also valid for matching games, for simple flow games, and for minimum coloring games.