Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

'Урок'
Домашнее задание: по желанию учащихся подготовитьсообщения о выращивании и переработке хлопчатника и льна,о роли льняных и хлопчатобумажных тканей в р...полностью>>
'Программа'
проведение маркетинговых исследований для формирования конкурентоспособных предложений с целью стимулирования повышения объема работ с постоянными зак...полностью>>
'Документ'
Термодинамическая вероятность протекания хим. реакции определяется величиной изменения свободной энергии Гиббса ∆G (изобарно-изотермического потенциал...полностью>>
'Программа'
Регуляция физиологических процессов человека. Строение нервной системы: центральный и периферический отделы. Нервная регуляция соматических и вегетати...полностью>>

Главная > Тесты

Сохрани ссылку в одной из сетей:
Информация о документе
Дата добавления:
Размер:
Доступные форматы для скачивания:

СОДЕРЖАНИЕ

П.И.Чайковский 3

1. ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ИГР И ИХ КЛАССИФИКАЦИЯ 3

1.1. Предмет и задачи теории игр 3

1.2. Терминология и классификация игр 4

1.3. Примеры игр 6

ТЕСТЫ 7

2. МАТРИЧНЫЕ ИГРЫ 8

2.1. Описание матричной игры 8

2.2. Принцип максимина в антагонистических играх. Седловая точка 9

ТЕСТЫ 11

ЗАДАЧИ 12

2.3. Чистые и смешанные стратегии 13

2.4. Основные теоремы матричных игр 14

ТЕСТЫ 15

2.5. Решение матричной игры (2х2) 16

ЗАДАЧИ 21

2.6. Упрощение матричных игр 22

2.7.Решение игр 2xn и mx2 24

ТЕСТЫ 26

ЗАДАЧИ 27

2.8. Решение игр mхn. Эквивалентные задачи линейного программирования 27

ТЕСТЫ 32

ЗАДАЧИ 32

2.9. Приближенный метод решения матричных игр mxn 32

2.10. Качественная оценка элементов платежной матрицы 34

2.11. Способы реализации случайного механизма выбора стратегий 35

ТЕСТЫ 37

ЗАДАЧИ 37

3. ПОЗИЦИОННЫЕ ИГРЫ 38

3.1. Общие сведения 38

3.2. Задание позиционной игры в виде дерева 39

3.3. Решение позиционной игры с полной информацией 41

3.4. Нормализация позиционной игры 42

ТЕСТЫ 43

ЗАДАЧИ 44

4. БЕСКОНЕЧНЫЕ АНТАГОНИСТИЧЕСКИЕ ИГРЫ 45

4.1.Общие сведения 45

4.2. Решение выпуклых игр на единичном квадрате 46

4.3. Примеры решения бесконечных антагонистических игр 47

ТЕСТЫ 52

ЗАДАЧИ 53

5. БЕСКОАЛИЦИОННЫЕ ИГРЫ 54

5.1. Общие сведения 54

5.2. Ситуации, оптимальные по Парето 55

5.3. Состояние равновесия по Нэшу 57

5.4. Описание биматричных игр 58

5.5. Решение биматричных игр 59

5.5. Пример решения биматричной игры 62

5.6. Метастратегии и метарасширения 66

ТЕСТЫ 68

ЗАДАЧИ 69

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 75

удк 519.83 + 519.86

Василевич Л.Ф. Теория игр. КИИМ, 2000

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

«Что наша жизнь? – Игра.»

«Пиковая дама».

П.И.Чайковский

1. ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ИГР И ИХ КЛАССИФИКАЦИЯ

1.1. Предмет и задачи теории игр

Первую попытку создать математическую теорию игр предпринял в 1921 г. Э.Борель. Как самостоятельная область науки впервые теория игр была систематизировано изложена в монографии Дж.фон Неймана и О.Моргенштерна “Теория игр и экономическое поведение” в 1944 г. С тех пор многие разделы экономической теории (например, теория несовершенной конкуренции, теория экономического стимулирования и др.) развивались в тесном контакте с теорией игр [2]. Теория игр с успехом применяется и в социальных науках (например, анализ процедур голосования, поиск равновесных концепций, определяющих кооперативные и некооперативные поведения лиц). Как правило, избиратели отводят кандидатов, представляющих крайние точки зрения, но при избрании одного из двух кандидатов, предлагающих различные компромиссные решения, возникает борьба. Даже идея Руссо об эволюции от «естественной свободы» к «гражданской свободе» формально соответствует с позиций теории игр точке зрения на кооперацию.

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

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

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

Теория игр - это математическая теория конфликтных ситуаций.

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

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

Теория игр, как и всякая математическая модель, имеет свои ограничения. Одним из них является предположение о полной (“идеальной”) разумности противников. В реальном конфликте зачастую оптимальная стратегия состоит в том, чтобы угадать, в чем противник “глуп” и воспользоваться этой глупостью в свою пользу [1].

Еще одним недостатком теории игр является то, что каждому из игроков должны быть известны все возможные действия (стратегии) противника, неизвестно лишь то, каким именно из них он воспользуется в данной партии. В реальном конфликте это обычно не так: перечень всех возможных стратегий противника как раз и неизвестен, а наилучшим решением в конфликтной ситуации нередко будет именно выход за пределы известных противнику стратегий, “ошарашивание” его чем-то совершенно новым, непредвиденным [1].

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

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

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

В настоящее время ведутся научные исследования, направленные на расширение областей применения теории игр.

1.2. Терминология и классификация игр

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

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

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

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

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

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

Повторим, что задача теории игр - нахождение оптимальных стратегий.

Классификация игр представлена на рис. 1.1.

1. В зависимости от видов ходов игры подразделяются на стратегические и азартные. Азартные игры состоят только из случайных ходов - ими теория игр не занимается. Если наряду со случайными ходами есть личные ходы, или все ходы личные, то такие игры называются стратегическими.

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

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

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

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

Рис. 1.1. Классификация игр

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

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

4. По количеству стратегий каждого игрока игры подразделяются на конечные (число стратегий каждого игрока конечно) и бесконечные (множество стратегий каждого игрока бесконечно).

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

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

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

7. Если любая возможная партия некоторой игры имеет нулевую сумму выигрышей fi, всех N игроков (), то говорят об игре с нулевой суммой. В противном случае игры называются играми с ненулевой суммой.

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

Конечная парная игра с нулевой суммой называется матричной игрой. Такая игра описывается платежной матрицей, в которой задаются выигрыши первого игрока. Номер строки матрицы соответвует номеру применяемой стратегии первого игрока, столбец - номеру применяемой стратегии второго игрока; на пересечении строки и столбца находится соответствующий выигрыш первого игрока (проигрыш второго игрока).

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

1.3. Примеры игр

Игра 1. Зачет

Пусть игрок 1 - студент, готовящийся к зачету, а игрок 2 - преподаватель, принимающий зачет. Будем считать, что у студента две стратегии: А1- хорошо подготовиться к зачету; А2 - не подготовиться. У преподавателя имеется тоже две стратегии: В1 - поставить зачет; В2 - не поставить зачет. В основу оценки значений выигрышей игроков можно положить, например, следующие соображения, отраженные в матрицах выигрышей

В1

В2

В1

В2

А1

+ (5)

(оценили по заслугам)

- (-6)

(обидно)

А1

+ (0)

(все нормально)

- (-3)

(проявил несправедли вость)

А2

(1)

(удалось словчить)

(0)

(получил по заслугам)

А2

-2

(дал себя обмануть)

- 1

(студент придет еще раз)

Выигрыши студента

Выигрыши преподавателя

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

Задача состоит в определении оптимальных стратегий для студента и для преподавателя.

Игра 2. Морра

Игрой “морра” называется игра любого числа лиц, в которой все игроки одновременно показывают (“выбрасывают”) некоторое число пальцев. Каждой ситуации приписываются выигрыши, которые игроки в условиях этой ситуации получают из “банка”. Например, каждый игрок выигрывает показанное им число пальцев, если все остальные игроки показали другое число; он ничего не выигрывает во все остальных случаях. В соответствии с приведенной классификацией данная игра является стратегической; в общем случае, множественной (в этом случае игра может быть бескоалиционной, коалиционной, и кооперативной) конечной.

В частном случае, когда игра парная - это будет матричная игра (матричная игра всегда является антагонистической).

Пусть два игрока «выбрасывают» одновременно один, два или три пальца. При четной сумме выигрывает первый игрок, при нечетной – второй. Выигрыш равен сумме «выброшенных пальцев». Таким образом, в данном случае каждый из игроков имеет по три стратегии, а матрица выигрышей первого игрока (проигрышей второго) имеет вид:

В1

В2

В3

А1

2

-3

4

А2

-3

4

-5

А3

4

-5

6

где Аi – стратегия первого игрока, заключающаяся в «выбрасывании» i пальцев;

Вj – стратегия второго игрока, заключающаяся в «выбрасывании» j пальцев.

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

Игра 3. Борьба за рынки

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

В0

В1

В2

В3

В4

А0

1

-1

-1

-1

-1

А1

1

1

-1

-1

-1

А2

-1

1

1

-1

-1

А3

-1

-1

1

1

-1

А4

-1

-1

-1

1

1

А5

-1

-1

-1

-1

1

Здесь Аi – стратегия фирмы А, заключающаяся в выделении i условных денежных единиц на защиту первого рынка; Вj – стратегия фирмы В, заключающаяся в выделении j условных денежных единиц на завоевание первого рынка.

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

ТЕСТЫ

(В – Верно, Н – Неверно)

1. Всякая конфликтная ситуация является антагонистической.

2. Всякая антагонистическая ситуация является конфликтной.

3. Цель теории игр - выработка рекомендаций по разумному поведению участников конфликта.

4. Недостатком теории игр является предположение о полной разумности противников.

5. В теории игр предполагается, что не все возможные стратегии противника известны.

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

7. В теории игр нахождение оптимальной стратегии осуществляется по многим критериям.

8. Стратегические игры состоят только из личных ходов.

9. В парной игре число стратегий каждого участника равно двум.

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

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

12. По виду описания игры делятся на игры с полной информацией или игры с неполной информацией.

13. Конечная множественная игра с нулевой суммой называется матричной.

14. Конечная парная игра с нулевой суммой называется биматричной игрой.

(Ответы: 1-Н; 2-В; 3-В; 4-В; 5-Н; 6-Н; 7-Н; 8-Н; 9-Н; 10-В; 11-В; 12-Н; 13-Н; 14-Н.)



Похожие документы:

  1. Ладная тематика рефератов, эссе и курсовых работ студентов по разделам программы

    Эссе
    ... матричного анализа. Неотрицательные матрицы в описании ... математика 1-2 11 ИТОГО: 11 з.е. ... выполнять тесты и ... принцип максимина, понятие гарантирующей стратегии. Седловая точка. Игры в нормальной форме. Определение антагонистической игры, решение игры ...
  2. Учебно-методический комплекс направление подготовки «экономика» - 080100 квалификации «бакалавр» заочная форма обучения

    Документ
    ... , ход, принципы максимина и минимакса, верхняя и нижняя цены игры, седловая точка, оптимальные стратегии, решение матричной игры; Повторите вопросы ...
  3. Учебное пособие Ижевск 2013 удк 338. 45: 519. 876. 2

    Документ
    ... матричной игры Исследование в матричных играх начинается с нахождения её седловой точки в чистых стратегиях. Если матричная игра имеет седловую точку в чистых стратегиях, то ...
  4. Учебное пособие рассмотрено и рекомендовано к публикации на заседании кафедры «Экономика отраслей и рынков». Протокол № от 2012г

    Методические рекомендации
    ... седловую точку. Тогда аi0j0 является значением игры. Легко видеть, что игра имеет седловую точку ... примеры матричных антагонистических игр с нулевой суммой. Задача определения оптимальной смешанной стратегии в антагонистической матричной игре с нулевой ...
  5. Учебно-методический комплекс дисциплины «Экономико-математическое моделирование» по кредитной технологии обучения для студентов специальности 050703 -информационные системы 050508 учет и аудит

    Учебно-методический комплекс
    ... описанием матричного ... Игра называется антагонистической ... тест: 1. В чем заключается балансовый принцип ... игры, минимаксную и максиминную стратегии и оптимальное решение игры, если существует седловая точка. 2) Решите игру ... . 11. Принцип оптимальности ...

Другие похожие документы..