WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 |   ...   | 8 | 9 || 11 |

Отрицательное значение платежной функции означает "проигрыш" игрока, например, если Q1 (x, y) = 5, то это означает, что первый игрок выиграл 5 единиц, а если Q1 (x, y) = –5, то первый игрок проиграл 5 единиц. Целью первого игрока является максимизация выигрыша, т.е. функцию Q1 (x, y) необходимо максимизировать. Очевидно, что целью первого игрока могла бы быть минимизация функции проигрыша Q1 (x, y), которая равна функции выигрыша, взятой с обратным знаком Q1 (x, y) = – Q1 (x, y).

Следовательно, Q1 (x, y) = 5 означает, что первый игрок проиграл 5 единиц, а Q1 (x, y) = –5 означает, что первый игрок выиграл 5 единиц.

Эти две задачи имеют, очевидно, право на существование, однако, в теории игр первый игрок всегда полагается выигрывающим, и платежная функция Q1 (x, y) определяет его выигрыш. Проигрышу соответствует отрицательное значение Q1 (x, y).

Аналогичные замечания могут быть отнесены к платежной матрице Qi любого i-го игрока.

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

Пусть Х – множество чистых стратегий, а х1, х2, …, хn – n чистых стратегий из этого множества.

Пусть игрок принимает решение использовать все эти чистые стратегии с разными вероятностями 1, 2, …, n. При этом игрок выбирает (варьирует) не чистые стратегии х1, х2, …, хn – они всегда заданы (одинаковые), а частоту (вероятность) использования каждой из них.

В этом случае стратегией будет вектор вероятностей = (1, 2, …, n), игрок должен пытаться найти такую стратегию (такое значение), при которой он получит максимальный успех.

Стратегия выбора вероятности называется смешанной стратегией.

Рассмотрим следующий пример. Так, чистыми стратегиями является установка орудия на север, юг, запад, восток. Смешанная стратегия = (0,1; 0,5; 0,2; 0,2) означает, что 10 % времени орудие смотрит на север, 50 % на юг и по 20 % времени оно повернуто на запад и восток. Если чистыми стратегиями являются покупка сахара, муки, картофеля, то = (0,5; 0,2; 0,3) означает, что деньги истрачены следующим образом: 50 % на сахар, 20 % на муку, 30 % на картофель. Принятие чистой стратегии означает, что покупатель принял решение истратить все деньги на один из этих продуктов.

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

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

Пусть в игре двух игроков первый игрок выбрал чистую стратегию х, а второй – чистую стратегию у, тогда ситуацией будет вектор (х, у).

Ситуацией в смешанных стратегиях будет вектор (, ), где = (1, …, n) – смешанная стратегия первого игрока, = (1, …, m) – смешанная стратегия второго игрока, i – вероятность использования чистой стратегии xi первым игроком, i – вероятность использования чистой стратегии yi вторым игроком.

Если ситуация сформулирована, то говорят, что игра состоялась.

Оценка стратегии игрока проводится по гарантированному выигрышу, т.е. по значению минимального выигрыша для данной стратегии. Так, для первого игрока оценка стратегии х проводится по функции ~ Q1(x) = min Q1(x, y), (6.1) yY в случае применения чистой стратегии или по функции ~ Q1() = minQ1(,) в случае применения смешанной стратегии, где – множество значений вектора вероятности = (1, …, m) второго игрока.

Очевидно, первому игроку хотелось бы выбрать такое х* или такой вектор *, при котором гаранти~ рованный выигрыш Q1(x) принял бы максимальное значение ~ ~ Q1(x*) = max Q1(x) x X или ~* ~ Q1 = Q1(x*) = max minQ1(x, y). (6.2) x X yY ~ Стратегия х*, доставляющая максимум гарантированному выигрышу Q первого игрока, называется максиминной x* = arg max min Q1(x, y). (6.3) x X yY Второму игроку также хотелось бы получить максимальное значение своего гарантированного вы~* игрыша Q2, который определяется аналогичным образом ~* ~ Q2 = Q2( y*) = max min Q2(x, y).

yY x X Однако ситуация (х*, у*) не всегда может считаться наилучшей. Действительно, х* – наилучшая стратегия, если у любая, а если у принимает конкретное значение у*, то, очевидно, что в общем случае можно найти другое х**, при котором Q1 (x**, y**) будет больше, чем Q1 (x*, y*).

Наилучшей ситуацией будет такая ситуация, при которой ни первому, ни второму игроку не выгодно от нее отклоняться. В теории игр такая ситуация носит название равновесной (х0, у0) Q1(x0, y0) Q1(x, y0), (6.4) Q2(x0, y0) Q2(x0, y).

Решением игровой задачи является нахождение наилучшей равновесной ситуации. Эта ситуация называется оптимальной.

Задачей теории игр является разработка алгоритмов нахождения равновесной (оптимальной) ситуации.

6.2 КЛАССИФИКАЦИЯ ИГРОВЫХ ЗАДАЧ Классификация игр, используемых в игровых задачах, представлена на рис. 6.2. Различают следующие игры.

Антагонистические игры моделируют конфликтные ситуации двух или многих лиц, интересы которых противоположны. Например, в случае двух игроков выигрыш одного равен проигрышу другого.

Неантагонистические игры (бесконфликтные) – это игры, в которых интересы сторон частично могут совпадать, они не являются диаметрально противоположными. Неантагонистические игры делятся на коалиционные и некоалиционные.

В коалиционных играх игроки могут договориться о целях, составить договор, объединиться.

Все игры делятся на конечные и бесконечные.

Конечными играми называются игры, имеющие конечное или счетное множество стратегий. В таких играх стратегии можно пометить цифрами i = 1, 2, …, n. Таким образом, вместо множества Х имеем множество (конечное или счетное) стратегий I = { i / 1, 2, …, n} – первого игрока и J = { j / 1, 2, …, m} – второго игрока.

ИГРЫ (состязательные задачи) Конфликтные Бесконфликтные (антагонистические) (неантагонистические) коалиционные некоалиционные Конечные Бесконечные Игры для двух лиц Игры для многих лиц Статические Динамические Дифференциальные Позиционные Рекурсивные Детерминированные Стохастические Рис. 6.2 Классификация задач теории игр Бесконечными называются игры, в которых множество стратегий хотя бы одного игрока – континиум, т.е. непрерывно. Например, инвестиции, вкладываемые в дело.

Статическая игра – это игра, в которой игроки выбирают свои стратегии только один раз, и эти стратегии сохраняются во всех играх.

В динамической игре стратегия меняется во времени, при этом используется информация о развитии игры в прошлом. Динамические игры – многодневные.

6.3 ПАРНЫЕ АНТАГОНИСТИЧЕСКИЕ ИГРЫ 6.3.1 Игры с седловой точкой Рассматривается конечная статическая антагонистическая игра двух лиц.

Пусть первое лицо имеет n чистых стратегий I = (1, 2, …, n), второе лицо имеет m чистых стратегий J = (1, 2, …, m).

Так как игра антагонистическая, то выигрыш первого игрока равен проигрышу второго игрока. Эта игра называется еще игрой с нулевой суммой. Очевидно, что для такой игры достаточно ввести матрицу выигрышей только для одного игрока.

Первого игрока (или игрока А) условно называют выигрывающим, а второго игрока (или игрока В) – проигрывающим. Естественно, что эти обозначения условные, так как отрицательный выигрыш – это проигрыш, а положительный проигрыш – это выигрыш.

Пусть матрица выигрышей первого лица имеет вид q11Kq1m Q = LLL. (6.5) qn1Kqnm Эта матрица называется платежной. Первый игрок имеет n стратегий – n строк, второй m стратегий – m столбцов.

Если первый игрок выбирает стратегию i, а второй j, то согласно матрице выигрыш первого игрока будет qij, соответственно второй игрок столько же потеряет.

j 1 2 … … m i 1 q11 q12 q1m … … 2 q21 q22 q2m … … … … … … … … n qn1 qn2 qnm … … В качестве примера рассмотрим игру двух лиц. Каждое лицо имеет две стратегии I = (1, 2), J = (1, 2), платежная матрица имеет вид 1 Q =.

2 Очевидно, игроки будут рассуждать следующим образом. Задача первого игрока получить максимально возможный гарантированный выигрыш. Допустим, что он выбирает первую стратегию. В этом случае гарантировано, что он выигрывает 1. Если же выберет вторую стратегию, то выиграет 4.

1 2 Si 1 1 5 2 2 4 Для общего случая аналогичным образом для каждой стратегии первого игрока может быть найден гарантированный выигрыш Si = min qij.

j 1 2 m Si … 1 q11 q12 q1m S… 2 q21 q22 q2m S… … … … … … … n qn1 qn2 qnm Sn … Для i-й стратегии первого игрока выигрыш не может быть меньше, чем Si, он будет больше, если второй игрок ошибется, но меньше Si он быть не может. Поэтому первому игроку естественно взять ту стратегию, где Si больше. Эта стратегия называется максиминной max max i0 = arg min qij = arg Si, (6.6) i j i величина max min qij = называется нижней ценой игры.

i j Если первый игрок будет стремиться к максиминной стратегии, то ни при каких условиях его выигрыш не будет меньше, чем : Q0(i0, j) для любого j.

Таким образом получим, что i0 = 2, = 4.

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

1 2 m … 1 q11 q12 q1m … 2 q21 q22 q2m … … … … … … n qn1 qn2 qnm … lj l1 l2 lm … Для каждого столбца находится величина l = max qij, которая определяет гарантированный проигj i рыш второго игрока. Больше он проиграть не может.

В рассматриваемом примере имеем следующее.

1 1 1 2 2 lj 2 Таким образом, при первой стратегии второго игрока, максимально, что может выиграть первый игрок, а второй проиграть – это 2. Больше проиграть последний не может. Если первый игрок ошибается, то он проигрывает меньше, больше проиграть он не может.

При второй стратегии второго игрока гарантированный проигрыш составит 5, больше он проиграть не может.

Какую же стратегию – первую или вторую выбрать второму игроку Очевидно первую, так как проигрыш будет всего лишь 2 при любой стратегии первого игрока min min j0 = arg l = arg max qij. (6.7) j j j i Эта стратегия носит название минимаксной, а величина = min max qij j i носит название верхней цены игры.

Нижняя и верхняя цены игры дают гарантированный уровень выигрыша и проигрыша для первого и второго игроков:

Q(i0, j), для ллюбог j;

Q(i, j0), для ллюбог i.

Если =, то говорят, что игра имеет седловую точку. Смысл ее понятен, если рассмотреть непрерывный случай. Значение = = называется ценой игры.

Ситуация (i0, j0) является оптимальной (i*, j*), так как она устойчива. Это ясно видно на рассмотренном примере = = 2, i0 = 2, j0 = 1 и ни одному игроку не выгодно ее менять Q(i, j*) Q(i*, j*) Q(i*, j).

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

Для полного понимания термина "седловая точка" рассмотрим непрерывную задачу. Итак, х Х, у Y, х и у непрерывны, вместо платежной матрицы имеется платежная функция для первого игрока Q (x, y). При этом как и раньше выигрыш одного игрока равен проигрышу другого. Максиминная стратегия первого игрока и минимаксная стратегия второго игрока находятся аналогичным образом дискретному случаю, т.е.

max x0 = arg minQ(x, y), max minQ(x, y) = ;

x y x y (6.8) min y0 = arg maxQ(x, y), min maxQ(x, y) =.

y x y x Если =, то имеется седловая точка. Графическая иллюстрация рассматриваемого непрерывного случая представлена на рис. 6.3.

6.3.2 Антагонистические игры без седловой точки Предположим, что верхняя и нижняя цены игры, как и в предыдущем случае, равны = min max qij, = max min qij, ( 6.9) i j j i но. В этом случае седловая точка отсутствует.

Q у у х (х*, у*) = (х0, у0) х Рис. 6.3 Графическая иллюстрация оптимального решения в антагонистической игре с седловой точкой Например, матрица платежей имеет вид 1 2 Si 1 1 3 2 4 2 lj 4 Очевидно, что = 2, i0 = 2; = 3, j0 = 2. Как и раньше Q(i0, j) 2, Q(i, j0 ) 3. Однако условие устойчивости Q(i, j0) Q(i0, j0 ) Q(i0, j) не соблюдается. Это означает, что (i0, j0 ) не является оптимальной ситуацией, так как она неустойчива. Первому игроку выгодно сменить стратегию, тогда выигрыш будет равен 3, а не 2. Соответственно второй игрок проиграет 3. Если он сам сменит стратегию на первую, то уменьшит свой проигрыш до единицы, а значит и уменьшит выигрыш первого игрока до единицы.

Это и означает неустойчивость ситуации (i0, j0 ).

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

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

Пусть смешанная стратегия первого игрока = (1, 2, …, n), где i – вероятность использования i-й чистой стратегии, смешанная стратегия второго игрока = (1, 2, …, m), где i – вероятность использования j чистой стратегии.

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

Если имеется две чистых стратегии I = (1, 2), то в этом случае смешанная стратегия будет = (1, 2), а множество всех возможных смешанных стратегий определяется прямой 1 + 2 = 1 (рис.

6.4). Очевидно, (0, 1) – чистая стратегия при i = 2, (1, 0) – чистая стратегия при i = 1.

Если имеется три чистых стратегии i = 1, 2, 3, то в пространстве 1 2 3 вероятностей имеется плоскость, определяемая уравнением 1 + 2 + 3 = 1 (рис. 6.5).

При этом чистые стратегии это при: i = 1 – (1,0,0); i = 2 – (0,1,0); i = 3 – (0,0,1).

Остальные стратегии – точки на поверхности, они определяются соответствующими значениями (1, 2, 3).

Целевая функция определяется формулой n m Q (,) = q1111 + q1212 + K + qnmnn = i, (6.10) qij j i=1 j= Рис. 6.4 Множество сме- Рис. 6.5 Множество смешанных стратегий при i = шанных стратегий при i = 1, 2 1, 2, так как вероятность одновременного совершения i-й стратегии первого игрока и j-й стратегии второго игрока будет ii. Эта функция Q (,) непрерывно зависит от и, и поэтому в смешанной стратегии исчезает платежная матрица и появляется платежная функция, которая для двух игроков равна Q (,) = q1111 + q1212 + q2121 + q2222. (6.11) Нижнее и верхнее значения игры для смешанной стратегии определяются как для непрерывной игры = max min Q (, ), E (6.12) = min max Q (, ).

E При этом максиминная стратегия 0 определяется как max 0 = arg min Q (, ), (6.13) E а минимаксная стратегия 0 как:

min 0 = arg max Q (, ). (6.14) E В теории игр доказывается, что в смешанных стратегиях всегда существует =, т.е. седловая точка.

Значение = = называется ценой игры со смешанными стратегиями. Значения 0, 0, соответствующие седловой точке, образуют устойчивую, а значит оптимальную ситуацию (0, 0) = ( *, *).

6.3.3 Алгоритмы решения задач без седловых точек Пусть *, * – оптимальные стратегии. Номера чистых стратегий * и *, вероятности которых не равны нулю, называются спектрами S, S соответственно S = {i = 1, 2, K, n / i 0}, S = {j = 1, 2, K, n / 0}.

j Иногда их называют реальными чистыми стратегиями.

Можно доказать, что 1) если S содержит K чистых стратегий, то S также содержит K чистых стратегий;

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

6.3.3.1 Игра 2 1 q11 qq21 qЧистые стратегии I = (1, 2), J = (1, 2).

В спектр входят обе стратегии. Если бы в спектр одного игрока входила бы одна стратегия S = (1), то и в спектр другого игрока также бы вошла одна стратегия S = (2), а это значит, что была бы седловая точка.

Допустим, что первый игрок придерживается максиминной стратегии * = (1*, 2*), а второй выбрал чистую стратегию j = 1. Тогда эти стратегии входят в спектр чисел * q111 + q21* =.

Для чистой стратегии j = 2 аналогичным образом можно записать * q121 + q22* =.

* Кроме того, 1 + * = 1.

Таким образом, имеем три уравнения и три неизвестных. Следовательно, решение однозначно.

Пусть теперь второй игрок придерживается минимаксной стратегии (1*, 2*), а первый чистой. Тогда аналогичным образом, как и предыдущем случае, имеем:

* q111 + q12* =, * q211 + q22* =, * 1 + * = 1.

Решение этих уравнений дает следующие расчетные формулы:

q11q22 - q12q =, q11 + q22 - (q12 + q21) q22 - q* 1 =, q11 + q22 - (q12 + q21) * * = 1 - 1, q22 - q* 1 =, q11 + q22 - (q12 + q21) * * = 1 - 1.

Pages:     | 1 |   ...   | 8 | 9 || 11 |






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.