Стохастические игры
Стохастические игры как разновидность многошаговых игр, в которых переход от одной позиции к другой совершается с определенной вероятностью. Расчетные методы их решения. Разработка и тестирование программного средства для решения игры "Герб-Решетка".
Рубрика | Экономико-математическое моделирование |
Вид | контрольная работа |
Язык | русский |
Дата добавления | 20.02.2013 |
Размер файла | 364,0 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Министерство образования и науки Российской Федерации
Государственное образовательное учреждение
высшего профессионального образования
«Оренбургский Государственный Университет»
Факультет экономики и управления
Кафедра математических методов и моделей в экономике
Отчет
по расчетно-графическому заданию
по дисциплине “Теория игр”
на тему
«Стохастические игры»
Ушатова С.Т.
Оренбург 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 - Иллюстрация работы программы
- Приложение А
- Размещено на http://www.allbest.ru/
- Размещено на http://www.allbest.ru/
- Текст программы
- 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.
- Размещено на Allbest.ru
Подобные документы
Элементы теории матричных игр. Способы решения матричных игр. Различия в подходах критериев оптимальности при определении оптимальной стратегии в условиях статистической неопределенности. Нахождение седловой точки игры. Графическое решение матричной игры.
контрольная работа [366,9 K], добавлен 12.05.2014Конфликтные ситуации в управленческой деятельности. Использование математического моделирования для решения управленческих задач. Определение биматричной игры и общий принцип ее решения. Состояние равновесия в смешанных стратегиях в биматричных матрицах.
реферат [26,9 K], добавлен 21.12.2010Понятие о классических и неоклассических антагонистических играх, их классификация. Характерные черты математической модели игровой ситуации. Матричные игры двух лиц. Принцип применения пессимистического критерия минимакса-максимина для их решения.
реферат [57,6 K], добавлен 17.07.2014Формальная постановка задачи, методы решения. Модульная организация приложения. Общая схема взаимодействия модулей, описание модулей. Текст программы, руководство пользователя. Тестовый пример игры, приложение Delphi, надежность программного обеспечения.
курсовая работа [14,4 K], добавлен 19.10.2010Предмет и задачи теории игр. Сведение матричной игры к задачам линейного программирования. Основные принципы разработки деловых игр для исследования экономических механизмов. Деловая игра "Снабжение". Решение матричной игры в смешанных стратегиях.
курсовая работа [1,8 M], добавлен 15.10.2012Рассмотрение содержания и методов решения матричной игры в смешанных стратегиях, способы ее сведения к задачам линейного программирования. Анализ геометрической интерпретации биматричных и бескоалиционных игр. Природа и структура кооперативных игр.
курс лекций [1,2 M], добавлен 11.07.2010Определение чистых стратегий холдинга. Составление платежной матрицы игры, ее верхней и нижней цены. Принятие оптимального решения об инвестиции в банк для получения наибольшей выгоды при улучшении финансового состояния металлургическому консорциуму.
курсовая работа [85,3 K], добавлен 19.05.2014Экспертные методы в исследовании систем управления; понятие, сущность, проблемы, для решения которых они применяются. Особенности интерактивного метода последовательных сравнений, его программная реализация; интерфейс, листинг программного продукта.
курсовая работа [700,4 K], добавлен 11.06.2011Основные положения теории расписаний, постановка задачи минимизации средневзвешенного суммарного штрафа и методы ее решения. Разработка алгоритма решения данной задачи методами полного перебора и оптимальной вставки, составление программы на Delphi.
курсовая работа [468,7 K], добавлен 10.04.2011Применение линейного программирования для решения транспортной задачи. Свойство системы ограничений, опорное решение задачи. Методы построения начального опорного решения. Распределительный метод, алгоритм решения транспортной задачи методом потенциалов.
реферат [4,1 M], добавлен 09.03.2011