Скачиваний:
94
Добавлен:
09.05.2014
Размер:
73.22 Кб
Скачать

Теория ИГР.

Теория ИГР – это математическая теория конфликтных ситуаций.

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

Рассмотрим ситуацию «перекресток»:

две машины едут навстречу друг другу.

  • Если вы оба снизите скорость, никто из вас ничего не проиграет.

  • Если вы затормозите, а он нет, то вы проиграете.

  • Если вы не снизите скорость, а он снизит, то он проиграет.

  • Если оба не снизите скорость, то оба проиграете (Произойдёт авария).

Этот пример нужен для осознания того, что могут проиграть и выиграть ОБА, а не только кто-то один.

В теории игр выделяются два поведения:

  • Личные

  • Вероятностные

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

При вероятностных – случайно (карты и другие азартные игры).

Существует понятие оптимальная стратегия – это такая стратегия, при многократном повторении которой (при многократном повторении игры) игроку обеспечивается максимальный средний выигрыш.

Основной принцип, заложенный при построении теории игр: мы не рассчитываем на ошибку противника (не рассчитываем, что он глупее нас).

Если игра состоит из нескольких ходов, то для нее всегда известна стратегия, ведущая к выигрышу. (крестики-нолики)

Стратегия игрока А – А

Стратегия игрока В – В

Каждой стратегии А можно сопоставить выигрыш игрока В. Для игр с нулевой суммой числа зеркальные.

Матрица при игре с «выкидыванием пальцев»: если сумма выкинутых пальцев четная, то мы выиграли, а если нечетная – противник.

наилучший выигрыш для противника

6 – наилучший выигрыш для нас

Противник выберет стратегию 4 или 4, а мы выберем -3.

Противник будет пытаться максимизировать свой выигрыш и минимизировать наш.

Еще один пример: Рассмотрим следующую игру:

У противника есть 3 типа самолетов. У нас есть 3 типа вооружения.

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

Матрица сопоставления: соответствие выбранного самолета выбранному вооружению.

Вооружение – А1, А2, А3

Самолеты - В1, В2, В3

наилучший выигрыш для противника

0,8 - наилучший выигрыш для нас

Противник не глупее нас, и мы с ним оба не знаем, что предпримет и предпочтет другой. Мы определяем некоторые аij, которые являются минимальным значением для каждой строки. ai=minaij.Затем из этих решений мы выбираем те, что принесут нам максимальный результат вне зависимости от «вредности» противника.

ά=max(i)min(j)aij - это минимальный выигрыш, «нижняя цена игры», хотя можем получить и больше.

Аналогично и противник: вi=max(j) aij

Минимаксный принцип: игра, для которой мы придерживаемся максиминной стратегии, а противник – минимаксной.

Для нас оптимальной является первая стратегия (в примере с «выкидыванием пальцев»). Если мы все время будем ее применять, то противник это поймет и накажет нас, выбрав стратегию 2 (-3).

Наши шаги при выборе стратегии:

  1. наш выбор стратегии: а11

  2. его выбор стратегии: а12

  3. наш выбор стратегии: а22

  4. его выбор стратегии: а32

Вернемся ко второму примеру: и для нас, и для противника оптимальная стратегия: а22(0,7). ά=β=γ. Игры, где верхняя и нижняя цена игры равны, называются играми с седловой точкой. Для них характерно:

  • Если любой из противников меняет стратегии, то неизбежно проигрывает.

  • γ - чистая цена игры.

  • Стратегия, соответствующая седловой точке, - ОПТИМАЛЬНА.

  • Если один из игроков придерживается этого принципа, то другому игроку не может быть выгодно менять стратегию.

  • Игры с Седловой точкой обладают устойчивостью.

  • Решение надо искать в смешанных стратегиях.

Мы имеем стратегии: А1, А2,… А3

Противник имеет стратегии: В1, В2,…Вn

Сопоставим вероятности выбора оптимальной стратегии:

SA*=(p1;p2; p3;…pn)

SB*=(q1;q2; q3;qn)

Решением игры называется пара оптимальных стратегий SA* и SB*, таких что если один придерживается оптимальной смешанной стратегии, то другому не может быть выгодно отступать от этой стратегии. Выигрыш соответствующего решения называется ЦЕНОЙ ИГРЫ. Если один из игроков придерживается оптимальной смешанной стратегии, то выигрыш остается неизменным и равным γ (цене игры) вне зависимости от того, что делает другой игрок, если только тот не выходит за пределы своих активных стратегий.

Рассмотрим простейший случай:

Имеется игра 2х2

Если есть седловая точка, то всё хорошо и дальше ничего делать не надо. Если нет, то ищем SA*=(p1;p2;) и SB*=(q1;q2;). Мы применяем нашу оптимальную стратегию с вероятностью р1а11 и р2а12, а противник только с вероятностью р1.

Чему равен средний выигрыш? γ= р1а11 + р2а21. Если мы применим смешанную стратегию, а противник - стратегию В, то выигрыш будет: γ= р1а21 + р2а22

р1 + р2=1

Если мы выбираем А2, а противник – В2,то схема будет такой. Любой смешанной стратегией будет соответствовать точка А1 и А2. N- максимально получаемый выигрыш вне зависимости от стратегии противника.

Каждой стратегии В соответствует некоторая прямая.

SA*=p1;p2; p3;…pn

SB*=q1;q2; q3;…qn

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

Наш выигрыш при применении оптимальной смешанной стратегии:

p1а11+ p2а21+pmam1γ (1 – противник использует В1. Если противник будет применять В2, то на месте этой единицы будет 2). Это мат. ожидание выигрыша.

p1а1n+ p2а2n+pmamnγ разделим все на γ

p1+p2+p3 …+pn=1

Обозначим х11/γ х22/γ х33/γ

Получим

L→min; γ→max; значит наш выигрыш будет максимальным.

Пример (пример с пальцами)

Прибавим везде 5

Решаем, находим х, интересующий нас: γ'= γ+5

5