Player-Compatible Learning and Player-Compatible Equilibrium
Drew Fudenberg Kevin He
econ.TH




Player-Compatible Learning and Player-Compatible EquilibriumWe thank Alessandro Bonatti, Dan Clark, Glenn Ellison, Ben Golub,
Shengwu Li, Dave Rand, Alex Wolitzky, and Muhamet Yildiz for valuable
conversations and comments. We thank National Science Foundation grant
SES 1643517 for financial support, and Giacomo Lanzani for research
assistance.
    Drew FudenbergDepartment of Economics, MIT. Email: 
Kevin HeCalifornia Institute of Technology and University of Pennsylvania.
Email: 
    

First version:     September 23, 2017This version:     May 27, 2020
==========================================================================================================================================================================================================================================================================================================================================================


Player-Compatible Equilibrium (PCE) imposes cross-player restrictions
on the magnitudes of the players' “trembles”
onto different strategies. These restrictions capture the idea that
trembles correspond to deliberate experiments by agents who are unsure
of the prevailing distribution of play. PCE selects intuitive equilibria
in a number of examples where trembling-hand perfect equilibrium <cit.>
and proper equilibrium <cit.> have no bite.
We show that rational learning and weighted fictitious play imply
our compatibility restrictions in a steady-state setting.

Keywords: non-equilibrium learning, equilibrium refinements,
trembling-hand perfect equilibrium, weighted fictitious play.

empty









§ INTRODUCTION


Starting with <cit.>, a number of papers
have used the device of vanishingly small “trembles” to refine
the set of Nash equilibria. This paper introduces player-compatible
equilibrium (PCE), which extends the tremble-based approach. PCE
requires that the trembles used to support an equilibrium satisfy
player compatibility, which imposes restrictions on how one
player's trembles compare to those of another. We say player i
is more player-compatible with strategy s_i^* than player j
is with strategy s_j^* if whenever s_j^* is optimal
for j against some correlated profile σ, s_i^* is
optimal for i against any profile σ̂ matching σ
in terms of the strategies of players other than i and j. PCE
is invariant to the utility representations of players' preferences
over game outcomes, and provides a link between tremble-based refinements
and learning-in-games. As we will explain, PCE interprets “trembles”
not as errors, but as players' deliberate experiments to learn how
others play. Its cross-player tremble restrictions derive from an
analysis of the relative frequencies of experiments that different
players choose to undertake over time under a number of commonly used
learning policies.

Section <ref> defines player compatibility and PCE, studies
their basic properties, and proves that PCE exist in all finite games.
The compatibility relation is easiest to satisfy when i and j
are “non-interacting,” meaning that their payoffs do not depend
on each other's play. But PCE can have bite even when all players
interact with each other, provided that the interactions are not too
strong. Moreover, as shown by the examples in Section <ref>,
PCE can rule out seemingly implausible equilibria that other tremble-based
refinements such as trembling-hand perfect equilibrium <cit.>
and proper equilibrium <cit.> cannot eliminate.

One of these examples is a “link-formation game,” where players
are split into two sides, and each player decides whether or not to
pay a cost to be Active and form links with all of the active
players on the other side. Players with lower costs are more compatible
with Active and so experiment with it more. In the “anti-monotonic”
version of the game, players who incur a higher private cost of link
formation give lower benefits to their linked partners; in the “co-monotonic”
version, higher cost players give others higher benefits. In the anti-monotonic
version the only PCE outcome is for all players to choose Active,
because the experimentation of the low-cost players induces all players
on the other side to be Active as well. On the other hand,
both “all Active” and “all Inactive” are
PCE outcomes in the co-monotonic case. In contrast to PCE making different
predictions in the two versions of the game, other equilibrium refinements
make the same predictions whether payoffs are anti-monotonic or co-monotonic.

To provide motivation for player-compatible trembles, we study a learning
framework where agents are born into different player roles and repeatedly
play the stage game. They face some time-invariant distribution of
opponents' play, as they would in a steady state of a model where
a continuum of anonymous agents are randomly matched each period.
We compare the experimentation behavior of agents in different player
roles who follow “index learning policies.” These policies assign
a numerical index to each strategy that only depends on data from
periods when that strategy was used, and play the strategy with the
highest index. We formulate an index compatibility condition
for index policies, and use a coupling argument to show that any index
policies for i and j satisfying this index-compatibility condition
for strategies s_i^* and s_j^* will lead to i experimenting
relatively more with s_i^* than j with s_j^* over
their lifetimes against any distribution of opponents' play.

Index compatibility provides a general condition for i to choose
s_i^* more often than j chooses s_j^*. This condition
applies across a range of observation structures and (not necessarily
optimal) learning policies. We link player compatibility with index
compatibility for two canonical learning policies in a class of “factorable
games.” In these games, playing a strategy s_i reveals how
opponents played at all the information sets that are relevant for
i's payoff when they play s_i, but gives no information about
the payoffs of i's other strategies. We show that player compatibility
implies index compatibility for the rational learning policy given
by the Gittins index, and for the weighted fictitious play heuristic
<cit.>. Interpreting trembles as play frequencies
during a learning process, our analysis provides a learning foundation
for PCE's cross-player tremble restrictions — in the link-formation
game, for example, it justifies the idea that low-cost agents “tremble
onto” Active more frequently than high-cost ones do.



 §.§ Related Work




  §.§.§ Tremble-Based Refinements


Tremble-based solution concepts date back to <cit.>,
who thanks Harsanyi for suggesting them. These solution concepts consider
totally mixed strategy profiles where players do not play an exact
best reply to the strategies of others, but may assign positive probability
to some or all strategies that are not best replies. Different solution
concepts in this class consider different kinds of “trembles,”
but they all make predictions based on the limits of these non-equilibrium
strategy profiles as the probability of trembling tends to zero. Since
we compare PCE to these refinements below, we summarize them here
for the reader's convenience.

An ϵ-perfect equilibrium is a totally mixed strategy
profile where every non-best reply has weight less than ϵ.
A limit of ϵ_t-perfect equilibria where ϵ_t→0
is called a trembling-hand perfect equilibrium. An ϵ-proper
equilibrium is a totally mixed strategy profile σ where for
every player i and strategies s_i and s_i' if u_i(s_i,σ_-i)<u_i(s_i',σ_-i)
then σ_i(s_i)<ϵ·σ_i(s_i^'). A limit
of ϵ_t-proper equilibria where ϵ_t→0 is
called a proper equilibrium; in this limit a more costly tremble
is infinitely less likely than a less costly one, regardless of the
cost difference. Approachable equilibrium <cit.>
is also based on the idea that strategies with worse payoffs are played
less often. It too is the limit of ϵ_t-perfect equilibria,
but where the players pay control costs to reduce their tremble probabilities.
When these costs are “regular,” all of the trembles are of the
same order. Because PCE does not require that the less likely trembles
are infinitely less likely than more likely ones, it is closer to
approachable equilibrium than to proper equilibrium. The strategic
stability concept of <cit.> is also defined
using trembles, but applies to components of Nash equilibria as opposed
to single strategy profiles.

Unlike PCE, proper equilibrium and approachable equilibrium do not
impose cross-player restrictions on the relative probabilities of
various trembles. For this reason, these equilibrium concepts reduce
to perfect Bayesian equilibrium in signaling games with two possible
signals, such as the beer-quiche game of <cit.>,
when each type of the sender is viewed as a different player. They
do impose restrictions when applied to the ex-ante form of the game,
i.e., at the stage before the sender has learned their type. However,
as <cit.> point out, evaluating the cost of mistakes
at the ex-ante stage of a signaling game means that the interim losses
are weighted by the prior distribution over sender types, so that
less likely types are more likely to tremble. In addition, applying
a different positive linear rescaling to each type's utility function
preserves every type's preference over lotteries on outcomes, but
changes the sets of proper and approachable equilibria, while such
utility rescalings have no effect on the set of PCE. In light of these
issues, we always apply tremble-based refinements at the interim stage
in Bayesian games.

Like PCE, extended proper equilibrium <cit.>
places restrictions on the relative probabilities of tremble by different
players, but it does so in a different way: An extended proper equilibrium
is the limit of (β,ϵ_t)-proper equilibria,
where β=(β_1,...β_I) is a strictly
positive vector of utility re-scaling, and σ_i(s_i)<ϵ_t·σ_j(s_j)
if player i's rescaled loss from s_i (compared to the best
response) is less than j's loss from s_j. In a signaling game
with only two possible signals, every Nash equilibrium where each
sender type strictly prefers not to deviate from their equilibrium
signal is an extended proper equilibrium at the interim stage, because
suitable utility rescalings for the types can lead to any ranking
of their utility costs of deviating to the off-path signal. By contrast,
Proposition <ref> shows every PCE must satisfy the
compatibility criterion of <cit.>, which has bite
even in binary signaling games such as the beer-quiche example of
<cit.>. So an extended proper equilibrium need
not be a PCE, a fact that Examples <ref> and <ref>
further demonstrate. Conversely, because extended proper equilibrium
makes some trembles infinitely less likely than others, it can eliminate
some PCE.[Example available on request.]



  §.§.§ The Learning Foundations of Equilibrium


This paper builds on the work of <cit.> and
<cit.> on learning
foundations for self-confirming and Nash equilibrium. It is also related
to recent work that that provides explicit learning foundations for
various equilibrium concepts that reflect ambiguity aversion, misspecified
priors, or model uncertainty, such as <cit.>,
<cit.>, <cit.>,
<cit.> and <cit.>. Unlike
those papers, we focus on characterizing the relative rates with which
different players experiment with strategies that are not myopically
optimal. For this reason our analysis of learning is closer to <cit.>
and <cit.>.

Our investigation of learning dynamics significantly expands on that
of <cit.>, which focused on a particular learning
policy (rational Bayesians) in a restricted set of games (signaling
games). In contrast, our analysis applies more broadly to any index
policies that satisfy an index compatibility condition. We
show that two strategies of i and j ranked by player compatibility
lead to index-compatible learning policies in the class of “factorable
games” defined in Section <ref>,
under both rational learning and weighted fictitious play. We develop
new tools to deal with new issues that arise in these more general
games. For instance, <cit.> compare the Gittins
indices of different sender types in signaling games using the fact
that any stopping time (for the auxiliary optimal-stopping problem
defining the index) of the less-compatible type is also feasible for
the more-compatible type. But our general setting allows player roles
to interact, so it is not always valid to exchange the stopping times
of two different roles. A feasible stopping time for i in the auxiliary
problem only conditions on past observations of -i's play, but
the optimal stopping time for j i may condition on past observations
of i's play in environments where i and j interact.

We deal with this problem by showing how i can nevertheless construct
a feasible stopping time that mimics an infeasible one of j.
Moreover, when a player faces more than one opponent, their optimal
experimentation policy may lead them to observe a correlated distribution
of opponents' play, even though the opponents do no actually play
correlated strategies. We discuss this issue of endogenous correlation
in Section <ref>; it is the reason we
define PCE in terms of correlated play.

In methodology the paper is related to other work on active learning
and experimentation. In single-agent settings, these include <cit.>,
<cit.>, and <cit.>.
In multi-agent settings additional issues arise such as free-riding
and encouraging others to learn, see e.g., <cit.>,
<cit.>, <cit.>, <cit.>,
<cit.>, <cit.>, <cit.>,
and the survey by <cit.>. Unlike most models
of multi-agent bandit problems, our agents only learn from personal
histories, not from the actions or histories of others. Our focus
is the comparison of experimentation policies under different payoff
parameters, which is central to PCE's cross-player tremble restrictions.



§ PLAYER-COMPATIBLE EQUILIBRIUM

In this section, we develop a concept of the relative “compatibility”
between two player-strategy pairs and discuss its properties. We then
introduce PCE, which builds cross-player tremble restrictions based
on this compatibility relation into an equilibrium concept.

Like proper equilibrium, PCE is defined on the strategic form of a
game. Of course many extensive forms can have the same strategic form,
and the learning motivation for PCE and player-compatible trembles
does depend on the underlying extensive form and the feedback structure,
but we postpone these issues until Section <ref>.



 §.§ Player Compatibility


Consider a game in its strategic form with a finite set of players
i∈𝕀, finite strategy sets |𝕊_i|≥2,[If 𝕊_i={s_i^*} is a singleton, we would have s_i^*≿ s_j
and s_j≿ s_i^* for any strategy s_j of any player
j if we follow the convention that the maximum over an empty set
is -∞.] and utility functions u_i:𝕊→ℝ, where 𝕊:=×_i𝕊_i.
For each i, let Δ(𝕊_i) denote the set of mixed
strategies for i. Let Δ^∘(𝕊) represent the
interior of Δ(𝕊), the set of full-support correlated
strategy profiles. We now define an incomplete or partial order on
strategy-player pairs.

For player i j and strategies s_i^*∈𝕊_i,
s_j^*∈𝕊_j, i is more player-compatible
with s_i^* than j is with s_j^*, abbreviated as
s_i^*≿ s_j^*,[This notation is unambiguous provided i and j have disjoint
strategy sets. In the event that i and j share some strategies,
we will clarify this notation by attaching player subscripts.] if for every totally mixed correlated strategy profiles σ∈Δ^∘(𝕊)
with 

    ∑_s∈𝕊u_j(s_j^*,s_-j)·σ(s)=max_s_j^'∈𝕊_j∑_s∈𝕊u_j(s_j^',s_-j)·σ(s),

we get 

    ∑_s∈𝕊u_i(s_i^*,s_-i)·σ̃(s)>max_s_i^”∈𝕊_i\{s_i^*}∑_s∈𝕊u_i(s_i^”,s_-i)·σ̃(s)

 for every totally mixed correlated strategy profile σ̃∈Δ^∘(𝕊)
satisfying marg_-ij(σ)=marg_-ij(σ̃).

In words, if s_j^* is weakly optimal for the less-compatible
j against σ, then s_i^* is strictly optimal for
the more-compatible i against any σ̃ whose marginal
on -ij's play agrees with the marginal of σ. The compatibility
condition does not depend on the particular expected utility functions
used to represent the players' preferences over probability distributions
on 𝕊.

We argue below in Theorem <ref>
that play in the learning model is constrained by the compatibility
relation, and that result is stronger when the compatibility relation
is more complete. Since Δ^∘(𝕊)⊆Δ(𝕊),
the compatibility relation is more complete than an alternative definition
that replaces totally mixed strategy profiles with any correlated
strategy profile, and Theorem <ref>
would continue to hold with this alternative definition. We restrict
to totally mixed strategies here to get a sharper conclusion. The
restriction fits with our assumptions in the learning model that all
agents have full-support prior beliefs about opponents' strategies
(for rational Bayesians) or strictly positive initial counts (for
weighted fictitious play). Conversely, since ×_iΔ^∘(𝕊_i)⊆Δ^∘(𝕊),
our definition of compatibility ranks fewer strategy-player pairs
than an alternative definition that only considers mixed strategy
profiles with independent mixing between different opponents.[Formally, this alternative definition would replace “totally mixed
correlated strategy profiles” with “independently and totally
mixed strategy profiles” in the definition of s_i^*≿ s_j^*.] We need to use the more stringent definition to match the microfoundations
of our compatibility-based cross-player restrictions: the definition
that only considers independent mixing imposes restrictions that the
learning model does not imply.[One form of our microfoundation for player-compatible trembles considers
rational learners who choose strategies based on their Gittins index.
Even for learners who hold independent beliefs about opponents' play
at different information sets, a strategy's Gittins index need not
be its expected payoff against independent randomizations by the opponents,
but we show that the index is always the expected payoff against some
correlated strategy profile.]

The compatibility relation is transitive, as the next proposition
shows.

 Suppose s_i^*≿ s_j^*≿ s_k^*
where s_i^*,s_j^*,s_k^* are strategies of i,j,k.
Then s_i^*≿ s_k^*.

The compatibility relation is also asymmetric, except in some “corner
cases.” Say that a strategy is strictly interior dominant
if it is strictly better than any other strategy versus any totally
mixed strategy profile of the opponents, and similarly say that it
is strictly interior dominated[Recall that a strategy can be strictly dominated even though it is
not strictly dominated by any pure strategy.] if it is strictly dominated versus totally mixed opponent
strategy profiles.

 If s_i^*≿ s_j^*, then at least
one of the following is true: (i) s_j^*≿̸s_i^*;
(ii) s_i^* is strictly interior dominated for i and s_j^*
is strictly interior dominated for j; (iii) s_i^* is strictly
interior dominant for i and s_j^* is strictly interior dominant
for j.[The converse of this statement is not true since the relation ≿
is not in general complete: we could have neither s_i^*≿ s_j^*
nor s_j^*≿ s_i^*.]


The proofs of Propositions <ref> and <ref>
are straightforward; they can be found in the Online Appendix.

The definition of player compatibility simplifies in the following
special case. A game has a multipartite structure if the set
of players 𝕀 can be divided into C mutually exclusive
classes, 𝕀=𝕀_1∪...∪𝕀_C, in
such a way that whenever i and j belong to the same class i,j∈𝕀_c,
(1) they are non-interacting, meaning neither player's payoff
depends on the other's strategy; and (2) they have the same strategy
set, 𝕊_i=𝕊_j. Every Bayesian game has a multipartite
structure when each type is viewed as a different player. As another
example, we will later use a complete-information game with a multipartite
structure, the link-formation game (Example <ref>), to
illustrate both PCE and the learning motivation for player-compatible
trembles.

In a game with multipartite structure with i,j∈𝕀_c,
we can write u_i(s_c,s_-ij) without ambiguity for s_c∈𝕊_i,
since all augmentations of the strategy profile s_-ij with a
strategy by player j lead to the same payoff for i. For s_c^*∈𝕊_i=𝕊_j,
the definition of s_ic^*≿ s_jc^* reduces[We use s_ic^* to refer to i's copy of s_c^* and s_jc^*
to refer to j's copy.] to: For every totally mixed correlated σ with σ_-ij∈Δ^∘(𝕊_-ij),

    ∑_s∈𝕊u_j(s_jc^*,s_-ij)·σ(s)=max_s_j^'∈𝕊_j∑_s∈𝕊u_j(s_j^',s_-ij)·σ(s)

 implies 

    ∑_s∈𝕊u_i(s_ic^*,s_-ij)·σ(s)>max_s_i^”∈𝕊_i\{s_ic^*}∑_s∈𝕊u_i(s_i^”,s_-ij)·σ(s).





 §.§ Player-Compatible Trembles and PCE


PCE is a tremble-based solution concept. It builds on and modifies
<cit.>'s definition of trembling-hand perfect
equilibrium (in the strategic form) as the limit of equilibria of
perturbed games in which agents are constrained to tremble, so we
begin by defining our notation for the trembles and the associated
constrained equilibria.

A tremble profile ϵ assigns a positive
number ϵ(s_i)>0 to every player i and
every pure strategy s_i∈𝕊_i. Given a tremble profile
ϵ, write Π_i^ϵ
for the set of ϵ-strategies of player
i, namely: 

    Π_i^ϵ{σ_i∈Δ(𝕊_i) s.t. σ_i(s_i)≥ϵ(s_i) ∀ s_i∈𝕊_i} .

We call σ^∘ an ϵ-equilibrium
if for each i, 

    σ_i^∘∈σ_i∈Π_i^ϵmax u_i(σ_i,σ_-i^∘).


Note that Π_i^ϵ is compact and convex.
It is also non-empty when ϵ is close enough
to 0. By standard results, whenever ϵ
is small enough so that Π_i^ϵ is non-empty
for each i, an ϵ-equilibrium exists.

The key building block for PCE is ϵ-PCE,
which is an ϵ-equilibrium where the tremble
profile is “co-monotonic” with ≿ in the following sense:

Tremble profile ϵ is player-compatible
if ϵ(s_i^*)≥ϵ(s_j^*)
for all i,j,s_i^*,s_j^* such that s_i^*≿ s_j^*.
An ϵ-equilibrium where ϵ
is player-compatible is called a player-compatible ϵ-equilibrium
(or ϵ-PCE).

The condition on ϵ says the minimum weight
i could assign to s_i^* is no smaller than the minimum weight
j could assign to s_j^* in the constrained game,

    min_σ_i∈Π_i^ϵσ_i(s_i^*)≥min_σ_j∈Π_j^ϵσ_j(s_j^*).

This is a “cross-player tremble restriction,” that is, a restriction
on the relative probabilities of trembles by different players. Note
that this restriction, like the player compatibility relation, depends
on the players' preferences over distributions on 𝕊 but
not on the particular utility representation. This invariance property
distinguishes player-compatible trembles from other models of stochastic
behavior such as the stochastic terms in logit best responses. Our
learning foundation will interpret these trembles not as mistakes,
but as deliberate experiments by agents trying to learn how others
play.

As is usual for tremble-based equilibrium refinements, we now define
PCE as the limit of a sequence of ϵ-PCE where
ϵ→0.

A strategy profile σ^* is a player-compatible equilibrium
(PCE) if there exists a sequence of player-compatible tremble profiles
ϵ^(t)→0 and an associated
sequence of strategy profiles σ^(t), where each σ^(t)
is an ϵ^(t)-PCE, such that σ^(t)→σ^*.

We think of PCE as primarily a solution concept for games with three
or more players, where the relative tremble probabilities of i j
affect some third party's best response. In two-player games, s_i^*≿ s_j^*
only when s_j^* is strictly interior dominated or s_i^*
is strictly interior dominant.

The cross-player restrictions embodied in player-compatible trembles
translate into analogous restrictions on PCE, as shown in the next
result.

 For any PCE σ^*, player k,
and strategy s̅_k such that σ_k^*(s̅_k)>0,
there exists a sequence of totally mixed strategy profiles σ_-k^(t)→σ_-k^*
such that

(i) for every pair i,j k with s_i^*≿ s_j^*,


    lim inf_t→∞σ_i^(t)(s_i^*)/σ_j^(t)(s_j^*)≥1;

 and (ii) s̅_k is a best response for k against every
σ_-k^(t) .

The proof is in the Appendix, as are the proofs of subsequent results
except where otherwise stated.

Treating each σ_-k^(t) as a totally mixed approximation
to σ_-k^*, in a PCE each player k essentially best
responds to totally mixed opponent play that respects player compatibility.

It is easy to show that every ϵ-PCE respects
player compatibility up to the “adding up constraint” that probabilities
on different strategies must sum up to 1 and i must place probability
no smaller than ϵ(s_i^') on strategies
s_i^' s_i^*. The “up to” qualification disappears
in the ϵ^(t)→0 limit because
the required probabilities on s_i^' s_i^* tend to 0.

Since PCE is defined as the limit of ϵ-equilibria
for a restricted class of trembles, the set of PCE form a subset of
trembling-hand perfect equilibria; the next result shows this subset
is not empty. It uses the fact that the tremble profiles with the
same lower bound on the probability of each action satisfy the compatibility
condition in any game.

 A PCE exists in every finite strategic-form
game.




 §.§ Learning and Player-Compatible Trembles

Sections <ref> and <ref>
provide a microfoundation for player-compatible trembles, which form
the core innovation of PCE. To preview the results, Sections <ref>
presents a general sufficient condition for i to experiment more
with s_i^* than j does with s_j^* over their lifetimes
that is applicable across a range of learning environments and learning
policies. Sections <ref> completes
the story by showing that in a class of games that includes our Section
<ref> examples, the player-compatibility condition
s_i^*≿ s_j^* implies Sections <ref>'s
sufficient condition for the rational learning policy and for weighted
fictitious play. For analyzing rational behavior, we consider agents
who start with the same priors over the play of their opponents. We
believe we could extend this conclusion to agents with slightly different
priors using a stronger notion of player compatibility, but we do
not pursue this result here.[To do this, we would measure the “strength” of the compatibility
ranking by saying that i is λ more player-compatible
with s_i^* than j is with s_j^* if the inequality
in the definition s_i^*≿ s_j^* holds for all σ̃∈Δ^∘(𝕊)
satisfying ||marg_-ij(σ)-marg_-ij(σ̃)||≤λ.
We believe that our learning foundation would extend to cases where
the agents' priors are sufficiently close compared to .]

PCE incorporates cross-player tremble restrictions derived from learning
into an equilibrium framework. It also imposes some extra restrictions
that we do not microfound, so the map from learning models to PCE
is inexact, but PCE does capture some novel implications of learning.
Like any game-theoretic equilibrium concept, it provides a reduced
form that allows analysts to study comparative statics in various
applications without needing to solve the dynamic learning problem
anew in each of them.

In Section <ref>, we expand the
game to include duplicate copies of some of the original strategies,
where two strategies are duplicates if they provide exactly the same
payoff and exactly the same information.[Two strategies with the same payoffs that give different information
about opponents' play are not equivalent in our learning model.] If s_i^*≿ s_j^* in the original game, then in the
expanded game we impose the cross-player tremble restriction that
the probability of i trembling onto the set of copies of s_i^*
is larger than the probability of j trembling onto the set of copies
of s_j^*. The way we update our PCE definition in the presence
of duplicates fits our interpretation of trembles as experimentation
frequencies: As we show, the sum of i's lifetime experimentation
frequencies with all duplicates of s_i^* is independent of
the number of duplicates under both rational behavior and weighted
fictitious play. We show that the set of PCE in the expanded game
with these new tremble restrictions is the same as the set of PCE
in the original game.




§ EXAMPLES OF PCE


In this section, we study examples of games where PCE rules out unintuitive
Nash equilibria. We will also use these examples to distinguish PCE
from existing refinements.



 §.§ The Restaurant Game


We start with a complete-information game where PCE differs from other
solution concepts.

 There are three players in the game: a food
critic, a regular diner, and a restaurant. Simultaneously, the restaurant
decides between ordering high-quality (H) or low-quality
(L) ingredients, while the critic and the diner decide whether
to go eat at the restaurant (R) or order pizza (Z)
and eat at home. The utility from Z is normalized to 0. If
both customers choose Z, the restaurant also gets 0 payoff.
Otherwise, the restaurant's payoff depends on the ingredient quality
and clientele. Choosing L yields a profit of +2 per customer
while choosing H yields a profit of +1 per customer. In addition,
if the food critic is present she will write a review based on ingredient
quality, which affects the restaurant's payoff by ±2.5. Each
customer gets a payoff of x<-1 from consuming food made with low-quality
ingredients and a payoff of y>0.5 from consuming food made with
high-quality ingredients, while the critic gets an additional +1 payoff
from going to the restaurant and writing a review (regardless of food
quality). Customers each incur a 0.5 congestion cost if they both
go to the restaurant. We depict this situation in the game tree below,
with c and d subscripts denoting strategies of the critic and
the diner. 

    < g r a p h i c s >



The strategies of the two customers affect each other's payoffs, so
the critic and the diner are not non-interacting players. In particular,
they cannot be mapped into two types of the same agent in a Bayesian
game.

The strategy profile (Z_c, Z_d,
L) is a proper equilibrium, sustained by the restaurant's
belief that when at least one customer plays R, it is far
more likely that the diner deviated to patronizing the restaurant
than the critic, even though the critic has a greater incentive to
go to the restaurant since she gets paid for writing reviews. It is
also an extended proper equilibrium.[(Z_c, Z_d, L)
is an extended proper equilibrium, because scaling the critic's payoff
by a large positive constant makes it more costly for the critic to
deviate to R1 than for the diner to deviate to R2.]

We claim that R_c≿R_d. Note
that for any profile σ of totally mixed, correlated play that
makes the diner indifferent between Z_d and R_d,
we must have u_1(R_c,σ̃_-c)≥0.5
for any profile σ̃ that agrees with σ in terms
of the restaurant's play. The critic's utility from R_c
is minimized when the diner chooses R_d
with probability 1, but even then the critic gets 0.5 higher utility
from going to a crowded restaurant than the diner gets from going
to an empty restaurant, holding fixed food quality at the restaurant.
This shows R_c≿R_d.

Whenever σ_c^(t)()/σ_d^(t)()>1/4,
the restaurant strictly prefers H over L. Thus by
Proposition <ref>, there is no PCE where the
restaurant plays L with positive probability. ⧫




 §.§ The Link-Formation Game


In the next example, PCE makes different predictions in two versions
of a game with different payoff parameters, while all other solution
concepts we know of make the same predictions in both versions.

There are 4 players in the game, split into two
sides: North and South. The players are named North-1, North-2, South-1,
and South-2, abbreviated as N1, N2, S1, and S2.

These players engage in a strategic link-formation game. Each player
simultaneously takes an action: either Inactive or Active.
An Inactive player forms no links. An Active player
forms a link with every Active player on the opposite side.
(Two players on the same side cannot form links.) For example, suppose
N1 plays Active, N2 plays Active, S1 plays Inactive,
and S2 plays Active. Then N1 creates a link to S2, N2 creates
a link to S2, S1 creates no links, and S2 creates links to both N1
and N2.



    < g r a p h i c s >



Each player i is characterized by two parameters: cost (c_i)
and quality (q_i). Cost refers to the private cost that a player
pays for each link they create. Quality refers to the benefit that
a player provides to others when they link to her. A player who forms
no links gets a payoff of 0. In the above example, the payoff to North-1
is q_S2-c_N1 and the payoff to South-2 is (q_N1-c_S2)+(q_N2-c_S2).

We consider two specifications of the payoff functions. In the anti-monotonic
version on the left, players with a higher cost have a lower quality.
In the co-monotonic version on the right, players with a higher
cost have a higher quality. There are two pure-strategy Nash outcomes
for each version: all links form or no links form. “All links form”
is the unique PCE outcome in the anti-monotonic case, while both “all
links” and “no links” are PCE outcomes under co-monotonicity.




3|c|Anti-MonotonicPlayer     Cost     QualityNorth-1     14     30North-2     19     10South-1     14     30South-2     19     10 

3|c|Co-MonotonicPlayer     Cost     QualityNorth-1     14     10North-2     19     30South-1     14     10South-2     19     30


PCE makes different predictions in these two versions of the game
because the compatibility structure with respect to own quality is
reversed. In both versions, Active_N1≿Active_N2,
but N1 has high quality in the anti-monotonic version, and low quality
in the co-monotonic version. Thus, in the anti-monotonic version but
not in the co-monotonic version, player-compatible trembles lead to
the high-quality counterparty choosing Active at least as
often as the low-quality counterparty, which means Active
has a positive expected payoff even when one's own cost is high.

In contrast, the set of equilibria that satisfy extended proper equilibrium,
proper equilibrium, trembling-hand perfect equilibrium, p-dominance,
Pareto efficiency, and strategic stability do not depend on whether
payoffs are anti-monotonic or co-monotonic, as shown in the Online
Appendix. ⧫




 §.§ Signaling Games


Recall that a signaling game is a two-player Bayesian game, where
P1 is a sender who knows their own type θ, and P2 only knows
that P1's type is drawn according to the distribution λ∈Δ(Θ)
on a finite type space Θ. After learning their type, the sender
sends a signal s∈ S to the receiver. Then, the receiver responds
with an action a∈ A. Utilities depend on the sender's type θ,
the signal s, and the action a.

<cit.>'s compatibility criterion is defined only
for signaling games. It does not use limits of games with trembles,
but instead restricts the beliefs that the receiver can have about
the sender's type. That sort of restriction does not seem easy to
generalize beyond games with observed actions, while using trembles
allows us to define PCE for general strategic-form games. As we will
see, the more general PCE definition implies the compatibility criterion
in signaling games.

With each sender type viewed as a different player, this game has
|Θ|+1 players, 𝕀=Θ∪{2}, where the strategy
set of each sender type θ is 𝕊_θ=S while
the strategy set of the receiver is 𝕊_2=A^S, the set
of signal-contingent plans. So a mixed strategy of θ is a
possibly mixed signal choice σ_1(·|θ)∈Δ(S),
while a mixed strategy σ_2∈Δ(A^S) of the receiver
is a mixed plan about how to respond to each signal.

<cit.> define type compatibility for signaling
games. A signal s^* is more type-compatible with θ than
with θ^' if for every behavioral strategy σ_2,


    u_1(s^*,σ_2;θ^')≥max_s^' s^*u_1(s^',σ_2;θ^')

 implies 

    u_1(s^*,σ_2;θ)>max_s^' s^*u_1(s^',σ_2;θ).

They also define the compatibility criterion, which imposes
restrictions on off-path beliefs in signaling games. Consider a Nash
equilibrium σ_1^*,σ_2^*. For any signal s^*
and receiver action a with σ_2^*(a| s^*)>0, the
compatibility criterion requires that a best responds to some belief
p∈Δ(Θ) about the sender's type such that, whenever
s^* is more type-compatible with θ than with θ^'
and s^* is not equilibrium dominated[Signal s^* is not equilibrium dominated for θ if max_a∈ Au_1(s^*,a;θ)>u_1(s_1,σ_2^*;θ)
for every s_1 with σ_1^*(s_1|θ)>0.] for θ, p satisfies p(θ^')/p(θ)≤λ(θ^')/λ(θ).

Since every totally mixed strategy of the receiver is payoff-equivalent
to a behavioral strategy, it is easy to see that type compatibility
implies s_θ^*≿ s_θ^'^*.[The converse does not hold. We defined type compatibility to require
testing against all receiver strategies and not just the totally mixed
ones, so it is possible that s_θ^*≿ s_θ^'^*
but s^* is not more type-compatible with θ than with
θ^', so type-compatibility is harder to satisfy than player
compatibility. We now realize that we could have restricted type compatibility
to only consider totally mixed strategies, and all of the results
of <cit.> would still hold.] The next result shows that when specialized to signaling games, all
PCE pass the compatibility criterion.

In a signaling game, every PCE σ^*
is a Nash equilibrium satisfying the compatibility criterion of <cit.>.

This proposition in particular implies that in the beer-quiche game
of <cit.>, the quiche-pooling equilibrium is
not a PCE, as it does not satisfy the compatibility criterion.



§ INDEX LEARNING POLICIES AND
INDEX COMPATIBILITY


This section characterizes a general class of “index learning policies”
that lead i to experiment more with s_i^* than j does
with s_j^*. The next section shows that optimal learning behavior
and weighted fictitious play belong to this class in “factorable”
games, when s_i^*≿ s_j^*. Together, these sections
link the player-compatibility relation with agents' learning behavior
under various learning policies, providing a learning foundation for
the tremble restrictions central to PCE.

The learning problem the players face depends on what they observe
about the play of others, which in turn depends on the extensive form
of the game, denoted by Γ. This game has a set of players
i∈𝕀 and also a player 0 that we will use to model Nature's
moves. The collection of information sets of player i∈𝕀
is written as ℋ_i. At each h∈ℋ_i,
player i chooses an action a_h from the finite set of possible
actions A_h. An extensive-form pure strategy of i specifies
an action at each information set h∈ℋ_i. We denote
by 𝕊_i the set of all such strategies. Let Z be the
set of terminal vertices of Γ. Also, let Z(s) denote the
terminal vertex reached under the pure strategy profile s∈×_i𝕊_i.

We consider an agent born into player role i who maintains this
role throughout their life. They have has a geometrically distributed
lifetime with 0≤γ<1 probability of survival between periods.
All agents share the same survival chance. Each period, the agent
plays the stage game Γ, choosing a strategy s_i∈𝕊_i.
Then, with probability γ, they continue into the next period
and play the stage game again. With complementary probability they
exit the system.

Each player is equipped with a finite set of observations 𝕆_i
and a feedback function 𝔬_i:Z→𝕆_i
that maps the terminal node reached to an observation. We assume each
player has perfect recall and remembers their chosen strategy.

The set of all finite histories of all lengths for i is
Y_i:=∪_t≥0(𝕊_i×𝕆_i)^t. For
a history y_i∈ Y_i and s_i∈𝕊_i, the subhistory
y_i,s_i is the (possibly empty) subsequence of y_i where
the agent played s_i.

To compare players i and j's relative experimentation probabilities,
we need the agents in these two player roles to face “equivalent”
learning environments. The next definition formalizes what this means;
it is a joint restriction on the game tree Γ and the feedback
structures (𝕆_i,𝔬_i), (𝕆_j,𝔬_j)
of the two player roles.

Agents i and j face isomorphic learning problems if:


  * There exists an isomorphism φ:𝕊_i→𝕊_j

  * For each s_i∈𝕊_i, the union ({s_i}×𝕆_i)∪({s_j}×𝕆_j)
of possible observations of i after s_i and possible observations
of j after s_j can be partitioned into a set of equivalence
classes 𝔼_s_i,s_j, where elements E∈𝔼_s_i,s_j
are disjoint subsets.

  * For each pure strategy profile s̃ and s_i∈𝕊_i
with s_j=φ(s_i), (s_i,𝔬_i(Z(s_i,s̃_-i)))
and (s_j,𝔬_j(Z(s_j,s̃_-j))) belong to
the same equivalence class in 𝔼_s_i,s_j.


Whenever we say i and j face isomorphic learning problems, it
is always with respect to some isomorphism φ and some collection
of equivalence classes 𝔼=(𝔼_s_i,φ(s_i))_s_i∈ S_i.
To make this explicit, sometimes we will say i and j face (φ,𝔼)-isomorphic
learning problems.

If i and j face isomorphic learning problems, there is a bijection
φ between the strategies of the two agents and a notion of
equivalence between the one-period histories they might observe after
choosing s_i and s_j, with s_j=φ(s_i). This
equivalence puts i's observation after (s_i,s̃_-i)
in the same equivalence class as j's observation after (s_j,s̃_-j),
for any profile s̃.

Consider Example <ref> when the Critic and the Diner
observe all other players' actions if they choose R, but
observe nothing if they choose Z. That is, 

    𝕆_C=𝕆_D={(L,R),(L,Z),(H,R),(H,Z),∅}.

 Consider the natural isomorphism φ(R_c)=R_d and φ(Z_c)=Z_d,
and partition histories after R_c and R_d as 

    𝔼_R_c,R_d=    {{ (R_c,(L,R)),(R_d,(L,R)),(R_c,(L,Z)),(R_d,(L,Z))} ,.
       .{ (R_c,(H,R)),(R_d,(H,R)),(R_c,(H,Z)),(R_d,(H,Z))}} .

The two equivalence classes in 𝔼_R_c,R_d represent
whether the restaurant is observed to play L or H.
Also let 𝔼_Z_c,Z_d={{(Z_c,∅),(Z_d,∅)}}
contain just one equivalence class, which corresponds to no observations.
It is clear that given any pure strategy profile s, (R_c,s_-c)
and (R_d,s_-d) lead to the same histories, up to equivalence
classes (i.e., the same observation of the restaurant's play.)

We extend the notion of equivalence to histories with more than one
period in the natural way.

Suppose i and j face (φ,𝔼)-isomorphic learning
problems with φ(s_i)=s_j. Say i's subhistory y_i,s_i
is equivalent to j's subhistory y_j,s_j, written
as y_i,s_i∼ y_j,s_j, if they are equivalent period by
period according to the equivalence classes 𝔼_s_i,φ(s_i).

Equivalence of y_i,s_i and y_j,s_j says i has played
s_i as many times as j has played s_j, and that the sequence
of observations that i encountered from experimenting with s_i
are the “same” as those that j encountered from experimenting
with s_j.

The following histories for the critic and the diner of the restaurant
game are equivalent for the strategy R (under the φ,𝔼
previously given). This equivalence arises because the subhistories
y_c,R and y_d,R contain the same sequences of the restaurant's
play (even though the two agents have different observations in terms
of how often the other patron goes to the restaurant).



The agent decides which strategy to use in each period based on their
history so far. We assume that this learning policy is a deterministic
map (which is w.l.o.g. for expected-utility maximizers), and denote
it r_i:Y_i→𝕊_i.

A learning policy is an index policy if there are index
functions (ι_s_i)_s_i∈𝕊_i with each ι_s_i
mapping subhistories of s_i to real numbers, such that r_i(y_i)∈s_i∈𝕊_imax{ι_s_i(y_i,s_i)}.

If an agent uses an index policy, we can think of their behavior in
the following way. At each history, they compute an index for each
strategy s_i∈𝕊_i based on the subhistory of those
periods where they chose s_i, and play a strategy with the highest
index.[To handle possible ties, we can introduce a strict order over each
agent's strategy set, and specify that if two strategies have the
same index the agent plays the one that is higher ranked.] The best-known example of an index policy is the Gittins index <cit.>.
Some heuristics for learning problems, such as weighted fictitious
play <cit.>, are also index policies. The key
restriction in an index policy is that each strategy's index depends
only on the observations when that strategy was played. Note that
index policies are deterministic, unlike some heuristics such as Thompson
sampling <cit.>.

Finally, we define a notion of the relative compatibility of index
policies r_i and r_j with various strategies.

Suppose i and j face (φ,𝔼)-isomorphic learning
problems with φ(s_i^*)=s_j^*. For two index policies
r_i and r_j, r_i is more index-compatible with
s_i^* than r_j is with s_j^* if for any histories
y_i,y_j and any strategy s_i^'∈𝕊_i, s_i^' s_i^*
satisfying


  * y_i,s_i^*∼ y_j,s_j^* and y_i,s_i^'∼ y_j,φ(s_i^')

  * s_j^* has weakly the highest index for j,

we have that s_i^' does not have the weakly highest index for
i.

The key result of this section, Proposition <ref>, shows
that index compatibility is a sufficient condition for average agents
in the role of player i to play s_i^* more frequently than
those in the j-role play s_j^*. This result is not obvious
because the index-compatibility relation only applies when two agents
have equivalent histories, which typically does not hold during the
dynamic process of experimentation. To formalize the result, suppose
that each agent is randomly matched with opponents in other player
roles, and that the play of these opponents corresponds to a fixed
mixed strategy profile σ, as it would in a steady state. We
call σ the social distribution. It, together with the
agent's learning policy, generates a stochastic process X_i^t
describing i's strategy in period t; denote its distribution
by ℙ_r_i,σ.

Let X_i^t be the 𝕊_i-valued random variable representing
i's play in period t. Player i's discounted lifetime
play under the social distribution σ and learning policy
r_i is ϕ_i(·;r_i,σ):𝕊_i→[0,1],
where for each s_i∈𝕊_i 

    ϕ_i(s_i;r_i,σ):=(1-γ)∑_t=1^∞γ^t-1·ℙ_r_i,σ{X_i^t=s_i}.


Each newborn player i expects to play each of s_i a share
ϕ_i(s_i;r_i,σ) of their lifetime.

 Suppose i and j face (φ,𝔼)-isomorphic
learning problems with φ(s_i^*)=s_j^*, and r_i,r_j
are index policies, with r_i more index-compatible with s_i^*
than r_j is with s_j^*. Then ϕ_i(s_i^*;r_i,σ_-i)≥ϕ_j(s_j^*;r_j,σ_-j)
for any 0≤γ<1 and σ∈×_kΔ(𝕊_k).

Note that Proposition <ref> holds whenever there exists
any (φ,𝔼) such that i,j face (φ,𝔼)-isomorphic
learning problems and r_i,r_j satisfy index-compatibility with
respect to (φ,𝔼).

The proof extends the coupling argument in the proof of <cit.>'s
Lemma 2, which only applies to the Gittins index in signaling games,
and also fills in a missing step (Lemma <ref>)
that the earlier proof implicitly assumed. To deal with the issue
that i and j learn from endogenous data that diverge as they
undertake different experiments, we couple the learning problems of
i and j using what we call response paths 𝔖∈((𝕊)^N)^∞
where N=max_i|𝕊_i|. We can think of 𝔖
as a two-dimensional array of strategy profiles, 𝔖=((𝔖_1,1,𝔖_1,2,...,𝔖_1,N),(𝔖_2,1,𝔖_2,2,...,𝔖_2,N),...),
where 𝔖_t,n_i∈𝕊 for every t≥1, 1≤ n_i≤ N.
We may enumerate each player's strategy set 𝕊_i and
interchangeably refer to each strategy s_i∈𝕊_i with
its assigned number n_s_i∈{1,...,N}. For a given path and
learning policy r_i for player i, imagine running the policy
against the data-generating process where the t-th time i plays
the n_i-th strategy in 𝕊_i, i is matched up
with opponents who play the strategies 𝔖_t,n_i.
Given a learning policy r_i, each 𝔖 induces a deterministic
infinite history of i's strategies y_i(𝔖,r_i)∈(𝕊_i)^∞.
(For n_i>|𝕊_i|, the values of (𝔖_t,n_i)_t≥1
do not matter for the induced history.) We show that under the hypothesis
that r_i is more index-compatible with s_i^* than r_j
is with s_j^*, the weighted lifetime frequency of s_i^*
in y_i(𝔖,r_i) is larger than the frequency of s_j^*
in y_j(𝔖,r_j) for every 𝔖, where play
in different periods of the infinite histories y_i(𝔖,r_i),y_j(𝔖,r_j)
are weighted by the probabilities of surviving into these periods,
just as in the definition of discounted lifetime play.

Lemma <ref> in the Appendix shows that when i
and j face i.i.d. draws of opponents' play from a fixed learning
environment σ, the discounted lifetime play are the same as
if they each faced a random response path 𝔖 drawn at
birth according to the (infinite) product measure over ((𝕊)^N)^∞
whose marginals correspond to σ^|𝕊_i|.



§ INDEX COMPATIBILITY AND
PLAYER COMPATIBILITY IN FACTORABLE GAMES


Section <ref> proves that whenever index-strategy
pairs (r_i,s_i^*) and (r_j,s_j^*) satisfy index
compatibility, and i and j face isomorphic learning problems,
index policy r_i uses s_i^* more often than r_j uses
s_j^* against any social distribution σ. Index compatibility
is a joint restriction on the agents' learning policy and the game's
feedback structure (𝕆,𝔬), which gives the domain
that the learning policies are defined on. This section shows that
player compatibility implies index compatibility for rational behavior
and weighted fictitious play in a class of factorable games.
Factorability applies to the examples discussed in Section <ref>
for players ranked by compatibility.



 §.§ Factorability and Isomorphic Factoring


In factorable games, agent i's observation is just their utility:
𝔬_i(s_i,s_-i)=u_i(s_i,s_-i). In general,
i's payoff u_i(s_i,s_-i) needs not reveal the actions
that others' strategies s_-i pick at all -i information sets
in the game tree. The definition of factorability puts restrictions
on the extensive-form game tree Γ to discipline what i
can learn from own payoffs.

Factorability says that playing strategy s_i∈𝕊_i
against any strategy profile of -i identifies all of the opponents'
actions that can be payoff-relevant for s_i, but does not reveal
any information about the payoff consequences of choosing any other
strategy s'_i s_i against the social distribution. From
i's perspective, it is as if the game tree can be “factored”
into disjoint parts based on the elements of 𝕊_i, and
playing each s_i∈𝕊_i lets i learn how s_-i
play at all payoff-relevant -i information sets in the s_i-part
of the game tree, but provides no information about s_-i in any
other part of the tree. We now make this idea formal.

For an information set h of j with j i, write P_h
for the partition on 𝕊_-i where two strategy profiles
s_-i,s'_-i are in the same element of the partition if they
prescribe the same play on h. That is, the partition elements in
P_h are {s_-i∈𝕊_-i:s_-i(h)=a_h} for a_h∈ A_h.
Thus partition P_h contains perfect information about play on
h, but no other information.

For each player i and strategy s_i∈𝕊_i,
let Π_i[s_i] be the coarsest partition of 𝕊_-i
that makes s_-i↦ u_i(s_i,s_-i) measurable. The game
Γ is factorable for i if:



  * For each s_i∈𝕊_i there exists a (possibly empty)
collection of -i's information sets F_i[s_i]⊆ℋ_-i
so that Π_i[s_i]=⋁_h∈ F_i[s_i]P_h. (The meet
across an empty collection is the coarsest possible partition on 𝕊_-i,
i.e. no information).

  * For two strategies s_i s'_i, F_i[s_i]∩ F_i[s'_i]=∅.

When Γ is factorable for i, we refer to F_i[s_i]
as the s_i-relevant information sets, a terminology we
now justify. In general, i's payoff from playing s_i can depend
on the profile of -i's actions at all opponent information sets.
Condition (1) implies that only opponents' actions on F_i[s_i]
matter for i's payoff after choosing s_i, and furthermore
this dependence is one-to-one. That is,


    u_i(s_i,s_-i)=u_i(s_i,s'_-i)⇔(∀ h∈ F_i[s_i]   s_-i(h)=s'_-i(h)).

 The one-to-one mapping from s_-i to i's payoff implies that
i's learning cannot be blocked by another player: By choosing s_i,
i can always use their own payoffs to identify actions on F_i[s_i]
regardless of what happens elsewhere in the game tree.[It is easy but expositionally costly to extend this to the case where
several actions on A_h lead to the same payoff for i.] It also shows that if Γ is factorable for i, then F_i[s_i]
are uniquely defined for all s_i. Suppose there were two collections
(F_i[s_i])_s_i∈𝕊_i and (F̃_i[s_i])_s_i∈𝕊_i
with F_i[s_i]\F̃_i[s_i]∅ for
some s_i∈𝕊_i that both satisfy Condition (1) of
Definition <ref>. Then there are two -i profiles
s_-i,s'_-i that match on F̃_i[s_i] but not on
F_i[s_i]. But then we get both u_i(s_i,s_-i)=u_i(s_i,s'_-i)
and u_i(s_i,s_-i) u_i(s_i,s'_-i), a contradiction.

Condition (2) implies that i cannot extrapolate the payoff consequence
of a different strategy s'_i s_i through playing s_i
(provided i's prior is independent about opponents' play on different
information sets). This is because there is no intersection between
the s_i-relevant information sets and the s'_i-relevant
ones. In particular this means that player i cannot “free ride”
on others' experiments and learn about the consequences of various
risky strategies while playing a safe one that is myopically optimal.

In short, Condition (1) ensures i gets information about play in
the same part of the game tree every time she plays s_i (instead
of learning about play in two different parts of the tree depending
on someone else's strategy), while Condition (2) guarantees that there
is no interaction between learning about different strategies.

If F_i[s_i] is empty, then s_i is a kind of “opt out”
action for i. After choosing s_i, i receives the same utility
from every reachable terminal node and gets no information about the
payoff consequences of any of their other strategies.



  §.§.§ Examples of Factorable Games


We now illustrate factorability using the examples from Section <ref>
and some other general classes of games.



  
The Restaurant Game

Consider the restaurant game from Example <ref>.
Since x<-1 and y>0.5, we have x y and x y+0.5. By
choosing R, the customer's payoff perfectly reveals others'
play. By choosing Z, the customer always gets 0 payoff (these
nodes are colored in the diagram below) and so cannot infer anyone
else's play.



    < g r a p h i c s >



The restaurant game is factorable for the Critic and the Diner. Let
F_i[R_i] consist of the two information sets
of -i and let F_i[Z_i] be the empty set
for each i∈{1,2}. It is easy to verify that the two conditions
of factorability are satisfied.

It is important for factorability that a customer who takes the “outside
option” of ordering pizza gets the same payoff regardless of the
restaurant's play, and does not observe the restaurant's quality choice
even if the other customer patronizes the restaurant. Factorability
rules out this sort of “free information,” so that when we analyze
the non-equilibrium learning problem we know that each agent can only
learn a strategy's payoff consequences by playing it themselves.



  
The Link-Formation Game

Consider the link-formation game from Example <ref>. The
payoff for a player choosing Inactive is always 0, whereas
the payoff for a player choosing Active exactly identifies
the play of the two players on the opposite side. We can let F_i[𝐀𝐜𝐭𝐢𝐯𝐞_i]
consist of the information sets of the other two agents on the other
side of i and let F_i[𝐈𝐧𝐚𝐜𝐭𝐢𝐯𝐞_i] be empty. This
specification of the s_i-relevant information sets shows the
stage game is factorable for every player.



  
Binary Participation Games

More generally, Γ is factorable for i whenever it is a
binary participation game for i.

Γ is a binary participation
game for i if the following are satisfied.


  * i has a unique information set with two actions, without loss labeled
In and Out.

  * All paths of play in Γ pass through i's information set.

  * All paths of play where i plays In pass through the same
information sets.

  * Terminal vertices associated with i playing Out all have
the same payoff for i.

  * Terminal vertices associated with i playing In all have
different payoffs for i.


Action Out is an outside option for i that leads to a
constant payoff regardless of others' play. We are implicitly assuming
in part (5) of the definition that the game has generic payoffs for
i after choosing In, in the sense that changing the action
at any one information set on the path of play will change i's
payoff.

If Γ is a binary participation game for i, let F_i[𝐈𝐧]
be the collection of -i information sets encountered in paths of
play where i chooses In. Let F_i[𝐎𝐮𝐭] be
the empty set. We see that Γ is factorable for i. Clearly
F_i[𝐈𝐧]∩ F_i[𝐎𝐮𝐭]=∅, so Condition
(2) of factorability is satisfied. When i chooses the strategy
In, the tree structure of Γ implies different profiles
of play on F_i[𝐈𝐧] must lead to different terminal nodes,
and the generic payoff condition means Condition (1) of factorability
is satisfied for strategy In. When i plays Out,
i gets the same payoff regardless of the others' play, so Condition
(1) of factorability is satisfied for strategy Out.

The restaurant game is a binary participation game for the critic
and the diner, where ordering pizza is the outside option. The link-formation
game is a binary participation game for every player, where Inactive
is the outside option.



  
Signaling to Multiple
Audiences

To give a different class of examples of factorable games, consider
a game of signaling to one or more audiences. To be precise, Nature
moves first and chooses a type for the sender, drawn according to
some known distribution over a finite set of types, Θ. The
sender then chooses a signal s∈ S, observed by all receivers
r_1,...,r_n_r. Each receiver then simultaneously chooses
an action. The profile of receiver actions, together with the sender's
type and signal, determine payoffs for all players. Viewing different
types of senders as different players, this game is factorable for
all sender types, provided payoffs are generic. This factorability
arises because for each type i, F_i[s] is the set of n_r
information sets for the receivers after seeing signal s.



  §.§.§ Examples of Non-Factorable Games


The next result gives a necessary condition for factorability, which
we then use to provide examples of non-factorable games. Suppose H
is an information set of player j i. Player i's payoff is
independent of h if u_i(a_h,a_-h)=u_i(a'_h,a_-h)
for all a_h,a'_h,a_-h, where a_h,a'_h are actions
on information set h, and a_-h is a profile of actions on
all other information sets in the game tree. In games where each player
moves at most once along any path of play, if i's payoff is not
independent of the action taken at some information set h, then
i can always put h onto the path of play via a unilateral deviation
at one of their information sets.

 Suppose each player moves at most once along
any path of play in Γ, the game is factorable for i, and
i's payoff is not independent of h^*. For any strategy profile,
either h^* is on the path of play, or i has a deviation at
one of their information sets that puts h^* onto the path of
play.

This result follows from two lemmas.

 For any game that is factorable for i
and any information set h^* for player j i where j has
at least two different actions, if h^*∈ F_i[s_i] for some
extensive-form strategy s_i∈𝕊_i, then h^* is
always on the path of play when i chooses s_i.



 For any game that is factorable for i
and any information set h^* of player j i, suppose i's
payoff is not independent of h^*. Then 1) j has at least two
different actions on h^*; and (2) there exists some extensive-form
strategy s_i∈𝕊_i so that h^*∈ F_i[s_i].

We can combine these two lemmas to prove the proposition. Consider
the centipede game for three players below.



    < g r a p h i c s >




Each player moves at most once on each path, and 1 and 2's payoffs
are not independent of the (unique) information set of player 3. But,
if both 1 and 2 choose “drop”, then no one step deviation by either
1 or 2 can put the information set of 3 onto the path of play. Proposition
<ref> thus implies the centipede game is not factorable
for either 1 or 2. Moreover, <cit.>
showed that in this game even very patient player 2's may not learn
to play a best response to player 3, so that the strategy profile
(drop, drop, pass) can persist even though it is not trembling-hand
perfect. Intuitively, if the player 1's only play pass as experiments,
then when the fraction of new players is very small, the player 2's
may not get to play often enough to make experimentation with pass
worthwhile.



    < g r a p h i c s >




As another example, the Selten's horse game displayed above is not
factorable for 1 or 2 if the payoffs are generic, even though the
conclusion of Proposition <ref> is satisfied. The information
set of 3 must belong to both F_1[Down] and F_1[Across]
because 3's play can affect 1's payoff even if 1 chooses Across, since
2 could choose Down. This violates the factorability requirement that
F_1[Down]∩ F_1[Across]=∅. The same
argument shows the information set of 3 must belong to both F_2[Down]
and F_2[Across], since when 1 chooses Down the play of
3 affects 2's payoff regardless of 2's play. So, again, F_2[Down]∩ F_2[Across]=∅
is violated.

Condition (2) of factorability also rules out games where i has
two strategies that give the same information, but one strategy always
has a worse payoff under all profiles of opponents' play. In this
case, we can think of the worse strategy as an informationally equivalent
but more costly experiment than the better strategy. Reasonable learning
policies (including rational learning) will not use such strategies,
but we do not capture this feature in the general definition of PCE
because our setup there only considers abstract strategy spaces 𝕊_i
and not an extensive-form game tree.[It would be interesting to try to refine the definition of PCE to
capture this, perhaps using the “signal function” approach of
<cit.> and <cit.>.]



  §.§.§ Isomorphic Factoring


In order to compare the learning behavior of agents i and j,
it is not enough that the game is factorable for each of them. We
must also ensure that they face isomorphic learning problems in order
to apply Proposition <ref>. To do this we define the notion
of isomorphic factoring.

When Γ is factorable for both i and j, the factoring
is isomorphic for i and j if there exists a bijection
φ:𝕊_i→𝕊_j such that F_i[s_i]∩ℋ_-ij=F_j[φ(s_i)]∩ℋ_-ij
for every s_i∈𝕊_i.

This says the s_i-relevant information sets (for i) are the
same as the φ(s_i)-relevant information sets (for j),
insofar as the actions of -ij are concerned. For example, the restaurant
game is isomorphically factorable for the critic and the diner (under
the isomorphism φ(R1)=R2, φ(Z1)=Z2)
because F_1[R1]∩ℋ_3=F_2[R2]∩ℋ_3=
the singleton set containing the unique information set of the restaurant.
As another example, all signaling games (with possibly many receivers
as in Section <ref>) are isomorphically
factorable for the different types of the sender. Similarly, the link-formation
game is isomorphically factorable for pairs (N1, N2), and (S1, S2),
but note that it is not isomorphically factorable for (N1, S1).

Factorability and isomorphic factoring let us construct (φ,𝔼)
so that i and j face (φ,𝔼)-isomorphic learning
problems. The equivalence classes 𝔼_s_i,φ(s_i)
for s_i∈𝕊_i are such that (s_i,u_i(s_i,s̃_-i))∼(φ(s_i),u_j(φ(s_i),ŝ_-j)
if and only if s̃_-i|_F_i[s_i]∩ℋ_-ij=ŝ_-j|_F_j[φ(s_i)]∩ℋ_-ij.



 §.§ Rational Learning in Factorable Games


We first consider rational agents who maximize expected discounted
payoffs. This learning rule requires two additional elements: a Bayesian
prior belief over others' play and a discount factor. We assume that
each agent i starts with a regular independent prior:

Agent i has a regular independent prior if their beliefs
g_i on ×_h∈ℋ_-iΔ(A_h) can be written
as the product of full-support marginal densities on Δ(A_h)
across different h∈ℋ_-i, so that g_i((α_h)_h∈ℋ_-i)=∏_h∈ℋ_-ig_i^h(α_h)
with g_i^h(α_h)>0 for all α_h∈Δ^∘(A_h).

Thus, the agent thinks the social distribution assigns an unknown
mixed action at each -i information set, and thinks actions at
different -i information sets are generated independently from
these underlying mixed actions, whether the information sets belong
to the same player or to different players. Furthermore, the agent
holds independent beliefs about the mixed actions at different information
sets.[We assume that agents do not know Nature's mixed actions, which must
be learned just as the play of other players. If agents know Nature's
move, then a regular independent prior would be a density g_i
on ×_h∈ℋ_𝕀\{i}Δ(A_h),
so that g_i((α_h)_ℋ_𝕀\{i})=∏_h∈ℋ_𝕀\{i}g_i^h(α_h)
with g_i^h(α_h)>0 for all α_h∈Δ^∘(A_h).
As <cit.> point out, an agent who believes
two opponents are randomizing independently may nevertheless have
subjective correlation in their uncertainty about the randomizing
probabilities of these opponents. Here we study the natural special
case where the agents' prior beliefs about the opponents are independent,
i.e., a product measure.] The agent updates g_i by applying Bayes rule to their history
y_i. If the stage game is a signaling game, for example, this
independence assumption means that the senders only update their beliefs
about the receiver's response to a given signal based on the responses
received to that signal, and that the senders' beliefs about this
response do not depend on the responses they have observed to other
signals.

In addition to the survival chance 0≤γ<1 between periods,
the agent further discounts future payoffs according to their patience
0≤δ<1, so their overall effective discount factor is 0≤δγ<1.
All agents have the same patience level.

Given a belief about the distribution of play at each opponent information
set, we can calculate the Gittins index of each strategy s_i∈𝕊_i.
Let ν_s_i∈×_h∈ F_i[s_i]Δ(Δ(A_h))
be a belief over opponents' mixed actions at the information sets
in F_i[s_i]. The Gittins index of s_i under belief ν_s_i
is given by the maximum value of the following auxiliary optimization
problem:


    sup_τ≥1𝔼_ν_s_i{∑_t=1^τ(δγ)^t-1· u_i(s_i,(a_h(t))_h∈ F_i[s_i])}𝔼_ν_s_i{∑_t=1^τ(δγ)^t-1},

where the supremum is taken over all positive-valued stopping times
τ≥1. Here (a_h(t))_h∈ F_i[s_i] means the profile
of actions that -i plays on F_i[s_i] the t-th time that
i uses s_i — by assumption about factorable games, only
these actions and not actions elsewhere in the game tree determine
i's payoff from playing s_i, and i can always infer these
actions from their own payoffs. The distribution over the infinite
sequence of profiles (a_h(t))_t=1^∞ is given by i's
belief ν_s_i, that is, there is some fixed mixed action in
×_h∈ F_i[s_i]Δ(A_h) that generates profiles
(a_h(t)) i.i.d. across periods t. The event {τ=T}
for T≥1 corresponds to using s_i for T periods, observing
the first T elements (a_h(t))_t=1^T, then stopping.

A learning policy that chooses a strategy s_i with the highest
Gittins index after each history y_i solves the rational agent's
dynamic optimization problem. We denote any such policy as OPT_i,
suppressing its dependence on δ and g_i.



 §.§ Weighted Fictitious Play in Factorable Games


Next we consider the weighted fictitious play heuristic, a generalization
of <cit.>'s fictitious play.[This heuristic was first estimated on lab data by <cit.>.
It was generalized by <cit.> and
later analyzed by <cit.>.] Agent i keeps track of counts for actions at the opponent
information sets in the game tree, 

    {N_h^a_h∈ℝ_++:h∈ℋ_-i,a_h∈ A_h}.

 The N_h^a_h values of a newcomer agent start at some
initial counts, N_h^a_h(0)>0, and the counts update as i
learns.

After history y_i of i where s_i has been used T≥0
times, i's subhistory for s_i can be viewed as y_i,s_i=(s_i,s_-i^(t)(h)_h∈ F_-i[s_i])_t=1^T
where s_-i^(t)(h)_h∈ F_-i[s_i] is the observed -i's
play on F_i[s_i] the t-th time that s_i was used. (This
is because there is a one-to-one relationship between s_-i's
play on F_i[s_i] and u_i(s_i,s_-i).) The updated count
on (h,a_h) for h∈ F_i[s_i] and a_h∈ A_h is


    N_h^a_h(y_i)=∑_t=1^T1(s_-i^(t)(h)=a_h)·ρ^(T-t)+ρ^TN_h^a_h(0)

 for some ρ∈(0,1]. That is, i calculates a weighted sum
for the total number of times that -i have played a_h in the
history y_i, where past observations on F_i[s_i] are discounted
at a rate ρ between successive uses of the strategy s_i.
All agents share the same weight factor ρ.

Following history y_i, i assigns an index to s_i equal
to its expected payoff when opponents play the mixed action α_h(a_h;y_i)=N_h^a_h(y_i)/∑_a_h^'∈ A_hN_h^a_h^'(y_i)
on information sets h∈ F_i[s_i]. Write WFP_i
for a learning policy that chooses a strategy with the highest weighted
fictitious play index after every history (suppressing its dependence
on ρ and the initial counts {N_h^a_h(0)}).

When ρ=1, the counts are updated according to the unweighted
fictitious play, and the limit of ρ→0 corresponds to myopically
best replying to the observed play when each strategy was most recently
used. The special case of the Gittins index where the prior g_i
marginalized to each Δ(A_h) is a Dirichlet distribution
and δ=0 is equivalent to the special case of unweighted fictitious
play (i.e., ρ=1) with some initial counts that depend on the
Dirichlet priors' parameters. In general OPT_i differs
from WFP_i outside of these corner cases.



 §.§ Player-Compatibility Implies Index-Compatibility of OPT
and WFP under Isomorphic Factoring


The main result of this paper, Theorem <ref>,
shows that if s_i^*≿ s_j^* in a game isomorphically
factorable for i and j with φ(s_i^*)=s_j^*,
then i uses s_i^* more frequently than j uses s_i^*
both under rational experimentation and under weighted fictitious
play. This comparison holds under the hypothesis that i and j
start their learning processes with the same “initial conditions.”
For OPT, this means i's prior g_i marginalized to
the s_i-relevant -ij information sets equals to j's prior
g_j marginalized to the φ(s_i)-relevant -ij information
sets for every s_i∈𝕊_i. For WFP, this
means i and j start with the same initial counts about -ij's
actions.

 Suppose s_i^*≿ s_j^*
and the game is isomorphically factorable for i and j with φ(s_i^*)=s_j^*.
For any common survival chance 0≤γ<1 and any social distribution
σ, we have ϕ_i(s_i^*;r_i,σ_-i)≥ϕ_j(s_j^*;r_j,σ_-j)
under either of the following conditions:



  * r_i=OPT_i, r_j=OPT_j, and priors g_i,g_j
are regular and equivalent[The theorem easily generalizes to the case where i starts with
one of L≥2 possible priors g_i^(1),...,g_i^(L) with
probabilities p_1,...,p_L and j starts with priors g_j^(1),...,g_j^(L)
with the same probabilities, and each g_i^(l),g_j^(l) is
a pair of equivalent regular priors for 1≤ l≤ L.]: that is, they satisfy g_i|_Δ(A_h):h∈ F_i[s_i]∩ℋ_-ij=g_j|_Δ(A_h):h∈ F_j[φ(s_i)]∩ℋ_-ij
for every s_i∈𝕊_i.

  * r_i=WFP_i, r_j=WFP_j, and i and j
have the same initial counts N_h^a_h(0) for every s_i∈𝕊_i,
h∈ F_i[s_i]∩ℋ_-ij, and a_h∈ A_h.


The proof works by showing that if s_i^*≿ s_j^*,
then both rational learning and weighted fictitious play are (φ,𝔼)-index
compatible. This then lets us apply Proposition <ref>'s
general conclusion about index compatible learning policies.



§ REPLICATION INVARIANCE
OF PCE


Fix a base game where each i has a finite strategy set 𝕊_i
and utility function u_i:𝕊→ℝ.

An extended game with duplicates is a game with the same players
as the base game, where 𝕊̅_i the set of strategies
of i is a finite subset of 𝕊_i×ℕ such
that for all (s_i,n_i)∈𝕊̅_i and (s_j,n_j)_j i∈𝕊̅_-i,
the payoff in the new game is u̅_i((s_i,n_i),(s_j,n_j)_j i)=u_i(s_i,s_j).
For every s_i∈𝕊_i, there exists some n_i∈ℕ
so that (s_i,n_i)∈𝕊̅_i.

The interpretation is that i has some copies of every strategy
they had in the base game, and could have different numbers of copies
of different strategies, where duplicate copies of the same strategy
have the same payoff consequences. For the learning foundation we
will now assume that the extended game is factorable, which implies
that each duplicate provides the same information. As an example,
suppose that in the Restaurant Game the critic can arrive at the restaurant
by taking the red bus or the blue bus, and the color of the bus is
not observed by other players, does not change anyone's payoffs, and
does not change what the diner observes. We can then replace R_c
with two actions R_c^red,R_c^blue at every node in the
diner's information set, letting R_c^red and R_c^blue
both have the same payoff consequences as R_c in the original
game. This modified game is an extended game with duplicates for the
original game.

Subsection <ref> defines player-compatible
trembles and PCE in extended games with duplicates. Using the compatibility
relation ≿ from the base game, a tremble profile in the
extended game with duplicates is player compatible if the sum
of tremble probabilities assigned to all copies of s_i^* exceeds
the sum assigned to all copies of s_j^*, whenever s_i^*≿ s_j^*.
PCE is then defined using this restriction on trembles. We show that
the set of PCE in the base game coincides with the set of PCE in the
extended game with duplicates.

This definition of player-compatible trembles in extended games with
duplicates fits with our interpretation of trembles as experimentation
frequencies and an analysis of how learning dynamics in the extended
game compare with those in the base game. The idea is that if all
copies of a strategy s_i give i the same information about
others' play, then i should be exactly indifferent between all
such copies after all histories in the learning process. Holding fixed
initial beliefs and the social distribution, i's weighted lifetime
average play of s_i in the base game should then equal the sum
of their weighted lifetime average plays of all copies of s_i
in the extended game with duplicates. Thus, any comparisons that hold
between the “tremble” probabilities of i onto s_i^*
and j onto s_j^* in the base game must also hold between
the “tremble” probabilities of i onto the copies of s_i^*
and j onto the copies of s_j^* in the extended game. We
formalize this intuition in binary participation games in Subsection
<ref> for rational learning and weighted
fictitious play.



 §.§ PCE in Extended Games with Duplicates


A tremble profile of the extended game ϵ̅
assigns a positive number ϵ̅(s_i,n_i)>0
to every player i and every pure strategy (s_i,n_i)∈𝕊̅_i.
We define ϵ̅-strategies of i
and ϵ̅-equilibrium of the extended
game in the usual way, relative to the strategy sets 𝕊̅_i.

Tremble profile ϵ̅ is player-compatible
in the extended game if ∑_n_iϵ̅(s_i^*,n_i)≥∑_n_jϵ̅(s_j^*,n_j)
for all i,j,s_i^*,s_j^* such that s_i^*≿ s_j^*.
An ϵ̅-equilibrium where ϵ̅
is player-compatible is called a player-compatible ϵ̅-equilibrium
(or ϵ̅-PCE).

We now relate ϵ̅-equilibria in the extended
game to ϵ-equilibria in the base game. Recall
the following constrained optimality condition that applies to both
the extended game and the base game:

A feasible mixed strategy of i is not a constrained best
response to a -i profile if and only if it assigns more than the
required weight to a non-optimal response.

We associate with a strategy profile σ̅∈×_i∈𝕀Δ(𝕊̅_i)
in the extended game a consolidated strategy profile 𝒞(σ̅)∈×_i∈𝕀Δ(𝕊_i)
in the base game, given by adding up the probabilities assigned to
all copies of each base-game strategy. More precisely, 𝒞(σ̅)_i(s_i):=∑_n_iσ̅_i(s_i,n_i).
Similarly, 𝒞(ϵ̅)
is the consolidated tremble profile, given by 𝒞(ϵ̅)(s_i):=∑_n_iϵ̅(s_i,n_i).

Conversely, given a strategy profile σ∈×_i∈𝕀Δ(𝕊_i)
in the base game, the extended strategy profile ℰ(σ)∈×_i∈𝕀Δ(𝕊̅_i)
is defined by ℰ(σ)_i(s_i,n_i):=σ_i(s_i)/N(s_i)
for each i,(s_i,n_i)∈𝕊̅_i, where N(s_i)
is the number of copies of s_i that 𝕊̅_i contains.
Similarly, ℰ(ϵ) is the
extended tremble profile, given by ℰ(ϵ)(s_i,n_i):=ϵ(s_i)/N(s_i).

 If σ̅ is an ϵ̅-equilibrium
in the extended game, then 𝒞(σ̅)
is an 𝒞(ϵ̅)-equilibrium
in the base game. If σ is an ϵ-equilibrium
in the base game, then ℰ(σ) is an ℰ(ϵ)-equilibrium
in the extended game.

The proof of results in this section can be found in the Online Appendix.

PCE is defined as usual in the extended game.

A strategy profile σ̅^* is a player-compatible
equilibrium (PCE) in the extended game if there exists a sequence
of player-compatible tremble profiles ϵ̅^(t)→0
and an associated sequence of strategy profiles σ̅^(t),
where each σ̅^(t) is an ϵ̅^(t)-PCE,
such that σ̅^(t)→σ̅^*.

These PCE correspond exactly to PCE of the base game.

If σ̅^* is a PCE in the
extended game, then 𝒞(σ̅^*) is
a PCE in the base game. If σ^* is a PCE in the base game,
then ℰ(σ^*) is a PCE in the extended
game.

In fact, starting from a PCE σ^* of the base game, we can
construct more PCE of the extended game than ℰ(σ^*)
by shifting around the probabilities assigned to different copies
of the same base-game strategy, but all these profiles essentially
correspond to the same outcome.



 §.§ Learning and Trembles in Binary
Participation Games with Duplicates


We give the simplest illustration of how learning dynamics in extended
games with duplicates relate to those in the base game, using binary
participation games. These results can also be developed for other
factorable games, but at the cost of more complicated notation.

Consider a binary participation game for i (Definition <ref>)
as the base game and create an extended game with duplicates by adding
an extra copy of the In strategy for i to the game tree,
called In-d. We show that when r_i is an optimal learning
policy for i or the weighted fictitious play heuristic, the discounted
lifetime play ϕ_i(In;r_i,σ_-i) for
the base game is equal to the sum ϕ_i(In;r_i,σ_-i)+ϕ_i(In-d;r_i,σ_-i)
in the new game, for the same social distribution σ.

We modify the original game tree Γ and information sets ℋ
to arrive at a new game tree Γ̅ with information sets
ℋ̅. The basic idea is that In-d gives the
same payoffs and information to i, and -i cannot tell which
one i chose.

By the definition of a binary participation game for i, let h_i
be i's unique information set in ℋ. Enumerate the
vertices in h_i as h_i={v_1,...,v_n}. Playing In
at vertex v_k in the original tree leads to some subtree Γ^(k)⊆Γ.
Start with Γ̅=Γ and add a new move, In-d,
to every v_k∈ h_i. Append a new subtree Γ̂^(k)
to Γ̅ for every v_k∈ h_i, such that Γ̂^(k)
is a copy of Γ^(k) (including payoffs at terminal vertices)
and playing In-d at v_k leads to Γ̂^(k).
Now we give a procedure to construct the information sets ℋ̅
to capture the idea that In and In-d are indistinguishable
to others. Start with ℋ̅=ℋ and let V^(k)
be the set of vertices in Γ^(k). For every 1≤ k≤ n
and v∈ V^(k), find the information set h∈ℋ̅
with v∈ h, then put h:=h∪{ṽ}, where ṽ
is the copy of v in Γ̂^(k). That is, each vertex
reachable after i chooses In-d is indistinguishable to
others from its “twin” reachable when i chooses In.

As discussed before, the Restaurant Game is a binary participation
game for the critic and the diner, with going to the restaurant as
In and ordering pizza as Out. We illustrate adding
a duplicate copy of R_c for the critic to the game, labeled R_c-d.
The critic's unique information set contains two vertices, and the
new game tree adds two new subtrees to the original game, highlighted
in red.



    < g r a p h i c s >




The set of histories in the learning framework for i with the extended
stage game is Ỹ_i=∪_t≥0({In,In-d,Out}×ℝ)^t.
We now define a notion of equivalence between a stochastic
learning policy in the extended game r̃_i:Ỹ_i→Δ({In,In-d,Out}}
and a (deterministic) learning policy in the original game, r_i:Y_i→{In,Out}.
Basically, r̃_i behaves just like r_i except it can
randomize between In and In-d.

Let ζ:Ỹ_i→ Y_i be such that for ỹ_i∈Ỹ_i,
ζ(ỹ_i)∈ Y_i replaces every instance of instance
of In-d with In. Learning policies r̃_i:Ỹ_i→Δ({In,In-d,Out}}
and r_i:Y_i→{In,Out} are
equivalent up to duplicates if for every ỹ_i∈Ỹ_i,
if r_i(ζ(ỹ_i))=Out, then also r̃_i(ỹ_i)(Out)=1.
If r_i(ζ(ỹ_i))=In, then r̃_i(ỹ_i)(In)+r̃_i(ỹ_i)(In-d)=1.

The main result of this section shows that rational learning and weighted
fictitious play lead to learning policies that are equivalent up to
duplicates in the base game and the extended game. Furthermore, any
pair of such equivalent policies in the two settings lead to the same
lifetime discounted frequencies of playing In for the original
game as playing In and In-d for the extended game
against the same social distributions of -i.

Technically, extensive-form strategies in (Γ,ℋ)
and (Γ̅,ℋ̅) are defined over two different
domains. To make sense of i facing the “same” social distribution
of -i's play in the two settings, let ψ:ℋ̅→ℋ
be the natural isomorphism between the two collections of information
sets. Each information set h̃ in the modified game is either
equal to an information set h∈ℋ, or it is an old information
set with some extra vertices added, that is there is some (unique)
h with h̃⊋ h. Let ψ(h̃):=h. Two
strategy profiles σ,σ̃ for (Γ,ℋ)
and (Γ̅,ℋ̅) are -i equivalent
if σ̃(h̃)=σ(ψ(h̃)) for all h̃∈ℋ̃_-i.

 Suppose stochastic learning
policy r̃_i in the extended game is equivalent up to duplicates
with the learning policy r_i in the base game.


  * For a fixed patience parameter 0≤δ<1 and regular prior g_i
over others' play,[The prior is over ×_h∈ℋ_-iΔ(A_h) in
the original stage game and over ×_h̃∈ℋ̃_-iΔ(A_h̃)
in the extended game, but we identify Δ(A_h̃) with
Δ(A_ψ(h̃)) for each h̃∈H̃_-i.
The same identification applies for the initial counts in the original
and extended games.] r_i is OPT_i if and only if r̃_i is
an optimal learning policy with the extended game.

  * For a fixed decay parameter 0≤ρ<1 and initial counts N_h^a_h(0),
r_i is WFP_i if and only if after every ỹ_i∈Ỹ_i,
r̃_i(ỹ_i) is supported on strategies that maximize
payoffs under the weighted fictitious play conjecture of -i's play.

  * For -i equivalent social distributions σ,σ̃
for the base game and extended games, ϕ_i(In;r_i,σ_-i)=ϕ_i(In;r̃_i,σ̃_-i)+ϕ_i(In-d;r̃_i,σ̃_-i).





§ CONCLUDING DISCUSSION


PCE makes two key contributions. First, it generates new and sensible
restrictions on equilibrium play by imposing cross-player restrictions
on the relative probabilities that different players assign to certain
strategies — namely, those strategy pairs s_i,s_j ranked
by the player-compatibility relation s_i≿ s_j. As we
have shown through examples, these cross-player restrictions distinguish
PCE from other refinement concepts and allows us to make comparative
statics predictions in some games where other equilibrium refinements
do not.

Second, PCE shows how restricted “trembles” can capture some of
the implications of non-equilibrium learning. PCE's cross-player restrictions
arise endogenously for a general class of index learning policies,
which includes both the standard model of Bayesian agents maximizing
their expected discounted lifetime utility, and computationally tractable
heuristics like weighted fictitious play. We conjecture that the result
that i is more likely to experiment with s_i than j is
with s_j when s_i≿ s_j applies in other natural
models of learning or dynamic adjustment, such as those considered
by <cit.>, and that
it may be possible to provide foundations for PCE in other and perhaps
larger classes of games.

The strength of the PCE refinement depends on the completeness of
the compatibility order ≿, since ϵ-PCE
imposes restrictions on i and j's play only when the relation
s_i≿ s_j holds. Our player compatibility definition
supposes that player i thinks all mixed strategies of other players
are possible, as it considers the set of all totally mixed correlated
strategies σ_-i∈Δ^∘(𝕊_-i). If the
players have some prior knowledge about their opponents' utility functions,
player i might deduce a priori that the other players will
only play strategies in some subset of Δ^∘(𝕊_-i).
As we show in <cit.>, in signaling games imposing
this kind of prior knowledge leads to a more complete version of the
compatibility order. It may similarly lead to a more refined version
of PCE.

PCE is defined for general strategic forms. We have only provided
learning foundations for player-compatible trembles in factorable
games. Moreover, even in factorable games, PCE imposes some extra
restrictions that we do not microfound, but we view this as a first
step in connecting together tremble-based refinement concepts with
learning-in-games. As we have shown through the link-formation game
and other examples, PCE is a convenient reduced form that generates
novel comparative statics predictions in various applications without
needing the analyst to solve the dynamic learning problem anew in
each of them.

ecta




Appendix





§ PROOFS OF RESULTS STATED IN
THE MAIN TEXT




 §.§ Proof of Proposition <ref>


We first state an auxiliary lemma.

If σ^∘ is an
ϵ-PCE and s_i^*≿ s_j^*, then

    σ_i^∘(s_i^*)≥min[σ_j^∘(s_j^*),1-∑_s_i^' s_i^*ϵ(s_i^')].




Suppose ϵ is player-compatible and let ϵ-equilibrium
σ^∘ be given. For s_i^*≿ s_j^*,
suppose σ_j^∘(s_j^*)=ϵ(s_j^*).
Then σ_i^∘(s_i^*)≥ϵ(s_i^*)≥ϵ(s_j^*)=σ_j^∘(s_j^*),
where the second inequality comes from ϵ being
player-compatible. On the other hand, suppose σ_j^∘(s_j^*)>ϵ(s_j^*).
Since σ^∘ is an ϵ-equilibrium,
the fact that j puts more than the minimum required weight on s_j^*
implies s_j^* is at least a weak best response for j against
σ^∘, with σ^∘ totally mixed due to the
trembles.The definition of s_i^*≿ s_j^* then implies
that s_i^* must be a strict best response for i against
σ^∘ as well. In the ϵ-equilibrium,
i must assign as much weight to s_i^* as possible, so that
σ_i^∘(s_i^*)=1-∑_s_i^' s_i^*ϵ(s_i^').
Combining these two cases establishes the desired result.

Proposition <ref>: For
any PCE σ^*, player k, and strategy s̅_k such
that σ_k^*(s̅_k)>0, there exists a sequence of
totally mixed strategy profiles σ_-k^(t)→σ_-k^*
such that

(i) for every pair i,j k with s_i^*≿ s_j^*,

    lim inf_t→∞σ_i^(t)(s_i^*)/σ_j^(t)(s_j^*)≥1;

and (ii) s̅_k is a best response for k against every
σ_-k^(t) .

By Lemma <ref>, for every ϵ^(t)-PCE
we get 

    σ_i^(t)(s_i^*)/σ_j^(t)(s_j^*)   ≥min[σ_j^(t)(s_j^*)/σ_j^(t)(s_j^*),1-∑_s_i^' s_i^*ϵ^(t)(s_i^'|i)/σ_j^(t)(s_j^*)]
        =min[1,1-∑_s_i^' s_i^*ϵ^(t)(s_i^'|i)/σ_j^(t)(s_j^*)]≥1-∑_s_i^' s_i^*ϵ^(t)(s_i^'|i).


This says 

    inf_t≥ Tσ_i^(t)(s_i^*)/σ_j^(t)(s_j^*)≥1-sup_t≥ T∑_s_i^' s_i^*ϵ^(t)(s_i^'|i).

For any sequence of trembles such that ϵ^(t)→0,
lim_T→∞sup_t≥ T∑_s_i^' s_i^*ϵ^(t)(s_i^'|i)=0,
so

    lim inf_t→∞σ_i^(t)(s_i^*)/σ_j^(t)(s_j^*)=lim_T→∞{inf_t≥ Tσ_i^(t)(s_i^*)/σ_j^(t)(s_j^*)}≥1.


This shows that if we fix a PCE σ^* and consider a sequence
of player-compatible trembles ϵ^(t) and ϵ^(t)-PCE
σ^(t)→σ^*, then each σ_-k^(t)
satisfies _t→∞σ_i^(t)(s_i^*)/σ_j^(t)(s_j^*)≥1
whenever i,j k and s_i^*≿ s_j^*. Furthermore,
from σ_k^*(s̅_k)>0 and σ_k^(t)→σ_k^*,
we know there is some T_1∈ℕ so that σ_k^(t)(s̅_k)>σ_k^*(s̅_k)/2
for all t≥ T_1. We may also find T_2∈ℕ so that
ϵ^(t)(s̅_k|k)<σ_k^*(s̅_k)/2
for all t≥ T_2, since ϵ^(t)→0.
So when t≥max(T_1,T_2), σ_k^(t) places strictly
more than the required weight on s̅_k, so s̅_k
is at least a weak best response for k against σ_-k^(t).
Now the subsequence of opponent play (σ_-k^(t))_t≥max(T_1,T_2)
satisfies the requirement of this proposition.




 §.§ Proof of Theorem <ref>


Theorem <ref>: PCE exists in every
finite strategic-form game.

Consider a sequence of tremble profiles with the same lower bound
on the probability of each strategy, that is ϵ^(t)(s_i|i)=ϵ^(t)
for all i and s_i, and with ϵ^(t) decreasing monotonically
to 0 in t. Each of these tremble profiles is player-compatible
(regardless of the compatibility structure ≿) and there
is some finite T large enough that t≥ T implies an ϵ^(t)-equilibrium
exists, and some subsequence of these ϵ^(t)-equilibria
converges since the space of strategy profiles is compact. By definition
these ϵ^(t)-equilibria are also ϵ^(t)-PCE,
which establishes existence of PCE.




 §.§  Proof of Proposition <ref>


Proposition <ref>: In a signaling
game, every PCE σ^* is a Nash equilibrium satisfying the
compatibility criterion of <cit.>.

Since every PCE is a trembling-hand perfect equilibrium and since
this latter solution concept refines Nash, σ^* is a Nash
equilibrium. To show that it satisfies the compatibility criterion,
we need to show that σ_2^* assigns probability 0 to plans
in A^S that, for some s∈ S, do not best respond to an “admissible”
belief at signal s under profile σ^*. For any plan assigned
positive probability under σ_2^*, by Proposition <ref>
we may find a sequence of totally mixed signal profiles σ_1^(t)
of the sender, so that whenever s_θ≿ s_θ^'
we have lim inf_t→∞σ_1^(t)(s|θ)/σ_1^(t)(s|θ^')≥1.
Write q^(t)(·| s) as the Bayesian posterior belief about
the sender's type after signal s under σ_1^(t), which
is well defined because each σ_1^(t) is totally mixed.
Whenever s_θ≿ s_θ^', this sequence of posterior
beliefs satisfies lim inf_t→∞q^(t)(θ| s)/q^(t)(θ^'| s)≥λ(θ)/λ(θ^'),
so if the receiver's plan best responds to every element in the sequence,
it also best responds to an accumulation point (q^∞(·| s))_s∈ S
with q^∞(θ| s)/q^∞(θ^'| s)≥λ(θ)/λ(θ^')
whenever s_θ≿ s_θ^'. Since the player compatibility
definition used in this paper is slightly easier to satisfy than the
type compatibility definition that the set P(s^',σ^*)
is based on, the plan best responds to P(s^',σ^*) after
every signal s^'.




 §.§ Proof of Proposition <ref>


Let N=max_i|𝕊_i|. We first show that i's discounted
lifetime play is the same whether i plays against strategy profiles
drawn i.i.d. in different periods from the social distribution σ_-i,
or against a response path drawn from a certain distribution η
at the start of i's life. The next lemma constructs this η
from σ, which is the same for all agents, and does not depend
on their (possibly stochastic) learning policies.

 In a factorable game, for each σ∈×_kΔ(𝕊_k),
there is a distribution η over response paths, so that for any
player i, any possibly random policy r_i:Y_i→Δ(𝕊_i),
and any strategy s_i∈𝕊_i, we have 

    ϕ_i(s_i;r_i,σ)=(1-γ)𝔼_𝔖∼η[∑_t=1^∞γ^t-1·(y_i^t(𝔖,r_i)=s_i)],

where y_i^t(𝔖,r_i) refers to the t-th period
history in y_i(𝔖,r_i).


In fact, we will prove a stronger statement: we will show there is
such a distribution that induces the same distribution over period-t
histories for every i, every learning policy r_i, and every
t.

Think of each response path 𝔖 as a two-dimensional array,
𝔖=(𝔖_t,n)_t∈ℕ,1≤ n≤ N.
For non-negative integers (m_n)_n=1^N, each finite two-dimensional
array of strategy profiles ((s_t,n)_t=1^m_n)_n=1^N
with each s_t,n∈𝕊 defines a “cylinder set” of
response paths with the form: 

    {𝔖:𝔖_t,n=s_t,n for each .

That is, the cylinder set consists of those response paths whose first
m_n elements for the n-th strategy match a given sequence
of strategy profiles, (s_t,n)_t=1^m_n. (If m_n=0,
then there is no restriction on 𝔖_t,n for any t.)
We specify the distribution η by specifying the probability
it assigns to these cylinder sets:


    η{ ((s_t,n)_t=1^m_n)_n=1^N} =∏_n=1^N∏_t=1^m_nσ(s_t,n),

where we have abused notation to write ((s_t,n)_t=1^m_n)_n=1^N
for the cylinder set satisfying this profile of sequences, and we
have used the convention that the empty product is defined to be 1.

We establish the claim by induction on t for period-t histories.
For t≥0, let Y_i[t]⊆ Y_i be the set of possible
period-t histories of i, that is Y_i[t]:=(𝕊_i×𝕆_i)^t.
In the base case of t=1, we show playing against a response path
drawn according to η and playing against a pure strategy[In the random matching model agents are facing a randomly drawn pure
strategy profile each period (and not a fixed behavior strategy):
they are matched with random opponents, who each play a pure strategy
in the game as a function of their personal history. From Kuhn's theorem,
this is equivalent to facing a fixed profile of behavior strategies.] drawn from σ_-i∈×_k iΔ(𝕊_k)
generate the same period-1 history. Fixing a learning policy r_i:Y_i→𝕊_i
of i, the probability of i having the period-1 history (s_i^(1),o^(1))∈ Y_i[1]
in the random-matching model is 1(r_i(∅)=s_i^(1))·σ(s:𝔬_i(Z(s_i^(1),s_-i))=o^(1)).
That is, i's policy must play s_i^(1) in the first period
of i's life. Then, i must encounter such a pure strategy that
generates the required observation o^(1), and this has probability
σ(s:𝔬_i(Z(s_i^(1),s_-i))=o^(1)). The
probability of this happening against a response path drawn from η
is 

    1(r_i(∅)=s_i^(1))·η(𝔖:𝔬_i(Z(s_i^(1),s_1,s_i^(1),-i))=o^(1))
    
    =    1(r_i(∅)=s_i^(1))·σ(s:𝔬_i(Z(s_i^(1),s_-i))=o^(1)),

where the second line comes from the probability η assigns to
cylinder sets.

We now proceed with the inductive step. By induction, suppose random
matching and the η-distributed response path induce the same
distribution over the set of period-T histories, Y_i[T], where
T≥1. Write this common distribution as ϕ_i,T^RM=ϕ_i,T^η=ϕ_i,T∈Δ(Y_i[T]).
We prove that they also generate the same distribution over length
T+1 histories.

Suppose random matching generates distribution ϕ_i,T+1^RM∈Δ(Y_i[T+1])
and the η-distributed response path generates distribution ϕ_i,T+1^η∈Δ(Y_i[T+1]).
Each length T+1 history y_i[T+1]∈ Y_i[T+1] may be written
as (y_i[T],(s_i^(T+1),o^(T+1))), where y_i[T] is a
length-T history and (s_i^(T+1),o^(T+1)) is a one-period
history corresponding to what happens in period T+1. Therefore,
we may write for each y_i[T+1], 

    ϕ_i,T+1^RM(y_i[T+1])=ϕ_i,T^RM(y_i[T])·ϕ_i,T+1|T^RM((s_i^(T+1),o^(T+1))|y_i[T]),

 and 

    ϕ_i,T+1^η(y_i[T+1])=ϕ_i,T^η(y_i[T])·ϕ_i,T+1|T^η(((s_i^(T+1),o^(T+1))|y_i[T]),

where ϕ_i,T+1|T^RM and ϕ_i,T+1|T^η are the
conditional probabilities of the form “having history (s_i^(T+1),o^(T+1))
in period T+1, conditional on having history y_i[T]∈ Y_i[T]
in the first T periods.” If such conditional probabilities are
always the same for the random-matching model and the η-distributed
response path model, then from the hypothesis ϕ_i,T^RM=ϕ_i,T^η,
we can conclude ϕ_i,T+1^RM=ϕ_i,T+1^η.

By argument exactly analogous to the base case, we have for the random-matching
model

    ϕ_i,T+1|T^RM((s_i^(T+1),o^(T+1))|y_i[T])=1(r_i(y_i(T))=s_i^(T+1))·σ(s:𝔬_i(Z(s_i^(T+1),s_-i))=o^(T+1)),

since the matching is independent across periods. In the η-distributed
response path model, since a single response path is drawn once and
fixed, one must compute the conditional probability that the drawn
𝔖 is such that the observation o^(T+1)will
be seen in period T+1, given the history y_i[T] (which is
informative about which response path i is facing).

For each 1≤ n≤ N, let the non-negative integer m_n represent
the number of times i has used the n-th strategy in 𝕊_i
in the history y_i[T]. Let (o_t,n)_1≤ t≤ m_n represent
the sequence of observations seen after using the n-th strategy,
in chronological order. Consider the following finite union of cylinder
sets, (s_t,n:𝔬_i(Z(n,s_t,n,-i))=o_t,n)_1≤ t≤ m_n,1≤ n≤ N.
This is the set of response sequences consistent with the observations
so far.

If 𝔖 is to produce the observation o^(T+1) from
i's next play of s_i^(T+1), then 𝔖 must belong
to a more restrictive cylinder set that satisfies the additional restriction
(s_m_s_i^(T+1)+1,s_i^(T+1):𝔬_i(Z(s_i^(T+1),s_-i))=o_m_s_i^(T+1)+1,s_i^(T+1)).
The conditional probability of 𝔖 belonging to this more
restrictive cylinder set, given that it falls in (s_t,n:𝔬_i(Z(n,s_t,n,-i))=o_t,n)_1≤ t≤ m_n,1≤ n≤ N,
is given by the ratio of η-probabilities of these unions of
cylinder sets, which from the product structure of η on cylinder
sets, must be σ(s:𝔬_i(Z(s_i^(T+1),s_-i))=o^(T+1)).

Thus, to prove that ϕ_i(s_i^*;r_i,σ_-i)≥ϕ_j(s_j^*;r_j,σ_-j),
it suffices to show that for every 𝔖, the period where
s_i^* is played for the k-th time in induced history y_i(𝔖,r_i)
happens earlier than the period where s_j^* is played for the
k-th time in history y_j(𝔖,r_j).

Now we turn to the proof of Proposition <ref>.

Let 0≤γ<1 and the social distribution σ be fixed.
Enumerate the strategy sets of i and j so that s_i and
φ(s_i) are assigned the same number for every s_i∈𝕊_i.
Consider the product distribution η on the space of response
paths, ((𝕊)^N)^∞, as in the proof of Lemma <ref>.

By Lemma <ref>, denote the period where s_i^*
appears in y_i(𝔖,r_i) for the k-th time as T_i^(k),
the period where s_j^* appears in y_j(𝔖,r_j)
for the k-th time as T_j^(k). The quantities T_i^(k),T_j^(k)
are defined to be ∞ if the corresponding strategies do not
appear at least k times in the infinite histories. Write #(s_i^';k)∈ℕ∪{∞}
be the number of times s_i^'∈𝕊_i is played in
the history y_i(𝔖,r_i) before T_i^(k). Similarly,
#(s_j^';k)∈ℕ∪{∞} denotes the number of
times s_j^'∈𝕊_j is played in the history y_j(𝔖,r_j)
before T_j^(k). Since φ establishes a bijection between
𝕊_i and 𝕊_j, it suffices to show that
for every k=1,2,3,... either T_j^(k)=∞ or for all s_i^' s_i^*,
#(s_i^';k)≤#(s_j^';k) where s_j^'=φ(s_i^').

We show this by induction on k. First we establish the base case
of k=1.

Suppose T_j^(1)∞, and, by way of contradiction, suppose
there is some s_i^' s_i^* such that #(s_i';1)>#(φ(s_i^');1).
Find the subhistory y_i of y_i(𝔖,r_i). that
leads to s_i^' being played for the (#(φ(s_i^');1)+1)-th
time, and find the subhistory y_j of y_j(𝔖,r_j)
that leads to j playing s_j^* for the first time (y_j
is well-defined because T_j^(1)∞). Note that y_i,s_i^*∼ y_j,s_j^*
vacuously, since i has never played s_i^* in y_i and
j has never played s_j^* in y_j.

Also, y_i,s_i^'∼ y_j,s_j^'. To see this, note that
i has played s_i^' for #(φ(s_i^');1) times
and j has played s_j^' for the same number of times. The
definition of response paths implies they faced the same sequence
of opponent strategy profiles, and the definition of isomorphic learning
problems implies they have gotten equivalent observations in all these
periods.

Since r_j(y_j)=s_j^* and r_j is an index policy, s_j^*
must have weakly the highest index at y_j. Since r_i is
more compatible with s_i^* than r_j is with s_j^*,
s_i^' must not have the weakly highest index at y_i. And
yet r_i(y_i)=s_i' contradiction.

Now suppose this statement holds for all k≤ K for some K≥1.
We show it also holds for k=K+1. If T_j^(K+1)=∞ or
T_j^(K)=∞, we are done. Otherwise, by way of contradiction,
suppose there is some s_i^' s_i^* so that #(s_i';K+1)>#(φ(s_i^');K+1).
Find the subhistory y_i of y_i(𝔖,r_i). that
leads to s_i^' being played for the (#(φ(s_i^');K+1)+1)-th
time. Since T_j^(K)∞, from the inductive hypothesis
T_i^(K)∞ and #(s_i';K)≤#(φ(s_i^');K).
That is, i must have played s_i^' no more than #(φ(s_i^');K)
times before playing s_i^* for the K-th time. Since #(φ(s_i^');K+1)+1>#(φ(s_i^');K),
the subhistory y_i must extend beyond period T_i^(K),
so it contains K instances of i playing s_i^*.

Next, find the subhistory y_j of y_j(𝔖,r_j)
that leads to j playing s_j^* for the (K+1)-th time.
(This is well-defined because T_j^(K+1)∞.) Note that
y_i,s_i^*∼ y_j,s_j^*, since i and j have played
s_i^*,s_j^* for K times each, and they were facing the
same response paths. Also, y_i,s_i^'∼ y_j,s_j^'
since i has played s_i^' for #(φ(s_i^');K+1)
times and j has played s_j^' for the same number of times.
Since r_j(y_j)=s_j^* and r_j is an index policy, s_j^*
must have weakly the highest index at y_j. Since r_i is
more compatible with s_i^* than r_j is with s_j^*,
s_i^' must not have the weakly highest index at y_i. And
yet r_i(y_i)=s_i' contradiction.




 §.§ Proof of Lemma <ref>


By way of contradiction, suppose there is some profile of moves by
-i, (a_h)_h∈ℋ_-i, so that h^* is off
the path of play in (s_i,(a_h)_h∈ℋ_-i)=(s_i,a_h^*,(a_h)_h∈ℋ_-i\ h^*).
Find a different action of j on h^*, a_h^*^' a_h^*.
Since h^* is off the path of play, both (s_i,a_h^*,(a_h)_h∈ℋ_-i\ h^*)
and (s_i,a_h^*^',(a_h)_h∈ℋ_-i\ h^*)
lead to the same payoff for i. But by Condition (1) in the definition
of factorability and the fact that h^*∈ F_i[s_i], we will
have found two -i action profiles s_-i,s_-i^' in two different
blocks of Π_i[s_i] with u_i(s_i,s_-i)=u_i(s_i,s_-i^').
This contradicts Π_i[s_i] being the coarsest partition of
𝕊_-i that makes u_i(s_i,·) measurable.




 §.§ Proof of Lemma <ref>


Since i's payoff is not independent of h^*, there exist actions
a_h^* a_h^*^' on h^* and a profile a_-h^*
of actions elsewhere in the game tree, so that u_i(a_h^*,a_-h^*) u_i(a_h^*^',a_-h^*).
Consider the strategy s_i for i that matches a_-h^*
in terms of play on i's information sets, so we may equivalently
write 

    u_i(s_i,a_h^*,(a_h)_h∈ℋ_-i\ h^*) u_i(s_i,a_h^*^',(a_h)_h∈ℋ_-i\ h^*),

 where (a_h)_h∈ℋ_-i\ h^* are the components
of a_-h^* corresponding to information sets of -i. If h^*∉ F_i[s_i],
then by Condition (1) of factorability, (a_h^*,(a_h)_h∈ℋ_-i\ h^*)
and (a_h^*^',(a_h)_h∈ℋ_-i\ h^*)
belong to the same block in Π_i[s_i]. Yet, they give different
payoffs to i, which contradicts that i's payoff after s_i
must be measurable with respect to Π_i[s_i].




 §.§ Proof of Proposition <ref>


Combining Lemmas <ref> and <ref>
implies there is an extensive-form strategy s_i∈𝕊_i
such that h^* is on the path of play whenever i chooses s_i.
Consider some strategy profile (s_i^∘,s_-i^∘) where
h^* is off the path. Then i can unilaterally deviate to s_i,
and h^* is on the path of (s_i,s_-i^∘). Furthermore,
i's play differs on the new path relative to the old path on exactly
one information set, since i plays at most once on any path. So
instead of deviating to s_i, i can deviate to s_i' that
matches s_i in terms of this information set where i's play
is modified, but otherwise is the same as s_i^∘. So h^*
is also on the path of play for (s_i's_-i^∘), where s_i^'
differs from s_i^∘ only on one information set.




§ INDEX COMPATIBILITY OF OPT AND
WFP WHEN S_I^*≿ S_J^*


In this section, we show that OPT and WFP are index compatible under
the conditions of Theorem <ref>.
This conclusion, when combined with Proposition <ref>,
implies Theorem <ref>.

Let the equivalence classes 𝔼 be such that (s_i,u_i(s_i,s̃_-i))∼(φ(s_i),u_j(φ(s_i),ŝ_-j)
if and only if s̃_-i|_F_i[s_i]∩ℋ_-ij=ŝ_-j|_F_j[φ(s_i)]∩ℋ_-ij.
Conditions on factorability and isomorphic factoring ensure that i,j
face (φ,𝔼)-isomorphic learning problems. Indeed,
if i and j faced the same pure profile s̃, then s̃_-i|_F_i[s_i]∩ℋ_-ij=s̃_-j|_F_j[φ(s_i)]∩ℋ_-ij
since F_i[s_i]∩ℋ_-ij=F_j[φ(s_i)]∩ℋ_-ij
by isomorphic factoring.



 §.§ Weighted Fictitious Play


To see that WFP satisfies index compatibility for s_i^* and
s_j^* under the conditions of Theorem <ref>,
let histories y_i,y_j and strategy s_i^' s_i^*
be given with y_i,s_i^*∼ y_j,s_j^*, y_i,s_i^'∼ y_j,φ(s_i^'),
and s_j^* having weakly the highest index for j. Construct
two totally mixed, independent behavior strategy profile, β,β̃
as follows. For each s_j∈𝕊_j, β(h):=α_h(·;y_j)
for all h∈ F_j[s_j]. (This is well-defined by Condition (2)
of factorability, as F_j[s_j]∩ F_j[s_j']=∅
if s_j s_j^'.) For those h∈ℋ\∪_s_j∈𝕊_jF_j[s_j],
arbitrarily specify a strictly mixed action α_h∈Δ(A_h)
for β(h). Having constructed β we turn to β̃.
For each s_i∈{s_i^*,s_i^'}, β̃(h):=α_h(·;y_i)
for all h∈ F_i[s_i]. For all other h∈ℋ, let
β̃(h):=β(h).

From the definition of y_i,s_i^*∼ y_j,s_j^*, β̃(h)=β(h)
for all h∈ F_i[s_i]∩ℋ_-ij. From the definition
of y_i,s_i^'∼ y_j,φ(s_i^'), β̃(h)=β(h)
for all h∈ F_i[s_i']∩ℋ_-ij. Also, β̃(h)=β(h)
for all other h∈ℋ_-ij by construction. So, β̃
and β are totally mixed behavior strategy profiles that match
on the -ij marginal, and they can be represented by σ̃,σ
totally mixed strategy profiles (over 𝕊) that match on
the -ij marginal.

Since j's payoff from each s_j only depends on -j's play
on F_j[s_j] by Condition (1) of factorability, ∑_s∈𝕊u_j(s_j,s_-j)·σ(s)
equals to the index that the weighted fictitious play agent assigns
to s_j after history y_j. Since s_j^* has the weakly
highest index, ∑_s∈𝕊u_j(s_j^*,s_-j)·σ(s)=max_s_j^'∈𝕊_j∑_s∈𝕊u_j(s_j^',s_-j)·σ(s).
From the definition of player compatibility, s_i^* is strictly
optimal against σ̃, which in particular means ∑_s∈𝕊u_i(s_i^*,s_-i)·σ̃(s)>∑_s∈𝕊u_i(s_i^',s_-i)·σ̃(s).
The RHS is i's index for s_i' after y_i, since σ̃
marginalized to every h∈ F_i[s_i'] is α_h(·;y_i)
by construction. This says s_i^' does not have the weakly highest
index for i after y_i.

Thus, WFP satisfies index compatibility for s_i^* and s_j^*.



 §.§ The Gittins Index


Write V(τ;s_i,ν_s_i) for the value of the above auxiliary
problem under the (not necessarily optimal) stopping time τ
in the definition of the Gittins index. The Gittins index of s_i
is sup_τ>0V(τ;s_i,ν_s_i). We begin by linking
V(τ;s_i,τ_s_i) to i's stage-game payoff from playing
s_i. From belief ν_s_i and stopping time τ, we
will construct the correlated profile α(ν_s_i,τ)∈Δ^∘(×_h∈ F_i[s_i]A_h),
so that V(τ;s_i,ν_s_i) is equal to i's expected payoff
when playing s_i while opponents play according to this correlated
profile on the s_i-relevant information sets.

A full-support belief ν_s_i∈×_h∈ F_i[s_i]Δ(Δ(A_h))
for player i together with a (possibly random) stopping rule τ>0
together induce a stochastic process (ã_(-i),t)_t≥1
over the space ×_h∈ F_i[s_i]A_h∪{∅},
where ã_(-i),t∈×_h∈ F_i[s_i]A_h
represents the opponents' actions observed in period t if τ≥ t,
and ã_(-i),t=∅ if τ<t. We
call ã_(-i),t player i's internal
history at period t and write ℙ_(-i) for the distribution
over internal histories that the stochastic process induces.

Internal histories live in the same space as player i's actual
experience in the learning problem, represented as a history in 𝕆_i.
The process over internal histories is i's prediction about what
would happen in the auxiliary problem if they were to use τ.

Enumerate all possible profiles of moves at information sets F_i[s_i]
as ×_h∈ F_i[s_i]A_h={a_(-i)^(1),...,a_(-i)^(K)},
let p_t,k:=ℙ_(-i)[ã_(-i),t=a_(-i)^(k)]
for 1≤ k≤ K be the probability under ν_s_iof seeing
the profile of actions a_(-i)^(k) in period t
of the stochastic process over internal histories, (ã_(-i),t)_t≥0,
and let p_t,0:=ℙ_(-i)[ã_(-i),t=∅]
be the probability of having stopped before period t.

The synthetic correlated profile at information sets in F_i[s_i]
is the element of Δ^∘(×_h∈ F_i[s_i]A_h)
(i.e. a correlated random action) that assigns probability ∑_t=1^∞β^t-1p_t,k/∑_t=1^∞β^t-1(1-p_t,0)
to the profile of actions a_(-i)^(k). Denote this
profile by α(ν_s_i,τ).

Note that the synthetic correlated profile depends on the belief ν_s_i
stopping rule τ, and effective discount factor β. Since
the belief ν_s_i has full support, there is always a positive
probability assigned to observing every possible profile of actions
on F_i[s_i] in the first period, so the synthetic correlated
profile is totally mixed. The significance of the synthetic correlated
profile is that it gives an alternative expression for the value of
the auxiliary problem under stopping rule τ.


    V(τ;s_i,ν_s_i)=u_i(s_i,α(ν_s_i,τ))


The proof is the same as in <cit.> and is omitted.[Notice that even though i starts with the belief that opponents
randomize independently at different information sets, and also holds
an independent prior belief, V(τ;s_i,ν_s_i) may not
be the payoff of playing s_i against a independent randomizations
by the opponent because of the endogenous correlation that we discussed
in the text.]

Consider now the situation where i and j share the same beliefs
about play of -ij on the common information sets F_i[s_i]∩ F_j[s_j]⊆ℋ_-ij.
For any pure-strategy stopping time τ_j of j, we define
a random stopping rule of i, the mimicking stopping time
for τ_j. Lemma <ref> will establish that the mimicking
stopping time generates a synthetic correlated profile that matches
the corresponding profile of τ_j on F_i[s_i]∩ F_j[s_j].

Note that τ_j maps j's internal histories to stopping decisions,
which do not live in the same space as i's internal histories.
In particular, τ_j could make use of i's play to decide
whether to stop. To mimic such a rule, i makes use of external
histories, which include both the common component of i's internal
history on F_i[s_i]∩ F_j[s_j], as well as simulated
histories on F_j[s_j]\(F_i[s_i]∩ F_j[s_j]).

For a given isomorphism φ between i and j with φ(s_i)=s_j
and F_i,F_j, we may write F_i[s_i]=F^C∪F̅^-i
with F^C⊆ℋ_-ij and F̅^-i⊆ℋ_-i.
Similarly, we may write F_j[s_j]=F^C∪F̅^-j with
F̅^-j⊆ℋ_-j. (So, F^C is the common
information sets that are observed after both s_i and s_j.)
Whenever j plays s_j, they observes some (a_(C),a_(-j))∈(×_h∈ F^CA_h)×(×_h∈F̅^-jA_h),
where a_(C) is a profile of actions at information
sets in F^C and a_(-j) is a profile of actions
at information sets in F̅^-j. So a pure-strategy stopping
rule in the auxiliary problem defining j's Gittins index for s_j
is a function τ_j:∪_t≥1[(×_h∈ F^CA_h)×(×_h∈F̅^-jA_h)]^t→{0,1}
that maps finite histories in 𝕆_jto stopping decisions,
where “0” means continue and “1” means stop.

Player i's mimicking stopping rule for τ_j draws
α^-j∈×_h∈F̅^-jΔ(A_h) from j's
belief ν_s_j on F̅^-j, and then draws (a_(-j),ℓ)_ℓ≥1
by independently generating a_(-j),ℓ from α^-j
each period. Conditional on (a_(-j),ℓ), i
stops according to the rule (τ_i|(a_(-j),ℓ))((a_(C),ℓ,a_(-i),ℓ)_ℓ=1^t):=τ_j((a_(C),ℓ,a_(-j),ℓ)_ℓ=1^t).[Note this is a valid (stochastic) stopping time, as the event {τ_i≤ T}
only depends on i's observations in 𝕆_i in the first
T periods, plus some private randomizations of i.]

That is, the mimicking stopping rule involves ex-ante randomization
across a family of pure-strategy stopping rules τ_i|(a_(-j),ℓ)_ℓ=1^∞,
indexed by (a_(-j),ℓ)_ℓ=1^∞. First,
i draws a behavior strategy on the information sets F̅^-j
according to j's belief about -j's play there. Then, i simulates
an infinite sequence (a_(-j),ℓ)_ℓ=1^∞
of i's play using this drawn behavior strategy and follows the
pure-strategy stopping rule τ_i|(a_(-j),ℓ)_ℓ=1^∞.

As in the definition of internal histories, the mimicking strategy
and i's belief ν_s_i generates a stochastic process (ã_(-i),t,ã_(C),t)_t≥1
of internal histories for i (representing actions on F_i[s_i]
that i anticipates seeing when they plays s_i). It also induces
a stochastic process (ẽ_(-j),t,ẽ_(C),t)_t≥1
of “external histories” defined in the following way:

The stochastic process of external histories (ẽ_(-j),t,ẽ_(C),t)_t≥1
is defined from the process of internal histories (ã_(-i),t,ã_(C),t)_t≥1
that τ_i generates and given by: (i) if τ_i<t, then
(ẽ_(-j),t,ẽ_(C),t)=∅;
(ii) otherwise, ẽ_(C),t=ã_(C),t,
and ẽ_(-j),t is the t-th element of the
infinite sequence (a_(-j),ℓ)_ℓ=1^∞
that i simulated before the first period of the auxiliary problem.

Write ℙ_e for the distribution over the sequence of
of external histories generated by i's mimicking stopping time
for τ_j, which is a function of τ_j,ν_s_j, and
ν_s_i.[To understand the distinction between internal and external histories,
note that the probability of i's first-period internal history
satisfying (ã_(-i),1,ã_(C),1)=(a̅_(-i),a̅_(C))
for some fixed values (a̅_(-i),a̅_(C))∈×_h∈ F_i[s_i]A_h
is given by the probability that a mixed play α_-i on F_i[s_i],
drawn according to i's belief ν_s_i, would generate the
profile of actions (a̅_(-i),a̅_(C)).
On the other hand, the probability of i's first-period external
history satisfying (ẽ_(-j),1,ẽ_(C),1)=(a̅_(-j),a̅_(C))
for some fixed values (a̅_(-j),a̅_(C))∈×_h∈ F_j[s_j]A_h
also depends on j's belief ν_s_j, for this belief determines
the distribution over (a_(-j),ℓ)_ℓ=1^∞
drawn before the start of the auxiliary problem.]

When using the mimicking stopping time for τ_j in the auxiliary
problem, i expects to see the same distribution of -ij's play
before stopping as j does when using τ_j, on the information
sets in F_i[s_i]∩ F_j[s_j]. This is formalized in the
next lemma.

 Suppose the game is isomorphcially factorable for
i and j with φ(s_i)=s_j, and suppose i holds
belief ν_s_i over play in F_i[s_i] and j holds
belief ν_s_j over play in F_j[s_j], such that ν_s_i|_F_i[s_i]∩ F_j[s_j]=ν_s_j|_F_i[s_i]∩ F_j[s_j],
that is the two sets of beliefs match when marginalized to the common
information sets in ℋ_-ij. Let τ_i be i's
mimicking stopping time for τ_j. Then, the synthetic correlated
profile α(ν_s_j,τ_j) marginalized to the information
sets of -ij is the same as α(ν_s_i,τ_i) marginalized
to the same information sets.


 Suppose the game is isomorphcially
factorable for i and j with φ(s_i)=s_j, φ(s_i^')=s_j^',
where s_i^* s_i^'. Suppose i is more player-compatible
with s_i^* than j is with s_j^*. Suppose i holds
belief ν_s_i∈×_h∈ F_i[s_i]Δ(Δ(A_h))
about opponents' play after each s_i and j holds belief ν_s_j∈×_h∈ F_j[s_j]Δ(Δ(A_h))
about opponents' play after each s_j, such that ν_s_i^*|_F_i[s_i^*]∩ F_j[s_j^*]=ν_s_j^*|_F_i[s_i^*]∩ F_j[s_j^*]
and ν_s_i^'|_F_i[s_i^']∩ F_j[s_j^']=ν_s_j^'|_F_i[s_i^']∩ F_j[s_j^'].
If s_j^* has the weakly highest Gittins index for j under
effective discount factor 0≤δγ<1, then s_i^'
does not have the weakly highest Gittins index for i under the
same effective discount factor.


We begin by defining a collection of totally mixed correlated profiles
(α_[s_j])_s_j∈𝕊_j where α_[s_j]∈Δ^∘(×_h∈ F_j[s_j]A_h).
For each s_j s_j^' the profile α_[s_j] is
the synthetic correlated profile α(ν_s_j,τ_s_j^*),
where τ_s_j^* is an optimal pure-strategy stopping time
in j's auxiliary stopping problem involving s_j. For s_j=s_j^',
the correlated profile α_[s_j^'] is instead the synthetic
correlated profile associated with the mimicking stopping rule for
τ_s_i^'^*, i.e. mimicking agent i's pure-strategy
optimal stopping time in i's auxiliary problem for s_i^'.

Next, define a profile of totally mixed correlated actions (α_[s_i])_s_i∈𝕊_i
for i's opponents on information sets (F_i[s_i])_s_i∈𝕊_i.
For each s_i∉{s_i^*,s_i^'}, just use the marginal
distribution of α_[φ(s_i)] constructed before on
F_i[s_i]∩ F_j[φ(s_i)], then arbitrarily specify
play in F_i[s_i]\ F_j[φ(s_i)], if any. For
s_i' the correlated profile is α(ν_s_i^',τ_s_i^'^*),
i.e. the synthetic move associated with i's optimal stopping rule
for s_i^'. Finally, for s_i^*, the correlated profile
α_[s_i^*] is the synthetic correlated profile associated
with the mimicking stopping rule for τ_s__j^*^*.

From Lemma <ref>, for every s_i, the profiles of correlated
actions α_[s_i] and α_[φ(s_i)] agree
when marginalized to the information sets F_i[s_i]∩ F_j[φ(s_i)].
Therefore, (α_[s_i])_s_i∈𝕊_i and (α_[s_j])_s_j∈𝕊_j
can be completed into two totally mixed correlated strategy profiles,
σ̃ and σ (over 𝕊), such that σ̃|_F_i[s_i]∩ F_j[φ(s_i)]=σ|_F_i[s_i]∩ F_j[φ(s_i)]
for every s_i. For each s_j s_j^', the Gittins index
of s_j for j is u_j(s_j,σ_s_j). Also, since
α_[s_j^'] is the mixed profile associated with the suboptimal
mimicking stopping time, u_j(s_j^',σ_s_j^') is
no larger than the Gittins index of s_j^' for j. By the
hypothesis that s_j^* has the weakly highest Gittins index
for j,u_j(s_j^*,σ_s_j^*)≥max_s_j s_j^*u_j(s_j,σ_s_j).
By the definition of strong player compatibility, we must also have
u_i(s_i^*,σ_s_i^*)>max_s_i s_i^*u_i(s_i,σ_s_i),
so in particular u_i(s_i^*,σ)>u_i(s_i'σ_s_i^').
But u_i(s_i^*,σ_s_i^*) is no larger than the Gittins
index of s_i^*, for α_[s_i^*] is the synthetic
strategy associated with a suboptimal mimicking stopping time. As
u_i(s_i'σ_s_i^') is equal to the Gittins index of
s_i' this shows s_i^' cannot have even weakly the highest
Gittins index at this belief,for s_i^* already has a strictly
higher Gittins index than s_i^' does.

To see that OPT is index compatible for s_i^*,s_j^* under
the conditions of Theorem <ref>,
let histories y_i,y_j and strategy s_i^' s_i^*
be given with y_i,s_i^*∼ y_j,s_j^*, y_i,s_i^'∼ y_j,φ(s_i^').
Since g_i,g_j are equivalent priors, i,j's posterior beliefs
match on every F∈ F_i[s_i]∩ F_j[φ(s_i)], for
s_i∈{s_i^*,s_i^'}. After such histories, if s_j^*
has weakly the highest Gittins index for j, we use the hypothesis
of player compatibility and Proposition <ref>
to see that s_i^' does not have the weakly highest Gittins
index for i.



 §.§  Proof of Lemma <ref>


Let (ã_(-i),t,ã_(C),t)_t≥1
and (ẽ_(-j),t,ẽ_(C),t)_t≥1
be the stochastic processes of internal and external histories for
τ_i, with distributions ℙ_-i and ℙ_e.
Enumerate possible profiles of actions on F^C as ×_h∈ F^CA_h={a_(C)^(1),...,a_(C)^(K_C)},
possible profiles of actions on F̅^-i as ×_h∈F̅^-iA_h={a_(-i)^(1),...,a_(-i)^(K_-i)},
and possible profiles of actions on F̅^-j as ×_h∈F̅^-jA_h={a_(-j)^(1),...,a_(-j)^(K_-j)}.

Write p_t,(k_-i,k_C):=ℙ_-i[(ã_(-i),t,ã_(C),t)=(a_(-i)^(k_-i),a_(C)^(k_C))]
for k_-i∈{1,...,K_-i} and k_C∈{1,...,K_C}. Also
write q_t,(k_-j,k_C):=ℙ_e[(ẽ_(-j),t,ẽ_(C),t)=(a_(-j)^(k_-j),a_(C)^(k_C))]
for k_-j∈{1,...,K_-j} and k_C∈{1,...,K_C}. Let
p_t,(0,0)=q_t,(0,0):=ℙ_-i[τ_i<t]=ℙ_e[τ_i<t]
be the probability of having stopped before period t.

The distribution of external histories that i expects to observe
before stopping under belief ν_s_iwhen using the mimicking
stopping rule τ_i is the same as the distribution of internal
histories that j expects to observe when using stopping rule τ_j
under belief ν_s_j, because i simulates the data-generating
process on F̅^-j by drawing a mixed action α^-j
according to j's belief ν_s_j|_F̅^-j and ν_s_i|_F^C=ν_s_j|_F^C.
Thus for every k_-j∈{1,...,K_-j} and every k_C∈{1,...,K_C},

    ∑_t=1^∞(δγ)^t-1q_t,(k_-j,k_C)/∑_t=1^∞(δγ)^t-1(1-q_t,(0,0))=α(ν_s_j,τ_j)(a_(-j)^(k_-j),a_(C)^(k_C)).

For a fixed k̅_C∈{1,...,K_C}, summing across k_-j
gives 

    ∑_t=1^∞(δγ)^t-1∑_k_-j=1^K_-jq_t,(k_-j,k̅_C)/∑_t=1^∞(δγ)^t-1(1-q_t,(0,0))=α(ν_s_j,τ_j)(a_(C)^(k̅_C)).

By definition, the processes (ã_(-i),t,ã_(C),t)_t≥0
and (ẽ_(-j),t,ẽ_(C),t)_t≥0
have the same marginal distribution on the second dimension: 

    ∑_k_-j=1^K_-jq_t,(k_-j,k̅_C)=ℙ_-i[ã_(C),t=a_(C)^(k̅_C)]=∑_k_-i=1^K_-ip_t,(k_-i,k̅_C).

Making this substitution and using the fact that p_t,(0,0)=q_t,(0,0),

    ∑_t=1^∞(δγ)^t-1∑_k_-i=1^K_-ip_t,(k_-i,k̅_C)/∑_t=1^∞(δγ)^t-1(1-p_t,(0,0))=α(ν_s_j,τ_j)(a_(C)^(k̅_C)).

But by the definition of synthetic correlated profile, the LHS is
∑_k_-i=1^K_-iα(ν_s_i,τ_i)(a_(-i)^(k_-i),a_(C)^(k̅_C))=α(ν_s_i,τ_i)(a_(C)^(k̅_C)).

Since the choice of a_(C)^(k̅_C)∈×_h∈ F^CA_h
was arbitrary, we have shown that the synthetic profile α(ν_s_j,τ_j)
of the original stopping rule τ_j and the one associated with
the mimicking strategy of i, α(ν_s_i,τ_i), coincide
on F^C.




Online Appendix





§ PROOFS OMITTED FROM THE APPENDIX




 §.§ Proof of Proposition <ref>


Suppose s_k^* is weakly optimal for k against some totally
mixed correlated profile σ^(k). We show that s_i^*
is strictly optimal for i against any totally mixed and correlated
σ^(i) with the property that marg_-ik(σ^(k))=marg_-ik(σ^(i)).

To do this, we first modify σ^(i) into a new totally profile
by copying how the action of i correlates with the actions of -(ik)
in σ^(k). For each s_-ik∈𝕊_-ik and s_i∈𝕊_i,
σ^(k)(s_i,s_-ik)>0 since marg_-k(σ^(k))∈Δ^∘(𝕊_-k).
So write p(s_i| s_-ik):=σ^(k)(s_i,s_-ik)/∑_s_i^'∈𝕊_iσ^(k)(s_i's_-ik)>0
as the conditional probability that i plays s_i given -ik
play s_-ik, in the profile σ^(k). Now construct the
profile σ̂̂̂∈Δ^∘(𝕊), where

    σ̂̂̂(s_i,s_-ik,s_k):=p(s_i| s_-ik)·σ^(i)(s_-ik,s_k).

 Profile σ̂̂̂ has the property that marg_-jk(σ̂̂̂)=marg_-jk(σ^(k)).
To see this, note first that because σ̂̂̂ and σ^(k)
agree on the -(ijk) marginal marg_-ik(σ^(k))=marg_-ik(σ^(i)).
Also, by construction, the conditional distribution of i's action
given profile of (-ijk)'s actions is the same.

From the hypothesis that s_j^*≿ s_k^*, we get j
finds s_j^* strictly optimal against σ̂̂̂.

But at the same time, marg_-i(σ̂̂̂)=marg_-i(σ^(i))
by construction, so this implies also marg_-ij(σ̂̂̂)=marg_-ij(σ^(i)).
From s_i^*≿ s_j^*, and the conclusion that j
finds s_j^* strictly optimal against σ̂̂̂
just obtained, we get i finds s_i^* strictly optimal against
σ^(i) as desired.




 §.§  Proof of Proposition <ref>


Suppose that s_i^*≿ s_j^* and that neither (ii)
nor (iii) holds. We show that these assumptions imply s_j^*≿̸s_i^*.

Partition the set Δ^∘(𝕊) into three subsets,
Π^+∪Π^0∪Π^-, with Π^+ consisting of σ∈Δ^∘(𝕊)
that make s_j^* strictly better than the best alternative pure
strategy, Π^0 the elements of Δ^∘(𝕊)
that make s_j^* indifferent to the best alternative, and Π^-
the elements that make s_j^* strictly worse. (These sets are
well defined because |𝕊_j|≥2, so j has at least
one alternative pure strategy to s_j^*.) If Π^0 is non-empty,
then there is some σ∈Π^0 such that ∑_s∈𝕊u_j(s_j^*,s_-j)σ(s)=max_s_j^'∈𝕊_j∑_s∈𝕊u_j(s_j^',s_-j)σ(s).
Because s_i^*≿ s_j^*, ∑_s∈𝕊u_i(s_i^*,s_-i)σ̂(s)>max_s_i^'∈𝕊_i\{s_i^*}∑_s∈𝕊u_i(s_i's_-i)σ̂(s)
for every σ̂∈Δ^∘(𝕊) such that marg_-ij(σ)=marg_-ij(σ̂).
Since at least one such σ̂ exists, we do not have s_j^*≿ s_i^*.

Also, if both Π^+ and Π^- are non-empty, then Π^0
is non-empty. This is because both σ↦∑_s∈𝕊u_j(s_j^*,s_-j)σ(s)
and σ↦max_s_j^'∈𝕊_j\{s_j^*}∑_s∈𝕊u_j(s_j^',s_-j)σ(s)
are continuous functions. If ∑_s∈𝕊u_j(s_j^*,s_-j)σ(s)-max_s_j^'∈𝕊_j\{s_j^*}∑_s∈𝕊u_j(s_j^',s_-j)σ(s)>0
and also ∑_s∈𝕊u_j(s_j^*,s_-j)σ̃(s)-max_s_j^'∈𝕊_j\{s_j^*}∑_s∈𝕊u_j(s_j^',s_-j)σ̃(s)<0,
then some mixture between σ and σ̃ must belong
to Π^0.

So we have shown that if either Π^0 is non-empty or both Π^+
and Π^- are non-empty, then s_j^*≿̸s_i^*.

If only Π^+ is non-empty, then s_j^* is strictly interior
dominant for j. Together with s_i^*≿ s_j^*, this
would imply that s_i^* is strictly interior dominant for i,
contradicting the assumption that (iii) does not hold.

Finally suppose that only Π^- is non-empty, so that for every
σ∈Δ^∘(𝕊) there exists a strictly better
pure response than s_j^* against σ_-j. Then, from
Lemma 4 of <cit.>, there is s a mixed strategy
σ_j for j that weakly dominates s_j^* against
all correlated strategy distributions. This σ_j strictly
dominates s_j^* against strategy distributions in Δ^∘(𝕊_-j),
so s_j^* is strictly interior dominated for j. Since (ii)
does not hold, there is a σ_-i∈Δ^∘(𝕊_-i)
against which s_i^* is a weak best response. Then, the fact
that s_j^* is not a strict best response against any σ_-j∈Δ^∘(𝕊_-j)
means s_j^*≿̸s_i^*.




 §.§ Proof of Lemma <ref>


We prove the first statement by contraposition. If 𝒞(σ̅)
is not an 𝒞(ϵ̅)-equilibrium
in the base game, then some i assigns more than the required weight
to some s_i^'∈𝕊_i that does not best respond to
𝒞(σ̅)_-i. This means no (s_i',n_i)∈𝕊̅_i
best responds to σ̅_-i, since all copies of a strategy
are payoff equivalent. Since 𝒞(σ̅)
and 𝒞(ϵ̅) are defined
by adding up the respective extended-game probabilities, 𝒞(σ̅)_i(s_i^')>𝒞(ϵ̅)(s_i^')
means ∑_n_iσ̅_i(s_i',n_i)>∑_n_iϵ̅(s_i',n_i).
So for at least one n_i^', σ̅_i(s_i',n_i^')>ϵ̅(s_i',n_i^'),
that is σ̅_i assigns more than required weight to the
non best response (s_i',n_i^')∈𝕊̅_i. We
conclude σ̅ is not an ϵ̅-equilibrium,
as desired.

Again by contraposition, suppose ℰ(σ)
is not an ℰ(ϵ)-equilibrium
in the extended game. This means some i assigns more than the required
weight to some (s_i',n_i^')∈𝕊̅_i that does
not best respond to ℰ(σ)_-i. This implies
s_i^' does not best respond to σ_-i. By the definition
of ℰ(ϵ) and ℰ(σ),
if ℰ(σ)_i(s_i',n_i^')>ℰ(ϵ)(s_i',n_i^'),
then also ℰ(σ)_i(s_i',n_i)>ℰ(ϵ)(s_i',n_i)
for every n_i such that (s_i',n_i)∈𝕊̅_i.
Therefore, we also have σ_i(s_i^')>ϵ(s_i^'),
so σ is not an ϵ-equilibrium in the
base game as desired.




 §.§ Proof of Proposition <ref>


Suppose σ̅^* is a PCE in the extended game. So, we
have σ̅^(t)→σ̅^* where each σ̅^(t)
is an ϵ̅^(t)-PCE, and each ϵ̅^(t)
is player-compatible (in the extended game sense). This means each
𝒞(ϵ̅^(t)) is player
compatible in the base game sense, and furthermore each 𝒞(σ̅^(t))
is an 𝒞(ϵ̅^(t))-equilibrium
(by Lemma <ref>), hence an 𝒞(ϵ̅^(t))-PCE.
Since ϵ̅^(t)→0, 𝒞(ϵ̅^(t))→0
as well. Since σ̅^(t)→σ̅^*, 𝒞(σ̅^(t))→𝒞(σ̅^*).
We have shown 𝒞(σ̅^*) is a PCE
in the base game.

The proof of the other statement is exactly analogous.




 §.§ Proof of Proposition <ref>


We have r_i=OPT_i if and only if for every ỹ_i∈Ỹ_i,
r_i(ψ(ỹ_i)) has the (weakly) higher Gittins index.
Since r_i,r̃_i are equivalent up to duplicates, this
means for any ỹ_i∈Ỹ_i, r̃_i(ỹ_i)
either puts probability 1 on Out or probability 1 on In
and In-d. Since In and In-d can be viewed
as two identical ways of pulling the risky arm in a two-armed bandit
with one safe arm and one risky arm, r̃_i is optimal if
and only if r̃_i(ỹ_i) assigns positive probability
1 to In and In-d when the risky arm has a (weakly)
higher Gittins index than the safe one. These two statements are equivalent
when r̃_i,r_i are equivalent up to duplicates, since
the Gittins index of the risky arm is the same under ỹ_i
and ψ(ỹ_i). Similarly, r_i=WFP_i if
and only if for every ỹ_i∈Ỹ_i, r_i(ψ(ỹ_i))
has the (weakly) higher “WFP” index, defined as the one-period
expected payoff of playing a certain strategy against the weighted
fictitious play conjecture of -i's play. These indices are the
same after history ỹ_i in the extended stage game and
after ψ(ỹ_i) in the original stage game.

Finally, let X_i^t be the random variable representing i's
play in period t in the base game under policy r_i and social
distribution σ_-i. Let X̃_i^t be the random
variable representing i's play in period t in the extended game
under policy r̃_i and social distribution σ̃_-i.
Because r_i,r̃_i are equivalent up to duplicates to
the empty history, ℙ_r_i,σ_-i[X_i^1=Out]=ℙ_r̃_i,σ̃_-i[X̃_i^1=Out].
Since σ_-i and σ̃_-i are -i equivalent,
(r_i,σ_-i) and (r̃_i,σ̃_-i)
generate the same distribution over length-1 histories (up to duplicates),
i.e. ℙ_r_i,σ_-i[y_i]=ℙ_r̃_i,σ̃_-i[ψ^-1(y_i)]
for all y_i∈({In,Out}×ℝ).
By induction suppose ℙ_r_i,σ_-i[y_i]=ℙ_r̃_i,σ̃_-i[ψ^-1(y_i)]
for all y_i∈({In,Out}×ℝ)^t,
for some t≥1. If r_i(y_i)=Out,
then using the fact that r_i,r̃_i are equivalent up
to duplicates, r̃_i(ỹ_i)(Out)=1
for all ỹ_i∈ψ^-1(y_i). Thus, for all x∈ℝ,
by the inductive hypothesis ℙ_r_i,σ_-i[(y_i,Out,x)]=ℙ_r̃_i,σ̃_-i[ψ^-1(y_i)×(Out,x)],
and ℙ_r_i,σ_-i[(y_i,In,x)]=ℙ_r̃_i,σ̃_-i[ψ^-1(y_i)×(In,x)]=ℙ_r̃_i,σ̃_-i[ψ^-1(y_i)×(In-d,x)]=0.
On the other hand, if r_i(y_i)=In, then
using the fact that r_i,r̃_i are equivalent up to duplicates,
r̃_i(ỹ_i)(In)+r̃_i(ỹ_i)(In-d)=1
for all ỹ_i∈ψ^-1(y_i). Thus, for all x∈ℝ,
by the inductive hypothesis, ℙ_r_i,σ_-i[(y_i,Out,x)]=ℙ_r̃_i,σ̃_-i[ψ^-1(y_i)×(Out,x)]=0,
and ℙ_r_i,σ_-i[(y_i,In,x)]=ℙ_r̃_i,σ̃_-i[ψ^-1(y_i)×(In,x)]+ℙ_r̃_i,σ̃_-i[ψ^-1(y_i)×(In-d,x)].
In either case, we get ℙ_r_i,σ_-i[y_i]=ℙ_r̃_i,σ̃_-i[ψ^-1(y_i)]
for all y_i∈({In,Out}×ℝ)^t+1,
and also ℙ_r_i,σ_-i[X_i^t=Out]=ℙ_r̃_i,σ̃_-i[X̃_i^t=Out].
By induction we get ℙ_r_i,σ_-i[X_i^t=Out]=ℙ_r̃_i,σ̃_-i[X̃_i^t=Out]
for every t≥1, thus ϕ_i(In;r_i,σ_-i)=ϕ_i(In;r̃_i,σ̃_-i)+ϕ_i(In-d;r̃_i,σ̃_-i).




§ REFINEMENTS IN THE LINK-FORMATION
GAME


Each of the following refinements selects the same subset of pure
Nash equilibria when applied to the anti-monotonic and co-monotonic
versions of the link-formation game: extended proper equilibrium,
proper equilibrium, trembling-hand perfect equilibrium, p-dominance,
Pareto efficiency, and strategic stability. Pairwise stability does
not apply to the link-formation game. Finally, the link-formation
game is not a potential game.


Step 1. Extended proper equilibrium, proper equilibrium, and
trembling-hand perfect equilibrium allow the “no links” equilibrium
in both versions of the game. For (q_i) anti-monotonic with
(c_i), for each ϵ>0 let N1 and S1 play Active
with probability ϵ^2, N2 and S2 play Active with
probability ϵ. For small enough ϵ, the expected
payoff of Active for player i is approximately (10-c_i)ϵ
since terms with higher order ϵ are negligible. It is clear
that this payoff is negative for small ϵ for every player
i, and that under the utility re-scalings β_N1=β_S1=10,
β_N2=β_S2=1, the loss to playing Active smaller
for N2 and S2 than for N1 and S1. So this strategy profile is a (β,ϵ)-extended
proper equilibrium. Taking ϵ→0, we arrive at the equilibrium
where each player chooses Inactive with probability 1.

For the version with (q_i) co-monotonic with (c_i), consider
the same strategies without re-scalings, i.e. β=1.
Then already the loss to playing Active smaller for N2 and
S2 than for N1 and S1, making the strategy profile a (1,ϵ)-extended
proper equilibrium.

These arguments show that the “no links” equilibrium is an extended
proper equilibrium in both versions of the game. Every extended proper
equilibrium is also proper and trembling-hand perfect, which completes
the step.

Step 2. p-dominance eliminates the “no links” equilibrium
in both versions of the game. Regardless of whether (q_i) are
co-monotonic or anti-monotonic with (c_i), under the belief that
all other players choose Active with probability p for
p∈(0,1), the expected payoff of playing Active (due
to additivity across links) is (1-p)·0+p·(10+30-2c_i)>0
for any c_i∈{14,19}.

Step 3. Pareto eliminates the “no links” equilibrium in
both versions of the game. It is immediate that the no-links equilibrium
outcome is Pareto dominated by the all-links equilibrium outcome under
both parameter specifications, so Pareto efficiency would rule it
out whether (c_i) is anti-monotonic or co-monotonic with (q_i).

Step 4. Strategic stability <cit.>
eliminates the “no links” equilibrium in both versions of the
game. First suppose the (c_i) are anti-monotonic with (q_i).
Let η=1/100 and let ϵ^'>0 be given. Define ϵ_N1(Active)=ϵ_S1(Active)=2ϵ^',
ϵ_N2(Active)=ϵ_S2(Active)=ϵ^'
and ϵ_i(Inactive)=ϵ^' for all
players i. When each i is constrained to play s_i with
probability at least ϵ_i(s_i), the only Nash equilibrium
is for each player to choose Active with probability 1-ϵ^'.
(To see this, consider N2's play in any such equilibrium σ.
If N2 weakly prefers Active, then N1 must strictly prefer
it, so σ_N1(𝐀𝐜𝐭𝐢𝐯𝐞)=1-ϵ^'≥σ_N2(𝐀𝐜𝐭𝐢𝐯𝐞).
On the other hand, if N2 strictly prefers Inactive, then
σ_N2(𝐀𝐜𝐭𝐢𝐯𝐞)=ϵ^'<2ϵ^'≤σ_N1(𝐀𝐜𝐭𝐢𝐯𝐞).
In either case, σ_N1(𝐀𝐜𝐭𝐢𝐯𝐞)≥σ_N2(𝐀𝐜𝐭𝐢𝐯𝐞).)
When both North players choose Active with probability 1-ϵ^',
each South player has Active as their strict best response,
so σ_S1(𝐀𝐜𝐭𝐢𝐯𝐞)=σ_S2(𝐀𝐜𝐭𝐢𝐯𝐞)=1-ϵ^'.
Against such a profile of South players, each North player has Active
as their strict best response, so σ_N1(𝐀𝐜𝐭𝐢𝐯𝐞)=σ_N2(𝐀𝐜𝐭𝐢𝐯𝐞)=1-ϵ^'.

Now suppose the (c_i) are co-monotonic with (q_i). Again
let η=1/100 and let ϵ^'>0 be given. Define ϵ_N1(Active)=ϵ_S1(Active)=ϵ^',
ϵ_N2(Active)=ϵ^'/1000, ϵ_S2(Active)=ϵ^'
and ϵ_i(Inactive)=ϵ^' for all
players i. Suppose by way of contradiction there is a Nash equilibrium
σ of the constrained game which is η-close to the Inactive
equilibrium. In such an equilibrium, N2 must strictly prefer Inactive,
otherwise N1 strictly prefers Active so σ could not
be η-close to the Inactive equilibrium. Similar argument
shows that S2 must strictly prefer Inactive. This shows N2
and S2 must play Active with the minimum possible probability,
that is σ_N2(Active)=ϵ^'/1000 and
σ_S2(Active)=ϵ^' . This implies
that, even if σ_N1(Active) were at its minimum
possible level of ϵ^', S1 would still strictly prefer
playing Inactive because S1 is 1000 times as likely to link
with the low-quality opponent as the high-quality opponent. This shows
σ_S1(Active)=ϵ^'. But when σ_S1(Active)=σ_S2(Active)=ϵ^',
N1 strictly prefers playing Active, so σ_N1(Active)=1-ϵ^'.
This contradicts σ being η-close to the no-links equilibrium.

Step 5. Pairwise stability <cit.>
does not apply to this game. This is because each player chooses
between either linking with every player on the opposite side who
plays Active, or linking with no one. A player cannot selectively
cut off one of their links while preserving the other.

Step 6. The game does not have an ordinal potential, so refinements
of potential games <cit.> do not
apply. To see that this is not a potential game, consider the anti-monotonic
parameterization. Suppose a potential P of the form P(a_N1,a_N2,a_S1,a_S2)
exists, where a_i=1 corresponds to i choosing Active,
a_i=0 corresponds to i choosing Inactive. We must
have 

    P(0,0,0,0)=P(1,0,0,0)=P(0,0,0,1),

since a unilateral deviation by one player from the Inactive
equilibrium does not change any player's payoffs. But notice that
u_N1(1,0,0,1)-u_N1(0,0,0,1)=10-14=-4, while u_S2(1,0,0,1)-u_S2(1,0,0,0)=30-19=11.
If the game has an ordinal potential, then both of these expressions
must have the same sign as P(1,0,0,1)-P(1,0,0,0)=P(1,0,0,1)-P(0,0,0,1),
which is not true. A similar argument shows the co-monotonic parameterization
does not have a potential either.


