Теория игр

4 задачи по теории игр ...

Задача 1. Две компании, занимающиеся производством антивирусного программного обеспечения, практически полностью делят рынок некоторого региона. Разрабатывая новую версию программного продукта для мобильных телефонов, каждая из компаний может использовать один из четырех вариантов продвижения нового программного продукта на рынок, который влияет на конечную стоимость продукции. В зависимости от сделанного выбора компании могут установить цену реализации единицы продукции на уровне 25, 22, 19 и 16 условных единиц соответственно.
Задача 2. Две отрасли могут осуществлять капитальные вложения в 3 объекта. Стратегии отраслей: i-я стратегия состоит в финансировании i-го объекта (i = 1, 2, 3). Учитывая особенности вкладов и местные условия, прибыли первой отрасли выражаются матрицей 3х3. Величинаприбыли первой отрасли считается такой же величиной убытка для второй отрасли - представленная игра может рассматриваться как игра двух игроков с нулевой суммой. Решить приближенно матричную игру методом Брауна-Робинсон (выполнить 10 итераций):
Задача 3. Сельскохозяйственное предприятие планирует посадить некоторую сельскохозяйственную культуру двух сортов. Посевная площадь 1000 га. Сорта отличаются друг от друга требованиями к влаге во время вегетационного периода. Проанализировав погодные условия, выделены 4 состояния погоды (S1, S2, S3, S4), отличающиеся режимом осадков и найдены статистические вероятности каждого состояния: p1=0.1; p2=0.3; p3=0.4; p4=0.2. Средняя урожайность (ц/га) каждого сорта на всем участке для каждой состояния погоды приведена в таблице:
Свести позиционную игру к матричной и решить ее:
1-й ход делает игрок A : он выбирает число x из множества двух чисел {1,2}.
2 -й ход делает игрок B : зная выбранное игроком A число x , он выбирает число y из множества двух чисел {1,2}.
3-й ход делает игрок A : зная о выбранном игроком B числе y на 2-м ходе, но забыв выбранное им самим на 1-м ходе число x , он выбирает число z из множества двух чисел {1,2}.
После этого игрок A получает вознаграждение за счет игрока B :
W(1,1,1) = -4 , W(1,1,2) = 5, W(2,1,1) = 4 , W(2,1,2) = -4 , W(1,2,1) = 2 , W(2,2,1) = -4 , W(1,2,2) = 4 , W(2,2,2) = -6

Задача 1. Две компании, занимающиеся производством антивирусного программного обеспечения, практически полностью делят рынок некоторого региона. Разрабатывая новую версию программного продукта для мобильных телефонов, каждая из компаний может использовать один из четырех вариантов продвижения нового программного продукта на рынок, который влияет на конечную стоимость продукции. В зависимости от сделанного выбора компании могут установить цену реализации единицы продукции на уровне 25, 22, 19 и 16 условных единиц соответственно.
Задача 2. Две отрасли могут осуществлять капитальные вложения в 3 объекта. Стратегии отраслей: i-я стратегия состоит в финансировании i-го объекта (i = 1, 2, 3). Учитывая особенности вкладов и местные условия, прибыли первой отрасли выражаются матрицей 3х3. Величина прибыли первой отрасли считается такой же величиной убытка для второй отрасли - представленная игра может рассматриваться как игра двух игроков с нулевой суммой. Решить приближенно матричную игру методом Брауна-Робинсон (выполнить 10 итераций):
Задача 3. Сельскохозяйственное предприятие планирует посадить некоторую сельскохозяйственную культуру двух сортов. Посевная площадь 1000 га. Сорта отличаются друг от друга требованиями к влаге во время вегетационного периода. Проанализировав погодные условия, выделены 4 состояния погоды (S1, S2, S3, S4), отличающиеся режимом осадков и найдены статистические вероятности каждого состояния: p1=0.1; p2=0.3; p3=0.4; p4=0.2. Средняя урожайность (ц/га) каждого сорта на всем участке для каждой состояния погоды приведена в таблице:
Свести позиционную игру к матричной и решить ее:
1-й ход делает игрок A : он выбирает число x из множества двух чисел {1,2}.
2 -й ход делает игрок B : зная выбранное игроком A число x , он выбирает число y из множества двух чисел {1,2}.
3-й ход делает игрок A : зная о выбранном игроком B числе y на 2-м ходе, но забыв выбранное им самим на 1-м ходе число x , он выбирает число z из множества двух чисел {1,2}.
После этого игрок A получает вознаграждение за счет игрока B :
W(1,1,1) = -4 , W(1,1,2) = 5, W(2,1,1) = 4 , W(2,1,2) = -4 , W(1,2,1) = 2 , W(2,2,1) = -4 , W(1,2,2) = 4 , W(2,2,2) = -6

Говорят, что i-я стратегия 1-го игрока доминирует его k-ю стратегию, если aij ≥ akj для всех j Э N и хотя бы для одного j aij > akj. В этом случае говорят также, что i-я стратегия (или строка) – доминирующая, k-я – доминируемая.Говорят, что j-я стратегия 2-го игрока доминирует его l-ю стратегию, если для всех j Э M aij ≤ ail и хотя бы для одного i aij < ail. В этом случае j-ю стратегию (столбец) называют доминирующей, l-ю – доминируемой.В платежной матрице отсутствуют доминирующие строки.В платежной матрице отсутствуют доминирующие столбцы.Так как игроки выбирают свои чистые стратегии случайным образом, то выигрыш игрока I будет случайной величиной. В этом случае игрок I должен выбрать свои смешанные стратегии так, чтобы получить максимальный средний выигрыш.Аналогично, игрок II должен выбрать свои смешанные стратегии так, чтобы минимизировать математическое ожидание игрока I.Пусть игра задана матрицей A размерности m x n. Каждое разыгрывание игры в чистых стратегиях будет далее называться партией. Метод Брауна-Робинсон — это итеративная процедура построения последовательности пар смешанных стратегий игроков, сходящейся к решению матричной игры.В 1-ой партии оба игрока выбирают произвольную чистую стратегию. Пусть сыграно k партий, причем выбор стратегии в каждой партии запоминается. В (k + 1)-ой партии каждый игрок выбирает ту чистую стратегию, которая максимизирует его ожидаемый выигрыш, если противник играет в соответствии с эмпирическим вероятностным распределением, сформировавшимся за k партий. Оценивается интервал для цены игры и, если он достаточно мал, процесс останавливается. Полученные при этом вероятностные распределения определяют смешанные стратегии игроков.Пусть на первом этапе выбрана стратегия №1Итерация №1. Минимальный элемент для нее равен -4 и находится под номером j=2. Следовательно, игрок II выбирает стратегию №2. Максимальный элемент равен 3 и находится под номером j=2. Следовательно, игрок I выбирает стратегию №2Итерация №2. Минимальный элемент для нее равен -5 и находится под номером j=3. Следовательно, игрок II выбирает стратегию №3Максимальный элемент равен 1 и находится под номером j=3. Следовательно, игрок I выбирает стратегию №3Остальное решение сведем в таблицу.kiB1B2B3jA1A2A3VminVmaxVср110-4-12-433-43-1/2221-1-53-5-11-5/21/2-133-22-73-6-5-1-7/3-1/3-4/343-55-93-7-9-3-9/4-3/4-3/253-88-113-8-13-5-11/5-1-8/563-1111-133-9-17-7-13/6-7/6-5/373-1414-153-10-21-9-15/7-9/7-12/783-1717-171-10-20-12-17/8-5/4-27/1691-1713-183-11-24-14-2-11/9-29/18101-179-193-12-28-16-19/10-6/5-31/20здесь:k - номер партии.i - номер стратегии, выбираемой игроком A.j - номер стратегии, выбираемой игроком В.Bi - накопленный игроком А выигрыш за k партий, при условии, что в данной партии B выбирает стратегию Bi.Аj - накопленный игроком В проигрыш за k партий, при условии, что в данной партии A выбирает стратегию Аj.Vmin - нижняя оценка игры = min (накопленный выигрыш)/k.Vmax - верхняя оценка игры = max (накопленный проигрыш)/k. Доказано, что:W=(Vmin+Vmax)/2, при k → ∞ и pi = Ni/kqj = Nj/kNi - сколько раз выбирается Аi стратегия.Nj - сколько раз выбирается Bj стратегия.NA1 = 3P(A1) = 3/10 = 3/10NA2 = 1P(A2) = 1/10 = 1/10NA3 = 6P(A3) = 6/10 = 3/5NB1 = 1P(B4) = 1/10 = 1/10NB2 = 1P(B4) = 1/10 = 1/10NB3 = 8P(B4) = 8/10 = 4/5Цена игры, W = -31/20Стратегия игрока I: p = (3/10, 1/10, 3/5)Стратегия игрока II: q = (1/10, 1/10, 4/5) Задача 3. Сельскохозяйственное предприятие планирует посадить некоторую сельскохозяйственную культуру двух сортов. Посевная площадь 1000 га. Сорта отличаются друг от друга требованиями к влаге во время вегетационного периода. Проанализировав погодные условия, выделены 4 состояния погоды (S1, S2, S3, S4), отличающиеся режимом осадков и найдены статистические вероятности каждого состояния: p1=0.1; p2=0.3; p3=0.4; p4=0.2. Средняя урожайность (ц/га) каждого сорта на всем участке для каждой состояния погоды приведена в таблице:S1S2S3S4Сорт 123+49=7229+49=7831+49=8037+49=86Сорт 236+49=8533+49=8228+49=7724+49=73Возможные варианты посева:А1) сорт 1 посадить на 75% площади, сорт 2 посадить на 25% площади;А2) сорт 1 посадить на 50% площади, сорт 2 посадить на 50% площади;А3) сорт 1 посадить на 25% площади, сорт 2 посадить на 75% площади;Определить оптимальную стратегию с помощью критериев максимального математического ожидания, недостаточного основания Лапласа, максиминного критерия Вальда, пессимизма-оптимизма Гурвица (коэффициент пессимизма взять равным 0,4), критерия Ходжа-Лемана (коэффициент достоверности информации о состояниях погоды принять равным 0,7), критерия минимаксного риска Сэвиджа.РешениеРассчитаем элементы матрицы полезности:А1) сорт 1 посадить на 75% площади (75/100*1000га = 750 га), сорт 2 посадить на 25% площади (25/100*1000га = 250 га):S1 = (750 га * 72 ц/га) + (250 га * 85 ц/га) = 75250 цS2 = (750 га * 78 ц/га) + (250 га * 82 ц/га) = 79000 цS3 = (750 га * 80 ц/га) + (250 га * 77 ц/га) = 79250 цS4 = (750 га * 86 ц/га) + (250 га * 73 ц/га) = 82750 цА2) сорт 1 посадить на 50% площади (50/100*1000га = 500 га), сорт 2 посадить на 50% площади (50/100*1000га = 500 га):S1 = (500 га * 72 ц/га) + (500 га * 85 ц/га) = 78500 цS2 = (500 га * 78 ц/га) + (500 га * 82 ц/га) = 80000 цS3 = (500 га * 80 ц/га) + (500 га * 77 ц/га) = 78500 цS4 = (500 га * 86 ц/га) + (500 га * 73 ц/га) = 79500 цА3) сорт 1 посадить на 25% площади (25/100*1000га = 250 га), сорт 2 посадить на 75% площади (75/100*1000га = 750 га):S1 = (250 га * 72 ц/га) + (750 га * 85 ц/га) = 81750 цS2 = (250 га * 78 ц/га) + (750 га * 82 ц/га) = 81000 цS3 = (250 га * 80 ц/га) + (750 га * 77 ц/га) = 77750 цS4 = (250 га * 86 ц/га) + (750 га * 73 ц/га) = 76250 цНа основании выполненных расчетов составим матрицу полезности:S1S2S3S4А175250790007925082750А278500800007850079500А381750810007775076250Элементы данной матрицы – сбор урожая (ц), при заданных вариантах посева и погодных условиях. Критерий Байеса.По критерию Байеса за оптимальные принимается та стратегия (чистая) Ai, при которой максимизируется средний выигрыш a или минимизируется средний риск r.Считаем значения ∑(aijpj)∑(a1,jpj) = 75250•0.1 + 79000•0.3 + 79250•0.4 + 82750•0.2 = 79475∑(a2,jpj) = 78500•0.1 + 80000•0.3 + 78500•0.4 + 79500•0.2 = 79150∑(a3,jpj) = 81750•0.1 + 81000•0.3 + 77750•0.4 + 76250•0.2 = 78825AiП1П2П3П4∑(aijpj)A1752523700317001655079475A2785024000314001590079150A3817524300311001525078825pj0.10.30.40.2Выбираем из (79475; 79150; 78825) максимальный элемент max=79475Вывод: выбираем стратегию А=1.Критерий Лапласа.Если вероятности состояний природы правдоподобны, для их оценки используют принцип недостаточного основания Лапласа, согласно которого все состояния природы полагаются равновероятными, т.е.:q1 = q2 = ... = qn = 1/n.qi = 1/4AiП1П2П3П4∑(aij)A118812.51975019812.520687.579062.5A21962520000196251987579125A320437.52025019437.519062.579187.5pj0.250.250.250.25Выбираем из (79062.5; 79125; 79187.5) максимальный элемент max=79187.5Вывод: выбираем стратегию А=3.Критерий Вальда.По критерию Вальда за оптимальную принимается чистая стратегия, которая в наихудших условиях гарантирует максимальный выигрыш, т.е.a = max(min aij)Критерий Вальда ориентирует статистику на самые неблагоприятные состояния природы, т.е. этот критерий выражает пессимистическую оценку ситуации.