Finite approximation of zero-sum games played in staircase-function continuous spaces
Вантажиться...
Дата
2021
Автори
Науковий керівник
Назва журналу
Номер ISSN
Назва тому
Видавець
КПІ ім. Ігоря Сікорського
Анотація
Background. There is a known method of approximating continuous zero-sum games, wherein an approximate solution is considered acceptable if it changes minimally by changing the sampling step minimally. However, the method cannot be applied straightforwardly to a zero-sum game played with staircase-function strategies. Besides, the independence of the player’s sampling step selection should be taken into account. Objective. The objective is to develop a method of finite approximation of zero-sum games played in staircase-function continuous spaces by taking into account that the players are likely to independently sample their pure strategy sets. Methods. To achieve the said objective, a zero-sum game, in which the players’ strategies are staircase functions of time, is formalized. In such a game, the set of the player’s pure strategies is a continuum of staircase functions of time, and the time is thought of as it is discrete. The conditions of sampling the set of possible values of the player’s pure strategy are stated so that the game becomes defined on a product of staircase-function finite spaces. In general, the sampling step is different at each player and the distribution of the sampled points (function-strategy values) is non-uniform. Results. A method of finite approximation of zero-sum games played in staircase-function continuous spaces is pre sented. The method consists in irregularly sampling the player’s pure strategy value set, solving smaller-sized matrix games, each defined on a subinterval where the pure strategy value is constant, and stacking their solutions if they are consistent. The stack of the smaller-sized matrix game solutions is an approximate solution to the initial staircase game. The (weak) consistency of the approximate solution is studied by how much the payoff and optimal situation change as the sampling density minimally increases by the three ways of the sampling increment: only the first player’s increment, only the second player’s increment, both the players’ increment. The consistency is decomposed into the payoff, opti mal strategy support cardinality, optimal strategy sampling density, and support probability consistency. It is practically reasonable to consider a relaxed payoff consistency. Conclusions. The suggested method of finite approximation of staircase zero-sum games consists in the independent samplings, solving smaller-sized matrix games in a reasonable time span, and stacking their solutions if they are con sistent. The finite approximation is regarded appropriate if at least the respective approximate (stacked) solution is e-payoff consistent.
Опис
Ключові слова
game theory, payoff functional, staircase-function strategy, matrix game, irregular sampling, approximate solution consistency, теорія ігор, функціонал виграшів, стратегія у формі сходинкової функції, матрична гра, нерегулярна дискретизація, узгодженість наближеного розв’язку
Бібліографічний опис
Romanuke, V. V. Finite approximation of zero-sum games played in staircase-function continuous spaces / V. V. Romanuke // Наукові вісті КПІ : міжнародний науково-технічний журнал. – 2021. – № 4(134). – С. 19–38. – Бібліогр.: 22 назви.