Скінчена апроксимація ігор з нульовою сумою, що розігруються у неперервних просторах сходинкових функцій

Вадим Васильович Романюк

doi:10.20535/kpisn.2021.4.242769

Т. · № 4 · 2021 чер 1, 2020 статті

Скінчена апроксимація ігор з нульовою сумою, що розігруються у неперервних просторах сходинкових функцій

ВР

Вадим Васильович Романюк Відповідальний Polish Naval Academy, Poland Україна

Опублікованочер 1, 2020

PDF

НВКПІ 4 ТОМ · 4

ТОМ · № 4 · 2021 Переглянути випуск

Анотація

Проблематика. Існує відомий спосіб апроксимації неперервних ігор з нульовою сумою, де наближений розв’язок вважається прийнятним, якщо він змінюється мінімально за мінімальної зміни кроку дискретизації. Однак цей метод не можна прямо застосувати до гри з нульовою сумою, що розігрується зі стратегіями у формі сходинкових функцій. Крім того, слід брати до уваги незалежність вибору гравцем кроку дискретизації. Мета дослідження. Мета полягає у тому, щоб розробити метод скінченної апроксимації ігор з нульовою сумою, які розігруються у неперервних просторах сходинкових функцій, беручи до уваги, що гравці, ймовірно, дискретизують множини своїх чистих стратегій самостійно. Методика реалізації. Для досягнення зазначеної мети формалізується гра з нульовою сумою, в якій стратегії гравців є сходинковими функціями часу. У такій грі множина чистих стратегій гравця є континуумом сходинкових функцій часу, і час вважається дискретним. Умови дискретизації множини можливих значень чистої стратегії гравця викладаються так, що гра стає визначеною на добутку скінченних просторів сходинкових функцій. Загалом, крок дискретизації у кожного гравця різний, і розподіл вибіркових точок (значень функції-стратегії) неоднорідний. Результати дослідження. Представлено метод скінченної апроксимації ігор з нульовою сумою, які розігруються у неперервних просторах сходинкових функцій. Метод полягає у нерегулярній дискретизації множини значень чистої стратегії гравця, розв’язуванні матричних ігор меншого розміру, кожна з яких визначена на підінтервалі, де значення чистої стратегії є постійним, й укладанні їхніх розв’язків, якщо вони є узгодженими. Уклад розв’язків матричних ігор меншого розміру є наближеним розв’язком вихідної сходинкової гри. Досліджується (слабка) узгодженість наближеного розв’язку тим, наскільки змінюється виграш та оптимальна ситуація, коли щільність дискретизації мінімально збільшується трьома способами: лише приріст у першого гравця, лише приріст у другого гравця, приріст в обох гравців. Узгодженість розкладається на узгодженість виграшів, узгодженість потужності спектру оптимальної стратегії, узгодженість щільності дискретизації оптимальної стратегії та узгодженість спектральних імовірностей. З практичної точки зору доцільно розглядати релаксовану узгодженість виграшів. Висновки. Запропонований метод скінченної апроксимації сходинкових ігор з нульовою сумою полягає у незалежних дискретизаціях, розв’язуванні матричних ігор меншого розміру за прийнятний проміжок часу та укладенні їхніх розв’язків, якщо вони є узгодженими. Скінченне наближення вважається прийнятним, якщо принаймні відповідний наближений (укладений) розв’язок є узгодженим за e-виграшами

Ключові слова

#теорія ігор #функціонал виграшів #узгодженість наближеного розв’язку #нерегулярна дискретизація #матрична гра #стратегія у формі сходинкової функції

Посилання

N. N. Vorob’yov, Game theory fundamentals. Noncooperative games, Moscow, Nauka, 1984, 496 p. (in Russian)
N. Nisan et al., Algorithmic Game Theory, Cambridge University Press, 2007, 778 p.
https://doi.org/10.1017/CBO9780511800481
M. J. Osborne, An introduction to game theory, Oxford University Press, 2003, 554 p.
K. Leyton-Brown and Y. Shoham, Essentials of game theory: a concise, multidisciplinary introduction, Morgan & Claypool Publishers, 2008, 104 p.
https://doi.org/10.2200/S00108ED1V01Y200802AIM003
R. B. Myerson, Game theory: Analysis of Conflict, Harvard University Press, 1997, 600 p.
N. N. Vorob’yov, Game theory for economists-cyberneticists, Moscow, Nauka, 1985, 272 p. (in Russian)
V. V. Romanuke, Theory of Antagonistic Games, Lviv, New World — 2000, 2010, 294 p. (in Ukrainian)
E. B. Yanovskaya, “Antagonistic games played in function spaces”, Lithuanian Mathematical Bulletin, no. 3, pp. 547 — 557, 1967.
E. B. Yanovskaya, “Minimax theorems for games on the unit square”, Probability theory and its applications, no. 9 (3), pp. 554 — 555, 1964.
. T. C. Schelling, The Strategy of Conflict, Harvard University, 1980, 328 p.
H. Moulin, “Extension of two-person zero-sum games”, Journal of Mathematical Analysis and Application, no. 55 (2), pp. 490 — 507, 1975.
V. V. Romanuke, “Finite approximation of continuous noncooperative two-person games on a product of linear strategy functional spaces”, Journal of Mathematics and Applications, vol. 43, pp. 123 — 138, 2020.
https://doi.org/10.7862/rf.2020.9
J. Yang et al., “Group formation in the spatial public goods game with continuous strategies”, Physica A: Statistical Mechanics and its Applications, vol. 505, pp. 737 — 743, 2018.
https://doi.org/10.1016/j.physa.2018.03.057
V. V. Romanuke, “Approximation of unit-hypercubic infinite two-sided noncooperative game via dimension-dependent irregular samplings and reshaping the multidimensional payoff matrices into flat matrices for solving the corresponding bimatrix game”, Computer Modelling and New Technologies, vol. 19, no. 3A, pp. 7 — 16, 2015.
V. V. Romanuke and V. G. Kamburg, “Approximation of isomorphic infinite two-person noncooperative games via variously sampling the players’ payoff functions and reshaping payoff matrices into bimatrix game”, Applied Computer Systems, vol. 20, pp. 5 — 14, 2016.
https://doi.org/10.1515/acss-2016-0009
S. P. Coraluppi and S. I. Marcus, “Risk-sensitive and minimax control of discrete-time, finite-state Markov decision processes”, Automatica, vol. 35 (2), pp. 301 — 309, 1999.
https://doi.org/10.1016/S0005-1098(98)00153-8
S. Rahal et al., “Hybrid strategies using linear and piecewise-linear decision rules for multistage adaptive linear optimization”, European Journal of Operational Research, vol. 290, iss. 3, pp. 1014 — 1030, 2021.
https://doi.org/10.1016/j.ejor.2020.08.054
V. V. Romanuke, “Approximation of unit-hypercubic infinite antagonistic game via dimension-dependent irregular samplings and reshaping the payoffs into flat matrix wherewith to solve the matrix game”, Journal of Information and Organizational Sciences, vol. 38, no. 2, pp. 125 — 143, 2014.
R. E. Edwards, Functional Analysis: Theory and Applications, New York, Holt, Rinehart and Winston, 1965, 781 p.
H. Khaloie et al., “Coordinated wind-thermal-energy storage offering strategy in energy and spinning reserve markets using a multi-stage model”, Applied Energy, vol. 259, 114168, 2020.
https://doi.org/10.1016/j.apenergy.2019.114168
V. V. Romanuke, “Adaptive finite approximation of continuous noncooperative games”, Journal of Automation and Information Sciences, vol. 52, iss. 10, pp. 31 — 41, 2020.
https://doi.org/10.1615/JAutomatInfScien.v52.i10.20

Попередня у випуску Байєсовське моделювання ризиків різної природи Наступна у випуску DevOps – концепт і структурне представлення

§ 06 — Пов'язані

Схожі статті в цьому журналі

Пов'язані рецензовані дослідження, опубліковані в цьому журналі.

Усі випуски

ДВОЕТАПНИЙ ПІДХІД ДО СЕГМЕНТАЦІЇ СУПУТНИКОВИХ ЗНІМКІВ ДЛЯ ОЦІНЮВАННЯ ПЛОЩІ АСФАЛЬТОВАНОГО ПОКРИТТЯ ПАРКОВОК

Олександр Гончарук, Надія Недашківська

Проблематика. Точна оцінка площі асфальтованих парковок є важливою для містобудування та екологічного моніторингу. Однак спектральна подібність асфальту паркувальних…

#семантична сегментація #супутникові знімки #паркінг #нейронна мережа

10.20535/kpisn.2026.3.367540

ФОРМАЛІЗАЦІЯ РОЗРІДЖЕНОГО ANP З БІНАРНИМИ ПОРІВНЯННЯМИ НА ОСНОВІ ДАНИХ У КОЛІ ОДНОРІДНИХ КОМПОНЕНТІВ ДЛЯ ПРІОРИТИЗАЦІЇ РОЗПОДІЛУ РЕСУРСІВ

Вадим Романюк

Проблематика. Задачі розподілу обмежених ресурсів між взаємозалежними однорідними об’єктами виникають у багатьох прикладних сферах — зокрема, під час конкурсного…

#розподіл ресурсів #однорідні компоненти #взаємозалежності #аналітичний мережевий процес

10.20535/kpisn.2026.3.368158

РОЗРОБКА МЕТОДУ ФОРМАЛІЗАЦІЇ ДИНАМІЧНИХ ТЕПЛОВИХ ПОРТРЕТІВ ДЛЯ НАДІЙНОГО ВИЯВЛЕННЯ ЦІЛЕЙ

Степан Лис, Оксана Оборська

Проблематика. Автоматизовані системи спостереження з БпЛА стикаються з подвійним викликом: виявленням теплоконтрастних об'єктів у реальному часі та їх ідентифікацією в…

#тепловізійні системи #ідентифікація цілей #локалізація зони інтересу #динамічний тепловий портрет

10.20535/kpisn.2026.3.359114

Статті цього автора (цих авторів), які найбільше читають

Схожі статті

Дмитро Петренко, Анатолій Протасов, АЛГОРИТМ БЕЗКАРТОГРАФІЧНОЇ НАВІГАЦІЇ РОБОТА HUSKY НА ОСНОВІ МОДЕЛЕЙ ГЛИБОКОГО НАВЧАННЯ З ПІДКРІПЛЕННЯМ ТА АДАПТИВНОГО НАВЧАЛЬНОГО ПЛАНУ , Наукові вісті КПІ: Том 143 № 2 (2026)
Костянтин Д. Грішин, Nadezhda Nedashkovskaya, МОДЕЛЬ МАШИННОГО НАВЧАННЯ ДЛЯ РОЗПІЗНАВАННЯ КОНФІГУРАЦІЙ РУК УКРАЇНСЬКОЇ ЖЕСТОВОЇ МОВИ , Наукові вісті КПІ: Том 143 № 2 (2026)
Roman M. Galagan, Andrii S. Momot, АНАЛІЗ ЗАСТОСУВАННЯ НЕЙРОННИХ МЕРЕЖ ДЛЯ ПІДВИЩЕННЯ ДОСТОВІРНОСТІ АКТИВНОГО ТЕПЛОВОГО НЕРУЙНІВНОГО КОНТРОЛЮ , Наукові вісті КПІ: № 1 (2019)
Sergii F. Petrenko, Anatolii V. Omelian, Olha O. Horbatiuk, Viktor S. Antonyuk, ДОСЛІДЖЕННЯ РЕЗОНАНСНИХ ХАРАКТЕРИСТИК П’ЄЗОЕЛЕКТРИЧНОГО ДВИГУНА ЗАЛЕЖНО ВІД РЕСУРСНОГО СТАНУ , Наукові вісті КПІ: № 1 (2019)
Vadim V. Romanuke, НАБІР ДАНИХ НЕСКІНЧЕННОГО МАСШТАБУВАННЯ ІЗ ЗОБРАЖЕНЬ У ГРАДАЦІЯХ СІРОГО З ОДНИМ БАГА¬ТО-КУТНИКОМ ЯК ШВИДКА ТЕСТОВА ПЛАТФОРМА ДЛЯ СЕМАНТИЧНОЇ СЕГМЕНТАЦІЇ ЗОБРАЖЕНЬ , Наукові вісті КПІ: № 1 (2019)
Ivan A. Dychka, Yevgeniya S. Sulema, ОПЕРАЦІЇ ВПОРЯДКУВАННЯ В АЛГЕБРИЧНІЙ СИСТЕМІ АГРЕГАТІВ ДЛЯ ОБРОБЛЕННЯ ДАНИХ МУЛЬТИОБРАЗУ , Наукові вісті КПІ: № 1 (2019)
Євген Панкратов, Григорій Тимчик, МІКРОСЕРВІСНА АРХІТЕКТУРА ТА АЛГОРИТМИ МОДУЛЬНОЇ СИСТЕМИ АВТОМАТИЗАЦІЇ ТЕХНОЛОГІЧНИХ ПРОЦЕСІВ МАЛОГО БІЗНЕСУ , Наукові вісті КПІ: Том 143 № 2 (2026)
Костянтин Бровко, Павло Буданов, Олег Великогорський, Юлія Олійник, Наталія Винокурова, Сергій Войтенко, ІМІТАЦІЙНА МОДЕЛЬ ЦИФРОВОГО ДВІЙНИКА ТЕХНОЛОГІЧНОГО ПРОЦЕСУ ЕНЕРГОБЛОКУ АЕС , Наукові вісті КПІ: Том 143 № 2 (2026)
Павло Кость, Лариса Гліненко, МЕТОДИКА ВИБОРУ СТРУКТУРИ ПЕРЕДАВАЛЬНОГО ТРАКТУ ДЛЯ ТЕРМОЯДЕРНИХ УСТАНОВОК , Наукові вісті КПІ: Том 143 № 2 (2026)
Вадим Романюк, ФОРМАЛІЗАЦІЯ РОЗРІДЖЕНОГО ANP З БІНАРНИМИ ПОРІВНЯННЯМИ НА ОСНОВІ ДАНИХ У КОЛІ ОДНОРІДНИХ КОМПОНЕНТІВ ДЛЯ ПРІОРИТИЗАЦІЇ РОЗПОДІЛУ РЕСУРСІВ , Наукові вісті КПІ: Том 144 № 3 (2026)

1-10 з 182 Наступне

Ви також можете розпочати розширений пошук схожих статей для цієї статті.

[1] N. N. Vorob’yov, Game theory fundamentals. Noncooperative games, Moscow, Nauka, 1984, 496 p. (in Russian)

[2] N. Nisan et al., Algorithmic Game Theory, Cambridge University Press, 2007, 778 p.

[3] https://doi.org/10.1017/CBO9780511800481

[4] M. J. Osborne, An introduction to game theory, Oxford University Press, 2003, 554 p.

[5] K. Leyton-Brown and Y. Shoham, Essentials of game theory: a concise, multidisciplinary introduction, Morgan & Claypool Publishers, 2008, 104 p.

[6] https://doi.org/10.2200/S00108ED1V01Y200802AIM003

[7] R. B. Myerson, Game theory: Analysis of Conflict, Harvard University Press, 1997, 600 p.

[8] N. N. Vorob’yov, Game theory for economists-cyberneticists, Moscow, Nauka, 1985, 272 p. (in Russian)

[9] V. V. Romanuke, Theory of Antagonistic Games, Lviv, New World — 2000, 2010, 294 p. (in Ukrainian)

[10] E. B. Yanovskaya, “Antagonistic games played in function spaces”, Lithuanian Mathematical Bulletin, no. 3, pp. 547 — 557, 1967.

[11] E. B. Yanovskaya, “Minimax theorems for games on the unit square”, Probability theory and its applications, no. 9 (3), pp. 554 — 555, 1964.

[12] . T. C. Schelling, The Strategy of Conflict, Harvard University, 1980, 328 p.

[13] H. Moulin, “Extension of two-person zero-sum games”, Journal of Mathematical Analysis and Application, no. 55 (2), pp. 490 — 507, 1975.

[14] V. V. Romanuke, “Finite approximation of continuous noncooperative two-person games on a product of linear strategy functional spaces”, Journal of Mathematics and Applications, vol. 43, pp. 123 — 138, 2020.

[15] https://doi.org/10.7862/rf.2020.9

[16] J. Yang et al., “Group formation in the spatial public goods game with continuous strategies”, Physica A: Statistical Mechanics and its Applications, vol. 505, pp. 737 — 743, 2018.

[17] https://doi.org/10.1016/j.physa.2018.03.057

[18] V. V. Romanuke, “Approximation of unit-hypercubic infinite two-sided noncooperative game via dimension-dependent irregular samplings and reshaping the multidimensional payoff matrices into flat matrices for solving the corresponding bimatrix game”, Computer Modelling and New Technologies, vol. 19, no. 3A, pp. 7 — 16, 2015.

[19] V. V. Romanuke and V. G. Kamburg, “Approximation of isomorphic infinite two-person noncooperative games via variously sampling the players’ payoff functions and reshaping payoff matrices into bimatrix game”, Applied Computer Systems, vol. 20, pp. 5 — 14, 2016.

[20] https://doi.org/10.1515/acss-2016-0009

[21] S. P. Coraluppi and S. I. Marcus, “Risk-sensitive and minimax control of discrete-time, finite-state Markov decision processes”, Automatica, vol. 35 (2), pp. 301 — 309, 1999.

[22] https://doi.org/10.1016/S0005-1098(98)00153-8

[23] S. Rahal et al., “Hybrid strategies using linear and piecewise-linear decision rules for multistage adaptive linear optimization”, European Journal of Operational Research, vol. 290, iss. 3, pp. 1014 — 1030, 2021.

[24] https://doi.org/10.1016/j.ejor.2020.08.054

[25] V. V. Romanuke, “Approximation of unit-hypercubic infinite antagonistic game via dimension-dependent irregular samplings and reshaping the payoffs into flat matrix wherewith to solve the matrix game”, Journal of Information and Organizational Sciences, vol. 38, no. 2, pp. 125 — 143, 2014.

[26] R. E. Edwards, Functional Analysis: Theory and Applications, New York, Holt, Rinehart and Winston, 1965, 781 p.

[27] H. Khaloie et al., “Coordinated wind-thermal-energy storage offering strategy in energy and spinning reserve markets using a multi-stage model”, Applied Energy, vol. 259, 114168, 2020.

[28] https://doi.org/10.1016/j.apenergy.2019.114168

[29] V. V. Romanuke, “Adaptive finite approximation of continuous noncooperative games”, Journal of Automation and Information Sciences, vol. 52, iss. 10, pp. 31 — 41, 2020.

[30] https://doi.org/10.1615/JAutomatInfScien.v52.i10.20