Цена игры это число вектор матрица

Цена игры это число вектор матрица

Теория игр

Возможно Вас заинтересуют следующие разделы:

Список вопросов теста

В биматричной игре размерности 3×3 ситуаций равновесия бывает.

Биматричная игра может быть определена .

двумя произвольными матрицами

двумя матрицами только с положительными элементами

двумя матрицами только с отрицательными элементами

В графическом методе решения игр 2хn непосредственно из графика находят.

цену игры и оптимальную стратегию 2-го игрок*

оптимальные стратегии обоих игроков

цену игры и оптимальную стратегию 1 -го игрока

Если известно, что функция выигрыша 1-го игрока равна числу 1 в седловой точке, то значения выигрыша для 2-го игрока могут принимать .

значение, равное 1

только положительные значения

По характеру взаимоотношений позиционная игра относится к . играм

В антагонистической игре произвольной размерности выигрыш первого игрока — это .

вектор, или упорядоченное множество

Принцип доминирования позволяет удалять из матрицы за один шаг.

подматрицы меньших размеров

Исход игры в позиционных играх с полной и неполной информацией .

зависит от индивидуальности игрока

зависит от уровня информированности игроков

зависит от выбора стратегий игрока

не зависит от уровни информированности

Антагонистическая игра может быть задана:

множеством стратегий обоих игроков

функцией выигрыша обоих игроков

множеством стратегий обоих игроков и функцией выигрыша первого игрока

множеством стратегий обоих игроков и ценой игры

Антагонистическая игра – это частный случай матричной игры, при котором обязательным требованием является то, что …

оба игрока имеют конечное число стратегий

один из игроков имеет бесконечное число стратегий

оба игрока имеют одно и то же число стратегий

оба игрока имеют бесконечно много стратегий

Если в матрице все строки одинаковы и имеют вид ( 4 5 0 1), то оптимальной для 2-го игрока является … стратегия

Пусть в матричной игре размерности 2×3 одна из смешанных стратегий 1 -го игрока имеет вид (0.3, 0.7), а одна из смешанных стратегий 2-го игрока имеет вид (0.3, X, 0.5) — тогда число X равно .

Оптимальная смешанная стратегия смешивается только из тех чистых стратегий, вероятности которых .

имеют любое значение от нуля до единицы

отличны от нуля

Матричная игра – это частный случай биматричной игры, для которой всегда справедливо, что матрица А …

не равна матрице В

равна матрице В, взятой с обратным знаком

равна матрице В

В теореме Неймана утверждается, что в каждой матричной игре ситуация равновесия существует .

хотя бы в смешанных стратегиях

в линейных комбинациях смешанных и чистых стратегий

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

В теореме Нэша утверждается, что всякая биматричная игра имеет хотя бы одну ситуацию равновесия в.

линейных комбинациях смешанных и чистых стратегий

Если элемент матрицы aij соответствует седловой точке, то.

возможно, что этот элемент меньше всех в строке

этот элемент строго больше всех в строке

возможно, что в строке есть элементы и больше, и меньше, чем этот элемент

возможно, что этот элемент второй по порядку в строке

В позиционных играх с неполной информацией информационное множество отражает осведомленность игрока о .

своих фактических стратегиях

вероятностях применения стратегий обоих игроков

всех своих стратегиях и противника, предшествующих текущему ходу

Стратегия игрока в конечной позиционной игре есть функция, определенная на .

нескольких информационных множествах

всех информационных множествах

одном информационном множестве

Решением позиционной игры с полной информацией являются .

оптимальные чистые стратегии

оптимальные смешанные стратегии

линейные комбинации смешанных и чистых стратегий

Максимальное число седловых точек, которое может быть в игре размерности 2×3 (матрица может содержать любые числа), равно .

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

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

Смешанной стратегией первого игрока называется вектор , каждая компонента () которого − это вероятность применения первым игроком его i-й чистой стратегии в многоходовой игре.

Из определения смешанной стратегии следует, что компоненты вектора p удовлетворяют следующим соотношениям:

(5)

Аналогично определяется смешанная стратегия второго игрока. Смешанной стратегией второго игрока называется вектор , каждая компонента , , которого − это вероятность применения вторым игроком его j-й чистой стратегии в многоходовой игре. Компоненты вектора qудовлетворяют условиям:

(6)

Заметим, что чистые стратегии игроков являются частным случаем его смешанных стратегий. Например, i -я чистая стратегия игрока может быть представлена в виде такой смешанной стратегии, у которой i–я компонента равна 1, а все остальные − 0.

Читайте также:  Как достать окно за пределами рабочего стола

Если игроки используют свои смешанные стратегии, то функция

(7)

называется платежной функцией.

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

Первый игрок стремится максимизировать свой гарантированный выигрыш , который определяется из условия:

Поэтому оптимальная смешанная стратегия первого игрока является решением следующей задачи:

.

Второй игрок стремится минимизировать свой возможный наибольший проигрыш при выборе стратегии , который определяется из условия:

Поэтому оптимальная смешанная стратегия второго игрока является решением следующей задачи:

.

Если и − оптимальные смешанные стратегии игроков, то число

(8)

называется ценой игры.

Утверждение 2. Любая матричная игра имеет оптимальное решение в смешанных стратегиях.

Задача 1. Графическое решение матричных игр.

1. Найдем оптимальные стратегии игроков в игре, заданной платежной матрицей

.

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

Нижняя цена игры равна max <4, 3>= 4.

Верхняя цена этой игры равна min <7, 9, 9, 9>= 7.

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

Графически решаются те матричные игры, в которых хотя бы у одного из игроков есть лишь две чистые стратегии. Задача именно этого игрока и решается графически. В задаче 1 у первого игрока две чистых стратегии, а у второго − четыре, поэтому будем решать графически задачу первого игрока.

Смешанная стратегия первого игрока задается вектором . Построения осуществляются следующим образом. На горизонтальной прямой откладывается отрезок единичной длины, характеризующий вероятность применения чистых стратегий первым игроком. Каждой точке этого отрезка сопоставляется смешанная стратегия первого игрока по следующему правилу: расстояние от точки до правого конца отрезка задает величину , а расстояние до левого его конца − величину (см. рисунок 1.1). Для определенных таким образом величин и выполняются соотношения , , поэтому, согласно (5), вектор задает смешанные стратегии первого игрока.

Тогда точка 0 задает вектор (1, 0), т. е. первую чистую стратегию первого игрока, а точка 1 задает вектор (0, 1), т. е. вторую чистую стратегию первого игрока. Далее через концы единичного отрезка проводятся вертикальные линии. На этих линиях откладываются выигрыши первого игрока при применении вторым игроком его различных чистых стратегий. При этом выигрыши в случае применения первым игроком его первой чистой стратегии располагаются на левой вертикальной линии, а соответствующие второй чистой стратегии первого игрока − на правой вертикали. Точки левой и правой вертикали, соответствующие одной и той же чистой стратегии второго игрока, соединяются отрезками. На рисунке 1.2 изображены выигрыши первого игрока при применении вторым игроком первой чистой стратегии. Римскими цифрами указано, что второй игрок применяет именно первую чистую стратегию.

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

Аналогичные построения выполняются для остальных чистых стратегий второго игрока (рисунок 1.3). Римские цифры указывают на номер его чистой стратегии.

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

При определении оптимальной смешанной стратегии первого игрока и цены игры используется следующее утверждение:

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

  • АлтГТУ 419
  • АлтГУ 113
  • АмПГУ 296
  • АГТУ 266
  • БИТТУ 794
  • БГТУ «Военмех» 1191
  • БГМУ 172
  • БГТУ 602
  • БГУ 153
  • БГУИР 391
  • БелГУТ 4908
  • БГЭУ 962
  • БНТУ 1070
  • БТЭУ ПК 689
  • БрГУ 179
  • ВНТУ 119
  • ВГУЭС 426
  • ВлГУ 645
  • ВМедА 611
  • ВолгГТУ 235
  • ВНУ им. Даля 166
  • ВЗФЭИ 245
  • ВятГСХА 101
  • ВятГГУ 139
  • ВятГУ 559
  • ГГДСК 171
  • ГомГМК 501
  • ГГМУ 1967
  • ГГТУ им. Сухого 4467
  • ГГУ им. Скорины 1590
  • ГМА им. Макарова 300
  • ДГПУ 159
  • ДальГАУ 279
  • ДВГГУ 134
  • ДВГМУ 409
  • ДВГТУ 936
  • ДВГУПС 305
  • ДВФУ 949
  • ДонГТУ 497
  • ДИТМ МНТУ 109
  • ИвГМА 488
  • ИГХТУ 130
  • ИжГТУ 143
  • КемГППК 171
  • КемГУ 507
  • КГМТУ 269
  • КировАТ 147
  • КГКСЭП 407
  • КГТА им. Дегтярева 174
  • КнАГТУ 2909
  • КрасГАУ 370
  • КрасГМУ 630
  • КГПУ им. Астафьева 133
  • КГТУ (СФУ) 567
  • КГТЭИ (СФУ) 112
  • КПК №2 177
  • КубГТУ 139
  • КубГУ 107
  • КузГПА 182
  • КузГТУ 789
  • МГТУ им. Носова 367
  • МГЭУ им. Сахарова 232
  • МГЭК 249
  • МГПУ 165
  • МАИ 144
  • МАДИ 151
  • МГИУ 1179
  • МГОУ 121
  • МГСУ 330
  • МГУ 273
  • МГУКИ 101
  • МГУПИ 225
  • МГУПС (МИИТ) 636
  • МГУТУ 122
  • МТУСИ 179
  • ХАИ 656
  • ТПУ 454
  • НИУ МЭИ 641
  • НМСУ «Горный» 1701
  • ХПИ 1534
  • НТУУ «КПИ» 212
  • НУК им. Макарова 542
  • НВ 777
  • НГАВТ 362
  • НГАУ 411
  • НГАСУ 817
  • НГМУ 665
  • НГПУ 214
  • НГТУ 4610
  • НГУ 1992
  • НГУЭУ 499
  • НИИ 201
  • ОмГТУ 301
  • ОмГУПС 230
  • СПбПК №4 115
  • ПГУПС 2489
  • ПГПУ им. Короленко 296
  • ПНТУ им. Кондратюка 119
  • РАНХиГС 186
  • РОАТ МИИТ 608
  • РТА 243
  • РГГМУ 118
  • РГПУ им. Герцена 124
  • РГППУ 142
  • РГСУ 162
  • «МАТИ» — РГТУ 121
  • РГУНиГ 260
  • РЭУ им. Плеханова 122
  • РГАТУ им. Соловьёва 219
  • РязГМУ 125
  • РГРТУ 666
  • СамГТУ 130
  • СПбГАСУ 318
  • ИНЖЭКОН 328
  • СПбГИПСР 136
  • СПбГЛТУ им. Кирова 227
  • СПбГМТУ 143
  • СПбГПМУ 147
  • СПбГПУ 1598
  • СПбГТИ (ТУ) 292
  • СПбГТУРП 235
  • СПбГУ 582
  • ГУАП 524
  • СПбГУНиПТ 291
  • СПбГУПТД 438
  • СПбГУСЭ 226
  • СПбГУТ 193
  • СПГУТД 151
  • СПбГУЭФ 145
  • СПбГЭТУ «ЛЭТИ» 380
  • ПИМаш 247
  • НИУ ИТМО 531
  • СГТУ им. Гагарина 114
  • СахГУ 278
  • СЗТУ 484
  • СибАГС 249
  • СибГАУ 462
  • СибГИУ 1655
  • СибГТУ 946
  • СГУПС 1513
  • СибГУТИ 2083
  • СибУПК 377
  • СФУ 2423
  • СНАУ 567
  • СумГУ 768
  • ТРТУ 149
  • ТОГУ 551
  • ТГЭУ 325
  • ТГУ (Томск) 276
  • ТГПУ 181
  • ТулГУ 553
  • УкрГАЖТ 234
  • УлГТУ 536
  • УИПКПРО 123
  • УрГПУ 195
  • УГТУ-УПИ 758
  • УГНТУ 570
  • УГТУ 134
  • ХГАЭП 138
  • ХГАФК 110
  • ХНАГХ 407
  • ХНУВД 512
  • ХНУ им. Каразина 305
  • ХНУРЭ 324
  • ХНЭУ 495
  • ЦПУ 157
  • ЧитГУ 220
  • ЮУрГУ 306
Читайте также:  Поиск слов в документе word

Полный список ВУЗов

Чтобы распечатать файл, скачайте его (в формате Word).

Рассмотрим простейшую математическую модель конечной конфликтной ситуации, в которой имеется два участника и выигрыш одного равен проигрышу другого. Такая модель называется антагонистической игрой двух лиц с нулевой суммой. Игра состоит из двух ходов: игрок А выбирает одну из возможных стратегий Аi, , а игрок В выбирает одну из возможных стратегий Вj, . Каждый выбор производится при полном незнании выбора соперника. В результате выигрыш игроков составит соответственно aij и —aij. Цель игрока А — максимизировать величину aij, а игрока В — минимизировать эту величину.

Определение 1. Матрица, составленная из величин aij, , ,

называется платежной матрицей, или матрицей игры. Каждый элемент платежной матрицы aij, , равен выигрышу А (проигрышу В), если он выбрал стратегию Аi, , а игрок В выбирал стратегию Вj, .

Пример. В игре участвуют первый и второй игроки, каждый из них может записать независимо от другого цифры 1, 2 и 3. Если разность между цифрами, записанная игроками, положительна, то первый игрок выигрывает количество очков, равное разности между цифрами, и, наоборот, если разность отрицательна, то выигрывает второй игрок. Если разность равна нулю, то игра заканчивается вничью.

У первого игрока три стратегии (варианта действия): А1 (записать 1), А2 (записать 2), А3 (записать 3); у второго игрока также три стратегии: В1, В2, В3 (см. таблицу).

В1 = 1 В2 = 2 В3 = 3
А1 = 1 -1 -2
А2 = 2 -1
А3 = 3

Задача первого игрока — максимизировать свой выигрыш. Задача второго игрока — минимизировать свой проигрыш или минимизировать выигрыш первого игрока. Платежная матрица имеет вид

.

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

Найдем наилучшую стратегию первого игрока. Если игрок А выбрал стратегию Аi, , то в худшем случае (например, если его ход известен В) он получит выигрыш . Предвидя такую возможность, игрок А должен выбрать такую стратегию, чтобы максимизировать свой минимальный выигрыш.

.

Определение 2. Величина a — гарантированный выигрыш игрока А называется нижней ценой игры. Стратегия Aiопт, обеспечивающая получение выигрыша a, называется максиминной.

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

Аналогично определяется наилучшая стратегия второго игрока. Игрок В при выборе стратегии Вj, в худшем случае получит проигрыш . Он выбирает стратегию Bjопт, при которой его проигрыш будет минимальным и составит

Читайте также:  Количество дней в месяцах таблица

.

Определение 3. Величина b — гарантированный проигрыш игрока В называется верхней ценой игры. Стратегия Bjопт, обеспечивающая получение проигрыша b, называется минимаксной.

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

Фактический выигрыш игрока А (проигрыш игрока В) при разумных действиях партнеров ограничен верхней и нижней ценой игры. Для матричной игры справедливо неравенство a £ b.

Определение 4. Если a = b =v, т. е.

= ,

то выигрыш игрока А (проигрыш игрока В) оределяется числом v. Оно называется ценой игры.

Определение 5. Если a = b =v, то такая игра называется игрой с седловой точкой, элемент матрицы аiопт jопт = v, соответствующий паре оптимальных стратегий (Aiопт, Bjопт), называется седловой точкой матрицы. Этот элемент является ценой игры.

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

Определение 6. Если игра имеет седловую точку, то говорят, что она решается в чистых стратегиях.

Найдем решение игры рассмотренного выше примера:

,

a = a3 — нижняя цена игры.

,

b = b3 — верхняя цена игры.

Так как a = b = 0, матрица игры имеет седловую точку.

Оптимальная стратегия первого игрока – А3 , второго — B3. Из таблицы видно, что отклонение первого игрока от оптимальной стратегии уменьшает его выигрыш, а отклонение второго игрока от В3 увеличивает его проигрыш.

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

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

Примерами игр с полной информацией могут служить шашки, шахматы, "крестики-нолики" и т.д.

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

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

Решение матричной игры в смешанных стратегиях

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

, .

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

, .

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

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

Определение 3. Если все элементы i-й строки платежной матрицы больше соответствующих элементов k-й строки, то
i-я стратегия игрока
А называется доминирующей над k-й стратегией. Если все элементы j-го столбца платежной матрицы меньше соответствующих элементов k-го столбца, то j-я стратегия игрока В называется доминирующей над k-й стратегией.

Пример.Рассмотрим игру, представленную платежной матрицей

.

a = max (2, 2, 3, 2) = 3, b = min (7, 6, 6, 4, 5) = 4, a ¹ b, .

Все элементы стратегии А2 меньше элементов стратегии А3, т.е. А2 заведомо невыгодна для первого игрока и ее можно исключить. Все элементы А4 меньше А3, исключаем А4.

.

Для второго игрока: сравнивая В1 и В4, исключаем В1; сравнивая В2 и В4, исключаем В2; сравнивая В3 и В4, исключаем В3. В результате преобразований получим матрицу

.

a = max (2, 3) = 3, b = min (4, 5) = 4, a ¹ b, .

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: Сдача сессии и защита диплома — страшная бессонница, которая потом кажется страшным сном. 9189 — | 7397 — или читать все.

Ссылка на основную публикацию
Adblock detector