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

Стохастические игры как разновидность многошаговых игр, в которых переход от одной позиции к другой совершается с определенной вероятностью. Расчетные методы их решения. Разработка и тестирование программного средства для решения игры "Герб-Решетка".

Рубрика Экономико-математическое моделирование
Вид контрольная работа
Язык русский
Дата добавления 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

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.