# Renegotiation Perfection in Infinite Games

Authors: Julian C. Jamison
Journal: Game Theory
 (2014)

---

## Abstract

We study the dynamic structure of equilibria in game theory. Allowing players in a game the opportunity to renegotiate, or switch to a feasible and Pareto superior equilibrium, can lead to welfare gains. However, in an extensive-form game this can also make it more difficult to enforce punishment strategies, leading to the question of which equilibria are feasible after all. This paper attempts to resolve that question by presenting the first definition of renegotiation-proofness in general games. This new concept, the renegotiation perfect set, satisfies five axioms. The first three axioms—namely Rationality, Consistency, and Internal Stability—characterize weakly renegotiation-proof sets. There is a natural generalized tournament defined on the class of all WRP sets, and the final two axioms—External Stability and Optimality—pick a unique “winner” from this tournament. The tournament solution concept employed, termed the catalog, is based on Dutta’s minimal covering set and can be applied to many settings other than renegotiation. It is shown that the renegotiation perfection concept is an extension of the standard renegotiation-proof definition for finite games, introduced by (Benoit and Krishna 1993), and that it captures the notion of a strongly renegotiation-proof equilibrium as defined by (Farrell and Maskin 1989).


---

## Body

## 1. Introduction

In sharp contrast with the welfare theorems of general equilibrium theory, traditional equilibrium concepts in game theory exhibit no particular tendency to pick out Pareto efficient outcomes. The various Folk theorems suggest that “coordination” may be possible in repeated games but that great many other strategy choices can also be supported as equilibria.1 This result displays an unfortunate lack of predictive power. However, even were it possible to reach an efficient equilibrium in a one-shot game, repeated games pose another quandary: coordination generally requires the threat of punishments, and these are in turn often inefficient by their very nature. Thus if it is always possible to renegotiate to an efficient equilibrium, punishments may no longer be credible and the original equilibrium itself breaks down. Equilibria that are immune to such problems are called renegotiation-proof. The relationship between renegotiation-proofness and Pareto efficiency is exactly analogous to that between subgame perfection and Nash equilibrium: both require credibility of off-path events.The motivation and underlying assumption for the renegotiation literature in game theory is that the group of players as a whole can (and hence will) switch to a Pareto superior outcome whenever possible. The process by which this occurs is not explicitly modeled.2 In this paper we take an axiomatic approach to determine which equilibrium payoffs, the renegotiation perfect set, are possible outcomes in this setting. The first axiom, Rationality, restricts attention to Nash equilibria only. The second axiom, Consistency, requires that all continuation equilibria also be renegotiation perfect. The third axiom, Internal Stability, states that no renegotiation perfect equilibrium should Pareto dominate another. This axiom begins to capture the assumption above, and together these axioms define weakly renegotiation-proof (WRP) equilibria.This relation based on Pareto dominance defines a generalized tournament structure between WRP sets. Axiom four, External Stability, demands that the set of renegotiation perfect equilibria be comparable to all other WRP sets according to the tournament solution concept. This is stability in the sense that if two sets were not distinguishable, there could be no rationale for selecting one of them.3 The final axiom, Optimality, given that everything is now comparable, simply picks out the best element according to the tournament ordering. This is the renegotiation perfect set, a proposed complete solution to the renegotiation problem.The tournament solution concept used in the definition above is termed the catalog of the tournament. A generalized tournament is an incomplete order, or relation, (perhaps intransitive) with qualitative strengths between elements that are comparable. One element is said to cover another if it beats the other and everything the other beats. Dutta [1] introduces the minimal covering set, such that any other element is covered when added to this set. It extends in a straightforward manner to generalized tournaments, and, when iteratively applied, making use of the additional information conveyed by the relation strengths, yields the tournament catalog as defined here. This is a ranking rather than a set of winners only. It is applicable in situations such as voting, where strengths are determined by number of votes received, and equilibrium selection in normal-form games, where strengths might be derived from relative payoffs.The question of renegotiation-proofness in games was first raised for the case of infinitely repeated stage games, in the contemporaneous papers of Bernheim and Ray [2] and Farrell and Maskin [3]. Both papers introduced concepts equivalent to weakly renegotiation-proof equilibria in this setting. In fact this terminology is due to the latter paper, which also defines strongly renegotiation-proof equilibria. Unfortunately these do not exist in all games, but when they do they are contained in the renegotiation perfect set. The question of renegotiation-proofness in finite games is less contentious, having been settled by Benoit and Krishna [4] using a backward induction argument. Their definition, Pareto perfection, is also captured by the renegotiation perfect concept, a useful check on its reasonability. The infinite case has proven to be more troublesome due to the inherent circularities involved, and other partial solutions have been proposed in the last decade.4 An overview of the relevant literature follows in the next section.One final point, concerning nomenclature, is worth making before proceeding with the paper. The renegotiation literature has perhaps been somewhat unfortunately named, in that it is not a theory of renegotiation but rather of the implications deriving from the possibility of renegotiation. This is the reason for using the generic term renegotiation-proofness: it is in fact a theory of nonrenegotiation. Indeed, since all of the games considered have complete information and no stochastic element, all actions are correctly foreseen and hence no actual renegotiation should ever take place. Other roughly synonymous terms for the idea of stability with respect to the constant possibility of unanimous deviation to an alternate and preferred feasible equilibrium are dynamic consistency and Pareto perfection. The moniker “renegotiation perfect” will be reserved for the specific definition developed in this paper.5This outline of the paper is immediately followed by Section2, which presents a more detailed look at the previous literature in the field, including where the present paper lies in relation to it. Section 3 then discusses generalized tournaments and defines the catalog solution concept. Section 4 develops the central axiomatic formulation of renegotiation perfection and states results. Section 5 briefly concludes, and finally an appendix collects proofs of the various propositions.


## 2. Literature

As stated previously, the idea behind the renegotiation question is that somehow the players can get together between actions in the game. At this point they are all aware of what strategy choices are directed by the current equilibrium, but we assume that it is possible for them to switch to different strategies if they can believably agree to do so. This can be because of explicit opportunities to communicate,6 or it can be due to more indirect machinations. In any case, the vital problem is that of determining believability, which has three attributes: first, that the new choices constitute an equilibrium; second, that the associated payoffs Pareto dominate the payoffs expected according to the current equilibrium (else why switch?); and third, that the proposed new equilibrium be immune to the same sort of deviations (else how is it credible?). In infinitely repeated games, this introduces an obvious circularity and so the problem is born. Note that this discussion is implicitly assuming a kind of stationarity, in that the solution to the problem will be a single set of renegotiation-proof equilibria to be considered feasible at any time. This set depends only on the structure of the game and not, for example, on the history of play.7 In particular, no preference is given to the current equilibrium, unlike in several of the papers discussed below.8 The justification for this approach is that an equilibrium concept is being defined, rather than say a process. One would not expect the set of Nash equilibria in identical subgames to depend on the history of actions so far.One paper that does discuss an explicit model of communication is Blume [5], which also considers bargaining over continuation payoffs. The focus in this paper is over the bargaining outcomes rather than the renegotiation question. It treats primarily the case of finite games, although the model is briefly extended to cover the infinite case as well. Unfortunately, existence cannot be guaranteed in the infinite setting, which is a common drawback arising from the circular nature of the problem. It also differs from the present paper by imposing costs on bargaining. Another paper looking at bargaining instead of Pareto jumps between equilibria is that of Abreu et al. [6]. This approach is better suited to some situations than to others, and naturally more assumptions need to be made about the explicit nature of the process. The analysis here is more general (apart from spelling out the details of the bargaining game) but also more difficult, tending to yield more limited results. Something like it, however, would be an important addition to the model of the present paper. Finally, this is related to the coalition-proofness concept, developed by Bernheim et al. [7], in which some of the same questions arise as in renegotiation models.Returning to the slightly simpler, baseline case of unanimity (Pareto dominance) and stationarity (“let bygones be bygones”), we start with finitely repeated games. Here the definitive paper is Benoit and Krishna’s [4], which gives a full characterization of the Pareto perfect equilibria and discusses behavior as the time horizon lengthens indefinitely. Just as with subgame perfection, the definition proceeds backward step by step, recursively requiring efficiency subject to the constraints imposed by the set of feasible continuation equilibria. These equilibria turn out to be neither generically efficient nor generically inefficient within the entire SPE set. Renegotiation perfection, which applies to all finite games, coincides with Pareto perfection in finitely repeated games. In this sense, it is an extension of the finite definition to the infinite case. A scattering of other works has been done on renegotiation-proofness in finite games; for instance, Wen [8] centers on finite games with more than two players.The literature on renegotiation-proofness in infinitely repeated games began with the simultaneous (and neighboring) papers of Bernheim and Ray [2] and Farrell and Maskin [3], predating and stimulating the work on finite games. The increase in difficulty for the infinite case arises from the fact that it is necessary to determine the set of renegotiation-proof equilibria at the same time that the set of credible continuation equilibria is determined. If in a particular game the question of feasibility had been previously resolved for all equilibria but one, the problem would be trivial for that one, by comparing it with the feasible equilibria and checking that its continuation equilibria were all feasible. But to do this for all equilibria simultaneously is more troublesome.Bernheim and Ray [2] define internally consistent equilibria to be those such that the equilibrium and all of its continuation equilibria are mutually Pareto incomparable. They then strengthen this to the concept of consistent sets, which always exist. Unfortunately there may be multiple consistent sets, and elements of one may dominate elements of another, so it is not clear how to interpret the choice of any particular one of them. This is a case for which the stationarity assumption will not be satisfied.Farrell and Maskin [3] introduce the concept of a weakly renegotiation-proof (WRP) set and equilibrium. Their definition is equivalent to internal consistency, and both are equivalent to axioms one through three below when applied to infinitely repeated games.9 They give a fairly full characterization of WRP sets, including generic intersection with the Pareto frontier, and analyze examples of WRP equilibria in various games. They too impose an external condition, deriving a new concept called strongly renegotiation-proof (SRP). A set is said to be SRP if it is WRP and if no element is dominated by any element of a WRP set. This avoids any circularity but is conceptually an overly strict condition since a WRP set may be excluded on the basis of another WRP set that is in turn also excluded. Indeed, SRP equilibria often fail to exist in practice. Any SRP equilibrium that does exist is also renegotiation perfect, as shown in Section 4 below. So renegotiation perfection is an extension of this idea that exists for all games. This also implies that their characterization results about SRP sets (and WRP sets) can be carried over to the renegotiation perfection context.Abreu and Pearce [9] and Pearce [10] also study renegotiation in infinite games, but with quite a different approach. They do not require internal stability for an equilibrium to be renegotiation-proof. The reason that this can be consistent is that stricter conditions are placed on proposed deviations than are placed on the current equilibrium. So punishments may still be credible, since it is no longer necessarily possible to return to the original equilibrium. This is of course a departure from the stationarity assumption outlined above, and it is also the case that existence fails here for certain types of games. However, in some situations this provides a truly viable alternate model of renegotiation.Bergin and MacLeod [11] synthesize much of the literature (up to that point), including both the finite and infinite cases. They provide an almost complete axiomatic framework, in order to relate previous work, which unfortunately but inevitably involves considerable notation. They also have a brief section on the explicit modeling of communication. The only new concept introduced, recursive efficiency, again gives some precedence to the status quo, though it has some other desirable qualities. One reason for the prevalence of such nonstationary approaches is that they help to alleviate the circularity and self-comparison problems.It is worth pointing out that there is an entire renegotiation literature in contract theory as well. One of the main distinctions between it and the game theory literature, of course, is that the principal is generally choosing the contract. The effect of allowing renegotiation is therefore always negative (from the principal’s point of view), even if renegotiation only occurs with the consent of both parties, because avoiding it becomes simply one more constraint in the principal’s optimal contract problem. This result is roughly consistent with the game theoretic result that it may be impossible to reach the Pareto frontier if renegotiation is allowed. The contracts literature is often more general along the dimension of allowing asymmetric information, stochastic output processes, and so forth (which implies that renegotiation may actually take place in equilibrium). On the other hand, it tends to be limited to a finite number of periods, usually two, and is thus of only modest help in the present effort.


## 3. Tournaments

In this section we examine some aspects of tournament theory and define a generalized tournament. Iterative applications of the minimal covering set, along with suitable extensions thereof, allow us to distinguish and then rank elements as finely as possible. One component of generalized tournaments, the relative strength of the relation between elements that are in fact comparable, is naturally helpful in this endeavor. The result is called the catalog of the tournament and is of independent interest as well as of interest to applied work in various fields. Of course, it is developed here specifically in preparation for the analysis of renegotiation in the next section. The efficient reader can focus on Definitions1–4 and the result of Proposition 11 as the minimally necessary background for the remainder of the paper.Definition 1.
A tournamentT is a pair (
T
,
R
) such that (a)
Tis a finite set;
(b)
R is a binary relation on T;
(c)
∄
x
∈
T: x
R
x;
(d)
∀
x
,
y
∈ either x
R
y or y
R
x but not both.The motivation for the name lies in the original story of a group of contestants, vying for a prize, who meet pairwise with each match producing exactly one winner. A more practical example giving rise to the same situation is a voting model in which there is a selection of alternatives and it is known how each would fare against any other single alternative.10 In both cases, the problem is usually how to pick a winner or set of winners, and there is a multitude of solution concepts available in the tournament literature. Naturally, if x is a Condorcet winner, that is, if x
R
y
∀
y
∈
T
/
x, then x is the unique winner according to any of the solution concepts. The difficulty arises when there is no such x.Definition 2.
A generalized tournamentT is a triple (
T
,
R
,
λ
) such that (a)
R is a binary relation on T;
(b)
∄
x
∈
T
:
x
R
x;
(c)
λ is a label function from {
(
x
,
y
)
∈
T
2
∣
x
R
y
} to the real line ℜ;
(d)
if{
x
n
}
⊆
T with lim
⁡
n
→
∞
x
n
=
x and x
n
R
y
∀
n (resp., y
R
x
n
∀
n), then x
∈
T and x
R
y (resp., y
R
x).The last part of the definition, which is trivially satisfied ifT is finite, is a technical condition that basically says that T should be closed in some topology and the tournament structure (as given by R) should be continuous with respect to that topology. This extends the standard tournament concept in three directions: first, elements are permitted not to be comparable (i.e., to tie); second, elements that are comparable have a label on their relationship, which can be interpreted as a qualitative assessment of the strength of the comparison; and third, infinite tournaments are allowed, as long as they satisfy the basic “niceness” property of condition (d). For instance, in the voting context ties are no longer a problem, and the labels might correspond to the relative number of votes for one option when paired against another, incorporating more information into the model. In Section 4 below, a method for deriving a generalized tournament from an arbitrary binary relation is described, but for now we simply assume that we are given one from whatever source and begin the process of comparing and ranking elements.Definition 3.
Forx
,
y
∈
T, by x
c
o
v
e
r
s
y (written x
≻
y) we understand that x
R
y and that ∀
z
∈
T
y
R
z
⇒
x
R
z. The uncovered set UC
(
T
) is then {
x
∈
T
∣
∄
y
∈
T
:
y
≻
x
}.The idea is that if one element covers another, this implies an unambiguous comparison between the two in favor of the first one: it beats the second and it beats everything the second one beats as well. The uncovered set is simply the set of maximal elements with respect to this order. SinceT induces a canonical relation on any subset of T, we can define UC
2
(
T
)
=
UC
(
UC
(
T
)
)
,
UC
3
(
T
)
,
…
,
UC
∞
(
T
), known as the iterated uncovered sets. However it is possible to refine this idea even further.Definition 4.
The minimal covering setMC
(
T
) is the smallest subset of T satisfying
(1)
∀
x
∈
T
∖
MC
(
T
)
,
x
∉
UC
(
MC
(
T
)
∪
{
x
}
)
.When applied to standard tournaments, this is equivalent to the definition given by Dutta [1]. It says that any other element, when added to this set, will be covered by some element of the set. In some sense, these are the core stable elements, at least with respect to the covering relation and, for now, excluding information from the labels. The minimal covering set has many desirable properties for a tournament solution concept, several of which will be needed in the sequel and are therefore stated here.Proposition 5.
It is shown as follows.(a)
Covering is a transitive relation.
(b)
M
C
(
T
)
exists and is well defined for all generalized tournaments
T.
(c)
M
C
(
T
)
⊆
U
C
∞
(
T
).
(d)
M
C
(
M
C
(
T
)
)
=
M
C
(
T
)
, and hence
U
C
(
M
C
(
T
)
)
=
M
C
(
T
).
(e)
M
C
is monotonic; that is, if
x
∈
M
C
(
T
)
and
R
is changed so as to strengthen
x
(leaving all else unchanged), it is still the case that
x
∈
M
C
(
T
).
(f)
M
C
is independent of losers; that is, neither deleting any
x
⊈
M
C
(
T
)
nor changing
R
outside of
M
C
(
T
)
has any effect on
M
C
(
T
)
.
(g)
The minimal covering set can be characterized axiomatically.The idea is to now extend the minimal covering set solution in two ways. The first of these is to get a full ranking rather than a set of winners (along the lines of looking atMC
(
T
∖
MC
(
T
)
), and so on). The second is to refine these sets further, in part by using the label information that is available. This is because it is necessary to distinguish and rank elements as discriminately as possible. The approach is to define two further relations on the same set T, without labels, and to use their minimal covering sets as necessary in an iterative procedure that continuously breaks T down into disjoint subsets, with a complete ordering between the subsets. This will be the tournament catalog. For clarity, if A
⊆
T we write MC
R
(
A
) for the minimal covering set of A according to the relation on A induced by R on T.Definition 6.
The binary relationS
A on A
⊆
T is given by
(2)
∀
x
,
y
∈
A
,
x
S
A
y
iff
x
∈
MC
R
(
A
∖
{
y
}
)
but
y
⊈
MC
R
(
A
∖
{
x
}
)
.In essence, this says thatx is superior to y, according to this relation, whenever removing x means that y is not a “winner,” but not vice versa. That is, x does not depend on y in order to argue that it should be chosen. If x, but not y, is in MC
(
A
) then x
S
A
y holds trivially, but this relation is particularly useful for comparing elements within the minimal covering set itself without introducing any new concepts. It is this refinement that we are interested in. Naturally, we denote minimal covering sets with respect to this relation by MC
S, with the subscript on S implied by the argument to the MC operator.Definition 7.
IfA
=
{
A
i
}
i
=
1
n
⊆
T
n such that A
i
⊆
A
i
+
1
for
all
i
=
1
,
…
,
n
-
1, the binary relation L
A on A
1 is given by for all x
,
y
∈
A
1
x
L
A
y if and only if there exists i such that either (a)
for
all
z
∈
A
i
:
x
R
z and y
R
z, λ
(
x
,
z
)
≥
λ
(
y
,
z
) with at least one strict inequalityor(b)
{
z
∈
A
i
∣
y
R
z
}
⊂
{
z
∈
A
i
∣
x
R
z
} and for
all
z
∈
A
i
:
y
R
z
λ
(
x
,
z
)
≥
λ
(
y
,
z
).This third relation makes use of the strength assessments to differentiate even further among elements. Given a nested sequence of sets, we compare elements of the innermost set by checking to see if one “weakly dominates” the other in label strength over the set of things beaten by both or if one beats strictly more elements than the other and at least as strongly. To allow the widest room for comparison, the domination can take place at any superset in the given sequence.11 Because direct comparisons between elements according to the basic relation R are more relevant to choosing a winner, the label relation, denoted by a superscript L, is reserved for third-string efforts to produce a ranking (recall that the goal is to distinguish as finely as possible). In other settings, however, it is possible that labels would be the primary or only means of comparison.We are now ready to give the formal, recursive algorithm that produces the tournament catalog. Fix a generalized tournamentT and consider subsets A
σ of T, where σ
∈
[
0,1
]
<
∞ is a finite list of numbers in the unit interval. Notationally, we take A
⌀
=
T. By σ
|
n we understand the restriction of σ to its first n components, and by σ
,
α for α
∈
[
0,1
] the concatenation of σ and α, therefore, is also a point in [
0,1
]
<
∞.Definition 8.
GivenA
⌀
⊆
T, the process ℘ is as follows. (1)
IfMC
R
(
A
σ
)
=
A
σ, go to (2).
Otherwise, pick an index setA
σ
⊆
[
0,1
] containing {
0,1
} and define
A
σ
,
β
=
MC
R
(
∪
{
A
σ
,
α
∣
α
≤
β
,
α
∈
β
σ
}
), so that in particular
A
σ
,
1
=
MC
R
(
A
σ
). Now apply ℘ to A
σ
,
β for each β
∈
B
σ.
(2)
IfMC
s
(
A
σ
)
=
A
σ, go to (3).
Otherwise, pick an index setA
σ
⊆
[
0,1
] containing {
0,1
} and define
A
σ
,
β
=
MC
s
(
∪
{
A
σ
,
α
∣
α
≤
β
,
α
∈
β
σ
}
), so that in particular
A
σ
,
1
=
MC
s
(
A
σ
). Now apply ℘ to A
σ
,
β for each β
∈
B
σ.
(3)
Letn
=
|
σ
| and set A
i
=
A
σ
∣
n
+
1
-
i for i
=
1
,
…
,
n
+
1, so that A
=
{
A
i
}
i
=
1
n
+
1 is a nested sequence of sets in T and L
A is thereby defined.
IfMC
L
(
A
σ
)
=
A
σ, apply ℘ to A
σ
,
1
=
A
σ.
Otherwise, pick an index setB
σ
⊆
[
0,1
] containing {
0,1
} and define
A
σ
,
β
=
MC
L
(
∪
{
A
σ
,
α
∣
α
≤
β
,
α
∈
β
σ
}
), so that in particular
A
σ
,
1
=
MC
L
(
A
σ
). Now apply ℘ to A
σ
,
β for each β
∈
B
σ.This completes the definition. The idea is that, at each step, we first look to see if the standard minimal covering set has any effect. If it does, we use it to divide the original set into disjoint subsets, each of which is the minimal covering set for everything up to and including itself. These sets are naturally ordered, and their indicesβ retain that order. We then apply ℘ iteratively to each subset, attempting to refine further. If MC
R has no effect, we turn to the relation S and perform the same check, proceeding analogously if possible. Finally, the label relation L is employed, and if it fails then the process gives up. In nonpathological cases, very few steps will not be vacuous. If we apply ℘ to the whole tournament, that is, to A
⌀
=
T, then for each x
∈
T and n
<
∞ there is exactly one σ
n
(
x
) with |
σ
|
=
n and x
=
A
σ. Furthermore, these are consistent in the sense that if n
<
n
′ then σ
n
(
x
)
=
σ
n
(
x
)
∣
n, and hence σ
(
x
)
∈
[
0,1
]
∞ is well defined as the “limit” of σ
n
(
x
)’s.Definition 9.
For a generalized tournamentT, the catalog order is given by
(3)
∀
x
,
y
∈
T
x
<
c
y
⟺
σ
(
x
)
<
lex
σ
(
y
)
.
The tournament catalog is the pair (
T
,
<
c
).Of course,<
lex refers to the lexicographic order. It is appropriate in this case because the first component of σ
(
x
) refers to the first step in the process ℘, which is more authoritative in the sense that later steps are refinements of it. So elements are compared first on this basis, next on the second step, and so on. Of course, several elements may induce the same sequence σ; they are indistinguishable by ℘. The tournament catalog is a “pseudochain”: two elements may not be comparable, but in this case the set of successors (or predecessors) of one of them is identical to that of the other one.12 In some contexts, there is a distinguished element x
0
∈
T, such as the status quo in voting or more generally any default or focal point. By definition, this element can be differentiated from all others.Definition 10.
LetI
(
T
) be the closure of {
x
∈
T
∣
∄
y
∈
T
:
σ
(
x
)
=
σ
(
y
)
}
∪
{
x
0
}.
Then the catalog index forT is the pair (
I
(
T
)
,
<
c
).The index of a tournament thus picks out all elements that can be unambiguously compared with every element of the tournament (not just of the index),13 and it is maximal with respect to this property. It is in fact completely ordered, as seen below.Proposition 11.
It is shown as follows.(a)
The tournament catalog and its index are well defined.
(b)
The catalog index is a chain.This concludes the presentation of the catalog (and its index) as a solution concept for generalized tournaments. In the following section, this concept is utilized to help develop a notion of renegotiation-proofness (and some examples of catalogs are given). However, it has many other applications, including the simple voting context used throughout the course of the discussion. One other possible application is to the equilibrium selection problem in normal-form games. In this case we might say thatx
R
y if a majority (or two-thirds or all) of the players prefer outcome x to outcome y, and the labels are based on individual payoff differences between the equilibria. The motivation for such a model is that rational players, if faced with a selection problem, should try to pick out the “best” (i.e., winning in the terminology of tournaments) equilibrium and base their actions choices on that decision, assuming that others are doing likewise.14


## 4. Renegotiation

This section develops the central model of the paper. Five axioms are discussed, which together lead to the definition of renegotiation perfect equilibria. The axioms attempt to capture some of what is meant by being renegotiation-proof or immune to the possibility of unanimous deviations to Pareto superior alternatives. Examples are given, and formal relationships with previous work are outlined. The latter conclusions, that renegotiation perfection generalizes previous concepts, allow direct referral to some known characterization results.We consider arbitraryn-player extensive-form games with perfect recall and at least one Nash equilibrium;15 the set of all such games is called G. The strategy space of a game G
∈
G is denoted by Σ
(
G
)
=
×
i
=
1
n
Σ
i
(
G
), and payoffs are mappings u
i
:
Σ
(
G
)
→
ℜ. We let NE
(
G
) be the set of Nash equilibria of G and let u
(
NE
(
G
)
)
⊆
ℜ
n be the associated set of Nash payoffs. If the action history h leads to a singleton information set (such as between stages in a stage game with perfectly observed actions), this begins a well-defined subgame G
′
=
G
∣
h, and then a strategy profile σ
∈
Σ
(
G
) induces continuation strategies σ
′
=
σ
|
h
∈
Σ
(
G
′
) and continuation payoffs u
(
σ
′
)
∈
ℜ
n. The axioms are on set-valued correspondences R
:
G
⇒
ℜ
n. That is, for all G
∈
G, R
:
G
↦
R
(
g
)
⊆
ℜ
n. ConsiderA.1
(Rationality)∀
G
∈
G
,
R
(
G
)
⊆
u
(
NE
(
G
)
).The first axiom simply states that all payoffs in theR-set should be supportable by Nash equilibria. Since, ultimately, the goal is to define a new equilibrium concept addressing renegotiation concerns but within the existing framework; this requirement is straightforward. ConsiderA.2
(Consistency) Anyu
∈
R
(
G
) equals u
(
σ
) for some σ
∈
Σ
(
G
) such that if σ
′
=
σ
∣
h for some history h, then u
(
σ
′
)
∈
R
(
G
′
), where G
′
=
G
|
h is the induced subgame.The second axiom is likely equally uncontroversial, asking for a basic dynamic consistency in the correspondenceR. The motivation is that if an equilibrium requires the use of continuation payoffs which are not themselves feasible (according to R), then they will be unable to effectively enforce the original equilibrium, rendering it infeasible as well. This is analogous to the credibility arguments supporting the subgame perfection concept, and indeed it is clear that the first two axioms together imply that all payoffs in the R-set are supportable with subgame perfect equilibria.Definition 12.
IfA
,
B
⊆
ℜ
n then A confounds B, written A
⊳
B, if A
∩
[
B
+
ℜ
+
+
n
]
≠
⌀.This is equivalent to saying that there is some element ofA that strictly Pareto dominates some element of B. This is a key notion in the context of renegotiation since the underlying assumption is that there is always the possibility of jumping to Pareto superior points.16 That is, if players are expecting payoffs from a set B and they may have an incentive to switch to the set A, calling into question the believability of ever expecting B. ConsiderA.3
(Internal Stability)∀
G
∈
G
,
R
(
G
)
⋫
R
(
G
).Axiom three demands that there be no strict Pareto dominance within theR-set itself.17 The rationale for the axiom then follows from the definition and the fact that the central notion under consideration is credibility: anything in this set is by assumption credible and is therefore a viable alternative at any time. Hence anything dominated by such a point will be renegotiated away from and cannot itself be renegotiation-proof, which is precisely the statement of the axiom. Put slightly differently, the set R
(
G
) forms a Pareto antichain.Definition 13.
IfR satisfies A.1–A.3, then R
(
G
) is a weakly renegotiation-proof set in G.These WRP sets form the building blocks for much of the rest of the discussion. In the context of infinitely repeated stage games, it is easy to see that this definition coincides with that of Farrell and Maskin [3], from whom the terminology is taken. It is thus also equivalent, in that context, to the notion of internally consistent sets as introduced by Bernheim and Ray [2]. For a given game G, we let W
(
G
) be the set of all WRP sets in G. There is typically a multitude of WRP sets in any particular game, some of which may be preferred to others by all players in all circumstances. This lack of external comparison (along with the lack of uniqueness) makes weak renegotiation-proofness an insufficient concept. Farrell and Maskin characterize all equilibria that can be supported with WRP payoffs and show that generically some of these are efficient.In order to make comparisons within the class of WRP sets, we shall use the tournament index concept developed in the previous section. This requires a relation on the setW
(
G
) to make it into a generalized tournament. The basic comparison available is whether or not one set confounds another, directly or indirectly (i.e., through a sequence of sets, each confounding the next).18 Formally, fixing G and for x
,
y
∈
W
(
G
) define k
(
x
,
y
)
=
min
⁡
〈
n
∣
∃
x
=
x
0
,
x
1
,
…
,
x
n
=
y s.t. x
i
∈
W
(
G
)
∀
i and x
i
⊳
x
i
+
1
∀
i
=
0,1
,
…
,
n
-
1
〉, with k
(
x
,
y
)
=
∞ if no such n exists. We also make use of the set of predecessors of x in W
(
G
), namely, ⊳
+
(
x
)
=
{
y
∈
W
(
G
)
∣
y
⊳
x
}.Definition 14.
FixG and let x
,
y
∈
W
(
G
) be WRP sets in G. Then x
R
y if (a)
k
(
x
,
y
)
<
k
(
y
,
x
);
(b)
k
(
x
,
y
)
=
k
(
y
,
x
) but x
⊃
y; or
(c)
k
(
x
,
y
)
=
k
(
y
,
x
)
,
x
⊈
y but ⊳
+
(
x
)
⊂
⊳
+
(
y
).Thus to comparex and y, we first check to see if one confounds the other more directly. Recall the definitions and motivations: this means that it is easier to renegotiate (by way of Pareto jumps) from y to x than it is from x to y. For instance, it may be that x indirectly confounds y in a minimal chain of three steps but y cannot indirectly confound x at all. Then x is in a stronger, or more dominant, position and so x
R
y. If on the other hand this comparison cannot be made, then a strictly larger set is preferable because (other aspects being equal) we wish to be as open-minded as possible when considering whether or not certain payoffs are renegotiation-proof.19
,
20 Finally, since once again the goal is to use as much information as possible to distinguish elements (in this case WRP sets), a simple comparison between predecessors can be made. One set is in a stronger position than another if everything that confounds it also confounds the other but not vice versa.21Definition 15.
The renegotiation tournamentT
(
G
) is (
W
(
G
)
,
R
,
λ
) where λ
(
x
,
y
)
=
(a)
(
-
k
(
x
,
y
)
)
/
k
(
y
,
x
) if k
(
y
,
x
)
<
∞ and 1
/
k
(
x
,
y
) otherwise,
(b,  c)
0 anytime thatk
(
x
,
y
)
=
k
(
y
,
x
).Of course this also yields a catalog order<
c on W
(
G
) and a completely ordered index I
(
T
(
G
)
) for the renegotiation tournament. We define the distinguished element x
0 to be the Pareto frontier of the convex hull of payoffs achievable by myopically optimal subgame perfect equilibria.22 These, even if nothing else can be agreed upon, are certainly feasible and can be differentiated. As stated previously, it would also be possible to define x
0 as the payoffs arising from the current (i.e., status quo) equilibrium, as long as they formed a WRP set. With this firmly in hand, we are now ready to state the final two axioms of renegotiation perfection. ConsiderA.4
(External Stability)∀
G
∈
G
,
R
(
G
)
∈
I
(
T
(
G
)
).The fourth axiom basically requires that theR-set always be comparable in the catalog order with all other WRP sets in G. This is the essence of being externally stable: if it were not distinguishable then by definition it would be at best an arbitrary choice. The true danger here lies in the fact that an equally valid argument could then be made in favor of any WRP set not comparable with it, meaning it could be renegotiated away from if the possibility arose and thus violating the whole motivation.A.5
(Optimality)∀
G
∈
G and x
∈
I
(
T
(
G
)
)
,
x
≯
c
R
(
G
).The final axiom states that no distinguishable (i.e., externally stable) WRP set should be greater in the catalog order than theR-set. If there was such a “better” set, it would not be rational for optimizing players to accept only the R-set, again violating the motivation that we are attempting to list certain properties in agreement with our sense of what renegotiation-proof sets ought to behave like. Separating the external requirements into these two distinct conditions turns out to be, perhaps somewhat surprisingly, one of the most clarifying aspects of this approach. We list the axioms once more in their entirety for the sake of completeness:A.1
(Rationality)∀
G
∈
G
,
R
(
G
)
⊆
u
(
NE
(
G
)
)
A.2
(Consistency) Anyu
∈
R
(
G
) equals u
(
σ
) for some σ
∈
Σ
(
G
) such that if σ
′
=
σ
|
h for some history h, then u
(
σ
′
)
∈
R
(
G
′
), where G
′
=
G
|
h is the induced subgame.
A.3
(Internal Stability)∀
G
∈
G
,
R
(
G
)
⋫
R
(
G
).
A.4
(External Stability)∀
G
∈
G
,
R
(
G
)
∈
I
(
T
(
G
)
).
A.5
(Optimality)∀
G
∈
G and x
∈
I
(
T
(
G
)
)
,
x
≯
c
R
(
G
).Definition 16.
A correspondenceR
:
G
⇒
ℜ
n is renegotiation perfect if it satisfies A.1–A.5. In this case, R
(
G
) is called the renegotiation perfect set (of payoffs) for G, denoted by RP
(
G
), and a strategy profile σ
∈
Σ
(
g
) is a renegotiation perfect equilibrium of G if, for all histories h (inducing strategies σ
′ on the subgame G
′), u
(
σ
′
)
∈
R
(
G
′
).Proposition 17.
∀
G
∈
G, R
P
(
G
) is nonempty and well defined (i.e., unique).Thus a renegotiation perfect equilibrium is a strategy profile such that all of its continuation payoffs are in the appropriate renegotiation perfect set, and these equilibria exist for all extensive-form games (at least those with a Nash equilibrium). The axioms require that renegotiation perfect sets be self-enforcing and resistant to counter proposals from both within the set and outside it. It is also possible, without invoking an entire cooperative framework, to interpret the axioms in a societal manner; for instance, A.1 is individual rationality, while A.5 is social rationality.23We turn next to the particular setting of finitely repeated stage games, for which there exists already an accepted definition of renegotiation-proofness. This is the Pareto perfection concept developed by Benoit and Krishna [4].24 To briefly recap their definition, let G be a one-shot game25 with a Nash equilibrium and let P
1
=
WEff
NE
(
G
), the set of weakly efficient Nash equilibria of G. Next let Q
2
⊆
Σ
(
G
2
) be the set of all subgame perfect equilibria of G
2 that use only continuation equilibria in P
1; with two periods remaining nothing else is credible, given that otherwise renegotiation to some element of P
1 would occur in the final period. Since optimality must hold at this stage as well, they define P
2
=
WEff
Q
2. By iterating this recursive efficiency procedure, one reaches P
m, the set of Pareto perfect equilibria of the m-repetition G
m.Proposition 18.
For any one-shot gameG, R
P
(
G
m
)
=
u
(
P
m
)   ∀
m
=
1,2
,
….This result and its proof imply that, in finitely repeated stage games, all Pareto perfect equilibria are renegotiation perfect, and vice versa. In this sense, renegotiation perfection is an extension (there may be several) of Pareto perfection to infinite games. Since the latter concept is relatively uncontroversial, this provides a good plausibility check on the former concept. The intuition behind the proof of the proposition, which uses induction to show thatu
(
P
m
) satisfies A.1–A.5, is straightforward. Axioms one and three are trivial (minimal WRP sets are all singletons here), axiom two follows from the inductive hypothesis, and axioms four and five follow from the fact that u
(
P
m
) is in fact a Condorcet winner in the renegotiation tournament. To look at it in the other direction, axioms one through three imply that only subgame perfect equilibria with renegotiation perfect continuation payoffs can be considered, that is, Q
m, and then axioms four and five narrow it down to the Pareto frontier of this set, that is, P
m. Everything tends to be simpler in the finite case, but the underlying processes are identical to the general case.We next briefly consider the particular case of infinitely repeated games, which has occupied much of the attention in the renegotiation literature. One partial solution in this context was introduced in the original paper by Farrell and Maskin. In the present terminology, it can be stated as follows.Definition 19.
A setx
∈
W
(
G
) is strongly renegotiation-proof (SRP) in G if there exists no y
∈
W
(
g
) such that y
⊳
x.That is, no element of the WRP setx should be Pareto dominated by any element of any other WRP set. In terms of logical consistency of the definition, this requirement is definitely too strict (as the authors explicitly acknowledge in their choice of a name), since it rules out sets simply because they are confounded by other sets that may or may not be SRP themselves. This avoids many of the circularity problems but also avoids the underlying motivation that only jumps to continuation payoffs that are themselves feasible should constitute valid objections or deviations. However, these equilibria are easier to define and, precisely because the constraint is overly strict, any payoff that is supported by such an equilibrium is indisputably renegotiation-proof.26 The problem, of course, is that there may exist no such equilibria at all, which again runs counter to the idea behind models of renegotiation-proofness that they are a search for what outcomes might reasonably be agreed upon by rational players in this setting.Proposition 20.
IfG is an infinitely repeated game and x is SRP in G, then x
⊆
R
P
(
G
).This result says that SRP payoffs, if they exist, are also renegotiation perfect. Since SRP equilibria (supported entirely by SRP payoffs) do exist in some games of economic interest, and since Farrell and Maskin [3] are able to show some properties of SRP equilibria (including some results about when they exist), this is a useful proposition in terms of better understanding renegotiation perfect equilibria. Characterizing its formal relationship with other proposed concepts for infinite games would be a logical next step in this regard.


## 5. Conclusion

This paper has presented a new definition, renegotiation perfect equilibrium, for extensive-form games. The problem it attempts to address is of what happens if players are given the opportunity to “renegotiate” to Pareto superior payoffs between actions in the game. Given that this is the case, punishments may no longer be credible. Rational players will be able to foresee this problem and will avoid equilibria which cannot be supported, but what, in the end, is the set of feasible equilibria? This is an important question since it merges the off-path credibility requirements epitomized by subgame perfection with the social choice arguments behind Pareto optimality. At least in the self-referential world of infinitely repeated games, it has also proven to be a difficult question to address. While renegotiation perfection does not have all the answers, it is the first proposed solution that applies in all contexts and exists for all games.The innovation in the present axiomatic approach is twofold: first, the application of tournament theory to the renegotiation problem (including the development of the catalog, a new solution tool for generalized tournaments that is independently useful); and second, considering the questions of external stability (i.e., distinguishability) and optimality (i.e., maximality) separately. The main results are that renegotiation perfect payoffs exist for all extensive-form games, finite and infinite, and that they capture key previous concepts from the literature.Naturally, the analysis of renegotiation perfection is incomplete. It would be beneficial to have true formal models of the underlying communication and bargaining processes (including perhaps adding the possibility of coalition formation). A fuller characterization of renegotiation perfect payoffs, both in specific games and in general, would lead to a deeper understanding of the concept. But quite possibly the most fruitful investigations, however, are in the field of stochastic games. It is only in this context that actual renegotiation can be expected to take place in equilibrium, so that the goal is to eventually have not just a theory of renegotiation-proofness but rather an actual working theory of renegotiation. Such an extension would provide an excellent opportunity to test the implications and the relative merits of any competing theories of renegotiation-proofness. This paper attempts to provide one step in the progression toward these future endeavors.



---

*Source: 742508-2014-02-26.xml*