Линейные задачи оптимизации. Ч.1. Линейное программирование. Лутманов С.В. - 118 стр.

5. ПРИМЕНЕНИЕ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ В ТЕОРИИ ИГР


     Процесс игры можно трактовать следующим образом. Игроки независимо
друг от друга выбирают ряды матрицы A : первый игрок выбирает строку
матрицы, а второй игрок – столбец матрицы. Элемент матрицы A , стоящий на
пересечении выбранных рядов, является значением платы в игре. Описанную
игру будем называть матричной игрой с матрицей A .
     Существование седловой точки в матричной игре означает, что
наименьший элемент среди наибольших элементов из каждой строки совпадает
с наибольшим элементом среди наименьших элементов из каждого столбца.
Оптимальными стратегиями игроков будут те ряды матрицы A , на пересечении
которых стоит указанный элемент. Цена игры равна значению этого элемента.
     Пример 3. В матричной игре с матрицей
                                     æ2         6    -10ö÷
                                                      7
                                     çç                   ÷
                                      çç-3      4    -3 ÷÷÷
                                                      2
                                A = çç                    ÷
                                       çç 8     5 -3 1 ÷÷÷
                                        çç                ÷÷
                                         çè 0   5 6   7 ø÷÷

существует седловая точка. Она образована стратегией первого игрока,
состоящей в выборе второй строки, и стратегии второго игрока, состоящей в
выборе второго столбца. Цена игры здесь равна 4.
     В случае отсутствия седловой точки в игре полезно перейти к
расширенной модели конфликта. Следует считать, что игра повторяется много
раз. При этом игрока интересует выигрыш не в каждой отдельной партии, а
средний выигрыш по многим партиям.
     Определение 8. «Смешанной» стратегией первого игрока называется
вектор
                         æ u1 ö÷
                         çç ÷
                                   ÷
                    u = çç L ÷÷ Î R m , u i ³ 0, i Î {1,L, m} , å u i = 1 .
                                                                 m

                          çç ÷÷
                           çèu m ÷÷ø                            i=1




Множество всех «смешанных» стратегий первого игрока обозначим символом
U.

     Координату ui вектора u следует понимать как вероятность выбора
первым игроком строки матрицы с номером i Î {1,L, m} . Заметим, что частным

                                                118