Discrete time, multiple participant, fixed rate queuing type problem and the corresponding congruence formulation

Question

The subject problem, as defined below, is one that both arises within and which was introduced to the author (of this post) through a recreational mathematics context. This statement is salient to the extent that the terminology associated with the context is retained (one may readily recast the problem using terminology arising from any number of other application contexts). In creating this post, I had to balance the factors of length v. properly defining the problem (along with showing the work that I have already done on it). I chose the latter over the former. I have both interspersed the questions/issues that I have throughout the presentation and also at the terminus of the post.

With this preamble noted, we proceed with the problem definition. Consider a situation, involving multiple participants and a set of rules, in which one is interested in determining the relationship(s) between the following: the discrete time values at which any given participant is granted preference for engaging in an action and (b) the relationship described in (a) across all participants. The following parameters are salient in further describing the problem:

N: Total number of participants {N: N $\in$ $\mathbb{N}$, N>1}.

k: Discrete measure of time {k: k $\in$ $\mathbb{N}$, k>0, $k_{j+1}$ - $k_{j}$ = 1 $\forall$ j}.

$s_{i}$: Speed of the $i^{th}$ participant {$s_{i}$: $s_{i}$ $\in$ $\mathbb{R}$, $s_{i}$ > 0, $\forall$ i}.

$\tau_{i}$: Turn meter fill rate of the $i^{th}$ participant {$\tau_{i}$: $\tau_{i}$ $\in$ $\mathbb{R}$,0 < $\tau_{i}$ < 1, $\forall$ i}.

$TM_{i}$(k): Turn meter value of the $i^{th}$ participant at time k {$TM_{i}$(k): $TM_{i}$(k) $\in$ $\mathbb{R}$,$TM_{i}$(0) = 0 $\forall$ i, $TM_{i}$(k) > 0, $\forall$ i, k $\neq$ 0}. Expressed in units of decimal percent.

$\sigma_{i}$: The number of discrete units of time that when multiplied by $\tau_{i}$,produces a value of $TM_{i}$(k) $\ge$ 1 {$\sigma_{i}$: $\sigma_{i}$ $\in$ $\mathbb{N}$, $\sigma_{i}$ > 0, $\forall$ i}.

TM$_{ic}$: Critical value of turn meter for the $i^{th}$ participant, which is a fixed value for each participant {TM$_{ic}$ $\in$ $\mathbb{R}$,TM$_{ic}$ $\ge$ 1, $\forall$ i}. Expressed in units of decimal percent.

$n_{i}$: Action (i.e. turn) number at issue for the $i^{th}$ participant {$n_{i}$: $n_{i}$ $\in$ $\mathbb{N}$, $n_{i}$ $\ge$0,$\forall$ i}. Clearly, every participant will have their own sequence of actions at issue that follows <0,1,2,3,...>. While one should specify between a specific turn number for the $i^{th}$ participant participant, the integer sequence of turns for the same and the set, such is not done here.

The following rules are operative:

1. The value of time, during the event, k, is the independent variable. It starts at a value of 0, increases by unity for each increment of time, and terminates at some unspecified positive value.
2. At k = 0, each participant starts with a turn meter value of 0. At each time increment, a certain amount, $\tau_{i}$, is added to the extant value of each combatant's turn meter.
3. Only one participant can be granted the ability to take engage in an an action (per value of k) and only participant can perform an action (i.e. take a turn) (per value of k). In order to perform an action at some value k, the participant must first 'win turn meter' at k - 1.
4. In order for a participant to 'win turn meter,' both of the following must hold: (a) the turn meter value for that participant must be equal to or greater unity and (b) that participant must have the highest turn meter value amongst all combatants.
5. For a participant that meets the first criteria of the fourth rule, but not the second, at some value k-1, the turn meter of the same is simply incremented by their base turn meter rate at the next value of k.
6. For a participant that 'wins turn meter' at k - 1, that participant is granted a turn at k and that participant's turn meter is reset to the appropriate value of $\tau$.

The following basic relationships hold. The first is the relationship between speed and turn meter rate (where c is a constant that is equal to 100/0.07):

$$\tau_{i} = \frac{s_{i}}{c} \tag{1}$$

Because the turn meter value increases by a fixed amount for each increment of discrete time, we can readily calculate the number of discrete time increments required for the turn meter value to be greater than or equal to unity.

$$\sigma_{i} = \lceil \tau_{i}^{-1} \rceil = \lceil c \times s_{i}^{-1} \rceil \tag{2}$$

The critical turn meter value for each participant can then readily be determined as:

$$TM_{ic} = \sigma_{i} \times \tau_{i} \tag{3}$$

One can readily substitute for $\sigma_{i}$, from equation (2) into equation (3) and rewrite the ceiling function as a floor function without much apparent avail. For the case of a single participant, we can define a nominal relationship between the tick value on which turns are won and the corresponding turn number. Turn $n_{i}$ is won on:

$$k = \sigma_{i}\times n_{i} \tag{4}$$

In the case of multiple participants, due to the rules listed above, equation (4) no longer generally holds. The approach taken thus far (clearly suboptimal), by the subject author, has been to include an additive, integer, term, to equation (4). This results in the following: turn $n_{i}$ is won on

$$k = \sigma_{i} \times n_{i} + a_{i}\tag{5}$$

Where a$_{i}$ has an initial value of zero and changes by +1 as a result of each turn meter conflict loss. Thusly, this term generally will only have fixed values over specific domains of k and n$_{i}$. Does this formulation specifically tell one what the turn meter value is for each combatant at some time value, k? No. Does this formulation specifically tell one what the turn number is that is at issue for a specific participant and at a specific value of k? No. It would appear that the answers to such questions would require knowing the value of a$_{i}$ at the previous turn and also at the current turn. With this clear and present issue noted, it is useful to consider the two approaches that have been undertaken, within the confines of a specific, easy, example.

Given three (N = 3) participant with speeds 190, 180 and 140, respectively, determine the relationship between the k and n for each participant. Using the above the equations, the respective values for $\tau$ are {0.133, 0.070, 0.098}, the respective values for $\sigma$ are {8, 15, 11} and the respective values for TM$_{c}$ are {1.064, 1.050, 1.078}.

The first method is to use procedural programming by creating a for loop with an internal check that implements the relevant rules from above. This is quite easily done. For k = 104-108 (as an example), the corresponding TM values are {0.931,0.980, 0.490}, {1.064, 0.980, 0.588}, {0.133, 1.120, 0.686}, {0.266, 0.070, 0.784}, and {0.399, 0.140, 0.882}. Combatant 1 wins turn meter for turn 13 at k = 105 (rather than at k = 104) and combatant 2 wins turn meter for turn 7 at k = 106 (rather than at k = 105). This method works but does not aid helping with questions along the lines of what should the speed of a fourth participant be so as to not interfere with the established order (or a similar question.

The second method is to approach the problem from a congruence perspective. Equation (4) can readily be rewritten as the following:

$$k\equiv0 (mod\sigma_{i}) \tag{6}$$

Similarly, for equation (5):

$$k\equiv a_{i} (mod\sigma_{i}) \tag{7}$$

Both forms require external tracking of the turn numbers. For the case in which conflicts are present (considered pairwise), one has $\sigma_{i} \times\ n_{i} + a_{i} = \sigma_{j} \times\ n_{j} + a_{j}$. Defining a$_{ji}$ as a$_{j} - a_{i}$, one can readily generate the turn based pairwise congruences and the time based congruence (using the Chinese remainder theorem).

For participants 1-2:

$n_{1} \equiv 2a_{21} \pmod {15}$

$n_{2} \equiv 1a_{21} \pmod {8}$

$k \equiv 105a_{1} + 16a_{2}\pmod {120}$

For participants 1-3:

$n_{1} \equiv 4a_{13}\pmod {11}$

$n_{3} \equiv 3a_{13}\pmod {8}$

$k \equiv 33a_{1} + 56a_{3}\pmod {88}$

For participants 2-3:

$n_{2}\equiv 8a_{23}\pmod {11}$

$n_{3}\equiv 11a_{23}\pmod {15}$

$k\equiv 121a_{2}+ 45a_{3}\pmod {165}$

From these equations one may readily see the following:

1. The first contested value of k is the minimum value of the three moduli (each being the pairwise least common multiple). In this case, this occurs at k = 88, which then results in $a_{1}$ being equal to 1 at k = 89.
2. Because of the first finding, the first contested value of k between 1 and 2 occurs at k = 105, rather than k = 120. This then results in $a_{2}$ being equal to 1 at k = 106.
3. For 1-2, after the first conflict, the ratio of turn numbers $\Delta{n_{1}}$ : $\Delta{n_{2}}$ becomes 2:1.
4. For 1-3, after the first conflict, the ratio of turn numbers $\Delta{n_{1}}$ : $\Delta{n_{3}}$ becomes 4:3.
5. For 2-3, after the first conflict, the ratio of turn numbers $\Delta{n_{2}}$ : $\Delta{n_{3}}$becomes 2:3 (rather than the nominal 8:11).

This example was referred to as easy due to the fact that participant 3 serves as an 'anchor'(i.e. $a_{3} = 0 \forall$ k). While this approach works it quickly becomes tedious and lengthy, in regards to implementation, as the number of participants increases.

Issues:

1. It appears clear to me that my formulation of the problem is, at best, incomplete, due to the fact that the formulation of equation (5) does not explicitly track $\tau$. This becomes a problem in situations where a conflict arises between two or more participants at say k-1 and results in the losing participant having a higher TM value at k when pitted against another participant for whom, normally, the critical turn meter value is greater than the losing participant. Furthermore, the use of the discrete time offsets (i.e. $a_{i}$) appear to increase the complexity of the formulation. Is there an alternative, better, formulation?
2. The congruence formulation mitigates the turn meter rate issue to a certain extent (the singular participant congruence relationship(s) are no longer valid once a loss occurs for a pairwise comparison) but determining the temporal order of occurrence of turns becomes a bear as the number of participants increases. This makes the approach more complex than simply using a for loop with values that are determined randomly. Is there an alternative, better, formulation?
3. Is there a reference (or multiple) where a similar problem is presented?
4. In all cases, there is a transient response and a steady state response. In certain cases, the steady state response is one that fits specific values of a remainder group (modulo n). Can this be used from a design perspective?
5. For a fixed value of $\sigma$, one can readily calculate the inclusive lower boundary and exclusive upper boundary for s, $\tau$ and $TM_{c}$. The inclusive lower boundary for $TM_{c}$, for any value of $\sigma$, is unity (as an example). Also, for any two participants, it is clear why the turn ratios are the ratios of the integer coefficients that precede each $a_{ji}$ term for the situation in which neither participant has an intervening losing conflict. Can these facts be used in a more intuitive way?

Thank you, in advance, for all of your help and kind consideration.