Суть этого алгоритма [92] состоит в соединении основной схемы итеративного алгоритма решения соответствующей нецелочисленной задачи с идеей доводки его до целочисленного методом случайного поиска. Итеративный алгоритм, основанный на идее известного метода Брауна— Робинсона решения матричных игр, дает возможность получить приближенное решение задачи линейного программирования при небольших затратах машинного времени. Проведенные эксперименты доказывают, что в применении к некоторым классам задач линейного программирования итеративные алгоритмы могут конкурировать с симплексными [92]. [c.190]
Вообще говоря — это матричная игра, т. е. антагонистиче- [c.32]
Матричные игры. М. Государственное издательство [c.324]
С математической точки зрения деловые игры представляют собой общий случай стратегических матричных игр, в которых по определенным правилам находится оптимальная (минимаксная) стратегия. Необходимым условием игры является наличие противоречия или конфликта между сторонами в системе управления. Взаимодействие участников игры обусловлено специальными правилами. Эти правила выражают права и обязанности сторон, зафиксированные в действующих законодательных актах (постановлениях, приказах, инструкциях и т. п.). Важной составляющей деловых игр является информация, на основе которой (в соответствии с правилами игры) принимаются решения. Кроме того, в деловых играх предусматриваются критерии деятельности участников, по которым производится оценка эффективности принимаемых решений. [c.115]
Глава 1 МАТРИЧНЫЕ ИГРЫ [c.23]
Определение. Антагонистические игры, в которых каждый игрок имеет конечное множество стратегий, называются матричными играми. [c.25]
Процесс "игры в матричную игру" удобно представить себе следующим образом задается матрица А игрок 1 выбирает некоторую строку этой матрицы, а игрок 2 — некоторый ее столбец. Эти выборы осуществляются игроками независимо друг от друга. После того как выборы произведены, игрок 1 получает от игрока 2 выигрыш, равный числу, стоящему на пересечении выбранных строки и столбца. Разумеется, если это число отрицательное, то речь идет о фактическом проигрыше игрока 1. [c.25]
Ясно, что матрицы выигрышей в изоморфных друг другу матричных играх отличаются друг от друга разве лишь порядками строк и столбцов, а в зеркально-изоморфных друг другу играх — еще и транспонированием с переменой знаков всех элементов. [c.25]
Применительно к матричным играм говорят о седловых точках матрицы выигрышей. П [c.33]
Пусть некоторый класс игр Ж является "зеркально-замкнутым", т.е. вместе с каждой своей игрой содержит зеркально изоморфную ей (так как все игры, зеркально изоморфные данной, изоморфны друг другу, мы, в соответствии с только что сказанным, можем говорить об одной зеркально изоморфной игре). Таким классом является, например, класс всех антагонистических игр или класс всех матричных игр. [c.37]
Обратимся теперь непосредственно к рассмотрению матричных игр. Матричную игру с матрицей выигрышей А будем, как указывалось, обозначать через Г . Если не оговорено противное, матричная игра будет считаться т X -игрой. Стратегии игрока ] обозначаются номерами соответствующих строк, а стратегии игрока 2 — номерами столбцов, /-я строка матрицы А обозначается через Л/, /-и ее столбец — через Л/у, а элемент, стоящий на их пересечении, — через а . [c.42]
Очевидно, ситуацией в матричной игре можно считать пару чисел (/,/), где / — номер строки матрицы выигрышей, / — номер ее столбца. [c.42]
Ввиду конечности множеств стратегий в матричной игре все относящиеся к ее стратегиям экстремумы достигаются, так что минимаксы (2.5) и (2.6) могут быть записаны как [c.42]
В соответствии с теоремой п. 6.1 для существования в матричной игре седловых точек необходимо и достаточно, чтобы были равны мини-максы (7.1) max min я/у = min max л/у общее значение этих минимаксов [c.42]
Фундаментальные симплексы смешанных стратегий игроков 1 и 2 в матричной игре Г = (х, у, Я) обозначаются соответственно через X и Y. Заметим, что X и Y являются компактами. [c.45]
СМЕШАННОЕ РАСШИРЕНИЕ МАТРИЧНОЙ ИГРЫ [c.45]
По любой матричной игре можно построить игру, стратегиями которой являются смешанные стратегии исходной матричной игры. [c.45]
Определение. Смешанным расширением матричной игры Г = [c.46]
Вспоминая определение приемлемых ситуаций в антагонистической игре, получаем, что ситуация (X, Y ) в смешанном расширении матричной игры является приемлемой для игрока 1 тогда и только тогда когда при любом х G х выполняется неравенство [c.46]
Произведение X AY T является значением смешанного расширения матричной игры. [c.46]
Теорема. Если Г = < X, Y, //> — смешанное расширение матричной игры ТА = Г, то [c.47]
Таким образом, из наличия у матричной игры значения следует его наличие и в ее смешанном расширении, а также равенство этих двух значений. Это дает нам основание говорить просто о значении матричной игры Г , обозначая его просто через v д и прибавляя, когда это нужно, слова "в чистых стратегиях" или "в смешанных стратегиях". [c.48]
Теорема. Если две матричные игры ГА и Г аффинно эквиваленты, то их смешанные расширения также аффинно эквивалентны. [c.48]
Теорема. Если п - изоморфизм матричной игры Г - < х, у, Я > на матричную игру Г = < х , у , Я >, Г и Г - смешанные расширения этих игр и для любых X X, л х, Y E.Y и у .у положено [c.48]
Случай зеркального изоморфизма игр рассматривается аналогично. П 9.9. Далее мы докажем, что ситуация равновесия в смешанном расширении существуют для любой матричной игры. [c.49]
Нашей ближайшей задачей является доказательство существования в матричных играх ситуации равновесия в смешанных стратегиях. Согласно теореме п. 6.1 для этого необходимо и достаточно установить существование и равенство минимаксов [c.49]
ЗАДАЧА РЕШЕНИЯ МАТРИЧНЫХ ИГР [c.55]
Доказанная в предыдущем параграфе теорема о минимаксах утверждает, что во всякой матричной игре игроки имеют смешанные оптимальные стратегии. Однако никаких явных путей для вычисления таких стратегий эта теорема не указывает. В этом смысле она оказывается типичной "теоремой существования". Проанализируем складывающееся в связи с этим положение дел. [c.55]
Установление существования в матричных играх оптимальных стратегий игроков означает, прежде всего, реализуемость принципа мак симина. По существу это выражает тот "метаматематический" факт, что принцип мак-симина не противоречит конструкции матричной игры и ее смешанного расширения. Этот факт может стать побудительным мотивом к поискам опти- [c.55]
Впрочем, для матричных игр все эти проблемы получают достаточно удовлетворительное и притом сравнительно простое решение. [c.56]
Теорем а. Для матричной игры ТА имеет место соотношение [c.56]
Следующие критерии оптимальности стратегий игроков в матричной игре не предполагают знания значения этой игры. [c.57]
МНОЖЕСТВА ОПТИМАЛЬНЫХ СТРАТЕГИЙ ИГРОКОВ В МАТРИЧНЫХ ИГРАХ [c.59]
Теорема. В матричной игре Г множества оптимальных стратегий игроков (А) и ОТ (А) являются выпуклыми непустыми многогранниками. [c.59]
Нэш Д. Бескоалиционные игры / Матричные игры. М. Физматгиз, [c.139]
Матричные игры. Для выбора решения применяется платеж- пая матрица, или матрица решений. Она представля тсобой таблицу, в которой по вертикали указываются возможные решения, [c.116]
См. также Антагонистические игры, Бескоалиционные игры, Бесконечные игры, Биматричиая игра, Дифференциаль-ные игры, Игра с "природой ", Игры с непротивоположными интересами, Игры с ненулевой суммой, Игры с нулевой суммой, Конечные и бесконечные игры, Кооперативные игры, Матричные игры, Некооперативные игры, Парные игры, Позиционные игры, Прямоугольные игры. [c.112]
МАТРИЧНЫЕ ИГРЫ [matrix games] — класс антагонистических игр, в которых участвуют два игрока, причем каждый игрок располагает конечным числом стратегий. Если один игрок имеет т стратегий, а второй — п, то можно построить матрицу игры размерностью тхп. М.и. могут иметь седловую точку, но могут и не иметь ее. В последнем случае решение игры в чистых стратегиях невозможно и оптимальные стратегии игроков отыскиваются среди их смешанных стратегий. М.и. для нахождения таких стратегий удобно преобразовывать в задачи линейного программирования. [c.189]
Матричная игра полностью определяется своей матрицей выигрышей. Поэтому игру с матрицей выигрышей А мы будем обычно обозначать через ГА или Г (Л). Если А является гаХи-матрицей (т.е. имеет m строк и п столбцов), то будем говорить, что ГА есть m X -игра. [c.25]
Определение. Пара (X, У) смешанных стратегий игроков в матричной игре, где X и Y как случайные величины являются независимыми, назьюается ситуацией в смешанных стратегиях в этой игре. G [c.45]
Матричная игра, очевидно, является подыгрой своего смешанного расширения. Для седловых точек этих игр справедливо обращение свойства независимости от посторонних альтернатив (п. 5.4). Кроме того, это свойство распространяется и на оптимальные стратегии игроков (см. п. 5.6). [c.47]
С л е дств и е 2.- Для существования в смешанном расширении матричной игры ситуаций равновесия необходимо и достаточно доказать существование и равенство минимаксов [c.50]
Смотреть страницы где упоминается термин Матричные игры
: [c.212] [c.12] [c.58] [c.58] [c.473] [c.80] [c.42] [c.56]Смотреть главы в:
Теория игр для экономистов-кибернетиков -> Матричные игры
Экономические и финансовые риски Оценка, управление, портфель инвестиций -> Матричные игры
Теория риска и моделирование рисковых ситуаций -> Матричные игры