Лекция 14. Принятие решений в условиях неопределенности. Введение в матричные игры.

Комбинированный метод шифрования является наиболее рациональным, объединяя в себе высокое быстродействие симметричного шифрования и высокую криптостойкость, гарантируемую системами с открытым ключем.

Таким образом, при комбинированном методе шифрования применяются криптографические ключи как симметричных, так и асимметричных криптосистем.

Такой подход иногда называют схемой электронного цифрового конверта.

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

1. Создать (например, сгенерировать случайным образом) симметричный ключ, называемый в этом методе сеансовым ключом K_s.

2. Зашифровать сообщение PT на сеансовом ключе K_s.

3. Зашифровать сеансовый ключ K_s на открытом ключе К_В1 пользователя В.

4. Передать по открытому каналу связи в адрес пользователя В зашифрованное сообщение вместе с зашифрованным сеансовым ключом.

Действия пользователя В при получении зашифрованного сообщения и зашифрованного сеансового ключа должны быть обратными:

5. Расшифровать на своем секретном ключе К_В2 сеансовый ключ K_s.

6. С помощью полученного сеансового ключа K_s расшифровать и прочитать сообщение PT.

При использовании комбинированного метода шифрования можно быть уверенным в том, что только пользователь В сможет правильно расшифровать ключ K_s и прочитать сообщение PT.

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

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

Таблица 4.3

Длины ключей для симметричных и асимметричных криптосистем при одинаковой их криптостойкости

Комбинированный метод допускает возможность выполнения процедуры аутентификации, т.е. проверки подлинности передаваемого сообщения.

Для этого пользователь А на основе функции хэширования сообщения и своего секретного ключа К_А с помощью известного алгоритма электронной цифровой подписи (ЭЦП) генерирует свою подпись и записывает ее, например, в конец передаваемого файла.

Пользователь В, прочитав принятое сообщение, может убедиться в подлинности цифровой подписи абонента А.

Используя тот же алгоритм ЭЦП и результат хэширования принятого сообщения, пользователь В проверяет полученную подпись (см. след лек).

14.1.Основные понятия теории игр.Введение в матричные игры

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

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

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

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

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

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

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

Под антагонистической игрой понимается взаимодействие двух субъектов (организаций, фирм, стран) с противоположными интересами.

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

Оптимальной стратегией называют такую стратегию, при которой достигается максимальный ожидаемый средний выигрыш игрока или минимально возможный средний проигрыш (независимо от поведения противника) при многократном повторении игры.

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

Матричные игры — это игры, где два игрока играют в игру с нулевой суммой, имея конечное число «чистых» стратегий: {1,…, m} и {1,…, n} и "(ij) задан платеж a_ij второго игрока первому. Матрица (a_ij) задает выигрыш первого игрока и проигрыш второго.

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

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

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

14.2. Формальное описание матричной антагонистической игры

Важными и хорошо изученными играми являются парные антагонистические игры.

Тройка G=<X,Y,A>, где X, Y - множества чистых стратегий 1-го и 2-го игроков соответственно, A(x,y) xX, yY – функция выигрыша первого игрока, или просто функция выигрыша, называется антагонистической игрой с нулевой суммой.

Если X и Y конечны, то G называется конечной антагонистической игрой. Пары стратегий вида (x,y) называются ситуациями в игре G. Цель каждого из игроков в игре – получить максимальный выигрыш. Игрок 1, изменяя xX, старается максимизировать A(x,y), а игрок 2 выбирает yY так, чтобы минимизировать A(x,y), но каждый из игроков в отдельности не контролирует полностью значение A(x,y). Задача теории игр состоит в определении наиболее рационального поведения каждого игрока.

Процесс разыгрывания конечной антагонистической игры состоит в следующем.

1) 1-й игрок выбирает чистую стратегию xX;

2) Независимо от первого игрока 2-й игрок выбирает чистую стратегию yY;

3) Возникает ситуация (x,y), в которой 1-й игрок получает от 2-го игрока выигрыш A(x,y), при этом 2-й игрок столько же проигрывает, т.е. его выигрыш составляет - A(x,y).

Так как число возможных действий каждого из игроков конечно, а содержательная сущность стратегии определяется вне математической модели, можно предполагать, что 1-й игрок имеет m стратегий, т.е. X={1,2,…,m, }, а 2-й игрок имеет n стратегий, т.е. Y={1,2,…,n}. Пусть из своих m стратегий 1-й игрок выберет i-ю стратегию (i=1,…m), а 2-й игрок выберет j-ю стратегию (j=1,…n), тогда значения функции A(x,y) естественно представить в виде матрицы A размерности m×n

где в i-й строке расположены выигрыши 1-го игрока в ситуациях (i,1),…,(i,n), а в j-м столбце – проигрыши 2-го игрока в ситуациях (1,j),…,(m,j).