1 Introduction
From the origin, games in extensive form have been formulated on a tree. In his seminal paper Extensive Games and the Problem of Information [7], Kuhn claimed that “The use of a geometrical model (…) clarifies the delicate problem of information”. This tells us that the proper handling of information was a strong motivation for Kuhn’s extensive games. On the game tree, moves are those vertices that possess alternatives, then moves are partitioned into players moves, themselves partitioned into information sets (with the constraint that no two moves in an information set can be on the same play). Kuhn mentions agents, one agent per information set, to “personalize the interpretation” but the notion is not central (to the point that his definition of perfect recall “obviates the use of agents”).
By contrast, in the socalled Witsenhausen’s intrinsic model [9, 10], agents play a central role. Each agent is equipped with a decision set and a field, and the same for Nature. Then, Witsenhausen introduces the product set and the product field. This product set hosts the agents’ information subfields. The Witsenhausen’s intrinsic model was elaborated in the control theory setting, in order to handle how information is distributed among agents and how it impacts their strategies. Although not explicitly designed for games, Witsenhausen’s intrinsic model had, from the start, the potential to be adapted to games. Indeed, in [9]
Witsenhausen places his own model in the context of game theory by referring to von Neuman and Morgenstern
[8], Kuhn [7] and Aumann [2].In this paper, we introduce a new representation of games that we call games in intrinsic form. Game representations play a key role in their analysis (see the illuminating introduction of the book [1]), and we claim that games in intrinsic form display appealing features. In the philosophy of the treebased extensive form (Kuhn’s view), the temporal ordering is hardcoded in the tree structure: one goes from the root to the leaves, making decisions at the moves, contingent on information, chance and strategies. For Kuhn, the time arrow (tree) comes first; information comes second (partition of the move vertices). By contrast, for Witsenhausen, information comes first; the time arrow comes (possibly) second, under a proper causality assumption contingent to the information structure.
Not having a hardcoded temporal ordering makes mathematical representations less constrained, hence more general. Moreover, Witsenhausen’s framework makes representations more intrinsic. As an illustration, let us consider a game where two players play once but at the same time. To formulate it on a tree requires to arbitrarily decide which of the two plays first. This is not the case for games in intrinsic form, where each player/agent is equipped with an information subfield and strategies that are measurable with respect to the latter; writing the system of two equations that express decisions as the output of strategies leads to a unique outcome, without having to solve one equation first, and the other second.
The tree representation of games has its pros and cons. On the one hand, trees are perfect to follow step by step how a game is played as any strategy profile induces a unique play: one goes from the root to the leaves, passing from one node to the next by an edge that depends on the strategy profile. On the other hand, in games with information, information sets are represented as “union” of tree nodes that must satisfy restrictive axioms, and such unions do not comply in a natural way with the tree structure, which can render the game analysis delicate [1, 4, 5]. By contrast, the notion of Witsenhausen’s intrinsic games (Wgames) does not require an explicit description of the play temporality, and the intrinsic form replaces the tree structure with a product structure, more amenable to mathematical analysis. If the introduction of the model may seem involved, we argue that the resulting structure is a powerful mathematical tool, because there are many situations in which it is easier to reason and discuss with mathematical formulas than with trees.
We illustrate our claim with a proof of the celebrated Kuhn’s equivalence theorem for games in intrinsic form. Indeed, as a first step in a broader research program, we show that equivalence between mixed and behavioral strategies holds under perfect recall for Wgames. More precisely, our proof relies on an equivalence between behavioral, mixed and a new notion of productmixed strategies. These latter form a subclass of mixed strategies. In the spirit of [2], in a productmixed strategy, each agent (corresponding to time index in [2]) generates strategies from a random device that is independent of all the other agents. We prove that, under perfect recall for Wgames, any mixed strategy of a player is not only equivalent to a behavioral strategy, but also to a productmixed strategy where all the agents under control of the player randomly select their pure strategy independently of the other agents.
The paper is organized as follows. In Sect. 2, we present the finite version of Witsenhausen’s intrinsic model. Then, in Sect. 3, we propose a formal definition of games in intrinsic form (Wgames), and then discuss three notions of “randomization” of pure strategies — mixed, productmixed and behavioral. Finally, we derive an equivalent of Kuhn’s equivalence theorem for games in intrinsic form in Sect. 4. In Appendix A, we present background material on fields, atoms and partitions, as these notions lay at the core of Witsenhausen’s intrinsic model in the finite case. In all the paper, we adopt the convention that a player is female (hence using “she” and “her”), whereas an agent is male (“he”, “his”).
2 Witsenhausen’s intrinsic model (the finite case)
In this paper, we tackle the issue of information in the context of finite games. For this purpose, we will present the socalled intrinsic model of Witsenhausen [10, 6] but with finite sets rather than with infinite ones as in the original exposition. We refer the reader to Appendix A for background material on fields, atoms and partitions.
In §2.1, we present the finite version of Witsenhausen’s intrinsic model, where we highlight the role of the configuration field that contains the information subfields of all agents. In §2.2, we illustrate, on a few examples, the ease with which one can model information in strategic contexts, using subfields of the configuration field. Finally, we present in §2.3 the notions of solvability and causality.
2.1 Finite Witsenhausen’s intrinsic model (Wmodel)
We present the finite version of Witsenhausen’s intrinsic model, introduced some five decades ago in the control community [9, 10].
A finite Wmodel is a collection , where

is a finite set, whose elements are called agents;

is a finite set which represents all uncertainties; any is called a state of Nature; is the complete field over ;

for any , is a finite set, the set of decisions for agent ; is the complete field over ;

for any , is a subfield of the following product field
(1) and is called the information field of the agent .
The configuration space is the product space (called hybrid space by Witsenhausen, hence the notation)  
(2a)  
As all fields and are complete, the product configuration field  
(2b)  
is also the complete field of . A configuration is denoted by  
(2c) 
In lieu of the information field in (1), it will be convenient to consider the equivalence relation , on the configuration space , defined in such a way that the equivalence classes coincide with the atoms of , that is, with the elements of the partition in (33):
(3) 
Thus defined, the subset is the unique atom in that contains the configuration .
We will need the following equivalent characterization of measurable mappings, which is a slight reformulation of [6, Proposition 3.35].
(adapted from [6, Proposition 3.35]) Let be a mapping, where is a set and is a field over . We suppose that the field contains all the singletons. Then, for any agent , the following statements are equivalent:
(4a)  
(4b)  
(4c) 
In any of these equivalent cases, we say that the mapping is measurable, and, for all , we denote by the unique element of in , that is,
(5) 
Then, using the extended notation above (3), we have the property
(6) 
Now that we have explicited measurable mappings with respect to agents information subfields, we introduce the notion of pure Wstrategy.
([9, 10]) A pure Wstrategy of agent is a mapping
(7a)  
from configurations to decisions, which is measurable with respect to the information field of agent , that is,  
(7b) 
We denote by the set of all pure Wstrategies of agent . A pure Wstrategies profile is a family  
(8a)  
of pure Wstrategies, one per agent . The set of pure Wstrategies profiles is  
(8b) 
Condition (7b) expresses the property that any (pure) Wstrategy of agent may only depend upon the information available to the agent.
In what follows, we will need some notations. For any nonempty subset of agents, we define
(9a)  
(9b)  
(9c)  
(9d) 
2.2 Examples
We illustrate, on a few examples, the ease with which one can model information in strategic contexts, using subfields of the configuration field. Even if we have presented the finite version of Witsenhausen’s intrinsic model in §2.1, we take the opportunity here to show its potential to describe infinite decision and Nature sets.
Sequential decisions Suppose an individual has to take decisions (say, an element of ) at every discrete time step in the set^{3}^{3}3For any integers , denotes the subset . , where is an integer. The situation will be modeled with (possibly) Nature set and field , and with agents in , and their corresponding sets, , and fields, (the Borel field of ), for . Then, one builds up the product set and the product field . Every agent is equipped with an information field . Then, we show how we can express four information patterns: sequentiality, memory of past information, memory of past actions, perfect recall. The inclusions , for , express that every agent can remember no more than his past actions (sequentiality); memory of past information is represented by the inclusions , for ; memory of past actions is represented by the inclusions , for ; perfect recall is represented by the inclusions , for .
To represent players — each of whom makes a sequence of decisions, one for each period — we use agents, labelled by . With obvious notations, the inclusions express memory of one’s own past information, whereas the inclusions , express memory of all players past actions.
PrincipalAgent models
A branch of Economics studies socalled PrincipalAgent models with two decision makers (agents) — the Principal (leader) who makes decisions , where the set is equipped with a field , and the Agent (follower) who makes decisions , where the set is equipped with a field — and with Nature, corresponding to private information (or type) of the Agent , taking values in a set , equipped with a field .
Hidden type (leading to adverse selection or to signaling) is represented by any information structure with the property that, on the one hand,
(10) 
that is, the Principal does not know the Agent type, but can possibly observe the Agent action, and, on the other hand, that
(11) 
that is, the Agent knows the state of nature (his type).
Hidden action (leading to moral hazard) is represented by any information structure with the property that, on the one hand,
(12) 
that is, the Principal does not know the Agent action, but can possibly observe the Agent type and, on the other hand, that the inclusion (11) holds true, that is, the agent knows the state of nature (his type).
Stackelberg leadership model In Stackelberg games, the leader makes a decision — based at most upon the partial observation of the state of Nature — and the the follower makes a decision — based at most upon the partial observation of the state of Nature , and upon the leader decision . This kind of information structure is expressed with the following inclusions of fields:
(13) 
Even if the players are called leader and follower, there is no explicit time arrow in (13). It is the information structure that reveals the time arrow. Indeed, if we label the leader as (first player) and the follower as (second player), the inclusions (13) become the inclusions , and : the sequence of information fields is “adapted” to the filtration . But if we label the leader as and the follower as , the new sequence of information fields would not be “adapted” to the new filtration. It is the information structure that prevents the follower to play first, but that makes possible the leader to play first and the follower to play second.
2.3 Solvability and causality
In the Kuhn formulation, Witsenhausen says that “For any combination of policies one can find the corresponding outcome by following the tree along selected branches, and this is an explicit procedure” [9]. In the Witsenhausen formulation, there is no such explicit procedure as, for any combination of policies, there may be none, one or many solutions to the closedloop equations; these equations express the decision of one agent as the output of his strategy, supplied with Nature outcome and with all agents decisions. This is why Witsenhausen needs a property of solvability, whereas Kuhn does not need it as it is hardcoded in the tree structure. Then, Witsenhausen defines the notion of causality (which parallels that of tree) and proves in [9] that solvability holds true under causality. Yet, in [9, Theorem 2], Witsenhausen exhibits an example of noncausal Wmodel that is solvable.
2.3.1 Solvability
With any given pure Wstrategies profile we associate the setvalued mapping
(14)  
With this definition, we slightly reformulate below how Witsenhausen introduced the property of solvability.
Thus, under the solvability property, for any state of nature , there exists one, and only one, decision profile which is a solution of the closedloop equations
(15a) 
In this case, we define the solution map
(15b) 
as the unique element contained in the image set that is, for all , .
2.3.2 Configurationorderings
In his articles [9, 10], Witsenhausen introduces a notion of causality that relies on suitable configurationorderings. Here, we introduce our own notations, because they make possible a compact formulation of the causality property and, later, of perfect recall.
For any finite set , let denote the cardinal of . Thus, denotes the cardinal of the set , that is, is the number of agents. For , let denote the set of orderings, that is, injective mappings from to :  
(16a)  
The set is the set of total orderings of agents in , that is, bijective mappings from to (in contrast with partial orderings in for ). For any , any ordering , and any integer , is the restriction of the ordering to the first integers. For any , there is a natural mapping  
(16b)  
which is the restriction of any (total) ordering of to . We define the set of orderings by  
(16c)  
For any , and any ordering , we define the range of the ordering as the subset  
(16d)  
the cardinal of the ordering as the integer  
(16e)  
the last element of the ordering as the agent  
(16f)  
the restriction of the ordering to the first elements  
(16g) 
With the notations introduced, any ordering can be written as , with the convention that when .
([9, 10]) A configurationordering is a mapping from configurations towards total orderings. With any configurationordering , and any ordering , we associate the subset of configurations defined by
(17) 
By convention, we put . Along each configuration , the agents are ordered by . The set in (17) contains all the configurations for which the agent is acting first, the agent is acting second, …, till the last agent acting at stage .
2.3.3 Causality
In his article [9], Witsenhausen introduces a notion of causality and he proves that causal systems are solvable.
The following definition can be interpreted as follows. In a causal Wmodel, there exists a configurationordering with the following property: when an agent is called to play — as he is the last one in an ordering — what he knows cannot depend on decisions made by agents that are not his predecessors (in the range of the ordering under consideration).
([9, 10]) A Wmodel (as in Definition 2.1) is causal if there exists (at least) one configurationordering with the property that
(18) 
Otherwise said, once we know the first agents, the information of the (last) agent depends at most on the decisions of the (previous) agents in the range . In (18), the subset of configurations has been defined in (17), the last agent in (16f), the partial ordering in (16g), the range in (16d), and — using the definition (9b) of the subfield of , with the subset of agents defined in (16g) and (16d) — the subfield of is
(19) 
Witsenhausen’s intrinsic model deals with agents, information and strategies, but not with players and preferences. We now turn to extending the Witsenhausen’s intrinsic model to games.
3 Finite games in intrinsic form
We are now ready to embed Witsenhausen’s intrinsic model into game theory. In §3.1, we introduce a formal definition of a finite game in intrinsic form (Wgame), and in §3.2 we introduce three notions of “randomization” of pure strategies — mixed, productmixed and behavioral. In §3.3, we discuss relations between productmixed and behavioral Wstrategies.
In what follows, when is a finite set, we denote by
the set of probability distributions over
. When needed, the set can be equipped with the Borel topology and the Borel field, as is homeomorphic to the simplex of , and is thus homeomorphic to a closed subset of a finite dimensional space.3.1 Definition of a finite game in intrinsic form (Wgame)
We introduce a formal definition of a finite game in intrinsic form (Wgame).
A finite Wgame , or a finite game in intrinsic form, is a made of

a family , where the set of players is finite, of two by two disjoint nonempty sets whose union is the set of agents; each subset is interpreted as the subset of executive agents of the player ,

a finite Wmodel , as in Definition 2.1,

for each player , a preference relation on the set of mappings .
A finite Wgame is said to be solvable (resp. causal) if the underlying Wmodel is solvable as in Definition 15b (resp. causal as in Definition 2.3.3).
We comment on the preference relations on the set of mappings . Our definition covers (like in [3]) the most traditional preference relation , which is the numerical expected utility preference. In this latter, each player is endowed, on the one hand, with a criterion (payoff), that is, a measurable function , and, on the other hand, with a belief, that is, a probability distribution over the states of Nature . Then, given , , one says that if
Note also that the Definition 3.1 includes Bayesian games, by specifying a product structure for — where some factors represent types of players, and one factor represents chance — and by considering additional probability distributions.
3.2 Mixed, productmixed and behavioral strategies
We introduce three notions of “randomization” of pure strategies: mixed, productmixed and behavioral.
The notion of mixed strategy comes from the study of games in normalized form, where each player has to select a pure strategy, the collection of which determines a unique outcome. If we allow the players to select their pure strategy at random, the lottery they use is called a mixed strategy. For an extensive game, a mixed strategy can be interpreted in the following sense. First, the player selects a pure strategy using the lottery. Second, the game is played. When the player is called by the umpire, she plays the action specified by the selected pure strategy for the current information set.
Observe that there is only one dice roll per player. This dice roll determines the reactions of the player for every situation of the game. It would be more natural to let the player roll a dice every time she has to play, leading to the notion of behavioral strategy.
A fundamental question in game theory is to identify settings in which those two views (mixed strategy and behavioral strategy) are equivalent. To formulate this question in the Wgame framework, we will give formal definitions of these two notions of randomization. We will also add a third one, that we call productmixed strategy, and which is in the spirit of Aumann [2], as each agent (corresponding to time index in [2]) “generates” strategies from a random device that is independent of all the other agents.
3.2.1 Mixed Wstrategies
For any agent , the set of pure Wstrategies for agent (see Definition 2.1) is finite, hence the set of probability distributions over is is homeomorphic to , the simplex of , and is thus homeomorphic to a closed subset of a finite dimensional space. So is the space of probability distributions over the set of pure Wstrategies profiles. We will also consider the sets
(20) 
of pure Wstrategies profiles, player by player, and the set of probability distributions over .
We consider a finite Wgame, as in Definition 3.1. A mixed Wstrategy for player is an element of , the set of probability distributions over the set in (20) of Wstrategies of the executive agents in . The set of mixed Wstrategies profiles is . A mixed Wstrategies profile is denoted by  
(21a)  
and, when we focus on player , we write  
(21b) 
We consider a solvable finite Wgame (see Definition 3.1), and a mixed Wstrategies profile as in (21a). For any , we denote by  
(22a)  
the pushforward probability, on the space of the product probability distribution on by the mapping  
(22b)  
where is the solution map (15b), which exists by the solvability assumption. 
By (15a), which defines the solution map, and by definition of a pushforward probability, we have, for any configuration ,
3.2.2 Productmixed Wstrategies
In a mixed Wstrategy, the executive agents of player can be correlated because the probability in Definition 21 is a joint probability on the product space . We now introduce productmixed Wstrategies, where the executive agents of player are independent in the sense that the probability is the product of individual probabilities, each of them on the individual space of the strategies of one agent .
3.2.3 Behavioral Wstrategies
We formalize the intuition of behavioral strategies in Wgames by the following definition of behavioral Wstrategies.
We consider a finite Wgame, as in Definition 3.1. A behavioral Wstrategy for player is a family , where
(23) 
is an measurable stochastic kernel for each , that is, if one of the two equivalent statements holds true:

on the one hand, the function is measurable, for any and, on the other hand, each is a probability distribution on the finite set , for any ,

on the one hand, , for any and, on the other hand, for any , we have , , and .
The equivalences come from the fact that the sets and are finite and equipped with their respective complete fields, and by Proposition 2.1, and especially (4b).
3.3 Relations between productmixed and behavioral Wstrategies
Here, we show that productmixed and behavioral Wstrategies are “equivalent” in the sense that a productmixed Wstrategy naturally induces a behavioral Wstrategy, and that a behavioral Wstrategy can be “realized” as a productmixed Wstrategy (see Figure 1).
From productmixed to behavioral Wstrategies
We prove that a productmixed Wstrategy naturally induces a behavioral Wstrategy.
We consider a finite Wgame, as in Definition 3.1, and a player .
For any productmixed Wstrategy , as in Definition 3.2.2, we define, for any agent ,
(24) 
Then, is a behavioral Wstrategy, as in Definition 3.2.3.
Proof.
Let be given a productmixed Wstrategy .
To prove that (24) defines a behavioral Wstrategy, we have to show (see Item 1 in Definition 3.2.3), on the one hand, that the function is measurable, for any and, on the other hand, that each is a probability on the finite set , for any . For this purpose, we will use the more practical characterization of Item 2 in Definition 3.2.3.
Let us fix . Let be such that , where we recall that the classes of the equivalence relation in (3) are exactly the atoms in . By (6), we have that . Therefore, from the expression (24), we have obtained that , hence that the function is measurable, by Proposition 2.1, and especially (4b).
By the expression (24), we have that , and, since is a probability on , that .
This ends the proof. ∎
From behavioral to productmixed Wstrategies
We prove that a behavioral Wstrategy can be “realized” as a productmixed Wstrategy.
We consider a finite Wgame, as in Definition 3.1, and a player .
Comments
There are no comments yet.