Kernel-based type spaces

Type space is of fundamental importance in epistemic game theory. This paper shows how to build type space if players approach the game in a way advocated by Bernheim's justification procedure. If an agent fixes a strategy profile of her opponents and ponders which of their beliefs about her set of strategies make this profile optimal, such an analysis is represented by kernels and yields disintegrable beliefs. Our construction requires that underlying space is Polish.     

The equivalence of the Dekel–Fudenberg iterative procedure and weakly perfect rationalizability

Summary. Two approaches have been proposed in the literature to refine the rationalizability solution concept: either assuming that a player believes that with small probability her opponents choose strategies that are irrational, or assuming that their is a small amount of payoff uncertainty. We show that both approaches lead to the same refinement if strategy perturbations are made according to the concept of weakly perfect rationalizability, and if there is payoff uncertainty as in Dekel and Fudenberg [J. of Econ. Theory 52 (1990), 243–267]. For both cases, the strategies that survive are obtained by starting with one round of elimination of weakly dominated strategies followed by many rounds of elimination of strictly dominated strategies. Received: 10 December 1998; revised version: 26 April 1999     

Proper belief revision and equilibrium in dynamic games

We present a theory of rationality in dynamic games in which players, during the course of the game, may revise their beliefs about the opponents’ utility functions. The theory is based upon the following three principles: (1) the players’ initial beliefs about the opponents’ utilities should agree on some profile u of utility functions, (2) every player should believe, at each of his information sets, that his opponents are carrying out optimal strategies and (3) a player at information set h should not change his belief about an opponent's ranking of strategies a and b if both a and b could have led to h. Scenarios with these properties are called preference conjecture equilibria for the profile u of utility functions. We show that every normal form proper equilibrium for u induces a preference conjecture equilibrium for u, thus implying existence of preference conjecture equilibrium.     

Robustness to strategic uncertainty

We introduce a criterion for robustness to strategic uncertainty in games with continuum strategy sets. We model a player's uncertainty about another player's strategy as an atomless probability distribution over that player's strategy set. We call a strategy profile robust to strategic uncertainty if it is the limit, as uncertainty vanishes, of some sequence of strategy profiles in which every player's strategy is optimal under his or her uncertainty about the others. When payoff functions are continuous we show that our criterion is a refinement of Nash equilibrium and we also give sufficient conditions for existence of a robust strategy profile. In addition, we apply the criterion to Bertrand games with convex costs, a class of games with discontinuous payoff functions and a continuum of Nash equilibria. We show that it then selects a unique Nash equilibrium, in agreement with some recent experimental findings.     

Perfect Information and Potential Games

Games with perfect information giving rise to potential normal forms are described. For agent normal forms, a potential is defined such that a strategy profile is a maximizer for the potential if and only if it is a subgame perfect equilibrium. In the normal form of any game with perfect information, every better reply path where the players do not change their choices at irrelevant nodes leads to an equilibrium. Journal of Economic Literature Classification Number: C72.     

Optimal incentive contracts with multiple agents

A setting in which a single principal contracts with two agents who possess perfect private information about their own productivity is considered. With correlated productivities, each agent's private information also provides a signal about the other agent's productivity. In contrast to the setting in which there is only one agent, it is shown that such private information may be of no value to the agents. It is only if the agents are risk-averse that their private information may allow them to command rents. Moreover, when the agents are constrained only to reveal their private information truthfully as a Nash equilibrium, the Pareto optimal incentive scheme may induce the agents to adopt strategies other than truth-telling. This leads to the consideration of truth-telling equilibria that are not Pareto dominated in the subgame played by the agents. Among all such equilibria, the one preferred by the principal restricts one agent to tell the truth as a dominant strategy and the other as a Nash response to truth.     

Informational Constraints and the Overlapping Generations Model: Folk and Anti-Folk Theorems

This paper analyses the sustainability of inter-generational transfers in Samuelson's consumption-loan model when agents are imperfectly informed about past events. We find that with mild informational constraints, transfers cannot be supported by pure-strategy equilibria. Mixed strategies allow transfers to be sustained even if agents have little information, so that a version of the Folk theorem holds. However, these equilibria are not robust. If each agent's utility function is subjected to a small random perturbation as in Harsanyi (1973), these mixed strategy equilibria unravel, and only the zero-transfer allocation survives as the unique rationalizable outcome. This result is an example of mixed strategy equilibrium of an extensive form game which cannot be purified.     

On the impossibility of achieving no regrets in repeated games

Regret-minimizing strategies for repeated games have been receiving increasing attention in the literature. These are simple adaptive behavior rules that lead to no regrets and, if followed by all players, exhibit nice convergence properties: the average play converges to correlated equilibrium, or even to Nash equilibrium in certain classes of games. However, the no-regret property relies on a strong assumption that each player treats her opponents as unresponsive and fully ignores the opponents’ possible reactions to her actions. We show that if at least one player is slightly responsive, it is impossible to achieve no regrets, and convergence results for regret minimization with responsive opponents are unknown.     

Mechanism Design under Alternative Information Structures and Constrained Capacity

In applied models, the choice of a particular incomplete information structure appears to have been motivated primarily by technical convenience. The information structures used can be classified as either probabilistic or partitional. Information is probabilistic if no agent can rule out any type profile of the remaining agents and, for at least one type of one agent, the conditional and marginal probability distributions over the remaining agents' types are not equal. Information is partitional if the only information the agents have is that one or more agents (individually) can rule out type profiles of the remaining agents and, for at least one type of one agent, that agent has information about the remaining agents. Partitional information includes complete information as a special case. Existing results on complete information environments suggest that partitional information might simplify implementation problems. Within the context of an applied agency model in which capacity is constrained, we provide results that seem to challenge this intuition.Journal of Economic LiteratureClassification Numbers: C72, D82.     

Cooperative behavior and the frequency of social interaction

We report results from an experiment that examines play in an indefinitely repeated, two-player Prisoner's Dilemma game. Each experimental session involves N subjects and a sequence of indefinitely repeated games. The main treatment consists of whether agents are matched in fixed pairings or matched randomly in each indefinitely repeated game. Within the random matching treatment, we elicit player's strategies and beliefs or vary the information that players have about their opponents. Contrary to a theoretical possibility suggested by Kandori [1992. Social norms and community enforcement. Rev. Econ. Stud. 59, 63–80], a cooperative norm does not emerge in the treatments where players are matched randomly. On the other hand, in the fixed pairings treatment, the evidence suggests that a cooperative norm does emerge as players gain more experience.     

Optimal truncation in matching markets

Although no stable matching mechanism can induce truth-telling as a dominant strategy for all participants (Roth, 1982), recent studies have presented conditions under which truthful reporting by all agents is close to optimal (Immorlica and Mahdian, 2005, Kojima and Pathak, 2009, Lee, 2011). Our results demonstrate that in large, uniform markets using the Men-Proposing Deferred Acceptance Algorithm, each woman's best response to truthful behavior by all other agents is to truncate her list substantially. In fact, the optimal degree of truncation for such a woman goes to 100% of her list as the market size grows large. In general one-to-one markets we provide comparative statics for optimal truncation strategies: reduction in risk aversion and reduced correlation across preferences each lead agents to truncate more. So while several recent papers focused on the limits of strategic manipulation, our results serve as a reminder that without pre-conditions ensuring truthful reporting, there exists a potential for significant manipulation even in settings where agents have little information.     

A myopic adjustment process leading to best-reply matching

We analyze a myopic strategy adjustment process in strategic-form games. It is shown that the steady states of the continuous time limit, which is constructed assuming frequent play and slow adjustment of strategies, are exactly the best-reply matching equilibria, as discussed by Droste, Kosfeld, and Voorneveld (2000. Mimeo, Tilburg University). In a best-reply matching equilibrium every player ‘matches’ the probability of playing a pure strategy to the probability that this pure strategy is a best reply to the pure-strategy profile played by his opponents. We derive stability results for the steady states of the continuous time limit in 2×2 bimatrix games and coordination games. Analyzing the asymptotic behavior of the stochastic adjustment process in discrete time shows convergence to minimal curb sets of the game. Moreover, absorbing states of the process correspond to best-reply matching equilibria of the game.     

A spectrum of equilibration processes in game theory

In game theory, four dynamic processes converging towards an equilibrium are distinguished and ordered by way of agents' decreasing cognitive capacities. In the eductive process, each player has enough information to simulate perfectly the others' behavior and gets immediately to the equilibrium. In epistemic learning, each player updates his beliefs about others' future strategies, with regard to their sequentially observed actions. In behavioral learning, each player modifies his own strategies according to the observed payoffs obtained from his past actions. In the evolutionary process, each agent has a fixed strategy and reproduces in proportion to the utilities obtained through stochastic interactions. All along the spectrum, longer term dynamics makes up for weaker rationality, and physical relations substitute for mental interactions. Convergence, if any, is towards an always stronger equilibrium notion and selection of an equilibrium state becomes more sensitive to context and history. The processes can be mixed if associated to different periods, agents or mechanisms and deepened if obtained by formal reasoning principles.     

Unfolding Social Hierarchies

Consider a large population of finitely-lived agents organized into n different hierarchical levels. Every period, all those placed at each level are randomly matched to play a given symmetric game. Based on the resulting outcome, a ρ-fraction of agents who (within their own level) attain the highest payoffs are promoted upwards. On the other hand, newcomers replacing those who die every period enter at the lowest level and choose irreversibly the strategy to be played for the rest of their life. This choice is made, with some noise, by imitating one of the strategies adopted at the highest level.  In this setup, the unique long-run behavior of the system is fully characterized for the whole class of 2×2 coordination games and two alternative variations of the model. The results crucially depend on the key “institutional” parameters ρ and n. In particular, it is shown that inefficient behavior prevails in the long run (even when risk-dominated) if promotion is only mildly selective—high ρ—and the social system is quite hierarchical—large n. In a stylized manner, these parameter conditions may be viewed as reflecting a sort of institutional deficiency that impairs economic performance. Journal of Economic Literature Classification Numbers: C70, C72, C73, D72.     

How Proper Is Sequential Equilibrium?

A strategy profile of a normal form game is proper if and only if it is quasi-perfect in every extensive form (with that normal form). Thus, properness requires optimality along a sequence of supporting trembles, while sequentiality only requires optimality in the limit. A decision-theoretic implementation of sequential rationality, strategic independence respecting equilibrium (SIRE), is defined and compared to proper equilibrium, using lexicographic probability systems. Finally, we give tremble-based characterizations, which do not involve structural features of the game, of the rankings of strategies that underlie proper equilibrium and SIRE.Journal of Economic LiteratureClassification Numbers: C70, C72.     

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.     

Decentralized decision-making in a large team with local information

We study a problem involving a team of agents each associated with a node in a chain. Each agent makes a decision that influences only his own cost and those of adjacent agents. Prior to making his decision, each agent observes only the cost structure associated with nodes that can be reached by traversing no more than r arcs. Decisions are selected without any coordination, with the common objective of minimizing average cost among agents. We consider such decisions decentralized since agents act based on different information. Cost incurred by an optimal centralized strategy, in which a single decision-maker has access to all information and dictates all decisions, is employed as a performance benchmark. We show that, to maintain a certain level of performance relative to optimal centralized strategies, decentralized deterministic strategies require r to be proportional to the number of agents. This means that the amount of information accessible to any agent should be proportional to the total number of agents. Stochastic strategies, on the other hand, decentralize more gracefully—the amount of information required by each agent is independent of the total number of agents.     

The effects of heterogeneous interaction and risk attitude adaptation on the evolution of cooperation

This paper addresses the evolution of cooperation in a multi-agent system with agents interacting heterogeneously with each other based on the iterated prisoner’s dilemma (IPD) game. The heterogeneity of interaction is defined in two models. First, agents in a network are restricted to interacting with only their neighbors (local interaction). Second, agents are allowed to adopt different IPD strategies against different opponents (discriminative interaction). These two heterogeneous interaction scenarios are different to the classical evolutionary game, in which each agent interacts with every other agent in the population by adopting the same strategy against all opponents. Moreover, agents adapt their risk attitudes while engaging in interactions. Agents with payoffs above (or below) their aspirations will become more risk averse (or risk seeking) in subsequent interactions, wherein risk is defined as the standard deviation of one-move payoffs in the IPD game. In simulation experiments with agents using only own historical payoffs as aspirations (historical comparison), we find that the whole population can achieve a high level of cooperation via the risk attitude adaptation mechanism, in the cases of either local or discriminative interaction models. Meanwhile, when agents use the population’s average payoff as aspirations (social comparison) for adapting risk attitudes, the high level of cooperation can only be sustained in a portion of the population (i.e., partial cooperation). This finding also holds true in both of the heterogeneous scenarios. Considering that payoffs cannot be precisely estimated in a realistic IPD game, simulation experiments are also conducted with a Gaussian disturbance added to the game payoffs. The results reveal that partial cooperation in the population under social comparison is more robust to the variation in payoffs than the global cooperation under historical comparison.     

The value of a stochastic information structure

Upon observing a signal, a Bayesian decision maker updates her probability distribution over the state space, chooses an action, and receives a payoff that depends on the state and the action taken. An information structure determines the set of possible signals and the probability of each signal given a state. For a fixed decision problem, the value of an information structure is the maximal expected utility that the decision maker can get when the observed signals are governed by this structure. Thus, every decision problem induces a preference order over information structures according to their value. We characterize preference orders that can be obtained in this way. We also characterize the functions defined over information structures that measure their value.     

Wishful Thinking in Strategic Environments

Towards developing a theory of systematic biases about strategies, I analyse strategic implications of a particular bias: wishful thinking about the strategies. I identify a player as a wishful thinker if she hopes to enjoy the highest pay-off that is consistent with her information about the others' strategies. I develop a straightforward elimination process that characterizes the strategy profiles that are consistent with wishful thinking, mutual knowledge of wishful thinking, and so on. Every pure-strategy Nash equilibrium is consistent with common knowledge of wishful thinking. For generic two-person games, I further show that the pure Nash equilibrium strategies are the only strategies that are consistent with common knowledge of wishful thinking. My analysis also illustrates how one can characterize the strategic implications of general decision rules using the tools of game theory.