Hybrid method for solving bi–matrix games

Issue 2 from 29.06.2018

Для нахождения решения биматричной игры в смешанных стратегиях можно ис- пользовать приближенный метод решения биматричных игр (2LP-метод) и/или метод Лем- ке – Хаусона (LH-метод). В 2LP-методе поиск решения биматричной игры сводится к итера- тивному поиску глобального минимума функции Нэша, имеющего большое число локальных минимумов, не совпадающих с глобальным минимумом. Тем не менее поочеред- ная минимизация этой функции по одной из двух переменных (стратегий) при фиксации другой переменной легко сводится к линейному программированию. Осуществляя перебор начальных чистых стратегий и решая на каждой итерации две задачи линейного програм- мирования, 2LP-метод позволяет найти точное решение игры, если выполнено условие до- полнительности либо некоторое приближение к множеству точек Нэша при незначительном нарушении условия дополнительности. Достоинством метода является его простота, глав- ным недостатком – снижение эффективности при малой заполненности и/или при нали- чии взаимозависимости матриц, задающих функции выигрышей игроков. В LH-методе по- иск решения биматричной игры заменяется поиском решения связанной с игрой системы линейных равенств. Начиная с единичного базиса метод делает шаги симплексного типа с целью уменьшить число нарушенных условий дополнительности. Как правило, но не всег- да, этим методом удается найти точное решение игры. Предлагаемый нами гибридный ме- тод производит дооптимизацию приближенного решения, полученного 2LP-алгоритмом, при помощи LH-алгоритма, использующего базис приближенного решения. Эффективность метода Лемке – Хаусона и нашего гибридного метода оказалась примерно одинаковой. С по- мощью гибридного метода удалось найти решение нескольких игр, для которых точное ре- шение не было получено ни 2LP-методом, ни LH-методом.

2144 14

HYBRID METHOD FOR SOLVING BI-MATRIX GAMES

from 01.04.2018

Для нахождения решения биматричной игры в смешанных стратегиях можно использовать приближенный метод решения биматричных игр (2LP-метод) и/или метод Лемке–Хаусона (LH-метод). В 2LP-методе поиск решения биматричной игры сводится к итеративному поиску глобального минимума функции Нэша, имеющего большое число локальных минимумов, не совпадающих с глобальным минимумом. Тем не менее поочередная минимизация этой функции по одной из двух переменных (стратегий) при фиксации другой переменной легко сводится к линейному программированию. Осуществляя перебор начальных чистых стратегий и решая на каждой итерации две задачи линейного программирования, 2LP-метод позволяет найти точное решение игры, если выполнено условие дополнительности либо некоторое приближение к множеству точек Нэша при незначительном нарушении условия дополнительности. Достоинством метода является его простота, главным недостатком – снижение эффективности при малой заполненности и/или при наличии взаимозависимости матриц, задающих функции выигрышей игроков. В LH-методе поиск решения биматричной игры заменяется поиском решения связанной с игрой системы линейных равенств. Начиная с единичного базиса метод делает шаги симплексного типа с целью уменьшить число нарушенных условий дополнительности. Как правило, но не всегда, этим методом удается найти точное решение игры. Предлагаемый нами гибридный метод производит дооптимизацию приближенного решения, полученного 2LP-алгоритмом, при помощи LH-алгоритма, использующего базис приближенного решения. Эффективность метода Лемке–Хаусона и нашего гибридного метода оказалась примерно одинаковой. С помощью гибридного метода удалось найти решение нескольких игр, для которых точное решение не было получено ни 2LP-методом, ни LH-методом.

947 8

EFFICIENCY OF AN APPROXIMATE ALGORITHM TO SOLVE FINITE THREE-PERSON GAMES (A COMPUTATIONAL EXPERIENCE)

Issue 1 from 01.01.2017

Дано краткое описание предложенного Е.Г. Гольштейном приближенного метода решения конечной бескоалиционной игры трех лиц в смешанных стратегиях. Поиск решения игры сводится к итеративному поиску глобального минимума так называемой функции Нэша, являющейся мерой близости точки к множеству решений игры и имеющей большое число локальных минимумов, не совпадающих с глобальным минимумом. Тем не менее, минимизация этой функции по одной из трех переменных (стратегий) при фиксации двух других переменных легко сводится к линейному программированию. Осуществляя перебор начальных пар чистых стратегий и решая на каждой итерации три задачи линейного программирования, метод отыскивает точное решение игры, если выполнено условие дополнительности, либо приемлемое приближение к множеству точек Нэша при незначительном нарушении условия дополнительности. Численное тестирование метода на двух семействах сгенерированных игр выявило его достоинства и недостатки. Предлагаемый метод эффективен при независимых или мало зависимых таблицах, определяющих выигрыши игроков. При росте коэффициента взаимозависимости таблиц эффективность метода снижается.

996 4

AN APPROXIMATE METHOD FOR SOLVING FINITE THREE-PERSON GAMES

Issue 1 from 01.01.2014

Описан численный алгоритм решения конечной бескоалиционной игры трех лиц в смешанных стратегиях. Алгоритм основан на минимизации некоторой функции, которая имеет большое число локальных минимумов, и опирается на линейное программирование.

887 1

ON MODIFICATIONS OF THE ULTIMATE NON-COALITIONAL GAME HAVING A CONVEX STRUCTURE

Issue №4 from 01.10.2010

С бескоалиционной игрой многих лиц естественным образом связывается некоторое отображение. Если это отображение является монотонным, то говорят, что игра имеет выпуклую структуру и для таких игр существуют эффективные численные методы решения. Как правило, конечные бескоалиционные игры в смешанных стратегиях не имеют выпуклой структуры. В статье рассматриваются модификации таких игр, основанные на возмущениях функций выигрышей игроков. Устанавливаются нижние оценки величин возмущений, прикоторых модифицированная игра приобретает выпуклую структуру. Приводятся два новых необходимых и достаточных условия наличия выпуклой структуры у конечной бескоалиционной игры многих лиц.

855 2

ON ONE BALANCE PROBLEM RELATED TO NON-COALITIONAL GAMES

Issue №4 from 01.10.2009

Рассматривается задача равновесия, частным случаем которой является задача отыскания точки Нэша бескоалиционной игры многих лиц. Приводится численный алгоритм решения этой задачи. При определенных требованиях к задаче получена оценка скорости сходимости алгоритма. Отмечена связь между задачей равновесия и определяемым ею вариационным неравенством.

921 0

A NUMERICAL METHOD FOR SOLVING BIMATRIX GAMES

Issue 4 from 01.10.2013

Предложен метод решения биматричных игр, основанный на поиске глобального минимума функции Нэша. Осуществляя перебор начальных чистых стратегий, метод отыскивает точное решение игры, если выполнено условие дополнительности, либо приемлемое приближение к множеству точек Нэша. Проведено численное тестирование метода, выявившее его достоинства и недостатки.

941 1

METHOD FOR SOLVING VARIATION INEQUALITIES USING INACCURATE INITIAL DATA

Issue №3 from 01.07.2008

Отмечена связь между задачей решения вариационного неравенства и задачей отыскания неподвижной точки точечно-множественного отображения выпуклого компакта в себя. Приведены примеры вариационных неравенств, связанных с выпуклой оптимизацией, выпуклой антагонистической игрой, выпуклой некоалиционной игрой многих лиц, задачей отыскания равновесных цен. Описан итеративный метод оракульного типа решения вариационного неравенства, определяемого монотонным отображением, при наличии ошибок в откликах оракула. Установлены требования к ошибкам оракула, гарантирующие возможность отыскания -решения вариационного неравенства при фиксированном > 0. Получена оценка сверху для числа итераций метода, необходимых для вычисления -решения вариационного неравенства.

830 2

ON THE MONOTONE OF THE DISPLAY RELATED TO THE NON-ANTAGONISTIC PLAY OF TWO PERSONS

Issue №4 from 01.10.2008

С игрой двух лиц связывается отображение, которое, в свою очередь, порождает вариационное неравенство. Задача отыскания точек Нэша игры сводится к решению этого неравенства. Отображение, связанное с неантагонистической игрой, не обязано быть монотонным. Численные методы решения вариационного неравенства существенно опираются на монотонность отображения, порождающего неравенство. Выявлен ряд классов неантагонистических игр двух лиц, для которых соответствующие отображения обладают свойством монотонности.

855 2

ON A CLASS OF ANTAGONISTIC GAMES

Issue 3 from 07.07.2012

Выделен класс антагонистических игр, обладающих свойствами кососимметричной матричной игры. При определенных условиях бескоалиционная игра многих лиц оказывается эквивалентной игре из этого класса. Если игра многих лиц конечна, то функция выигрышей эквивалентной антагонистической игры билинейна и кососимметрична.

895 1

SADDLE-POINT METHOD THAT USES INACCURATE SOURCE DATA

Issue №3 from 01.07.2007

Описан метод оракульного типа отыскания седловой точки выпукло-вогнутой липшицевой функции при наличии ошибок в откликах оракула. Установлены требования к ошибкам оракула. При соблюдении этих требований метод позволяет найти Вседловую точку исследуемой функции при фиксированном e > 0. Получена оценка сверху для числа итераций, необходимых для вычисления e-седловой точки.

850 0

BLOCK PROGRAMMING METHODS

Issue 1 from 01.01.1966

901 0

ON A MODIFICATION OF THE SEQUENTIAL METHOD PLAN IMPROVEMENTS

Issue 1 from 06.01.1965

769 0

DUAL PROBLEMS OF CONVEX PROGRAMMING

Issue 3 from 06.05.1965

699 0

Some New Development in the Mathematical Programming

Issue 5 from 01.09.1967

647 0

Обобщённые соотношения двойственности в экстремальных задачах

Issue 4 from 01.07.1968

647 0

Непрерывная зависимость от параметра множества решений минимаксной задачи

Issue 6 from 01.11.1968

786 0

ON A CLASS OF ANTAGONISTIC GAMES

Issue 3 from 20.07.2012

Выделен класс антагонистических игр, обладающих свойствами кососимметричной матричной игры. При определенных условиях бескоалиционная игра многих лиц оказывается эквивалентной игре из этого класса. Если игра многих лиц конечна, то функция выигрышей эквивалентной антагонистической игры билинейна и кососимметрична.

773 1

RAS Social ScienceЭкономика и математические методы Economics and the Mathematical Methods

Evgeny Golshtein

Interests

By this author

Indexing

RAS Social ScienceЭкономика и математические методы Economics and the Mathematical Methods

Evgeny Golshtein

Interests

By this author

Indexing

Via social network