Alternative routs of games with rigid schedule

Relay-races, as the basic conception of corporative-concurrent system description, may be applied to modeling of such fields of human activity, as industry, economics, politics, defense, sport, etc [1–4]. Due to conception announced teams, participating in relay-race, should to pass the distance, which is divided onto stages by relay-points, and team participants should to pass the stage in real physical time. Common case of random time relay-race simulation was considered in [2, 5], where for description of teams behavior such abstraction, as semi-Markov process was used. Semi-Markov process is quite universal mathematical apparatus, and when instead of random time emerges rigid schedule, it can be used too. Rigidity of stage passing time permit substantially simplify model of the system and calculation of forfeit, but also leads to substantial restrictions of results obtained.

On practice teams, participated the relay race, may vary their schedules, and for an external observer such variations are the stochastic ones. This permits to consider different combinations of schedules and to improve results obtained. Approaches to modeling of relay-races with rigid schedules and alternative routes are currently known insufficiently, that explains necessity and relevance of the investigations in this domain.

Fig. 1. Structure of alternative routes rigid schedule relay-race

The model of relay-race with M teams may be performed as M -parallel semi-Markov process [6–8]:

^{Ц    { ц} 1 ,..., Ц т ,..., Ц м ⁽ t ^)} ,

Цт {Am,hm (t)] , where t is the physical time; Цт is the ordinary semi-Markov process, Am is the set of states; hm (t) is the semi-Markov matrix, which describes an activity of the m-th team;

h j ( m ) , l ( m )

A m { a 0 ( m )’ ^a 1 ( m )’

...

, a j ( m )

a J ( m ) } ^;

^h m ⁽ t ) = [ h j ( m ),l ( m )⁽ t ) ] ;

^h m ( t ) = [ h j ( m ) , l ( m ) ( t ) ] , ¹ ^ j ( ^m ) , ^l ( ^m ) ^ J ;

K ( m , j )

J К h k ( m,j

⁽ t ) | k ( m , j ) = 1

(t), when l (m ) = j (m) +1,0 < j (m )< J (m)-1;

0 in all other cases .

Due to rigid schedule and quasi-stochastic principle of route selection [9]

h k ( m , j )⁽ t ) = p k ( m , j ) fk ( m , j )⁽ t ) = p k ( m , j ) ^S ^ t T k ( m , j ) J ^{,                             (6)}

where p k ( m j .) is the probability of route selection; f k ( m j .) ( t ) is the pure time density of residence the process at the state a j ( m ) with further switch to the state a j ( m ) + 1 on the k -th route; S ( t - T k ( m j )) is the Dirac S -function; T k ( mj ) is the rigid time of passing the j -th stage by participant of team m with k ( m , j ) -th route.

Comparison of classic competition [2] and competition with rigid schedule is shown on the fig. 2;

When classic competition, times of semi-Markov process residence in states a j .( m ) and a i ( n ) are equal to f k ( mj ) ( t ) and f^ nni ) ( t ) , correspondingly. When rigid schedule times are equal to S [ t - T k ( m j ) J and S [ t - T ni ) J . Formulae, which describe weighted time density and probabilities of winning the j -th stage of race by m -th team, if all participating teams start their stages simultaneously, are as follows:

M

^ wm , j ) ( t ) = f k ( m , j ) ( t ) П [ 1 — F l ( n,i ) ( t ) J ,                                (7)

n = 1 n # m

^ . m , j ) ( t ) =

^

" Wm , j ) = Jv^ m , j )⁽ t ) ^dt ;

^S ( t ^- T k ( m , j ) ) ,w^hen T k ( m , j ) nonsense, otherwise ,

= ^min { T l ( 1, . )

T .    . T.

T k ( m , j ),..., T l ( M , i ) } ^;

w nk (m, j)

!,when T k ( m , j ) 0, otherwise ,

= ^min { T l ( 1, . )

T .    . T.

T k ( m , j ),..., T l ( M , i ) } ,

t where F (t) = J f. (5)d0 is the distribution function; 9is the auxiliary argument.

Pure time density of winning the j -th stage of race by m -th team is as follows:

w ^ m tt

V k ( m , j )⁽ t ) = ^w       •                                        ⁽¹¹⁾

ⁿ k ( m , j )

When paired competition, formulae, which describe the time density of waiting by m -th, winner, team until n -th, loser, team, finishes the stage, are as follows:

^

n( t) J fk (mj)(^}-f n ,0( t+e) de

^ k ( m , j ) ^ l ( n , i )⁽ t ) =          _TO

J F k ( m , j )⁽ t ) ^dF l ( n , i )⁽ t )

Ф к ( m , j ) ^ l ( n , i ) ⁽ t )

^S [ t - T l ( n , i ) ⁺ T k ( m , j ) ^] , whenTk ( m , j )

^- T l ( n , i );

nonsense, otherwise,

where n ( t ) is the Heaviside function;

n ( t ) =

0, when t - 0;

• 1,    otherwise.

It is necessary to admit, that in the case under consideration, unlike the case considered at [2], the draw effect emerges. It is caused with the infinitesimal probability of two or more teams stage passing times coincidence when time intervals are a random ones, and quite real rigid schedule case, when some time intervals are quite the same (the case is shown on the fig. 2, b , bottom line).

Due to the fact, that for all teams, participated in a race, number of the stage j at every relay point may to increment only, for external viewer sequence of switches during relays in the system as a whole has the nature of evolution [10–13], which develops from functional state, being defined with vector

^[14] ( a 0 ( 1 )^,—^, a 0 ( m )

a 0 ( M ) ) till functional state ( a J ( 1 ),

...

^{, a} J ( m ) ^,

...,

a J ( M ) ) . Trajectory of evolution

depends of routes, which every team select for passing of proper stages and schedules which develop from routes selected. Owing to random character of routes selection trajectory of evolution is the random one. Common number of routes, on which m -th team as a whole may overcome the distance is equal to

J

K ( m ) = П K ( m , j ) ,                               (14)

j = 1

where K ( m , j ) is the common number of routs of m -th team j -th stage.

Common number of different variants of rigid relay-races is as follows:

M

K = П K ( m ) .                              (15)

m = 1

• 2.    Recursive procedure of relay-race evolution analysis

Let us select from all possible routes on which m-th team may overcome the distance the к (m) -th variant, in which routes к(m,1), ..., к(m, j), ..., к(m, J) are selected (note, that in common case к(m,1)^ .. ^ к(m, j)^ .. ^ к(m, J), since these are different functions of m and j). So 1 (m) -th and K(m) -th variants correspond to combinations 1(m,1), ..., 1(m, j), ..., 1(m, J) and K (m,1), ...,

K ( m , j ) , ..., K ( m , J ) respectively. Such a selection should be executed on routes of all other teams. For selected routes the recursive procedure of relay-race evolution may be worked out. For this purpose auxiliary time 6 should be introduced. Recursive procedure of evolution analysis is as follows.

Initial functional state of the semi-Markov process (1) as a whole is ( a 0 ( 1 ),..., a ₀ ( m ),..., a ₀ ( M ) ) , where elements of vector are numbers of relay-race starting points. All teams start race simultaneously, and into auxiliary time e next substitutions should be made:

^e 0 ⁽¹⁾ ^ ^Т к ( 1,1 ) , ..., ^e 0 ^{( m} ) ^ ^Т к ( m ,1 ) , ..., ^e 0 ⁽ M ) ^ ^Т к ( M ,1 ) , ⁽¹⁶⁾ where arrow ^ indicates the direction of substitution; index means the quantity of previous switches.

Rigid time intervals 0 ₀ ( 1 ) ,..., 0 ₀ ( m ) ,..., 0 ₀ ( M ) compete between them, and result of competition is winning the stage by those teams, which have minimal value of 0 . This values fulfill the subset 0 0 :

0 0 = { 0 0* ( u ) ,..., 0 0 ( v ) ,..., 0 0 ( w ) } ;                                  (17)

{00 (u),..., 00 (v),..., 00 (w)} = min 0 {00 (1),..., 00 (m),..., 00 (M)}, where u, v, w are auxiliary indices for nomination the number of team.

It is obviously, that

_*         _* У X               _* У X               _* У X                                                          , , - ,

00 ^ 00 (u) =... = 00 (v) =... = 00 (w) .

i. e. teams with numbers

S (1) = 00|.(20)

Due to the switches, next substitutions should be maid to prepare next step of recursion: index of 0 ₀ ( m ) , 1 <  m <  M . should be replaced with index of s ( 1 ) ^ 0 + S ( 1 ) ; time intervals, which will compete further should be replaced as follows

0 ₀ ( m ) - 0 0, when m ё N * ;

⁰ s ( 1 ) ^{( m} ) ^ *

T k ( m ,2 )^{,when m e} N 0 ;

indices i ( m ) of elements of vector ( a ₀ ( 1 ),..., a ₀ ( m ),..., a ₀ ( M ) ) should be replaced as follows:

l ( m )

^ *

0 ( m ) , when m ё N * ;

1 ( m ) , when m e N * .

In such a way on the second step or recursion rigid time intervals 0 _s ( 1 ) ( 1 ) ..... 6 , ( 1 ) ( m ) ..... 0 ₀₎ ( M )

will compete between them.

Let us assume that on the r-th step of the recursion vector of functional state of semi-Markov process is (aj(1)-1..... aj(m)-p..., aj(M)—1), and time intervals 0s(r-1)(1)..... 0s(r-1)(m)..... 0s(r-0M) com- pete between them. Result of competition is winning the stage by those teams, which have minimal value of 0. This values fulfill the subset 00(r-1):

0s(r-1) = {0s(r-1) (u)..... 0s(r-1) (v)..... 0s(r-1) (w)} ;

{ ⁰ s ( r - 1 ) ⁽ u ) ..... ⁰ s ( r - 1 ) ⁽ v ) ..... ⁰ s ( r - 1 ) ⁽ w ) ] = ^min ₀ { ⁰ S ( r - 1 ) ⁽¹⁾..... ⁰ s ( r - 1 ) ^{( m} ) ..... ⁰ s ( r - 1 ) ^{( M} ) ] .

It is obviously, that

**     **

0s(r-1) ^ 0s(r-1) (u) = ... = 0s(r-1) (v) = ... = 0s(r-1) (w) .

i.e. teams with numbers

**    **

Ns(r-1) ={arg0s(r-1) (u)]. .... arg0s(r-1) (v)]. .... arg0s(r-1) (w)]]

win the competition. Quantity of switches on the r -th step of recursion is equal to cardinal number of ^{subset 0} * s ₍ r - 1 ) :

s ( r) = 0s(r-1)| .

Due to the switches, following substitutions should be maid to prepare next step of recursion:

index of 9 s ( _r - 1 ) ( m ) 1 <  m <  M , should be replaced with index s ( r ) ^ s ( r - 1 ) + s ( r ) ; time intervals, which will compete further should be replaced as follows –

⁹ s ( r - 1 )^{( m} )^{- 9} s ( r - 1 ),^{when m} ^ N * ( r - 1 );

⁹ s ( r ) ( m ) ^ “

T k ( m , j + 1 )^,when m ^e N * ( r - 1 );

components of vector ( a j .( 1 ^ - 1 ,

...

^, a j ( m ) - 1 ^,

...

, a j ( M ) - 1 ) should be replaced as follows -

a j ( m ) - 1 ^ “

a j ( m ) - 1 ^,when m ^ N * ( r - 1 ); _ a j ( m ) ,w^hen m ^e N * ( r - 1 ).

In

⁹ s ( r ) ( 1 ) ^,

such a way on the   ( r +1)-th   step or

recursion rigid time

intervals

...

, ⁹ s ( r )⁽ m ) ,

...

, ⁹ _s ( r ) ( M ) compete between them.

Let assume that on the lust but one step of recursion

( ^a J ( 1 ), ⁹ mj -3¹

...

, a j ( u ) - 1 ,

...

, a J ( v ) - 1 ,

...

'^{, a} J ( m )^,

..

., a j ( w ) - 1 ,

...

, a J ( м ) ) ,

after MJ – 3 switches vector became and rigid time intervals

( k ) , 9 _MJ - 3 ( l ) , 9 _MJ - 3 ( n ) compete between them only. Let us also assume, that minimal values of

• 9 ,    which fulfill the subset © J_{M - 3} , are

® JM - 3 ^- { ⁹ JM - 3 ^{( u} ) , ⁹ JM - 3 ^{( w} ) } ^;

{ ⁹ JM - 3 ^{( u} ) ,

...

, ⁹ jm - 3 ⁽ w ) } £ ^min ₉ ^{{ 9} mj - 3 ^{( u} ) , ⁹ mj - 3 ^{( v} ) , ⁹ mj - 3 ⁽ w ) } . ⁹ MJ - 3 ^ ⁹ MJ - 3 ^{( u} ) ^{- 9} MJ - 3 ^{( w} ) ,

i. e. teams with numbers u and w win the competition.

Due to (29) and (30) on the last but one step two switches occur, namely u -th and w -th teams reach

the

( ^a J ( 1 ),

final point of race and after that functional state became

...

, a j ( u ),

...

, ^a J ( v ) - 1 ,

...

^{, a} J ( m )^,

..

., a j ( w ),

...

, a j ( м ) ) , i.e. w —th team on the last step should finish the

distance at the time

⁹ MJ - 3 + 2 ⁽ l ) - ⁹ MJ - 3 ⁽ l ) ⁹ MJ - 3 ,

and relay race in the state ( a j ( 1 ),

...

'^, a J ( m )^,

..

., a J ( M ) ) will over.

• 3.    Schedule effectiveness evaluation recursive procedure

Quite natural for evaluation of rigid schedule effectiveness is the model, in which all possible pairs of teams, f.e. m -th and n -th, and forfeit ^, distributed at the time, are considered. Distributed , . .                                 ,                                i(m), j(n)        ,                                                    ,                                   .

forfeit, in turn, is defined as payment, which the n -th team pays to the m -th team, namely

• > 0, when i ( m ) > j ( n ) ;

^ ( m ) , j ( n ) ( t ) j ^{- 0 when} i ( ^m ) >  ^j ( n ) ; <  0, when i ( m ) < j ( n ) ,

where 0 <  i ( m ) , j ( n ) < J .

For evaluation of common forfeit, which the m-th team receives from the n-th team, one can to use the recursive procedure, described above. At initial two-elements functional state (a0(m), a0(n)) substitu- tions

• ⁹ 0 ^{( m} ) ^ T k ( m ,1 ) , ⁹ 0 ^{( n} ) ^ T k ( n ,1 )

  
  

should be done.

In this simplified two-parallel semi-Markov process only time intervals 0 ₀ ( m ) , 0 ₀ ( n ) compete between them. Possible result of competition may be the next:

• a)    wins the team m , if 0 0 ( m ) <  0 0 ( n ) , then 0 0 = { 0 * ( m ) } = min { 0 ₀ ( m ) , 0 ₀ ( n ) } , 0 0 ^ 0 0 ( m ) ,

s ( 1 ) = 1;

• b)    wins the team n , if 0 ₀ ( m ) >  0 ₀ ( n ) , then 0 0 = { 0 * ( n ) } = min { 0 ₀ ( n ) , 0 ₀ ( n ) } , 0 0 ^ 0 0 ( n ) ,

s (1) = 1;

c) competition is draw, if 0 ₀ ( m ) = 0 ₀ ( n ) , then 0 0 = { 0 0 ( m ) , 0 0 ( m ) } = min { 0 ₀ ( m ) , 0 ₀ ( n ) } ,

_*        _* У    X      _* У    X       У Х

00 ^ 00 (m ) = 00 (m), s (1) = 2.

Value of forfeit is equal as follows:

^s(0) [k (m,1), k (n,1)] = J ^m),0(n) (t) dt , where insertion indices k(m,1),k(n,1) substitution (33).

Substitutions for preparing next step of recursion are as follows: indices of 0 ₀ ( m ) , 0 ₀ ( n ) , should be replaced with

s (1) ^ 0 + s (1);

1in the case a), b);

2in the case c);

time intervals, which will compete further and components of vector [ 0 ( m ) , 0 ( m ) ] should be replaced as follows

0S (1)(m ) ^ ‘

0s (1)(n ) ^ ‘

'^Tk ( m ,2 ) in ^the cases ^a), ^c); 0 ₀ ( m ) - 0 ₀ in the cases b); T k ( n ,2 ) in the cases b), c);

0 ₀ ( n ) - 0 0 in the cases a);

components of vector ( a ₀ ( _m ), a ₀ ( _n ) ) should be replaced as follows -

( ^a 1 ( m ), a 0 ( n ) ) ^{in the case a)};

( a 0 ( m ), a 0 ( n ) ) ^ ‘ ( a 0 ( m ), ^a 1 ( n ) ) in ^the case ^b) ( a 1 ( m ), a 1 ( n ) ) in ^the case ^c).

In such a way on the second step or recursion rigid time intervals 0 _S ( 1 ) ( m ) , 0 _S ( 1 ) ( n ) will compete between them.

Let us assume that on the r- th step of the recursion vector of functional state of semi-Markov process is ( a i ( _m ), a j ( n ) ) , and time intervals 0 _S ( r - 1 ) ( m ) , 0 _S ( _r - 1 ) ( n ) compete between them. Possible result of competition may be the next:

• a)    wins the team m , if         0 _S ( _r — 1 ) ( m ) < 0 _S ( _r — 1 ) ( n ) ,        then

⁰ S ( r - 1 ) = { ⁰ S ( r - 1 ) ( ^m ) } = ^min { ⁰ S ( r - 1 ) ( ^m ) , ⁰ S ( r - 1 ) ( ⁿ ) ] , ⁰ S ( r - 1 ) ^ ⁰ * ( r - 1 ) ( ^m ) , ^S ( ^r ) ^ ^S ( ^{r -} 1 ) ⁺ 1;

• b)    wins the team         n ,         if          6 s ( r - 1 ) ( m ) >  6 s ( r - 1 ) ( n ) ,         then

^Q S ( Г - 1 ) ⁼ { ⁶ 5 *( Г - 1 ) ( n ) } = min { ⁶ S ( Г - 1 ) ( n ) , ⁶ S ( Г - 1 ) ( n ) } , ⁶ * Г - 1 ) ^ ⁶ * Г - 1 ) ( n ) , ^S ( r ) ^ ^S ( r - 1 ) ⁺ 1;

• c)    competition is draw, if 6 s ( _{r - 1} ) ( m ) = 6 s ( _r - 1 ) ( n ) , then ⁰ S ( r - 1 ) = { ⁶ * r - 1 ) ⁽ m ) , ⁶ * ( r - 1 ) ⁽ m ) } = min { ⁶ s ( r - 1 ) ⁽ m ) , ⁶ s ( r - 1 ) ⁽ n ) ] ,          ⁶ * ( r - 1 ) ^ ⁶ S ( r - 1 ) ⁽ m ) = ⁶ * r - 1 ) ⁽ m ) ,

s ( r ) ^ s ( r - 1 ) + 2.

Value of forfeit is equal as follows:

⁶ s * ( r - 1 )

° s ( r - 1 ) ^[ k ( ^m , i ) , k ( n , ^j ) ] = J ° i ( m ) ,j ( n ) ( t ) dt .                             ⁽³⁹⁾

Substitutions for preparing next step of recursion are as follows:

indices of 6s(r-1) (m), 6s(r-1) (n), should be replaced with index of s (r) ^ s (r -1) + s (r), where s (r) is defined as (36);

time intervals, which will compete further and components of vector [ i ( m ) , j ( m ) ] should be replaced as follows

^T ( m , i + 1 ) ^{inthe casesa)}, ^c);

⁶ s ( r )⁽ m ) ^ ‘

• ⁶ s ( r - 1 )^{( m ) - 6} * r - 1 )^inthecaseb);

' T k ( n , j + 1 )^inthecases b),^c);

⁶ s ( r ) ⁽ n ) ^ ‘

• ⁶ s ( r - 1 ) ( ⁿ )^{- 6} s ( r - 1 )^{in the case} a);

components of vector [ i ( m ) , j ( n ) ] should be replaced as follows

( a i ( m ) + 1 , %- ( n ) ) ^{in the case a)};

( a i ( m ), a j ( n ) ) ^ ‘ ( a i ( m ), a j ( n ) + 1 ) in ^the case ^b);

( a i ( m ) + 1 , a j ( n ) + 1 ) in ^the case ^c).

So on the ( r+ 1)-th step or recursion rigid time intervals 6 s ( _r ) ( m ) , 6 s ( _r ) ( n ) will compete between them.

Let us assume, that on the last step of recursion only m -th team stays in race, and time, it spend from a previous switch till finishing J) -th stage, obtained on previous stage of recursion, is 6 * R 1 ). Value of forfeit on the last stage is is equal as follows:

⁶ s ( R - 1 )

^ s ( R - 1 ) ^[ k ( ^m , J ^- 1 ) , k ( n , J ) ] , = J ^CT J ( m ) - 1, J ( n ) ( t ) dt .                         ⁽⁴²⁾

For evaluation of common forfeit one should to evaluate probability of realization of the k ( m ) -th evolution trajectory of team m and k ( n ) -th evolution trajectory of team n . They are as follows:

J pk(m) =Пpk(m,i) , 1 ( m ^ k ( m ^ K^ ( m ) ;

i = 1

J p k( n )=П pk (n, j) , 1(n )^ k (n )^ K1(n ) .                                (43)

j = 1

Weighted sum of forfeit, which the m -th team receives from m -th team when realized k ( m ) -th and k ( n ) -th evolution trajectories is as follows:

R - 1

Gk(m),Цn) (m, n) = pk(m)pk(n) E ^(r-1) [k (m, i), k (n, j)] *

r = 0

Common sum of forfeit, which the m -th team receives from the n -th team is as follows:

Common sum of forfeit, which the m -th team receives from the n -th team, when is as follows

K( n)

^(m,n )=. E _ E °k (m), k (n)(m, n) *

k ( m ) = 1 ( m ) k ( m ) = 1 ( m )

Common sum of forfeit, which the m -th team receives from all other teams, is as follows

M ct(m)= E ^(m,n) *(46)

n = 1, n ^ m

It is necessary to admit, that common sum of forfeit, ^ ( m ) , the m -th team receives from all other teams, rigidly depends of schedules of all participants of races, including the m -th team and probabilities of routes selection. So to change a sum of forfeit ^ ( m ) one may both change m -th team schedule, and probabilities of selection possible routes on the every stage of the distance. This is essential obstacle, from point of view of putting and solving the forfeit optimization task.

Conclusion

Results obtained gives to system engineers and economists rather simple method of evaluation the effectiveness of those or that team management decisions on the basis of opponent teams behavior observation. Method of forfeit calculation proposed, gives a solid forfeit figure, based on the real knowledge of the strategies of opponents and possible changes of opponents plans. This, in turn, permits to use the game theory [15, 16] to work out a managing strategy, for increasing sum of forfeit which team under management receives from other teams, participated in relay race.

Further investigation in this area should be directed to finding common recommendation for scheduling m -th team strategy with optimization sum of forfeit [17].

The research was carried out within the state assignment of the Ministry of Education and Science of Russian Federation (No 2.3121.2017/PCH).