Основные понятия теории игр

Игровые модели принятия решений

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

Под неопределенностью следует понимать отсутствие, неполноту информации об объекте, процессе, явлении или неуверенность в достоверности информации. Источниками неопределенности могут быть, например, погодные условия, противодействие противника, уровень надежности изделий, издержки при сборе и обработке информации и т.д. Достаточно частой является и такая ситуация, когда источником неопределенности является само лицо, принимающее решения (например, из-за неполной профессиональной компетентности). Во всех этих случаях говорят о возникновении ситуации риска.

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

Признаками ситуации риска являются:

· наличие неопределенности;

· необходимость выбора альтернатив (условий, которые, в общем то, невозможно не приять);

· возможность оценить вероятность осуществления выбираемых альтернатив.

С точки зрения полноты исходных данных определенность и неопределенность являются двумя крайними случаями, а риск определяет промежуточную ситуацию, в которой приходится принимать решение. Математический аппарат принятия решений в условиях риска и неопределенности представлен, в основном, в теории игр.

Игра - это совокупность правил, описывающих сущность конфликтной ситуации и возможные выходы из нее. Эти правила устанавливают:

· выбор действий игроков на каждом этапе игры;

· информацию, которой обладает каждый игрок при осуществлении выборов;

· плату для каждого игрока после завершения любого этапа игры.

В общем случае игру можно определить следующим образом:

· имеются n конфликтующих сторон (игроков), принимающих решения и, интересы которых не совпадают;

· сформулированы правила выбора допустимых стратегий, известные игрокам;

· определен набор возможных конечных состояний игры (например, выигрыш, ничья, проигрыш);

· всем игрокам заранее известны платежи, соответствующие каждому возможному конечному состоянию. Платежи задаются в виде матрицы A = ║a_ij║.

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

Игра называется конечной, если у каждого игрока конечное число стратегий. Результаты конечной парной игры с нулевой суммой можно задавать матрицей, строки и столбцы которой соответствуют различным стратегиям, а элементы - выигрышам одной из сторон (проигрышам другой стороны). Эта матрица называется платежной матрицей.

Если первый игрок имеет m стратегий, а второй n, то говорят, что мы имеем дело с игрой m ґ n. Рассмотрим такую игру. Пусть заданы множество стратегий: для первого игрока {A _i}, для второго игрока {B_j}, платежная матрица A m ґ n = a_ij, где a_ij - выигрыш первого игрока при выборе стратегий A_i и проигрыш второго - при выборе стратегии B_j. Поскольку интересы игроков противоположны, то первый стремиться максимизировать свой выигрыш, а второй - минимизировать свой проигрыш. Если игроки оба умны, то им целесообразно использовать очень пессимистичный критерий, что позволит им свести к минимуму выигрыш (проигрыш). Величина этого минимума

α_i=min a _ij,i= 1,…, m.

^j

Первый игрок (при любых ответах противника) будет стремиться найти такую стратегию, при которой α_i обращается в максимум

α=max α_i =max min a _ij.

^{i i j}

Величина α называется нижней ценой игры. Ей соответствует максиминная стратегия, при которой первый игрок обеспечит себе выигрыш не меньше α. Величина αявляется гарантированным выигрышем первого игрока при любых стратегиях второго игрока.

Аналогично определим по каждому столбцу матрицы β_j=max a_ij,j= 1,…,n, найдем минимальное значение β_j

β=min β_j=min max a _ij.

^{j j i}

Величина βназывается верхней ценой игры. Ей соответствует минимаксная стратегия второго игрока. Величинаβпредставляет собой гарантированный проигрыш второго игрока при любой стратегии первого игрока. Если α=β (то есть верхняя цена игры равна нижней цене), то соответствующие стратегии называют оптимальными, а про игру говорят, что она имеет седловую точку. Седловая точка является минимальным элементом соответствующей строки и максимальным элементом соответствующего столбца. Величина C = β=αназывается ценой игры. Она определяет средний выигрыш игрока А и средний проигрыш игрока В при использовании ими оптимальных стратегий.

Если в платежной матрице А все элементы строки A _i = (a_i1,a_i2,…, a_in) не меньще соответствующих элементов строки A _k=(a_k1,a_k2,…,a_kn), и по крайней мере один больше, то строка A _i называется доминирующей, а строка A _k - доминируемой. Аналогичны понятия «доминирующий столбец» и «доминируемый столбец». Первому игроку невыгодно применять стратегии, которым соответствуют доминируемые строки; второму игроку невыгодно применять стратегии, которым соответствуют доминирующие столбцы. Поэтому при решении игры можно уменьшить размеры платежной матрицы путем удаления из нее доминирующих столбцов и доминируемых строк.

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

Смешанная стратегия для игрока А представляет собой вектор P= {p₁,p₂,…,p_m}, а смешанная стратегия для игрока В представляет собой вектор Q= {q₁,q₂,…,q_n}, где p_i,q_j - вероятность выбораi-ой (j-ой) стратегии первым (вторым) игроком. Сумма каждой из этих вероятностей должна быть равна 1. В этом случае платежная матрица игры имеет вид (таблица 8.1)

Таблица 8.1

Игрок А выбирает стратегию p_i так, чтобы максимизировать наименьший ожидаемый выигрыш по столбцам платежной матрицы, тогда как игрок В выбирает стратегию q_j с целью минимизировать наибольший ожидаемый проигрыш по строкам. Математически при смешанных стратегиях это описывается следующим образом.

Игрок А выбирает стратегию p_i, дающую

_{m m m}

max{min(∑a_i1∙p_i,∑a_i2∙p_i,…,∑a_in∙p_i)},

^{pi i=1 i=1 i=1}

а игрок В выбирает стратегию q_j, дающую

_{n n n}

min{max(∑a_1j∙q_j,∑a_2j∙q_j,…,∑a_mj∙q_j)}.

^{qi j=1 j=1 j=1}

Когда стратегии p^*_i и q^*_j оптимальны, то выполняется строгое равенство между максиминным ожидаемым выигрышем и минимаксным проигрышем, а результирующее значение равно оптимальному (ожидаемому) значению игры:

_{m n}

M(p^*_i, q^*_j) = ∑ ∑a_ij∙p^*_i ∙q^*_j.

^{i=1 j=1}

Рассмотренные варианты теории игр могут служить основой для эффективного управления системами и процессами.