Repeated congestion games with bounded rationality

We consider a repeated congestion game with imperfect monitoring. At each stage, each player chooses to use some facilities and pays a cost that increases with the congestion. Two versions of the model are examined: a public monitoring setting where agents observe the cost of each available facility, and a private monitoring one where players observe only the cost of the facilities they use. A partial folk theorem holds: a Pareto-optimal outcome may result from selfish behavior and be sustained by a belief-free equilibrium of the repeated game. We prove this result assuming that players use strategies of bounded complexity and we estimate the strategic complexity needed to achieve efficiency. It is shown that, under some conditions on the number of players and the structure of the game, this complexity is very small even under private monitoring. The case of network routing games is examined in detail.     

On the probability of existence of pure equilibria in matrix games

We examine the probability that a randomly chosen matrix game admits pure equilibria and its behavior as the number of actions of the players or the number of players increases. We show that, for zero-sum games, the probability of having pure equilibria goes to zero as the number of actions goes to infinity, but it goes to a nonzero constant for a two-player game. For many-player games, if the number of players goes to infinity, the probability of existence of pure equilibria goes to zero even if the number of actions does not go to infinity.This research was supported in part by NSF Grant CCR-92-22734.     

Repeated proximity games

We consider repeated games with complete information and imperfect monitoring, where each player is assigned a fixed subset of players and only observes the moves chosen by the players in this subset. This structure is naturally represented by a directed graph. We prove that a generalized folk theorem holds for any payoff function if and only if the graph is 2-connected, and then extend this result to the context of finitely repeated games. Received June 1997/Revised version March 1998     

Limiting distributions of the number of pure strategy Nash equilibria in n-person games

We study the number of pure strategy Nash equilibria in a “random” n-person non-cooperative game in which all players have a countable number of strategies. We consider both the cases where all players have strictly and weakly ordinal preferences over their outcomes. For both cases, we show that the distribution of the number of pure strategy Nash equilibria approaches the Poisson distribution with mean 1 as the numbers of strategies of two or more players go to infinity. We also find, for each case, the distribution of the number of pure strategy Nash equilibria when the number of strategies of one player goes to infinity, while those of the other players remain finite.     

Delayed perfect monitoring in repeated games

Delayed perfect monitoring in an infinitely repeated discounted game is studied. A player perfectly observes any other player’s action choice with a fixed and finite delay. The observational delays between different pairs of players are heterogeneous and asymmetric. The Folk theorem extends to this setup. As is shown for an example, for a range of discount factors, the set of perfect public equilibria is reduced under certain conditions and efficiency improves when the players take into account private information. This model applies to many situations in which there is a heterogeneous delay between information generation and the players’ reaction.     

Crowding games are sequentially solvable

A sequential-move version of a given normal-form game Γ is an extensive-form game of perfect information in which each player chooses his action after observing the actions of all players who precede him and the payoffs are determined according to the payoff functions in Γ. A normal-form game Γ is sequentially solvable if each of its sequential-move versions has a subgame-perfect equilibrium in pure strategies such that the players' actions on the equilibrium path constitute an equilibrium of Γ.  A crowding game is a normal-form game in which the players share a common set of actions and the payoff a particular player receives for choosing a particular action is a nonincreasing function of the total number of players choosing that action. It is shown that every crowding game is sequentially solvable. However, not every pure-strategy equilibrium of a crowding game can be obtained in the manner described above. A sufficient, but not necessary, condition for the existence of a sequential-move version of the game that yields a given equilibrium is that there is no other equilibrium that Pareto dominates it. Received July 1997/Final version May 1998     

Markov stopping games with random priority

In the paper a construction of Nash equilibria for a random priority finite horizon two-person non-zero sum game with stopping of Markov process is given. The method is used to solve the two-person non-zero-sum game version of the secretary problem. Each player can choose only one applicant. If both players would like to select the same one, then the lottery chooses the player. The aim of the players is to choose the best candidate. An analysis of the solutions for different lotteries is given. Some lotteries admit equilibria with equal Nash values for the players.The research was supported in part by Committee of Scientific Research under Grant KBN 211639101.     

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”.     

Social norms and choice: a weak folk theorem for repeated matching games

A folk theorem which holds for all repeated matching games is established. The folk theorem holds any time the stage game payoffs of any two players are not affinely equivalent. The result is independent of population size and matching rule—including rules that depend on players choices or the history of play.