Preliminary and Incomplete.
Please Do Not Distribute.
Games with Segmented Knowledge:
Part II
Canonical Representation and Basic Properties
By
Zivan Forshner*
August 2007
Saturday, November 17, 2018
File: Gskcrbp005.doc
*TelHaiAcademicCollege
E-mail:
5.Canonical Representation of Games with Segmented Knowledge
In part I of this paper, an objective was set for this paper: to study – from a general equilibrium point of view – the notions of behavior adopted by a non-empty and denumerable collection of players playing in a collection of games whose payoffs belong to a non-denumerable set, where the collection of games contains all four states of information. In section 4 the observation hasbeen made that every game with segmented knowledge "sits on top" of a normal form game. Put differently, a collection of games with segmented knowledge (to be denoted ) is being put in a relation with a collection of normal form games (to be denoted ).This relation is in addition to the well known relation between normal form games and extensive form games. Recall that with every normal form game, there is at least one (and typically several) extensive form games which are associated with that normal form gameand hence a collection of normal form games (to be denoted ) is being put in a relation with a collection of extensive form games (to be denoted). If we take the two normal form collections to be the same collection of games (i.e. if ) then we get "triangles" consisted of three games, one of each game form. If the two normal form collections are not the same collection of games (i.e. if ) then we get "rectangles" (or higher polygons) consisted of four (or more) games. The latter situationsnecessarily correspond to swaps in games briefly discussed in part I of the paper, where the swap is conducted at the normal form level so one normal form game is replaced with another normal form game.In this framework, a typical rectangle is consisted of a game with segmented knowledge , an extensive form game and two normal form games and . In an environment in which players acquire information over time, the sequencing and evolution of the information is given by . Yet the "changes" in the normal form being conducted may be "minor" so a sense of continuity may be maintained. To state the obvious, if the changes conducted between the normal form games (i.e. in the transition from to ) are onlyin the payoffs and are "small", the continuity is relative to the usual topology on , where n is the number the players in the both and . However, changes in payoffs need neither be "small" nor need changes in thenormal form be confined to payoff, and all such changes need to be explored. This description is, of course very informal (and completely imprecise) because continuity requires a topology on games and – here – we are still very far from understanding these issues. Here my intension is to provide small teasers in order to give the reader a sense of direction were I am heading. At this stage of my discussion I shall focus on the triangles, and within the triangles, the a-priori interest is in triangles which correspond to – essentially - the same game. In contrast, in the four (or higher) dimensional polygons, I can be viewed as comparing "apples and oranges" because the normal form games in the polygons are different. That is, unless a sense of continuity can be maintained. By examining these three "layers" (i.e. a collection of games with segmented knowledge, a collection of normal form games and a collection of extensive form games), one can analyze the relationships between different information structures all being associated with the same normal form game. It is those relationships that I wish to analyze in the present sequence of papers.
Here – i.e. in part II of the paper - I shall make use of the first fact mentioned above. Namely, that any game with segmented knowledge "sits on top" of a normal form game,in order to obtain a different – yet equivalent – representation for games with segmented knowledge. The gain which I shall derive from the revised version of games with segmented knowledge is three fold: (i) The revised representation eases considerably the analysis of games with segmented knowledge; (ii) The revised representation has an endogenous information variable that literally pops out from the revised representation and can be used by players of games with segmented knowledge to measure their knowledge and lack of knowledge with respect to the rules of the game; (iii) The revised representation allows the possibility to understand "swaps" in games. Swaps in games are important for my general equilibrium objective because it allows for consideration of "game of games". In other words, it does allow for meta-games (or super-games) and allows their analysis. As is well known, a question often being asked in that relation is why can't we specify the meta-game as a game and analyze it directly?It is hard – at present - to provide a good answer to that question other than saying that unfortunately the meta-game need not be a game. To that response the question is always why can't it be a game? What is the problem of making it a game? These responds brings us right back to where we started. Namely, why can't we specify the meta-game as a game and analyze it directly? By considering "swaps in games"one is able to bypass the difficulties associated with a meta-game which is not a game, and retains a viable approach (unlike the former) of providing explanations for why the meta-game is not a game (if indeed it is not a game). One simply does not get to any such situation because the preliminary analysis conducted, has brought the analyzer to the conclusion that it is not in his interest to take action leading to unfavorable outcomes.
When one wishes to represent the knowledge structure of any game with segmented knowledge, it makes sense to use the integers 1 and0 in order to indicate knowledge (1) and lack of knowledge (0) on the players' part. At this stage, the fact pointed out implicitly by Harsanyi - and which wasmade explicitin theorem 3.2. –in which our collection of games can be taken to be –without loss of generality – a collection in which there can be no lack of knowledge on the players' part regarding who are the players which participate in the game, becomes very useful. As already discussed above, that part of the game can be taken to be fixed and so we are allowed to make usageof the idea that this part is known to the players of a game with segmented knowledge. In this way we do not need to know something directly but it suffices for our needs that the players of a game with segmented knowledge have this knowledge. It is a fact that there exist situations in which the knowledge that someone has a piece of information that allows somebody that does not have that piece of information to reach conclusions that would be impossible to reach otherwise (for an example of such case – other than two players sitting in a room wearing red hats and the village of betraying wives - see appendix A). Specifically, from the three elements that any game given in thenormal form of a gamespecifies (i.e. set of players, strategy sets and payoff functions), there is a need to specify the knowledgethat the players of the game have (or lack having)only about two elements. Namely, about strategy sets and about payoff functions. The gain is not associated with the reduction from a necessity to specify 3 elements to a sufficiency to specify only 2 elements but is embodied in the fact that the set of players is both fixed and known. Since no game has an empty set of players, the fact that the set of players is knownimplies that we have a non-emptyand known domain over which various mappings can be specified. Accordingly, I shall consider the specification of knowledge that every player has with respect to any player (including himself), as a mapping which maps the set of players of a given game into the "corners" of the (real) unit square. Equivalently, we can think on these points in the unit square as being the position (or location) of players in the (real) unit square. Thus, rather than mapping the players into the corners, one can think of players "sitting" idle in these corners throughout a game with segmented knowledge. A swap in games with segmented knowledge in this representation may be simply a "move" of some players from one corner to another corner. However, notall "swaps" in games can be so easily represented. There are, obviously, swaps in games that contain far more complicated changes in the game. The distinctive property is whether the changes are confined to the location of players in the corners or that there are changes in strategy sets or payoff functions (or both). If that occurs, the swap in games is associated with the normal form and a simple move from one corner to another corner will not suffice to represent such a swap in games. So, while I am aware that some swaps in games cannot be captured by simple changes, some swaps can. This point of view leads to the following definition.
Definition 5.1:Let G1 and G2 be two n-person games in normal form whose sets of players are equal. A swap in games from G1to G2 is said to be complexif there exist a player whose strategy set or payoff function (or both) have changed during the swap from G1 to G2. A swap in games from G1to G2 is said to be simple if no such player exist.
Four important observations must be made with respect to the above definition. First observe that the definition speaks about normal form games. Neither extensive form games nor games with segmented knowledge are considered by definition 5.1. Second observe that whenever a swap of games is simple, there is no actual change in the normal form. The two normal form games are equal to one another and in this case we set. Third observe that if a swap in games is complex, then and in this case it is impossible to have a common gameG. The most that one will be able to achieve is to have a game G which is being set to be equal to at most one of the games. Clearly, it is conceivable that an attempt to set a common game will end with a game which differs from bothG1 and G2. Fourth observe that it is up-front required by definition 5.1 to have the sameset of players. Note that same set of players implies not only in number but also in identity. Definition 5.1 does notconsider a swap in games which have different sets of players. The general rule is that this kindof swap goes together with a complex change in the game (i.e. a change in strategy sets or payoff function (or both)). Yet, one may be – perhaps – able to "trick" definition 5.1, if one has at his disposalidentical twins. In this case (when one of the twins is replaced by his brother) we can have two games whose sets of players are equal but not identical. However, as our experience indicates, such a "trick" is short lived. While almost all (if not all) identical twins use this trick once in a while, an extended period of time allows one to develop ways to distinguish between the twins, even if the twins did not give up on their tricks. In the game theoretic framework, an extended period of time means within the extensive form of a game.
It may initially seem that I picked up a strange place to define the concept of a swap in games. The concept uses normal form games, and if indeed the concept is to be useful, it seems reasonable to expect its introduction along with the introduction of normal form games (about 80 years old by now). That, obviously, did not occur. It did not occur exactly because the usefulness of the concept is very limited and if it is useful at all, than it is useful only in the context of games with segmented knowledge. Later it will be showed how one combines simple swaps (i.e. moves between corners of the (real) unit square) with complex swaps between games which cannot be represented using simple changes.For now my exposition will proceed in an orderly fashion. First, I shall describe and analyze games with segmented knowledge. Only later, shall I consider swap in games. For now, definition 5.1 is put aside and no usage of it will be made here (i.e. in part II of the paper).
I shall now move to describe the way knowledge regarding the normal form aspects of a game situation is represented in any game with segmented knowledge. The coordinates of the "corners" of the (real) unit square will refer to the knowledge a given player has regarding any player (including himself). Formally, the (real) unit square is given by . The order of the coordinates in the unit square is absolutely essential (at least as long as the real square is considered; later a complex unit square will be considered and there the order of the coordinates will be allowed to be arbitrary). Specifically, the origin denotes no knowledge regarding either the strategy set nor about the payoff function; denotes knowledge regarding the strategy set and lack of knowledge regarding the payoff function; denotes lack of knowledge regarding the strategy set and knowledge regarding the payoff function; finally denotes knowledge regarding both the strategy set as well as the payoff function. It is noted that in the corners (0,0) and (1,1) one is allowed to switch the coordinates without changing anything. In contrast this is not true for the corners (1,0) or (0,1). Formally, a game with segmented knowledge Λ can be described by a pair where is an n-person normal form game whose set of players is - where - and is a vector of mappings, whereevery map in maps players into corners of the (real) unit square. Formally, . The interpretation is that if – for example -, then player does not know player's strategy set but knows player's payoff function. The three other possibilities are interpreted similarly. Do observe that the "location" of any player is notabsolute in the sense that need not be equal to . There is, of course, no "problem"with player in any such situation, nor is it the case that player has the ability of being in two different locations at the same point of time. It is just that players know (or don't know) different things about player . Beyond that, since the game is a game with segmented knowledge, the usage of the term time is inappropriate.
The next step in the revised presentation of a game with segmented knowledge pertains to the vector of mappings . Here I shallreplace the vector of mappingswith a knowledge matrix denoted . The dimensions of knowledge matrix are , and its entries are either 0 or 1. Occasionally, I shall use the phrase that is a matrix over . By the time that this replacement is completed, the game with segmented knowledge Λ is represented by a pair where G is a normal form game and K is a knowledge matrix over {0,1}. When, and if, there is a need (or a wish) to point the fact that the transition from a given game with segmented knowledge Λ into the pair was done using the vector of mappings as described above, the notations will be used. Note that the transformation that a game with segmented knowledge Λ undergoes from the "shape" given by Λ to the shape given by , is completely technical. It does not alter the game nor does it alter the knowledge that the players of Λ have. The pair (or ) is called the canonical representation of a game with segmented knowledge.
I shall summarize the above procedure. The transformation which any game with segmented knowledge Λ undergoes when it is to be represented in the canonical representation of a game with segmented knowledge is carried out in steps. Given any game with segmented knowledge Λ, in the first step one "captures" the normal form game G. In the second step one identifies the set of players.[1] In the third step one uses the set of players of either Λ or G (these sets are identical) and builds the vector of mappings where . This is the point where the gain from the fact that the set of players is fixed and is known, is capitalized. Without this fact, we would be unable to build the mappings in the vector of mappings. During the third step, the normal form game is left untouched and one replaces the mappings into a knowledge matrix.In the forth step the vector of mappings is replaced by the knowledge matrix . When the forth step has been completed, a game with segmented knowledge Λ is represented by a pair where G is a normal form game and K is a knowledge matrix over {0,1}. The entire procedure starting with a given game with segmented knowledge Λ, up to the representation of Λ by its canonical form is brought by figure 1 below.
Insert here Figure 1
I shall comment here that if games with segmented knowledge are given in canonical form, a swap in games can now also be made at the incomplete information level, justifying the incomplete information. Previously, I briefly considered swaps in game at the normal form level; that is when we have a rectangle of games. Now it is in addition possible to conduct swaps in the games in the segmented knowledge level.
6.The Information Variable
In the canonical representation of a fixed game with segmented knowledge, each row of the knowledge matrix is associated with a player of Gor Λ (again, the two sets are equal) and the columns of alternate between strategy sets and payoff functions of the players of G. Furthermore, the rows and the columns of the knowledge matrix correspond to the "names" of the players and are ordered using the usual order on the set of natural numbers denoted by . The set of natural numbers must not be confused with the set of players N. The former is, of course, infinite while the latteris finite. Thus raw jof the knowledge matrix – where - represents the knowledge (lack of knowledge) of player j, where , regarding the normal form aspects of the players of G (including himself). Columns of the knowledge matrix also correspond to players yet here the relation is not as simple as was the case with the rows. Specifically, the first and second columns corresponds respectively to the strategy set and the payoff function of player 1, columns 3 and 4 corresponds respectively to the strategy set and the payoff function of player 2, columns 5 and 6 corresponds respectively to the strategy set and the payoff function of player 3 and so on up to columns and which corresponds respectively to the strategy set and the payoff function of playern. Since lack of knowledge regarding either of the strategy sets or payoff function (or both) is allowed with respect to every player, I move forward by not attaching any significance to any specific entry of the knowledge matrix.