Existence of equilibria in countable games: An algebraic approach

Although mixed extensions of finite games always admit equilibria, this is not the case for countable games, the best-known example being Waldʼs pick-the-larger-integer game. Several authors have provided conditions for the existence of equilibria in infinite games. These conditions are typically of topological nature and are rarely applicable to countable games. Here we establish an existence result for the equilibrium of countable games when the strategy sets are a countable group, the payoffs are functions of the group operation, and mixed strategies are not requested to be σ-additive. As a byproduct we show that if finitely additive mixed strategies are allowed, then Waldʼs game admits an equilibrium. Finally we extend the main results to uncountable games.     

Conservative belief and rationality

Playersʼ beliefs may be incompatible, in the sense that player i can assign probability 1 to an event E to which player j assigns probability 0. One way to block incompatibility is to assume a common prior. We consider here a different approach: we require playersʼ beliefs to be conservative, in the sense that all players must ascribe the actual world positive probability. We show that common conservative belief of rationality (CCBR) characterizes strategies in the support of a subjective correlated equilibrium where all playersʼ beliefs have common support. We also define a notion of strong rationalizability, and show that it is characterized by CCBR.     

Common priors under incomplete information: a unification

Summary. While the meaningfulness of the common prior assumption (CPA) under incomplete information has been established recently by various authors, its epistemic rationale has not yet been adequately clarified. To do so, we provide a characterization of the CPA in terms of a new condition called “Mutual Calibration”, and argue that it constitutes a more transparent and more primitive formalization of the Harsanyi Doctrine than the existing characterizations. Our analysis unifies the understanding of the CPA under incomplete information and clarifies the role of higher-order expectations and of the difference between situations with only two and those with at least three agents. In the concluding section, the analysis is applied to the problem of defining Bayesian consistency of the intertemporal beliefs of a single-agent with imperfect memory. The CPA yields a notion of “Bayesian updating without a prior”. Received: March 24, 2000; revised version: April 27, 2000     

Correlated Nash equilibrium

We modify the epistemic conditions for Nash equilibrium only to accommodate Gilboa and Schmeidler's [I. Gilboa, D. Schmeidler, Maxmin expected utility with nonunique prior, J. Math. Econ. 18 (1989) 141-153] maxmin expected utility preferences, and identify the equilibrium concept in n-player strategic games that characterizes the modified epistemic conditions. The epistemic characterization supports the equilibrium concept as a minimal generalization of Nash equilibrium, in the sense that it deviates from Nash equilibrium only in terms of players' attitude towards ambiguity. Consequently, comparing it with Nash equilibrium constitutes a ceteris paribus study of the effects of ambiguity on how a game is played. For example, with ambiguity, (beliefs about) action choices are in general correlated.     

Dynamic consistency for non-expected utility preferences

This paper considers a generalization of the Savage framework in which there are two state spaces as follows: one to model events and one to define acts. The distinction between these two spaces typically induces non-consequentialist motives. The dynamic derivation of the Sure Thing Principle is studied in this framework. When these two spaces are substantially different, there exists a class of preferences that satisfy dynamic consistency and, at the same time, rationalize violations of the Sure Thing Principle. Consequently, it is possible to use non-expected utility preferences to study problems with dynamic consistency, as long as preferences belong to the previous class and as long as problems refer to information structures, defined as partitions over the set that serves to model events.     

Conditional belief types

We study type spaces where a player's type at a state is a conditional probability on the space. We axiomatize these spaces using conditional belief operators, examining three additional axioms of increasing strength. First, introspection, which requires the agent to be unconditionally certain of her beliefs. Second, echo, according to which the unconditional beliefs implied by the condition must be held given the condition. Third, determination, which says that the conditional beliefs are the unconditional beliefs that are conditionally certain. Echo implies that conditioning on an event is the same as conditioning on the event being certain, which formalizes the standard informal interpretation of conditional probability. The game-theoretic application of our model, discussed within an example, sheds light on a number of issues in the analysis of extensive form games. Type spaces are closely related to the sphere models of counterfactual conditionals and to models of hypothetical knowledge.     

Nonparametric learning rules from bandit experiments: The eyes have it!

How do people learn? We assess, in a model-free manner, subjectsʼ belief dynamics in a two-armed bandit learning experiment. A novel feature of our approach is to supplement the choice and reward data with subjectsʼ eye movements during the experiment to pin down estimates of subjectsʼ beliefs. Estimates show that subjects are more reluctant to “update down” following unsuccessful choices, than “update up” following successful choices. The profits from following the estimated learning and decision rules are smaller (by about 25% of average earnings by subjects in this experiment) than what would be obtained from a fully-rational Bayesian learning model, but comparable to the profits from alternative non-Bayesian learning models, including reinforcement learning and a simple “win-stay” choice heuristic.     

Iterated Expectations and Common Priors

A necessary and sufficient condition for the existence of a common prior for several players is given in terms of the players' present beliefs only. A common prior exists iff for each random variable it is common knowledge that all its iterated expectations converge to the same value; this value is its expectation with respect to the common prior. The proof is based on the presentation of type functions as Markov matrices.Journal of Economic LiteratureClassification Numbers: C70, D82.     

The probability of nontrivial common knowledge

We study the probability that two or more agents can attain common knowledge of nontrivial events when the size of the state space grows large. We adopt the standard epistemic model where the knowledge of an agent is represented by a partition of the state space. Each agent is endowed with a partition generated by a random scheme consistent with his cognitive capacity. Assuming that agentsʼ partitions are independently distributed, we prove that the asymptotic probability of nontrivial common knowledge undergoes a phase transition. Regardless of the number of agents, when their cognitive capacity is sufficiently large, the probability goes to one; and when it is small, it goes to zero. Our proofs rely on a graph-theoretic characterization of common knowledge that has independent interest.     

Strategic complexity in repeated extensive games

This paper studies a machine (finite automaton) playing a two-player repeated game of a simple extensive-form game with perfect information. We introduce a new complexity measure called multiple complexity which incorporates a strategyʼs responsiveness to information in the stage game as well as the number of states of the machine. We completely characterize the Nash equilibrium of the machine game. In the sequential-move prisonerʼs dilemma, cooperation can be sustained as an equilibrium.     

How common are common priors?

To answer the question in the title we vary agents? beliefs against the background of a fixed knowledge space, that is, a state space with a partition for each agent. Beliefs are the posterior probabilities of agents, which we call type profiles. We then ask what is the topological size of the set of consistent type profiles, those that are derived from a common prior (or a common improper prior in the case of an infinite state space). The answer depends on what we term the tightness of the partition profile. A partition profile is tight if in some state it is common knowledge that any increase of any single agent?s knowledge results in an increase in common knowledge. We show that for partition profiles that are tight the set of consistent type profiles is topologically large, while for partition profiles that are not tight this set is topologically small.     

Strategic approximations of discontinuous games

An infinite game is approximated by restricting the players to finite subsets of their pure strategy spaces. A strategic approximationof an infinite game is a countable subset of pure strategies with the property that limits of all equilibria of all sequences of approximating games whose finite strategy sets eventually include each member of the countable set must be equilibria of the infinite game. We provide conditions under which infinite games admit strategic approximations.     

Common belief of rationality in games of perfect information

Aumann (1995) showed that for games with perfect information common knowledge of substantive rationality implies backward induction. Substantive rationality is defined in epistemic terms, that is, in terms of knowledge. We show that when substantive rationality is defined in doxastic terms, that is, in terms of belief, then common belief of substantive rationality implies backward induction. Aumann (1998) showed that material rationality implies backward induction in the centipede game. This result does not hold when rationality is defined doxastically. However, if beliefs are interpersonally consistent then common belief of material rationality in the centipede game implies common belief of backward induction.     

Universal type structures with unawareness

Infinite hierarchies of awareness and beliefs arise in games with unawareness, similarly to belief hierarchies in standard games. A natural question is whether each hierarchy describes the playerʼs awareness of the hierarchies of other players and beliefs over these, or whether the reasoning can continue indefinitely. This paper constructs the universal type structure with unawareness where each type has an awareness level and a belief over types. Countable hierarchies are therefore sufficient to describe all uncertainty in games with unawareness.     

Characterizing the Common Prior Assumption

Logical characterizations of the common prior assumption (CPA) are investigated. Two approaches are considered. The first is called frame distinguishability, and is similar in spirit to the approaches considered in the economics literature. Results similar to those obtained in the economics literature are proved here as well, namely, that we can distinguish finite spaces that satisfy the CPA from those that do not in terms of disagreements in expectation. However, it is shown that, for the language used here, no formulas can distinguish infinite spaces satisfying the CPA from those that do not. The second approach considered is that of finding a sound and complete axiomatization. Such an axiomatization is provided; again, the key axiom involves disagreements in expectation. The same axiom system is shown to be sound and complete both in the finite and the infinite case. Thus, the two approaches to characterizing the CPA behave quite differently in the case of infinite spaces. Journal of Economic Literature Classification Numbers: C70, D80.     

Reduced game and converse consistency

The initiating points of the current paper are the axiomatic characterizations, in terms of consistency, of the equal allocation of nonseparable cost value (by Moulin), the Shapley value (by Hart and Mas-Colell), and the prenucleolus (by Orshan). The basic axioms are the same, but three different reduced games can be used to distinguish these three solutions. The main purpose of the paper is to illustrate that besides the definitions of reduced games are different, the axiom converse consistency also plays an important role to distinguish these three solutions.     

Disclosure of information in matching markets with non-transferable utility

We present a model of two-sided matching where utility is non-transferable and information about individualsʼ skills is private, utilities are strictly increasing in the partnerʼs skill and satisfy increasing differences. Skills can be either revealed or kept hidden, but while agents on one side have verifiable skills, agents on the other side have skills that are unverifiable unless certified, and certification is costly. Agents who have revealed their skill enter a standard matching market, while others are matched randomly. We find that in equilibrium only agents with skills above a cutoff reveal, and then they match assortatively. We show that an equilibrium always exists, and we discuss multiplicity. Increasing differences play an important role to shape equilibria, and we remark that this is unusual in matching models with non-transferable utility. We close the paper with some comparative statics exercises where we show the existence of non-trivial externalities and welfare implications.     

Trust and trustworthiness reputations in an investment game

Trust is an essential component of good social outcomes and effective economic performance. Reputation on the trusteeʼs past behavior in the same role has proven to be greatly effective at raising the level of trust. In this study, we show that providing information on the trusteeʼs past behavior as the trustor is equally effective as a reputation system. In fact, people still find it worthwhile to invest in a reputation as a trusting person, even though the immediate payoff for trusting is poor. This confirms the role of indirect reciprocity as a strategic notion based on reputation, whereby pro-social actions by one person towards a second person are sanctioned by a third party.     

Abstention and signaling in large repeated elections

I consider a two period model of repeated elections in which politicians update their beliefs about the preferences of the voters after the first period election and set second period policies accordingly. When voting is costless, a positive fraction of voters abstains for any finite population, but abstention vanishes in the limit of an arbitrarily large election. I demonstrate that in large elections, a single vote changes second period policies by an amount exponentially large compared to the probability of influencing the first period election if the probabilities with which voters vote for the two candidates differ. Using this, I prove that the limiting voting behavior in the first election is independent of the first period policy choices of the candidates. The incentive to vote to signal oneʼs preferences thus dominates the incentive to vote to increase the chances of electing oneʼs preferred candidate.     

Social norms and trust among strangers

We study the development of a social norm of trust and reciprocity among a group of strangers via the “contagious strategy” as defined in Kandori (1992). Over an infinite horizon, the players anonymously and randomly meet each other and play a binary trust game. In order to provide the investors with proper incentives to follow the contagious strategy, there is a sufficient condition that requires that there exists an outside option for the investors. Moreover, the investorsʼ payoff from the outside option must converge to the payoff from trust and reciprocity as the group size goes to infinity. We show that this sufficient condition is also a necessary condition to sustain any sequential equilibrium in which the trustees adopt the contagious strategy. Our results imply that a contagious equilibrium only supports trust if trust contributes almost nothing to the investorsʼ payoffs.