=Paper=
{{Paper
|id=Vol-2638/paper22
|storemode=property
|title=Resource-based games
|pdfUrl=https://ceur-ws.org/Vol-2638/paper22.pdf
|volume=Vol-2638
|authors=Igor Sheremet
|dblpUrl=https://dblp.org/rec/conf/iccs-de/Sheremet20
}}
==Resource-based games==
https://ceur-ws.org/Vol-2638/paper22.pdf
Resource-based games
I A Sheremet1
1
Russian Foundation for Basic Research, Leninskiy Prosp., 32a, Moscow, Russia,
119334
sheremet@rfbr.ru
Abstract. Article is dedicated to the multigrammatical modelling of games. Basic notions and
definitions, concerning multisets and multiset grammars, are considered. So called resource-
based games are introduced, and representation of their simplest class – antagonistic resource-
based 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.
1. Introduction
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
Copyright © 2020 for this paper by its authors. Use permitted under Creative Commons License Attribution
4.0 International (CC BY 4.0).
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, multi-
agent 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 resource-
based cooperative and coalitional games – in Section 4. Directions of further research in the RBG area
are discussed in the conclusion.
2. Multisets, operations on multisets, and multiset grammars
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)
𝑣 = {𝑎
⏟1 , . . . , 𝑎1 , . . . , ⏟
𝑎𝑖 , . . . , 𝑎𝑖 , . . . , ⏟
𝑎𝑚 , . . . , 𝑎𝑚 },
𝑛1 𝑡𝑖𝑚𝑒𝑠 𝑛𝑖 𝑡𝑖𝑚𝑒𝑠 𝑛𝑚 𝑡𝑖𝑚𝑒𝑠
and this is recorded as
𝑣 = {𝑛1 ⋅ 𝑎1 , . . . , 𝑛𝑚 ⋅ 𝑎𝑚 }, (2)
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
𝑚
(3)
|𝑣| = ∑ 𝑛𝑖 ,
𝑖=1
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 {𝜙}.
Zero multiplicity of some object is identical to absence of this object in multiset, i.e.
{𝑛1 ⋅ 𝑎1 , . . . , 𝑛𝑚 ⋅ 𝑎𝑚 , 0 ⋅ 𝑎𝑚+1 } = {𝑛1 ⋅ 𝑎1 , . . . , 𝑛𝑚 ⋅ 𝑎𝑚 }. (4)
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
(∀𝑛 ⋅ 𝑎 ∈ 𝑣)(∃𝑛′ ⋅ 𝑎 ∈ 𝑣 ′)𝑛 ≤ 𝑛′ , (5)
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.
Example 1. Let
𝑣 = {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 non-
negative 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 , . . . , (𝑛 × 𝑛𝑚 ) ⋅ 𝑎𝑚 }, (6)
where “×” denotes multiplication of integer numbers;
𝑣 + 𝑣 ′ = ⋃{(𝑛 + 𝑛′ ) ∙ 𝑎},
𝑎 ∈ 𝛽(𝑣) ∪ 𝛽(𝑣′) (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{𝑛, 𝑛′ } ∙ 𝑎},
𝛼 ∈ 𝛽(𝑣) ∪ 𝛽(𝑣′) (9)
𝑛∙𝑎 ∈𝑣
𝑛′ ∙ 𝑎 ∈ 𝑣
𝑣 ∩ 𝑣 ′ = ⋃{min{𝑛, 𝑛′ } ∙ 𝑎}
𝛼 ∈ 𝛽(𝑣) ∪ 𝛽(𝑣′) (10)
𝑛∙𝑎 ∈𝑣
𝑛′ ∙ 𝑎 ∈ 𝑣
We have used the aforementioned equivalence between 𝑎 ∉ 𝑣 and 0 ⋅ 𝑎 ∈ 𝑣 in (9)-(10).
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.
Conditions entering filter 𝐹 may be boundary and optimizing.
Boundary condition (BC) is written as 𝑎𝜃𝑛, where 𝜃 ∈ {>, <, ≥, ≤, =}. Multiset 𝑣 satisfies BC 𝑎𝜃𝑛,
if 𝑚 ⋅ 𝑎 ∈ 𝑣, and 𝑚𝜃𝑛 is true (as everywhere, 𝑎 ∉ 𝑣 is equivalent to 0 ⋅ 𝑎 ∈ 𝑣).
Let 𝐹≤ = {𝑏𝑐1 , . . . , 𝑏𝑐𝑘 } be a filter, containing only boundary conditions.
Then
𝑘
𝑣 ↓ 𝐹≤ = ⋂(𝑉 ↓ {𝑏𝑐𝑖 }). (11)
𝑖=1
Example 3. Let 𝑉 = {𝑣1 , 𝑣2 , 𝑣3 }, where
𝑣1 = {3 ⋅ (eur), 5 ⋅ (rur)},
𝑣2 = {7 ⋅ (usd), 9 ⋅ (rur)},
𝑣3 = {4 ⋅ (eur), 11 ⋅ (usd), 15 ⋅ (rur)},
and
𝐹≤ = {(usd) > 3, (rur) ≤ 10}.
Then
𝑉 ↓ 𝐹≤ = (𝑉 ↓ {(usd) > 3}) ∩ (𝑉 ↓ {(rur) ≤ 10}) = {𝑣2 , 𝑣3 } ∩ {𝑣1 , 𝑣2 } = {𝑣2 }. ∎
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 𝑎 ≥ 𝑛.
Let 𝐹𝑜𝑝𝑡 = {𝑜𝑐1 , . . . , 𝑜𝑐𝑙 } be a filter, containing only optimizing conditions. Then, similarly to (6),
𝑙
𝑣 ↓ 𝐹𝑜𝑝𝑡 = ⋂(𝑣 ↓ {𝑜𝑐𝑖 }). (12)
𝑖=1
Example 4. Let 𝑉 be the same as in the Example 3, and
𝐹𝑜𝑝𝑡 = {(usd) = max,(rur) = min}.
Then
𝑣 ↓ 𝐹𝑜𝑝𝑡 = 𝑣 ↓ {(usd) = max})(𝑣 ↓ {(rur) = min}) = {𝑣3 } ∩ {𝑣1 } = {𝜙}. ∎
If filter F contains both boundary and optimizing conditions, i.e.
𝐹 = 𝐹≤ ∪ 𝐹𝑜𝑝𝑡 , (13)
then
𝑉 ↓ 𝐹 = (𝑉 ↓ 𝐹≤ ) ↓ 𝐹𝑜𝑝𝑡 , (14)
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
𝑣 → 𝑣′, (15)
where multisets 𝑣 and 𝑣 ′ are called left part and right part of the rule 𝑟 respectively, 𝑣 ≠ {𝜙}, and “→”
is divider.
Application of the rule 𝑟 to the multiset 𝑣̄ is defined as follows. If 𝑣 ⊆ 𝑣̄ , then the result of 𝑟
application to 𝑣̄ is multiset
𝑣̅ ′ = 𝑣̅ − 𝑣 + 𝑣′ (16)
i.e., speaking informally, MS v, which is submultiset of MS 𝑣̄ , is replaced by
MS 𝑣′. The result of application of rule 𝑟 to multiset 𝑣̄ is denoted
𝑟
𝑣̄ ⇒ 𝑣̅ ′ (17)
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
follows:
𝑉(0) = {𝑣0 }, (18)
𝑟
𝑉(𝑖+1) = 𝑉(𝑖) ∪ ( ⋃ ⋃ {𝑣̅ ′ |𝑣̄ ⇒ 𝑣̅ ′ }) (19)
𝑣̄ ∈𝑉(𝑖) 𝑟∈𝑅
𝑉𝑆 = 𝑉(∞) . (20)
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
∞
(21)
𝑉𝑆 = ⋃ 𝑉(𝑖) ,
𝑖=0
and in general case 𝑉𝑆 may be infinite.
If MS 𝑣̅ ′ may be generated from MS 𝑣̄ by application of scheme R, it is denoted
𝑅 (22)
𝑣̄ ⇒ 𝑣̅ ′ ,
so, from this point of view,
𝑅 (23)
𝑉𝑆 = {𝑣̄ |𝑣0 ⇒ 𝑣̄ }.
Multiset 𝑣̄ ∈ 𝑉𝑆 is called terminal multiset (TMS), if
𝑟
(∀𝑟 ∈ 𝑅)𝑣̄ ⇒ {𝜙}, (24)
i.e. no any rule 𝑟 ∈ 𝑅 may be applied to 𝑣̄ . Set of terminal multisets (STMS) generated by application
of multiset grammar 𝑆 is denoted 𝑉̄𝑆 . Obviously,
𝑉̄𝑆 ⊆ 𝑉𝑆 . (25)
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)}},
𝑉(1) = 𝑉(0) ∪ {{2 ⋅ (eur), 11 ⋅ (usd), 4 ⋅ (rur)}, {7 ⋅ (eur), 4 ⋅ (usd), 2 ⋅ (rur)}},
𝑉(2) = 𝑉(1) ∪ {4 ⋅ (eur), 8 ⋅ (usd), 2 ⋅ (rur)}, {4 ⋅ (eur), 8 ⋅ (usd), 2 ⋅ (rur)}, {9 ⋅ (eur), 1 ⋅ (usd)}}, . ..
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
exchanged to 2 euros). ∎
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 𝑆 = ⟨𝑣0 , 𝑅, 𝐹⟩, where 𝑣0 and 𝑅 are kernel and scheme, while 𝐹
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 ,𝑅〉 ↓ 𝐹. (26)
Verbally, 𝑉𝑆 is subset of 𝑉 〈𝑣0 ,𝑅〉 , which includes only such elements of this set, that satisfy filter F.
Example 6. Consider 𝑆 = ⟨𝑣0 , 𝑅, 𝐹⟩, where 𝑣0 and 𝑅 are the same, as in the Example 5, and filter
𝐹 = {(eur) > 7, (rur) = min}, that means 𝑉̅𝑆 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.
3. Resource-based antagonistic 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.
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,
𝑣𝐴 = {𝑛1𝐴 ⋅ (𝑎1 , 𝐴), . . . , 𝑛𝑚
𝐴 (𝑎
⋅ 𝑚 , 𝐴)}, (27)
while initial RB of player B is multiset
𝑣𝐵 = {𝑛1𝐵 ⋅ (𝑎1′ , 𝐵), . . . , 𝑛𝑙𝐵 ⋅ (𝑎𝑙′ , 𝐵)}. (28)
Multiset
𝑣𝐴,𝐵 = 𝑣𝐴 ∪ 𝑣𝐵 (29)
will be called initial resource base of the game.
For moves representation we shall use rules having following form:
{1 ⋅ 𝑥, 𝑙1 ⋅ (𝑎𝑖1 , 𝑥), . . . , 𝑏𝑘 ⋅ (𝑎𝑖𝑘 , 𝑥)} →
(30)
{−𝑚1 ⋅ (𝑎𝑗1 , 𝑦), . . . , −𝑚𝑔 ⋅ (𝑎𝑗𝑔 , 𝑦) , 1 ⋅ 𝑦},
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.
The new and principal thing in (30) are negative multiplicities −𝑚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
𝑣̅ ′ = 𝑣̅ − 𝑣 + 𝑣+′ − (−𝑣−′ ), (31)
where
𝑣 ′ = 𝑣+′ + 𝑣−′ (32)
−{−𝑚1 ∙ 𝑎1 , … , −𝑚𝑙 ∙ 𝑎𝑙 } = {𝑚1 ∙ 𝑎1 , … , 𝑚𝑙 ∙ 𝑎𝑙 } (33)
Let us illustrate (31)-(33) by following example
Example 7. Let
𝑣̅ = {1 ∙ 𝐴, 3 ∙ (eur, 𝐴), 4 ∙ (usd, 𝐴), 1 ∙ (eur, 𝐵), 3 ∙ (usd, 𝐵)},
and rule 𝑟 is
{1 ∙ 𝐴, 2 ∙ (eur, 𝐴), 2 ∙ (usd, 𝐴)} → {−3 ∙ (eur, 𝐵), 1 ∙ 𝐵}.
according to (32)
𝑣+′ = {1 ∙ 𝐵},
𝑣−′ = −3 ∙ (eur, 𝐵),
−𝑣−′ = {3 ∙ (eur, 𝐵)},
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, 𝐵)}.∎
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
𝑣0 = {1 ⋅ 𝐴} + 𝑣𝐴,𝐵 , (34)
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:
𝑅 = 𝑅𝐴 ∪ 𝑅𝐵 , (35)
where
𝑅𝐴 = {𝑟 | {1 ∙ 𝐴} + 𝑣 → 𝑣′ ∈ 𝑅}, (36)
𝑅𝐵 = {𝑟 | {1 ∙ 𝐵} + 𝑣 → 𝑣′ ∈ 𝑅}, (37)
and
𝐹 = 𝐹𝐴 ∪ 𝐹𝐵 (38)
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 no-
winner. If 𝑉̅𝑆𝐴 ≠ {∅} and 𝑉̅𝑆𝐵 = {∅}, winner is player 𝐴; if 𝑉̅𝑆𝐴 = {∅} and 𝑉̅𝑆𝐵 ≠ {∅}, winner is player 𝐵.
Here 𝑆𝐴 =< 𝑣0 , 𝑅, 𝐹𝐴 >, 𝑆𝐵 =< 𝑣0 , 𝑅, 𝐹𝐵 >.
Let us illustrate described technique of RBG multiset modelling by example.
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.
Table 1.
№ Spent by 𝐴 Eliminated from 𝐵
1 2 ⋅ 𝑎, 1 ⋅ 𝑏 1 ⋅ 𝑎, 1 ⋅ 𝑑
2 1 ⋅ 𝑎, 3 ⋅ 𝑏 2⋅𝑏
3 1 ⋅ 𝑎, 2 ⋅ 𝑏, 3 ⋅ 𝑐 1 ⋅ 𝑏, 4 ⋅ 𝑑
Table 2.
№ Spent by 𝐵 Eliminated from 𝐴
1 3 ⋅ 𝑎, 2 ⋅ 𝑏 2 ⋅ 𝑎, 1 ⋅ 𝑏
2 1 ⋅ 𝑏, 1 ⋅ 𝑐, 4 ⋅ 𝑑 4⋅𝑐
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
objects 𝑏.
By this, game, which first move will be done by player A, may be represented by multigrammar
𝑆 = ⟨𝑣0 , 𝑅, 𝐹⟩, where
𝑣0 = {4 ⋅ (𝑎, 𝐴), 8 ⋅ (𝑏, 𝐴), 9 ⋅ (𝑐, 𝐴), 6 ⋅ (𝑎, 𝐵), 10 ⋅ (𝑏, 𝐵), 3 ⋅ (𝑐, 𝐵), 12 ⋅ (𝑑, 𝐵), 1 ⋅ 𝐴}.
According to tables 1 and 2, scheme R will contain following rules marked 𝑟𝑖𝐴 and 𝑟𝑗𝐵 :
(𝑟1𝐴 ): {1 ∙ 𝐴, 2 ∙ (𝑎, 𝐴), 1 ∙ (𝑏, 𝐴)} → {−1 ∙ (𝑎, 𝐵), −1 ∙ (𝑑, 𝐵), 1 ∙ 𝐵},
(𝑟2𝐴 ): {1 ∙ 𝐴, 1 ∙ (𝑎, 𝐴), 3 ∙ (𝑏, 𝐴)} → {−2 ∙ (𝑎, 𝐵), 1 ∙ 𝐵},
(𝑟3𝐴 ): {1 ∙ 𝐴, 1 ∙ (𝑎, 𝐴), 2 ∙ (𝑏, 𝐴), 3 ∙ (𝑐, 𝐴)} → {−1 ∙ (𝑏, 𝐵), −4 ∙ (𝑑, 𝐵), 1 ∙ 𝐵},
(𝑟1𝐵 ): {1 ∙ 𝐵, 3 ∙ (𝑎, 𝐵), 2 ∙ (𝑏, 𝐵)} → {−2 ∙ (𝑎, 𝐴), −1 ∙ (𝑏, 𝐴), 1 ∙ 𝐴},
(𝑟2𝐵 ): {1 ∙ 𝐵, 3 ∙ (𝑎, 𝐵), 2 ∙ (𝑏, 𝐵)} → {−4 ∙ (𝑐, 𝐴), 1 ∙ 𝐴}.
Filter 𝐹 contains following conditions:
(𝐶1𝐴 ): (𝑎, 𝐴) ≥ 2,
(𝐶2𝐴 ): (𝑏, 𝐴) ≥ 4,
(𝐶3𝐴 ): (𝑐, 𝐴) = max,
(𝐶4𝐴 ): (𝑑, 𝐵) = min,
(𝐶5𝐴 ): (𝑏, 𝐵) ≤ 2,
(𝐶1𝐵 ): (𝑎, 𝐵) ≥ 3,
(𝐶2𝐵 ): (𝑏, 𝐵) ≥ 5,
(𝐶3𝐵 ): (𝑐, 𝐴) = min,
(𝐶4𝐵 ): (𝑏, 𝐴) ≤ 3.
As seen, subfilter 𝐹𝐴 = {𝐶1𝐴 , . . . , 𝐶5𝐴 } defines goal of player 𝐴, while subfilter 𝐹𝐵 = {𝐶1𝐵 , . . . , 𝐶4𝐵 } – goal
of player 𝐵.
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 (𝑥, 𝑋)𝜃𝑛 is represented by 𝜃𝑛, and
each optimizing condition (𝑥, 𝑋) = 𝑜𝑝𝑡 is represented by 𝑜𝑝𝑡, both having place in
column (𝑥, 𝑋).
𝑟𝑖𝐴 𝑟1𝐵 𝑟4𝐴
Generation chain 𝑣0 ⇒ 𝑣1 ⇒ 𝑣2 ⇒ 𝑣3 is represented by Table 3; as may be seen, multiset 𝑣3 does
not satisfy filter F.
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
satisfy them. ∎
Let us consider some variations of the proposed basic techniques of multigrammatical modelling of
resource-driven games.
Table 3.
𝑣 𝐴 𝐵
𝐴 𝐵
𝑟 𝑎 𝑏 𝑐 𝑎 𝑏 𝑐 𝑑
𝑣0 4 8 9 6 10 3 12 1 —
𝑟1𝐴 −2 −3 — −1 — — −1 −1 1
𝑣1 2 5 9 5 10 3 11 — 1
𝑟1𝐵 −2 −1 — −3 −2 — — 1 −1
𝑣2 — 4 9 2 8 3 11 1 —
𝑟4𝐴 — — — — — — — −1 —
𝑣3 — 4 9 2 8 3 11 — —
𝐹𝐴 ≥2 ≥4 Max — ≤2 — min — —
𝐹𝐵 — ≤3 min ≥3 ≥5 — — — —
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 , 𝑦), . . . , 𝑚𝑞 ⋅ (𝑎𝑗𝑞 , 𝑦)} → (39)
{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 , 𝑦), … , 𝑚𝑝 ∙ (𝑎𝑗𝑝 , 𝑦)} →
(40)
{1 ∙ 𝑦, −𝑙1′ ∙ (𝑎𝑗′1 , 𝑦), … , −𝑙𝑞′ ∙ (𝑎𝑗′𝑞 , 𝑦) , 𝑚1 ∙ (𝑎𝑗1 , 𝑥), … , 𝑚𝑝 ∙ (𝑎𝑗𝑝 , 𝑥)}.
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 𝑎𝑗′𝑞 .
Otherwise such operation would not be implemented.
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 , 𝑥), . . . , 𝑙𝑘 ⋅ (𝑎𝑖𝑘 , 𝑥)} →
(41)
{1 ⋅ 𝑥, 𝑙1′ ⋅ (𝑎𝑖′ 1 , 𝑥), . . . , 𝑙𝑞′ ⋅ (𝑎𝑖𝑞 , 𝑥)}.
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
n1
a1
...
nm A a
am
Figure 1.
by 𝑎𝑖 – name of object (item, resource) – and 𝑛𝑖 – amount (volume, quantity) of such objects. So
graphical representation having place at Fig. 1 describes, that 𝑛𝑖 objects 𝑎1 , . . . , 𝑛𝑚 objects 𝑎𝑚 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.
Player A Player B
n1 m1
a1 A1 b1
...
...
B1 b1
...
...
...
...
... G ...
...
...
...
...
nm ml
am Al al bk Bk bl
...
...
Figure 2.
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 ⋅ 𝑎𝑞′ }. (43)
Let us illustrate introduced generalization by example.
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.
All the said concerned antagonistic RBG with sequential moves.
Simultanious moves may be represented as follows. Namely, it is sufficient to use rules of the
following form:
{1 ∙ 𝐴, 1 ∙ 𝐵, 𝑙1 ∙ (𝑎𝑖1 , 𝐴), … , 𝑙𝑘 ∙ (𝑎𝑖𝑘 , 𝐴), 𝑚1 ∙ (𝑎𝑗1 , 𝐵), … , 𝑚𝑞 ∙ (𝑎𝑗𝑞 , 𝐵)} → {1 ∙ 𝐴, 1 ∙ 𝐵} (44)
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.
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.
4. Resource-based cooperative and coalitional games
Let us begin from cooperative RBG.
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):
{1 ∙ 𝐴, 1 ∙ 𝐵, 𝑙1 ∙ (𝑎𝑖1 , 𝐴), … , 𝑙𝑘 ∙ (𝑎𝑖𝑘 , 𝐴), 𝑚1 ∙ (𝑎𝑗1 , 𝐵), … , 𝑚𝑞 ∙ (𝑎𝑗𝑞 , 𝐵)} →
(45)
{1 ∙ 𝐴, 1 ∙ 𝐵, 𝑚1 ∙ (𝑎𝑗1 , 𝐴), … , 𝑚𝑞 ∙ (𝑎𝑗𝑞 , 𝐴) , 𝑙1 ∙ (𝑎𝑖1 , 𝐵), … , 𝑙𝑘 ∙ (𝑎𝑖𝑘 , 𝐵)}
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 , 𝐴), … , 𝑙𝑘 ∙ (𝑎𝑖𝑘 , 𝐴)} →
(46)
{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 )}. (47)
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 𝑎𝑖𝑚 and belonging to player 𝑥𝑚 ∈ {𝐴, 𝐵}.
Of course, there may be 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
{1 ∙ 𝑥1 , … ,1 ∙ 𝑥𝑚 , 𝑙1 ∙ (𝑎𝑖1 , 𝑥𝑖1 ), … , 𝑙𝑘 ∙ (𝑎𝑖𝑘 , 𝑥𝑖𝑘 )} →
(48)
{1 ∙ 𝑥1 , … ,1 ∙ 𝑥𝑚 , 𝑙1′ ∙ (𝑎𝑗1 , 𝑥𝑗1 ), … , 𝑙𝑘′ ′ ∙ (𝑎𝑗𝑘′ , 𝑥𝑗𝑘′ )}
and kernel is
{1 ⋅ 𝑥1 , . . . ,1 ⋅ 𝑥𝑚 } + 𝑣1 +. . . +𝑣𝑚 , (49)
where 𝑥𝑖 is name of 𝑖-th player, and 𝑣𝑖 is his initial resource base. As seen, rules like (47) represent
cooperation of players in order to create such resource base, which would satisfy filter
𝐹 = 𝐹1 ∪. . .∪ 𝐹𝑚 , (50)
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
coalitions, but cooperative inside any coalition.
Multigrammatical representation of games makes it easy to describe logic of behavior of any number
of coalitions and players entering them.
5. Conclusions
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.
However, described approach in his present form is not free of some limitations.
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
{𝑛1 ⋅ 𝑎1 , . . . , 𝑛𝑚 ⋅ 𝑎𝑚 } → {𝑛1′ ⋅ 𝑎1′ , . . . , 𝑛𝑙′ ⋅ 𝑎𝑙′ , 𝑘 ′ ⋅ 𝛥𝑡}, (51)
which application to temporal MS 𝑣̄ + {𝑘 ⋅ 𝑡} is as follows. If
{𝑛1 ⋅ 𝑎1 , . . . , 𝑛𝑚 ⋅ 𝑎𝑚 } ⊆ 𝑣̄ ∈ 𝑉𝑆
then temporal MS
𝑣̅ ′ = 𝑣̅ − {𝑛1 ⋅ 𝑎1 , . . . , 𝑛𝑚 ⋅ 𝑎𝑚 } + {𝑛1′ ⋅ 𝑎1′ , . . . , 𝑛𝑙′ ⋅ 𝑎𝑙′ , (𝑘 + 𝑘 ′ ) ⋅ 𝑡} ∈ 𝑉𝑆 (52)
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.
References
[1] Bierman H S and Fernandez I F 1997 Game theory for applied economists. 2d edition (Addison-
Wesley) p 480
[2] Papayoanou P 2010 Game Theory for Business: A Primer in Strategic Gaming (Probabilistic
Publishing) p 192
[3] Harrington J E 2014 Games, strategies, and decision making. 2d edition (Worth Publishers) p 736
[4] ShohamY and Leyton-Brown K 2009 Multiagent Systems: Algorithmic, Game-Theoretic, and
Logical Foundations (New-York: Cambridge University Press) p 532
[5] Belardinelli F and Argento F 2017 Multi-Agent Systems and Agreements Technologies (15th
European Conf., EUMAS 2017, and 5th Int. Conf., AT 2017. Revised Selected Papers) p 554
[6] Waldrop M M 2018 Free Agents: Monumentally complex models are gaming out disaster
scenarios with millions of simulated people (Science) 360 (6385) 144-147
[7] Sycara K P 1998 Multiagent Systems AI Magazine 19(2) 79-92
[8] Yeoh W and Yokoo M 2012 Distributed Problem Solving AI Magazine 33(3) 53-65
[9] Pena D, Tschernykh A, Nesmachnow S, Massobrio R, Feoktistov A, Bychkov I, Radchenko G,
Drozdov A Y, and Garichev S N 2019 Operating cost and quality of service optimization for
multi-vehicle-type timetabling for urban bus systems J. of Parallel and Distributed Computing
133 272-285
[10] Adam N R and Dogramaci A 1979 Current Issues in Computer Simulation (New-York: Academic
Press) p 292
[11] Pooley R J 1987 An Introduction to Programming in Simula (Alfred Waller Ltd) p 344
[12] 2007 SIMSCRIPT III Users Manual (San Diego, CA : CACI Products Company) p 152
[13] Naraynasamy V, Wong K W , Rai S and Chiou A 2010 Complex Game Design Modeling
(Cultural Computing: Second IFIP TC 14, Entertainment Computing Symp., ECS2010) 65-74
[14] Sukhbatar S, Szlam A and Fergus R 2016 Learning Multiagent Communication with
Backpropagation Advances in Neural Information Processing Systems 2244-2252
[15] Havrylov S and Titov I 2017 Emergence of Language with Multi-agent Games: Learning to
Communicate with Sequences of Symbols Preprint cs-lg/1705.11192
[16] Rodriguez J 2018 Modern Game Theory and Multi-Agent Reinforcement Learning Systems
Towards Data Science.
[17] Sheremet I A 2010 Recursive Multisets and their Applications (Moscow: Nauka) p 292
[18] Sheremet I A 2011 Recursive Multisets and their Applications (Berlin: NG Verlag) p 249
[19] Sheremet I A 2018 Multiset Analysis of Consequences of Natural Disasters Impacts on Large-
Scale Industrial Systems (Data Science J.) 17:4 1-17
[20] Sheremet I 2019 Multiset-based assessment of resilience of sociotechnological systems to natural
hazards Natural Hazards - Risks, Exposure, Response, and Resilience ed J Tiefenbacher
(London: Intech Open)
[21] Sheremet I 2019 Multiset-Based Knowledge Representation for the Assessment and Optimization
of Large-Scale Sociotechnical Systems Enhanced Expert Systems ed P Vizureanu (London:
Intech Open)
[22] Sheremet I 2019 Unitary Multiset Grammars and Metagrammars Algorithmics and Applications
Enhanced Expert Systems ed P Vizureanu (London: Intech Open)
[23] Petrovskiy A B 2003 Spaces of sets and multisets (Moscow: URSS) p 248
[24] Petrovskiy A B 2018 Theory of measured sets and multisets (Moscow: Nauka) p 360
[25] Date C I 2012 An Introduction to Database Systems. 8th edition (London: Pearson) p 247
[26] Darwen H 2012 An Introduction to Relational Database Theory (London: bookboon.com) p 239
[27] Chomsky N 2002 Syntactic Structures (The Hague: Mouton de Gruyter) p 118
[28] Aumann R J and Maschler R B 1995 Repeated Games with Incomplete Information (Cambridge,
MA: MIT Press) p 360
[29] Jiiang D Y 2010 Situation Analysis of Double Action Games with Entropy (New-York: Science
Press)
[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