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

Proposition of multi-agent conflict situation simulation and reinforcement learning toolset with demonstration of early stage implementation

Jarosz Robert

Computer Science and Mathematical Modelling

|

2023

|

No. 17

13--22

EN

This paper introduces conceptual approach to modelling conflicts. A flexible framework compatible in development phase is presented. Model scalability, possibility of parallelization and computational distribution over network is discussed. As example of application there are presented two variants of classic game theory problems. At the end of the paper current problems are briefly stated and future work direction is presented.

PL

W artykule opisano koncepcję biblioteki do symulacji interakcji między graczami rozpatrującymi sytuacje konfliktowe. Opisano w nim założenia, w tym wymagania funkcjonalne dla oprogramowania. Przedstawiono proponowane rozwiązanie i wstępną wersję implementacji wraz z przykładami zastosowania koncepcji w klasycznych problemach teorii gier.

3

Kiedy można wygrać i jak wtedy grać, żeby wygrać?

Słanina Piotr

MINUT Matematyka i Informatyka na Uczelniach Technicznych

|

2022

|

Nr 4

1-15

PL

ednym z głównych problemów w grze kombinatorycznej jest wskazanie gracza, który jest w stanie zapewnić sobie zwycięstwo (tak zwane rozwiązanie gry). Jeżeli już to się uda, to czasami nadal nie będziemy w stanie wskazać temu graczowi, jak ma grać, aby wygrać. W tym artykule czytelnik zapozna się z najpopularniejszymi matematycznymi narzędziami, stosowanymi przy poszukiwaniu najlepszych strategii w grach kombinatorycznych. Ich opisy będą uzupełnione o przykłady gier. Będą się one pojawiały według stopnia trudności ich rozwiązania od najłatwiejszych do nierozwązanych po dzień dzisiejszy.

4

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.

5

Multi-criteria multi-stage game optimization

Lisowski Józef

Journal of Automation, Electronics and Electrical Engineering

|

2022

|

Vol. 4, No. 1

37--42

EN

The article presents a mathematical model of a multi-stage game of the process of safe control of a transport object in possible collision situations with other encountered objects, containing a description of state variables, state and control constraints, and sets of permissible object strategies. Multi-criteria optimization tasks were formulated in the form of positional and matrix games under the conditions of playing non-cooperative and cooperative control as well as non-game optimal control. The multi-criteria control algorithms corresponding to these tasks were computer simulated in Matlab / Simulink on the example of a real situation.

PL

W artykule przedstawiono model matematyczny wieloetapowej gry procesu bezpiecznego sterowania obiektem transportowym w możliwych sytuacjach kolizyjnych z innymi spotkanymi obiektami, zawierający opis zmiennych stanu, ograniczeń stanu i sterowania oraz zbiory dopuszczalnych strategii obiektów. Sformułowano wielokryterialne zadania optymalizacyjne w postaci gry pozycyjnej i macierzowej, w warunkach rozgrywającego sterowania niekooperacyjnego i kooperacyjnego oraz nierozgrywającego sterowania optymalnego. Algorytmy sterowania wielokryterialnego odpowiadające tym zadaniom poddano symulacji komputerowej w programie Matlab/Simulink na przykładzie rzeczywistej sytuacji.

6

Overview of selected reinforcement learning solutions to several game theory problems

Jarosz Robert

Computer Science and Mathematical Modelling

|

2022

|

No. 15-16

13--22

EN

This paper collects several applications of reinforcement learning in solving some problems related to game theory. The methods were selected to possibly show variety of problems and approaches. Selections includes Thompson Sampling, Q-learning, DQN and AlphaGo Zero using Monte Carlo Tree Search algorithm. Paper attempts to show intuition behind proposed algorithms with shallow explaining of technical details. This approach aims at presenting overview of the topic without assuming deep knowledge about statistics and artificial intelligence.

PL

Artykuł gromadzi wybrane podejścia do rozwiązania problemów z teorii gier wykorzystując uczenie ze wzmocnieniem. Zastosowania zostały dobrane tak, aby przedstawić możliwie przekrojowo klasy problemów i podejścia do ich rozwiązania. W zbiorze wybranych algorytmów znalazły się: próbkowanie Thompsona, Q-learning (Q-uczenie), DQN, AlphaGo Zero. W artykule nacisk położono na przedstawienie intuicji sposobu działania algorytmów, koncentrując się na przeglądzie technologii zamiast na technicznych szczegółach.

7

Analysis of selected reinforcement learning applications in contract bridge

Jarosz Robert

Computer Science and Mathematical Modelling

|

2022

|

No. 15-16

23--31

EN

This paper presents an overview of four selected solutions addressing problem of bidding in card game of contract bridge. In the beginning the basic rules are presented along with basic problem size estimation. Brief description of collected work is presented in chronological order, tracking evolution of approaches to the problem. While presenting solution a short description of mathematical base is attached. In the end a comparison of solution is made, followed by an attempt to estimate future development of techniques.

PL

Artykuł przedstawia cztery wybrane podejścia do rozgrywania licytacji w brydżu. W części pierwszej przybliżane są zasady brydża, stanu wiedzy na jego temat oraz krótkie oszacowanie poziomu komplikacji problemu. W części zasadniczej przedstawiono krótkie opisy podejść badaczy do problemu licytacji, badania przedstawione są w kolejności chronologicznej, ukazując ewolucję podejść do problemu. W trakcie opisywania rozwiązań, przybliżane są po krótce matematyczne zasady działania wykorzystanych mechanizmów uczenia maszynowego. Część końcowa podsumowuje przedstawione porównanie rozwiązań i oszacowanie kierunku przyszłego rozwoju.

8

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.

9

A communication network routing problem: Modeling and optimization using non-cooperative game theory

Dubey Sapana P., Kedar Ganesh D., Ghate Suresh H.

International Journal of Applied Mathematics and Computer Science

|

2021

|

Vol. 31, no. 1

155--164

EN

We consider a communication network routing problem wherein a number of users need to efficiently transmit their throughput demand in the form of data packets (incurring less cost and less delay) through one or more links. Using the game theoretic perspective, we propose a dynamic model which ensures unhindered transmission of data even in the case where the capacity of the link is exceeded. The model incorporates a mechanism in which users are appropriately punished (with additional cost) when the total data to be transmitted exceeds the capacity of the link. The model has multiple Nash equilibrium points. To arrive at rational strategies, we introduce the concept of focal points and get what is termed focal Nash equilibrium (FNE) points for the model. We further introduce the concept of preferred focal Nash equilibrium (PFNE) points and find their relation with the Pareto optimal solution for the model.

10

Analysis of the main body behaviour of non-point source pollution control based on multimodal game model

Li Xin, Shang Jie

Ecological Chemistry and Engineering. S

|

2021

|

Vol. 28, nr 4

563--579

EN

The issue of agricultural non-point source pollution has attracted the attention of the state and the masse. In the non-point source pollution control organizations which composed of the governments, farmers and fertiliser sellers, due to the characteristics of rational economic body, the phenomenon of ”market failure” and ”government failure” may occur in the process of non-point source pollution control. In this paper, the author applies game theory to analyse the main behaviour characteristics of the three main bodies, and constructs the incomplete information dynamic game model that the government, farmers and fertiliser sellers participate in. According to the results of the equilibrium solution of the Haysani Axiom model, it is found that the decisions made by the three bodies of the government, the fertiliser seller and the farmer in the behaviour choice stage have a great influence on the behaviour choice of the other two bodies, and the process of each strategy choice by the three bodies is a dynamic game process of the three bodies. Finally, according to the main influencing factors reflected in the equilibrium solution, proposed the related non-point source pollution control countermeasure suggestion to the government main body.

11

Applying chaos theory to risk management in a game of chance

Jóźwiak Ireneusz J., Mariański Aleksander, Switana Jan, Szczepanik Michał

Zeszyty Naukowe. Organizacja i Zarządzanie / Politechnika Śląska

|

2020

|

z. 144

195--211

EN

Purpose: The purpose of the paper is to illustrate the usage of techniques known from chaos theory to analyze the risk Design/methodology/approach: In this case the objects of application are winnings graphs of different poker players. Two types of players are presented; winning players (those with positive expected value) and breaking even players (expected value close to zero). Findings: Charts were analyzed with a fractal dimension calculated with the box method. Originality/value: Relation between fractal dimension and Hurst exponent is shown. Relation between risk in sense of chaos theory and players’ long-term winning is also described. Further applications of chaos theory to analyze the risk in games of chance are also proposed.

12

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.

13

A Simulation Study on the Impact of Activity Crashing on the Project Duration and Cost under Different Budget Release Scenarios

Song Jie, Servranckx Tom, Martens Annelies, Vanhoucke Mario

Annals of Computer Science and Information Systems

|

2020

|

Vol. 21

603--606

EN

The main goal of project control is to identify project opportunities or problems during project execution, such that corrective actions can be taken to bring the project in danger back on track when necessary. In this study, we define different scenarios to allocate the limited budget used for the cost of activity execution, delays, and corrective actions, according to the timing and amount of the budget release. A large computational experiment is conducted on real-life project data to evaluate the performance of each scenario. The results show that both the timing and amount of the budget release have an effect on project performance.

14

A model of transit freight distribution on a railway network

Kozachenko Dmytro, Skalozub Vladyslav, Gera Bogdan, Hermaniuk Yuliia, Korobiova Ruslana, Gorbova Aleksandra

Transport Problems

|

2019

|

T. 14, z. 3

17--26

EN

The peculiarity of the transit freight transportation by rail in international traffic is the fact that while performing transportation, the railway administrations are in competition among themselves. At the same time, the routes of cargo traffic volumes significantly depend on the conditions of transportation by railways of individual states. The mathematical model for the distribution of transit freight traffic volumes on the railway network, based on the methods of graph theory and game theory, was proposed in this article. The developed model enables the evaluation of the possibilities of attracting transit freight traffic volumes by individual railway administrations by changing the tariff value and transportation conditions.

15

Strategic analysis of implementation assets and threats

Piech Henryk, Grodzki Grzegorz

Journal of Applied Mathematics and Computational Mechanics

|

2019

|

Vol. 18, nr 2

65--74

EN

The main goal of the work is to support the marketing strategy using the characteristics created on the base of the game theory and uncertain knowledge. We want to elaborate algorithm, which does not require game-playing investigation. The additional aim consists in adaptating the game strategy to the concrete e.g. economic situation, described by selected, specific parameters. The next aim consists in exploitation uncertain knowledge as a data also. Game theory is the part of mathematics approach extended by Nash and adopted to psychology, sociology, politics, economics and informatics (artificial intelligence) problems. Game Theory provides mathematical tools for analyzing situations in which parties, called players, make decisions that are interdependent. This causes each player to consider the other player’s possible decisions, or strategies, in formulating his own strategy. This approach based on the assumption, that a solution to a game describes the optimal decisions of the players, who may have similar, opposed, or mixed interests, and the outcomes that may result from these decisions. This will be described as an example.

16

Best response dynamics for VLSI physical design placement

Rapoport Michael, Tamir Tami

Annals of Computer Science and Information Systems

|

2019

|

Vol. 18

147--156

EN

The physical design placement problem is one of the hardest and most important problems in micro chips production. The placement defines how to place the electrical components on the chip. We consider the problem as a combinatorial optimization problem, whose instance is defined by a set of $2$-dimensional rectangles, with various sizes and wire connectivity requirements. We focus on minimizing the placement area and the total wire length.

17

Resource allocation in LTE-unlicensed femtocell networks

Martyna J.

Przegląd Telekomunikacyjny + Wiadomości Telekomunikacyjne

|

2018

|

nr 8-9

839--843, CD

EN

In this paper, resource allocation technique for LTE femtocell network in licensed and unlicensed bands is proposed. Additionally, allocation of wireless resources to each mobile user in the Wi-Fi band occurs in parallel with the bandwidth allocation between competing users in LTE. To improve the performance of femtocells, a heuristic algorithm based on Kalai-Smorodinsky solution of bargaining problem is presented. The numerical simulation conf rms the correctness of the adopted mode.

PL

W artykule zaproponowano technike przydzielania zasobów dla sieci femtokomórkowej w licencjonowanych i nielicencjonowanych pasmach. Ponadto przydzielanie zasobów bezprzewodowych każdemu użzytkownikowi mobilnemu w paśmie Wi-Fi odbywa się równolegle z alokacją szerokości pasma pomiędzy konkurującymi użytkownikami w LTE. W artykule przedstawiono heurystyczny algorytm oparty na schemacie arbitrażowym Kalai-Smorodinsky'ego dla przetargu. Symulacja numeryczna potwierdza poprawność przyjętej metody alokacji zasobów.

18

Analiza wymuszeń pierwszeństwa przejazdu na skrzyżowaniach z punktu widzenia teorii gier

Jabłonka J.

Autobusy : technika, eksploatacja, systemy transportowe

|

2018

|

R. 19, nr 6

110--114, CD

PL

Założenie, że każdy uczestnik ruchu drogowego przestrzega przepisów, idealnie dostosowuje swoje zachowanie do warunków panujących na drodze, jest nierealistyczne, a jako podstawa podejmowania działań może doprowadzić do kolizji i wypadku. W artykule przedstawiono modele teoriogrowe pozwalające zrozumieć zachowania kierowców, którzy umyślnie wymuszają pierwszeństwo przejazdu, a ich jedyną motywacją jest jak najkrótszy czas przejazdu przez skrzyżowanie. Rozważane są dwa rodzaje sytuacji na skrzyżowaniach: z ruchem kierowanym i niekierowanym ze znakiem STOP. Przedstawione modele matematyczne zilustrowano dostępnymi w Internecie nagraniami rzeczywistych zachowań kierowców.

EN

The assumption that each road participant adheres to the rules, ideally adapts his behavior to the prevailing road conditions, is unrealistic, and as the basis for taking action can lead to collisions and accidents. The article presents the theoretical models allowing to understand the behavior of drivers who deliberately enforce the priority of passing, and their only motivation is the shortest travel time through the intersection. Two types of situations at crossroads are considered: with guided and non-guided traffic with the STOP sign. The presented mathematical models are illustrated by the real-life recordings of drivers available on the Internet.

19

Teoria gier w technice bilansowania mocy czynnej w mikrosieciach niskiego napięcia

Affelt J., Lisowski J.

Zeszyty Naukowe Akademii Morskiej w Gdyni

|

2017

|

nr 98

11--19

PL

W artykule podjęto problem opracowania koncepcji rozproszonego zarzą- dzania popytem energii elektrycznej w mikrosieciach niskiego napięcia z użyciem algorytmu wykorzystującego elementy teorii gier. Takie rozwiązanie może być stosowane jako podstawowy sposób bilansowania mocy czynnej oraz jako system awaryjny w przypadku przejścia sieci w tryb pracy izolowanej lub w inteligentnych sieciach elektroenergetycznych w sytuacji utraty komunikacji pomiędzy sterownikami.

EN

The article discusses the problem of developing a concept of fully distributed Demand Side Management in a low-voltage microgrid, using an algorithm based on game theory. The following solution can be used as a primary method to maintain the balance of active power and as a backup system in a case of switching the microgrid to isolated mode, and also in Smart Power Grid in a situation where there is a loss of communication between the controllers.

20

Optimal power allocation for cognitive LTE-femtocell networks based on game theory

Martyna J.

Przegląd Telekomunikacyjny + Wiadomości Telekomunikacyjne

|

2017

|

nr 8-9

1067--1071, CD

EN

In this paper, a new power control scheme for cognitive LTE-femtocell networks based on game theory is proposed. The problem is formulated as a coalition graph game problem to maximise throughput and system fairness. Then, a heuristic low-complexity algorithm to solving so presented problem is given. Simulation results have validated that the proposed scheme is effective in managing the cognitive femtocell network.

PL

W tym artykule proponuje się nowy schemat kontroli mocy dla sieci kognitywnych femtokomórek LTE oparty o teorię gier. Problem jest sformułowany jako gra koalicyjna, maksymalizująca przepustowość i sprawiedliwość systemu. Następnie, przedstawiono heurystyczny algorytm o małej złożoności dla rozwiązanie tego problemu. Wyniki symulacji potwierdziły, że proponowany schemat jest efektywny dla zarządzanie femtokomórką kognitywną LTE.