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

ОСНОВНЫЕ ПОНЯТИЯ СТАТИСТИЧЕСКИХ ИГР

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

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

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

Следовательно, основными отличиями статистических игр от стратегических являются:

а) отсутствие стремления к выигрышу у игрока-природы, то есть отсутствие антагонистического противника;

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

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

1) На проведение эксперимента требуется время, которого может и не быть, особенно когда решение надо принимать немедленно.

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

Поэтому важной задачей статистика является и само принятие решения о проведении эксперимента - о необходимости и возможности проведения эксперимента, и об объеме исследований.

Таким образом:

1) Игры, в которых один из игроков - природа, называются статистическими.

2) Теория таких игр называется теорией статистических решений.

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

Пространство стратегий природы

Под стратегией природы будем понимать полную совокупность внешних условий, в которых приходится принимать решения статистику. Эту совокупность внешних условий называют – множеством состояний природы , которое состоит из отдельных состояний природы , называемых чистыми стратегиями природы.

Если бы заранее было известно, какую из своих чистых стратегий применит природа в каждом конкретном случае, то статистик принимал бы решение на основании полного знания состояний природы, то есть имел бы игру в условиях полной определенности. Однако обычно известен только полный перечень чистых стратегий . Кроме того, из прошлого опыта или по результатам проведения экспериментов, игрок может определить априорное распределение вероятностей состояния природы. Это распределение определяется или функцией распределения вероятностей , или плотностью распределения вероятностей , или в виде перечня состояний и соответствующих им вероятностей (как дискретная случайная величина):

Здесь и .

Такое априорное распределение вероятностей состояний природы называется смешанной стратегией природы.

Примеры статистических игр

№ 3.1.(Задача о замене оборудования). Установленное на предприятии сложное и дорогое оборудование после нескольких лет работы может оказаться в одном из трех состояний: - оборудование вполне работоспособно и требует лишь небольшого текущего ремонта; - оборудование работоспособно, но некоторые детали значительно износились и требуют серьезного ремонта или даже замены; - дальнейшая эксплуатация оборудования невозможна.

Прошлый опыт эксплуатации аналогичного оборудования показывает, что в 20% случаях оно может находиться в состоянии , в 50% случаях - в состоянии , и в 30% - в состоянии .

Для предприятия возможны три различных варианта действия: - оставить оборудование в работе еще на один год, проведя незначительный ремонт своими силами; - провести капитальный ремонт оборудования с вызовом специальной бригады ремонтников; - заменить оборудование новым.

Требуется найти байесовское оптимальное решение действий предприятия при следующей матрице потерь:

.

Решение. Вычислим средние потери предприятия:

,

,

.

Тогда байесовское решение дает нам стратегия , так как

.

Ответ: .

№ 3.2.(Задача о технологической линии). На технологическую линию может поступить сырье с малым и с большим количеством примесей. Известно, что в среднем поступает 60% сырья первого вида и 40% сырья второго вида. Для использования различных видов сырья предусмотрены три режима работы технологической линии: , и . Потери, отражающие качество выпускаемой продукции и расходы сырья, в зависимости от качества сырья и режима работы технологической линии, имеют вид:

.

Требуется найти байесовское оптимальное решение.

Решение. Вычислим средние потери:

,

,

.

Тогда оптимальной является чистая стратегия , так как

.

Ответ: .

Принцип минимакса

Согласно этого принципа, статистик выбирает ту стратегию , при которой его средние потери будут наименьшими при наихудшем для него состоянии природы, то есть

(3.7)

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

№ 3.4.Найти минимаксную стратегию в задаче о технологической линии.

Решение. Построим графики функций потерь и для отрезков и .

5 3

3 2

1 1

0 1 0 1

Рис. 3.3 . Рис. 3.4 .

Значения выделим на рисунке жирными линиями. Тогда минимум этой величины достигается на рис.3.3 при , и равен 3, а на рис.4 определяется точкой пересечения прямых как:

,

то есть достигается при , и равен .

Таким образом, принцип минимакса дает точку на отрезке , соответствующую , и определяет смешанную стратегию

,

при которой потери статистика будут не больше ед. при любой стратегии природы.

Иногда выбирают стратегию исходя из так называемых дополнительных потерь:

. (3.8)

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

№ 3.5.Найти минимаксную стратегию в задаче о технологической линии, исходя из дополнительных потерь.

Решение. Так как при , а при , то матрица дополнительных потерь примет вид:

.

Применим принцип минимакса графически. Для этого построим сначала выпуклую оболочку :

0 1 3

Рис. 3.5

Спроектируем отрезок на оси координат и получим следующие выражения для функции дополнительных потерь:

,

.

Для отрезка получаем аналогично:

,

.

Построим графики дополнительных потерь:

3 3

1 1

0 1 0 1

Рис.3.6 . Рис. 3.7 .

Тогда на рис. 3.6 минимум от максимума дополнительных потерь достигается при , равен 1, и получаем чистую стратегию . Для рис.3.7 получаем , и стратегию .

Следовательно, оптимальной является чистая стратегия , и минимаксные дополнительные потери равны 1 ед.

Минимаксные принципы исходят из предположения о том, что природа действует наихудшим для статистика образом, и поэтому выражают точку зрения ЛПР, не расположенного к риску. Недостатком этих методов является и то, что они не учитывают априорной информации о состояниях природы, что ограничивает возможный выигрыш статистика. Поэтому минимаксные принципы можно рекомендовать в случае отсутствия априорной информации о состояниях природы, или если есть веские основания сомневаться в достоверности такой информации.

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

Байесовский принцип

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

. (3.9)

Наилучшей стратегией при этом будет та, которая минимизирует величину (9), а именно:

. (3.10)

Эту стратегию и называют байесовской.

№ 3.6.Найти байесовскую стратегию в задаче о технологической линии, представленной в виде - игры.

Решение. Для допустимых стратегий, определяемых отрезком , имеем:

.

Тогда при , что соответствует смешанной стратегии .

Для отрезка получаем:

.

Тогда при , что соответствует той же смешанной стратегии .

Следовательно, байесовской стратегией является чистая стратегия с оптимальным значением потерь 1,8 ед.

Ответ: ; .

Постановка задачи

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

Прежде всего, статистик должен принять решение о том, проводить или не проводить эксперимент. В случае положительного ответа на этот вопрос, он должен далее решить:

а) каким должен быть этот эксперимент;

б) сколько следует провести испытаний, чтобы считать эксперимент законченным;

в) какие предпринять действия при тех или иных исходах эксперимента.

Предположим, что статистик принял решение о проведении единичного эксперимента, под которым будем понимать такой эксперимент, объем и порядок проведения которого заранее определены.

Так, если надо проверить, является ли данная монета симметричной, можно провести единичный эксперимент, состоящий в бросании монеты раз. При этом пространство исходов этого эксперимента состоит из элементов вида:

.

Например, для определения вероятности выпадения герба при одном бросании монеты, Пирсон провел эксперимент, состоящий из 24000 бросаний монеты. То есть пространство возможных исходов эксперимента состояло из элементов.

Пространство выборок

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

, , , (3.11)

где - условная вероятность того, что исходом эксперимента будет при данном состоянии природы .

Совокупность трех элементов: пространства исходов эксперимента , пространства состояний природы и распределения вероятностей называют пространством выборок:

. (3.12)

Пространство выборок удобно задавать в виде таблицы, содержащей распределение вероятностей на прямом произведении множеств .

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

Результаты эксперимента ( - примесей не обнаружено, - примеси в небольшом количестве, - примесей много) представим в следующей таблице:

	0,60	0,20
	0,25	0,30
	0,15	0,50

Например, 0,25 - это вероятность того, что при действительном состоянии природы (сырье с малым количеством примесей), эксперимент обнаружит их в небольшом количестве.

Решающая функция

Если в задаче без эксперимента статистик должен принять решение из пространства решений , исходя из априорной информации о состояниях природы, то в задаче с экспериментом, он принимает решение в зависимости от исхода эксперимента .

Чтобы формализовать эту задачу нужно заранее проанализировать все возможные исходы эксперимента, и составить правило , определяющее, какое решение следует принять при каждом из возможных исходов эксперимента . Это правило представляет собой отображение пространства исходов эксперимента на пространство решений :

, (3.13)

или

.

Правило , определяющее решение , которое должен принять статистик при каждом возможном исходе эксперимента , называется решающей функцией, а полный перечень возможных решающих функций называется пространством решающих функций .

№ 3.8.Рассмотрим решающие функции в условиях № 3.7. Это

,

где , и - решения, которые принимает статистик при исходах эксперимента , и соответственно. Например, означает, что при исходе эксперимента принимается решение , при исходе - решение , при исходе - решение .

Видно, что число чистых стратегий статистика значительно увеличилось. В № 8 это число равно , а в общем случае , где - количество возможных решений статистика , а - количество возможных исходов эксперимента .

Понятие решающей функции позволяет более четко сформулировать задачу статистика. Эта задача состоит в том, чтобы из пространства решающих функций , выбрать такую решающую функцию , которая позволит принимать наиболее выгодные решения. Для этого необходимо уметь оценивать различные решающие функции, что можно сделать при помощи, так называемых, функций риска.

Функции риска

Если статистик остановил свой выбор на некоторой решающей функции , то он, тем самым, определил для каждого исхода эксперимента , , соответствующее решение , которому при данном состоянии природы будут соответствовать потери:

. (3.14)

Но при заданном , исход эксперимента будет случайной величиной с вероятностями:

,

на пространстве . Поэтому и потери будут случайными величинами с вероятностями .

Следовательно, необходимо вести речь о средних потерях, определенных на всем пространстве возможных исходов эксперимента . Эти средние потери называются функцией риска:

. (3.15)

Функция риска определяется для каждого состояния природы и для каждой решающей функции . То есть определяется на прямом произведении множеств точно так же, как функция потерь , в игре без эксперимента, определялась на прямом произведении множеств . Следовательно, пространство решающих функций и функция риска , в игре с единичным экспериментом, играют ту же роль, что и пространство возможных стратегий статистика и функция потерь в игре без эксперимента. Это означает, что игру с единичным экспериментом можно решить теми же самыми методами, что и игру без эксперимента. Плохо только то, что количество чистых стратегий статистика неимоверно возрастает.

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

Тогда функция риска, при применении смешанных стратегий, будет вычисляться как математическое ожидание (среднее):

, (3.16)

или с учетом (3.15):

. (3.17)

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

№ 3.9.Вычислить функции риска в задаче о технологической линии.

Решение. Для удобства расчетов потери статистика и вероятности сведем в одну таблицу:

				0,60	0,25	0,15
				0,20	0,30	0,50

Вычислим, например, . Согласно формуле (3.15), получаем:

.

Тогда

,

.

И так далее, можно вычислить все значения функции риска.

Пример задачи принятия решений в сельском хозяйстве

Рассмотрим задачу о том, на каких участках сажать картофель: на влажных , или на засушливых . Множество состояний природы состоит из двух элементов: - влажное лето (осадков будет выше нормы), - сухое лето (осадков будет ниже нормы). По результатам многолетних наблюдений известна соответствующая прибыль в расчете на 1 га (в у.е.):

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

Определим функцию потерь в виде разности между наибольшей прибылью (25) и прибылью которую можно получить во всех остальных случаях:

20 0

5 17

Определим множество исходов эксперимента как: - наблюдается (весной) большое количество осадков, - малое количество осадков, со следующими условными вероятностями :

	0,60	0,30
	0,40	0,70

Построим пространство решающих функций :

и вычислим функции риска, представив для удобства расчетов потери и условные вероятности в одной таблице:

			0,60	0,40
			0,30	0,70

Тогда можем получить следующие функции риска:

,

,

,

,

,

,

,

.

Представим полученные значения в виде матрицы (таблицы) рисков:

		13,4	8,6

Видно, что стратегия является недопустимой, так как при сравнении ее со стратегией , получаем следующие неравенства: . Поэтому стратегию можно исключить. Это приводит к следующей матрице рисков:

		8,6

Найдем сначала байесовское решение, предполагая, что априорное распределение вероятностей состояний природы имеет вид: .

Тогда средние потери (риски) будут равны:

,

,

,

Видно, что

.

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

Найдем теперь минимаксное решение . Согласно принципу минимакса необходимо выполнение следующих условий:

где - цена игры. Разделив на все неравенства, получаем задачу линейного программирования.

Найти

,

при ограничениях:

Решив эту задачу, получаем:

,

то есть

,

и

.

Таким образом, минимаксная стратегия заключается в выборе стратегии с вероятностью 0,0385, и стратегии с вероятностью 0,9615. Это означает, что если весной наблюдается большое число осадков , то с вероятностью 0,0385 прини<