Теория игр

ГБОУ ВПО

«Ставропольский государственный медицинский университет»

Факультет гуманитарного и медико-биологического образования

Кафедра организации здравоохранения, экономики и социальной работы

Дисциплина: «Теория игр»

 

 

 

 

Контрольная работа

Вариант №1

 

Исполнитель

студентка факультета ГМБО

заочная форма обучения

направление: Экономика

2 курса 280 группы

Зачётная книжка № 80026

Автандилян Лиана Леноровна

 

Ставрополь, 2014

Вариант №6

1. Позиционные игры.
2. Доминирование

 

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

Переходы игрока из одного информационного состояния в другое могут сопровождаться получением или утратой им информации об уже имевших место информационных состояниях (как самого игрока, так и других игроков) и выбиравшихся в них альтернативах. Полное описание этого называется информацией игрока в П. и. Информация игрока о самом себе (т. е. о собственных бывших состояниях и альтернативах) называется его памятью. Особенности информации и памяти игроков в игре могут позволить упрощать характеризацию её ситуаций равновесия и сужать область их поисков. Так, если П. и. с конечным числом информационных состояний есть игра с полной информацией (т. е. в любой её момент каждый игрок знает все бывшие информационные состояния и сделанные в них выборы), то в ней имеются ситуации равновесия в чистых стратегиях, т. е. без обращения к смешанным стратегиям. При переходе к П. и. с бесконечным множеством информационных состояний (например, два игрока поочередно называют десятичные цифры a1, а2, a3, a4,... и если получающееся в результате число 0, a1a2a3a4... будет принадлежать некоторому множеству, то первый игрок выигрывает единицу; в противном случае единицу выигрывает второй игрок) это утверждение теряет силу, и могут наблюдаться явления парадоксального характера, математически весьма сложные. Если в П. и. с конечным числом информационных состояний некоторый игрок имеет полную память (т. е. знает все бывшие собственные информационные состояния и выборы в них), то он может без ущерба для себя ограничиться стратегиями поведения, в которых выборы альтернатив в различных информационных состояниях могут быть случайными (рандомизированными), но должны быть стохастически независимыми в совокупности.

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

 

В некоторых случаях исход игры можно предсказать однозначно, если игроки, как принято говорить, рациональны, и их выигрыши таковы, что рациональный выбор игроков не зависит от выбора других игроков. 
 
Такая ситуация имеет место в игре «Выбор компьютера», если выгода от совместимости программного обеспечения (с) сравнительно мала, например, в случае, когда a = 2, b = 3, c = 1. 
 
Доминирующие стратегии 

:		Игрок 2
		IBM	Mac
Игрок 1	IBM	с = 1	b = 3
		a+c = 3	а = 2
	Mac	0	b+c = 4
		0	с = 1

 
Тогда, если Игрок 2 выберет «IBM» (что соответствует левой колонке таблицы), то Игроку 1 выгоднее выбрать «IBM», чем «Mac» (поскольку 3 > 0). Если Игрок 2 выберет «Mac» (правая колонка), то Игроку 1 все равно выгоднее выбрать «IBM», чем «Mac» (поскольку 2 > 1). 
Иначе говоря, вне зависимости от того, какой компьютер выберет Игрок 2, Игроку 1 выгодно выбрать компьютер IBM PC. Аналогично, Игрок 2 предпочтет Макинтош, поскольку 3 > 1 и 4 > 0.  
В каждом столбце (т.е. при заданной стратегии Игрока 2) для Игрока 1 подчеркнем самое большое значение выигрыша (в данном случае это a+c=3 и а=2). 
В каждой строке (т.е. при заданной стратегии Игрока 1) для Игрока 2 подчеркнем самое большое значение выигрыша (в данном случае это b=3 и b+c=4). 
Для каждого игрока имеет место так называемое строгое доминирование стратегий. 
Определения

Если стратегия xi игрока i при любых действиях других игроков дает ему больший выигрыш, чем его стратегия yi, то говорят, что стратегия xi строго доминирует стратегию yi. 
Дадим формальное определение строгого доминирования. Здесь и в дальнейшем мы будем применять обозначение x–i, что означает «все элементы набора x, кроме i-го», т.е. 
x–i = (x1, ..., xi–1, xi+1, xn). 
 
 
При этом будем считать, что (xi, x–i) – это то же самое, что x. 
Стратегия xi  игрока i строго доминирует стратегию yi  этого же игрока, если при любых стратегиях x–i, выбранных остальными игроками, выполнено условие: 
ui(xi, x–i) > ui(yi, x–i), (т.е. выигрыш от xi  всегда больше выигрыша от yi) 
Стратегия xi  игрока i является его строго доминирующей стратегией, если при любых стратегиях, выбранных остальными игроками x–i, она дает игроку i больший выигрыш, чем любая другая его стратегияyi , т.е. 
ui(xi, x–i) > ui(yi, x–i), при любом yi ¹ xi. 
(Строго доминирующая стратегия игрока строго доминирует любую другую его стратегию). 
В соответствие с данным определением не может существовать более одной строго доминирующей стратегии.  
Естественно ожидать, что рациональный игрок выберет именно такую стратегию. Поэтому при наличии у каждого игрока строго доминирующей стратегии исход игры можно предсказать однозначно. 
Игра 2. «Дилемма заключенного». Игра представляет знаменитый пример ситуации, которая в дальнейшем будет встречаться в разных вариантах. Опишем ее классический вариант, который дал название целому классу подобных ситуаций.  
Два индивида, подозреваемых в совершении тяжкого преступления, могут быть осуждены на срок в 25 лет в том случае, если следствию удастся доказать факт совершения преступления. Следователи убеждены в виновности подозреваемых, но без сотрудничества с ними (по крайней мере, одного из них), не способны доказать их виновность. Поэтому следователи идут на сделку с подозреваемыми, предложив каждому из них сотрудничество в обмен на снижение срока наказания – до 10 лет каждому из подозреваемых, если сотрудничать со следствием согласятся оба подозреваемых, и – до 1 года (согласившемуся на сотрудничество подозреваемому), если сотрудничать согласится только один из них. При отказе от сотрудничества обоих подозреваемых существующие улики позволяют осудить обоих обвиняемых только на срок до 3 лет.  
Задача 1. Охарактеризуйте описанную ситуацию в виде игры (игроки, их стратегии, матрица выигрышей). Какие стратегии, по Вашему мнению, выберут игроки, и каким при этом будет исход игры? 
Решение. В этой игре участвуют два игрока. Каждый из них имеет две стратегии «согласиться на сотрудничество» или просто «согласиться» и «отказаться от сотрудничества» или просто «отказаться». Поскольку в игре два игрока и конечное множество стратегий, то можно построить матрицу игры. Она имеет вид  
^ Доминирующие стратегии 

Дилемма заключенного		Игрок 2
		Отказаться	Согласиться
Игрок 1	Отказаться	–3	–1
		–3	–25
	Согласиться	–25	–10
		–1	–10

 
 
У каждого игрока есть строго доминирующая стратегия «согласиться на сотрудничество».  
 
Замечание. «Дилеммой заключенного» называется любая игра двух лиц, матрица выигрышей которой симметрична и имеет вид, представленный в таблице, причем d > a – b. Ее особенность – наличие у каждого игрока строго доминирующей стратегии и тот факт, что существуют ситуации, в которых выигрыши каждого игрока выше, чем при выборе доминирующих стратегий.  
 

Обобщенная дилемма		Игрок 2
		Стратегия 1	Стратегия 2
Игрок 1	Стратегия 1	a	a + c
		a	a – b
	Стратегия 2	a – b	d
		a + c	d

 
 
Задача 2. Проверьте, что выбор стратегий в обобщенной «дилемме заключенного» полностью аналогичен рассмотренному частному случаю. 
Ответ: Оба выберут Стратегию 2, так как она является доминирующей стратегия для обоих игроков.  
Задача 3. В чем Вы видите сходство и различие между решениями игр «Дилемма заключенного» и «Выбор компьютера»? Можете ли Вы предложить ситуации, которые аналогичны «Дилемме заключенного»? 
 
 
Ответ: Сходство в том, что в обеих играх у каждого игрока есть строго доминирующая стратегия. Но игра «Выбор компьютера» не является примером «дилеммы заключенного», поскольку в этой игре не существует ситуации, в которой выигрыши обоих игроков выше, чем в ситуации, которую они предпочтут при рациональном выборе.  
Предсказание исхода игры двух лиц не столь однозначно, если у каждого игрока имеется лишь так называемая (слабо) доминирующая стратегия, обеспечивающая этому игроку не меньший выигрыш, чем любая другая его стратегия при любых стратегиях других игроков. Приведем определение (слабого) доминирования. 
Определение

Стратегия xi  игрока i доминирует (слабо доминирует) его стратегию yi , если при любых стратегиях, выбранных остальными игроками x–i, выполнено 
ui(xi, x–i) ³ ui(yi, x–i),  
и существует хотя бы один набор стратегий других игроков, такой что 
ui(xi, x) > ui(yi, x). 
Иначе говорят, что стратегия yi доминируется стратегией xi. 
Определение

Стратегия xi  игрока i является его доминирующей стратегией (слабо доминирующей), если при любых стратегиях, выбранных остальными игроками, x–i , она доминирует (слабо доминирует) любую другую его стратегию yi  либо эквивалентна ей, т.е. 
ui(xi, x–i) ³ ui(yi, x–i)  при всех x–i, yi  
Из определения следует, что строгое доминирование является частным случаем доминирования. 
Определение

Исход игры x*  является равновесием в доминирующих стратегиях, если стратегия каждого игрока в этом исходе является его доминирующей стратегией. 
 
Примером ситуации, в которой у каждого игрока есть доминирующая стратегия, но нет строго доминирующей стратегии, является аукцион Викри.  
Игра 3. «Аукцион Ви¢кри». Некий предмет продается с аукциона. Каждый из окупателей (i = 1, ..., m) подает в тайне от других свою заявку – предлагаемую им цену pi. Побеждает участник, предложивший самую высокую цену, но платит он самую большую цену, предложенную другими покупателями. Если самую высокую цену предложат сразу несколько участников, то победитель определяется жребием.  
Другими словами, если i-й участник окажется победителем, то его выигрыш составит vi – p, где vi – ценность для него данного предмета, p – цена, которую он должен заплатить (выигрыш остальных покупателей будет равен нулю). 
Особенность аукциона Викри состоит в том, что «правдивая» стратегия является доминирующей стратегией для каждого участника. «Правдивая» стратегия заключается в том, что участник называет цену, совпадающую с ценностью для него данного предмета (pi = vi).  
Проверим это. Сначала проанализируем данную игру в случае, когда есть всего два участника (m = 2), а предлагаемые цены (заявки участников) могут принимать только конечное число значений.  
Пусть, например, v1 > v2, и v1– v2 = 1. Предположим, что заявки могут принимать значения v1–2, v1–1, v1,v1 +1 или, в других обозначениях v2–1, v2, v2+1, v2 +2. 
Задача 4. Опишете игру, соответсвующую аукциону Викри (укажите игроков, их стратегии и функции выигыша). 
Ответ. Если при равенстве заявок предмет получает любой участник с вероятностью ½ и если его выигрыш оценивается (средней) величиной, то матрица выигрышей имеет вид: 

^ Аукцион Викри		Игрок 2 (выбор p2)
		v2–1 = v1–2	v2 = v1–1	v2+1 = v1	v2+2 = v1+1
^ Игрок 1    (выбор p1)	v1–2	(ничья) 1/2	1	1	1
		1	0	0	0
	v1–1	0	(ничья) 0	0	0
		2	1/2	0	0
	v1	0	0	(ничья) –1/2	-1
		2	1.	0	0
	v1+1	0	0	0	(ничья) -1
		2	1	0	-1/2

 
 
Например, в левой верхней клетке, если выиграет Игрок 1, то его выигрыш составит 2, но поскольку он выигрывает с вероятностью ½, то его средний выигрыш равен 1. 
 
Стратегия pi = vi является доминирующей (но не строго доминирующей) стратегией каждого участника аукциона. Поэтому в данной игре существует равновесие в доминирующих стратегиях  
Задача 5. Проверьте, что «правдивые» заявки являются доминирующими стратегиями каждого игрока, но не строго доминирующими стратегиями.  
Вернемся к анализу аукциона с любым числом участников, в котором участники не ограничены в выборе заявок. Покажем, что утверждение задачи 5 имеет место и в случае, когда нет ограничений на величину заявок участников. Для простоты будем по-прежнему предполагать, что в аукционе два участника. (При большем количестве участников рассуждения будут аналогичными).  
Поскольку участники входят в данную игру симметрично, то достаточно рассмотреть мотивацию только одного из них, например, 1-го. 
Вычислим сначала выигрыши Игрока 1 при разных исходах. Если Игрок 1 назовет более высокую цену, чем Игрок 2 (p1 > p2), то он выиграет аукцион и заплатит p2. При этом его выигрыш составит v1 – p2. Если Игрок 1 назовет более низкую цену, чем Игрок 2 (p1 < p2), то он проиграет аукцион и получит выигрыш 0. Если цены совпадут (p1 = p2), то с вероятностью 1/2 Игрок 1 получит выигрыш v1 – p2, а с вероятностью 1/2 он выигрыш 0. Таким образом, его ожидаемый выигрыш составит (v1 – p2)/2. Окончательно запишем функцию выигрыша Игрока 1: 
 
 
 
Чтобы показать, что «правдивая» стратегия, p1 = v1, является доминирующей, нужно показать, что она дает не меньший выигрыш, чем любая другая стратегия. Следует рассмотреть 3 случая: p2 > v1, p2 = v1 и p2 < v1. 
 
Случай p2 > v1. В этом случае Игроку 1 не выгодно выигрывать аукцион, поскольку его выигрыш был бы отрицательный, а в случае проигрыша он получит 0. Поэтому «правдивая» стратегия является одной из оптимальных. 
 
Случай p2 = v1. В этом случае Игрок 1 получит 0. Значит, «правдивая» стратегия даст ему выигрыш не меньший, чем любая другая. 
 
Случа p2 < v1. В этом случае Игроку 1 выгодно выиграть аукцион, поскольку его выигрыш будет положительным. «Правдивая» стратегия обеспечивает ему максимальный выигрыш, v1 – p2. 
 
Мы видим, что «правдивая» стратегия, в самом деле, является доминирующей для Игрока 1. Более того, как несложно увидеть, это единственная доминирующая стратегия. Если он назовет цену ниже или выше своей оценки v1, то можно подобрать такую цену Игрока 2, что Игрок 1 потеряет по сравнению с p1 = v1. 
Проведя аналогичные рассуждения для Игрока 2, мы сделаем вывод, что в этой игре существует (единственное) равновесие в доминирующих стратегиях: 
 
p1 = v1, p2 = v2.