Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

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


Теория игр.

В практических задачах иногда необходимо найти оптимальное решение в условиях неопределенности. Такого рода задачами занимается раздел математики «Теория игр и статистических решений». Методы, предложенные в нем, часто не дают оптимального решения, а попросту помогают разобраться в ситуации, оценить каждое решение с различных точек зрения. Руководствуясь этими методами, можно принять до конца продуманное решение. Риск при выборе решения в условиях неопределенности всегда неизбежен. Задача: сделать его по возможности минимальным.

Остановимся на математической теории конфликтных ситуаций. Здесь изучаются проблемы выбора коллективных решений, т.е. когда решение принимается рядом лиц (игроков), интересы которых не совпадают. Цель теории игр – выработка рекомендаций по разумному поведению участников конфликта.

Чтобы сделать возможным математический анализ конфликта, строится его математическая модель, называемая игрой. От реального конфликта игра отличается тем, что ведётся по определённым правилам. Эти правила указывают «права и обязанности» участников, а также исход игры – выигрыш (проигрыш) каждого в зависимости от сложившейся обстановки. Игра – это имитационная модель, развитие которой во времени можно представить как ряд последовательных ходов участников. Ход – это выбор игроком предусмотренного игрой действия. Ходы бывают личные, когда игрок сознательно выбирает вариант действия (шахматы) и случайные, осуществляемые механизмом случайного выбора (бросание кубика, вынимание карт из колоды). Стратегией игрока называется совокупность правил, определяющих выбор варианта действий при каждом личном ходе в зависимости от сложившейся ситуации. Оптимальной стратегией игрока называется такая, которая обеспечивает ему наилучшее положение в игре, т.е. максимальный выигрыш.

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

 

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

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



  В1 В2 . . . Вn
A1 a11 a12 . . . a1n
A2 a21 a22 . . . A2n
Am am1 am2 . . . amn

 

ПРИМЕР 5.1.

  В1 В2 В3 В4 В5 min
A1 3 4 5 2 3 2
A2 1 8 4 3 4 1
А3 10 3 1 7 6 1
A4 4 5 3 4 8 3
max 10 8 5 7 8

Какой стратегией лучше всего воспользоваться игроку А? Стремление получить максимальный выигрыш в 10 единиц, может привести к жалкому выигрышу в 1 единицу, т.к. разумный противник в ответ на нашу стратегию А3 выберет стратегию В3. Исходя из принципа осторожности («всегда рассчитывай на худшее»), надо выбрать ту стратегию, при которой наш минимальный выигрыш максимален. Это «принцип минимакса»: поступай так, чтобы при наихудшем для тебя поведении противника получить максимальный выигрыш. Из всех наших минимальных выигрышей максимальным будет 3. Выбрав соответствующую ему стратегию A4, мы получим гарантированный выигрыш в 3 единицы. Этот выигрыш является нижней ценой игры (максимин). Теперь порассуждаем за противника. Из всех своих стратегий он предпочтёт ту, в которой отдаст минимум из возможных максимальных выигрышей игрока А. Этот выигрыш является верхней ценой игры (минимакс). В нашем примере такой стратегией является В3. При изменении стратегии одним игроком противник также может сменить стратегию, и цена игры будет колебаться.

Нижняя цена игры Vн– максимальный из всех возможных минимальных выигрышей. Верхняя цена игры Vв – минимальный из всех возможных максимальных выигрышей. В примере Vн =max(min aij)=3; Vв=min(max aij )=5.

В случае, когда Vн =Vв, минимаксные стратегии игроков будут устойчивыми. Стратегии, при которых этот выигрыш достигается, называются оптимальными чистыми стратегиями, их совокупность – решением игры, а выигрыш – седловой точкой.Игры с полной информацией всегда имеют седловую точку и решаются в чистых стратегиях. Но если решение игры известно, то играть не имеет смысла.

 

<== предыдущая лекция | следующая лекция ==>
Максимальный поток на сети | Задачи, приводимые к матричным играм

Дата добавления: 2014-01-20; Просмотров: 269; Нарушение авторских прав?


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Рекомендуемые страницы:

Читайте также:
studopedia.su - Студопедия (2013 - 2020) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление
Генерация страницы за: 0.002 сек.