Pure Strategy Nash Equilibria Refinement in Bimatrix Games by Using Domination Efficiency along with Maximin and the Superoptimality Rule

Скорочена інформація про документ
dc.contributor.authorRomanuke, V. V.
dc.contributor.authorРоманюк, Вадим Васильович
dc.date.accessioned2018-09-24T14:56:28Z
dc.date.available2018-09-24T14:56:28Z
dc.date.issued2018
dc.description.abstractenBackground. Multiple Nash equilibria bring a new problem of selecting amongst them but this problem is solved by refining the equilibria. However, none of the existing refinements can guarantee a single refined Nash equilibrium. In some games, Nash equilibria are nonrefinable. Objective. For solving the nonrefinability problem of pure strategy Nash equilibria in bimatrix games, the goal is to develop an algorithm which could facilitate in refining the equilibria as much further as possible. Methods. A Nash equilibria refinement is suggested, which is based on the classical refinement by selecting only efficient equilibria that dominate by their payoffs. The suggested refinement exploits maximin subsequently. The superoptimality rule is involved if maximin fails to produce just a single refined equilibrium. Results. An algorithm of using domination efficiency along with maximin and the superoptimality rule has been developed for refining Nash equilibria in bimatrix games. The algorithm has 10 definite steps at which the refinement is progressively accomplished. The developed concept of the equilibria refinement does not concern games with payoff symmetry and mirror-like symmetry. Conclusions. The suggested pure strategy Nash equilibria refinement is a contribution to the equilibria refinement game theory field. The developed algorithm allows selecting amongst nonrefinable Nash equilibria in bimatrix games. It partially removes the uncertainty of equilibria, without going into mixed strategies. There are only two negative cases when the refinement fails. For a case when more than a single refined equilibrium is produced, the superoptimality rule may be used for a player having multiple refined equilibrium strategies but the other player has just a single refined equilibrium strategy.uk
dc.description.abstractruПроблематика. Множественные равновесия Неша порождают новую проблему выбора между ними, но эта проблема решается усовершенствованием таких равновесий. Однако ни один из существующих методов усовершенствования не может гарантировать единственное усовершенствованное равновесие Неша. В некоторых играх равновесия Неша не подлежат усовершенствованию. Цель исследования. Для решения проблемы невозможности усовершенствовать равновесия Неша в чистых стратегиях в биматричных играх необходимо разработать алгоритм, который бы как можно больше способствовал в усовершенствовании равновесий. Методика реализации. Предлагается метод усовершенствования равновесий Неша, основанный на классическом усовершенствовании с выделением только эффективных равновесий, доминирующих по своим выигрышам. Впоследствии предлагаемый метод усовершенствования использует максимин. Правило сверхоптимальности привлекается, если максимин не позволяет получить всего одно усовершенствованное равновесие. Результаты исследования. Для усовершенствования равновесий Неша в биматричных играх разработан алгоритм с использованием эффективности доминирования вместе с максимином и правилом сверхоптимальности. Алгоритм состоит из 10 конкретных шагов, на которых постепенно выполняется усовершенствование. Разработанная концепция усовершенствования равновесий не касается игр с симметрией или зеркальной симметрией выигрышей. Выводы. Предложенное усовершенствование равновесий Неша в чистых стратегиях является вкладом в область усовершенствования равновесий в теории игр. Разработанный алгоритм позволяет выбирать среди не подлежащих усовершенствованию равновесий Неша в биматричных играх. Частично он устраняет неопределенность равновесий без перехода на смешанные стратегии. Существуют всего лишь два негативных случая, когда усовершенствование не удается. Для случая, когда производится более чем одно усовершенствованное равновесие, правило сверхоптимальности может быть применено игроком, имеющем множественные усовершенствованные равновесные стратегии, а другой игрок обладает лишь единственной усовершенствованной равновесной стратегией.uk
dc.description.abstractukПроблематика. Множинні рівноваги Неша породжують нову проблему вибору між ними, але ця проблема вирішується удосконаленням таких рівноваг. Однак жоден з існуючих методів удосконалення не може гарантувати єдину вдосконалену рівновагу Неша. У деяких іграх рівноваги Неша не підлягають удосконаленню. Мета дослідження. Для вирішення проблеми неможливості вдосконалити рівноваги Неша в чистих стратегіях у біматричних іграх необхідно розробити алгоритм, який би якомога більше сприяв в удосконаленні рівноваг. Методика реалізації. Пропонується метод удосконалення рівноваг Неша, заснований на класичному удосконаленні з виділенням тільки ефективних рівноваг, домінуючих за своїми виграшами. Згодом пропонований метод удосконалення використовує максимін. Правило надоптимальності залучається, якщо максимін не дає змоги отримати всього одну вдосконалену рівновагу. Результати дослідження. Для удосконалення рівноваг Неша в біматричних іграх розроблено алгоритм із використанням ефективності домінування разом із максиміном і правилом надоптимальності. Алгоритм складається з 10 конкретних кроків, на яких поступово виконується удосконалення. Розроблена концепція удосконалення рівноваг не стосується ігор із симетрією або дзеркальною симетрією виграшів. Висновки. Запропоноване удосконалення рівноваг Неша в чистих стратегіях є внеском в область удосконалення рівноваг у теорії ігор. Розроблений алгоритм дає змогу вибирати серед рівноваг Неша, що не підлягають удосконаленню, в біматричних іграх. Частково він усуває невизначеність рівноваг без переходу на змішані стратегії. Існують всього лише два негативних ви­падки, коли удосконалення не вдається. Для випадку, коли виробляється більше ніж одна удосконалена рівновага, правило надоптимальності може бути ужито гравцем, який має численні удосконалені рівноважні стратегії, а інший гравець має лише єдину удосконалену рівноважну стратегію.uk
dc.format.pagerangeС. 42-52uk
dc.identifier.citationRomanuke, V. V. Pure Strategy Nash Equilibria Refinement in Bimatrix Games by Using Domination Efficiency along with Maximin and the Superoptimality Rule / V. V. Romanuke // Наукові вісті КПІ : міжнародний науково-технічний журнал. – 2018. – № 3(119). – С. 42–52. – Бібліогр.: 45 назв.uk
dc.identifier.doihttps://doi.org/10.20535/1810-0546.2018.3.123853
dc.identifier.urihttps://ela.kpi.ua/handle/123456789/24578
dc.language.isoenuk
dc.publisherКПІ ім. Ігоря Сікорськогоuk
dc.publisher.placeКиївuk
dc.sourceНаукові вісті КПІ : міжнародний науково-технічний журнал, 2018, № 3(119)uk
dc.subjectbimatrix gameuk
dc.subjectNash equilibriauk
dc.subjectrefinementuk
dc.subjectdomination efficiencyuk
dc.subjectmaximinuk
dc.subjectsuperoptimality ruleuk
dc.subjectбіматрична граuk
dc.subjectрівноваги Нешаuk
dc.subjectудосконаленняuk
dc.subjectефективність домінуванняuk
dc.subjectмаксимінuk
dc.subjectправило надоптимальностіuk
dc.subjectбиматричная играuk
dc.subjectравновесия Нешаuk
dc.subjectусовершенствованиеuk
dc.subjectэффективность доминированияuk
dc.subjectмаксиминuk
dc.subjectправило сверхоптимальностиuk
dc.subject.udc519.833.2:519.812.3
dc.titlePure Strategy Nash Equilibria Refinement in Bimatrix Games by Using Domination Efficiency along with Maximin and the Superoptimality Ruleuk
dc.title.alternativeУдосконалення рівноваг Неша в чистих стратегіях у біматричних іграх за використання ефективності домінування разом із максиміном і правилом надоптимальностіuk
dc.title.alternativeУсовершенствование равновесий Неша в чистых стратегиях в биматричных играх с использованием эффективности доминирования вместе с максимином и правилом сверхоптимальностиuk
dc.typeArticleuk

Файли

Контейнер файлів
Зараз показуємо 1 - 1 з 1
Ескіз
Назва:
NVKPI2018-3_05.pdf
Розмір:
352.54 KB
Формат:
Adobe Portable Document Format
Опис:
Завантажити
Ліцензійна угода
Зараз показуємо 1 - 1 з 1
Ескіз недоступний
Назва:
license.txt
Розмір:
7.74 KB
Формат:
Item-specific license agreed upon to submission
Опис:
Завантажити

Зібрання

Наукові вісті КПІ: міжнародний науково-технічний журнал, № 3(119)