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

 

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

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

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

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

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

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









Отчет

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

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

на тему

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




Ушатова С.Т.






Оренбург 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 - Иллюстрация работы программы


Приложение А



Текст программыUnit1;, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,, StdCtrls, Grids;= class(TForm): TStringGrid;: TLabel;: TStringGrid;: TLabel;: TButton;: TLabel;: TEdit;: TStringGrid;: TStringGrid;: TLabel;: TStringGrid;: TEdit;: TLabel;Button1Click(Sender: TObject);

{ Private declarations }

{ Public declarations };formirovanie (kol,c:integer);{v:array of real}: TForm1;:array [1..2,1..2] of integer;

i,j,kol,k,c,z,l,o:integer;

ver:array [1..2] of real;:array [1..8] of real;:array [1..4,1..2,1..2] of real;

{$R *.dfm}formirovanie (kol,c:integer);i:=1 to kol do beginj:=1 to 2 do begink:=1 to 2 do begin:=matis[j,k];(z>0) then begin if (c-z-i)>0 then begin:=z+i;[i,j,k]:=matis[j,k]+ver[1]*v[l];end else[i,j,k]:=c-i;end;(z<0) then begin if abs(z)>=abs(i) then begin[i,j,k]:=-i;end else begin

o:=abs(i+z);[i,j,k]:=matis[j,k]+ver[1]*v[o];

end;;;;;;TForm1.Button1Click(Sender: TObject);.Cells[0,0]:='A/B';.Cells[0,1]:='A1';.Cells[0,2]:='A2';.Cells[1,0]:='B1';.Cells[2,0]:='B2';[1]:=strtofloat(stringgrid1.Cells[0,0]);[2]:=1-ver[1];:=strtoint(edit1.Text);:=strtoint(edit2.text);.RowCount:=kol;.RowCount:=kol;.RowCount:=kol;i:=1 to kol do begin.Cells[0,i-1]:='x'+inttostr(i);.Cells[0,i-1]:='y'+inttostr(i);.Cells[0,i-1]:='v'+inttostr(i);;i:=1 to kol do begin[i]:=0;;i:=1 to 2 do beginj:=1 to 2 do[i,j]:=strtoint(stringgrid2.Cells[i,j]);;i:=1 to kol do begin(kol,c,{v});j:=1 to kol do begin[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]);;;(kol,c,{v});:=1; j:=0;(j<=3) and (i<=4) do begin.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]));.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]));.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]));.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]));(i);(j);;i:=1 to kol do.Cells[1,i-1]:=floattostr(v[i]);

end;.


Министерство образования и науки Российской Федерации Государственное образовательное учреждение высшего профессионального образования «Оренбургск

Больше работ по теме:

КОНТАКТНЫЙ EMAIL: [email protected]

Скачать реферат © 2019 | Пользовательское соглашение

Скачать      Реферат

ПРОФЕССИОНАЛЬНАЯ ПОМОЩЬ СТУДЕНТАМ