Wyniki wyszukiwania - BazTech

1

Equilibrium stacks for a non-cooperative game defined on a product of staircase-function continuous and finite strategy spaces

Romanuke Vadim

Journal of Mathematics and Applications

|

2023

|

Vol. 46

79--114

EN

A method of solving a non-cooperative game defined on a product of staircase-function strategy spaces is presented. The spaces can be finite and continuous as well. The method is based on stacking equilibria of “short” non-cooperative games, each defined on an interval where the pure strategy value is constant. In the case of finite non-cooperative games, which factually are multidimensional-matrix games, the equilibria are considered in general terms, so they can be in mixed strategies as well. The stack is any combination (succession) of the respective equilibria of the “short” multidimensional-matrix games. Apart from the stack, there are no other equilibria in this “long” (staircase-function) multidimensional-matrix game. An example of staircase-function quadmatrix game is presented to show how the stacking is fulfilled for a case of when every “short” quadmatrix game has a single pure-strategy equilibrium. The presented method, further “breaking” the initial staircase-function game into a succession of “short” games, is far more tractable than a straightforward approach to solving directly the “long” non-cooperative game would be.

2

Traveling salesman problem parallelization by solving clustered subproblems

Romanuke Vadim

Foundations of Computing and Decision Sciences

|

2023

|

Vol. 48, No. 4

453--481

EN

A method of parallelizing the process of solving the traveling salesman problem is suggested, where the solver is a heuristic algorithm. The traveling salesman problem parallelization is fulfilled by clustering the nodes into a given number of groups. Every group (cluster) is an open-loop subproblem that can be solved independently of other subproblems. Then the solutions of the respective subproblems are aggregated into a closed loop route being an approximate solution to the initial traveling salesman problem. The clusters should be enumerated such that then the connection of two “neighboring” subproblems (with successive numbers) be as short as possible. For this, the destination nodes of the open-loop subproblems are selected farthest from the depot and closest to the starting node for the subsequent subproblem. The initial set of nodes can be clustered manually by covering them with a finite regular-polygon mesh having the required number of cells. The efficiency of the parallelization is increased by solving all the subproblems in parallel, but the problem should be at least of 1000 nodes or so. Then, having no more than a few hundred nodes in a cluster, the genetic algorithm is especially efficient by executing all the routine calculations during every iteration whose duration becomes shorter.

3

Impact of starting outlier removal on accuracy of time series forecast ING

Romanuke Vadim

Maritime Technical Journal

|

2022

|

nr 1 (224)

1--15

EN

The presence of an outlier at the starting point of a univariate time series negatively influences the forecasting accuracy. The starting outlier is effectively removed only by making it equal to the second time point value. The forecasting accuracy is significantly improved after the removal. The favorable impact of the starting outlier removal on the time series forecasting accuracy is strong. It is the least favorable for time series with exponential rising. In the worst case of a time series, on average only 7 % to 11 % forecasts after the starting outlier removal are worse than they would be without the removal.

PL

Wartość odstająca w punkcie początkowym jednowymiarowego szeregu czasowego negatywnie wpływa na dokładność prognozowania. W ramach przeprowadzonych badań dokonano analizy wpływu usunięcia wartości odstającej poprzez zrównanie jej z wartością drugiego punktu cza-sowego. Uzyskane wyniki wskazują, że przyjęta metoda znacznie poprawia dokładność progno-zowania dla większości szeregów czasowych. Jednak w przypadku szeregów czasowych z wykładniczym wzrostem, metoda okazała się mniej skuteczna. Minimalny wzrost dokładności prognozowania wynosił w tym przypadku od 7 % do 11 %.

4

Arima Model optimal selection for time series forecasting

Romanuke Vadim

Maritime Technical Journal

|

2022

|

nr 1 (224)

28--40

EN

A fast-and-flexible method of ARIMA model optimal selection is suggested for univariate time series forecasting. The method allows obtaining as-highly-accurate-as-possible forecasts auto-matically. It is based on effectively finding lags by the autocorrelation function of a detrended time series, where the best-fitting polynomial trend is subtracted from the time series. The fore-casting quality criteria are the root-mean-square error (RMSE) and the maximum absolute error (MaxAE) allowing to register information about the average inaccuracy and worst outlier. Thus, the ARIMA model optimal selection is performed by simultaneously minimizing RMSE and Max-AE, whereupon the minimum defines the best model. Otherwise, if the minimum does not exist, a combination of minimal-RMSE and minimal-MaxAE ARIMA models is used.

PL

W pracy zaproponowano szybką i elastyczną metodę optymalnego doboru modelu ARIMA na potrzeby prognozowania szeregów czasowych z jedną zmienną. Metoda pozwala na uzyskanie możliwie najdokładniejszych prognoz, opierając się na skutecznym znajdowaniu opóźnień. Po-szukiwanie opóźnień realizowane jest za pomocą funkcji autokorelacji szeregu czasowego bez trendu, w którym najlepiej dopasowany trend wielomianowy jest odejmowany od szeregu cza-sowego. Za kryteria jakości prognozowania przyjęto średni błąd kwadratowy (RMSE) i maksy-malny błąd bezwzględny (MaxAE), które pozwoliły na rejestrację informacji o średniej i maksymalnej niedokładności. Optymalny dobór modelu ARIMA odbywa się poprzez jednoczesną minimalizację RMSE i MaxAE, dla której wartość minimalna określa najlepszy model. W przeciw-nym razie, jeśli minimum nie istnieje, używana jest kombinacja modeli ARIMA z minimalnym RMSE i minimalnym MaxAE.

5

Time-unit shifting in 2-person games played in finite and uncountably infinite staircase-function spaces

Romanuke Vadim

Journal of Mathematics and Applications

|

2022

|

Vol. 45

133--179

EN

A computationally efficient and tractable method is presented to find the best equilibrium in a finite 2-person game played with staircase-function strategies. The method is based on stacking equilibria of smaller-sized bimatrix games, each defined on a time unit where the pure strategy value is constant. Every pure strategy is a staircase function defined on a time interval consisting of an integer number of time units (subintervals). If a time-unit shifting happens, where the initial time interval is narrowed by an integer number of time units, the respective equilibrium solution of any “narrower” subgame can be taken from the “wider” game equilibrium. If the game is uncountably infinite, i. e. a set of pure strategy possible values is uncountably infinite, and all time-unit equilibria exist, stacking equilibria of smaller-sized 2-person games defined on a rectangle works as well.

6

Equilibrium stacks for a three-person game on a product of staircase-function continuous and finite strategy spaces

Romanuke Vadim

Foundations of Computing and Decision Sciences

|

2022

|

Vol. 47, No. 1

27--64

EN

A method of solving a three-person game defined on a product of staircase-function strategy spaces is presented. The spaces can be finite and continuous. The method is based on stacking equilibria of “short” three-person games, each defined on an interval where the pure strategy value is constant. In the case of finite three-person games, which factually are trimatrix games, the equilibria are considered in general terms, so they can be in mixed strategies as well. The stack is any interval-wise combination (succession) of the respective equilibria of the “short” trimatrix games. Apart from the stack, there are no other equilibria in this “long” trimatrix game. An example is presented to show how the stacking is fulfilled for a case of when every “short” trimatrix game has a pure-strategy equilibrium. The presented method, further “breaking” the initial “long” game defined on a product of staircase-function finite spaces, is far more tractable than a straightforward approach to solving directly the “long” trimatrix game would be.

7

Zero-sum games on a product of staircase-function finite spaces

Romanuke Vadim

Journal of Mathematics and Applications

|

2021

|

Vol. 44

75--91

EN

A tractable method of solving zero-sum games defined on a product of staircase-function finite spaces is presented. The method is based on stacking solutions of “smaller” matrix games, each defined on an interval where the pure strategy value is constant. The stack is always possible, even when only time is discrete, so the set of pure strategy possible values can be continuous. Any combination of the solutions of the “smaller” matrix games is a solution of the initial zero-sum game.

8

Acceptable-and-attractive Approximate Solution of a Continuous Non-Cooperative Game on a Product of Sinusoidal Strategy Functional Spaces

Romanuke Vadim

Foundations of Computing and Decision Sciences

|

2021

|

Vol. 46, No. 2

173--197

EN

A problem of solving a continuous noncooperative game is considered, where the player’s pure strategies are sinusoidal functions of time. In order to reduce issues of practical computability, certainty, and realizability, a method of solving the game approximately is presented. The method is based on mapping the product of the functional spaces into a hyperparallelepiped of the players’ phase lags. The hyperparallelepiped is then substituted with a hypercubic grid due to a uniform sampling. Thus, the initial game is mapped into a finite one, in which the players’ payoff matrices are hypercubic. The approximation is an iterative procedure. The number of intervals along the player’s phase lag is gradually increased, and the respective finite games are solved until an acceptable solution of the finite game becomes sufficiently close to the same-type solutions at the preceding iterations. The sufficient closeness implies that the player’s strategies at the succeeding iterations should be not farther from each other than at the preceding iterations. In a more feasible form, it implies that the respective distance polylines are required to be decreasing on average once they are smoothed with respective polynomials of degree 2, where the parabolas must be having positive coefficients at the squared variable.

9

Pilot symbol error re-orthogonalization in 2×2 mimo systems of wireless communication

Romanuke Vadim

Scientific Journal of Polish Naval Academy

|

2020

|

R. 61 nr 3 (222)

43--67

EN

A 2×2 MIMO wireless communication system with channel estimation is simulated, in which two transmit, and two receive antennas are employed. The orthogonal pilot signal approach is used for the channel estimation, where the Hadamard sequences are used for piloting. Data are modulated by coherent binary phase-shift keying, whereupon an orthogonal space-time block coding subsystem encodes information symbols by using the Alamouti code. Based on the simulation, it is ascertained a possibility to decrease the bit-error rate by substituting the Hadamard sequences for the sequences having irregular structures, and constituting the eight known orthogonal bases. Considering a de-orthogonalization caused by two any pilot sequence symbol errors, the bit-error rate is decreased by almost 2.9 %. If de-orthogonalizations are caused by two repeated indefinite, and definite pilot sequence symbol errors, the decrements are almost 16 % and 10 %, respectively. Whichever sequences are used for piloting, the 2×2 MIMO system is ascertained to be resistant to the de-orthogonalization if the frame is of 128 to 256 symbols piloted with 32 to 64 symbols, respectively.

PL

W pracy przedstawiono symulowany system komunikacji bezprzewodowej 2×2 MIMO z oszacowaniem kanału, składający się z dwóch anten nadawczych i dwóch anten odbiorczych. W procesie szacowania kanału zastosowano podejście ortogonalnego sygnału pilotującego z wykorzystaniem sekwencji Hadamarda. Na potrzeby badań symulacyjnych przyjęto modulowanie danych za pośrednictwem spójnego binarnego kluczowania z przesunięciem fazowym, podczas gdy ortogonalny podsystem kodowania bloków czasoprzestrzennych odpowiedzialny był za kodowanie informacji z wykorzystaniem kodu Alamouti. Na podstawie symulacji ustalono możliwość zmniejszenia współczynnika błędnych bitów przez zastąpienie sekwencji Hadamarda sekwencjami należącymi do ośmiu znanych baz ortogonalnych i charakteryzującymi się nieregularnymi strukturami. W przypadku deortogonalizacji wynikającej z dwóch dowolnych błędów symboli sekwencji pilotujących, współczynnik ten został zmniejszony o prawie 2.9 %. Jeśli deortogonalizacje są spowodowane przez dwa powtarzające się błędy symboli sekwencji pilotujących, nieokreślone i określone błędy uległy zmniejszeniu o odpowiednio 10 % i 16 %. Bez względu na to, które sekwencje zostały użyte do pilotowania, wykazano odporność systemu 2×2 MIMO na deortogonalizację w przypadku, gdy ramka zawierała od 128 do 256 symboli, a rozmiar sekwencji pilotującej mieścił się w zakresie od 32 do 64 symboli.

10

Doppler Effect in 2 × 2 to 4 × 4 MIMO systems of wireless communication with orthogonal pilot channel estimation

Romanuke Vadim

Scientific Journal of Polish Naval Academy

|

2020

|

R. 61 nr 4 (223)

5--20

EN

The Doppler effect in 2×2, 3×3, 4×4 MIMO wireless communication systems with channel estimation is studied. The orthogonal pilot signal approach is used for the channel estimation, where the Hadamard sequences are used for piloting, along with the eight alternative orthogonal sets similar to the Walsh set. MIMO transmissions are simulated for 10 cases of the frame length and pilot symbols per frame by no Doppler shift to 1100 Hz Doppler shift with a step of 100 Hz. Based on the simulation, it is ascertained that MIMO transmissions of shorter frames are less sensitive to the Doppler effect. Despite increasing the number of antennas does not mitigate the Doppler effect, and the bit-error rate performance of 4×4 MIMO systems worsens faster than that of 2×2 MIMO systems, it is better to use the maximum number of antennas. The Doppler effect does badly worsen the performance at highway and express train speeds (100 km/hr, and faster), leaving only possibility to further shorten transmissions. This, however, decreases the data rate, but the respective accuracy-versus-data-rate tradeoff must be acceptable.

PL

W pracy przedstawiono badania efektu Dopplera w systemach komunikacji bezprzewodowej 2×2, 3×3, 4×4 MIMO z estymacją kanału. W procesie szacowania kanału zastosowano podejście sygnału pilotującego w wykorzystaniem sekwencji Hadamarda, wraz z ośmioma alternatywnymi zestawami baz ortogonalnych, podobnymi do zestawu Walsha. Transmisje MIMO zostały zasymulowane dla 10 przypadków, różniących się długością ramki i symboli pilotujących oraz częstotliwością Dopplera, której zakres zmieniał się od 0 do 1100 Hz z krokiem 100 Hz. Na podstawie badań symulacyjnych wykazano, że transmisje krótszych ramek MIMO są mniej wrażliwe na efekt Dopplera. Pomimo, że zwiększenie liczby anten nie zmniejsza efektu Dopplera, a wydajność współczynnika błędnych bitów w systemach 4×4 MIMO pogarsza się szybciej niż w systemach 2×2 MIMO, przeprowadzone badania wskazują na korzyści z zastosowania większej ilości anten. Efekt Dopplera znacznie pogarsza jakość transmisji przy prędkościach powyżej 100 km/h (ruch samochodów na autostradach lub pociągów ekspresowych), determinując potrzebę redukcji przesyłanych danych. To jednak zmniejsza szybkość transmisji danych, ale odpowiedni kompromis między dokładnością a szybkością przesyłania danych musi być akceptowalny.

11

Finite approximation of continuous noncooperative two-person games on a product of linear strategy functional spaces

Romanuke Vadim

Journal of Mathematics and Applications

|

2020

|

Vol. 43

123--138

EN

A method of the finite approximation of continuous non-cooperative two-person games is presented. The method is based on sampling the functional spaces, which serve as the sets of pure strategies of the players. The pure strategy is a linear function of time, in which the trend-defining coefficient is variable. The spaces of the players’ pure strategies are sampled uniformly so that the resulting finite game is a bimatrix game whose payoff matrices are square. The approximation procedure starts with not a great number of intervals. Then this number is gradually increased, and new, bigger, bimatrix games are solved until an acceptable solution of the bimatrix game becomes sufficiently close to the same-type solutions at the preceding iterations. The closeness is expressed as the absolute difference between the trend-defining coefficients of the strategies from the neighboring solutions. These distances should be decreasing once they are smoothed with respective polynomials of degree 2.

12

Division-by-q dichotomization for interval uncertainty reduction by cutting off equal parts from the left and right based on expert judgments under short-termed observations

Romanuke Vadim

Foundations of Computing and Decision Sciences

|

2020

|

Vol. 45, No. 2

125--155

EN

A problem of reducing interval uncertainty is considered by an approach of cutting off equal parts from the left and right. The interval contains admissible values of an observed object’s parameter. The object’s parameter cannot be measured directly or deductively computed, so it is estimated by expert judgments. Terms of observations are short, and the object’s statistical data are poor. Thus an algorithm of flexibly reducing interval uncertainty is designed via adjusting the parameter by expert procedures and allowing to control cutting off. While the parameter is adjusted forward, the interval becomes progressively narrowed after every next expert procedure. The narrowing is performed via division-by-q dichotomization cutting off the q–1-th parts from the left and right. If the current parameter’s value falls outside of the interval, forward adjustment is canceled. Then backward adjustment is executed, where one of the endpoints is moved backwards. Adjustment is not executed when the current parameter’s value enclosed within the interval is simultaneously too close to both left and right endpoints. If the value is “trapped” like that for a definite number of times in succession, the early stop fires.

13

A minimax approach to mapping partial interval uncertainties into point estimates

Romanuke Vadim

Journal of Mathematics and Applications

|

2019

|

Vol. 42

147--185

EN

A problem of simultaneously reducing a group of interval uncertainties is considered. The intervals are positively normalized. There is a constraint, by which the sum of any point estimates taken from those intervals is equal to 1. Hence, the last interval is suspended. For mapping the interval uncertainties into point estimates, a minimax decision-making method is suggested. The last interval’s point estimate is then tacitly found. Minimax is applied to a maximal disbalance between a real unknown amount and a guessed amount. These amounts are interpreted as aftermaths of the point estimation. According to this model, the decision-maker is granted a pure strategy, whose components are the most appropriate point estimates. Such strategy is always single. Its components are always less than the right endpoints. The best mapping case is when we obtain a totally regular strategy whose components are greater than the left endpoints. The irregular strategy’s components admitting many left endpoints are computed by special formulae. The worst strategy exists, whose single component is greater than the corresponding left endpoint. Apart from the point estimation, irregularities in the decision-maker’s optimal strategy may serve as an evidence of the intervals’ incorrectness. The irregularity of higher ranks is a criterion for correcting the intervals.