Стохастические игры

Министерство образования и науки Российской Федерации

Государственное образовательное учреждение

высшего профессионального образования

«Оренбургский Государственный Университет»

Факультет экономики и управления

Кафедра математических методов и моделей в экономике

Отчет

по расчетно-графическому заданию

по дисциплине “Теория игр”

на тему

«Стохастические игры»

Ушатова С.Т.

Оренбург 2012

Содержание

• Введение
• 1. Стохастические игры
• 2. Задача « Герб - Решетка»
• 3. Блок-схема программы
• 4. Тестовый пример
• Приложение А
• Введение
• В последние три десятилетия наблюдается стремительное повышение интереса к теории игр, которая, с одной стороны, наряду с математическими моделями общего равновесия и теорией социального выбора, сыграла ключевую роль в создании современной экономической теории, а с другой, является одним из важнейших инструментов анализа огромного многообразия задач, возникающих не только в экономике, но и в политике, социальных науках, военном деле, биологии и др.
• Развитие теории игр, изучение ее методов и их применение в практике народно-хозяйственной деятельности оказывает помощь в совершенствовании системы подготовки и принятия решений, способствует научно-техническому прогрессу.
• Игра характеризуется системой правил, определяющих количество участников игры, их возможные действия и распределение выигрышей в зависимости от их поведения и исходов. Цель теории игр - это выработка рекомендаций по рациональному образу действий каждого из противников в ходе конфликтной ситуации. По количеству ходов игры делятся на одношаговые и многошаговые. К многошаговым относятся такие игры, в которых хотя бы один из игроков делает больше одного хода. Основное преимущество - может быть бесконечно много шагов (ходов). Один из видов многошаговых игр в данной расчетно-графической работе мы рассмотрим.
• Целью данной работы является разработка программного средства для решения стохастических игр.
• Объект исследования - стохастическая игра «Герб - Решетка»
• Предмет изучения - теоретические аспекты и расчетные метод решения стохастических игр.
• Для достижения поставленной цели необходимо решить следующие задачи:
• - изучить теорию по стохастическим играм;
• - решить игру «Герб - Решетка» расчетным путем;
• - разработать и протестировать программное средство для решения стохастических игр на примере игры «Герб - Решетка»
• стохастический игра программный
• 1. Стохастические игры
• Разновидностью многошаговых игр являются стохастические игры, в которых имеется несколько игровых позиций, и переход от одной позиции к другой совершается с определенной вероятностью. В правилах игры предусматриваются выигрыши на каждом шаге игры. Таким образом, в стохастической игре возможны возвращения к предшествующей позиции и теоретически возможно бесконечное продолжение игры и бесконечно большой выигрыш. Однако, чтобы исключить такую возможность, в правилах игры предусматривается задание таких переходных вероятностей, что бесконечное продолжение игры может быть с вероятностью нуль, а математическое ожидание выигрыша конечно.
• Игра разыгрывается в течение ряда этапов. В начале каждого этапа игра находится в некотором состоянии. Игроки выбирают свои действия и получают выигрыши, зависящие от текущего состояния и действий. После этого система переходит случайным образом в другое состояние, распределение вероятности переходов зависит от предшествующего состояния и действий игроков.
• Эта процедура повторяется в течение конечного или бесконечного числа шагов. Общий выигрыш игроков часто определяется как дисконтированная сумма выигрышей на каждом этапе или нижний предел средних выигрышей за конечное число шагов.
• При конечном числе игроков, конечных множествах действий и состояний игра с конечным числом повторений всегда имеет равновесие Нэша.
• Это справедливо также для игр с бесконечным числом повторений, если выигрыши участников представляют собой дисконтированную сумму. Участник не может увеличить выигрыш, изменив своё решение в одностороннем порядке, когда другие участники не меняют решения. Такая совокупность стратегий выбранных участниками и их выигрыши называются равновесием Нэша в игре Курно.
• Стохастическая игра задается набором игровых элементов или позиций каждый игровой элемент представляется матрицей порядка , где - число стратегий первого игрока, - число стратегий второго игрока.
• Элементы матрицы задаются в следующем виде:
• (1)
• где - номер стратегии первого игрока ();- номер стратегии второго игрока (; - выигрыш первого игрока на -м шаге, если первый игрок применит стратегию , а второй ; - вероятность перехода на позицию с позиции , если на -й позиции первый игрок применил свою стратегию , а второй , причем с вероятностью
• (2)
• осуществляется переход на игровой элемент, а с вероятностью
• (3)
• игра заканчивается.
• Условие (2) или (3) показывает, что вероятность бесконечного продолжения игры равна 0, а математическое ожидание выигрыша конечно.
• Смешанной стратегией первого игрока называется полный набор вероятностей применения его чистых стратегий на -м шаге игры в игровом элементе .
• Очевидно, удовлетворяет соотношениям
• . (4)
• Смешанной стратегией второго игрока называется полный набор вероятностей применения его чистых стратегий на -м шаге игры в игровом элементе .
• Очевидно, для должны удовлетворяться следующие соотношения:
• . (5)
• Смешанная стратегия называется стационарной, если вероятности применения его чистых стратегий не зависят от шага игры . Стационарные смешанные стратегии записываются так:
• ,.
• Поскольку средний выигрыш игрока зависит от того, с какой позиции начинается игра, то и цена игры зависит от этого.
• Обозначим через цену игры, если первым шагом игры был игровой элемент . Таким образом определяется вектор цены игры . Каждому значению соответствуют оптимальные смешанные стратегии игроков.
• Если вектор существует, то можно заменить игровой элемент на , т.е. получается, что
• где означает цену игры с матрицей , а элементами будут
• . (6)
• Теперь возникают следующие вопросы:
• Существует ли вектор ?
• Единственный ли вектор ?
• Как найти вектор и оптимальные стратегии?
• На эти вопросы дает ответ следующая лемма и теорема.
• Лемма 1. Пусть матрицы и порядка , удовлетворяющие условию
• ,
• где - действительное число, тогда .
• Доказательство. Пусть ,- оптимальная стратегия второго игрока в игре с матрицей . Тогда для всех
• ,
• так что дает верхнюю границу проигрыша в игре с матрицей , которая меньше .
• Теорема 1. Существует в точности один вектор цен игры , удовлетворяющий соотношениям
• , (7)
• где определена по формуле (6).
• Доказательство. Покажем сначала единственность. Предположим, что существуют два вектора и , удовлетворяющих соотношениям (7). Пусть - номер компоненты, для которой
• ,
• и пусть для определенности . Определим две матрицы и следующими соотношениями:
• ,.
• Очевидно,
• .
• Из леммы 1 следует, что
• .
• Поскольку и удовлетворяют (6) и (7), то
• ,
• что противоречит предпосылке и доказывает единственность.
• Докажем существование. Доказательство конструктивное, основанное на построении последовательности векторов, сходящейся к требуемому вектору. Пусть - номер члена последовательности. Определим члены последовательности следующими соотношениями:
• , (8)
• , (9)
• . (10)
• Требуется доказать: 1) последовательность векторов сходится; предел этой последовательности удовлетворяет условиям (6), (7). Положим
• . (11)
• Поскольку выполняется (2) и множества индексов конечные, то существует и .
• Если положить
• ,
• то по лемме 1 следует, что и, следовательно, . Поэтому согласно признаку сходимости Коши последовательность должна сходиться к пределу, который обозначим через .
• Пусть теперь
• ,
• где
• .
• Покажем, что для всех . Действительно, на основании сходимости последовательностей для любого можно выбрать столь большим, что для всех выполнялись неравенства:
• , (12)
• . (13)
• Из (12) и леммы 1 следует, что для всех
• ,
• а это вместе с (13) означает, что для всех
• .
• Поскольку произвольно, то , что и требовалось доказать.
• Используя конструктивный способ доказательства теоремы 1, можно построить аппроксимацию цен игровых элементов следующим образом: предположим, что игра будет продолжаться как стохастическая, пока не будет разыграна раз, а затем её необходимо заканчивать (если она не закончилась естественно раньше), тогда получим усеченную игру на разорение, а не стохастическую игру. Решив её известными методами, получим вектор цен и оптимальные стратегии в матричных играх с матрицами . Число , определенное формулой (11), обладает тем свойством, что вероятность продолжения игры более шагов, какие бы стратегии не использовались, не превосходит (здесь в степени ). Поэтому, если достаточно велико, то мало, и мы можем аппроксимировать стохастическую игру игрой, усеченной после шагов. Оптимальные стратегии и усеченных игр сходятся к оптимальным стационарным стратегиям стохастической игры.
• 2. Задача « Герб - Решетка»
• Игроки 1 и 2 имеют вместе пять единиц. На каждом шаге игры игрок 1 выбирает либо «герб», либо «решетку»; игрок 2, не зная выбора игрока 1, делает аналогичный выбор. Если выборы совпадают, игрок 2 платит игроку 1 либо три, либо одну единицу в зависимости от того, что было выбрано, «герб» или «решетка». Если выборы не совпадают, игрок 1 платит игроку 2 две единицы. После каждого шага бросается монета для того чтобы определить, продолжать игру или закончить ее; кроме того, игра заканчивается, как только один из игроков разорится. Мы накладываем еще дополнительное условие, состоящее в том, что ни один игрок не может платить больше, чем он имеет.
• Рассмотренная игра может быть представлена четырьмя игровыми элементами , где - величина капитала, которую имеет первый игрок в начале данного шага:
• ,,
• ,.
• Действительно. Рассмотрим, например, первое выражение . У первого игрока есть одна единица: если он выиграет 3 единицы, то он может разыграть 4 единицы с вероятностью 0,5 (этому соответствует элемент матрицы игрового элемента ; если он проиграет свою единицу, то он разорится, и игра заканчивается (это соответствует элементам и матрицы игрового элемента ); если он выигрывает одну единицу, то у него станет 2 единицы капитала, он может продолжать игру с вероятностью 0,5 (это соответствует элементу игрового элемента ). Аналогично объясняются и остальные игровые элементы ,,.
• Используя для этой игры формулы (8), (9), (10) и в качестве начального приближения , получим 1-е приближения для ,,,, обозначенные соответственно ,,,, заменяя которые в матрицах ,,, значениями цены игры , получим:
• ,,
• ,.
• Решая эти игры, найдем вектор . Например, для цены игры с игровым элементом получим уравнения:
• где - вероятность применения первым игроком в игровом элементе своей первой чистой стратегии. Исключим из последних уравнений, тогда .
• Аналогично составляем уравнения для игрового элемента и получаем:
• где - вероятность применения первым игроком в игровом элементе своей первой чистой стратегии. Исключим из последних уравнений, получим . Аналогично находим ; . Таким образом, нашли вектор .
• Подставляя теперь в матрицы для ,,, соответственно значения вместо ,,,, получим матрицы игр для второй итерации:
• ,,
• ,.
• Решая игры с матрицами, соответствующими этим игровым элементам получим вектор цены игры для второй итерации:
• .
• Проведение аналогично третьей и четвертой итерации дает:
• .
• Итак, соответственные компоненты векторов , отличаются друг от друга вторым десятичным знаком, следовательно, можно считать, что вектор цены игры получен с точностью до двух десятичных знаков. Если такая точность нас удовлетворяет, то вычисляем оптимальные смешанные стратегии, соответствующие этой четвертой итерации, решая игры с матрицами, которые получены из ,,, путем подстановки в правые части этих игровых элементов вместо ,,, соответственно значения ,,,, т.е.
• ,,
• ,.
• Решая отдельно игры с этими матрицами, соответственно получим
• Эти векторы дают оптимальные стационарные смешанные стратегии игроков в стохастической игре, т.е. находясь в игровом элементе (имея капитал одну единицу), игроки должны применить свои стратегии согласно векторам и , и средний выигрыш составит ; находясь в игровом элементе (имея капитал 2 единицы), игроки должны применить свои стратегии согласно векторам и , и средний выигрыш составит ; находясь в игровом элементе (имея капитал 3 единицы), игроки должны применять свои стратегии согласно векторам и , и средний выигрыш составит ; находясь в игровом элементе (имея капитал 4 единицы), игроки должны применять свои стратегии согласно векторам и , и средний выигрыш составит , т.е. на каждом шаге (игровом элементе) будет выигрыш соответствовать вектору цены игры .
• 3. Блок-схема программы
• 4. Тестовый пример
• Рисунок 1 - Иллюстрация работы программы
• Приложение А
• Текст программы
• unit Unit1;
• interface
• uses
• Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
• Dialogs, StdCtrls, Grids;
• type
• TForm1 = class(TForm)
• StringGrid1: TStringGrid;
• Label1: TLabel;
• StringGrid2: TStringGrid;
• Label3: TLabel;
• Button1: TButton;
• Label4: TLabel;
• Edit1: TEdit;
• StringGrid3: TStringGrid;
• StringGrid4: TStringGrid;
• Label2: TLabel;
• StringGrid5: TStringGrid;
• Edit2: TEdit;
• Label5: TLabel;
• procedure Button1Click(Sender: TObject);
• private
• { Private declarations }
• public
• { Public declarations }
• end;
• Procedure formirovanie (kol,c:integer);{v:array of real}
• var
• Form1: TForm1;
• matis:array [1..2,1..2] of integer;
• i,j,kol,k,c,z,l,o:integer;
• ver:array [1..2] of real;
• v:array [1..8] of real;
• g:array [1..4,1..2,1..2] of real;
• implementation
• {$R *.dfm}
• Procedure formirovanie (kol,c:integer);
• begin
• For i:=1 to kol do begin
• For j:=1 to 2 do begin
• For k:=1 to 2 do begin
• z:=matis[j,k];
• if (z>0) then begin if (c-z-i)>0 then begin
• l:=z+i;
• g[i,j,k]:=matis[j,k]+ver[1]*v[l];end else
• g[i,j,k]:=c-i;end;
• if (z<0) then begin if abs(z)>=abs(i) then begin
• g[i,j,k]:=-i;end else begin
• o:=abs(i+z);
• g[i,j,k]:=matis[j,k]+ver[1]*v[o];
• end;
• end;
• end;
• end;
• end;
• end;
• procedure TForm1.Button1Click(Sender: TObject);
• begin
• stringgrid2.Cells[0,0]:='A/B';
• stringgrid2.Cells[0,1]:='A1';
• stringgrid2.Cells[0,2]:='A2';
• stringgrid2.Cells[1,0]:='B1';
• stringgrid2.Cells[2,0]:='B2';
• ver[1]:=strtofloat(stringgrid1.Cells[0,0]);
• ver[2]:=1-ver[1];
• kol:=strtoint(edit1.Text);
• c:=strtoint(edit2.text);
• stringgrid3.RowCount:=kol;
• stringgrid4.RowCount:=kol;
• stringgrid5.RowCount:=kol;
• For i:=1 to kol do begin
• stringgrid3.Cells[0,i-1]:='x'+inttostr(i);
• stringgrid4.Cells[0,i-1]:='y'+inttostr(i);
• stringgrid5.Cells[0,i-1]:='v'+inttostr(i);
• end;
• For i:=1 to kol do begin
• v[i]:=0;
• end;
• For i:=1 to 2 do begin
• For j:=1 to 2 do
• matis[i,j]:=strtoint(stringgrid2.Cells[i,j]);
• end;
• For i:=1 to kol do begin
• formirovanie(kol,c,{v});
• For j:=1 to kol do begin
• v[j]:=(g[j,1,1]*g[j,2,2]-g[j,2,1]*g[j,1,2])/(g[j,1,1]+g[j,2,2]-g[j,2,1]-g[j,1,2]);
• end;
• end;
• formirovanie(kol,c,{v});
• i:=1; j:=0;
• While (j<=3) and (i<=4) do begin
• stringgrid3.Cells[1,j]:=floattostr((g[i,2,2]-g[i,1,2])/(g[i,1,1]+g[i,2,2]-g[i,2,1]-g[i,1,2]));
• stringgrid3.Cells[2,j]:=floattostr((g[i,1,1]-g[i,2,1])/(g[i,2,2]+g[i,1,1]-g[i,2,1]-g[i,1,2]));
• stringgrid4.Cells[1,j]:=floattostr((g[i,2,2]-g[i,2,1])/(g[i,1,1]+g[i,2,2]-g[i,2,1]-g[i,1,2]));
• stringgrid4.Cells[2,j]:=floattostr((g[i,1,1]-g[i,1,2])/(g[i,2,2]+g[i,1,1]-g[i,2,1]-g[i,1,2]));
• inc(i);
• inc(j);
• end;
• For i:=1 to kol do
• stringgrid5.Cells[1,i-1]:=floattostr(v[i]);
• end;
• end.