Approximate common knowledge revisited

Suppose we replace “knowledge” by “belief with probability p” in standard definitions of common knowledge. Very different notions arise depending on the exact definition of common knowledge used in the substitution. This paper demonstrates those differences and identifies which notion is relevant in each of three contexts: equilibrium analysis in incomplete information games, best response dynamics in incomplete information games, and agreeing to disagree/no trade results.     

Monotonicity in asymmetric first-price auctions with affiliation

I study monotonicity of equilibrium strategies in first-price auctions with asymmetric bidders, risk aversion, affiliated types, and interdependent values. Every mixed-strategy equilibrium is shown to be outcome-equivalent to a monotone pure-strategy equilibrium under the “priority rule” for breaking ties. This provides a missing link to establish uniqueness in the “general symmetric model” of Milgrom and Weber (Econometrica 50:1089–1122, 1982). Non-monotone equilibria can exist under the “coin-flip rule” but they are distinguishable: all non-monotone equilibria have positive probability of ties whereas all monotone equilibria have zero probability of ties. This provides a justification for the standard empirical practice of restricting attention to monotone strategies. Hendricks et al. (2003) provide an overview of recent empirical work. For a survey of experimental work, see Kagel and Levin (2002).     

Equilibrium and perfection in discounted supergames

In this paper, we discuss equilibrium and perfect equilibrium in a simplified model of the supergame. We assume that players can observe the mixed moves employed by all players at each previous stage. For this model, we obtain a complete characterization of the set of equilibrium outcomes, and a fairly weak sufficient condition for this set to coincide with the set of perfect equilibrium outcomes.Inter alia, simple proofs of the Folk Theorem and the result that the requirement of perfection does not eliminate any equilibrium outcomes for the undiscounted supergame are presented.     

On equilibrium in pure strategies in games with many players

We demonstrate that, if there are sufficiently many players, any Bayesian equilibrium of an incomplete information game can be “ε-purified” . That is, close to any Bayesian equilibrium there is an approximate Bayesian equilibrium in pure strategies. Our main contribution is obtaining this result for games with a countable set of pure strategies. In order to do so we derive a mathematical result, in the spirit of the Shapley–Folkman Theorem, permitting countable strategy sets. Our main assumption is a “large game property,” dictating that the actions of relatively small subsets of players cannot have large affects on the payoffs of other players. E. Cartwright and M. Wooders are indebted to Phillip Reny, Frank Page and two anonymous referees for helpful comments.     

Choice of solution in one-step bimatrix games

A new approach to the solution of one-step games is constructed, without using the concept of mixed strategy. The notion of a “set” solution of a bimatrix game is defined. It is shown that this solution always exists and may be found by a finite procedure. Examples are given illustrating the form of the “set” solution and the structure of the set of best responses for various levels of information availability to the players regarding the opponent’s behavior. __________ Translated from Nelineinaya Dinamika i Upravlenie, No. 4, pp. 341–356, 2004.     

Negotiation-proof Nash equilibrium

This paper defines “negotiation-proof Nash equilibrium', a notion that applies to environments where players can negotiate openly and directly prior to the play of a noncooperative game. It recognizes the possibility that a group of self-interested players may choose, voluntarily and without binding agreement, to coordinate their choice of strategies and make joint objections; moreover, it takes the perfect foresight of rational players fully into account. The merit of the notion of negotiation-proof Nash equilibrium is twofold: (1) It offers a way to rectify the nestedness assumption and myopia embedded in the notion of coalition-proof Nash equilibrium. (2) The negotiation process is formalized by a “graph”, which serves as a natural extension to the approach that models preplay communication by an extensive game. Received: October 1998/Final version: May 2000     

On the role of chance moves and information in two-person games

The value of information has been the subject of many studies in a strategic context. The central question in these studies is how valuable the information hidden in the chance moves of a game is for one or more of the players. Generally speaking, only the extra possibilities that are beneficial for the players have been considered so far. In this note we study the value of information for a special class of two-person games. For these games we also investigate how “badly” the players can do, both with and without knowing the result of the chance move. In this way one can determine to what extent the players are restricted in their possibilities by the fact that some information is hidden in the chance moves of the games. This allows for a comparison of the influence of the chance move to the control that the players have over the game result.     

Weak equilibrium in a spatial model

Spatial models of two-player competition in spaces with more than one dimension almost never have pure-strategy Nash equilibria, and the study of the equilibrium positions, if they exist, yields a disappointing result: the two players must choose the same position to achieve equilibrium. In this work, a discrete game is proposed in which the existence of Nash equilibria is studied using a geometric argument. This includes a definition of equilibrium which is weaker than the classical one to avoid the uniqueness of the equilibrium position. As a result, a “region of equilibrium” appears, which can be located by geometric methods. In this area, the players can move around in an “almost-equilibrium” situation and do not necessarily have to adopt the same position.     

Probabilistic Choice in Games: Properties of Rosenthal’s t-Solutions

The t-solutions introduced in R. W. Rosenthal (1989, Int J Game Theory 18:273–292) are quantal response equilibria based on the linear probability model. Choice probabilities in t-solutions are related to the determination of leveling taxes in taxation problems. The set of t-solutions coincides with the set of Nash equilibria of a game with quadratic control costs. Evaluating the set of t-solutions for increasing values of t yields that players become increasingly capable of iteratively eliminating never-best replies and eventually only play rationalizable actions with positive probability. These features are not shared by logit quantal response equilibria. Moreover, there exists a path of t-solutions linking uniform randomization to Nash equilibrium     

The Existence and Uniqueness of Nash Equilibrium Point in an m-player Game “Shoot Later, Shoot First!”

We consider the following “silent duel” of m players with a possible economic interpretation. Each player has one “bullet”, which she can shoot at any time during the time interval [0,1]. The probability that the i-th player hits the “target” at moment t is given by an increasing accuracy function f _i (t). The winner is the player who hits the target first. Under natural assumptions on the functions f _i (t) we prove the existence and uniqueness of a Nash equilibrium point in this game, and we provide an explicit construction of this equilibrium. This construction allows us to obtain exact solutions for many specific examples. Some of them are presented.This work was partly supported by RBRF grants 03-01-00479.     

A remark on the princess and monster search game

We consider two zero-sum search games in which a searcher moves along a continuous trajectory in a search setQ. The probability of detection depends on the distance between the two players. The problem is open loop, i.e. neither player receives any information about the other as the game progresses. The payoff to a hider is the elapsed time before detection. Optimal mixed strategies are obtained.     

Generalized correlated equilibrium for two-person games in extensive form with perfect information

A correlation scheme (leading to a special equilibrium called “soft” correlated equilibrium) is applied for two-person finite games in extensive form with perfect information. Randomization by an umpire takes place over the leaves of the game tree. At every decision point players have the choice either to follow the recommendation of the umpire blindly or freely choose any other action except the one suggested. This scheme can lead to Pareto-improved outcomes of other correlated equilibria. Computational issues of maximizing a linear function over the set of soft correlated equilibria are considered and a linear-time algorithm in terms of the number of edges in the game tree is given for a special procedure called “subgame perfect optimization”.     

Game theoretical optimization inspired by information theory

Inspired by previous work on information theoretical optimization problems, the basics of an axiomatic theory of certain special two-person zero-sum games is developed. One of the players, “Observer”, is imagined to have a “mind”, the other, “Nature”, not. These ideas lead to un-symmetric modeling as the two players are treated quite differently. Basic concavity- and convexity results as well as a general minimax theorem are derived from the axioms.     

Junctions of singularly degenerating domains with different limit dimensions 1

The asymptotic series for solutions of the mixed boundary-value problem for the Poisson equation in a domain, which is a junction of singularly degenerating domains, are constructed. In this paper, which is the first part of the publication, the three-dimensional problem (“wheel hub with spokes”) and the analogous two-dimensional problems are considered. The methods of matched and compound asymptotic expansions are used. It is shown that a special self-adjoint extension of the operator of the limit problem in the “hub” supplied by the straight-line segments (“limits of spokes”) can be chosen as an asymptotical model of the problem in question; the extension parameters are to be some integral characteristics of the boundary-layer problems. Bibliography: 39 titles. Translated from Trudy Seminara imeni I. G. Petrovskogo. No. 18, pp. 3–78, 1995.     

Proper rationalizability and backward induction

This paper introduces a new normal form rationalizability concept, which in reduced normal form games corresponding to generic finite extensive games of perfect information yields the unique backward induction outcome. The basic assumption is that every player trembles “more or less rationally” as in the definition of a ε-proper equilibrium by Myerson (1978). In the same way that proper equilibrium refines Nash and perfect equilibrium, our model strengthens the normal form rationalizability concepts by Bernheim (1984), B?rgers (1994) and Pearce (1984). Common knowledge of trembling implies the iterated elimination of strategies that are strictly dominated at an information set. The elimination process starts at the end of the game tree and goes backwards to the beginning. Received: October 1996/Final version: May 1999     

Equilibria of a two-stage market with chance outcome in the spot market

We address the problem of how to improve the efficiency of markets of similar goods (electric power, gas, and other resources). One way to undermine the market dominance of some companies is the possibility of forward contracts. Here a model of the spot and forward markets functioning as Curnout auctions is studied using the example of symmetrical oligopoly. Suppliers try to maximize their profit by this two-stage game’s strategies of traded subgame equilibrium (TSE). The conditions for equilibrium achieved by correlated mixed strategies are elucidated: either a “bull” or “bear” market is established according to a chance factor. The optimum strategies of rational bidders are found to depend on the reserve price and a risk-avoiding parameter. TSE is compared to the Nash equilibria for one-stage models.     

Righting the early history of computing,or how sausage was made

The short answer to the question just posed seems to be, “Not much.” Since I have given “the long answer” elsewhere,¹² I can summarize it here. Berg could see no point in writing Bromley. What could he write to someone he believed guilty of plagiarism? What could such a letter accomplish? He did, however, write to New York University Press; to all the universities involved, and to the Works’ English publisher (Pickering and Chatto), who said they passed the letter on to Campbell-Kelly (30 June 1990); to a great many professional societies in Australia, England, and the United States; to a great many governmental agencies and some politicians in those countries; to some publications, both academic and popular; to the Pope and several cardinals; and to a miscellany of other individuals. Generally, those in the best position to do something—for example, the three universities involved —did not even answer Berg’s letter. Others often did answer, but their answer was generally that they were in no position to do anything. That was how matters stood when I published my first article on “the Berg Affair”.₁₂ Its publication finally roused those best positioned to answer. Late in 1993, Galler, Bromley, and Campbell-Kelly wrote letters to the editor of Accountability in Research criticizing me for not getting their side of the story before I published Berg’s. Campbell-Kelly threatened the journal’s publisher with a lawsuit if I (or it) did not retract. The three also provided some insight into what their explanation of events might be. Bromley, though listed prominently in ads for the Works, claimed to have had only a small part, merely advising Campbell-Kelly on selection and arrangement of the papers printed in Volumes 2 and 3. Campbell-Kelly confirmed that Bromley took no part in the detailed editing or in the provision of documents. That work was performed by one C.J.D. (“Jim”) Roberts, a “London-based independent scholar” who was “editorial consultant to the Works” (and, apparently, worked directly under Campbell-Kelly). Roberts seems to deserve more public credit than he has so far received. According to Campbell-Kelly, it was Roberts who, making a systematic search for unknown holdings of Babbage, turned up the original of the letter to Quetelet by writing the Royal Library (one “tiny triumph” among many). Campbell-Kelly also claimed that neither he nor Roberts knew of Berg’s prior discovery.     

Local Search Proximal Algorithms as Decision Dynamics with Costs to Move

Acceptable moves for the “worthwhile-to-move” incremental principle are such that “advantages-to-move” are higher than some fraction of “costs-to-move”. When combined with optimization, this principle gives raise to adaptive local search proximal algorithms. Convergence results are given in two distinctive cases, namely low local costs-to-move and high local costs-to-move. In this last case, one obtains a dynamic cognitive approach to Ekeland’s ϵ-variational principle. Introduction of costs-to-move in the algorithms yields robustness and stability properties.     

A Strong Anti-Folk Theorem

We study the properties of finitely complex, symmetric, globally stable, and semi-perfect equilibria. We show that: (1) If a strategy satisfies these properties then players play a Nash equilibrium of the stage game in every period; (2) The set of finitely complex, symmetric, globally stable, semi-perfect equilibrium payoffs in the repeated game equals the set of Nash equilibria payoffs in the stage game; and (3) A strategy vector satisfies these properties in a Pareto optimal way if and only if players play some Pareto optimal Nash equilibrium of the stage game in every stage. Our second main result is a strong anti-Folk Theorem, since, in contrast to what is described by the Folk Theorem, the set of equilibrium payoffs does not expand when the game is repeated.This paper is a revised version of Chapter 3 of my Ph.D. thesis, which has circulated under the title “An Interpretation of Nash Equilibrium Based on the Notion of Social Institutions”.