Статьи автора

Гибридный метод поиска решения биматричных игр

Выпуск 2 от 29.06.2018

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

2144 14

ГИБРИДНЫЙ МЕТОД ПОИСКА РЕШЕНИЯ БИМАТРИЧНЫХ ИГР

от 01.04.2018

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

947 8

ЭФФЕКТИВНОСТЬ ПРИБЛИЖЕННОГО МЕТОДА РЕШЕНИЯ КОНЕЧНОЙ ИГРЫ ТРЕХ ЛИЦ (ВЫЧИСЛИТЕЛЬНЫЙ ОПЫТ)

Выпуск № 1 от 01.01.2017

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

995 4

ПРИБЛИЖЕННЫЙ МЕТОД РЕШЕНИЯ КОНЕЧНОЙ ИГРЫ ТРЕХ ЛИЦ

Выпуск № 1 от 01.01.2014

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

886 1

О МОДИФИКАЦИЯХ КОНЕЧНОЙ БЕСКОАЛИЦИОННОЙ ИГРЫ, ИМЕЮЩИХ ВЫПУКЛУЮ СТРУКТУРУ

Выпуск №4 от 01.10.2010

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

855 2

ОБ ОДНОЙ ЗАДАЧЕ РАВНОВЕСИЯ, СВЯЗАННОЙ С БЕСКОАЛИЦИОННЫМИ ИГРАМИ

Выпуск №4 от 01.10.2009

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

921 0

ОБ ОДНОМ ЧИСЛЕННОМ МЕТОДЕ РЕШЕНИЯ БИМАТРИЧНЫХ ИГР

Выпуск № 4 от 01.10.2013

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

941 1

МЕТОД РЕШЕНИЯ ВАРИАЦИОННЫХ НЕРАВЕНСТВ, ИСПОЛЬЗУЮЩИЙ НЕТОЧНЫЕ ИСХОДНЫЕ ДАННЫЕ

Выпуск №3 от 01.07.2008

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

830 2

О МОНОТОННОСТИ ОТОБРАЖЕНИЯ, СВЯЗАННОГО С НЕАНТАГОНИСТИЧЕСКОЙ ИГРОЙ ДВУХ ЛИЦ

Выпуск №4 от 01.10.2008

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

855 2

ОБ ОДНОМ КЛАССЕ АНТАГОНИСТИЧЕСКИХ ИГР

Выпуск № 3 от 07.07.2012

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

895 1

СЕДЛОВОЙ МЕТОД, ИСПОЛЬЗУЮЩИЙ НЕТОЧНЫЕ ИСХОДНЫЕ ДАННЫЕ

Выпуск №3 от 01.07.2007

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

850 0

МЕТОДЫ БЛОЧНОГО ПРОГРАММИРОВАНИЯ

Выпуск 1 от 01.01.1966

901 0

ОБ ОДНОМ ВИДОИЗМЕНЕНИИ МЕТОДА ПОСЛЕДОВАТЕЛЬНОГО УЛУЧШЕНИЯ ПЛАНА

Выпуск № 1 от 06.01.1965

769 0

ДВОЙСТВЕННЫЕ ЗАДАЧИ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ

Выпуск № 3 от 06.05.1965

699 0

О НЕКОТОРЫХ СОВРЕМЕННЫХ НАПРАВЛЕНИЯХ В МАТЕМАТИЧЕСКОМ ПРОГРАММИРОВАНИИ

Выпуск №5 от 01.09.1967

645 0

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

Номер 4 от 01.07.1968

647 0

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

Номер 6 от 01.11.1968

786 0

ОБ ОДНОМ КЛАССЕ АНТАГОНИСТИЧЕСКИХ ИГР

Номер 3 от 20.07.2012

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

773 1

Экономические оптимизационные задачи большой размерности (американо-советский семинар)

Выпуск № 2 от 02.03.1981

670 0

О некоторых последних до стижениях в оптимизации

Выпуск № 1 от 01.01.1990

812 0

Диалоговая система анализа многокритериальных задач

Выпуск № 4 от 01.08.1990

684 0

Новый алгоритм двойственной декомпозиции с приложением к задачам транспортного типа

Выпуск № 2 от 01.04.1994

711 0

Соотношение цен и зарплаты в экономике, описываемой расширенной моделью “затраты-выпуск"

Выпуск № 2 от 01.04.1995

659 0

Метод уровней, его обобщения и приложения

Выпуск № 3 от 01.07.1995

740 0