Article is dedicated to the multigrammatical modelling of games. Basic notions and definitions, concerning multisets and multiset grammars, are considered. So called resourcebased games are introduced, and representation of their simplest class - antagonistic resourcebased games - by filtering multiset grammars is considered in details. More sophisticated cooperative and coalitional resource-based games are proposed. Directions of further development of resource-based games by application of multigrammatical framework are discussed.
Substantial background of any kind of conflict between sociotechnological systems (STS), every of which includes people and technological devices, is that both opposing sides possess some amounts of resources (called usually their “resource bases”, RB), and goals of both are to eliminate (destroy) or capture resources of the counterpart, spending for this purpose some adequate amounts of its own resources. So logics of any counterpart behavior at any moment is defined by current resources he possesses and possible actions he may perform, spending some part of his own RB for eliminating/capturing of some part of RB of the opponent. Thus conflict is implemented as a chain of sequentially made actions (mutual impacts) of opponents until it is possible. Problem of planning of behavior of opponents during conflict is to determine such sequence of actions (“strategy”), leading to the end of the conflict (i.e. final resource bases of the players), which meets goals of both or at least one of the opponents, who is declared winner. Such conflicts are called below resource-based (RBC).
Conflicts of any nature and scale are objects of the game theory (GT), which is one of the most valuable and usable parts of modern operations research, providing decision makers by clear, simply applied and effectively algorithmically implemented methodology of strict mathematical representation of logics of action of opposing subjects [1, 2, 3].
However, despite widespread and commonly understood essence of the described resource-based conflicts, GT state of the art is such, that available mathematical tools, used nowadays by GT developers, are not exactly suitable for completely adequate mathematical formalization of such conflicts, because application of these tools demands explicit representation of sets of possible implementations of conflicts in a form of trees, matrices or automata. By this, dimensionalities of practically interest representations of RBC are so large, and time, necessary for their construction, so long, that in most cases it is very hard or even impossible to apply known GT approaches to the adequate modelling of real RBC.
Alternative approach, which consideration in the context of RBC may have evident reasons, have raised from the artificial intelligence area. It differs from GT by basic representation of the potential activities of the opposing sides and possible ways of application of their capabilities during conflict. This approach is called “multi-agent” [4, 5, 6], following that every STS is represented as a set of active entities, called agents, operating independently in accordance with their internal logics. Interactions between agents are implemented in full accordance with set of a priori established mutual agreements, providing resolution of current situations and constructing consequences of the aforementioned interactions. Agents form multi-agent system (MAS) [7, 8, 9].
In comparison with modern GT models, MAS do not demand explicit representation of action of the opposing sides during conflict. It is sufficient to define implicitly logics of action of all agents, entering MAS, and to construct the initial state of this MAS, i.e. set of initial states of its agents. All further behavior of the modelled STS until some final state will be explicated by MAS itself [13, 14, 15, 16].
Being in some sense more advanced approach in comparison with classical GT frameworks, multiagent technologies (MAT) usually do not operate notions of strict optimality and optimal strategies in the sense of game theory, and in most cases implement “what-if” regimes, providing heuristic-based assessment of very limited number of all possible consequences of decisions made by the opposing sides.
In order to integrate best features of both GT- and MAT-centered technologies of modelling resource-based conflicts, a new approach to representation and solution of such conflicts is proposed in this article. Its basic notion is “resource-based game” (RBG), and its mathematical background is theory of recursive multisets, which basic mathematical toolkit are multiset grammars (MG) [17, 18, 19, 20, 21, 22]. This toolkit is result of deep integration in one multiset-based formalism key advantages of classical operations research (strict mathematical definition and correct algorithmic availability of provably optimal solutions) and modern knowledge engineering (generality, simplicity and flexibility of problems representation). This article is introduction to the theory of RBG, which main nowadays application is economical combinatorics.
Section 2 contains main definitions and notions of the theory of recursive multisets, necessary for further considerations. Resource-based antagonistic games are introduced in Section 3, while resourcebased cooperative and coalitional games – in Section 4. Directions of further research in the RBG area are discussed in the conclusion.
A background of classical theory of sets is notion of set as an unordered collection of mutually distinguishable elements. Theory of multisets is based on the assumption, that aforementioned collection may contain identical (indistinguishable) elements: | | = ∑ , =1 and this is recorded as = {⏟1, . . . , 1 , . . . , ⏟ , . . . , , . . . , ⏟ , . . . , }, 1
= { 1 ⋅ 1, . . . , ⋅ }, where v is called multiset, – objects, – multiplicities of objects, and ⋅ – multiobjects (MO), = 1, . . . , . Number | | = , being quantity of MO in MS , is called it’s dimensionality, while number (1) (2) (3) is called power of MS v. Following (2), multiset may be considered as a set of multiobjects, and, from the substantial point of view, multiset {1 ⋅ 1, . . . ,1 ⋅ } and set { 1, . . . , } mean one and the same collection. Set { 1, . . . , } is called basis of MS v and is denoted ( ). Empty multiset as well as empty set is denoted { }.
{ 1 ⋅ 1, . . . , ⋅ , 0 ⋅ +1} = { 1 ⋅ 1, . . . , ⋅ }.
Fact, that object enters MS , or, just the same, MS includes object , is denoted ∈ . Symbol “∈” is also used to denote, that MO ⋅ enters MS (MS includes MO ⋅ ): ⋅ ∈ . Structure of the left operand determines what kind of relation is denoted in every particular case. Similarly, symbol “∉” is used to de-note, that object (multiobject ) does not enter multiset . Due to (4), ∉ and 0 ⋅ ∈ are equivalent.
Two main relations on multisets – inclusion (“⊆”) and strict inclusion (“⊂”) – are defined as follows. MS is included to MS ′, if
(∀ ⋅ ∈ )(∃ ′ ⋅ ∈ ′) ≤ ′, i.e. for every multiobject ⋅ entering MS there exist multiobject ′ ⋅ , which multiplicity ′ is not less than . There may be also ′ ⋅ ′ ∈ ′ such that ′ ∉ (this does not contradict (5), because 0 ⋅ ′ ∈ and 0 < ′). If ⊆ ′ and ≠ ′, then MS is strictly included to MS ′, that is denoted ⊂ ′. MS , which is included to MS ′, is called submultiset of MS ′; MS , which is strictly included to MS ′, is called strict submultiset of MS ′.
Let us illustrate introduced notions by the following example, where objects will be represented by strings in brackets. This same notation will be used in all examples, having place in this chapter.
= {3 ⋅ (eur), 5 ⋅ (usd), 10 ⋅ (rur)}, ′ = {6 ⋅ (eur), 5 ⋅ (usd), 15 ⋅ (rur)}.
As seen, according to (5), ⊆ ′ and ⊂ ′.∎
As it is known from [23, 24], multiplicities may be not only non-negative integer, but also nonnegative rational numbers. Three main operations on multisets are multiplication by a constant, addition, and subtraction, which are denoted by bold symbols ∗, + and − respectively. Semantics of these operations is defined by use of the well-known set-theoretical operations (join and intersection), as well as of the arithmetic operations:
∗ { 1 ⋅ 1, . . . , ⋅ } = {( × 1)⋅ 1, . . . , ( × )⋅ }, where “×” denotes multiplication of integer numbers; + ′ = ⋃{( + ′)∙ }, ∈ ( )∪ ( ′) ∙ ∈ ′∙ ∈ − ′ = ⋃{( − ′)⋅ }.
⋅ ∈ (4) (5) (6) (7) (8)
Along with these operations, there will be used set-theoretical operations on multisets – join and intersection, – denoted respectively by bold symbols ∪ and ∩, different from ∪ and ∩: ′ ⋅ ∈ ′
> ′ ∙ ∈ ′∙ ∈ ∙ ∈ ′∙ ∈ ∪ ′ = ⋃{max{ , ′} ∙ },
∈ ( )∪ ( ′) ∩ ′ = ⋃{min{ , ′} ∙ }
∈ ( )∪ ( ′)
Example 2. Let v and ′ be as in the Example 1. Then 3 ∗ = {9 ⋅ (eur), 15 ⋅ (usd), 30 ⋅ (eur)}, + ′ = {9 ⋅ (eur), 10 ⋅ (usd), 25 ⋅ (rur)}, − ′ = { }, ′ − = {3 ⋅ (eur), 5 ⋅ (rur)}, ∪ ′ = {6 ⋅ (eur), 5 ⋅ (usd), 15 ⋅ ( ∩ ′ = {3 ⋅ (eur), 5 ⋅ (usd), 10 ⋅ (rur)} = ,
)}, because ⊂ ′. ∎
All described operations are well known from theory of multisets [23, 24]; their common feature is that their operands are multisets. The following operation called “filtration” has set of multisets (SMS) as the first operand and set of conditions called “filter” as the second operand. Filtration is denoted as ↓ , where is filtrated SMS, “↓” – symbol of operation, and is filter.
may be boundary and optimizing.
, where ∈ {>, <, ≥, ≤, =}. Multiset satisfies BC
if ⋅ ∈ , and
is true (as everywhere, ∉ is equivalent to 0 ⋅ ∈ ).
Let ≤ = { 1, . . . , } be a filter, containing only boundary conditions. =1 ↓ ≤ = ⋂( ↓ { }).
1 = {3 ⋅ (eur), 5 ⋅ (rur)}, 2 = {7 ⋅ (usd), 9 ⋅ (rur)}, 3 = {4 ⋅ (eur), 11 ⋅ (usd), 15 ⋅ (rur)}, = { 1, 2, 3}, where and
≤ = {(usd)> 3, (rur)≤ 10}. ↓ ≤ = ( ↓ {(usd)> 3})∩ ( ↓ {(rur)≤ 10})= { 2, 3} ∩ { 1, 2} = { 2}. ∎ (9) (10) (11) Optimizing condition (OC) is written = , where ∈ { , }. Multiset ∈ satisfies OC = max, if ⋅ ∈ , and all ′ ∈ − { } satisfy boundary condition ≤ . Similarly, multiset ∈ satisfies OC = min, if ⋅ ∈ , and all ′ ∈ − { } satisfy boundary condition ≥ . = { 1, . . . , } be a filter, containing only optimizing conditions. Then, similarly to (6), (12) (13) (14) (15) (16) (17) i.e. result of filtering set of multisets by filter is obtained by application of boundary subfilter ≤ to , and then resulting SMS is filtered by optimizing subfilter . This substantial interpretation of SMS filtering is a background for multiset representation of classical problems of operations research [17, 18]. On the other hand, it is clear, that language of filters is very close to query languages, providing access to the relational and relational-like databases [25, 26].
Introduced operations on multisets and sets of multisets make it possible to define syntax and semantics of family of multiset grammars. It’s background is notion of multiset grammar as a couple = ⟨ 0, ⟩, where 0 is multiset, and R is a finite set of rules; 0 is called kernel, and R is called scheme. The set of all objects used in kernel and scheme of MG S is denoted . Rule ∈ is a construction is divider. application to ̄is multiset
= ↓ {(usd)= max})( ↓ {(rur)= min})= { 3} ∩ { 1} = { }. ∎
→ ′, ̅′ = ̅− + ′ ̄ ⇒ ̅′
↓ then Example 4. Let be the same as in the Example 3, and = {(usd)= max,(rur)= min}.
=1 ↓
= ⋂( ↓ { }). = ≤ ∪
, ↓ = ( ↓ ≤)↓ , where multisets and ′ are called left part and right part of the rule respectively, ≠ { }, and “→”
Application of the rule to the multiset ̄ is defined as follows. If ⊆ ̄, then the result of i.e., speaking informally,
MS v, which is submultiset of
MS ̄, is replaced by
follows: and it is said, that MS ̅′ is generated from MS ̄by application of rule . If left part is not submultiset of MS ̄, result of application to ̄is assumed empty MS { }.
Recursive definition of set of multisets, generated by application of multigrammar = ⟨ 0, ⟩, is as ( +1) = ( )∪ ( ⋃ ⋃ { ̅′ | ̄ ⇒ ̅′})
(0) = { 0},
̄∈ ( ) ∈
= (∞). = ⋃ ( ), ∞
As seen, includes all multisets, which may be generated from MS 0 by sequential application of rules ∈ , and is nothing but fixed point of the sequence (0), (1), . . . , ( ), . . ., so and in general case may be infinite.
If MS ̅′ may be generated from MS ̄by application of scheme R, it is denoted so, from this point of view,
Multiset ̄ ∈ is called terminal multiset (TMS), if
= { ̄| 0 ⇒ ̄}. (∀ ∈ ) ̄ ⇒ { }, (18) (19) (20) (21) (22) (23) (24) (25) i.e. no any rule ∈ may be applied to ̄. Set of terminal multisets (STMS) generated by application of multiset grammar is denoted ̄ . Obviously, Example 5. Let = ⟨ 0, ⟩, where 0 = {5 ⋅ (eur), 7 ⋅ (usd), 4 ⋅ (rur)}, and
= { 1, 2}, where 1 is {3 ⋅ (eur)} → {4 ⋅ (usd)}, and 2 is {3 ⋅ (usd), 2 ⋅ (rur)} → {2 ⋅ (eur)}.
According to (18) – (19), (0) = {{5 ⋅ (eur), 7 ⋅ (usd), 4 ⋅ (rur)}}, exchanged to 2 euros). ∎ (1) = (0)∪ {{2 ⋅ (eur), 11 ⋅ (usd), 4 ⋅ (rur)}, {7 ⋅ (eur), 4 ⋅ (usd), 2 ⋅ (rur)}}, As seen, this MG provides generation of all possible collections of euros, dollars, and rubles, which may be obtained from the initial collection 0 by sequential currency exchanges, which parameters are fixed by rules 1 and 2 (3 euros may be exchanged to 4 dollars, while 3 dollars and 2 rubles may be
Generalizing introduced notions, we may affirm, that multiset grammars have the same conceptual background, as classical string-operating grammars, proposed by N. Chomsky [27]. Despite primary elements, which are processed (multisets and strings), differ, the key logical construction of both formalisms – generation of new elements from already generated by replacement of their parts according to the applicable rules – is the same. Chomsky grammars are used for generation of sets of strings (“sentential forms”) until sentences of language, while multiset grammars provide generation of sets of multisets until terminal MS. Due to the fact, that multiobjects contain both numerical and symbolic components (multiplicities and object names), generation of multisets incorporates numerical computation, that provides a lot of new opportunities for simple formalizing and effective solution of various practical problems with combinatorial background. To implement such opportunities, so called filtering multiset grammars were proposed in [17, 18]. FMG are such generalization of MG, that integrate two basic concepts – generation of set of multisets and selection from it such MS, that satisfy some logical conditions, joined to filter.
Filtering multiset grammar is a triple is a filter, including boundary and optimizing conditions, defining multisets, which would be selected from set of terminal MS, generated by MG ⟨ 0, ⟩, i.e.
= ⟨ 0, , ⟩, where 0 and are kernel and scheme, while = 〈 0, 〉 ↓ . (26) Verbally, is subset of 〈 0, 〉 , which includes only such elements of this set, that satisfy filter F. = {(eur)> 7, (rur)= min}, that means ̅ Example 6. Consider = ⟨ 0, , ⟩, where 0 and are the same, as in the Example 5, and filter would include collections, created by all possible chains of currency exchange, that contain more than 7 euros, and minimal sum of rubles. According to (9), (18) – (20) and (26), STMS, generated by application of FMG , would contain, at least, multiset {9 ⋅ (eur), 1 ⋅ (usd)}, because it includes multiobject 9 ⋅ (eur)satisfying boundary condition (eur)> 7, as well as MO 0 ⋅ (rur)with absolutely minimal multiplicity 0, thus satisfying optimizing condition (rur)= min. (Remind, that (rur)∉ is equivalent to 0 ⋅ (rur)∈ ).∎
As may be seen, generation of set of terminal multisets by application of filtering multiset grammar is nothing but knowledge- and goal- driven computation.
By this we finish brief introduction to the mathematical toolkit, which will be used below for representation of the proposed resource-based games.
We shall begin from the simplest kind of game, where two participating sides (players A and B), each owning his resource base, make their moves sequentially, one after another. Each move (“impact”) provides extraction (elimination) of some amount of resources from the RB of the moving player as well as from the RB of his opponent, i.e., to reduce opponent’s resource base, player must spend some part of his own RB. This situation is typical for conflicts of various nature. Along with resource base, every player has his moves base (MB), i.e. set of his possible moves; each move may be made only in the case, when player’s resource base contains all resources, necessary for this move. Also, every player may stop his activity, and after that, as well as in the case, where next move can’t be done by lack of resources, game is also stopped. So, game continues until next move may be done. Game result is join of players resource bases at the moment, when game is stopped. It is postulated, that every player owns full information about RB and MB of his opponent. Along with RB and MB every player at the beginning of the game formulates his goal, i.e. what conditions would satisfy both players resource bases when the game stops. Participating the game, any player wishes to reach his goal. If there exists such final state of the game, that both players goals are reached, game is called bi-winners; if only one player’s goal is reachable – one-winner; otherwise – no-winner, or empty. According to the background of game theory [1, 2], described game may be related as antagonistic and with sequential moves.
Multiset where = { 1 ⋅ ( 1, ), . . . , ⋅ ( , )}, = { 1 ⋅ ( 1′, ), . . . , ⋅ ( ′ , )}.
, = ∪ {1 ⋅ , 1 ⋅ ( 1 , ), . . . , ⋅ ( , )} →
{− 1 ⋅ ( 1 , ), . . . , − ⋅ ( , ), 1 ⋅ }, will be called initial resource base of the game.
where , ∈ { , }, and ≠ . According to FMG semantics, application of rule (30) is possible, if left part of this rule is submultiset of the current multiset ̄, generated by execution of previous steps.
− 1, … , − , which from the substantial point of view provide elimination of regarding numbers of proper amounts of resources from the RB of opposite player . To apply such kind of rules we shall redefine (16) as
Let us consider multigrammatical representation of the described games, which since now will be strict mathematical definition of the verbally described earlier resource-based games.
First of all, we shall fix structure of lexemes, denoting resources; namely, the last would be composite objects of the form ( , ), where a is name of the resource, ∈ { , } – owner of the resource, and “( “, ”)” and “,” are dividers. So multiobject ⋅ ( , )describes the fact, that units of resource belong to (are in ownership of) player . Thus, initial resource base of player A is multiset, while initial RB of player B is multiset ̅′ = ̅− + +′ − (− −′ ),
′ = +′ + −′ −{− 1 ∙ 1, … , − ∙ } = { 1 ∙ 1, … , ∙ }
Example 7. Let and rule is according to (32) +′ = {1 ∙ }, −′ = −3 ∙ (eur, ), − −′ = {3 ∙ (eur, )}, ̅= {1 ∙ , 3 ∙ (eur, ), 4 ∙ (usd, ), 1 ∙ (eur, ), 3 ∙ (usd, )}, {1 ∙ , 2 ∙ (eur, ), 2 ∙ (usd, )} → {−3 ∙ (eur, ), 1 ∙ }. and result of application of rule to multiset ̅is MS ̅′ = {1 ∙ (eur, ), 2 ∙ (usd, ), 1 ∙ (eur, ), 3 ∙ (usd, )} + {1 ∙ } − {3 ∙ (eur, )} = = {1 ∙ , 1 ∙ (eur, ), 2 ∙ (usd, ), 3 ∙ (usd, )}.∎ (27) (28) (29) (30) (31) (32) (33)
As it is easy to see, replacement of (16) by (31)-(32) is necessary to avoid negative multiplicities in generated multisets. This is done by transformation (31), which provides application of MS subtraction (8), which excludes appearance of such multiplicities, i.e. negative amounts of resources.
Now it is clear, that result of application of rule (30) is appearance of multiobject 1 ⋅ , which presence in the generated multiset provides possibility of the next move of player ≠ . As seen, such form of rules exactly corresponds to the verbally described above logic and dynamic of the considered games.
Now we may construct filtering multigrammar representing game in full accordance with its verbal description.
This FMG = ⟨ 0, , ⟩ is such, that multiset is kernel, corresponding to the initial state of the game, which starts from the player’s A move with initial resource base of the game, defined by (27)-(29). Scheme R is join of moves bases of both players: 0 = {1 ⋅ } + , ,
= ∪ , = { | {1 ∙ } + → ′ ∈ }, = { | {1 ∙ } + → ′ ∈ },
= ∪ where and is filter, being join of subfilters and , representing goals of participation of players in the game. Filter provides selection of all terminal multisets which satisfy both players goals. These TMS form set ̄ , representing all possible results of the game, which satisfy both players. If ̄ = { }, game is nowinner. If ̅ ≠ {∅} and ̅ = {∅}, winner is player ; if ̅ = {∅} and ̅ ≠ {∅}, winner is player . Here =< 0, , >, =< 0, , >.
Example 7. Let initial resource base of player is {4 ⋅ , 8 ⋅ , 9 ⋅ }, RB of player – {6 ⋅ , 10 ⋅ , 3 ⋅ , 12 ⋅ }, and their capabilities (possible mutual impacts) are presented in the following tables. Player’s goal is that, after game stops, his resource base would contain no less than 2 objects , no less than 4 objects and maximal possible number of objects , while resource base of player minimal possible number of objects , as well as no more than 2 objects . Player’s goal is that, after game stops, his resource base would contain no less than 3 objects , no less than 5 objects , while resource base of player
would contain minimal possible number of objects and no more than 3 0 = {4 ⋅ ( , ), 8 ⋅ ( , ), 9 ⋅ ( , ), 6 ⋅ ( , ), 10 ⋅ ( , ), 3 ⋅ ( , ), 12 ⋅ ( , ), 1 ⋅ }. According to tables 1 and 2, scheme R will contain following rules marked and : ( 2 ): {1 ∙ , 1 ∙ ( , ), 3 ∙ ( , )} → {−2 ∙ ( , ), 1 ∙ }, ( 1 ): {1 ∙ , 2 ∙ ( , ), 1 ∙ ( , )} → {−1 ∙ ( , ), −1 ∙ ( , ), 1 ∙ }, Filter contains following conditions: ( 2 ): {1 ∙ , 3 ∙ ( , ), 2 ∙ ( , )} → {−4 ∙ ( , ), 1 ∙ }. ( 1 ): {1 ∙ , 3 ∙ ( , ), 2 ∙ ( , )} → {−2 ∙ ( , ), −1 ∙ ( , ), 1 ∙ }, ( 3 ): {1 ∙ , 1 ∙ ( , ), 2 ∙ ( , ), 3 ∙ ( , )} → {−1 ∙ ( , ), −4 ∙ ( , ), 1 ∙ }, ( 1 ): ( , )≥ 2, ( 2 ): ( , )≥ 4, ( 3 ): ( , )= max, ( 4 ): ( , )= min, ( 5 ): ( , )≤ 2, ( 1 ): ( , )≥ 3, ( 2 ): ( , )≥ 5, ( 3 ): ( , )= min, ( 4 ): ( , )≤ 3. of player .
As seen, subfilter = { 1 , . . . , 5 } defines goal of player , while subfilter = { 1 , . . . , 4 } – goal
Let us apply to 0. To simplify representation of generation chains, we shall use table, which columns correspond to objects having place in the generated multisets, each represented by string of the table. Number having place on the intersection of column ( , )and string is multiplicity of object ( , ) in multiset , i.e. ⋅ ( , )∈ . Each string, representing multiset , is followed by string, representing rule, applied to , in a form of multiplicities of objects having place in this rule; that, which are in the left part of rule, are negative numbers, while multiplicities from the right part are represented by positive numbers. Table corresponds to one generation chain, and two lowest strings represents subfilters and in such a way, that each boundary condition ( , ) each optimizing condition ( , )= is represented by is represented by
, and , both having place in Generation chain 0 ⇒ 1 ⇒ 2 ⇒ 3 is represented by Table 3; as may be seen, multiset 3 does We shall not continue generation by reason this game is no-winner (empty); it is obvious, if to consider conditions entering filter – some of them (for example, ( , )≥ 4 ∈ and ( , )≤ 3 ∈ ) are contradictory, i.e. no one final multiset generation by scheme application to kernel 0 will not column ( , ). not satisfy filter F. satisfy them. ∎ resource-driven games.
Let us consider some variations of the proposed basic techniques of multigrammatical modelling of 0 1
More complicated case may include not only elimination of resources of the opposing player by spending own resources, but also change of their ownership (“their capturing”). Such moves may be represented by rules having following form: {1 ⋅ , 1 ⋅ ( 1, ), . . . , ⋅ ( , ),
1 ⋅ ( 1, ), . . . , ⋅ ( , )} →
{1 ⋅ , 1 ⋅ ( 1, ), . . . , ⋅ ( , )}.
As seen, player , spending 1 objects 1, . . . , objects , removes 1 objects 1, . . . , objects to his ownership from the opposing player. Unlike previous case (30), where result of every move was elimination of resources from both players resource bases, here occurs possibility of keeping resources reusable, but their owner becomes another player. (Note, that according to MG semantics, rule (39) will be applied only if all removed resources in necessary amounts have place in player’s y ownership). Example 8. Let us join to the moves base (i.e. scheme R) of the Example 7 two new moves (rules), providing capturing resources of the opposing player: ( 4 ): {1 ∙ , 3 ∙ ( , ), 1 ∙ ( , ), 1 ∙ ( , ), 1 ∙ ( , )} → {1 ∙ , 1 ∙ ( , ), 1 ∙ ( , )}, ( 3 ): {1 ∙ , 1 ∙ ( , ), 3 ∙ ( , ), 1 ∙ ( , ), 2 ∙ ( , )} → {1 ∙ , 1 ∙ ( , ), 2 ∙ ( , )}. As seen, 5 application provides capturing one object and one object , belonging to player , by player , spending for this purpose three objects and one object . Similarly, 4 application provides removal of one object and two objects from to , the last spending for this action one object and three objects . ∎
In general case there may be combination of two previous cases, when one move provides both elimination (destruction) of some resources of the opposing player as well as capturing of another his resources remaining reusable. Such “combined” moves have following form: {1 ∙ , 1 ∙ ( 1, ), … , ∙ ( , ), 1 ∙ ( 1 , ), … , ∙ ( , )} →
{1 ∙ , − 1′ ∙ ( ′1 , ), … , − ′ ∙ ( ′ , ), 1 ∙ ( 1, ), … , ∙ ( , )}.
(39) (40) As seen, this move provides elimination of 1′ objects ′1 , . . . , ′ objects ′ , belonging to player , and removal of 1 objects 1 , . . . , objects from his ownership to player , who would spend for this purpose 1 objects 1, . . . , objects .Note, that (40) would be applicable only in the case when resource base of player before move of player includes no less than 1′ objects ′1 ,…, ′ objects ′ .
The next level of complexity presumes that some player is capable to produce new objects from being already in his ownership, and aftermath to use produced resources during further steps of the game (conflict). To implement such feature, we shall introduce so-called internal moves, which are defined by rules, containing “control” multiobjects 1 ⋅ in both parts of rule: {1 ⋅ , 1 ⋅ ( 1 , ), . . . , ⋅ ( , )} →
{1 ⋅ , 1′ ⋅ ( ′1 , ), . . . , ′ ⋅ ( , )}.
(41) As seen, after this rule application, player x remains active and will do the next move, and so until there will be applied rule with multiobject 1 ⋅ instead of 1 ⋅ in the right part. Moves described by (41) will be called internal.
Let us now describe, how player’s producing capabilities may be defined by means of internal moves techniques. For this purpose, we shall use intermediate “black box” representation for description of mentioned capabilities. Namely, we shall assume, that player possesses set of producing (manufacturing) devices, each represented by “black box” with inputs and one output (Fig.1). Every -th input is marked a 1 am n 1 ... nm
A graphical representation having place at Fig. 1 describes, that objects 1, . . . , objects by – name of object (item, resource) – and – amount (volume, quantity) of such objects. So are required for producing (manufacturing) one object .
Each object produced by means of any device may be used in a “manufacturing chains” providing creation of new objects. So, the whole “manufacturing potential” (or “technological base”) of player x may be represented by set of rules like {1 ⋅ , 1 ⋅ 1, . . . , ⋅ } → {1 ⋅ , 1 ⋅ }, (42) each corresponding its own producing (manufacturing) device.
Some of produced objects may be used in moves, providing impacts on the opposing player, along with objects, used in these moves directly. Graphical representation of such game has place at Fig. 2, where players interaction (i.e. moves like (40)) is implemented through the depicted ellipse G. a 1 . .
. am . . . . .
A 1 ...
A l a l . . .
. .
.
G .
In general case every or some of “black boxes” may have not one but > 1 outputs, and then rules, representing it, have the following form:
{1 ⋅ , 1 ⋅ 1, . . . , ⋅ } → {1 ⋅ , 1 ⋅ 1′, . . ,1 ⋅ ′ }.
Example 9. Let us join to the moves base (scheme ), obtained in the previous example 8, two new moves (rules), providing manufacturing objects, which may be used for preparing impacts: ( 6 ): {1 ⋅ , 1 ⋅ ( , ), 2 ⋅ ( , )} → {1 ⋅ , 1 ⋅ ( , )}, ( 5 ): {1 ⋅ , 1 ⋅ ( , ), 1 ⋅ ( , )} → {1 ⋅ , 1 ⋅ ( , )}.
Since these rules appearance in the scheme , generation chains (i.e. moves sequences) will implement manufacturing operations, providing inclusion to the player’s resource base additional objects , each produced by spending one object and two objects , as well as to the player’s resource base additional objects , each produced by spending one object and one object .∎
Let us note, that resources spent for manufacturing of new object may be its spare parts as well as consumables necessary for operation of manufacturing device (electrical energy, fuels etc.). Among such resources there would be obligatory “active state of the device”, represented by special multiobject 1 ⋅ , where is name of device. Such multiobjects may be, as all other presenting in the resource bases, eliminated (destroyed) and captured as a result of some moves of the opposing side. Such techniques provide simple representation of actions providing destructive impacts not only on resource base but also on technological base.
Of course, kernel of the corresponding multigrammar will be in this case {1 ⋅ , 1 ⋅ } + + , where and are initial resource bases of both players.
Goals of game for both players are, as higher, represented by subfilters and joined to one filter = ∪ of corresponding filtering multigrammar. m 1 m l b 1 . .
Along with simultaneous moves, made by both players, there may be internal moves of the same form as (41). By this moves each player may prepare to simultaneous moves, made by both of them. All the said about such moves higher in this section is applicable to this kind of antagonistic RBG. As may be seen, multigrammatical representation provides easy use of both sequential and parallel moves in one game.
As it is known from game theory, there may be also cooperative games, where players interact without causing mutual damage, but, on the contrary, helping one another in order to provide their goals reachability. This kind of RBG is considered in the following section.
Cooperation means, that there may be resources exchange between players, or one of them may deliver his own resources to another without any compensation. Also, of course, any player may produce new resources from his own, and also from resources, belonging to the second player.
Resources exchange may be represented by rule of the following form (in a simultaneous moves version): (45) (46) (47)
As may be seen, application of this rule results in transfer of 1 units of resource 1,…, units of resource , all belonging to player , to the player ownership. Instead of mentioned transferred resources player will get 1 units of resource 1,…, units of resource , which until exchange belonged to player .
In the “altruistic” case, when one player does not demand on any compensation from his partner, corresponding rule is as follows: {1 ∙ , 1 ∙ , 1 ∙ ( 1, ), … , ∙ ( , )} →
{1 ∙ , 1 ∙ , 1 ∙ ( 1, ), … , ∙ ( , )}.
Cooperation inside producing (manufacturing) process presumes possible use of resources, that belong to one player, for production of resources, which, being manufactured, may belong to another player.
Structure of rules, representing producing (manufacturing) capabilities of players, is the same, as (42), but, for generality, multiobjects are extended by information about ownership, which, as was said higher, may be of both sides. Such rules, implementing internal moves of players, may be as follows: {1 ∙ , 1 ∙ ( 1, 1), … , ∙ (
, )} → {1 ∙ , 1 ∙ ( , +1)}.
This means, that player ∈ { , }, doing his move, produces one unit of resource and belonging to player +1 ∈ { , }, using for this purpose 1 units of resource 1 and belonging to player 1 ∈ { , }, . . . , units of resource
Of course, there may
∈ { , }. multiobject 1 ⋅ , where ≠ , in the right part of rule (47). In this case move is not internal, because the next move may be done only by another player.
Filtering multiset grammar = ⟨ 0, , ⟩, which kernel 0 is initial resource base joined with “starting” multiobject(s), scheme contains rules of form (45) – (47), and filter contains conditions, defining goals of both players, is representation of cooperative game with two players.
Further generalization of cooperative games with two players are cooperative games with arbitrary number of players
≥ 2 (multi-player games).
As may be seen, described techniques of multigrammatical representation of games provides simple and natural description of games with any number of players. It is sufficient to use multiobjects of the form 1 ⋅ , where is name of the player, in any combinations, in the right and left parts of the rules. Such games are easily represented by multigrammars, which schemes contain rules like and kernel is {1 ∙ 1, … ,1 ∙ , 1 ∙ ( 1 , 1), … , ∙ (
{1 ∙ 1, … ,1 ∙ , 1′ ∙ ( 1 , 1 ), … , ′ ′ ∙ ( , )} →
′
, ′ )} {1 ⋅ 1, . . . ,1 ⋅ } + 1+. . . + , cooperation of players in order to create such resource base, which would satisfy filter where is name of -th player, and is his initial resource base. As seen, rules like (47) represent = 1 ∪. . .∪ , coalitions, but cooperative inside any coalition. of coalitions and players entering them. where is subfilter, defining goal of -th player. Of course, along with rules (38) there may be rules, representing internal moves of any player, but also there may be moves, done simultaneously by any subset of players { 1, . . . , } ⊂ { 1, . . . , }. Such kind of cooperation may be implemented not only in the case, when players do help one another, but also in the case when some of them join in order to oppose another. Following terminology of classical game theory, such stable sets (groups) of players, synchronizing their moves and matching their goals, may be called coalitions, and such games – coalitional resource-based games. As may be seen, these games are antagonistic, regarding opposing
Multigrammatical representation of games makes it easy to describe logic of behavior of any number
Presented paper introduces a new class of games, covering a wide area of interactions of sociotechnological systems, and its basic novelty is consideration of interacting STS as entities, which consume, produce, destroy and capture various resources. Secondly, a novel multiset-based mathematical toolkit, integrating descriptional properties of classical mathematical programming and modern knowledge engineering, is used for strict formalizing of the introduced games, and, thus, for solving problems in the fully automated mode, saving to the decision makers and their staff a minimal work on the MG-represented knowledge base creation and maintenance. “What – if” mode here may be used without any difficulties.
First of them is lack of time in rules, representing resources motion and use. This makes impossible description of STS operation on the time scale, that is highly important for precise modelling of any kind of conflict and cooperation. An adequate tool for elimination of this drawback are temporal multiset grammars (TMG), introduced in brief in [19]. TMG operate so called temporal multisets having form { 1 ⋅ 1, . . . , ⋅ , ⋅ }, where t is special object (“time”), and multiplicity means, that MS { 1 ⋅ 1, . . . , ⋅ } is actual at moment since STS have begun its operation. Scheme of TMG contains so called temporal rules like (48) (49) (50) (52) { 1 ⋅ 1, . . . , ⋅ } → { 1′ ⋅ 1′, . . . , ′ ⋅ ′ , ′ ⋅ }, which application to temporal MS ̄+ { ⋅ } is as follows. If { 1 ⋅ 1, . . . , ⋅ } ⊆ ̄ ∈ then temporal MS
̅′ = ̅− { 1 ⋅ 1, . . . , ⋅ } + { 1′ ⋅ 1′, . . . , ′ ⋅ ′ , ( + ′)⋅ } ∈
From the substantial point of view (52) means, that new temporal MS ̅′ will be actual at moment + ′. In (51) is one more special object (“time interval”), which multiplicity ′ defines duration of replacement of MS { 1 ⋅ 1, . . . , ⋅ } by MS { 1′ ⋅ 1′, . . . , ′ ⋅ ′ } (in the case of producing devices/facilities ′ means duration of manufacturing of collection of resources { 1′ ⋅ 1′, . . . , ′ ⋅ ′ } given input collection of resources { 1 ⋅ 1, . . . , ⋅ }).
Another limitation flows out of absence in rules, representing moves, information about locations of players. This feature restricts family of the considered games by those, which have place at one compact location. However, it is not so difficult to represent distributed games, which represent conflicts and cooperation, ongoing in some wide geospatial areas. Techniques of such representation is based on inclusion to the introduced higher composite lexemes like ( , )the third component being symbolic or numeric description of point or area, where collection of units of resource a belonging to player would be located. So multiobjects used in rules are as ∙ ( , , ). Such techniques, proposed in [19], was applied in [20], dedicated to the assessment of resilience of critical infrastructures to the destructive impacts, multiplied by cascading (chain) effects.
One more limitation of the proposed framework is that it is not directly applicable to the incomplete information games [28, 29, 30], which are most useful for practice. We have considered all kinds of games in presumption, that all information about resources and moves at all steps of the game (or generation steps while rules application) is available to all players. However, this presumption is far from reality, where every player at every moment is aware only about some part of resource bases and moves bases of other players. Moreover, this information in general case may be incomplete, ambiguous, unreliable, contradictive etc.; saying shortly, imperfect.
To handle such games, further generalization of multiset grammars, called multiset metagrammars (MMG), may be applied effectively.
MMG differ from MG by existence of multiplicities-variables and containing them metarules (MR), which provide natural implanting to the multigrammatical framework powerful toolkit of interval analysis [31, 32]. One valuable simplification of MMG called unitary multiset metagrammars is fully described in [17, 18].
The most general and powerful class of multiset grammars, providing natural representation and efficient solution of various games, are temporal multiset metagrammars (TMMG). This direction of the development of the multigrammatical framework and its implementation will be considered in future publications.
Acknowledgments Author is grateful to Acad. Igor Bychkov, Acad. Yuriy Shokin, Prof. Fred Roberts, and Prof. Don Saari for useful discussions. [30] Sandomirsky F 2014 Repeated games of incomplete information with large sets of states (Int. J.
of Game Theory) 43(4) 767-789 [31] Shokin Yu I 1996 On interval problems, interval algorithms and their complexity (Computational
Technologies) 1(1) 3 [32] Hansen E and Walster G W 2004 Global Optimization Using Interval Analysis (New-York: Marcel Dekker) p 530