Contestable Norms
Mikhail Safronov

Bruno Strulovici∗

University of Cambridge

Northwestern University

December 19, 2018

Abstract
To be sustainable without external enforcement, social norms, contracts, and other agreements must not only deter violations but also withstand proposals to move to other norms,
contracts, or agreements. We introduce contestable norms, which achieve both objectives, analyze their efficiency, stability, design, and conceptual foundation, and characterize their payoffs.
Contestable norms may be inefficient even when agents have arbitrarily frequent opportunities
to interact and challenge the incumbent norm, to an extent that is determined by the amount ofconflict inherent in agents’ strategic environment. The analysis sheds new light on the efficientinstitution hypothesis and the renegotiation paradox.

Keywords: Institutions; Renegotiation; Social Norms; Social Conventions; Repeated Games;
Bargaining; Coase theorem

JEL Codes: C7; D02; D61; O1.

1

Introduction

Consider a group of individuals following an inefficient social norm. If these individuals can propose
and collectively decide on changing the norm, will the group necessarily adopt a more efficient norm,or can large inefficiencies persist?
∗

We are grateful for comments from Daron Acemoglu, Anke Becker, Eddie Dekel, Georgy Egorov, Tim Feddersen,Mark Granovetter, Paul Milgrom, David Miller, Josh Mollner, Ichiro Obara, Francisco Poggi, Anja Prummer, Larry
Samuelson, Ilya Segal, Tadashi Sekiguchi, Andrei Shleifer, Ludvig Sinander, Takuo Sugaya, Joel Watson, Asher
Wolinsky, our discussant Alex Wolitzky, and seminar participants at the 2015 SAET meeting, the 2015 World Congressof the Econometric Society, the 2016 Asian Meeting of the Econometric Society, and the 2018 Winter Meetings of
the AEA. Strulovici gratefully acknowledges financial support from an NSF CAREER Award (Grant No. 1151410)
and a fellowship from the Alfred P. Sloan Foundation.

1

This question is at the heart of the Coase theorem (Coase (1960)), which states that, in the absenceof any frictions on their ability to bargain, individuals should achieve efficient outcomes. Building on this theorem, economists have formulated and explored the efficient institution hypothesis(North and Thomas (1973)), which postulates that in the absence of transaction costs, agentsshould converge to efficient institutions. According to the literature that developed from this idea,
inefficiencies can persist only if agents face direct transaction costs, asymmetric information, orinfrequent interactions (Acemoglu (2003) and Acemoglu, Johnson, and Robinson (2005)).
This paper concerns a mechanism affecting social norms and other agreements that involves noneof the above frictions, whose gist is as follows: Consider the case of two coworkers embroiled in
an uncooperative interaction that reduces their utility. Suppose that these agents are completely
isolated from any third-party influence, that they maximize their individual utility, and that they
face no communication friction, impatience, or asymmetric information whatsoever. Would theynecessarily agree to adopt a more cooperative norm between them?
The answer, it turns out, depends on how proposals to improve the current norm are perceived
by these agents, as well as on the nature of their interaction. Suppose, first, that cooperating is
the unique Pareto efficient strategy, as in the coordination game of Figure 1(a), which represents
agents’ payoffs π1 and π2 in the game. Then, any proposal to cooperate should be accepted: theagent on the receiving end of such a proposal would gain nothing from rejecting it.
Now suppose instead that the coworkers’ relationship in each period is captured by the setting of
Figure 1(b), and that the current equilibrium is Pareto inefficient, giving each worker an average
payoff of 0.5. What happens if one of the agents, Ann, proposes to switch to a tit-for-tat equilibriumthat sustains full cooperation, so that both agents achieve a payoff of 1? The decision to accept the
proposal now depends on what happens if the other agent, Bob, rejects the proposal. If rejection
triggers a continuation that gives Bob a payoff of 2 and Ann a payoff of 0, say, Bob will reject the
proposal and Ann’s proposal will backfire. Anticipating this, Ann will abstain from making such a
proposal and, if the interaction between the workers is symmetric, so will Bob.

2

π2

π2

(0, 2)(1, 1)(1, 1)(0.5, 0.5)π10(a) Coordination game

(2, 0)0π1(b) Game of conflict

Figure 1: Payoffs sustainable by contestable norms (green area)
Examples abound in which unanimously beneficial proposals can backfire on the proposers, whether
these proposals are formal or informal. In a legislative context, for instance, a bill may be rejectedin favor of an amendment, which the instigator of the bill dislikes more than the status quo. A
rebellion against an oppressive regime may trigger political change that is worse for the instigatorsof the rebellion than the previous regime. Individuals faced with an inefficient tradition may beperceived, if they suggest abandoning the tradition, as disrespectful, blasphemous, or treasonous,
and end up losing their status, possession, or freedom, while those who reject the challenge and“defend” the tradition are rewarded above and beyond what they would gain from abandoning it.
In these examples, inefficient norms may persist in the absence of standard frictions, such as
informational asymmetries or exogenous transaction costs. Any prediction about norm efficiency
must take into account how proposals are perceived, and how these perceptions affect individuals’
incentives to make and accept such proposals. This observation underscores a distinctive aspectof norms, which concerns how they reward and punish proposals. In the coworkers’ example, anorm must not only specify rules governing how the coworkers respond to misbehavior, such as a
tit-for-tat response, but also how proposals to change these rules affect their future interactions.
This higher-order aspect of norms, which concerns “rules about rules” or, more precisely, rules
about how to change rules, is a necessary component of any interaction, whether it is explicit—asin the case of constitutions, which stipulate rules by which they can be amended—or implicit. For
instance, proposals to ban an inefficient tradition may systematically be ignored,1 which is one
1

A well-documented example concerns the tradition of footbinding in China: several bans of this tradition wereattempted across the centuries, to no avail until the early twentieth century. See, e.g., Gamble (1943) and Guiso,
Sapienza, and Zingales (2006).

3

particular way of handling proposals, or they may depend on a country’s political stability, which
affects the likely durability of these proposals, should they be accepted.2
To analyze these questions formally, we consider a standard repeated game augmented with aproposal stage, which works as follows. At the end of each period, an agent may be selected at
random to send a message, interpreted as a proposal to change the continuation equilibrium, or
norm, of the game.3 Other agents then send a binary message, interpreted as an acceptance orrejection decision. We are interested in equilibria of this augmented repeated game that obey thefollowing refinement: if enough agents accept a proposal, the continuation equilibrium implements
the proposal; if the proposal is rejected, this triggers a different continuation equilibrium, which
also satisfies the refinement. We call these equilibria contestable norms and study the payoffs thatare sustainable by such norms as the interaction between agents become arbitrarily frequent4 andthe frequency of proposals, q, becomes arbitrarily large per unit of time.
We find that contestable norms may be inefficient. However, this inefficiency is not unrestricted:
we establish sharp bounds on the amount of inefficiency that depends on the underlying structureof agents’ interactions and provide a more nuanced version of the efficient institution hypothesis.
The set of sustainable payoffs greatly depends on the amount of conflict between players in thegame, as illustrated in Figure 1. More precisely, this set is determined by a single payoff vector (onepayoff for each agent) such that all feasible payoffs above this vector can be sustained. This set is
illustrated by Figure 2 for two different stage games. We denote by v the minmax payoff vector¯and by P1 and P2 the highest individually rational payoff vectors for agents 1 and 2, respectively.5
Green areas represent the set of payoffs achievable by contestable norms for various stage games as
the proposal frequency q becomes arbitrarily large, and orange areas contain all additional payoffs
achievable by contestable norms for fixed q. For all q large enough, agent 1’s payoff in a contestablenorm is guaranteed to exceed his payoff from P2 (or fall short by a vanishingly small amount), andvice versa for agent 2.
We find that the inefficiency of contestable norms can increase as one enriches the set of feasible
2

For example, Poyker (2018) finds that efforts to abandon female genital mutilation in African countries are

weaker in countries with unstable regimes, whose rules are more likely to be overturned. Interpreted from ourtheory’s perspective, the stability of political regimes affects how individuals perceive the value of proposing changes
to traditions and, hence, whether such proposals are put forward.
3
Formally, a norm is an equilibrium of the repeated game with negotiation (i.e., the repeated game that includes
in each period a message exchange). See Section 2 for the definition.
4
We consider the set of implementable payoffs as the duration between periods goes to 0 and agents’ discountfactor between consecutive periods goes to 1.
5
A payoff vector is individually rational if it gives each agent at least his minmax payoff.

4

π2

π2
P2

P2

O(1/q)

P1

P1
π1

v
¯

π1

v
¯

Figure 2: Necessary and sufficient conditions for various configurations
payoffs. For example, the prisoner’s dilemma of Figure 1(b) may be viewed as an enriched versionof the pure-coordination game of Figure 1(a), in which the Pareto frontier has been expanded on
both sides of the symmetric efficient point.
Additional action profiles giving high payoffs to some agents and low payoffs to other agents mayhelp sustain inefficient norms by creating new ways of rewarding the former agents at the expenseof the latter ones, should they propose a new norm. Such action profiles increase the potential
for conflict between agents and affect their strategic environment. A higher scope for conflict–in a
sense made precise by our analysis–thus reduces the minimal efficiency of social norms.
A particularly striking instance of this result concerns the introduction or removal of monetarytransfers between agents.6 By nature, a monetary transfer benefits one agent at the expense ofanother, and thus creates an ideal way of introducing disagreements across agents. Consider again
the coordination game of Figure 1(a) and suppose that one adds to this game the possibility ofmaking transfers across agents. This transforms the boundary of the game as in Figure 1(b). Thus,
the set of contestable norms goes from a unique efficient norm to a much larger set that includes
very inefficient norms. Intuitively, the introduction of money allows agents to deter proposals byfining anyone who makes a proposal and rewarding the rejector above and beyond what he would
gain from accepting the proposal. Reciprocally, removing money can improve the efficiency ofsocial norms by reducing the scope for conflict between agents: when moving from Figure 1(b)to Figure 1(a), agents’ utility improves unambiguously regardless of what equilibrium was played
before the move.

6

In the context of our repeated game, “money” should be interpreted as a good that is perfectly transferable

across agents and enters their utility quasi-linearly.

5Norm design
Social norms may be interpreted in a broader context, in which some individuals are not active
players of the game and benefit from the inefficiency that arises from the perspective of the active
players. The active players, whose interactions are explicitly modeled, are part of a larger societyor organization and exert externalities on unmodeled agents. Potential applications include bidders
in an auction (the auctioneer, owner of the good, and/or citizens affected by the outcome of theauction are the inactive players), firms in a cartel, members of a criminal organization, or citizens
that the social planner wishes to control, as in the case of a dictatorship.
From the perspective of norm design, our results have several consequences. First, social perceptions about proposals to change a norm can matter as much as the norm itself. Second, theintroduction or suppression of actions that increase the potential conflict across agents affects theset of norms that can be sustained. The rules that enforce a Pareto-inefficient norm have thevirtue of being self-sustaining in the sense that the designer does not need to intervene once thegame has started. The designer’s role then consists in setting rules at the beginning of the game,specifying how players should interpret deviations in actions and proposals, and possibly adding actions that creates scope for conflict between the agents. We discuss several applications in Section 6.
Stability vs. efficiency
Social responses to proposals have an impact that goes beyond the question of efficiency. They also
affect the stability of social norms, and their very existence. To see this, consider a constitution that
excludes all amendments. Under such a constitution, proposals are dismissed, and the constitution
is perfectly stable (ignoring, for the sake of the argument, any revolution or coup).
Now consider a constitution which can be amended according to some majority rule. If this majority
rule is very permissive (say, a simple majority), the constitution may be repeatedly challenged.
Building on this logic, we construct games in which contestable norms based on the simple majority
rule fail to exist. More generally, increasing the acceptance threshold required for a proposal to pass
has the effect of increasing the set of contestable norms. This is intuitive: constitutions that put
more restrictions on the process leading to successful constitutional amendments are more stable.
However, as the set of contestable norms increases, so does their potential inefficiency. This illustrates a tradeoff between stability and efficiency: norms that are more permissive (proposals areeasier to pass) should be expected to be more efficient but less stable. This tradeoff occurs even in
environments with two players: as the frequency of proposals increases, the set of contestable norms
shrinks and becomes more efficient, but may become empty as the frequency becomes arbitrarily

6large. More precisely, we show that while contestable norms are always guaranteed to exist withtwo players when the proposal frequency per unit of time is fixed at some level q > 0 and the timeinterval between periods, ε, goes to zero, they may fail to exist if the proposal frequency is inversely
proportional to ε. The analysis thus identifies the “right” amount of negotiation frictions underwhich contestable norms are guaranteed to exist.
The Concept of a Norm
In addition to its substantive implications, this paper emphasizes several theoretical aspects ofnorms. First, they are self-enforcing objects, since they must deter norm deviators.7 Second,norms evolve.8 Our modeling approach unifies these two aspects by treating norms as subgameperfect equilibria of an augmented game. Norms are thus doubly dynamic: they can evolve as aresult of actions (for example, a player’s failure to cooperate in some period could trigger a newnorm in which not only players no longer cooperate, but proposals to cooperate are deterred), or
proposals.
As soon as one recognizes the possibility that norms can be challenged by proposals, one mustalso recognize that proposals are richer objects than mere rules of actions: they also specify how
proposals themselves are perceived. Of course, how proposals are perceived could itself be subject
to proposals. A subtle, but necessary implication of considering “meta-rules” about how society
reacts to changes in existing rules, is that the meta-rules themselves could be subject to negotiation:
should there be “meta2 -rules” governing how proposals to change meta-rules are dealt with? Howabout “meta3 -rules” about proposals to change meta2 -rules?
We show that any attempt to close the infinite regress by considering a ‘proposal space’ that is
the limit of proposal hierarchies is bound to fail. Intuitively, such a proposal space would consistof proposals describing how to handle any subsequent proposal, and would thus have to containits power set, which is ruled out by Cantor’s impossibility theorem (see, e.g., Mendelson (1997)).
Fortunately, the infinite regress can be addressed by treating proposals solely on the basis of thecontinuation payoffs that they imply, in a way that parallels the recursive approach of Abreu,
Pearce, and Stacchetti (1990). This consideration explains our focus on norm payoffs rather thanother procedural aspect of norms. However, we also provide an alternative formulation of norms
which coarsens them into a finite set of elements and categorizes proposals so as to circumvent
7

This feature is common is many concepts of norms found in the literature, from economic history (Greif (1994))

to game theory (Kandori (1992)). In sociology, “norms” are social expectations that guide behavior, regardless ofwhether this behavior is individually optimal. Our use of the term is closer to the various meanings that it takes in
economics, and to the concept of “convention” that is sometimes used in sociology (Granovetter (2017)).
8This aspect plays a key role in evolutionary studies of norms, as noted in the literature review below.

7

Cantor’s theorem (Appendix B).

1.1

Related Literature and Interpretation

There is a very large literature on the efficiency and evolution of social norms, which provides perspectives from a wide variety of disciplines that include sociology, anthropology, political science,law and economics, economic history, and evolutionary game theory. Elster (1989) describes numerous examples of inefficient social norms. Economic historians have documented many inefficient
cultural traits and traditions that persist across decades and centuries.9 As a specific example ofa social norm that seems inefficient from the perspective of the agents involved in the norm, butwhich benefits a third party, Burawoy (1979) documents industries in which workers follow a norm
in which producing high quality work is viewed as a sign of masculinity among workers, and notesthat this norm among workers may be benefit their employer more than it does the workers.
There exist several concepts of efficiency, and one may wonder whether footbinding, infibulation,“toxic masculinity” and other inefficient traditions are merely inefficient from the standpoint ofsome welfare aggregate, such as utilitarian welfare, or also in a Pareto sense, which is the conceptof efficiency emphasized in this paper.
Our results provide several perspectives on this distinction. First, if a tradition or institution harms
all but a few beneficiaries, why aren’t these beneficiaries compensated in exchange for abandoning
the inefficient tradition or institution? What mechanism prevents such a change? This paper
provides precisely such a mechanism.10 Second, whether a norm is Pareto inefficient or merely
inefficient for some welfare aggregate is ultimately an empirical question. In this regard, our results
show that one may not conclude that a norm is Pareto efficient simply because it has withstood
the test of time, even in the absence of any standard friction: we show that the transition process
required to implement a Pareto improvement may be impeded by how proposals are perceived
within the norm and by what consequences are triggered when the proposals are rejected. Third,
we show that whenever several Pareto-efficient norms exist, there must also exist sustainable norms
that are Pareto inefficient.11 It follows that if an enduring tradition, institution, or norm seems
inefficient relative to another sustainable norm for some notion of welfare, then either the first norm
9
10

Recent work includes Becker (2018), who studies the persistence of female genital mutilation.
In fact, we show that money or another transferable resources can exacerbate the inefficiency problem by creating

more scope for disagreement across agents.
11
Geometrically, the set of implementable payoffs takes the form of a positive orthant intersected with the set of
feasible payoffs. This implies that it generically includes a set of positive Lebesgue measure in the payoff space and,hence, Pareto-inefficient points.

8

is Pareto inefficient, or there exists another norm that is Pareto inefficient and sustainable.12
Our analysis presents some resemblance with slippery-slope arguments. In a slippery-slope argument, a moderate reform that is preferred to the status quo is not implemented because doing so
could trigger a more radical reform that a blocking coalition dislikes relative to the status quo. As
a result, the status quo may persist even when it is Pareto dominated by the moderate reform. In
such a setting, Pareto-improving outcomes cannot be sustained as a dynamic equilibrium (i.e., themoderate reform is unstable), otherwise they would be implemented.13 In this paper, by contrast,
Pareto-improving outcomes are sustainable by some norms. However, other norms discourage proposals to implement these Pareto improvements by triggering, when rejected, outcomes (akin to
the radical reform in the slippery-slope argument) that harm the proposer and reward the rejectersabove and beyond their gain from accepting the proposal.
Another perspective on norms comes from biology (Maynard Smith and Price (1973)) and is theobject of evolutionary game theory (Sandholm (2010)). According to this perspective, a norm
is typically viewed as a way to play a one-shot game—as opposed to a self-enforcing equilibrium
between forward looking individuals—which evolves in the absence of communication as individuals
adjust their actions to improve their immediate payoffs. There typically exist evolutionarily stableinefficient norms because individuals cannot coordinate their efforts to move to a Pareto-improving
equilibrium.
Our perspective is closer to studies of a “political Coase theorem” (Acemoglu (2003)), which aims
to understand whether institutions, norms, and other agreements are bound to become efficientwhen agents can bargain over outcomes. Importantly, in this literature failures of a political Coasetheorem are obtained in settings that do not presume the existence of exogenous commitment or
enforcement institutions. On the contrary: because they aim to provide foundations for existing
institutions, these studies require any commitment capacity to emerge endogenously from agents’interactions and beliefs.
Starting with Farrell (1983), most of the literature on renegotiation in repeated games (Pearce(1987), Bernheim and Ray (1989), Farrell and Maskin (1989), and Abreu and Pearce (1991))14 does
12

Indeed, either one of these two norms that is Pareto inefficient, or they are both Pareto efficient, in which casethere must exist a third norm that is sustainable and Pareto inefficient.
13See, e.g., Acemoglu, Egorov, and Sonin (2012) for the stability of inefficient policies in a dynamic context.
Although commitment is sometimes offered as a solution, Roesler, Shelegia, and Strulovici (2018) show that thissolution may be ineffective: by allowing society to commit to dynamic policies, one increases the set of alternatives
that society must choose from, and in fact one does so in such a way that Condorcet cycles emerge among dynamic
policies precisely when some commitment policy would improve upon the equilibrium policy without commitment.
14
See also DeMarzo (1988), Asheim (1991), Bergin and MacLeod (1993), Abreu, Pearce, and Stacchetti (1993),

9not model renegotiation by an explicit proposal protocol across players. Instead, renegotiation is
captured by solution concepts that involve efficiency comparisons between various equilibria. In
Farrell and Maskin, an equilibrium is renegotiation-proof if it is not Pareto dominated by any otherequilibrium in a relevant class.15
Several papers study settings in which players explicitly bargain over how to play a one-shot game,including Farrell (1987), Rabin (1994), and Arvan, Cabral, and Santos (1999), and Santos (2000).
Miller and Watson (2013) study a repeated game in which players bargain over relational contracts.
They consider explicit and general protocols of renegotiation in each period. Like Santos (2000),
they assume that in case of a disagreement, the continuation of the game is independent of the events
that occurred during the unsuccessful bargaining stage, such as the identity of the proposers andthe nature of the proposals made during that stage. This No-Fault Disagreement axiom, together
with the availability of unlimited transfers across players leads to efficiency (see Section 7.1). We
explore the consequences of their axiom in Appendix L.16
Busch and Wen (1995) and Abreu and Pearce (2007) have derived explicit or implicit inefficiency
results in models featuring players who can frictionlessly negotiate over continuation plans andhave the ability to commit to efficient long-term plans. Such commitment is ruled out here, whichmakes inefficiency results harder to obtain: In order to sustain an inefficient norm, agents musthave access to continuations that deter them from proposing more efficient norms. When exogenous commitment is available, such continuations are de facto accessible. In our setting, however,these continuations must be contestable and cannot be taken for granted, which makes the general
construction of contestable norms (inefficient or otherwise) more challenging in our setting. In fact,
when exogenous commitment is available, folk theorems can be obtained even for payoff structuresin which contestable norms fail to exist.
Benoı̂t and Krishna (1993), Blume (1994), and Ray (1994).
15
Abreu and Pearce (1991) consider a different criterion for renegotiation-proofness that involves the comparisonof the worst continuation payoffs of the equilibria being compared. They do not model the process of changing thenorm.
16More generally, the literature on relational contracts has sometimes considered the possibility that inefficientagreements be renegotiated. In this literature, the availability of unlimited transfers together implies that the relevant
relational contracts are renegotiation-proof. See, e.g., Kletzer and Wright (2000), Levin (2003). As noted, this result
need no longer hold once renegotiation is modeled explicitly.

10

2

Setting

Our baseline model aims to capture all the ideas discussed in the Introduction as simply as possible.
It features two agents, which may be viewed as two individuals or two homogeneous groups, and asimple protocol of negotiation, in which at most one challenge (a proposal to change the continuationplay) is made in each period.
We consider a repeated game with renegotiation, in which each period features an action stage
followed by a renegotiation stage. In each period, one player (at most) gets to make a proposal,
which may be accepted or rejected before moving to the next period. Section 5 extends the analysis
to more agents, and Appendix E considers more general protocols of proposals, showing that themain results are unaffected by this generalization.
For i ∈ {1, 2}, player i’s stage-game action, ai , lies in a finite set denoted Ai . The vector a = (a1 , a2 )determines the current-period payoffs u(a) = (u1 (a), u2 (a)). A distribution αi over Ai is a mixed

action for i, and α = (α1 , α2 ) denotes the vector of mixed actions for both players. Players put aweight ε ∈ (0, 1) on the current period, which corresponds to a common discount factor δ = 1 − ε.

Each period consists of the following stages:
1) Players observe the realization z of a public randomization device taking values in [0, 1];
2) They simultaneously and privately choose a mixed strategy αi ∈ ∆(Ai ), i ∈ {1, 2}.17 Condi-

tional on the realization z of the public randomization device, players choose their mixed actions
independently of each other;
3) The vector a of actions is observed, and the period’s payoffs are realized;
17

In accordance with current practice, we allow players to use privately mixed strategies. This feature distinguishes

our analysis from some of the earlier work on renegotiation. For example, Farrell and Maskin (1989) assume that
players can observe each other’s mixed strategies, rather than just the realized actions. This distinction can severely
affect the set of weakly renegotiation-proof (WRP) equilibria, the concept introduced by Farrell and Maskin. Appendix K provides an example in which all Pareto-efficient WRP equilibria (which are known to exist) are destroyed
and the repetition of an inefficient stage-game Nash equilibrium is the only WRP equilibrium when mixing is private.
Intuitively, when players observe each other’s mixed strategy, without loss of generality there is a single continuation
payoff vector, conditional on players’ mixed strategies. When mixtures are unobservable, however, there must be
a continuation vector for each possible outcome of the mixture, chosen so as to make each player indifferent acrossall actions in the support of his mixed strategy. Moreover, all of these vectors must belong to the renegotiationproof set. This is problematic because some of these continuations may have Pareto-ranked payoffs, violating weakrenegotiation-proofness. Bernheim and Ray (1989) rule out mixing altogether, focusing their analysis on pure-strategy
equilibria.

114) With probability p < 1, one of the players is given an opportunity to send a message from a set
M, whose cardinality weakly exceeds the cardinality of the continuum. Each player has the sameprobability 2p of being chosen.18 The chosen player may conceal his opportunity to send a message
by remaining silent, or mix between sending a message and remaining silent;5) If i sent a message, player −i decides whether to accept it, possibly mixing between acceptanceand rejection. The resulting decision D−i equals 1 if −i accepts the message and 0 if he rejects it.19

The public history of a period consists of a realization z of the randomization device; an action
vector a; a (possibly empty) message mi sent by one of the players, denoted by i, and if i sent anonempty message mi , an acceptance decision D−i . In addition, each player privately observes the
mixing probability used for each of his decisions.
We focus on public equilibria of this game, which we will sometimes call norms to indicate thatthey concern the enlarged game, and we let S denote the set of all norms. Since messages canalways be ignored regardless of whether they were accepted, the set of players’ expected payoffs

across all norms contains the set V (δ) of continuation payoffs of the underlying repeated gamewithout renegotiation. Moreover, the reverse inclusion still holds, as any norm in S can be replicated without renegotiation: During the renegotiation stage, players’ behavior may affect theircontinuation payoffs in the next period. Before the renegotiation stage, players consider these continuation payoffs as random variables, which depend on which player gets a chance to propose,and (mixed) equilibrium strategies. Since the cardinality of players’ continuation payoffs coincides
with the cardinality of outcomes of the public randomization device, the randomization device cansimulate the outcome of renegotiation, yielding the same distribution over continuation payoffs in
the next period. This proves the following lemma.
Lemma 1 The set of continuation payoffs implemented by all the norms in S coincides with V (δ).
Our main concept is an equilibrium refinement applied to norms.
Let H+ denote the set of all finite public histories in which no off-path proposal was accepted in
the past, and which end after an action stage.20
18

When players have different probabilities of making a proposal, the sufficient conditions are unchanged and thenecessary conditions entail a payoff lower bound on each player that increases with this player’s proposal probability,
consistent with the intuition that a higher proposal probability means increased bargaining power. See Appendix C.
19
The paper’s main results hold as stated when the renegotiation stage includes multiple rounds of negotiation.
See Appendix E.
20
Formally, let H denote the set of all finite public histories ending after an action stage: The elements of H take theform h = (z0 , a0 , m0,i0 , D0,−i0 , . . . , zt , at , mt,it , Dt,−it , zt+1 , at+1 ) for some period t + 1, where mt,it = Dt,−it = ∅12

Definition 1 A norm is contestable if the following hold for every history h ∈ H+ :1. Message Richness Each message m ∈ M is assigned a norm in S, and the payoff vectors
implemented by these norms cover all of V (δ);21

2. Binding Acceptance If a message is proposed and accepted immediately following h, thenorm assigned to it is played from the next period onward.

Definition 1 thus requires that all accepted on-path proposals as well as the first accepted off-path
proposal be implemented. Put differently, Definition 1 means that i) as long as players have notrejected the rule stipulating that any accepted proposal is played, they obey the rule, and ii) the
only way for them to depart from the rule is to make and accept an off-path proposal that violates
the rule.22
Under a contestable norm, players can credibly propose, accept, and thus implement, any alternative
norm. However, a player on the receiving end of any Pareto-improving off-path proposal finds it
optimal to reject it. We emphasize that, under a contestable norm, any accepted proposal is binding
even if the proposal itself is not contestable. Indeed, an accepted proposal governs not only how
players respond to each other’s actions but also how they respond to each other’s proposals. It
is perfectly admissible, for instance, for players to agree at some point to ignore all subsequent
proposals—regardless of the response to these proposals—just as they may agree to ignore specificdeviations in the underlying game.
Contestable norms have a set-theoretic formulation provided in Section 4: We define a convention asa set of norms, and introduce a notion of stability for conventions. A norm is contestable if and only
if the convention consisting of all continuations of the norm—those that follow histories at which
no off-path proposal was accepted—is stable, with a reciprocal statement provided in Section 4.
We also introduce a notion of a “credible” proposal23 and show that restricting the contestability
refinement to “credible” proposals yields the same necessary and sufficient conditions as thoseobtained when all proposals are included in the refinement.
when no one proposed in period t. Then H+ consists of all histories h ∈ H with the following property: For every

period t′ covered by h for which m = mt′ ,it′ is nonempty, either m is in the support of it′ ’s on-path proposals, given
the history h truncated after the action stage of period t′ , or Dt′ ,−it′ = 0, that is, −it′ rejects m.
21
This condition is always achievable: By assumption, M has at least the cardinality of the continuum. Therefore,

each payoff vector v in V (δ) can be mapped to some message m, by assigning to m a norm that implements v.
22
Of course, off-path proposals do not necessarily imply a rejection of this rule.
23
A proposal is credible relative to a convention of norms if any subsequent deviation from the proposal, whether
at the action or the proposal stage, triggers a continuation norm in the convention.

13

3

Main Result

Our main objective is to study, for each level of renegotiation frictions, the set of payoffs achievedby contestable norms as the players’ discount factor δ goes to 1.
To achieve this objective, we adjust the probability p of a renegotiation opportunity in each period
so that it is proportional to the period’s weight ε = 1 − δ. This normalization has the followinginterpretation: If ε represents the duration of each period and p = qε for some parameter q > 0,then the probability that a proposal opportunity arises within one unit of time, that is, within
K = 1/ε periods, is 1 − (1 − p)K = 1 − (1 − qε)1/ε ∼ q. The parameter q thus stands for thefrequency of proposal opportunities per unit time. This normalization is useful for capturing a
non-degenerate effect of renegotiation frictions.24
Given q ≥ 0, a payoff vector X is sustainable at frequency q if there is a threshold ε(X) > 0 suchthat for all ε ∈ (0, ε(X)), X is implemented by some contestable norm associated with discountfactor δ = 1 − ε and renegotiation frequency q. We let V (q) denote the set of all payoff vectors

which are sustainable at frequency q, and we let V̄ = ∩q≥0 V (q). Every payoff vector X in V̄ is
implementable regardless of the renegotiation frequency and is said to be sustainable.

Let v i denote i’s minmax payoff in the stage game,25 and let Pi denote the feasible payoff vector¯
that gives i his maximal payoff among all payoff vectors above the minmax. If several such vectors
exist, the vector whose payoff for −i is the lowest is chosen. The weak individually rational Pareto

frontier—consisting of vectors which are not strictly Pareto dominated—is a piecewise linear curve
joining P1 and P2 .
24

Theorem 1 implies that if the probability p of a per-period renegotiation opportunity is fixed independently ofε, the necessary condition for contestability reduces to the sufficient condition described by the theorem, which is
independent of p. With p independent of ε = 1 − δ, letting δ go to 1 essentially eliminates any renegotiation friction,

regardless of p, as any failure to renegotiate an inefficient norm in the current period will be followed by an opportunity
to renegotiate which comes arbitrarily soon. Moreover, the exploding renegotiation frequency which results from thisassumption also creates an instability as δ goes to 1: For each p > 0, there are examples for which contestablenorms fail to exist as δ goes to 1, as described in Appendix G. Our example features an inefficient stage-game Nashequilibrium as well as Pareto-efficient equilibria which require the threat of harsh off-path punishments, in order tosustain efficient on-path behavior. When renegotiation opportunities arrive at a fixed rate p > 0 per period and δ
goes to 1, the expected length of punishments becomes too short for the Pareto-efficient vectors above the stage-game
Nash equilibrium to be implementable—the gain from a deviation in action is proportional to ε = 1 − δ (the weight

put on the current period), while the duration of any punishment is of order pε (i.e., until it is renegotiated), and isthus smaller than the deviation gain, for judiciously chosen payoffs. The inefficient stage-game Nash equilibrium is
not contestable either, as it is destroyed by any Pareto-efficient proposal.
25
As usual, player −i is allowed to use a mixed strategy to minmax i.

14

π2
P2

v
¯

P1

q
(π1 (P2 ) − v 1 )
2+q
¯

π1

Figure 3: Necessary and sufficient conditions for fixed q
For any payoff vector A, let πi (A) denote the ith component of A. In the statement of the following
theorem, v1 = π1 (P2 ) denotes the first component of P2 and v2 = π2 (P1 ) denotes the second
component of P1 .
Theorem 1 The set of sustainable payoffs satisfies the following conditions:
1. (Sufficiency) If
for i ∈ {1, 2}(1)qπi (A) ≥ v i +(vi − v i )
¯
¯
2+q

(2)

πi (A) > vi
or if A = P1 = P2 , then A is sustainable.
2. (Necessity) If A ∈ V (q), thenfor i ∈ {1, 2}. If A is sustainable, the inequalities in (1) must hold as weak inequalities forboth players.

Condition (1) thus fully characterizes (up to its boundary) the set of sustainable payoffs. The
sufficient and necessary conditions are respectively derived in Appendices A.1 and A.2.26
26

Appendix A.1 focuses on the case P1 6= P2 . If P1 = P2 , players have perfectly aligned interests, as they bothwant to implement P1 and the construction is trivial. When P1 = P2 , the necessary condition selects this vector as

the unique outcome as renegotiation frictions become negligible. If the weak Pareto frontier lies strictly above theminmax values, and consists of a segment giving a constant payoff to one of the players—a degenerate case—thenevery payoff on the frontier is sustainable.

15

Figure 3 illustrates Theorem 1 for a fixed q. The green region represents the payoff vectors known
to be sustainable, and the orange region represents the additional vectors which may be sustainable.
When q = 0 (no renegotiation), the orange region extends all the way to the minmax vector v and¯
we recover the Folk Theorem. As renegotiation frictions become arbitrarily small (q → +∞), theorange region disappears, as the necessary and sufficient conditions become identical (up to theirboundary).
One consequence of Theorem 1 is that V (q) is nonempty for all q ≥ 0, and hence is the set ofsustainable payoffs. In particular, our concept of contestability provides a well-defined counterpoint

to the standard Folk Theorem when renegotiation is introduced into repeated games, allowing us
to compare the impact of renegotiation across different strategic situations of the stage game, fromperfectly aligned interests to extreme misalignments, and to establish for a large class of games thepossibility of sustaining inefficient norms, even when δ is arbitrarily close to 1 and players could
frictionlessly and credibly propose and agree on Pareto-improving proposals.27
As Figures 1 and 2 illustrate, the impact of renegotiation hinges on the alignment structure of thestage game. As the game becomes less cooperative, there is more scope for disagreement among
the players, which can be used to implement a larger set of feasible payoffs. Strategic renegotiation
thus does not destroy the implementability of Pareto-efficient payoffs, but it does not prevent
Pareto-inefficient ones either, and the severity of the inefficiency which may be sustained increases
as players’ interests become more divergent.

3.1

Comparative statics: bargaining frictions and discounting

In standard repeated games with public randomization, it is well known that the set of implementable payoffs gets larger as δ goes to one. This property does not hold with renegotiation.
For example, suppose that the stage game has an inefficient Nash equilibrium that violates thenecessary conditions given in Theorem 1 for q = 21 . For small ε, Theorem 1 implies that this Nashequilibrium payoff, and an open neighborhood around it, is not sustainable. As ε goes to 1, however, there is a norm under which players follow this Nash equilibrium in the first period (before
possibly renegotiating to a Pareto-superior continuation). Since the current-period weight is arbitrarily close to 1, players’ payoffs are arbitrarily close to those of the inefficient Nash equilibrium,
which cannot occur if the value of ε lies below a certain threshold.
27

It should be noted that for fixed ε, there need not exist any contestable norm, just as strongly renegotiation-proof

equilibria (Farrell and Maskin (1989)) and externally consistent norms (Bernheim and Ray (1989)) may fail to exist
for fixed discount factors. Indeed, we have constructed a family of counter-examples for a fixed ε > 0 and all valuesof q > 0.

16

Although discount-factor monotonicity is violated in the presence of renegotiation, a different kindof monotonicity arises here, namely, with respect to negotiation frictions: The more opportunities
players have to renegotiate their norm, the smaller the set of sustainable payoffs. This result holds
for all values of the discount factor and is proved in Appendix F.
Proposition 1 For every fixed ε ∈ (0, 1), the set of sustainable payoffs is decreasing in q.

4

Equivalent notions of stability

This section provides set-theoretic formulations of contestable norms, and then shows that ournecessary and sufficient conditions are unchanged if only a subset of “credible” proposals is taken
seriously.

4.1

Stable Conventions

We introduce a set-theoretic notion of norms, which facilitates the comparison of our concept withexisting notions of renegotiation-proofness (e.g., Farrell and Maskin (1989) and Bernheim and Ray(1989)).
Definition 2 A subset C ⊂ S of norms is a convention if for any s ∈ C as long as no off-path

proposal was accepted, the continuation of s belongs to the convention C.28

The definition implies that if players start with a norm in a convention, then all on-path proposals(whether they are accepted or rejected), as well as rejected off-path proposals, have their continuations in the convention. In particular, deviations in actions are punished within the convention, as
long as no off-path proposal to leave the convention has been accepted. One may informally view
C as a “social norm:” it describes the set of continuations which players perceive as consistent with“business as usual.” A convention can be abandoned only when some player makes an off-path

proposal outside of it that is accepted by the other player. The following notion of stability requiresthat such proposals be taken seriously by the players.
Definition 3 A convention C is stable if, in any period starting with a norm in C, the propertiesof Message Richness and Binding Acceptance from Definition 1 are satisfied.
28

Continuations of s are always defined at the beginning of the corresponding period.

17

Since all on-path continuations of norms in C must all belong to C—by definition of a convention—

stability implies that any Pareto-improving proposal lying outside the convention is rejected withprobability 1; for if it were accepted, stability would require that the proposal be implemented.
Stability thus requires that no player ever has an incentive to make proposals outside of theconvention—hence the terminology. Intuitively, stability is achieved by rewarding a player on thereceiving end of a deviating proposal whenever he rejects it. Crucially, however, this continuation,
which rewards the rejector and deters the proposer, must lie within the convention.
As anticipated, convention stability is equivalent to contestability in the following sense.
Proposition 2 A norm is contestable if and only if it is part of a stable convention.
The proof of this equivalence is straightforward: First, any norm belonging to a stable convention
must be contestable, since all continuations of on-path proposals and rejected off-path proposals lie
in the convention, and thus subject to the stability condition. For the reverse direction, take any
contestable norm and consider the set consisting of this norm together with all of its continuations
at the beginning of periods following histories for which no off-path proposals has been accepted.
This set forms a convention, by construction, which is stable, by contestability of the norm.

Closed vs. open conventions
The conventions defined above are open in the sense that they allow players to depart from theconvention when an off-equilibrium proposal is accepted. This possibility is absent from earlier
studies of renegotiation-proof equilibrium. However, these perspectives can be reconciled: we showthat convention stability can be recast in terms of a purely set-theoretic definition.
Definition 4 A subset C of S is a closed convention if for any s ∈ C, any continuation of s
belongs to C.

The only difference with Definition 2 is that continuations belong to the convention even when offpath proposals are accepted. To offset this change, our earlier definition of stability is translated
into the language of set-theoretic analysis.
Definition 5 A closed convention C is stable if it satisfies the following property: Consider any

norm of C and history at which i gets a chance to make a proposal, and let Ûi denote i’s continuation

payoff. Then, for any proposal with payoff vector U which gives i a payoff πi (U ) > Ûi , there is apayoff vector U ′ of C such that π−i (U ′ ) ≥ π−i (U ) and πi (U ′ ) ≤ Ûi .
18

Theorem 2
1. For any closed convention C c , there exists an open convention C o which has the same payoff set,and vice versa.

2. For any stable closed convention C c , there exists a stable open convention C o which has the same
payoff set, and vice versa.

4.2

Credible proposals

Stability requires that players implement any accepted proposal. When players are used to aconvention C, one may wonder why players should take all proposals seriously, particularly whenthese proposals lie outside of the convention. It turns out that Theorem 1’s necessary and sufficientconditions are identical if one restricts proposals to a much smaller subset of “credible” proposals.
Definition 6 Given a convention C, a norm is C-credible (or just “credible”, when there is noconfusion) if any off-equilibrium play (action, proposal, or acceptance decision) triggers a contin-

uation that belongs to C (for the appropriate stage within the period). A continuation payoff isC-credible if it is implemented by a C-credible norm.

Starting with a norm belonging to some convention C, a credible proposal is such that any futuredeviation triggers a reversal to the convention. For example, if a convention includes a “punishment”
norm that gives low payoff to both players, the convention can support many credible norms by
imposing that any deviation trigger the punishment norm. Since the players may deviate at different
stages of any period, after a deviation they will play the next stage according to the convention.29
In addition, any subsequent deviation (namely, accepting an off-path proposal) may trigger a norm
which does not belong to the convention.
Definition 7 A convention C is credibly stable if:
1. Message C-Richness Each m ∈ M is associated with a norm of S, and each C-credible
payoff is implemented by an C-credible norm associated with some message;

2. C-Binding Acceptance If a message is accepted, whose associated norm is C-credible, theassociated norm is implemented.

29

For example, if a player deviates during the action stage, the players will then engage in renegotiation under therules prescribed by the convention. If a player deviates during the renegotiation stage by sending the wrong message
or making the off-path acceptance choice, then in the next period the players will choose their actions according to
the convention.

19

Definition 7 is clearly more permissive than Definition 3, because it imposes the refinement over asmaller set of proposals. However, we have the following result.
Theorem 3 The set of points sustained by credibly stable conventions obeys the necessary andsufficient conditions of Theorem 1.
The proof is straightforward: first, any stable convention is credibly stable since the latter mustsustain fewer proposal challenges than the former. Our construction for the sufficiency condition
thus still applies. Second, the proposals used in Appendix A.2 to derive the necessary conditionsof Theorem 1 are credible, as shown in this appendix. The necessary conditions are thus identicalfor stable and credibly stable conventions.

5

Arbitrary number of players

The analysis so far has focused on two players, a common restriction to study renegotiation in
repeated games.30 Extending the analysis to more players raises new conceptual issues. Can
proposals be targeted toward a subset of individuals? What happens if only a subset of the players
accepts the proposal?
This section explores some of these issues, allowing for an arbitrary number, n, of players. Aftera player has made a proposal, other players vote on accepting the proposal. We assume that thevote is simultaneous and show in an extension that sequential voting does not alter our conclusions(Appendix J.2).
The setting builds on the two-player setting, modified as follows. At the proposal stage, each player
i has the same probability np (p < 1) of being chosen to send a message. The renegotiation friction
parameter q is still defined by p = qε. This player may choose to conceal his opportunity to send amessage. If i sends a message, other players vote on whether to accept it, resulting in a vector of
acceptance votes D−n ∈ {0, 1}n−1 .31
With multiple players voting on a proposal, we consider the supermajority rule: a proposal isaccepted if at least L players support it, with L ∈ {⌊N/2⌋, . . . , N − 1}.32 Each fixed value of L
30

E.g., Farrell and Maskin (1989), Benoı̂t and Krishna (1993), and Santos (2000). Abreu, Pearce, and Stacchetti(1993) focus instead on symmetric equilibria.
31
As in the two-player case, if no message is sent the identity of a sender is arbitrarily chosen and the empty
message is assumed to be rejected by everyone else.
32
The lower bound N/2 is natural to interpret the voting as a supermajority rule, but not necessary for the analysis.
The upper bound N − 1 corresponds to the unanimity rule, keeping in mind that the proposer is not voting over his

20defines a concept of contestable norm refinement, as in the two-player case. Let H+ denote the setof all finite public histories ending after an action stage such that no off-path proposal has been
accepted by the supermajority.
Definition 8 A norm is contestable if the following holds for any history h ∈ H+ :1. Message Richness Each message m ∈ M is assigned a norm of S. The payoff vectors
associated to these norms cover the set V (δ);

2. Binding Acceptance If a message is accepted by at least L voters, the norm assigned to itis played from next period onward.

As with with most of the literature on voting, we assume that if a proposal fails the vote, thecontinuation is independent of the exact number, or identity, of the voters who voted to reject it.33

Definition 9 A contestable norm s is simple if, for any history h ∈ H+ , when player i makes a
proposal mi , there are two continuations, depending on whether mi passes or fails the supermajority
vote.
In the analysis that follows, we focus to fix ideas on the unanimity rule (L = N − 1). This rule iseasier to interpret (since no player is “forced” to espouse a new norm that he has not chosen), but
the analysis of other supermajority rule is qualitatively the same. As usual with voting games, we
eliminate weakly dominated strategies.
Assumption 1 A player votes in favor of the proposal if it gives him a strictly higher payoff thanits continuation payoff in case of a rejection.
We also assume that the individually-rational payoff set has full-dimension, which guarantees that
the Folk Theorem holds for the underlying repeated game (Fudenberg and Maskin (1986)).
The key to characterizing contestable norms is to determine each player i’s worst possible punishment if he makes an unprescribed proposal. Suppose that i makes a proposal with corresponding
payoff vector C, and let V denote the set of payoff vectors across all continuations of our candidate

contestable norm, s, following histories at which no off-path proposal has been accepted by the su-

permajority. (All payoffs in V are estimated at the beginning of a period.) If s is contestable, C will
own proposal.
33
The case in which continuations can depend arbitrarily on the voting profile in considered in Appendix J.1.

21

be implemented if all players accept i’s proposal. If anyone rejects the proposal, norm simplicity
implies that there is a single payoff vector in V, D(C), which will be realized. If D(C) gives πj (C)or more to at least one player j 6= i, this player will refuse the implementation of C, and the norm

implementing D(C) will be played.

Following any proposal with payoff C by player i, the worst punishment in V for player i minimizes
i’s payoff over the set:34

D(C, V) = {D(C) ∈ V : ∃j 6= i : πj (D(C)) ≥ πj (C)}.
Let πi (C, V) denote i’s payoff under this worst punishment.
Viewing πi (C, V) as a function of C, one can then find the proposal with a continuation C(V) which

maximizes i’s payoff at the worst punishment: C(V) = arg maxC {πi (C, V)}, and the corresponding
payoff, πi (V), for i. The payoff C(V) may be viewed as follows. The most efficient way of preventing
player i from making a non-prescribed proposal is by implementing his worst punishment. Anticipating this, if player i deviates from his prescription, he may as well choose the optimal proposal,
which gives the payoff C(V).
These observations lead to two iterative procedures starting from the set F of strictly individually-

rational payoffs in the stage game, which are described in Appendix I and shown to converge andgenerate distinct sets VN and VS that capture necessary and sufficient conditions for a payoff to besustainable. 35 The resulting sets VN and VS are both positive orthants, whose vertices give lower

bounds on players’ payoffs (calculated at the beginning of period) under both procedures, and are
denoted πmin,i (VS ) and πmin,i (VN ), for any player i. The payoff πmin,i (VN ) satisfies the following

condition:
πmin,i (VN ) =nvi + qπi (VN )
n+q

(3)

Similarly, we have πmin,i (VS ) = πi (VS ).
We can now state the main result of this section. Let P denote the Pareto frontier of the feasible
payoffs in the stage game and, for each i, P−i denote any individually-rational payoff vector of P

which minimizes i’s payoff. Also let R denote the open positive orthant whose vertex is the vector(πi (P−i ))ni=1 . In the two-player case, this set characterized the sufficient conditions for sustainablepayoffs. With n > 2 players, we show that R still consists of sustainable payoff vectors, though

it might not include all of them. The theorem is stated for the case in which the Pareto frontier
34
35

For the existence of a worst punishment, the set V needs to be closed. Our construction will satisfy this condition.
Intuitively, each player i can guarantee to get his worst punishment when having a chance to propose, thus one

can remove sufficiently low continuation payoffs from the set F sequentially for all players.

22

supports a non-zero range of payoffs for each player.36
Theorem 4 i) Any sustainable payoff37 lies in VN ; ii) generically, any payoff in the interior of VS

is sustainable; iii) any payoff in the interior of R is sustainable.

Theorem 4 implies that sustainable payoffs always exist: due to the full dimensionality condition,
the interior of R is non-empty. In addition, fixing players’ action sets A1 , ..., AN , any stage gameis characterized by the set of payoff vectors {u(a)}, a ∈ A1 × ... × AN ; that set can be represented
as a vector in a Euclidean space (with dimensionality equal to the total number of different action

profiles times the number of players). For an open dense set of that Euclidean space, that is, for“generic” games, any payoff in the interior of VS is sustainable. As in the two-player case, the sets

defined by the necessary and sufficient conditions converge to each other as renegotiation frictions
vanish (see Appendix I.3). Moreover, these two sets are non-decreasing, according to the inclusion
order, in the number L that determines the supermajority rule.
Proposition 3 The sets VS and VN converge to each other as q goes to infinity. The sets are
non-decreasing in L.

When players respond sequentially to a proposal, the same result obtains.38
Since more permissive voting rules (i.e., lower L) reduce the set of contestable norms, it is natural
to ask when this set is nonempty—we already know that it is the case when unanimity is required toaccept a proposal. In Appendix J.3, we provide various examples showing that contestable norms
may or may not exist when proposals are decided according to the simple majority rule.

6

Applications and interpretation: a novel mechanism for miscoordination and inertia

Theorem 1, and the inefficiencies that it allows, hold even though i) the game has complete information; ii) agents’ discount factor is arbitrarily close to 1; iii) agents can exchange messages at
36

When the feasible set has a unique Pareto-efficient point, this point is the only sustainable payoff. When atleast two players have multiple payoffs on the Pareto frontier, the set of sustainable payoffs is always a non-empty
full-dimensional orthant. When all points of the Pareto frontier give the same payoff to all but one player, any payoffon the Pareto frontier is sustainable.
37
Sustainable payoffs are defined as in the two-player setting.
38
See Appendix J.2. Sequential and simultaneous voting are in fact equivalent under the assumption, standard in
the voting literature, that a player votes for the proposal if it gives him higher expected payoff than rejecting it.

23

arbitrarily high frequency, and these messages of are unambiguously understood by all agents as
proposals to implement specific norms; and iv) accepted agreements are binding.
Inefficient payoffs are sustained by rules which discourage proposals, including Pareto-improving
ones, and that may be viewed as part of a social norm among the players. Although such a social
norm seems undesirable from the perspective of the players, it may be interpreted in a broader
context, in which the designer of the norm is not an active player of the game and benefits fromthe inefficiency that arises from the perspective of the players.
In particular, the agents who are explicitly modeled may be part of a larger society or organizationthat exerts externalities on other economic, unmodeled agents.
Potential applications include bidders in an auction, firms in a cartel, members of a radical organization, or simply citizens which the social planner wishes to control, as in the case of a dictatorship.
In these applications, high payoffs for these players mean that they are colluding, polluting, shirking, or, more generally, adversely affecting individuals who are included in the social planner’s
objective.
Viewed from this perspective, the rules which enforce a Pareto-inefficient norm have the virtue ofbeing self-sustaining, in the sense that the social planner does not need to intervene once the gamehas started. There is no need for external monitoring or punishment.
Consider, for instance, a regulator who wishes to prevent collusive pricing in an oligopolistic market. Of course, if the firms can be given self-sustaining rules that prevent collusion, such a design ischeaper for the regulator than explicitly monitoring the firms and administering the punishments.
Likewise, the manager of an administrative office who is facing high costs of monitoring his employees may wish to create a social norm between them which makes the employees to exert higheffort and under which an employee’s proposal to shirk is rebuked by other employees and thwarted
without requiring the manager’s intervention. The designer’s role consists of setting the rules at the
beginning of the game, specifying how players should interpret deviations in actions and proposals.
Once this common understanding is reached, the designer completely withdraws from the game,and the players enforce the rules themselves by punishing one another if one of them ever deviatesfrom these rules.
Of course, proposal-deterring norms do not have to be designed by anyone. The players may simply
be trapped in a norm with this feature—perhaps what remains of an unmodeled evolution of past
behavior. An example may be “acting tough” and discouraging any suggestion to “soften up” evenwhen doing so would in fact lead to a Pareto improvement.

24Suppose that the designer of a norm can also make new actions available to the players (such as
snitching on one another, as in the prisoner’s dilemma). If he or she introduces actions that increase
the misalignment between the players increases the maximal inefficiency of sustainable outcomes,
and thus potentially also the (unmodeled) payoff of the norm’s designer. From a designer’s perspective, creating actions which benefit only one player but not others facilitates the deterrence ofcollusive proposals.
We sketch two applications below, in which norms are Pareto inefficient from the players’ perspective
but beneficial to some social planner whose sole involvement in the game may be to design the norm
governing players’ interactions.
Cournot competition
Consider two symmetric firms which, under Cournot competition, produce more than the monopolistic output. These firms could achieve a higher profit by each producing half of the monopolistic
output. However, proposals to move away from the current equilibrium may be subject to a normthat treats any such proposal as corrupt behavior. The firm on the receiving end of such a proposal
could reject it, triggering a continuation in which, say, the rejector produces the Stackelberg leader’soutput in each period and the proposer produces the Stackelberg follower’s output. These outputs
give the proposer a lower payoff than that in the competitive equilibrium, and his competitor ahigher payoff than half of the monopoly’s profit.39
Political inertia and dictatorship
Consider an authoritarian regime facing the risk of a revolution. In this regime, citizens may be
exploited through high taxes, expropriation, and other channels. Faced with this situation, various
citizen factions may attempt to persuade others to start a revolution (an off-path proposal). If the
proposal is accepted, the authoritarian regime falls, which (ideally) increases the well-being of all
the citizens. However, the regime may impose a norm that thwarts this threat by rewarding anyone
who reveals the plot and punishing its instigator. Importantly, all rewards and punishments areadministered by the citizens, without the dictator getting involved or even monitoring them. This
provides a novel, completely endogenous explanation for the stability of dictatorships, even when
citizens could credibly coordinate to overthrow the regime. It exposes the limits of attempts tocoordinate when the norm in place anticipates such attempts.
39

The punishment for the proposer, that is, the Stackelberg equilibrium, is inefficient. However, it suffices toincentivize a rejection to the proposal and thus deter a Pareto-improving proposal.

25

The dynamic nature of social norms
Our analysis emphasizes the dynamic nature of social norms, particularly with regard to how“innovative” proposals are perceived. For instance, starting from a Pareto-inefficient norm, a first
proposal to increase cooperation and increase both players’ payoffs may be perceived as acceptable
and actually implemented. To be sustained, however, this cooperation may require the threatof off-path punishment stages. During the punishment stages the kind of cooperation originallyproposed is no longer acceptable.

7

Conclusion

This paper provides a model of contestable norms in which proposals to overturn these norms are
explicitly considered as part of an enlarged dynamic game. Contestable norms are equilibria of thisenlarged game: they prescribe not just which actions to take but which proposals to make and how
to react to any proposal to change the incumbent norm. We characterize the set of contestable norm
payoffs as agents’ discount factor goes to 1. Our model is simple in at least three respects: i) the
protocol of negotiation, which consists of a one-shot proposal/acceptance stage in the stage game;ii) the concept of contestable norms, which is a single, straightforward equilibrium refinement; andiii) the characterization of the set of sustainable payoffs, in terms of a simple orthant intersectedwith the set of individually rational payoffs. Our results results are unchanged if the negotiation
protocol is expanded, or if the refinement is restricted to a set of credible proposals. Finally, no
assumption was imposed on the payoffs of the stage game beyond a standard full-dimensionality
condition for the set of feasible payoffs when there are three or more agents.

7.1

Relation to Models of Bargaining over Equilibria

When renegotiation is viewed as a strategic interaction, renegotiation-proof equilibria may contain Pareto-ranked continuations. This happens when Pareto-improving proposals are deterred bypunishing the proposer and rewarding the rejector beyond the proposal. This idea also underlies
the results of Santos (2000), who considers players bargaining over which equilibrium to play in a
one-shot game, as well as Miller and Watson’s (2013) Theorem 1, which shows that renegotiation
has no restrictive power when it must satisfy only their “Internal Agreement Consistency” Axiom.
That theorem and ours differ in two important ways. First, their argument requires unboundedtransfers: To punish a proposer, say player 1, one requires him to make a very large transfer toplayer 2 in the next period. If the weight of a single period is ε, the transfer must be of order 1ε ,26hence the necessity of unbounded transfers as ε goes to zero. These large transfers permit player
1’s continuation value to jump immediately from some punishment payoff v10 to a higher continuation value v1 , which is easy to implement. Second, in each period the transfer stage takes place
before the action stage (and, in particular, is distinct from it). If player 1 deviates by making asmaller transfer than prescribed, it suffices to have him minmaxed by the other player and resetthe continuation value to v10 for the next period in order to punish this deviation.
When stage-game payoffs are bounded, as in our setting, the continuation value of a player cannot
jump by an ε-independent amount. The equilibrium construction must thus keep track of continuation values and make sure that they are implementable at all stages and following all deviations. In
the absence of a separate transfer stage, moreover, if player 1 deviates in action when implementing
v10 , his continuation value must fall below v10 . Implementing this lower value may be difficult or even
impossible. In fact, it is this impossibility which creates new restrictions on the set of sustainablepayoffs and destroys the Folk Theorem obtained in Miller and Watson’s Theorem 1.

7.2

Extensions

Two important assumptions were maintained throughout the paper: First, the agents’ physicalenvironment does not change over time. Second, all proposals and decisions are public. The first
restriction is made for convenience: one could apply our framework and concepts to dynamic games
in which payoffs evolve over time. A crude way of conceptualizing within our model is to assume
that the analysis starts in some period, labeled ‘1’, which immediately follows some unexpected,
one-time payoff shock affecting agents’ payoffs. Agents may thus have inherited a norm at time 1
that resulted from past interactions, and which may have been efficient, say, for the previous payoffs
but become inefficient after the payoff shock.40 The restriction to publicly observed proposals andagreements, which becomes relevant when there are three or more agents, is much more significant.
With an arbitrary number of agents, several new questions emerge: Could a subset of agents makea partial agreement, possibly at the expense of other agents? What would this imply for otheragents’ strategies? Could such agreements be private and gradually discovered by the remaining
agents? Exclusive negotiations of this kind are common, for instance when agents are divided
into relatively homogeneous groups within which negotiation is easier or when they are engaged in
specific relationships such as those that arise in supplier chains. They may also arise in community enforcement models, in which matching parties may engage in local renegotiation to alleviate
40

For example, suppose that players face a coordination game with two actions, A or B. At time 0 a payoff shock

occurs. Both actions are equilibria of the underlying game before and after the shock; coordinating on A was played
and was Pareto efficient until time 0 while coordinating on B becomes efficient after the payoff shock.

27

punishments (Ali, Miller, and Yang (2016)). When agreements are public, these questions relate
to the study of coalition formation and coalition-proof equilibria (Bernheim, Peleg, and Whinston(1987)). Even if agents can make meaningful private agreements, such agreements may generate
asymmetric information among players and create well-known challenges to analyze the formation
and behavior of subsequent coalitions, as pointed out by Crémer (1996) and, in the context of
auctions, by McAfee and McMillan (1992), and Caillaud and Jehiel (1998). See also Che and Kim(2006) for a more recent treatment of this issue. Understanding how private or partial agreementsof this kind affect the entire group and shape social norms seems a particularly interesting direction
for future.

References
Abreu, D., Pearce, D. (2007) “Bargaining, Reputation, and Equilibrium Selection in RepeatedGames with Contracts,” Econometrica, Vol. 75, pp. 653–710.
Abreu, D., Pearce, D. (1991) “A perspective on renegotiation in repeated games,” in R. Selten(ed.), Game Equilibrium Models, Springer Berlin Heidelberg.
Abreu, D., Pearce, D., and E. Stacchetti (1990) “Toward a Theory of Discounted RepearedGames with Imperfect Monitoring,” Econometrica, Vol. 58, pp. 1041–1063.
Abreu, D., Pearce, D., and E. Stacchetti (1993) “Renegotiation and Symmetry in RepeatedGames,” Journal of Economic Theory, Vol. 60, pp. 217–240.
Acemoglu, D. (2003) “Why Not a Political Coase Theorem? Social Conflict, Commitment andPolitics,” Journal of Comparative Economics, Vol. 31, pp. 620–652.
Acemoglu, D., Egorov, G., and K. Sonin (2012) “ Dynamics and Stability of Constitutions,
Coalitions, and Clubs,” in American Economic Review, Vol. 102, pp. 1446–1076.
Acemoglu, D., Johnson, S., and J. Robinson (2005) “ Institutions as a Fundamental Causeof Long-Run Growth,” in Handbook of Economic Growth, Ch. 6, pp. 385–472.
Ali, N., Miller, D., and D. Yang (2016) “Renegotiation-Proof Multilateral Enforcement,”
Working Paper, Pennsylvania State University and University of Michigan.
Arvan, L., Cabral, L., and V. Santos (1999) “Meaningful cheap talk must improve equilibrium
payoffs,” Mathematical Social Sciences, Vol. 37, pp. 97–106.

28

Asheim, G. (1991) “Extending Renegotiation-Proofness to Infinite Horizon Games,” Games andEconomic Behavior, Vol. 3, pp. 278–294.
Becker, A. (2018) “On the Economic Origins of Female Genital Cutting,” Working Paper.
Benoı̂t, J.-P., Krishna, V. (1993) “Renegotiation in Finitely Repeated Games,” Econometrica,
Vol. 61, pp. 303–323.
Bergin, J., MacLeod, B. (1993) “Efficiency and Renegotiation in Repeated Games,” Journal of
Economic Theory, Vol. 61, pp. 42–73.
Bernheim, B.D, Peleg, B., Whinston, M. (1987) “Coalition-Proof Nash Equilibria I. Concepts,” Journal of Economic Theory, Vol. 42, pp. 1-12.
Bernheim, B.D., Ray, D. (1989) “Collective Dynamic Consistency in Repeated Games,” Gamesand Economic Behavior, Vol. 1, pp. 295–326.
Blume, A. (1994) “Intraplay Communication in Repeated Games,” Games and Economic Behavior, Vol. 6, pp. 181–211.
Burawoy, M. (1979) “The Anthropology of Industrial Work,” Annual Review of Anthropology,
Vol. 8, pp. 231–266.
Busch, L.-A., Wen, Q. (1995) “Perfect Equilibria in Negotiation Model,” Econometrica, Vol. 63,
pp. 545–565.
Caillaud, B. and Jehiel, P. (1998) “Collusion in Auctions with Externalities,” Rand Journalof Economics, Vol. 29, pp. 680–702.
Che, Y.-K., Kim, J. (2006) “Robustly Collusion-Proof Implementation,” Econometrica, Vol. 74,
pp. 1063–1107.
Coase, R.H. (1960) “The Problem of Social Cost,” Journal of Law and Economics, Vol. 3, pp. 1–
44.
Crémer, J. (1996) “Manipulations by Coalitions Under Asymmetric Information: The Case of
Groves Mechanisms,” Games and Economic Behavior, Vol. 13, pp. 39–73.
DeMarzo, P. (1988) “Coalitions and Sustainable Social Norms in Repeated Games,” mimeo,
Stanford University.
Elster, J. (1989) “Social Norms and Economic Theory.” Journal of Economic Perspectives, Vol. 3,
pp. 99–117.
29

Farrell, J. (1983) “Credible Repeated Game Equilibrium,” Unpublished Manuscript.
Farrell, J. (1987) “Cheap Talk, Communication, and Entry.” Rand Journal of Economics,
Vol. 18, pp. 34–39.
Farrell, J., Maskin, E. (1989) “Renegotiation in Repeated Games,” Games and Economic
Behavior, Vol. 1, pp. 327–360.
Fudenberg, D., Maskin, E. (1986) “The Folk Theorem in Repeated Games with Discounting
or with Incomplete Information,” Econometrica, Vol. 54, pp. 533–554.
Gamble, S. (1943) “The Disappearance of Foot-Binding in Tinghsien,” American Journal of
Sociology, Vol. 49, pp. 181–183.
Granovetter, M. (2017) Society and Economy: Framework and Principles, Harvard University
Press.
Greif, A. (1994) “Cultural Beliefs and the Organization of Society: A Historical and Theoretical Reflection onCollectivist and Individualist Societies,” Journal of Political Economy, Vol. 102,
pp. 912–950.
Guiso, L., Sapienza, P., Zingales, L. (2006) “Does Culture Affect Economic Outcomes?,”
Journal of Economic Perspectives, Vol. 20, pp. 23–48.
Kandori, M. (1992) “Social Norms and Community Enforcement,” Review of Economic Studies,Vol. 59, pp. 63–80.
Kletzer, K., Wright, B. (2000) “Sovereign Debt as Intertemporal Barter,” American Economic
Review, Vol. 90, pp. 621–639.
Levin, J. (2003) “Relational Incentive Contracts,” American Economic Review, Vol. 93, pp. 835–
857.
Maynard Smith, J., Price, G.R. (1973) “The Logic of Animal Conflict,” Nature, Vol. 246,
pp. 15–18.
Mendelson, E (1997) Introduction to Mathematical Logic, 4th ed. Chapman & Hall, London.
McAfee, R.P., McMillan, J. (1992) “Bidding Rings,” American Economic Review, Vol. 82,
pp. 579–599.
Miller, D., Watson, J. (2013) “A Theory of Disagreement in Repeated Games with Bargaining,”
Econometrica, Vol. 81, pp. 2303–2350.
30

North, D., Thomas R.P. (1973) The Rise of the Western World: A New Economic History,
New York: Cambridge University Press.
Pearce, D. (1987) “Renegotiation-Proof Equilibria: Collective Rationality and Intertemporal
Cooperation,” Cowles Foundation Discussion Paper, No. 855.
Poyker, M. (2018) “Regime Stability and the Persistence of Traditional Practices,” Working
Paper.
Rabin, M. (1994) “A Model of Pre-Game Communication,” Journal of Economic Theory, Vol. 63,
pp. 370-391.
Ray, D. (1994) “Internally Renegotiation-Proof Equilibrium Sets: Limit Behavior with Low Discounting,” Games and Economic Behavior, Vol. 6, pp. 162–177.
Roessler, C., Strulovici, B., Shelegia, S. (2018) “Collective Commitment,” Journal of Political Economy, Vol. 126, pp. 347–380.
Sandholm, W. (2010) Population Games and Evolutionary Dynamics, Cambridge: The MIT
Press.
Santos, V. (2000) “Alternating-Announcements Cheap Talk,” Journal of Economic Behavior &Organization, Vol. 42, pp. 405–416.

A

Proof of Theorem 1

A.1

Sufficient Conditions

We construct, for any payoff vector (hereafter, “point”) A satisfying (1) and ε sufficiently small
a norm s ∈ S which implements A and is contestable at all frequencies q ≥ 0. The construction

is based on points A1 and A2 such that Ai gives i his worst possible payoff among all contestable
continuations of s (that is, continuations following histories at which no off-path proposal was
accepted).41 When i’s continuation payoff is at an ε-independent distance above his payoff from
Ai , it is easy to incentivize him to follow any prescribed action, since any deviation provides a
maximal gain of order ε and can be punished by implementing Ai . One challenge is to choose Ai sothat i is adequately incentivized near Ai . The second important points of the construction are D1
and D2 , which serve to deter off-path proposals. These points are chosen to be Pareto efficient, and41

Unless stated otherwise, points refer to expected payoffs at the beginning of the current period.

31set so that any relevant off-path proposal by i may be deterred by having −i reject the proposal andhave Di be implemented instead. Di must therefore be chosen so that −i is sufficiently rewarded,

and i punished, for any proposal that i may entertain.
Preliminaries

Since the message space has the cardinality of the continuum, we can without loss of generality
identify it with the set V (δ) of feasible payoff vectors, a full dimensional subset of R2 .42
We interpret each message X ∈ V (δ) as a proposal to move to a continuation whose expected payoff

is X. For any point X implemented by some contestable continuation of the candidate norm s, letsX denote the corresponding continuation.43
To distinguish players’ expected payoffs at each stage of each period, we introduce the following
notation. Given a subset L of norms, let U (L) ⊂ R2 —or just U , when there is no confusion—denotethe set of expected payoffs for the players across all possible norms in L, computed before public
randomization. V is defined identically but computed after the realization of the randomization

device z. U is thus included in the convex hull of V. Finally, let W consist of continuations

payoffs after actions and payoffs are observed and incurred in the current period, but before theproposal stage. Each element of W is a convex combination of three expected payoff vectors

corresponding to the following events: player 1 gets to make a proposal, player 2 does, or no one
does. Because elements of W define continuation payoffs excluding the current period, to make themcommensurate with payoffs in U , we evaluate them at the next period (i.e., ignoring the discountfactor between the two periods). With this convention, payoffs in W are convex combinations ofelements of U .

Elements of U , V, and W are points of two-dimensional sets. Recall that for any payoff vector X,
we let πi (X) denote the ith component of X.

ProofFor each player i, there are two configurations to consider, depending on whether i’s minmax payoffv i is less than or equal to πi (P−i ). We first consider the case in which both players are in the former¯
configuration.
Case 1: v 1 = π1 (P2 ) and v 2 = π2 (P1 ). Consider any point A satisfying (1). For ε small¯¯
1enough, the points A1 and A2 with coordinates (π1 , π2 )(A1 ) = (v 1 + ε 2 , π2 (A)) and (π1 , π2 )(A2 ) =¯
1(π1 (A), v 2 + ε 2 ) are individually rational and such that π1 (A1 ) < π1 (A) and π2 (A2 ) < π2 (A). The¯
42

If M’s cardinality exceed the cardinality of the continuum, we assign the minmax payoff to all superfluous

messages.
43
There is only one continuation for each payoff X considered below, so sX is well defined.

32

π2
P2 D
1

C11
A1 B11
B12

A
C12

C21
B21

v
¯

C22
B22
A2

D2
P1

π1

Figure 4: Construction of a self-sustaining norm
norm sA1 implementing A1 is constructed as follows (sA2 has a similar construction):
1) Action stage: player 2 minmaxes player 1, possibly mixing between several actions {a2j }j . Player
1 best responds by a pure action a1,minmax achieving his minmax payoff.

1a) If no deviation in action is observed, the continuation payoff vector B1j ∈ W is a function of 2’s

realized action, a2j , and is chosen so that i) 2 is indifferent between all actions a2j used to minmax
1, ii) 1’s continuation payoff is independent of j (so the vectors {B1j }j all lie on the same verticalline as shown on Figure 4), and iii) the promise-keeping condition is satisfied for both players. In
particular,
π1 (A1 ) = εv 1 + (1 − ε)π1 (B1j )(4)¯
for all indices j corresponding to some action a2j in 2’s minmaxing distribution. In particular, thepoints B1j all lie within an ε-proportional distance of A1 .
1b) If 2 deviates in action (i.e., chooses an action outside of the mixture used to minmax 1), thecontinuation payoffs jump to the point A2 , mentioned above, which gives 2 her lowest possible
payoff.44 For small ε, this punishment suffices to incentivize 2 because any deviation gain is oforder ε whereas π2 (A2 ) is arbitrarily close to 2’s minmax payoff, causing 2 an ε-independent loss.
1c) If 1 deviates in action, disregard this. Such a deviation is suboptimal since 1 was prescribed to44More precisely, players start implementing the payoff B21 , which is the analogue of the point B11 , following theimplementation of A2 .

33

best respond to being minmaxed by 2.
2) Proposal stage: the norm sB1j implementing B1j is as follows: if either 2 gets a chance to makea proposal, or no player does, the play returns to sA1 . 2 is prescribed to remain silent. If 1 getsa chance to make a proposal, he proposes a continuation sC1j whose corresponding payoff vector
C1j lies on the line going through A1 and B1j and is chosen so as to satisfy the promise-keeping
conditionppπ1 (B1j ) = 1 −π1 (A1 ) + π1 (C1j )
2
2

(5)

Player 2 is prescribed to accept proposal sC1j . The points {C1j }j give the same payoff to 1,
independently of j. Their implementation is described in 3) below.

2a) If 1 proposes any continuation other than sC1j that improves his payoff, he is punished by acontinuation sD1 —triggered if player 2 rejects 1’s proposal—chosen such that i) π1 (D1 ) < π1 (C1j )and ii) 2 prefers π2 (D1 ) to her payoff under 1’s proposal sC1j . Precisely, D1 is defined as the pointof the Pareto frontier that gives 1 a payoff ofπ1 (A1 ) + π1 (C1j )(6)
2√
As explained shortly, 1’s payoff at C1j is of order ε above what 1 gets at A1 or B1j . If 1 proposesa plan that makes him worse off than sC1j , 2 accepts it if only if improves her payoff. Of course,such a proposal never arises in equilibrium.
2b) If 2 deviates by making a proposal or rejecting 1’s offer to move to C1j , players jump to
the continuation sD2 , which punishes 2’s deviation (in the former case, sD2 is assigned as thecontinuation arising when 1 rejects 2’s proposal). No proposal simultaneously gives 1 more thanhis payoff at sD2 and 2 more than his payoff from sA1 .
3) Next periods: the norm sC1j is implementable because it gives 1 a payoff of order√

ε above what

A1 and B1j give him. A deviation in action by 1 brings a gain of order ε and is punished by a drop√of order ε in 1’s continuation payoff, and is thus suboptimal, for ε small enough. sC1j can be
implemented by a deterministic sequence of actions keeping players’ continuation payoffs within adistance Kε from C1j . The rules implementing this sequence are simple: play a deterministic action
profile keeping continuation payoffs ε-close to C1j and do not allow any proposal. If 1 deviates inactions, jump to one of the continuations sB1j ; if he deviates in proposals, jump to sD1 if 2 rejects
this offer. A similar rule is applied for player 2, who has even more to lose from a deviation.
4) The point D1 also gives 1 a payoff of order√

ε above A1 and B1j . sD1 can therefore be

implemented similarly to sC1j . Again, any proposal is ignored.

34

√
O( ε)

D1

O(ε3/2 )
C11

√
O( ε)

A1

B11

B12
√
O( ε)

C12

minmaxfor Player 1

Figure 5: Construction details
The construction is represented on Figure 4. The magnitudes of payoff differences between the
points involved in the construction are indicated on Figure 5.
We verify the claim that all C1j ’s lie at a√ε-proportional distance to the right of A1 . From (4)and (5), we have
π1 (A1 ) = εv 1 + (1 − ε)π1 (Bj ) = εv 1 + (1 − ε)
¯
¯

h
i
qε 
qε
1−
π1 (A1 ) + π1 (C1j )2
2

Ignoring the terms of order ε2 and higher, this implies that


q 
qε
π1 (A1 ) = εv 1 + 1 − 1 +ε π1 (A1 ) + π1 (C1j ).
¯
2
2
Subtracting π1 (A1 ) from both sides and dividing by ε yields
1q
ε 2 = π1 (A1 ) − v 1 = (π1 (C1j ) − π1 (A1 )) ,
¯
2

(7)

which shows the claim.
−−−−→
−−−−→
The direction of each vector A1 C1j , which is also A1 B1j ’s direction, depends only on 2’s action,
a2j ; it does not change when ε goes to 0. This shows that, for ε small enough, C1j is a feasible
payoff and π2 (C1j ) exceeds π2 (A2 ) by an ε-independent value.
As noted, the system of actions and proposals implementing sAi ’s, sBij ’s and sCij ’s and sDi ’s isincentive compatible in actions and in proposals. To conclude the construction, observe that A
gives each player i a payoff higher than Ai , by an amount that is independent of ε. One may
35therefore implement A by a deterministic sequence of actions, chosen so that the continuation
payoffs stay within a distance Kε of A.45 Deviations in actions are punished by moving to sB11
or sB21 , depending on the deviator’s identity. Deviations in proposals are similarly punished bymoving to sD1 or sD2 .
To verify that the norm is contestable, notice that whenever 1 gets to make a proposal (at anyof continuations considered in the construction), his payoff is at least π1 (D1 ). Since D1 is on the
Pareto frontier, any proposal giving 1 strictly more than π1 (D1 ) must give 2 less than π2 (D1 ). Thismeans that sD1 can serve as a punishment in case 1 makes such a proposal.
Remaining cases: v 1 < π1 (P2 ) and/or v 2 < π2 (P1 )¯¯The construction is almost identical in other cases. The only difficulty is that the difference π1 (A1 )−√v 1 is now bounded below away from zero, whereas it was previously of order ε. This may lead to¯situations in which the points C1j constructed above are no longer feasible and/or give 2 a payoff
lower than π2 (A2 ). The difficulty is easily addressed by adding, for each j, a point E1j lying on thesegment [A1 B1j ]—and thus also on the line (A1 C1j )—such that if player 2 gets a chance to makea proposal, or if nobody does, players’ continuation payoffs jump to E1j . The promise keeping
condition (5) becomespp
π1 (E1j ) + π1 (C1j )π1 (B1j ) = 1 −2
2Choosing E1j close enough to B1j ensures that C1j lies within a distance(8)√

ε of B1j and, hence,of A1 . This guarantees that C1j is feasible and does not drop below π2 (A2 ), so that the rest of
the argument for the first case can be applied. To implement sE1j , we use public randomization to
implement it as a probabilistic mixture of sA1 and sC1j .

A.2

Necessary Conditions

The interesting case is when v i < πi (P−i ): otherwise, Theorem 1 predicts only that i’s payoff must¯
be individually rational. We derive the necessary condition for player 1; the same argument can beapplied to player 2.
Suppose that π1 (P2 ) > v 1 and, by contradiction, that there is a point A ∈ V (q) such that π1 (A) <¯qv1 = v 1 + 2+q(π1 (P2 ) − v 1 ): one can construct, for any ε small enough and per-period probability¯¯
p = qε of proposal opportunity, a contestable norm s that implements A.
45

It is possible to show that each of A, A1 , and A2 can be implemented so that players’ continuation payoffs

eventually converge to a Pareto-efficient point. Under this “redemptive” implementation, if players switch to a
Pareto-inefficient element following a deviation, they will eventually forgive and forget past deviations.

36

Let C1 denote 1’s infimum payoff over all continuations of s following histories at which it is 1’sturn to make a proposal and no off-path proposal has yet been accepted. Since the Pareto point
P2 is a possible proposal payoff,46 and since it Pareto dominates all payoffs with π1 < π1 (P2 ), C1
must satisfy π1 (P2 ) ≤ C1 .
We now contradict this inequality. Let N denote the set of continuations of s at the beginningof all periods following histories at which no off-path proposal has been accepted. Also let A1 =inf V ∈V(N ) π1 (V ), B1 = inf W ∈W(N ) π1 (W ), and D1 = inf U ∈U (N ) π1 (U ), and consider any sequence{Vk } ∈ V(N ) such that π1 (Vk ) →k→+∞ A1 . For any Vk there is an action that implements it in
the first period of the corresponding continuation. However, if player 1 deviates, he can guarantee

himself an immediate payoff of at least v 1 , and the worst punishment for him after deviation gives¯
him at least B1 . Therefore, π1 (Vk ) ≥ εv 1 + (1 − ε)B1 . Since this inequality holds for all Vk we¯obtain, taking the limit:
A1 ≥ εv 1 + (1 − ε)B1¯

(9)Since any element of U (N ) lies in the convex hull of V(N ), and player 1 can always conceal his
opportunity to propose, we have C1 ≥ D1 ≥ A1 . Consider now a sequence {Wk } ∈ W(N ) such that

π1 (Wk ) → B1 . Any element Wk is a weighted average of an expected payoff vector EUk1 whenever

1 gets a chance to make a proposal, an expected payoff vector EUk2 when it is 2’s turn to make aproposal, and a payoff vector Uk0 in case no one gets to make a proposal:
Wk =

p
p
(EUk1 ) + (EUk2 ) + (1 − p)(Uk0 )
2
2

(10)

We note that EUk1 is a mixture of elements of U (N ) resulting from 1’s mixture over proposals and2’s mixture over her acceptance decision. Similarly, EUk2 is a mixture of elements of U (N ).

Since all elements Uk ’s belong to U (N ), we have π1 (EUk2 ) ≥ A1 and π1 (Uk0 ) ≥ A1 . Equation (10)thus implies thatppπ1 (Wk ) ≥ (1 − )A1 + π1 (EUk1 ).
2
2

Recalling that C1 denotes 1’s infimum payoff when he gets to make a proposal, we getppπ1 (Wk ) ≥ (1 − )A1 + C1 .
2
2Taking limits, B1 ≥ (1 − 2p )A1 + 2p C1 , orB1 ≥ (1 −46qεqε)A1 + C1 .
2
2

(11)

By the Folk Theorem, P2 can be implemented by an equilibrium of the repeated game without renegotiation.

P2 can thus also be implemented as a norm of the enlarged game in which all proposals are ignored, i.e., treated ascheap talk.

37

qεCombining (9) and (11), we conclude that A1 ≥ εv 1 + (1 − ε)[(1 − qε2 )A1 + 2 C1 ]. Ignoring terms¯
of order ε2 in the right-hand side of this equation, A1 ≥ εv 1 + (1 − [1 + 2q ]ε)A1 + qε
2 C1 . Subtracting¯
A1 on both sides of the last equation and dividing by ε, we obtainqq
0 ≥ v 1 − [1 + ]A1 + C1
¯
2
2

(12)

q
From A1 ≤ π1 (A), C1 ≥ π1 (P2 ), and π1 (A) < v1 = v 1 + 2+q(π1 (P2 ) − v 1 ), we get¯¯qq
0 < v 1 − [1 + ]A1 + C1¯
22
which contradicts (12). This shows the necessary condition for player 1.
An identical reasoning for player 2 shows the second necessary condition. This proves the resultfor P1 6= P2 . A similar reasoning applies when P1 = P2 .
Credible proposals Section 4 has introduced the concept of C-credible proposals, and claimed
that the necessity conditions were unaffected if the proposals involved in the definition of stability

were restricted to being credible. To prove this claim, it suffices to verify that the proposal to move
to P2 , used just above to derive the necessary condition, is C-credible. The norm implementing

P2 is constructed as follows: players are prescribed to play, in all periods, the pure action profile
with payoff P2 , and to abstain from making any proposal. Any deviation, whether in action
or in proposal, triggers the continuation implementing A—which is supposed to exist, by thecontradiction hypothesis. Clearly, player 2 cannot benefit from deviating as she is getting herhighest possible payoff in the game. Moreover, the difference π1 (P2 ) − π1 (A) is by assumption

2bounded below by 2+q(π1 (P2 ) − v 1 ), which is ε-independent. Therefore, 1 cannot benefit from¯
deviating either: a deviation in action may create an immediate gain of order ε, but triggers adrop in continuation payoffs that is ε-independent and dominates the gain. A deviation in proposal
yields the payoff vector A, which again is detrimental to 1.

38

For Online Publication
Contestable Norms
Mikhail Safronov

Bruno Strulovici

University of Cambridge

Northwestern University

December 19, 2018∗

We are grateful for comments from Daron Acemoglu, Anke Becker, Eddie Dekel, Georgy Egorov, Tim Feddersen,Mark Granovetter, Paul Milgrom, David Miller, Josh Mollner, Ichiro Obara, Francisco Poggi, Anja Prummer, Larry
Samuelson, Ilya Segal, Tadashi Sekiguchi, Andrei Shleifer, Ludvig Sinander, Takuo Sugaya, Joel Watson, Asher
Wolinsky, our discussant Alex Wolitzky, and seminar participants at the 2015 SAET meeting, the 2015 World Congressof the Econometric Society, the 2016 Asian Meeting of the Econometric Society, and the 2018 Winter Meetings of
the AEA. Strulovici gratefully acknowledges financial support from an NSF CAREER Award (Grant No. 1151410)
and a fellowship from the Alfred P. Sloan Foundation.

1

B

Messages as arbitrary norms: A conceptual difficulty

In the main text, we defined the negotiation stage through an exogenously given set of messages,
and then assigned a norm to each message, requiring that each payoff vector of the feasible set beassigned a message. One may wonder if it is possible to assign a message to each norm, rather
than to each payoff. This requirement is much stronger since there are potentially many equilibria
that yield the same payoff. Moreover, this creates a circularity problem, because if one enlarges
the message space, this changes the underlying game (since more messages can be sent) and thus
the set of equilibria.
To be specific, suppose that the description of each period, in Section 2, is modified as follows.
Steps 1–3 and 5 are unchanged, but Step 4 is replaced by the following step:4’) With probability p < 1, one of the players is chosen to propose a new plan for continuation of
the game. Each player has the same probability of 2p being chosen. The chosen player may conceal
his proposal opportunity by remaining silent, or mix between making a proposal or staying silent.
The object of a proposal is an infinite-horizon plan m from the set M of all possible plans, defined
as follows

A plan in period t describes players’ strategy for the infinite repetition of the stage-game describedabove, from period t + 1 onwards. These decisions (actions, proposals, and acceptance mixtures)are history-dependent. The setting being time invariant, it is convenient to define recursively theset M of plans. A plan m ∈ M in period t is described by the following elements:a) For each realization z of the public randomization device, a pair α = α[m](z) of mixed actions
that players should play in period t + 1;b1) For each player i, a distribution µ̄i = µ̄i [m](z, a) ∈ ∆(M ∪ ∅) over proposals, where theoutcome ∅ means that i abstains from making a proposal (unbeknownst to player −i). We assume

that distributions have a finite support over plans.1 The proposal distribution can depend on therealization z of the public randomization device and on the pair a of observed actions. Because
p < 1, not observing any proposal from either player is always consistent with “on-path” behavior.
The realized proposal is denoted µi ;b2) A probability q−i = q−i [m](z, a, µi ) that −i accepts i’s proposal (whenever µi 6= ∅), which may

depend on z, a, and µi ;1

We will in fact impose a uniform upper bound on this support, as explained below.

1b3) If no one has made a proposal, the acceptance stage is skipped. To economize on notation,
we assume that some player i is, even in that case, conventionally selected (randomly or deterministically) as the proposer and let µi = ∅ and D−i = 0. (So, −i’s conventional response is tosystematically “reject” a non proposal.)c) A continuation plan m+1 = m+1 [m](z, a, i, µi , D−i ) ∈ M for period t + 2 onwards, as a functionof z, a, i, µi , D−i , where i indicates the identity of the last proposer.2

While the above definition seems natural, it turns out to be too permissive for the set of plans to bewell-defined: there does not exist a set of plans so large as to contain all the possible continuationprescriptions allowed above. In particular, in the above construction, a plan must specify anacceptance decision for each possible proposal. Therefore, each plan m must specify—among otherthings—a function which maps each element of M (the proposal) to a binary decision (acceptance).

This implies that the set M of plans must contain, in order to include all possible prescriptions,its power set 2M . Such a set does not exist, since any set has a strictly lower cardinality than its
power set, by Cantor’s Power Set Theorem (see, e.g., Mendelson (1997)).

C

Asymmetric proposing probabilities

It is easy to extend the analysis to a protocol in which one of the players has a higher probability
factor qi of proposal than the other player. The sufficient conditions are unchanged in this setting,but the necessary conditions become tighter for the player whose proposal probability is higher,
which translates into a higher minimal guaranteed payoff for that player across all contestablenorms. To see this clearly suppose that v 1 < π1 (P2 ) and v 2 < π2 (P1 ), so that renegotiation¯¯
potentially benefits both players relative to minmax payoffs, and consider the case in which 1 canmake frequent proposals while 2 never gets a chance to make a proposal (i.e., q1 is arbitrarily large
while q2 = 0). Then, 2’s minimal guaranteed sustainable payoff collapses to her minmax payoff,
while 1 is guaranteed to get a payoff of at least π1 (P2 ). More generally, player i’s minimal payoff,
given by (2), is calculated using the probability qi that he gets an opportunity to make a proposal,
and is independent of the other player’s probability of getting that opportunity. As qi increases,
player i’s guaranteed continuation payoff increases as well, and vice versa.
2

Clearly, this plan must be independent of i whenever µi = ∅, so that the convention chosen for the proposer in

the absence of any actual proposal is indeed irrelevant. This restriction is applied throughout.

2D

Truthful norms

For any number of players and any norm there is a payoff-equivalent norm, which is truthful in thesense that any on-path proposal is always accepted and implemented. Indeed, when some player
i gets a chance to make a proposal, he can make any number of proposals in equilibrium, theexpectation of which is some continuation payoff C. We alter the norm by prescribing player i tomake only one proposal with payoff C. The altered norm prescribes all other players to accept
the proposal and C to be implemented regardless of the acceptance decision. The payoff C can be
implemented using public randomization.
If i deviates and proposes a Pareto improvement relative to C, everyone is prescribed to reject it.
With two players, the new norm prescribes to have the same rejection continuation as in the original
norm. The incentive to accept the proposal is unaffected by the transformation, so the other player
is incentivized to reject an off-path proposal.
With more than two players rejecting the off-path proposal is an equilibrium. When the norm
is simple (see Section 5) and players vote for the payoff-improving proposal, as in Assumption 1,
player i is still prescribed to propose C. If player i makes an off-path proposal which gives him
more than πi (C), for each such a proposal there is at least one player j 6= i who rejects it, asotherwise this off-path proposal would be made and accepted in the original norm.

E

General renegotiation protocols

The benchmark model can be extended to allow multiple rounds of renegotiation within each period
without affecting the main results. We consider a multi-round renegotiation environment similar toMiller and Watson (2013), adopting their notation. In each period, with probability qi ε player i canmake a proposal to player j, which initiates a stochastic alternating-offer renegotiation protocol.
The renegotiation rounds are numbered as l ∈ {1, 2, ...},with l = 1 being the original proposal ofplayer i. If at any round the proposal is accepted, the players stop renegotiation and move to thenext period; otherwise the players continue renegotiation. Conditional on reaching the round l > 1,
player i is selected to be the proposer with probability ρi,l . Conditional on rejecting the proposalQin l-th round, the renegotiation breaks with probability βl ∈ [0, 1], with ∞l=1 (1 − βl ) = 0. The

values of ρi,l , l > 1, and of βl , l ≥ 1, are assumed to be independent of made proposals, and of theidentity of the original proposer, and are the same across different time periods.

The presence of multiple rounds of renegotiation affects the set of equilibria in the repeated game3with renegotiation. Nevertheless, Definition 1 has straightforward extensions applied to each roundof renegotiation and Theorem 1 continues to hold as stated. It is equally easy to show for environment of Section L, below, where the continuation of a failed proposal is independent of the
proposer, that Theorems 8 and 9 also continue to hold.3
Theorem 5 Theorem 1 extends to multi-round renegotiation.
The proof for sufficient conditions in Theorem 1 still holds, since player i can be punished formaking an unprescribed proposal by moving to the continuation which gives the highest possible
payoff to the player j, which makes all the future rounds of renegotiation meaningless. The proof
for the necessary conditions in Theorem 1 also holds, since when player i gets a chance to propose,he can guarantee to move to the above continuation, in both the one-round and the multi-roundcases.

F

Comparative statics

Consider any q > q ′ and any norm s that is contestable at some frequency q. We will show theexistence of a norm s′ that is contestable at frequency for q ′ and payoff-equivalent to s.
Under the new norm s′ , any payoff A achieved by s following any history ending before the action
stage is implemented using the same mixed actions and the same subsequent continuations as prescribed by s. Consider now any vector payoff B, calculated before the proposal stage, implemented
by some continuation sB of s. sB is a mixture of three continuation equilibria: sC1 , which arises
when 1 gets a chance to make a proposal and is calculated after the proposal stage; sC2 which arises
if 2 gets to make a proposal; and sC , which arises if no one gets to make a proposal.
At frequency q ′ , B is implemented as follows: players are prescribed to make exactly the same
proposals (with the same prescribed punishments if someone made an off-path proposal). For B
to still to be the weighted average of the continuations occurring after the three proposal events,
we change the continuation payoff in case no proposal is made: the new continuation payoff in this′case, C ′ , has to lie on the line between B and C. The new continuation sC is achieved using public
3

Concerning Theorem 8, even in the multi-round case renegotiation ends in one round, with a continuation payoff

being on the Pareto frontier. Moreover, with each player i having a non-zero bargaining power (equivalent to πi > 0),
the proof of Theorem 9 in Section L.1 does not require the property of η-stability, since the Pareto-improving proposal
will lie in the interior of the Pareto set of stable norm.

4randomization, as it lies in the triangle (C, C1 , C2 ). This construction gets us close to the desired
norm s′ .
However, one also needs to make sure that players are correctly incentivized to make a proposal,
when they get an opportunity to do so, rather than to conceal this opportunity. This is the caseif π1 (C1 ) ≥ π1 (C) and π2 (C2 ) ≥ π2 (C), i.e., if each player gets at least as high a payoff when hemakes a proposal as when he remains silent. When one moves point C to C ′ , these incentives might
get violated, and the construction above must be adjusted as follows.

The new continuation payoff when no proposal is made, C ′ , lies in between C and B. Supposethat it violates 1’s incentives to make his prescribed proposal: π1 (C ′ ) > π1 (C1 ). Since, in the oldnorm, we had π1 (C1 ) ≥ π1 (C), such a violation is possible only if π1 (C2 ) > π1 (C1 ). In this case, we

modify the prescribed proposal for player 1 by moving point C1 towards C2 . As this happens, thevalue of π1 (C1 ) increases and the value π1 (C ′ ) decreases (to keep B the weighted average). Whenthese values become equal, the incentives for player 1 to make a proposal start holding again. With
the new continuation payoff C1′ for player 1’s proposal and renewed continuation payoff in case of
no proposal C ′′ , player 1 is incentivized to make the prescribed proposal. One then can check thatboth new points can be implemented: the payoff C1′ lies between C1 and C2 and therefore can be
implemented using public randomization, while point C ′′ lies within the triangle (C, C1 , C2 ) andcan therefore also be implemented.
The same procedure is applied to player 2. The modified continuation payoffs can be implemented
using public randomization device. The new norm s′ therefore has the same set of payoffs as theold norm s at any stage, and it is contestable at frequency q ′ .

G

Non-vanishing probability of proposal

The sufficient conditions of Theorem 1 rely on the probability p of a player being able to make aproposal being proportional to ε: p = qε. As explained intuitively at the beginning of Section 3,
when p is independent of ε, one can no longer guarantee the existence of sustainable payoffs for all
stage games. This section establishes the result formally: for p ∈ (0, 1], there exists a stage game

which has no sustainable payoffs when the discount factor δ is sufficiently close to 1.

An example of such a game is given by the matrix below, with some payoffs expressed in terms ofa large constant M .

5

-2M,-2M-2M,-2M-2M,-2M-1,7-1,-2M

0,0-2M,-2M-2M,-2M-2M,-2M

M,-2M

-2M,M

0,0

-2M,-2M-2M,-2M-2M,-2M

-2M,M

M,-2M

0,0

7,-1

-2M,M

M,-2M

-2M,-2M-2M,-2M

0,0-2M,-1

M,-2M

-2M,M

-2M,-2M-2M,-2M

0,0

0,0

0,0

0,0

0,0

0,0

0,0

The minmax values of players are v 1 = v 2 = 0, as seen from the last row and the last column. The
set of Pareto efficient payoffs is a part of a line which goes through points (−1, 7) and (7, −1), andis a segment between (0, 6) and (6, 0): any other stage game payoff gives strictly less total payoffof the players, π1 + π2 .

Lemma 2 For any p > 0, there exists M such that for all ε small enough, no contestable norm
exists.
Proof.

The proof proceeds by contradiction. Suppose there exists a contestable norm and let V

denote the set of payoff vectors implemented by all continuations of the norm that follow histories
at which no off-path proposal has been accepted. Consider the payoff vector Q2 ∈ V that gives thehighest payoff to player 2 in V, and suppose that π2 (Q2 ) > 0. If player 1 gets a chance to propose,

1 gets at least π1 (Q2 ). Therefore the infimum A1 of 1’s payoff over all elements of V satifies
A1 ≥ ε ∗ v 1 + (1 − ε)(p ∗ π1 (Q2 ) + (1 − p) ∗ A1 )¯because 1 is gets at least minmax payoff v 1 during the action stage, and can guarantee himself a¯payoff π1 (Q2 ) when he makes a proposal.
When implementing Q2 , the expected per-period payoff of player 2 must be strictly positive, sinceQ2 gives the maximal payoff to 2 in V. Player 2 can only choose one of the columns from the second

to the fifth. Moreover, player 2 cannot play a mixed strategy (over at least two of the columns fromthe second to the fifth), as any pure action in the mixture should give player 2 a strictly positive
payoff, which is impossible as shown below:
Let player 1 choose the rows from the first to the third with a total probability of β, and choose

the fourth and the fifth rows with the total probability of γ. If player 2 chooses either the secondor the third column, 2’s expected payoff is at most X1 = −2M β + M γ, while if 2 chooses either

the fourth or the fifth column, 2’s expected payoff is at most X2 = M β − 2M γ. Since both payoffs

X1 , X2 cannot both be strictly positive, 2 cannot mix between at least one of the second and thethird columns, and at least one of the fourth and the fifth columns.
6Let player 1 choose the fourth row with probability β ′ , and the fifth row with probability γ ′ . If
player 2 chooses the second column, 2’s expected payoff is at most X1′ = M β ′ − 2M γ ′ , while if 2chooses the third column, 2’s expected payoff is at most X2′ = −2M β ′ + M γ ′ . Since both payoffs

X1′ , X2′ cannot be strictly positive at the same time, 2 cannot mix between the second and the thirdcolumns.
Let player 1 choose the first row with probability α̂, the second row with probability β̂, and thethird row with probability γ̂. If 2 chooses the fourth column, his expected payoff is at mostX̂1 = 7α̂ − 2M β̂ + M γ̂, while if he chooses the fifth column, his expected payoff is at most X̂2 =−2M α̂ + M β̂ − 2M γ̂. The sum of the two payoffs is negative X̂1 + X̂2 = (7− 2M )α̂ − M β̂ − M γ̂ ≤ 0,

if M > 10. In particular, the payoffs X̂1 , X̂2 cannot both be strictly positive and, hence, player 2
cannot be mixing between the fourth and the fifth columns.
Thus, when implementing Q2 , player 2 has to choose one of the columns from the second to thefifth as a pure strategy. Respectively, player 1 is able to deviate and get a payoff of at least M .
Thus, 1’s continuation payoff has to satisfy:
π1 (Q2 ) ≥ ε ∗ M + (1 − ε)(p ∗ π1 (Q2 ) + (1 − p) ∗ A1 ).
Indeed, if player 1 deviates and gets M in the current period, during the renegotiation stage player
1 can secure the payoff π1 (Q2 ) if given a chance to propose, and otherwise gets at least A1 .
Combining the above inequalities yieldsp(M − π1 (Q2 )) ≤ (1 − p)(A1 − v 1 ),¯which is impossible for M large enough. Therefore, there is no contestable norm for which 2 getsa strictly positive payoff. By symmetry, the same holds for player 1. The only possible contestablenorm that remains is for both players to always minmax each other and get zero in each period.
However, this norm is not robust to a proposal to move to a babbling norm with payoff (3, 3), which
is implementable by the Folk Theorem as long as ε is small enough.



Although, existence may be an issue when p fixed, this need not be the case. In particular, if the perperiod payoff of a deviator is sufficiently low during the punishment phase, this will be suffice to deter deviations, even if the probability of renegotiation is large. There are many stage games for which
there exist sustainable payoffs at all frequencies of renegotiation. An example of such a game, inwhich Pareto inefficient punishment is needed to support on path behavior, is given by the following-14,0 0,0 0,6matrix:

-14,0

0,0

5,0

-14,1

2,1

0,0

7

The Pareto frontier of this game consists of all the payoffs which lie between the points (0, 6) and(5, 0). All these payoffs are sustainable as δ becomes sufficiently large, even if the value of p remains
fixed.
Proposition 4 There exists ε0 ∈ (0, 1) such that ∀ε < ε0 , any payoff on the Pareto frontier of thegame is sustainable for any value of p ∈ [0, 1].

Proof.

The proof of this proposition follows the construction of Appendix A.1. In order toimplement Pareto-efficient payoff Q = (0, 6), player 2 has to choose the third column, while player
1 has to choose the first row. However, 1 may be tempted to choose the second row and get apayoff of 5. In order to implement Q, therefore, there must be a Pareto-inefficient punishment forplayer 1, sufficiently harsh to deter 1 from making this deviation, despite being able to propose aPareto improvement with positive probability in each period. This is achieved as follows: when
implementing Q, if player 1 deviates and chooses the second row instead of the first one, he gets animmediate benefit of 5ε. Player 1 is punished by moving continuation payoff to point B = (−5.5ε, 1).
At this stage, if player 1 gets a chance to renegotiate, he proposes point C = (0.5ε, 1), otherwise
p/2
the play moves to point A = ([−5.5 − 6 1−p/2]ε, 1), which gives player 1 a continuation payoff of atleast −11.5ε. Point A is implemented by choosing the third row and the first column with a payoff(−14, 1), and at the renegotiation stage player 1 would have a continuation payoff of at least ε.
With this construction, point Q deters any off-path proposals by player 1.

H

Concept equivalence: Proof of Theorem 2.

1. Any closed convention C c is an open convention as well, so the first statement is trivially true.

Now consider any open convention C o . To construct a payoff-equivalent closed convention C c , wemodify each norm s of C o as follows: s’s rules on and off the equilibrium path are kept unchanged
except when a player, say i, sends a message mi which is off the equilibrium path. In this case,because C o is an open convention, the continuation if −i accepts the proposal need not lie in C o .
Following such a proposal, players are instead prescribed to behave as if i had remained silent.
The new rules define a norm: when playing the original norm s, i was not sending the message mianyway, so removing this option does not affect equilibrium behavior and payoffs. By construction,
the set of modified norms form a closed convention C c , and because each norm of C o has been
modified into a single payoff-equivalent norm of C c , the conventions are payoff equivalent.
82. We start with the observation that if two conventions C c and C o have the same payoff sets, thenany proposal that is credible according to either convention is credible according to the other one.
We now consider any stable open convention C o and construct the corresponding closed convention

C c as in Part 1. To show that C c is stable, consider any norm s of C c , history at which player igets to propose, and credible proposal U such that πi (U ) is strictly greater than i’s continuation

payoff Ûi . From the above observation, U is also credible for C o . If the proposal U gives player−i a lower payoff that Û does, then the payoff U ′ = Û satisfies Definition 5. If the proposal U

Pareto dominates Û , then for the norm s̃ of C o corresponding to s, and the same history, −i must

reject U with positive probability (for otherwise πi (U ) would coincide with Ûi ). Let U ′ denotethe continuation payoff if −i rejects U . By stability of C o , −i knows that if he accepts U it will
be implemented. Since it is weakly optimal for −i to reject U , it must therefore be the case that

π−i (U ′ ) ≥ π−i (U ). Moreover, it must also be the case that πi (U ′ ) ≤ Ûi , for otherwise it would

be strictly optimal for i to deviate by proposing U , and s̃ would not be a part of an open stable
convention C o . Using this U ′ in Definition 5, this implies that C c is stable.
Next, consider any stable closed convention C c . To construct a payoff-equivalent stable open con-vention C o , we simultaneously modify all norms of C c . The modification proceeds in two steps,

using a recursive representation norms. A norm may be viewed as a prescription of actions, proposals and acceptance decisions for the next period (each depending on what happened in earlier
stages), along with a continuation norm resulting from these stages applied to the period after next.
In Step 1, we modify the prescriptions for time t + 1, and still use norms of C c as continuation

norms. The purpose of this step is to make a prescription compatible with the requirement that
if a Pareto-improving, credible proposal is made and accepted, then it has to be played. In Step2, we replace these continuation norms of C c by those built in Step 1, to guarantee that the rule
applies at all periods, ensuring that credible norms which are accepted are implemented, so that
Definition 7 holds at all periods.
Consider any norm s of C c . We modify s as follows. For the modified norm s̃, the action stage andon-path proposals are prescribed exactly as in s.4 Now consider a history at which i makes any

proposal U which is not prescribed by s but which is C c -credible. If −i accepts the proposal, we
4

Another modification of s is needed when i proposes on path a continuation ŝ that lies outside of C c , which−i is supposed to accept, and which is followed by a continuation s′ in the convention C c (as it should, since theconvention is closed). This sequence of moves is replaced by i directly proposing s′ and having it accepted by −i.

The modified profile is also a norm, as is easily checked. More generally, any norm of the game may be turned into
a payoff-equivalent “truthful” norm of the game, i.e., one in which any proposal that is made and accepted on theequilibrium path is implemented, as explained and proved in Appendix D.

9construct s̃ by prescribing that players implement this proposal.5 If the proposal gives i a strictly
higher payoff than his continuation payoff Ûi , then by stability of C c , there must exist a payoff

vector U ′ corresponding to some norm s′ of C c , which gives player −i at least as much as U , andwhich gives player i at most Ûi . We prescribe playing the norm corresponding to U ′ in case player−i rejects the proposal. If U does not improve upon i’s continuation payoff, we prescribe playing

the continuation corresponding to any of i’s on-path proposals in case −i rejects U . Finally, if imakes a non-credible proposal, the proposal is ignored as if i had stayed silent.

We now verify that s̃ is a norm that yields the same payoff as s. Since s̃ prescribes the same actions
as s, players are incentivized to follow the prescription. If i gets a chance to make a proposal,
any proposal prescribed by s (and hence s̃) yields the same continuation payoff as in s. If player imakes a credible, off-equilibrium proposal that improves upon his on-path payoff, then player −i

is incentivized to reject it, and i’s continuation payoff is weakly lower than his on-path payoff. It
is never optimal for i to make a credible proposal that is lower than his on-path payoff, regardlessof −i’s acceptance decision. Finally, we replace all continuation norms by their modified versions.
There remains to verify that the set consisting of all modified norms forms a stable open convention,
denoted C o , which is payoff equivalent to C c . First, we notice that continuations outside of C o

may arise only when a player makes an off-path proposal (which, by construction, also has to becredible) which is accepted by the other player. Thus, C o is an open convention. By construction,
each element of C o corresponds to exactly one element of C c , which yields the same expected payoff.

Therefore, the conventions are payoff equivalent. As observed earlier, this implies that they have thesame set of credible proposals. This, in turn, implies that any Pareto-improving, credible proposalof C o that is accepted is played and, hence, that C o is stable.

I

Proofs of Section 5 (Arbitrary number of players)

We define the sequential constructions mentioned in the main text, which both start from theset F of strictly individually-rational payoffs in the stage game, i.e., the payoffs which would be
implementable without renegotiation as δ goes to 1. We then consider the minimal payoffs πi (F),i ∈ {1, ..., n} that each player i could guarantee himself when given a chance to make a proposal if
any payoff in F could be chosen as a punishment. We will build two decreasing sequences of sets,

starting from F, which will generate separate necessary and sufficient conditions for a payoff to besustainable.
5

At this point, we do not know yet that the proposal is C o -credible. We only know that it is C c -credible. However,the norm C o that we are constructing will be payoff equivalent to C c and hence have the same set of credible proposals.

10

To derive sufficient conditions, the kth set in the sequence, FSk , is reduced by removing all the
payoffs below πi (FSk ), to form the k + 1-th set in the sequence, starting with FS0 = F. We will showthat this process converges to a stable set which defines sufficient conditions.

k , is constructed inductively as follows.
To derive necessary conditions, the kth set in the sequence, FNk ) denote the lowest expected payoff for player i at the beginning of a period, among all
Let πmin,i (FN
k . This value is lower than the continuation payoff π (F k ) that i can guarantee
payoff vectors in FNiN

himself when he gets a chance to make a proposal. We havekπmin,i (FN) ≥ εvi + (1 − ε)

h qε
n

k
πi (FN) + (1 −iqεk)πmin,i (FN)
nIndeed, as in the two-player case, i gets at least vi as his current payoff, and can guarantee himselfk ) if he has a chance to make a proposal. As ε goes to 0, one can express the value πkπi (FN
min,i (FN )as:kπmin,i (FN)≥k)
nvi + qπi (FN
.
n+q

(13)

k is being reduced by removing the payoffs below (13). Iterations of thisAt each step the set FN

procedure converge to a steady set, as we show in the Appendix.
Proposition 5 Both procedures converge to steady sets.

I.1

Proof of Proposition 5

We fix one of the two procedures and let Fk denote the set corresponding to the k-th step in thesequential reduction of the set F under this procedure. We first show that points on the relative

Pareto frontier P(Fk ) of Fk are never removed by the procedure. Suppose, contrary to the claim,that some point A ∈ P(Fk ) was removed by the procedure. Then there would be a player i suchthat πi (A) < πi (Fk ). If A was prescribed as a punishment payoff for any proposal of player i, thenfor i’s optimal proposal with payoff C ∈ Fk , the punishment payoff A would not be credible as it isremoved at the k-th step. That is, any j 6= i has πj (A) < πj (C). Since A lies on the Pareto frontierof Fk , this means that πi (C) < πi (A): C gives i a lower payoff than πi (Fk ), which contradicts

C’s assumed optimality. One could simply prescribe both continuations to have C as their payoff
vector, and this would give i a lower payoff than πi (Fk ).
When evaluating the worst punishment D(C, Fk ) for player i for making a (non-prescribed) proposal
with payoff C, the optimal proposal (that is, the one which gives the highest payoff to player i fromthe worst punishment) always lies on the Pareto frontier. Indeed, consider a proposal with payoff
C, which is not Pareto-optimal, and another proposal with payoff C ′ , which Pareto dominates C.
11

The set D(C, Fk ) of possible punishment payoffs is strictly larger than the set D(C ′ , Fk ), since thelatter set gives every player j 6= i a higher lower-bound on his payoff. This implies that the proposal
C ′ gives player i a worst punishment payoff πi (C ′ , Fk ) at least as high as the proposal associatedwith payoff C.

Since no point on the relative Pareto frontier of F is removed in the sequential reduction, the set of

optimal proposals (in terms of evaluating the worst possible punishment) for any player i remains
the same along the sequence. However, the set of possible punishments keeps decreasing at each
step, which weakly increases, as a result, the minimal value πi (Fk ) with k. (Recall that πi (Fk ) is
i’s minimal payoff if he gets a chance to make a proposal). At each step, the set Fk is characterized

by the n lower bounds of the players’ payoffs {πmin,i (Fk )}i∈{1,...,n} . These lower bounds are weakly
increasing at each step, which implies that the procedure converges to a stable point.

I.2

Proof of Theorem 4

Necessity
Suppose that A lies outside of VN and, for any ε > 0 small enough, there exists a contestablenorm s(ε) such that A lies in the set V(ε) of payoff vectors across all continuations of s(ε) following

histories at which no off-path proposal was accepted by the supermajority. The sets V(ε) mustk as an argument of this inequality), up to an ε-term. Consider
satisfy inequality (13) (replacing FN

the limit of V(ε) as ε goes to 0. This limit payoff set contains A and satisfies inequality (13), whichk . However, this implies that
implies that A should have not been removed from any of the sets FN

A belongs to VN , a contradiction.
Sufficiency: RWe first prove that any point in R is sustainable. Consider any point A with πi > πi (P−i ) for
any i. As in the two-player case, one can find n points Ai such that for j 6= i πj (Ai ) = πj (A)√and πi (Ai ) = πi (P−i ) + ε. We build a contestable norm s, in which for each i, the point Ai

gives i his lowest payoff across all continuations, following histories at which no off-path proposal
was accepted. In the continuation norm sAi associated with payoff vector Ai , player i is beingminmaxed. Since players other than i may have to use mixed strategies, this generates a set B

of continuation payoffs, following the action stage, which depend on the realization of actions ofplayers other than i. Any continuation B ∈ B is implemented as follows: if i can make a proposal,
he is prescribed to propose some continuation with payoff C; other players are prescribed to remainsilent; in the absence of any proposal, the continuation returns to sAi . As in the two-player case,12

one can guarantee (possibly using the public randomization), that the distance Ai C is of order√ε.

Since the Pareto frontier is connected, so is its truncation to points for which i’s payoff lies above
πi (P−i ). One can therefore find a connected subset Sε of the frontier consisting of all points giving,for each i, a payoff greater than or equal to πi (Ai ) + Kε, where K is a constant chosen large enoughthat players are incentivized not to deviate in actions.
Continuation norms with payoffs in Sε are constructed in such a way that each player i gets atleast πi (Ai ) + Kε in all subsequent continuations.
When implementing Ai , players are already incentivized to follow the prescribed actions. If i makes
a non-prescribed proposal, then by construction of Sε there exists a continuation with a payoff Qi
in Sε that gives i a lower payoff than C. Indeed, the lower bound for πi at the set Sε is πi (Ai ) + Kε,√
while πi (C) − πi (Ai ) is of order ε.
Sufficiency: General Conditions
The proof is similar to that of the two-player case. For any point A ∈ VS with πi > πmin,i (VS ),√consider the set of points Ai ∈ VS such that for any i πi (Ai ) = πmin,i (VS ) + ε and π−i (Ai ) =π−i (A). The points Ai have a smaller i-th coordinate than A provided that ε is small enough. We√
also assume without loss of generality that πi (Aj ) − πi (Ai ) >> ε for any j 6= i.
We build a contestable norm s such that Ai gives the lowest payoff to player i across all continuations
following histories at which no off-path proposal was accepted. At sAi , player i is minmaxed. Since
players other than i may have to mix their actions, we construct a set of continuations withpayoffs B ∈ B, corresponding to the observed actions of players −i. For any continuation normsB associated with some payoff B ∈ B, i is prescribed to make a proposal with some payoff vector

C, and all other players are prescribed to remain silent. As with the two-player case, C can be√assumed to lie at a distance of order ε from Ai . When implementing the continuation norm sC
associated with C, players are prescribed to follow a deterministic sequence of actions such thatthe continuation payoff remains within an ε-distance from C. Players are prescribed not to makeany proposals.
The initial point A is also implemented by deterministic actions and no proposals. Moreover, eachpoint in the positive orthant starting at the vertex with ith coordinate πi (Ai ) + Kε for each i is
implemented by a contestable continuation norm of s in such a way that πi > πi (Ai ) + Kε: sAi is
a severe enough punishment for i that it is suboptimal for him to deviate in action.
The norm s can be shown to be generically contestable. The only new issue concerns i’s incentives

13

to deviate in proposal. We have reduced (increased the lower bounds on payoffs) the initial set VS√by an order of ε. The orthant defined by πi > πi (Ai ) + Kε for all i is part of the set of contestable
continuations, but some points lying below this orthant are removed from the original set VS . As aresult, the value πi (.), which i can guarantee if having a chance to propose, can now be larger. Our
goal is to show that, nevertheless, generically the value of πi (.) is smaller than πi (C), and therefore
player i is incentivized to propose sC .
When building a set VS by sequentially removing payoffs with πmin,i (.) < πi (.), the initial set ofindividually-rational payoffs gets reduced. If for player i the final value of πmin,i (VS ) is strictly

larger than his minmax payoff vi , then the value of πi (Ai ) − vi is of order ε0 . This means that the1

distance Ai C can be made of ε 4 -order. At the same time, the set VS (and, respectively, the value√
πi (.)) were changed by an order of ε, guaranteeing that πi (.) < πi (C).

If player i’s payoff πmin,i (VS ) equals to minmax vi , this means that i’s payoff was not increased
when building the set VS . Put it differently, one can consider a hyperplane of the set VS with

πi = vi , and find the maximum payoffs of other players πj , j 6= i on that hyperplane. The n − 1-dimensional payoff vector {πj }j6=i cannot lie within the interior of VS (otherwise, player i could

make a proposal dominating {πj }j6=i and thus guaranteeing himself a payoff higher than vi ). When√the set VS is reduced by (an arbitrarily small) ε-order, player i can gain incentives to make an

off-path proposal, only if the vector {πj }j6=i lies exactly on the Pareto frontier of VS . However, thispossibility is non-generic.

I.3

Proof of Proposition 3q—necessary
Intuition. A) Let L = N −1, that is, the voting rule is unanimous. The sets VS and VN

conditions depend on q, hence the superscript—are both obtained from F by sequentially increasing

the lower bounds on each player’s payoff when he gets a chance to make a proposal. VS is obtainedqby removing payoffs below πi (·) at each step, while VN
is obtained by removing payoffs below
nvi +qπi (.).
n+q

When q goes to infinity, the sets of payoffs removed at each step of these proceduresq
converges to the set VS as q goes
converge to each other. As we show below, this implies that VN

to infinity.

The set of sufficient conditions, VS , can be characterized by two sets of lower bounds for each player

i: πi (VS ) is the lower bound on i’s payoff when he gets a chance to make a proposal and πmin,i (VS )is the lower bound for his payoff at the beginning of a period. VS was constructed in such a waythat πi (VS ) ≤ πmin,i (VS ).

14

To capture this intuition, we first show by induction that VS is the largest set S of individually
rational payoffs whose Pareto frontier is equal to P(V) and such that πi (S) ≤ πmin,i (S) for any

i. Consider such a set S. The sequence of sets FSk converging to VS starts with FS0 = F, the setof all individually rational points. This implies that πi (S) ≥ πi (FS0 ), since FS0 contains S and,hence, the set of punishments if i makes an unprescribed proposal is higher with FS0 than with S,

resulting in a lower bound πi . We now show the induction hypothesis: if πi (S) ≥ πi (FSk ), then thesame condition holds for k + 1. Due to the way the payoffs are cut at step k, one has for eachi, πmin,i (FSk+1 ) = max{πmin,i (FSk ), πi (FSk )} ≤ πi (FSk ), which does not exceed πi (S) ≤ πmin,i (S).

Since the lower bound πmin,i (FSk+1 ) is lower than πmin,i (S), the set FSk+1 contains S, and one hasthat πi (S) ≥ πi (FSk+1 ). By induction, the limit set VS contains R.

q
Let VN denote the limit of VN
as q goes to infinity. We wish to show that VN = VS . Consider
k,q +∞
the sequences {FN}k=0 resulting from the procedure applied, for any fixed q, to derive necessary

conditions for this value of q. Due to the way points are removed at each step, it is easy to check that
′

k,q
k,q
⊂ FN
whenever q ′ > q; by the same logic, it is straightforward to check that VS is containedFN
q
in VN . To prove the reverse inclusion, note for each q and i, we have πmin,i (VN)≥

qnvi +qπi (VN
)
, as
n+q

this inequality holds at each step k of the procedure. Taking the limit as q goes to infinity, thelimiting set VN must satisfy for each i πi (VN ) ≤ πmin,i (VN ). From the previous paragraph, this

implies that VS contains VN , which concludes the proof.

B) Any other supermajority rule, L ∈ {⌊N/2⌋, . . . , N − 2}, would lead to a different function πi (.),

since the set of punishment for each off-path proposal would be smaller, compared to the case of
L = N − 1. However, the proof works the same. In addition, higher values of L lead to (weakly)

larger sets VN , VS : Those sets are obtained from sequential procedure of removing payoffs, startingfrom the set of all individually rational payoffs, and higher values of L shrink the set of removed

payoffs at each step.

J

Multiplayer agreements: Voter-dependent continuations, sequential voting and non-unanimity rules

J.1

Voter-dependent continuations

Suppose, first, that continuation payoffs can depend arbitrarily on the voting decision of eachplayer—except if everyone agrees on a proposal, in which case contestability dictates that the
proposal is implemented. With this high degree of flexibility, norms may be constructed so that all15

negotiation proposals are dissuaded and the Folk Theorem obtains.
Theorem 6 For any feasible payoff vector π with πi > vi for all i, π is sustainable.
To understand this result, we recall that in the underlying repeated game without negotiation, any
strictly individually-rational payoff vector can be implemented for ε small enough by minmaxing
any player i who deviates in actions, and switch to minmaxing any player j 6= i who deviates

when minmaxing player i. The same idea can be applied when negotiation is feasible, by deterring

it as follows: if a player, i, proposes another continuation, everyone else is prescribed to reject
the proposal and to start minmaxing player i. If another player, j, deviates from the prescribedrejection by accepting i’s proposal, and all other players reject it, then players are prescribedto minmax j instead of i. If two or more players accept i’s proposal, it is implemented, whichguarantees that the norm satisfies our contestability refinement. This prescription guarantees that
it is always suboptimal for a player to unilaterally accept a proposal and, consequently, that it
is also suboptimal to make any proposal. Unless some additional restrictions are imposed on thecontinuation payoffs, allowing for the possibility of renegotiation with three or more players thus
has no more predictive power on the set of equilibria and payoffs than the standard Folk Theorem.
To prove Theorem 6 formally, observe that since v ∈ F, the standard Folk Theorem implies thatfor ε small enough v can be achieved by an equilibrium of the underlying repeated game. Thisequilibrium can be embedded into a norm of the repeated game with renegotiation. According
to this norm, no proposal is ever prescribed at any stage of the game. If a player i ever makesa proposal, other players are prescribed to reject it and the continuation payoff corresponds topunishing player i, as if i had deviated in action in the underlying equilibrium. If only one player
j 6= i accepts i’s proposal, the continuation corresponds instead to the punishment equilibrium forj. If at least two players accept the proposal, it is implemented. These prescriptions guaranteethat any unilateral deviation in action, proposal, or acceptance decision is suboptimal.

J.2

Sequential voting in case of no restrictions

Sequential voting permits more than two continuation payoffs, depending on the sequence of acceptance decisions of the players. The set of sustainable payoffs is qualitatively similar to the earlier
analysis with simple norms but more permissive.
Proposition 6 Suppose that each proposal is decided by sequential voting. Then, sufficient andnecessary conditions analogous to those of Theorem 4 obtain, which are characterized by upper16

orthants. Moreover, the set characterized by each of these two conditions is larger than the corresponding set obtained with simple norms and simultaneous voting.
Sequential voting with many continuations thus provides more predictive power than simultaneous
voting with voter-dependent continuations, but less predictive power than the simultaneous-voting
specification with only two continuations.
Proof. [Sketch] Consider for simplicity the case of three players: player 1 makes a proposal andplayer 2 responds first, followed by player 3. Depending on responding players’ votes, there are
four possible continuations, one of which is equal to 1’s proposal and arises when 2 and 3 accept
the proposal.
The ability to punish 2 for accepting player 1’s proposal is constrained by the following issue: if 2
accepts the proposal, 3 will reject it only if the punishment for player 2 gives him at least the same
payoff as 1’s proposal, which will be implemented if he accepts it. This puts a lower bound on 2’spunishment payoff, which is higher than the minmax v2 .
As a result, 1’s punishment for making an off-path proposal is also limited. Since fewer punishments are available, fewer norms are contestable: sequential voting has more predictive power thansimultaneous voting. By nature of the arguments used to derive necessary and sufficient conditions,these conditions are characterized by upper orthants, even if players randomize their acceptancedecision. Since allowing only two continuations—as simple norms do with simultaneous voting—is
a special case of the more numerous continuations allowed by sequential voting, it follows that simple norms have more predictive power than the contestable norms obtained with sequential voting.


J.3

Non-unanimity rules

Theorem 4 implies that when unanimity is required for the proposal to pass, there always exist
sustainable payoffs. This section shows two results: a) for N > 2 players, sustainable payoffs may
not exist under non-unanimity rules; and b) in symmetric games, sustainable payoffs exist for any
supermajority rule, that is, for any L ≥ ⌊N/2⌋.6
Proposition 7 For any N > 2, there exist an N -player stage game and a threshold q̂ such thatin the related repeated game with renegotiation with voting rule L = N − 2, there do not exist
sustainable payoffs at frequency q, for all q > q̂.
6

Recall that L is the number of votes required in addition to the proposer for the proposal to pass.

17

In general, therefore, the existence of contestable norms is guaranteed only under the unanimity
rule. In the stage game that we construct, we show that if proposals can pass even when there is anegative vote, then each player, when she has a chance to propose, can guarantee herself too higha continuation payoff, which destroys stability of contestable norms.
Proof.
We first describe counterexamples for N ≥ 5 and then the small modifications needed for N = 3
and N = 4.

Players are numbered as {1, ..., N }. In the stage game, each player has N actions denoted a1 , ..., aN .

If all N players choose the same action a1 , the payoff vector is T1 = [X, 0, 10, 10−z, 10−φ1 z, ..., 10−101
φN −4 z] where X = 10(1 − N 1−1 ), φj = (2N )j for j ∈ {1, ..., N − 4}, and z = (2N. If)2 (2N )N−4

all players choose a2 , the payoff vector T2 is obtained by cycling clockwise the payoffs from T1 :T2 = [10 − φN −4 z, X, 0, 10, 10 − z, 10 − φ1 z, ..., 10 − φN −3 z]. In general, if all players choose ai ,then the payoff vector Ti is obtained by cycling payoffs from T1 , with player i getting payoff X. In
particular, the payoff vector TN = [0, 10, 10 − z, 10 − φ1 z, ..., 10 − φN −4 z, X].
If N − 1 players choose ai , and player j chooses a different action, then j gets the payoff he would

have gotten at Ti less z/2 and other players get their payoff from Ti . In all other cases players get apayoff vector T equal to (T1 +...+TN )/N . Note that the stage game satisfies the full dimensionality
condition.
The setting is as in the main text with L = N − 2, which means that a proposal is accepted if it getsat most one negative vote. Note that due to the monotonicity result of Proposition 3, nonexistence
for L = N − 2 implies nonexistence for all L ≤ N − 2.
The strategy in which all players choose ai forms a Nash equilibrium of the stage game and, hence,of the repeated game. Therefore, the corresponding payoff Ti constitutes a valid payoff proposal
for the repeated game with renegotiation. We show that player i = 1 can guarantee to get at least
X − z/2 by proposing T1 . More precisely, there does not exist a punishment vector which would

give 1 a payoff less than X − z/2 and which would be preferred to T1 by at least one player amongplayers 3, ..., N (implying that only player 2 may reject T1 if it is proposed by 1). First, let us showthat any Pareto-efficient payoff P , which gives player 1 a payoff strictly less than X, would makeall players 3, ..., N worse off compared to T1 . Without loss, P can be thought of as a weighted
average of vectors T2 , ..., TN , with weights p2 , ..., pN summing up to 1. Note that out of vectors
T2 , ..., TN −1 , the minimal payoff that 1 gets is 10 − φN −4 z at T2 . Thus, since P gives player 1 a18

payoff less than X, one has:(1 − pN ) × (10 − φN −4 z) + pN × 0 < X
or
10 − φN −4 z − X=
pN >10 − φN −4 z

10



1
1
N −1 − (2N )2
10 1 − (2N1 )2



4N 2
1
N −1 − 1>=
2
4N − 12N

1where the last inequality holds for N > 2. However, if pN > 2N
, each player 3, ..., N gets strictly

less from P than from T1 : First, T1 gives player 3 a maximal stage-game payoff of 10. Next, T1
gives player 4 a payoff of 10 − z, while TN gives player 4 a payoff 10 − φ1 z. Since TN is given a1weight of pN > 2N
by payoff P , and the maximal stage-game payoff is 10, P gives player 4 at most

φ1
= 10 − z. Similarly, any player j ∈ {5, ..., N − 1} gets a
pN (10 − φ1 z) + (1 − pN ) × 10 < 10 − z 2N

payoff of 10 − φj−4 z = 10 − (2N )j−4 × z from T1 , and at most pN (10 − φj−3 z) + (1 − pN ) × 10 <j−3)
10 − (2N2N

10× z = 10 − (2N )j−4 × z. Finally, player N gets a payoff of 10 − φN −4 × z = 10 − (2N)2from T1 , and a payoff of X = 10(1 − 2N1−1 ) from TN . That is, player N gets a payoff from P of at
10
most pN × 10(1 − 2N1−1 ) + (1 − pN ) ∗ 10 < 10 − (2N )(2N
−1) , which is less than what N gets at T1 .

Thus, if 1 proposes T1 , then there does not exist a Pareto-efficient payoff P that gives 1 a payoff
strictly less than X and that makes at least one of the players 3, ..., N weakly better off. Since theset of feasible payoffs lies between the hyperplanes defined by u1 + ... + uN = X + (10 − z) + (10 −φ1 z) + ... + (10 − φN −4 z) and by u1 + ... + uN = X + (10 − z) + (10 − φ1 z) + ... + (10 − φN −4 z) − z/2,

there does not exist a feasible payoff vector that would give player 1 a payoff lower than X − z/2

and that would make at least one of the players 3, ..., N weakly better off. Therefore, player 1 isguaranteed to get at least X − z/2 when he gets a chance to propose. Moreover, for all large enoughq and small enough ε, the continuation payoff of player 1 cannot lie too much below X −z/2 because
1’s opportunities to propose are very frequent. Therefore, 1’s continuation payoff is at least X − z

for any sustainable payoff. By the same argument, any player’s payoff must be at least X − z in acontestable norm with q large enough. However, this is impossible as it would imply that the sum of

players’s payoffs is at least N (X −z) = 10N −10 NN−1 −N z = 10(N −1)− N10−1 −N z, whereas the sumof players’ payoff in the stage game is bounded above by X +(10−z)+(10−φ1 z)+...+(10−φN −4 )z <2
X + 10(N − 2) − φ1 z = 10(N − 1) − N10−1 − N z, which is smaller.

For N = 3, a similar counterexample exists with T1 = (4, 0, 5) and a punishment for an individual
deviation in action of 1/100. In a contestable norm with q large, each player can guaranteed himself
a payoff close to 4 but the total average payoff across players is bounded above by 3. For N = 4 ,we use T1 = (10, 0, 15, 14) and a punishment of 1/100. Each player has a guaranteed payoff close
to 10 but the average payoff across players is bounded above by 9.75.
19

The non-existence result in Proposition 7 was obtained for games that are asymmetric. If one
restricts attention to symmetric games, then the existence of sustainable payoffs is restored for all
supermajority rules. An N -player stage game is symmetric if the set of actions is the same for all
players i: Ai = A and for each action profile a = (a1 , ..., aN ) it holds that if one permutes theactions in a, the payoffs of players u1 (a), ..., un (a) are permuted in the same way.

Proposition 8 For any N -player symmetric stage game, N > 2, and supermajority rule L ≥⌊N/2⌋, the set of sustainable payoffs is non-empty.
Proof.

Since the set of sustainable payoffs is nondecreasing in L by Proposition 3, it is enoughto prove existence for two cases: when N = 2k + 1 and L = k + 1 and when N = 2k and L = k.
In both cases, letting m denote the minimal number of votes against the proposal needed for the
proposal to fail, we have m = k.
Fixing a symmetric game throughout, we show the existence of a payoff vector such that no player
i can propose an alternative vector that would be accepted and would make i strictly better off.
Let Q denote the set of feasible payoffs satisfying the following conditions: each player gets at leasthis minmax payoff, and m players get some identical payoff x (where x can vary across elementsof Q). Let Q′ denote the subset of Q for which the common payoff x of the m players is maximal,

and let xm denote this maximal value. Note that, due to symmetry of the game, xm may also be
defined as the solution from the problem of maximizing the m-th largest payoff across all players
subject to each player getting at least his minmax. Payoff vectors in Q′ are such that m players

get xm , while the remaining N − m players have payoffs lying in some interval [y, Y ], where y is
weakly above the minmax.

We now show that for any proposal of player i, that gives at least minmax to each player, one canalways find a credible punishment for i such that i gets y, and each other player gets at least y.
Suppose that i proposes a payoff vector P to other players. The payoffs in P can be ordered in an
ascending sequence: w1 ≤ w2 ≤ ... ≤ wN −1 (excluding i’s own payoff). Note that the payoff wm

cannot exceed xm , since there are at least m payoffs wm ≤ ... ≤ wN −1 that are weakly higher than
wm . Thus, if one considers a punishment vector in which players who were offered w1 ≤ ... ≤ wm

get xm each, player i gets y, and all other N − m − 1 players get the same payoff that lies in [y, Y ],this punishment is attractive to the former m players, and the proposal is rejected.

Put differently, the payoff vector, in which m players get a payoff of xm each, and the other N − mplayers get a payoff of at least y each, is resistant to proposals: when a payoff vector gives eachplayer at least y, one can always incentivize enough players to reject any proposal, and hence, deter
any proposal. Moreover, any such a vector can be implemented (precisely, or in the limit as ε20

converges to zero) as a sustainable payoff as we now demonstrate.
If xm = y, then the symmetric payoff vector (xm , ..., xm ) is sustainable: either (xm , ..., xm ) is astage-game Nash equilibrium and it is trivially implemented, or there must exist an inefficient
symmetric Nash equilibrium7 which may be used to deter deviations in action: if anyone deviatesfrom the strategy implementing (xm , . . . , xm ), players switch to the inefficient Nash equilibrium
until someone proposes to resume implementation of (xm , ..., xm ). For any fixed q > 0, this threatsuffices to deter deviations as ε becomes arbitrarily small.
Consider now the case xm > y, and suppose first that the set Q′ is not a singleton, and that Y > y.

We consider the following punishment for (any) non-prescribed proposal: m players get xm each,while the other N − m players (including the proposer) get a payoff y ′ each, with Y > y ′ > y. This

payoff vector (lying strictly above the minmax) can be implemented: if any player i deviates inaction, i gets minmaxed until i gets a chance to propose to return back to this vector. Moreover,any payoff vector in which each player gets at least y ′ can be implemented as well. As ε goes tozero, y ′ can be chosen arbitrarily close to y.
Suppose now that Y = y: if m players have a payoff of xm each, all other players get exactly y (which
could be the minmax payoff). Let us fix some (small) positive η > 0 and note that if m players havepayoffs of xm −η each, it is possible to find a payoff W = y +Kη such that N −m−1 players get eacha continuation payoff of W , and one player gets (y + W )/2. Indeed, since the game is symmetric,
one can equalize payoffs across all N players. Let F = (xm − η, ..., xm − η, (y + W )/2, W, ..., W ).
We focus on the case n = 2k, which is the “hardest” one in the sense that the number of required
votes to reject the proposal is the same as with n = 2k + 1, but in the latter case there is more

freedom to choose punishment. Given a discount factor 1 − ε, one can look at the set of all SPEs,and find the “critical” SPEs which maximize the m-th highest continuation payoff. This payoff isarbitrarily close to xm , within xm − Aε for some A independent of ε. We denote this payoff by Xm

and note that Xm converges to xm as ε goes to zero. All other N − m players get a payoff close toy. Let ylow denote the highest of their payoffs.

Since the game is symmetric, one can consider another equilibrium, referred to as S-equilibrium
which is obtained from “critical” equilibria by mixing payoffs across players (with the help of arandomization device), and has the following payoff vector: one player gets Xm , one player gets(y + W )/2, while all the other players get the same payoff Z, where Z lies strictly between Xm andylow (and also between xm and y). We have y < ylow < (y + W )/2 < W < Z < xm − η < Xm < xm .
7

The existence of a symmetric Nash equilibrium is a well known result for symmetric game.

21

We show that for each unprescribed proposal of player i, there is a punishment which gives player
i a payoff of (y + W )/2. Indeed, if player i makes a proposal, he cannot make the m-th highest
proposal to other players strictly higher than Xm . If that m-th highest proposed payoff is exactly
Xm , then player i has to propose a “critical” SPE, that is, player i proposes a payoff vector in whichm players get Xm each, with N − m − 1 other players getting a payoff close to ylow . The credible

punishment takes the form of an S-equilibrium: it gives Xm to one player (who votes against the
proposal), (y + W )/2 to player i, and Z to all the other players (out of which N − m − 1 vote against

the proposal). Moreover, the same punishment works if the m-th highest payoff in i’s proposal is atleast xm − η (if η is much smaller than the difference between xm and y). If m-th highest proposalof player i is below xm − η, then one can use the punishment payoff F constructed earlier, in whichm players get a payoff of xm − η each (and vote against the proposal), player i gets (y + W )/2,
while all other players get a payoff of W .

Thus, for any possible proposal of player i, there is a punishment, in which i gets (y + W )/2,
less than what other players get by an amount proportional to η and independent of ε. Since(y + W )/2 exceeds y (and, respectively the minmax) by an ε-independent amount, one can sustain
a contestable norm in which any player’s payoff is at least (y + W )/2. If a deviation in action
occurs, the deviator is minmaxed until he gets a chance to propose and return to having (y + W )/2
for himself. In the event of an off-path proposal, the deviator gets precisely (y + W )/2.

K

Observable mixed strategies

We have assumed throughout the paper that when a player randomizes across several actions or
proposals, only the outcome of this randomization is observed by the other player. In particular,
players’ continuation values cannot directly depend on their choice of mixed strategy. Our results
do not change if instead we assume that mixed strategies are observable. For sufficient conditions,this fact is straightforward because our construction is clearly compatible with players observing
more information. For necessary conditions, payoff lower bounds were computed using only thatany player can guarantee himself at least his minmax payoff during the action stage and at least
some particular payoff during the proposal stage which satisfies the responder. These lower bounds
do not change when mixing is observable.
The observability of mixed strategies does affect, however, the set of weakly renegotiation-proof(WRP) equilibria defined by Farrell and Maskin (1989), as follows. An SPE σ is weakly-renegotiation
proof if there do not exist continuation equilibria σ 1 , σ 2 of σ such that σ 1 strictly Pareto dominates22

σ 2 . If a payoff vector arises as players’ continuation payoff following some history of a WRP
equilibrium, we will also say that these payoffs are WRP.
Assuming that mixing probabilities are observable, Farrell and Maskin obtained a sufficient condition for any feasible payoff to be WRP in the context of two-player repeated games. To formulate
this condition, they define ci (α) = maxa′i πi (a′i , α−i ) as the cheating payoff of player i when hechooses a best response to the (mixed) action α−i , and establish the following result.
Proposition 9 Let π = (π1 , π2 ) denote a feasible payoff. If there exist (mixed) action pairs αi =(αi1 , αi2 ) (for i = 1, 2) such that ci (αi ) < πi , and π−i (αi ) ≥ π−i , then the payoff π is WRP if δ issufficiently close to one.

Moreover, with observable mixed strategies the set of WRP payoffs generically contains Paretoefficient payoffs, as shown in Evans and Maskin (1989).
Theorem 7 Given the players’ action spaces A1 and A2 , for a generic choice of payoff functions,if players are sufficiently patient, then there exists a WRP equilibrium that is Pareto-efficient.
We now prove the existence of a symmetric stage game in which all Pareto-efficient payoffs above theminmax satisfy the requirement of the above proposition, but cannot be WRP if mixing probabilities
are unobserved, even if the stage game payoffs are slightly perturbed. The definition of WRP is
the same as before, except that equilibrium strategies now depend only on the history of realized
actions rather than on the history that included mixed strategies. The stage game is identical tothe one described in Appendix G with M = 100, and is reproduced here for convenience:-2M,-2M -2M,-2M -2M,-2M -1,7
-1,-2M
0,0-2M,-2M-2M,-2M-2M,-2M

M,-2M

-2M,M

0,0

-2M,-2M-2M,-2M-2M,-2M

-2M,M

M,-2M

0,0

7,-1

-2M,M

M,-2M

-2M,-2M-2M,-2M

0,0-2M,-1

M,-2M

-2M,M

-2M,-2M-2M,-2M

0,0

0,0

0,0

0,0

0,0

0,0

0,0

As noted in Appendix G, the minmax values of players are v 1 = v 2 = 0, as seen from the last
row and the last column. The set of Pareto efficient payoffs is a part of a line which goes throughpoints (−1, 7) and (7, −1), and is a segment between (0, 6) and (6, 0): any other stage game payoff

gives strictly less total payoff of the players, π1 + π2 . Let’s show that none of those Pareto efficient

payoffs can be a part of WRP given low enough ε (arbitrarily patient players), even if players haveaccess to a public randomization device. In fact, only the minmax payoff of (0, 0) is WRP:
23

Counter-Example 1 With unobservable mixed strategies, (0, 0) is the unique WRP payoff.
Suppose, by way of contradiction, that there is a point A that is the continuation payoff of some
WRP equilibrium σ and such that π2 (A) > 0 (the case of π1 (A) > 0 is similar). Consider the payoff
vector A′ corresponding to player 1’s lowest payoff and, hence, player 2’s highest payoff among allcontinuation payoffs of σ before public randomization.8 When implementing A′ , player 2 cannot
choose either the first or the last column, since there column give him at most zero, regardless of
1’s strategy; this would imply that 2’s continuation payoff in the next period satisfies π2 > π2 (A′ ),contradicting our choice of A′ . Therefore, 2 chooses among columns located between the secondand fifth.
Since A′ gives 1 his lowest possible payoff, when implementing A′ player 1 cannot get a period
payoff higher than π1 (A′ ), even if he always plays a stage-game best response. Otherwise, thepromise-keeping constraint would have to prescribe a continuation giving 1 a payoff lower thanπ1 (A′ ). If 2 chooses a pure strategy (among the columns from the second to the fifth), player 1 canguarantee himself a payoff of M = 100, which is greater than what 1 gets from any individuallyrational payoff. Moreover, as shown in Appendix G, there is no mixed strategy which gives player 2
a strictly positive payoff for each of 2’s actions. Thus, point A is not WRP. The only WRP payoff isthe minmax payoff (0, 0). Moreover, even if one slightly perturbs the stage game payoffs, there will
be no WRP equilibrium which provides the players with payoffs that are significantly higher thanthe minmax. By contrast, with observable mixed strategies and sufficiently patient players, one
could implement any Pareto efficient payoff strictly above the minmax. Any Pareto efficient payoff
satisfies Proposition 9 where α1 corresponds to 1 choosing the fourth row and 2 mixing between
the first and second columns with equal probability, and α2 corresponds to 1 mixing between thefirst and second rows with equal probability and 2 choosing the fourth column.

L

Contestable norms in the absence of proposer-specific punishments

One virtue of explicitly modeling the renegotiation process is to incorporate the logic of modern
repeated games analysis into renegotiation: just as arbitrary continuation equilibria may follow fromobserved actions in a repeated game, here arbitrary continuations may follow rejected proposals.
8

Since σ is WRP, 1’s lowest continuation payoff is achieved for 2’s highest continuation payoff. The proof can beeasily adjusted if σ’s payoff extrema are not achieved.

24

The paper has explored one consequence of this generality, which is that even good proposals may
be deterred, and Pareto dominated equilibria be sustained as a result.
While in the applications discussed earlier this flexibility seemed reasonable or even desirable, inother environments it is natural to ask what equilibria may be sustained when proposers cannot
be punished. Indeed, such a restriction is imposed in a number of models of explicit negotiation9
and sometimes formalized as a “No-Fault Disagreement” (NFD) axiom. The axiom requires thecontinuation equilibrium following a rejected proposal to coincide with the default continuation incase no proposal was made. This appendix shows how our results are modified when this refinement
is added.
In order to keep the language of the analysis as close as possible to the existing literature, this section
adopts the “stable convention” terminology of Definitions 2 and 3 instead of the contestability
refinement.10
Definition 10 A stable convention C is forgiving if for any equilibrium s in C, for any i and mi ,s+1 [s](z, a, i, mi , 0)=s+1 [s](z, a, i, ∅, 0).

Our concepts are modified as follows. A payoff vector A is said to be forgivingly q-sustainable if forall ε small enough, there is a forgiving stable convention containing an equilibrium which expected
payoff is equal to A. A is forgivingly sustainable if it is forgivingly q-sustainable for all q’s large
enough.
The main result in this case is given by the novel necessary conditions, which are much more
restrictive that those of Theorem 1: the continuation payoffs must lie within a distance O( 1q ) of theconvex hull of the (individually-rational) Pareto frontier. More precisely, for each feasible payoff
vector A, let ρ(A) denote the signed distance from the line (P1 P2 ), counted positively if A lies
below (P1 P2 ), and negatively otherwise, as indicated by Figure 6.
Let ρ̄ denote the maximum value of ρ among all feasible payoff vectors.
ρ̄
Theorem 8 If A is forgivingly q-sustainable, then ρ(A) ≤ 1+q.

One may also wonder whether all the feasible payoffs lying above the line (P1 P2 ) can be achieved inthis case. The next result provides a positive answer which is independent of negotiation frictions.
To establish this result, we slightly modify the definition of stability, as follows: deviating proposal
9

See Santos (2000) and Miller-Watson (2013). A similar idea appears in Farrell (1987), Rabin (1994), and Arvan,

Cabral, Santos (1999) for the case of simultaneous announcements.
10
The concepts used in this appendix can be readily re-expressed in terms of contestability.

25

P2

B : ρ(B) < 0

A : ρ(A) > 0
P1

Figure 6: Signed distance from (P1 P2 )

ρ̄ q
1+

Figure 7: Sustainable payoffs without proposer-specific punishments
which is accepted needs to be implemented only if it improves the proposer’s payoff by more thana constant η > 0, arbitrarily small but fixed, over his equilibrium payoff without the deviation.11
Definition 11 A convention C is η-stable if a) each message m ∈ M is assigned a norm in S,
and the payoff vectors implemented by these norms cover all of V (δ), and b) the following holds:

consider any norm of C and history at which i gets a chance to make a proposal and let Ûi denote

i’s continuation payoff. Then, whenever i proposes a norm s ∈ S giving him at least Ûi + η, and−i accepts it, µ is implemented.

Theorem 9 Assuming η-stability, any payoff vector A strictly above the segment (P1 P2 ) is forgivingly sustainable.
11

Using the refinement in Theorem 8 affects the corresponding bound by a factor η.

26

P2

Q1
A1

A2

Q2
P1

Figure 8: Construction of a convention with NFD (payoffs)
The role of η is to prevent off-path proposals whose payoffs lie near the boundary of the convention’s
payoff set, as detailed in the proof of the theorem.

L.1

Proof of Theorem 9 (Sufficient Conditions)Notation: throughout the analysis, for any payoff vector X achieved by some norm of C, we will

denote by X C the corresponding norm.

Consider two feasible Pareto points, Q1 and Q2 , lying at an arbitrarily small but strictly positive
distance from P2 and P1 , respectively, and illustrated by Figure 7. It suffices enough to show thatfor any ε small enough, there exists a forgiving stable convention C which includes Q1 and Q1 as

equilibrium payoffs, that is, convention has elements QC1 , QC2 . By public randomization, this will

imply that this convention can also be made to contain all payoffs above the segment [Q1 , Q2 ]. The
argument below focuses on the case in which P2 and P1 are determined by the minmax payoffs,
which is the harder one.12
We construct a convention which continuation payoffs just after the public randomization stage(before the action stage) consist of the Pareto frontier contained between Q1 and Q2 and of two
additional points, A1 and A2 , respectively lying within ε-proportional distance from Q1 and Q2 , asindicated on Figure 7. We describe the implementation of AC1 and QC1 ; AC2 and QC2 have a symmetric
implementation.
While Q1 is taken as given, the location of A1 depends on ε, and is determined by the following
12

If, say, π1 (P2 ) > v1 , it suffices to set Q1 = P2 in our construction and use it as as the best proposal for player 2.

27

Kε

Q1

Lε
B

C1

C
A1

Figure 9: Construction of a convention with NFD (implementation)
conditions
π1 (A1 ) = π1 (Q1 ) − Kεπ2 (A1 ) = π2 (Q1 ) − Lε,(14)

for constants K and L which will be determined ulteriorly.
To implement AC1 , players are prescribed to minmax each other. The continuation payoff B after
the action stage is a function of the players’ realized actions, a1 and a2 : B = B(a1 , a2 ). The
implementation is illustrated by Figure 9. For any action ai of player i the continuation payoff
πi (B(ai , aj )) does not depend on aj .
Given that player 2 has minmaxed player 1, let Eu1 (a1 ) denote 1’s expected payoff for the period,
as a function of his chosen action, a1 . 1’s continuation payoff, π1 (B(a1 , a2 )), satisfies the promisekeeping condition
π1 (A1 ) = εEu1 (a1 ) + (1 − ε)π1 (B(a1 , a2 )).
A similar relation holds for 2’s continuation payoff. By appropriately choosing players’ continuation
payoffs B(a1 , a2 )(a1 ,a2 )∈A , the construction can make players indifferent between taking any actionin the game.
Moreover, if the constant K appearing in (14) is large enough, then for any action profile (a1 , a2 ),one necessarily has π1 (B(a1 , a2 )) < π1 (Q1 )).13
Consider any of the continuation payoffs B(a1 , a2 )(a1 ,a2 )∈A after the action stage—henceforth referred to as ‘B’ for simplicity. B is a weighted average of three continuation payoffs corresponding
to the following events: player 1 makes a proposal, player 2 makes a proposal, no one makes a
13

Indeed, the distance between A and B(a1 , a2 ) is proportional to ε, with a coefficient bounded above by the highest

absolute value of the payoff of the stage game.

28

proposal. Let C denote the continuation payoff in case no one makes a proposal (this payoff iscomputed before the public randomization taking place in the following period).
For the convention to be forgiving, any rejected proposal results in payoff C. This implies that if
player 1 gets to make a proposal, in equilibrium he proposes the element with a Pareto-efficient
payoff C1 which gives 2 her default value π2 (C), making player 2 to accept the proposal in equilibrium.
The situation is different if player 2 gets to make a proposal. B C gives player 1 a lower payoff than
QC1 , and player 2 is prescribed to propose an element QC1 , which achieves her highest payoff in theconvention and also gives player 1 a higher payoff than C C does.
As shown on Figure 9, at element B C if player 1 gets a chance to make a proposal, he proposes C1C ,if 2 gets a chance to make a proposal, she proposes QC1 . B is thus a weighted average of C, C1 andQ1 . Given any point B, one can find a default option C such that B is indeed the right weighted
average, given the probabilities of proposal for each player.
We will verify at the end of this proof that the constants K and L from (14) may be chosen sothat C lies to the right of the line (A1 , Q1 ). If this is true, C C may be implemented, before public
randomization, as a weighted average of AC1 , QC1 , and QC2 .
The remaining element of interest, QC1 , is implemented as follows: players are prescribed to choose
the pure-strategy Pareto-efficient payoff northwest of Q1 . If 1 deviates in action, the continuation
payoff jumps to B; if 2 deviates, it jumps to the analog of B near Q2 . Players are incentivized to
1 (B)play as prescribed as long as π1 (Q1 )−πis large enough. This is achieved by judiciously choosingεthe constants K and L arising in (14), as explained next.
Determination of the constants K and L
First, we observe that for K large enough, the threat of jumping to continuation B C is enoughto incentivize player 1 to play as prescribed in the implementation of QC1 . We fix such a K—thischoice is independent of ε. We now show that for L big enough, for any realization of B (which
depends on which actions players choose while implementing AC ), the point C will lie to the rightof line A1 Q1 , as mentioned earlier.
Since a player’s probability of proposal and the distance from B to the Pareto line are both proportional ε, the distance between B and C must be proportional to ε2 . Therefore, if we can showthat each continuation point B(a1 , a2 ) lies to the right of the line A1 Q1 , at a strictly positive
ε-proportional distance, so does the point C, for sufficiently small ε.

29The points B(a1 , a2 ) are constructed by promise-keeping conditions. Let B ∗ denote the continuation
payoff, out of all continuations B(a1 , a2 ), which gives the lowest payoff to player 1 and the highest
payoff to player 2. B ∗ corresponds to the highest value Eu1 (a1 ) out of all actions a1 and to thelowest value Eu1 (a2 ) out of all actions a2 . It suffices to show that B ∗ lies to the right of A1 Q1 . We
recall the promise-keeping conditions
π1 (A1 ) = εEu1 (a1 ) + (1 − ε)π1 (B ∗ )π2 (A1 ) = εEu2 (a2 ) + (1 − ε)π2 (B ∗ )or, equivalently,[π1 (A1 ) − π1 (B ∗ )] = ε[Eu1 (a1 ) − π1 (B ∗ )][π2 (A1 ) − π2 (B ∗ )] = ε[Eu2 (a2 ) − π2 (B ∗ )].
∗2 (a2 )−π2 (B )The ratio of the absolute values of the right-hand sides in the two equations above, | Eu
Eu1 (a1 )−π1 (B ∗ ) |,determines the tangent of the angle of the vector A1 B ∗ above the horizontal. Since B ∗ is at an
Eu2 (a2 )−π2 (Q1 )|, plus ε-terms which can be ignored.
ε-distance from Q1 , this ratio simplifies to | Eu
1 (a1 )−π1 (Q2 )Player 1 cannot obtain a higher payoff than his minmax v 1 (as player 2 is minmaxing him), andplayer 2 cannot obtain a lower payoff than her lowest possible payoff in the game, which we denote
2 (Q1 )
as v. Therefore, the angle of the vector A1 B ∗ above the horizontal is no higher than | vv−π−π1 (Q2 ) |, a1

finite value independent of L and ε.

L
The tangent of the angle of the line (A1 Q1 ) above the horizonal is equal to K
. By choosing L high2 (Q1 )∗
enough, this ratio exceeds twice the ratio | vv−π−π1 (Q2 ) |. This guarantees that the vector A1 B lies
1

strictly to the right of the line (A1 Q1 ), as desired.

There remains to check that the convention satisfies all the conditions of Theorem 9. First, bothplayers are incentivized to propose as prescribed: player 1 proposes the best available option for
him, given the default option C. If player 2 wants to improve upon Q1 , she has to propose acontinuation which gives her at least η more than her on-path continuation payoff. For ε smallenough, however, the only proposals that would achieve this would have to give player 1 less thanπ1 (C), and would therefore be rejected. Second, the continuation payoff, C, is the same when aproposal is rejected, regardless of the identity of the proposer and the nature of the proposal. The
convention is thus forgiving. Finally, the point Q1 is a continuation of the convention both afterand before the public randomization, as desired.

30

L.2

Proof of Theorem 8 (Necessary Conditions)

Consider a forgiving stable convention C. For simplicity, we assume that at each stage of thegame—before the action stage, before the proposal stage, and before the public randomization

stage—there exist equilibria in the convention with respective payoff vectors A, B, and C, thatyield the maximal value of ρ at the corresponding stage.14 Let α denote the (possibly mixed)
action profile corresponding to the first-period play implementing element AC —the continuation
before the action stage, and let v(α) denote the expected current payoff resulting from α. Sinceρ(v(α)) ≤ ρ̄, we necessarily haveρ(A) ≤ ερ̄ + (1 − ε)ρ(B)
Point B, which is a continuation payoff before the proposal stage, is the weighted average of thecontinuation payoffs following accepted proposals, and of the default option. When a player—
player 1, say—gets a chance to make a proposal, the expected continuation payoff must lie within√
at most an ε-distance from the Pareto line. Otherwise, player 1 could propose a Pareto point√
which increases both players’ payoffs by a value proportional to ε, and is an equilibrium lying
above the minmax.15 This proposal would then be accepted by player 2 and would be a profitabledeviation for player 1. Therefore, if a player gets a chance to make a proposal, which happens with√probability qε, the resulting continuation cannot have a positive value of ρ that exceeds ε. Whenno one makes a proposal, the continuation payoff is dictated by the default continuation, whose
value of ρ is at most ρ(C). This implies that
ρ(B) ≤ qε ×√ε + (1 − qε)ρ(C).

Finally, since C is a convex combination of payoffs, obtained by public randomization, of equilibrium
payoffs before the action stage whose maximal ρ-value is achieved by A,
ρ(C) ≤ ρ(A).
Combining the above inequalities and getting rid of second-order ε-terms shows Theorem 8.

L.3

Arbitrary number of players without proposer-specific punishment

Finally, consider the most restrictive case of a simple convention that is also forgiving, as definedsimilarly to the simple norm in the two-player case.
14

If the supremum values are not achieved, the proof can be easily adjusted by taking appropriate limits.
With the more permissive concept of an η-stable convention, the continuation payoff has to lie within a distance√of ε + η from the Pareto line. Otherwise player 1 could make a proposal which gives him η more, and gives player√
2 ε more than the continuation payoff.
15

31

Definition 12 A simple convention C is forgiving if, for each period t and history h ∈ H+ endingin period t, the continuation play in case of a proposal not accepted by the supermajority is thesame as if no proposal was made.
The definitions of (forgivingly) sustainable payoffs at frequency q and (forgivingly) sustainablepayoffs are identical to those of the two-player case.
The necessary conditions resemble the two-player case. Let P ′ denote the set of individually-rational
Pareto-efficient payoffs and Co(P ′ ) denote the convex hull P ′ .

Proposition 10 If A is forgivingly q-sustainable, the distance from A to Co(P ′ ) is bounded above
by a decreasing function of q, which converges to 0 as q becomes arbitrarily large.
The proof closely mirrors the argument used for the two-player case and is only sketched here.
Suppose that A is the point of the convention which has the largest distance from Co(P ′ ) andthat A lies “too far” down away from Co(P ′ ). Whenever a player gets to make a proposal—whichhappens with probability proportional to q—he proposes a Pareto point (or close to it). Moreover,the continuation payoff A′ which follows if the proposal is rejected cannot lie farther away from
Co(P ′ ) than A does. Combining this puts a bound on A’s distance to Co(P ′ ), which vanishes as qgets large.
We conclude this section with sufficient conditions.
Theorem 10 Assuming η-stability, any point A in the set Co(P ′ ) lying strictly above the minmax
is forgivingly sustainable.
Proof. [Sketch] We construct a forgiving η-stable convention C as follows. The convention C includes

all Pareto-efficient payoffs which lie at some arbitrary small, but ε-independent distance from theminmax values. The convention C also includes, for each player, a set of Pareto-inefficient elements

used to build a punishment equilibrium for that player, all elements in each set lie within a distanceof order ε from the Pareto-efficient elements of the convention. For each player i, there is a Paretoinefficient payoff vector Ai which gives i his worst payoff in C. The equilibrium ACi which achieves

payoff Ai , together with its continuations, form the punishment set for player i, as described below.
If players were unable to make any proposal, one could implement payoff Ai as follows. Player
i is being minmaxed, which may require other players to use mixed strategies. As described inearlier proofs, this results in a set B 1 of continuation payoffs, (potentially) one for each observed
action profile (these various continuations are needed to incentivize the minmaxing strategy). Each32

continuation payoff B 1 ∈ B 1 is implemented by minmaxing player i, which again generates several

continuation payoffs in the next period, with generic element denoted as B 2 . Player i is minmaxedin this way for several periods. In each period i’s continuation payoff, πi , increases by an amount oforder ε. One can compute the number T of periods needed to minmax player i, so that πi exceeds
πi (Ai ) by a sufficiently high amount that i can be incentivized to play any action by the threatof returning to Ai . The value of T is independent of ε. After these T periods, each continuation
payoff B T can be implemented by playing a deterministic sequence of actions so that the continuation payoff always lies within some ε-proportional distance from B T . This implementation is anequilibrium, since the payoff Ai prevents any deviation from player i, and any deviation by anotherplayer leads to an even larger drop in the continuation payoff of the deviator.
When proposals are re-introduced in the game, there will be changes in the implementation of ACi ,but these changes will be insignificant. After the first round of minmaxing player i, the resulting
continuation payoff B 1 is calculated taken into account the possibility of proposals. That is, B 1C isthe convex combination of some default option, C 1C , if no one makes a proposal, and of proposals
payoffs CiC for each player, which are chosen to be Pareto efficient elements of the convention C.

The distance between the payoffs B 1 and C 1 is of order ε2 —as explained the similar proofs seen

earlier. In the next period, the continuation payoff before the actions will be C 1 (instead of B 1 , inthe previous paragraph). Therefore, if one repeats minmaxing player i for T periods, the resulting
continuation payoff compared to the case with no proposals, will differ by an amount of order ε2 ,which is negligible as ε becomes arbitrarily small. As the value of δ limits to one, the modified
implementation of Ai , based on minmaxing player i for T periods and then choosing a deterministic
sequence of actions, will thus be an equilibrium even with the possibility of proposals.
Finally, the payoff Ai (and, therefore, all the default continuation payoffs C’s) can be chosen so
as to lie within some distance Kε-distance from the Pareto line. With ε small enough, no player
can make an off-equilibrium proposal that would give him a payoff of at least η more than theequilibrium proposal, while keeping all other players at least at well as off as with the default
payoff C. Therefore, the constructed convention is η-stable. Using initial public randomization,
one can then include in the convention any point in the convex hull Co(P ′ ), which concludes theproof.



References
Arvan, L., Cabral, L., and V. Santos (1999) “Meaningful Cheap Talk Must Improve Equilibrium Payoffs,” Mathematical Social Sciences, Vol. 37, pp. 97–106.
33

Evans, J., Maskin, E. (1989) “Efficient Renegotiation-proof Equilibria in Repeated Games,”
Games and Economic Behavior, Vol. 1, pp. 361–369.
Farrell, J. (1987) “Cheap Talk, Communication, and Entry.” Rand Journal of Economics,
Vol. 18, pp. 34-39.
Farrell, J., Maskin, E. (1989) “Renegotiation in Repeated Games,” Games and Economic
Behavior, Vol. 1, pp. 327–360.
Mendelson, E (1997) Introduction to Mathematical Logic, 4th ed. Chapman & Hall, London.
Miller, D., Watson, J. (2013) “A Theory of Disagreement in Repeated Games with Bargaining,”
Econometrica, Vol. 81, pp. 2303–2350.
Rabin, M. (1994) “A Model of Pre-Game Communication,” Journal of Economic Theory, Vol. 63,
pp. 370-391.
Santos, V. (2000) “Alternating-Announcements Cheap Talk,” Journal of Economic Behavior &Organization, Vol. 42, pp. 405–416.

34