Core and periphery in networks

We study a model of network formation where the benefits from connections exhibit decreasing returns and decay with network distance. We show that the unique equilibrium network is a periphery-sponsored star, where one player, the center, maintains no links and earns a high payoff, while all other players maintain a single link to the center and earn lower payoffs. Both the star architecture and payoff inequality are preserved in an extension of the model where agents can make transfers and bargain over the formation of links, under the condition that the surplus of connections increases in the size of agents’ neighborhoods. Our model thus generates two common features of social and economic networks: (1) a core-periphery structure; (2) positive correlation between network centrality and payoffs.     

The formation of networks with transfers among players

We examine the formation of networks among a set of players whose payoffs depend on the structure of the network, when players may bargain by promising or demanding transfer payments when forming links. We vary three aspects of the game: (i) whether players can only make transfers to (and receive transfers from) players to whom they are directly linked, or whether they can also subsidize links that they are not directly involved in, (ii) whether or not transfers relating to a given link can be made contingent on the full resulting network or only on the link itself, and (iii) whether or not players can pay other players to refrain from forming links. We characterize the networks that are supported under these variations and show how each of the above aspects either accounts for a specific type of externality, or deals with the combinatorial nature of network payoffs.     

Uniform payoff security and Nash equilibrium in compact games

We introduce a condition, uniform payoff security, for games with compact Hausdorff strategy spaces and payoffs bounded and measurable in players’ strategies. We show that if any such compact game G is uniformly payoff secure, then its mixed extension is payoff secure. We also establish that if a uniformly payoff secure compact game G has a mixed extension with reciprocally upper semicontinuous payoffs, then G has a Nash equilibrium in mixed strategies. We provide several economic examples of compact games satisfying uniform payoff security.     

Repeated games with one-memory

We study the extent to which equilibrium payoffs of discounted repeated games can be obtained by 1-memory strategies. We establish the following in games with perfect (rich) action spaces: First, when the players are sufficiently patient, the subgame perfect Folk Theorem holds with 1-memory. Second, for arbitrary level of discounting, all strictly enforceable subgame perfect equilibrium payoffs can be approximately supported with 1-memory if the number of players exceeds two. Furthermore, in this case all subgame perfect equilibrium payoffs can be approximately supported by an ε-equilibrium with 1-memory. In two-player games, the same set of results hold if an additional restriction is assumed: Players must have common punishments. Finally, to illustrate the role of our assumptions, we present robust examples of games in which there is a subgame perfect equilibrium payoff profile that cannot be obtained with 1-memory. Thus, our results are the best that can be hoped for.     

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.     

Program equilibrium

In a computerized setting, players' strategies can be implemented by computer programs, to be executed on a shared computational devise. This situation becomes typical to new Internet economies, where agent technologies play a major role. This allows the definition of a program equilibrium. Following the fundamental ideas introduced by von Neumann in the 1940s (in parallel to his seminal contribution to game theory), a computer program can be used both as a set of instructions, as well as a file that can be read and compared with other files. We show that this idea implies that in a program equilibrium of the one-shot prisoners dilemma mutual cooperation is obtained. More generally, we show that the set of program equilibrium payoffs of a game coincides with the set of feasible and individually rational payoffs of it.     

On the folk theorem with one-dimensional payoffs and different discount factors

Proving the folk theorem in a game with three or more players usually requires imposing restrictions on the dimensionality of the stage-game payoffs. Fudenberg and Maskin (1986) assume full dimensionality of payoffs, while Abreu et al. (1994) assume the weaker NEU condition (“nonequivalent utilities”). In this note, we consider a class of n-player games where each player receives the same stage-game payoff, either zero or one. The stage-game payoffs therefore constitute a one-dimensional set, violating NEU. We show that if all players have different discount factors, then for discount factors sufficiently close to one, any strictly individually rational payoff profile can be obtained as the outcome of a subgame-perfect equilibrium with public correlation.     

Randomly available outside options in bargaining

We consider an extension of the standard Rubinstein model where both players are randomly allowed to leave the negotiation after a rejection, in which case they obtain a payoff of known value. We show that, when the value of the outside opportunities is of intermediate size, there exist a continuum of subgame-perfect equilibrium outcomes, including some with delayed agreements. Considering outside opportunities of significant value, we prove that efficient delays arise caused by the bargainers' aspirations, in waiting for their outside, option rather than by threats. Moreover, if taking the outside option decreases the probability that the opponent receives an outside option in the future, then it is possible that exactly two equilibrium payoffs coexist. In this latter case, inefficiencies may be created by agreeing too early.     

Equilibrium selection and the dynamic evolution of preferences

A population of fully rational agents plays a symmetric 2-player game in biological fitnesses, but each agent?s play is determined by his payoffs, which are free to evolve according to “survival of the fittest” pressures. An equilibrium-selection mechanism is assumed to exist, and deliver a unique outcome for any given profile of payoffs; this allows the evolution of payoffs to be modeled as a well-defined replicator dynamics. The existing static stability results that “efficient strict Nash implies stability” and “stability implies efficiency” are translated to this dynamic context, although the latter gives way to indeterminacy in the absence of a specific equilibrium-selection mechanism. A strong form of stability is established for the efficient outcome of games with common interests, whilst a weaker stability result is provided for efficient mixed-strategy equilibria of doubly symmetric games. The results are illustrated using the equilibrium-selection mechanism provided by global games.     

Farsighted network formation

This paper studies a model of dynamic network formation when individuals are farsighted: players evaluate the desirability of a “current” move in terms of its consequences on the entire discounted stream of payoffs. We define a concept of equilibrium which takes into account farsighted behavior of agents and allows for limited cooperation amongst agents. We show that an equilibrium process of network formation exists. We also show that there are valuation structures in which no equilibrium strategy profile can sustain efficient networks. We then provide sufficient conditions under which the equilibrium process will yield efficient outcomes.     

Belief-free equilibria in games with incomplete information: Characterization and existence

We generalize the results of Hörner and Lovo (2009) [15] to N-player games with arbitrary information structure. First, we characterize the set of belief-free equilibrium payoffs under low discounting as the set of feasible payoffs that are individually rational, jointly rational, and incentive compatible. Second, we provide necessary and sufficient conditions on the information structure for this set to be non-empty.     

A detail-free mediator

We present a cheap talk extension to any two-player, finite, complete information game, and ask what correlations over actions are implementable in Nash equilibria of the extended game. In the extension, players communicate repeatedly through a detail-free mediator that has been studied in Lehrer (1991) and in Gossner and Vieille (2001). The extension captures situations in which people can observe the opponentʼs face during the conversation. While Gossner and Vieille (2001) prove that no correlation can be securely implemented by using only this mediator, we prove a result closer to Lehrer (1991), namely, that the Nash equilibrium payoffs of the extended game essentially coincide with the correlated equilibrium payoffs of the underlying game. The contrasting results can be explained with our additional assumptions that the players can also communicate directly and, more importantly, the private messages sent to the mediator can be recorded and revealed later in the conversation.     

Stable games and their dynamics

We study a class of population games called stable games. These games are characterized by self-defeating externalities: when agents revise their strategies, the improvements in the payoffs of strategies to which revising agents are switching are always exceeded by the improvements in the payoffs of strategies which revising agents are abandoning. We prove that the set of Nash equilibria of a stable game is globally asymptotically stable under a wide range of evolutionary dynamics. Convergence results for stable games are not as general as those for potential games: in addition to monotonicity of the dynamics, integrability of the agents' revision protocols plays a key role.     

Stochastic imitation in finite games

In this paper we model an evolutionary process with perpetual random shocks, where individuals sample population-specific strategy-payoff pairs and imitate the most successful behavior. For finite n-player games we prove that in the limit, as the perturbations tend to zero, only strategy-tuples in minimal sets closed under single better replies will be played with positive probability. If the strategy-tuples in one such minimal set have strictly higher payoffs than all outside strategy-tuples, then the strategy-tuples in this set will be played with probability one in the limit, provided the minimal set is a product set and the sample is sufficiently large.     

Bid rotation and collusion in repeated auctions

This paper studies bidder collusion with communication in repeated auctions when no side transfer is possible. It presents a simple dynamic bid rotation scheme which coordinates bids based on communication history and enables intertemporal transfer of bidders’ payoffs. The paper derives a sufficient condition for such a dynamic scheme to be an equilibrium and characterizes the equilibrium payoffs in a general environment with affiliated signals and private or interdependent values. With IPV, it is shown that this dynamic scheme yields a strictly higher payoff to the bidders than any static collusion scheme which coordinates bids based only on the current reported signals.     

Structural holes in social networks

We consider a setting where every pair of players that undertake a transaction (e.g. exchange goods or information) creates a unit surplus. A transaction can take place only if the players involved have a connection. If the connection is direct the two players split the surplus equally, while if it is indirect then intermediate players also get an equal share of the surplus. Thus, individuals form links with others to create surplus, to gain intermediation rents, and to circumvent others who are trying to become intermediary.Our analysis clarifies the interplay between these forces in the process of strategic network formation. First, we show that, in the absence of capacity constraints on links, it leads to the emergence of a star network where a single agent acts as an intermediary for all transactions and enjoys significantly higher payoffs. Second, we study the implications of capacity constraints in the ability of agents to form links. In this case, distances between players must be long, which induces players who are “far off” to connect in order to avoid paying large intermediation rents. A cycle network then emerges, payoffs being equal across all players.     

UNIQUENESS OF EQUILIBRIUM PAYOFFS IN FINITELY REPEATED GAMES WITH IMPERFECT MONITORING*

This paper examines when a finitely repeated game with imperfect monitoring has a unique equilibrium payoff vector. This problem is nontrivial under imperfect monitoring, because uniqueness of equilibrium (outcome) in the stage game does not extend to finitely repeated games. A (correlated) equilibrium is equilibrium minimaxing if any player's equilibrium payoff is her minimax value when the other players choose a correlated action profile from the actions played in the equilibrium. The uniqueness result holds if all stage game correlated equilibria are equilibrium minimaxing and have the same payoffs. The uniqueness result does not hold under weaker conditions.     

Higher order game dynamics

Continuous-time game dynamics are typically first order systems where payoffs determine the growth rate of the players? strategy shares. In this paper, we investigate what happens beyond first order by viewing payoffs as higher order forces of change, specifying e.g. the acceleration of the players? evolution instead of its velocity (a viewpoint which emerges naturally when it comes to aggregating empirical data of past instances of play). To that end, we derive a wide class of higher order game dynamics, generalizing first order imitative dynamics, and, in particular, the replicator dynamics. We show that strictly dominated strategies become extinct in n-th order payoff-monotonic dynamics n   orders as fast as in the corresponding first order dynamics; furthermore, in stark contrast to first order, weakly dominated strategies also become extinct for n?2$n?2$. All in all, higher order payoff-monotonic dynamics lead to the elimination of weakly dominated strategies, followed by the iterated deletion of strictly dominated strategies, thus providing a dynamic justification of the well-known epistemic rationalizability process of Dekel and Fudenberg [7]. Finally, we also establish a higher order analogue of the folk theorem of evolutionary game theory, and we show that convergence to strict equilibria in n-th order dynamics is n orders as fast as in first order.     

Collusion as public monitoring becomes noisy: Experimental evidence

This paper uses laboratory experiments to test the implications of the theory of repeated games on equilibrium payoffs and estimate strategies in an infinitely repeated prisoners' dilemma game with imperfect public monitoring. We find that subjects' payoffs (i) decrease as noise increases, and (ii) are lower than the theoretical maximum for low noise, but exceed it for high noise. Under the assumption that the subjects' strategy uses thresholds on the public signal for transition between cooperation and punishment states, we find that the best fitting strategy simply compares the most recent public signal against a single threshold.     

A strategic implementation of the Average Tree solution for cycle-free graph games

In this note we provide a strategic implementation of the Average Tree solution for zero-monotonic cycle-free graph games. That is, we propose a non-cooperative mechanism of which the unique subgame perfect equilibrium payoffs correspond to the average hierarchical outcome of the game. This mechanism takes into account that a player is only able to communicate with other players (i.e., to make proposals about a division of the surplus of cooperation) when they are connected in the graph.