26. Предмет теории игр. Примеры игровых моделей в экономике.

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

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

27. Антагонистическая игра двух лиц с нулевой суммой. Платежная матрица.

Игра называется игрой с нулевой суммой, или антагонистической, если выигрыш одного из игроков равен проигрышу другого, т.е. для полного задания игры достаточно указать величину одного из них. Если обозначить а — выигрыш одного из игроков, b —выигрыш другого, то для игры с нулевой суммой b = —а, поэтому достаточно рассматривать, например а.

Платежная матрица:

Bi Aj	B1	B2	…	Bn
A1	a11	a12	…	a1n
A2	a21	a22	…	a2n
…	…	…	…	…
Am	am1	am2	…	amn

28. Оптимальные стратегии игроков. Верхняя и нижняя цена игры и соотношение между ними.

Оптимальная стратегия – стратегия, которая при многократном применении обеспечивает игроку максимально возможный выйгрыш.

Рассмотрим игру т х п с матрицей Р = (a_ij), i =1,2,...,т; j =1,2,...,п и определим наилучшую среди стратегий А₁,A₂,...,А_т. Выбирая стратегию А_i игрок А должен рассчитывать, что игрок В ответит на нее той из стратегий В_j, для которой выигрыш для игрока А минимален (игрок В стремится "навредить" игроку А).Обозначим через α_i, наименьший выигрыш игрока А при выборе им стратегии А_i для всех возможных стратегий игрока В(наименьшее число в i-ой строке платежной матрицы), т.е.

min a_ij = α_i

^j=1,...,n

Среди всех чисел α_i (i =1,2,...,m) выберем наибольшее:

α = max α_i

i=1,2,…,m

Назовем α нижней ценой игры, или максимальным выигрышем (максимином). Это гарантированный выигрыш игрока А при любой стратегии игрока В. Следовательно,

α = max min a_ij

i = 1,…,m j=1,…,n

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

β_j, = max a_ij

i = l,...,m

Среди всех чисел β_j выберем наименьшее β=min β_j

_j=1,2,...,n

и назовем β верхней ценой игры или минимаксным выигрышем (минимаксом). Это гарантированный проигрыш игрока В. Следовательно,

β = min max a_ij

j=1,…,п i=1,…,т

Стратегия, соответствующая минимаксу, называется минимаксной стратегией.

29. Игра с седловой точкой. Решение игры в чистых стратегиях. Приведите примеры игр с седловой точкой.

Седловая точка в математическом анализе— такая точка из области определения функции, которая является стационарной для данной функции, однако не является ее локальным экстремумом. Класс игр, имеющих седловую точку, имеет большое значение в теории игр. В частности, доказано, что если по правилам игры каждый из игроков знает результат всех предыдущих ходов, как своих, так и противника (так называемая игра с полной информацией), то игра имеет седловую точку и, значит, имеет решение в чистых стратегиях.       Примерами игр с полной информацией могут служить: шахматы, шашки, «крестики и нолики» и т. п. Приведем пример игры с полной информацией, решение которой легко найти.       Два игрока — К и С — поочередно кладут одинаковые монеты на круглый стол. Положение каждой монеты выбирается произвольно, лишь бы она не перекрывалась другими. Выигрывает тот из игроков, который положит монету последним (когда места для других уже не остается).       Стоит немножко подумать, чтобы убедиться, что исход этой игры всегда предрешен и что существует вполне определенная стратегия, гарантирующая выигрыш тому из игроков, который кладет монету первым (пусть это будет К). А именно К должен положить первую монету в центр стола, а далее на каждый ход С отвечать в точности симметричным относительно центра стола ходом! Бедный С может при этом вести себя как угодно, спасения ему все равно нет...       Очевидно, такая игра имеет смысл только для тех, кто не знает решения. Любопытно, что совершенно так же обстоит дело и с такой популярной игрой, как шахматы! Эта игра имеет смысл только до тех пор, пока не найдено ее решение.       Теоретически доказано, что решение существует и исход шахматной игры в сущности предрешен: если каждая сторона будет пользоваться своей оптимальной стратегией, то игра либо всегда будет кончаться выигрышем белых, либо всегда выигрышем черных, либо всегда ничьей! Но чем же именно? Мы пока этого не знаем, так как число возможных стратегий слишком велико, чтобы можно было построить матрицу шахматной игры и найти в ней седловую точку... Заметим в заключение, что седловых точек в матрице может быть не одна, а несколько; тог да решений игры в чистых стратегиях существует столько, сколько имеется седловых точек. Каждое из них дает выигрыш, равный цене игры.

30. Смешанные стратегии. Свойство оптимальности. Теорема Неймана.

Мы знаем, что если нижняя цена игры а равна верхней b (максимин равен минимаксу) то игра имеет седловую точку и по крайней мере одно решение в чистых стратегиях.       А если α ≠ β? Можно доказать, что и в этом случае решение всегда есть, только оно лежит не в области чистых, а в области смешанных стратегий. Решением игры называется такая пара стратегий — в общем случае смешанных, систематическое применение которых обеспечивает каждой стороне максимально возможный для нее по условиям игры выигрыш, определяемый ценой игры. Если же одна из сторон отступает от своей оптимальной стратегии (в то время как другая продолжает придерживаться своей), то это ни в коем случае не может быть выгодно для отступающего; это либо оставит его выигрыш неизменным, либо уменьшит. Таким образом, каждая конечная игра имеет решение (возможно, в области смешанных стратегий). Это положение называется основной теоремой теории игр.