Characterizing Solution Concepts in Games Using Knowledge-Based Programs

1 Introduction

Game theorists represent games in two standard ways: in normal form, where each agent simply chooses a strategy, and in extensive form, using game trees, where the agents make choices over time. An extensive-form representation has the advantage that it describes the dynamic structure of the game-it explicitly represents the sequence of decision problems encountered by agents. However, the extensiveform representation purports to do more than just describe the structure of the game; it also attempts to represent the information that players have in the game, by the use of information sets. Intuitively, an information set consists of a set of nodes in the game tree where a player has the same information. However, as Halpern [1997] has pointed out, information sets may not adequately represent a player's information.

Halpern makes this point by considering the following single-agent game of imperfect recall, originally presented by Piccione and Rubinstein [1997]: The game starts with nature moving either left or right, each with probability 1/2. The agent can then either stop the game (playing move S) and get

∗Supported in part by NSF under grants CTC-0208535 and ITR0325453, by ONR under grant N00014-02-1-0455, by the DoD Multidisciplinary University Research Initiative (MURI) program administered by the ONR under grants N00014-01-1-0795 and N00014-04-1-0725, and by AFOSR under grant F49620-02-1-0101.

Yoram Moses

Department of Electrical Engineering Technion-Israel Institute of Technology 32000 Haifa, Israel

email: moses@ee.technion.ac.il

a payoff of 2, or continue, by playing move B. If he continues, he gets a high payoff if he matches nature's move, and a low payoff otherwise. Although he originally knows nature's move, the information set that includes the nodes labeled x3 and x4 is intended to indicate that the player forgets whether nature moved left or right after moving B. Intuitively, when he is at the information set X, the agent is not supposed to knowwhether he is at x3 or at x4.

It is not hard to show that the strategy that maximizes expected utility chooses action S at node x1, action B at node x2, and action R at the information set X consisting of x3 and x4. Call this strategy f. Let f ′ be the strategy of choosing action B at x1, action S at x2, and L at X. Piccione and Rubinstein argue that if node x1 is reached, the player should reconsider, and decide to switch from f to f ′ . As Halpern points out, this is indeed true, provided that the player knows at each stage of the game what strategy he is currently using. However, in that case, if the player is using f at the information set, then he knows that he is at node x4; if he has switched and is using f ′ , then he knows that he is at x3. So, in this setting, it is no longer the case that the player does not know whether he is at x3 or x4 in the information set; he can infer which state he is at from the strategy he is using.

In game theory, a strategy is taken to be a function from information sets to actions. The intuition behind this is that, since an agent cannot tell the nodes in an information set apart, he must do the same thing at all these nodes. But this example shows that if the agent has imperfect recall but can switch strategies, then he can arrange to do different things at different nodes in the same information set. As Halpern [1997] observes, ' "situations that [an agent] cannot distinguish" and "nodes in the same information set" may be two quite different notions.' He suggests using the game tree to describe the structure of the game, and using the runs and systems framework [Fagin et al., 1995] to describe the agent's information. The idea is that an agent has an internal local state that describes all the information that he has. A strategy (or protocol in the language of [Fagin et al., 1995]) is a function from local states to actions. Protocols capture the intuition that what an agent does can depend only what he knows. But now an agent's knowledge is represented by its local state, not by an information set. Different assumptions about what agents know (for example, whether they know their current strategies) are captured by running the same protocol in different contexts. If the information sets appropriately represent an agent's knowledge in a game, then we can identify local states with information sets. But, as the example above shows, we cannot do this in general.

A number of solution concepts have been considered in the game-theory literature, ranging from Nash equilibrium and correlated equilibrium to refinements of Nash equilibrium such as sequential equilibrium and weaker notions such as rationalizability (see [Osborne and Rubinstein, 1994] for an overview). The fact that game trees represent both the game and the players' information has proved critical in defining solution concepts in extensive-form games. Can we still represent solution concepts in a useful way using runs and systems to represent a player's information? As we show here, not only can we do this, but we can do it in a way that gives deeper insight into solution concepts. Indeed, all the standard solution concepts in the literature can be understood as instances of a single knowledge-based (kb) program [Fagin et al., 1995; 1997], which captures the underlying intuition that a player should make a best response, given her beliefs. The differences between solution concepts arise from running the kb program in different contexts.

In a kb program, a player's actions depend explicitly on the player's knowledge. For example, a kb program could have a test that says "If you don't know that Ann received the information, then send her a message", which can be written

This kb program has the form of a standard if . . . then statement, except that the test in the if clause is a test on i's knowledge (expressed using the modal operator Bi for belief; see Section 2 for a discussion of the use of knowledge vs. belief).

Using such tests for knowledge allows us to abstract away from low-level details of how the knowledge is obtained. Kb programs have been applied to a number of problems in the computer science literature (see [Fagin et al., 1995] and the references therein). To see how they can be applied to understand equilibrium, given a game Γ in normal form, let Si(Γ) consist of all the pure strategies for player i in Γ. Roughly speaking, we want a kb program that says that if player i believes that she is about to perform strategy S (which we express with the formula doi(S)), and she believes that she would not do any better with another strategy, then she should indeed go ahead and run S. This test can be viewed as embodying rationality. There is a subtlety in expressing the statement "she would not do any better with another strategy". We express this by saying "if her expected utility, given that she will use strategy S, is x, then her expected utility if she were to use strategy S ′ is at most x." The "if she were to use S ′ " is a counterfactual statement. She is planning to use strategy S, but is contemplating what would happen if she were to do something counter to fact, namely, to use S ′ . Counterfactuals have been the subject of intense study in the philosophy literature (see, for example, [Lewis, 1973; Stalnaker, 1968]) and, more recently, in the game theory literature (see, for example, [Aumann, 1995; Halpern, 2001; Samet, 1996]). We write the counterfactual "If A were the case then B would be true" as "A ⪰ B". Although this statement involves an "if . . . then", the semantics of the counterfactual implication A ⪰ B is quite different from the material implication A ⇒ B. In particular, while A ⇒ B is true if A is false, A ⪰ B might not be.

With this background, consider the following kb program for player i:

This kb program is meant to capture the intuition above. Intuitively, it says that if player i believes that she is about to perform strategy S and, if her expected utility is x, then if she were to perform another strategy S ′ , then her expected utility would be no greater than x, then she should perform strategy S. Call this kb program EQNFΓ (with the individual instance for player i denoted by EQNFΓi ). As we show, if all players follow EQNFΓ , then they end up playing some type of equilibrium. Which type of equilibrium they play depends on the context. Due to space considerations, we focus on three examples in this abstract. If the players have a common prior on the joint strategies being used, and this common prior is such that players' beliefs are independent of the strategies they use, then they play a Nash equilibrium. Without this independence assumption, we get a correlated equilibrium. On the other hand, if players have possibly different priors on the space of strategies, then this kb program defines rationalizable strategies [Bernheim, 1984; Pearce, 1984].

To deal with extensive-form games, we need a slightly different kb program, since agents choose moves, not strategies. Let EQEFΓi be the following program, where a ∈ PM denotes that a is a move that is currently possible.

Just as EQNFΓ characterizes equilibria of a game Γ represented in normal form, EQEFΓ characterizes equilibria of a game represented in extensive form. We give one example here: sequential equilibrium. To capture sequential equilibrium, we need to assume that information sets do correctly describe an agent's knowledge. If we drop this assumption, however, we can distinguish between the two equilibria for the game described in Figure 1.

All these solution concepts are based on expected utility. But we can also consider solution concepts based on other decision rules. For example, Boutilier and Hyafil [2004] consider minimax-regret equilibria, where each player uses a strategy that is a best-response in a minimax-regret sense to the choices of the other players. Similarly, we can use maximin equilibria [Aghassi and Bertsimas, 2006]. As pointed out by Chu and Halpern [2003], all these decision rules can be viewed as instances of a generalized notion of expected utility, where uncertainty is represented by a plausibility measure, a generalization of a probability measure, utilities are elements of an arbitrary partially ordered space, and plausibilities and utilities are combined using ⊕ and ⊗, generalizations of + and ×. We show in the full paper that, just by interpreting "EUi = u" appropriately, we can capture these more exotic solution concepts as well. Moreover, we can capture solution concepts in games where the game itself is not common knowledge, or where agents are not aware of all moves available, as discussed by Halpern and Rˆego [2006].

Our approach thus provides a powerful tool for representing solution concepts, which works even if (a) information sets do not capture an agent's knowledge, (b) uncertainty is not represented by probability, or (c) the underlying game is not common knowledge.

The rest of this paper is organized as follows. In Section 2, we review the relevant background on game theory and knowledge-based programs. In Section 3, we show that EQNFΓ and EQEFΓ characterize Nash equilibrium, correlated equilibrium, rationalizability, and sequential equilibrium in a game Γ in the appropriate contexts. We conclude in Section 4 with a discussion of how our results compare to other characterizations of solution concepts.

2 Background

In this section, we review the relevant background on games and knowledge-based programs. We describe only what we need for proving our results. The reader is encouraged to consult [Osborne and Rubinstein, 1994] for more on game theory, [Fagin et al., 1995; 1997] for more on knowledge-based programs without counterfactuals, and [Halpern and Moses, 2004] for more on adding counterfactuals to knowledgebased programs.

2.1 Games and Strategies

A game in extensive form is described by a game tree. Associated with each non-leaf node or history is either a playerthe player whose move it is at that node-or nature (which can make a randomized move). The nodes where a player i moves are further partitioned into information sets. With each run or maximal history h in the game tree and player i we can associate i's utility, denoted ui(h), if that run is played. A strategy for player i is a (possibly randomized) function from i's information sets to actions. Thus a strategy for player i tells player i what to do at each node in the game tree where i is supposed to move. Intuitively, at all the nodes that player i cannot tell apart, player i must do the same thing. A joint strategy ⃗S = (S1, . . . , Sn) for the players determines a distribution over paths in the game tree. A normal-form game can be viewed as a special case of an extensive-form game where each player makes only one move, and all players move simultaneously.

2.2 Protocols, Systems, and Contexts

To explain kb programs, we must first describe standard protocols. We assume that, at any given point in time, a player in a game is in some local state. The local state could include the history of the game up to this point, the strategy being used by the player, and perhaps some other features of the player's type, such as beliefs about the strategies being used by other players. A global state is a tuple consisting of a local state for each player.

A protocol for player i is a function from player i's local states to actions. For ease of exposition, we consider only deterministic protocols, although it is relatively straightforward to model randomized protocols-corresponding to mixed strategies-as functions from local states to distributions over actions. Although we restrict to deterministic protocols, we deal with mixed strategies by considering distributions over pure strategies.

A run is a sequence of global states; formally, a run is a function from times to global states. Thus, r(m) is the global state in run r at time m. A point is a pair (r,m) consisting of a run r and time m. Let ri(m) be i's local state at the point (r,m); that is, if r(m) = (s1, . . . , sn), then ri(m) = si. A joint protocol is an assignment of a protocol for each player; essentially, a joint protocol is a joint strategy. At each point, a joint protocol ⃗ P performs a joint action (P1(r1(m)), . . . , Pn(rn(m))), which changes the global state. Thus, given an initial global state, a joint protocol ⃗ P generates a (unique) run, which can be thought of as an execution of ⃗ P. The runs in a normal-form game involve only one round and two time steps: time 0 (the initial state) and time 1, after the joint strategy has been executed. (We assume that the payoff is then represented in the player's local state at time 1.) In an extensive-form game, a run is again characterized by the strategies used, but now the length of the run depends on the path of play.

A probabilistic system is a tuple PS = (R, ⃗μ), where R is a set of runs and ⃗μ = (μ1, . . . , μn) associates a probablity μi on the runs of Rwith each player i. Intuitively, μi represents player i's prior beliefs. In the special case where μ1 = · · · = μn = μ, the players have a common prior μ on R. In this case, we write just (R, μ).

We are interested in the system corresponding to a joint protocol ⃗ P . To determine this system, we need to describe the setting in which ⃗ P is being executed. For our purposes, this setting can be modeled by a set G of global states, a subset G0 of G that describes the possible initial global states, a set As of possible joint actions at each global state s, and n probability measures on G0, one for each player. Thus, a probabilistic context is a tuple γ = (G, G0, {As : s ∈ G}, ⃗μ). 1 A joint protocol ⃗ P is appropriate for such a context γ if, for every global state s, the joint actions that ⃗ P can generate are in As. When ⃗ P is appropriate for γ, we abuse notation slightly and refer to γ by specifying only the pair (G0, ⃗μ). A protocol ⃗ P and a context γ for which ⃗ P is appropriate generate a system; the system depends on the initial states and probability measures in γ. Since these are all that matter, we typically simplify the description of a context by omitting the set G of global states and the sets As of global actions. Let R( ⃗ P , γ) denote the system generated by joint protocol ⃗ P in context γ. If γ = (G0, ⃗μ), thenR( ⃗ P , γ) = (R, ⃗μ′ ), where R consists of a the run r⃗s for each initial state ⃗s ∈ G0, where r⃗s is the run generated by ⃗ P when started in state ⃗s, and μ′i (r⃗s) = μi(⃗s), for i = 1, . . . , n.

1 We are implicitly assuming that the global state that results from

A probabilistic system (R, ⃗μ′ ) is compatible with a context γ = (G0, ⃗μ) if (a) every initial state in G0 is the initial state of some run in R, (b) every run is the run of some protocol appropriate for γ, and (c) if R(⃗s) is the set of runs in R with initial global state ⃗s, then μ′j (R(⃗s)) = μj(⃗s), for j = 1, . . . , n. Clearly R( ⃗ P , γ) is compatible with γ.

We can think of the context as describing background information. In distributed-systems applications, the context also typically includes information about message delivery. For example, it may determine whether all messages sent are received in one round, or whether they may take up to, say, five rounds. Moreover, when this is not obvious, the context specifies how actions transform the global state; for example, it describes what happens if in the same joint action two players attempt to modify the same memory cell. Since such issues do not arise in the games we consider, we ignore these facets of contexts here. For simplicity, we consider only contexts where each initial state corresponds to a particular joint strategy of Γ. That is, ΣΓi is a set of local states for player i indexed by (pure) strategies. The set ΣΓi can be viewed as describing i's types; the state sS can the thought of as the initial state where player i's type is such that he plays S (although we stress that this is only intuition; player i does not have to play S at the state sS). Let GΓ 0 = ΣΓ1 × . . . ×ΣΓn. We will be interested in contexts where the set of initial global states is a subset G0 of GΓ 0 . In a normal-formgame, the only actions possible for player i at an initial global state amount to choosing a pure strategy, so the joint actions are joint strategies; no actions are possible at later times. For an extensive-formgame, the possible moves are described by the game tree. We say that a context for an extensive-form game is standard if the local states have the form (s, I), where s is the initial state and I is the current information set. In a standard context, an agent's knowledge is indeed described by the information set. However, we do not require a context to be standard. For example, if an agent is allowed to switch strategies, then the local state could include the history of strategies used. In such a context, the agent in the game of Figure 1 would know more than just what is in the information set, and would want to switch strategies.

performing a joint action in As at the global state s is unique and obvious; otherwise, such information would also appear in the context, as in the general framework of [Fagin et al., 1995].

2.3 Knowledge-Based Programs

A knowledge-based program is a syntactic object. For our purposes, we can take a knowledge-based program for player i to have the form

where each κj is a Boolean combination of formulas of the form Biϕ, in which the ϕ's can have nested occurrences of Bℓ operators and counterfactual implications. We assume that the tests κ1, κ2, . . . are mutually exclusive and exhaustive, so that exactly one will evaluate to true in any given instance. The programEQNFΓi can be written in this form by simply replacing the for . . . do statement by one line for each pure strategy in Si(Γ); similarly for EQEFΓi .

We want to associate a protocol with a kb program. Unfortunately, we cannot "execute" a kb program as we can a protocol. How the kb program executes depends on the outcome of tests κj. Since the tests involve beliefs and counterfactuals, we need to interpret themwith respect to a system. The idea is that a kb program Pgi for player i and a probabilistic system PS together determine a protocol P for player i. Rather than giving the general definitions (which can be found in [Halpern and Moses, 2004]), we just show how they work in the two kb programs we consider in this paper: EQNF and EQEF.

Given a system PS = (R, ⃗μ), we associate with each formula ϕ a set [[ϕ]]PS of points in PS. Intuitively, [[ϕ]]PS is the set of points of PS where the formula ϕ is true. We need a little notation:

• If E is a set of points in PS, let R(E) denote the set of runs going through points in E; that is R(E) = {r : ∃m((r, m) ∈ E)}.
• Let Ki(r,m) denote the set of points that i cannot distinguish from (r, m): Ki(r, m) = {(r′ ,m′ ) : (r′i (m′ ) = ri(m)}. Roughly speaking, Ki(r,m) corresponds to i's information set at the point (r,m).
• Given a point (r,m) and a player i, let μ(i,r,m) be the probability measure that results from conditioning μi on Ki(r,m), i's information at (r,m). We cannot condition on Ki(r,m) directly: μi is a probability measure on runs, and Ki(r,m) is a set of points. So we actually condition, not on Ki(r, m), but on R(Ki(r, m)), the set of runs going through the points in Ki(r,m). Thus, μi,r,m = μi | R(Ki(r,m)). (For the purposes of this abstract, we do not specify μi,r,m if μi(R(Ki(r, m))) = 0. It turns out not to be relevant to our discussion.)

The kb programs we consider in this paper use a limited collection of formulas. We now can define [[ϕ]]PS for the formulas we consider that do not involve counterfactuals.

• In a system PS corresponding to a normal-form game Γ, if S ∈ Si(Γ), then [[doi(S)]]PS is the set of initial points (r, 0) such that player i uses strategy S in run r.
• Similarly, if PS corresponds to an extensive-formgame, then [[doi(a)]]PS is the set of points (r,m) of PS at which i performs action a.

• Player i believes a formula ϕ at a point (r,m) if the event corresponding to formula ϕ has probability 1 according to μi,r,m. That is, (r,m) ∈ [[Biϕ]]PS if μi(R(Ki(r,m)) ̸= 0 (so that conditioning on Ki(r,m) is defined) and μi,r,m([[ϕ]]PS ∩ Ki(r, m)) = 1.
• With every run r in the systems we consider, we can associate the joint (pure) strategy ⃗S used in r. 2 This pure strategy determines the history in the game, and thus determines player i's utility. Thus, we can associate with every point (r,m) player i's expected utility at (r,m), where the expectation is taken with respect to the probability μi,r,m. If u is a real number, then [[EUi = u]]PS is the set of points where player i's expected utility is u; [[EUi ≤ u]]PS is defined similarly.
• Assume that ϕ(x) has no occurrences of ∀. Then [[∀xϕ(x))]]PS = ∩a∈IR[[ϕ[x/a]]]PS, where ϕ[x/a] is the result of replacing all occurrences of x in ϕ by a. That is, ∀x is just universal quantification over x, where x ranges over the reals. This quantification arises for us when x represents a utility, so that ∀xϕ(x) is saying that ϕ holds for all choices of utility.

We now give the semantics of formulas involving counterfactuals. Here we consider only a restricted class of such formulas, those where the counterfactual only occurs in the form doi(S) ⪰ ϕ, which should be read as "if i were to use strategy S, then ϕ would be true. Intuitively, doi(S) ⪰ ϕ is true at a point (r,m) if ϕ holds in a world that differs from (r,m) only in that i uses the strategy S. That is, doi(S) ⪰ ϕ is true at (r,m) if ϕ is true at the point (r′ ,m) where, in run r′ , player i uses strategy S and all the other players use the same strategy that they do at (r,m). (This can be viewed as an instance of the general semantics for counterfactuals used in the philosophy literature [Lewis, 1973; Stalnaker, 1968] where ψ ⪰ ϕ is taken to be true at a world w if ϕ is true at all the worlds w′ closest to w where ψ is true.) Of course, if i actually uses strategy S in run r, then r′ = r. Similarly, in an extensive-form game Γ, the closest point to (r,m) where doi(a′ ) is true (assuming that a′ is an action that i can perform in the local state ri(m)) is the point (r′ , m) where all players other than player i use the same protocol in r′ and r, and i's protocol in r′ agrees with i's protocol in r except at the local state ri(m), where i performs action a′ . Thus, r′ is the run that results from player i making a single deviation (to a′ at time m) from the protocol she uses in r, and all other players use the same protocol as in r.

There is a problem with this approach. There is no guarantee that, in general, such a closest point (r′ ,m) exists in the system PS. To deal with this problem, we restrict attention to a class of systems where this point is guaranteed to exist. A system (R, ⃗μ) is complete with respect to context γ if R includes every run generated by a protocol appropriate for context γ. In complete systems, the closest point (r′ , m) is guaranteed to exist. For the remainder of the paper, we evaluate formulas only with respect to complete systems. In a complete system PS, we define [[doi(S) ⪰ ϕ]]PS to consist of all the points (r,m) such that the closest point (r′ ,m) to (r,m) where i uses strategy S is in [[ϕ]]PS. The definition of [[doi(a) ⪰ ϕ]]PS is similar. We say that a complete system (R′ , ⃗μ′ ) extends (R, ⃗μ) if μj and μ′j agree on R (so that μ′j (A) = μj(A)) for all A ⊆ R) for j = 1, . . . , n.

2 If we allow players to change strategies during a run, then we will in general have different joint strategies at each point in a run. For our theorems in the next section, we restrict to contexts where players do not change strategies.

Since each formula κ that appears as a test in a kb program Pgi for player i is a Boolean combination of formulas of the form Biϕ, it is easy to check that if (r,m) ∈ [[κ]]PS, then Ki(r,m) ⊆ [[κ]]PS. In other words, the truth of κ depends only on i's local state. Moreover, since the tests are mutually exclusive and exhaustive, exactly one of them holds in each local state. Given a system PS, we take the protocol PgPS i to be such that PgPS i (ℓ) = aj if, for some point (r,m) in PS with ri(m) = ℓ, we have (r,m) ∈ [[κj]]PS. Since κ1, κ2, . . . are mutually exclusive and exhaustive, there is exactly one action aj with this property.

We are mainly interested in protocols that implement a kb program. Intuitively, a joint protocol ⃗ P implements a kb program ⃗ Pg in context γ if ⃗ P performs the same actions as ⃗ Pg in all runs of ⃗ P that have positive probability, assuming that the knowledge tests in ⃗ Pg are interpreted with respect to the complete system PS extending R( ⃗ P, γ). Formally, a joint protocol ⃗ P (de facto) implements a joint kb program ⃗ Pg [Halpern and Moses, 2004] in a context γ = (G0, ⃗μ) if Pi(ℓ) = PgPS i (ℓ) for every local state ℓ = ri(m) such that r ∈ R( ⃗ P, γ) and μi(r) ̸= 0, where PS is the complete system extending R( ⃗ P, γ). We remark that, in general, there may not be any joint protocols that implement a kb program in a given context, there may be exactly one, or there may be more than one (see [Fagin et al., 1995] for examples). This is somewhat analogous to the fact that there may not be any equilibrium of a game for some notions of equilibrium, there may be one, or there may be more than one.

3 The Main Results

Fix a game Γ in normal form. Let P nf i be the protocol that, in initial state sS ∈ ΣΓi , chooses strategy S; let ⃗ P nf = (P nf 1 , . . . , P nf n ). Let STRATi be the random variable on initial global states that associates with an initial global state s player i's strategy in r. As we said, Nash equilibrium arises in contexts with a common prior. Suppose that γ = (G0, μ) is a context with a common prior. We say that μ is compatible with the mixed joint strategy ⃗S if μ is the probability on pure joint strategies induced by ⃗S (under the obvious identification of initial global states with joint strategies).

Theorem 3.1: The joint strategy ⃗S is a Nash equilibrium of the game Γ iff there is a common prior probability measure μ on GΓ 0 such that STRAT1, . . . , STRATn are independent with respect to μ, μ is compatible with ⃗S, and ⃗ P nf implements EQNFΓ in the context (GΓ 0 , μ).

Proof: Suppose that ⃗S is a (possibly mixed strategy) Nash equilibrium of the game Γ. Let μ⃗S be the unique probability on GΓ 0 compatible with ⃗S. If ⃗S is played, then the probability of a run where the pure joint strategy (T1, . . . , Tn) is played is just the product of the probabilities assigned to Ti by Si, so STRAT1, . . . , STRATn are independent with respect to μ⃗S . To see that ⃗ P nf implements EQNFΓ in the context γ = (GΓ 0 , μ⃗S ), let ℓ = ri(0) be a local state such that r = R( ⃗ P nf , γ) and μ(r) ̸= 0. If ℓ = sT , then P nf i (ℓ) = T , so T must be in the support of Si. Thus, T must be a best response to ⃗S-i, the joint strategy where each player j ̸= i plays its component of ⃗S. Since i uses strategy T in r, the formula Bi(doi(T ′ )) holds at (r, 0) iff T ′ = T . Moreover, since T is a best response, if u is i's expected utility with the joint strategy ⃗S, then for all T ′ , the formula doi(T ′ ) ⪰ (EUi ≤ u) holds at (r, 0). Thus, (EQNFΓi )PS (ℓ) = T , where PS is the complete system extending R( ⃗ P nf , γ). It follows that ⃗ P nf implements EQNFΓ.

For the converse, suppose that μ is a common prior probability measure on GΓ 0 , STRAT1, . . . , STRATn are independent with respect to μ, μ is compatible with ⃗S, and ⃗ P nf implements EQNFΓ in the context γ = (GΓ 0 , μ). We want to show that ⃗S is a Nash equilibrium. It suffices to show that each pure strategy T in the support of Si is a best response to ⃗S-i. Since μ is compatible with ⃗S, there must be a run r such that μ(r) > 0 and ri(0) = sT (i.e., player i chooses T in run r). It since ⃗ P nf implements EQNFΓ , and in the context γ, EQNFΓ ensures that no deviation from T can improve i's expected utility with respect to ⃗S-i, it follows that T is indeed a best response.

As is well known, players can sometimes achieve better outcomes than a Nash equilibrium if they have access to a helpful mediator. Consider the simple 2-player game described in Figure 2, where Alice, the row player, must choose between top and bottom (T and B), while Bob, the column player, must choose between left and right (L and R):

Figure 2: A simple 2-player game.

It is not hard to check that the best Nash equilibrium for this game has Alice randomizing between T and B, and Bob randomizing between L and R; this gives each of them expected utility 2. They can do better with a trusted mediator, who makes a recommendation by choosing at random between (T, L), (T,R), and (B, L). This gives each of them expected utility 8/3. This is a correlated equilibrium since, for example, if the mediator chooses (T, L), and thus sends recommendation T to Alice and L to Bob, then Alice considers it equally likely that Bob was told L and R, and thus has no incentive to deviate; similarly, Bob has no incentive to deviate. In general, a distribution μ over pure joint strategies is a correlated equilibrium if players cannot do better than following a mediator's recommendation if a mediator makes recommendations according to μ. (Note that, as in our example, if a mediator chooses a joint strategy (S1, . . . , Sn) according to μ, the mediator recommends Si to player i; player i is not told the joint strategy.) We omit the formal definition of correlated equilibrium (due to Aumman [1974]) here; however, we stress that a correlated equilibrium is a distribution over (pure) joint strategies. We can easily capture correlated equilibrium using EQNF.

Theorem 3.2: The distribution μ on joint strategies is a correlated equilibrium of the game Γ iff ⃗ P nf implements EQNFΓ in the context (GΓ 0 , μ).

Both Nash equilibrium and correlated equilibrium require a common prior on runs. By dropping this assumption, we get another standard solution concept: rationalizability [Bernheim, 1984; Pearce, 1984]. Intuitively, a strategy for player i is rationalizable if it is a best response to some beliefs that player i may have about the strategies that other players are following, assuming that these strategies are themselves best responses to beliefs that the other players have about strategies that other players are following, and so on. To make this precise, we need a little notation. Let S-i = Πj̸=iSj. Let ui( ⃗S) denote player i's utility if the strategy tuple ⃗S is played. We describe player i's beliefs about what strategies the other players are using by a probability μi on S-i. A strategy S for player i is a best response to beliefs described by a probability μi on S-i(Γ) if ∑⃗ T ∈S-i ui(S, ⃗ T )μi( ⃗ T) ≥ ∑⃗ T ∈S-i ui(S ′ , ⃗ T )μi( ⃗ T) for all S ′ ∈ Si. Following Osborne and Rubinstein [1994], we say that a strategy S for player i in game Γ is rationalizable if, for each player j, there is a set Zj ⊆ Sj(Γ) and, for each strategy T ∈ Zj, a probability measure μj,T on S-j(Γ) whose support is Z-j such that

• S ∈ Zi; and
• for each player j and strategy T ∈ Zj, T is a best response to the beliefs μj,T .

For ease of exposition, we consider only pure rationalizable strategies. This is essentially without loss of generality. It is easy to see that a mixed strategy S for player i is a best response to some beliefs μi of player i iff each pure strategy in the support of S is a best response to μi. Moreover, we can assume without loss of generality that the support of μi consists of only pure joint strategies.

Theorem 3.3: A pure strategy S for player i is rationalizable iff there exist probability measures μ1, . . . , μn, a set G0 ⊆ GΓ 0 , and a state ⃗s ∈ G0 such that P nf i (si) = S and ⃗ P nf implements EQNFΓ in the context (G0, ⃗μ).

Proof: First, suppose that ⃗ P nf implements EQNFΓ in context (G0, ⃗μ). We show that for each state ⃗s ∈ G0 and player i, the strategy S⃗s,i = ⃗ P nf i (si) is rationalizable. Let Zi = {S⃗s,i : ⃗s ∈ G0}. For S ∈ Zi, let E(S) = {⃗s ∈ G0 : si = sS}; that is, E(S) consists consists of all initial global states where player i's local state is sS; let μi,S = μi(· | E(S)) (under the obvious identification of global states in G0 with joint strategies). Since ⃗ P nf implements EQNFΓ, it easily follows that S best response to μi,S. Hence, all the strategies in Zi are rationalizable, as desired.

For the converse, let Zi consist of all the pure rationalizable strategies for player i. It follows from the definition of rationalizability that, for each strategy S ∈ Zi, there exists a probability measure μi,S on Z-i such that S is a best response to μi,S. For a set Z of strategies, we denote by ˜ Z the set {sT : T ∈ Z}. Set G0 = ˜ Z1×. . .× ˜ Zn, and choose some measure μi on G0 such that μi(· | E(S)) = μi,S for all S ∈ Zi. (We can take μi = ∑S∈Zi αSμi,S, where αS ∈ (0, 1) and ∑S∈Zi αS = 1.) Recall that P nf i (sS) = S for all states sS. It immediately follows that, for every rationalizable joint strategy ⃗S = (S1, . . . , Sn), both ⃗s = (sS1 , . . . , sSn ) ∈ G0, and ⃗S = ⃗ P nf (⃗s). Since the states in G0 all correspond to rationalizable strategies, and by definition of rationalizability each (individual) strategy Si is a best response to μi,S, it is easy to check that ⃗ P nf implements EQNFΓ in the context (GΓ 0 , ⃗μ), as desired.

We remark that Osborne and Rubinstein's definition of rationalizability allows μj,T to be such that j believes that other players' strategy choices are correlated. In most of the literature, players are assumed to believe that other players' choices are made independently. If we add that requirement, then we must impose the same requirement on the probability measures μ1, . . . , μn in Theorem 3.3.

Up to now we have considered solution concepts for games in normal form. Perhaps the best-known solution concept for games in extensive form is sequential equilibrium [Kreps and Wilson, 1982]. Roughly speaking, a joint strategy ⃗S is a sequential equilibrium if Si is a best response to ⃗S-i at all information sets, not just the information sets that are reached with positive probability when playing ⃗S. To understand how sequential equilibrium differs from Nash equilibrium, consider the game shown in Figure 3.

One Nash equilibrium of this game has A playing downA and B playing acrossB. However, this is not a sequential equilibrium, since playing across is not a best response for B if B is called on to play. This is not a problem in a Nash equilibrium because the node where B plays is not reached in the equilibrium. Sequential equilibrium refines Nash equilibrium (in the sense that every sequential equilibrium is a Nash equilibrium) and does not allow solutions such as (downA, acrossB). Intuitively, in a sequential equilibrium, every player must make a best response at every information set (even if it is reached with probability 0). In the game shown in Figure 3, the unique joint strategy in a sequential equilibrium has A choosing acrossA and B choosing downB.

The main difficulty in defining sequential equilibrium lies in capturing the intuition of best response in information sets that are reached with probability 0. To deal with this, a sequential equilibrium is defined to be a pair ( ⃗S, β), consisting of a joint strategy ⃗S and a belief system β, which associates with every information set I a probability β(I) on the histories in I. There are a number of somewhat subtle consistency conditions on these pairs pairs; we omit them here due to lack of space (see [Kreps and Wilson, 1982; Osborne and Rubinstein, 1994] for details). Our result depends on a recent characterization of sequential equilibrium [Halpern, 2006] that uses nonstandard probabilities, which can assign infinitesimal probabilities to histories. By assuming that every history gets positive (although possibly infinitesimal) probability, we can avoid the problem of dealing with information sets that are reached with probaility 0.

To every nonstandard real number r, there is a closest standard real number denoted st (r), and read "the standard part of r": |r - st (r) | is an infinitesimal. Given a nonstandard probability measure ν, we can define the standard probability measure st (ν) by taking st (ν) (w) = st (ν(w)). A nonstandard probability ν on G0 is compatible with joint strategy ⃗S if st (ν) is the probability on pure strategies induced by ⃗S. When dealing with nonstandard probabilities, we generalize the definition of implementation by requiring only that ⃗ P performs the same actions as ⃗ Pg in runs r of ⃗ P such that st (ν) (r) > 0. Moreover, the expression "EUi = x" in EQEFΓ is interpreted as "the standard part of i's expected utility is x" (since x ranges over the standard real numbers).

Theorem 3.4: If Γ is a game with perfect recall 3 there is a belief system β such that ( ⃗S, β) is a sequential equilibrium of Γ iff there is a common prior nonstandard probability measure ν on GΓ 0 that gives positive measure to all states such that STRAT1, . . . , STRATn are independent with respect to ν, ν is compatible with ⃗S, and ⃗ P ef implements EQEFΓ in the standard context (GΓ 0 , ν).

This is very similar in spirit to Theorem 3.1. The key difference is the use of a nonstandard probability measure. Intuitively, this forces ⃗S to be a best response even at information sets that are reached with (standard) probability 0.

The effect of interpreting "EUi = x" as "the standard part of i's expected utility is x" is that we ignore infinitesimal differences. Thus, for example, the strategy ⃗ P ef i (⃗ s0) might not be a best response to ⃗S-i; it might just be an ϵ-best response for some infinitesimal ϵ. As we show in the full paper, it follows from Halpern's [2006] results that we can also obtain a characterization of (trembling hand) perfect equilibrium [Selten, 1975], another standard refinement of Nash equilibrium, if we interpret "EUi = x" as "the expected utility for agent i is x" and allow x to range over the nonstandard reals instead of just the standard reals.

3 These are games where players remember all actions made and the states they have gone through; we give a formal definition in the full paper. See also [Osborne and Rubinstein, 1994].

4 Conclusions

We have shown how a number of different solution concepts from game theory can be captured by essentially one knowledge-based program, which comes in two variants: one appropriate for normal-form games and one for extensiveform games. The differences between these solution concepts is captured by changes in the context in which the games are played: whether players have a common prior (for Nash equilibrium, correlated equilibrium, and sequential equilibrium) or not (for rationalizability), whether strategies are chosen independently (for Nash equilibrium, sequential equilibrium, and rationalizability) or not (for correlated equilibrium); and whether uncertainty is represented using a standard or nonstandard probability measure.

Our results can be viewed as showing that each of these solution concepts sc can be characterized in terms of common knowledge of rationality (since the kb programs EQNFΓ and EQEFΓ embody rationality, and we are interested in systems "generated" by these program, so that rationality holds at all states), and common knowledge of some other features Xsc captured by the context appropriate for sc (e.g., that strategies are chosen independently or that the prior). Roughly speaking, our results say that if Xsc is common knowledge in a system, then common knowledge of rationality implies that the strategies used must satisfy solution concept sc; conversely, if a joint strategy ⃗S satisfies sc, then there is a system where Xsc is common knowledge, rationality is common knowledge, and ⃗S is being played at some state. Results similar in spirit have been proved for rationalizability [Brandenburger and Dekel, 187] and correlated equilibrium [Aumann, 1987]. Our approach allows us to unify and extend these results and, as suggested in the introduction, applies even to settings where the game is not common knowledge and in settings where uncertainty is not represented by probability. We believe that the approach captures the essence of the intuition that a solution concept should embody common knowledge of rationality.