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

Содержание

Пять задач по теории игр для интегрированных уроков — журнал

Автор текста: Алина Мирошникова

В начальной школе интегрированные уроки по требованиям новой программы появятся уже этой осенью. Но в старших классах без интеграции тоже не обойтись. Ведь если знания сортировать по школьным дисциплинам, ученики не смогут овладеть большинством перспективных профессий будущего. Например, биотехнологиями. Как можно интегрировать уроки с помощью игр, рассказал Виталий Шатковский — учитель информатики, победитель конкурса «Учитель года — 2017», руководитель студии программирования в житомирском Центре научно-технического творчества. Вот несколько игр, которые могут быть интересны и полезны школьникам.

Что такое теория игр?

Открытия, отмеченные пятью нобелевскими премиями. Почти 80 лет назад Джон Нейман и Оскар Моргенштерн математически вычислили стратегии игры в покер, где участники могут блефовать, а решения меняются в зависимости от поведения остальных игроков. Впоследствии другой ученый, Джон Нэш (тот самый, о котором снят фильм «Игры разума») проанализировал другие игры при условии, что действия одних игроков влияют на результаты других. Например, до начала партии в шахматы в распоряжении игроков — 400 вариантов только первых ходов. А дальше количество ходов резко возрастает. И современные IT-технологии позволяют обрабатывать даже этот огромный объем данных.

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

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

Правила. Это более зрелищная версия игры «Камень-ножницы-бумага», где по знакам рук определяют победителя.

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

Что касается «силы» персонажей, то самурай убивает дракона. Принцесса покоряет сердце самурая. А дракон съедает принцессу. Выбор игроки демонстрируют одновременно, по команде «раз-два-три».

Стратегии. По статистике, с наибольшей вероятностью (38%) новички выберут дракона, потому что фигура кажется сильной (33% — самурая, 29% — принцессу). Но в классе играют не новички, поэтому подумают на шаг дальше и выберут самурая, который преодолеет дракона. А для того, кто предвидит и этот выбор одноклассников, правильная стратегия — выбрать принцессу.

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

Правила. В городе построили новую короткую дорогу. Сегодня она открывается для проезда. Какую дорогу вы выбираете — старую или новую? Проголосуйте. Например, с помощью бесплатной интернет-платформы Kahoot.

Стратегии. Дорога открылась. Все водители, которые так долго этого ждали, двинутся туда. Возникнет затор. Таким образом, вам стоит выбрать старую дорогу. Впрочем, статистика показывает, что именно так думают 75% людей (это докажут и результаты голосования на Kahoot). Поэтому на самом деле новая дорога почти свободна, следует выбрать ее. Это парадокс Браеса в «переводе» с математического языка на бытовой.

Можно сделать еще один шаг. Сообщить эту стратегию ученикам (как это, собственно, делает Виталий Шатковский) и снова предложить им определиться, куда поехать.

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

Чему учит? Ориентироваться на компетентность и осведомленность остальных игроков, вычислять их стратегии.

Правила. Каждый из игроков выбирает любое целое число от 1 до 100. Затем определяют среднее арифметическое и вычисляют две трети от него (округленно). Тот, кто назвал ближайшее к этому результату — получит приз. Поэтому цель игрока — угадать эти две трети, ориентируясь на гипотезы: что именно загадают в группе.

Стратегии. Если все загадают 100, две трети этого — 67. Поэтому большее число нет смысла называть. Это максимальное число, называя которое, можно рассчитывать на приз. Поскольку все это знают, они выберут именно 67. Поэтому игрок, который это предвидит, должен выбрать две трети от 67, то есть 45.

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

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

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

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

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

Если игрок действует с максимальной выгодой для себя, группа от этого проигрывает. И это — пока еще не решенная проблема многих обществ.

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

Чему учит? Личные интересы противоречат групповым. При этом есть надежда, что группа «как-то без нас обойдется». Но когда проигрывает группа, это вредит каждому из участников.

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

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

Стратегии. Когда гривну пытаются купить за 1, 5 или 10 копеек — выгода очевидна. Поэтому ставки быстро растут. Но когда за гривну начинают предлагать суммы больше ее номинальной стоимости, кажется, понятно: это бессмысленно.

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

Игроки продолжают рассуждать таким образом еще долго. По статистике, победитель покупает банкноту за сумму, в 5-10 раз превышающую стоимость купюры, то есть теряет до 900%.

Чему учит? Стоит вовремя остановиться. Под вопросом оказывается рациональность игроков. Иногда проигрыш малой кровью — более хороший вариант, чем бессмысленная победа.

Поділитися цією статтею

Теория игр: задачи, примеры, решения

“Охота на оленя”. Формализовать игру и составить матрицу выигрышей.
«Игра полковника Блотто»
Алгоритм Куна
В каждой клетке доски 7×7 стоит шашка.
В мешке 64 килограмма семечек.
В одной из трёх комнат сидит принцесса, в другой — тигр, а оставшаяся комната пуста.
В одной тетради было написано 40 утверждений.
В трёх кучках лежит 11, 7 и 6 спичек соответственно.
Дана доска 11×11, в каждой клетке которой стоит по шашке.
Даны две кучки по 2014 камней. Играют двое.
Даны пять одинаковых по виду шаров массами 1000 г, 1001 г, 1002 г, 1004 г и 1007 г,
Два игрока выбирают числа из множества {1, 2, 3}.
Два игрока играют в честную игру до 6 побед.
Двое по очереди кладут пятаки на круглый стол, причем так, чтобы они не накладывались друг на друга.
Двое по очереди ломают шоколадку 6×8.
Двое по очереди ставят королей в клетки доски 9 × 9 так, чтобы короли не били друг друга.
Двое по очереди ставят ладей на шахматную доску так, чтобы ладьи не били друг друга.
До царя Гороха дошла молва, что кто-то из троих богатырей убил Змея Горыныча.
Есть веревочное кольцо. Алиса за него хватается.
Есть два множества X, Y и их декартово произведение.
Есть куча из n камней. Алиса делит ее на 2 непустые части, Боб выбирает одну из них и делит на 2 непустые части.
Есть куча из n камней. Алиса и Боб по очереди берут один или два камня.
Игра начинается с числа 0.
Из трех жителей К, М и Р отдаленного района один является правдолюбцем, другой – лжецом, а третий – хитрецом.
Имеется три кучки камней.
Имеются две кучки конфет: в одной – 20, в другой – 21.
Ладья стоит на поле a1.
На доске написаны 10 единиц и 10 двоек.
На окружности расставлено 20 точек.?
На острове Буяне жители деревни А – рыцари, деревни Б – лжецы, В – хитрец с причудой: они говорят попеременно правду и ложь.
На острове Невезения собрались рыцари, которые всегда говорят правду, и лжецы, которые всегда лгут, причем как рыцарей, так и лжецов было не меньше, чем по двое.
На отрезок [2, 5] наудачу кидают две точки.
На столе лежат две стопки монет: в одной из них 30 монет, а в другой – 20.
На столе лежит 37 спичек.
На тропинке с интервалом в 10 см поставлены 10 отметок.
На футбольный матч пришли любители и фанаты.
Найти оптимальные решения игроков в смешанных стратегиях.
Найти среднее значение f.
Определить верхнюю и нижнюю цену игры.
Перед двумя игроками лежат 5 спичек.
Петя и Вася нашли шкатулку.
Петя и Вася прогуляли экзамен.
Племя людоедов поймало Робинзона Крузо.
Программист Индусов работает с таблицей 2011×2013, в клетках которой произвольным образом расставлены числа 0 и 1.
Пусть события A, B, C удовлетворяют некоторому условию.
Путник послал проводника спросить у человека, работающего в поле, кто он – рыцарь или лжец.
Сидят мальчик и девочка. “Я – мальчик”
Составить биматрицу игры “камень, ножницы, бумага”.
Три жулика, каждый с двумя чемоданами, находятся на одном берегу реки, через которую они хотят переправиться.
Три человека со стиральной машиной хотят переправиться через реку.
Тривиальный покер. Играют два игрока картами от 10 до туза.
У Антона Евгеньевича работает четверо сотрудников: Дима, Женя, Миша и Стёпа.
У Малыша 43 ириски и 15 карамелек.
Числа от 1 до 20 выписаны в строчку.
Эксперты оценили по 20-балльной шкале степень риска проезда на 7 видах транспорта.

Теория игр: концепции решений и стратегическое превосходство (часть 4) | Ковшик Чиламкурти | Nerd For Tech

Вера и лучший ответ, общая рациональность

В этом разделе мы представим идею концепции решения. До сих пор мы делали акцент на представлении выигрыша для различных комбинаций уникальных решений игрока в стратегической среде. Эти представления бесполезны до тех пор, пока мы не применим какую-либо модель для предсказания решения данного игрока с учетом ожидаемых решений, принятых другими рациональными игроками. Мы описываем эту модель как концепции решения.
Например, оптимальность по Парето является концепцией решения. Оптимальность по Парето — это ситуация, которую нельзя изменить так, чтобы улучшить положение любого отдельного человека, не ухудшив положение хотя бы одного человека. Использование этой концепции решения в идеале должно приводить к уникальным действиям.

«строго доминантная стратегия — это стратегия, которая всегда является лучшим, что вы можете сделать, независимо от того, что выберут ваши оппоненты»

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

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

Здесь мы легко можем сделать вывод, что молчание { RS (молчать)} хуже, чем предательство { BE (предательство другого заключенного)} для каждого игрока, независимо от того, что делает его противник. Мы говорим, что такая стратегия предательства {BE} доминирует.

Определение: Пусть sᵢ∈ Sᵢ и s”ᵢ∈ Sᵢ возможные стратегии игрока i. Мы говорим, что в s”ᵢ строго доминирует sᵢ, если для любой возможной комбинации стратегий других игроков, s₋ᵢ∈ S₋ᵢ, выигрыш игрока i от s”ᵢ строго меньше, чем от sᵢ. То есть
vᵢ(sᵢ, s₋ᵢ) > vi(s”ᵢ, s₋ᵢ) для всех s₋ᵢ∈ S₋ᵢ .
Мы будем писать sᵢ >ᵢ s”ᵢ, чтобы обозначить, что s”ᵢ находится под строгим доминированием s₋ᵢ

Мы можем предложить новую концепцию решения, используя приведенное выше определение Концепция строгого доминирования: «строго доминирующая стратегия – это стратегия, которая всегда лучшее, что вы можете сделать, независимо от того, что выберут ваши оппоненты»

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

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

Легко заметить, что не существует строго доминирующей стратегии. для обоих игроков.
Обратите внимание, что если игрок 2 играет « M» , то игрок 1 также должен играть « M» , а если игрок 2 играет « H », то игрок 1 должен играть « H ». Совершенно очевидно, что здесь нет строгого доминирования.
При отсутствии стратегии строгого доминирования мы должны заключить, что концепция решения строгого доминирования может применяться не ко всем видам игр.

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

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

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

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

Если игрок 1 выбирает U, стратегия с наибольшим выигрышем для игрока 2 — L. Если игрок 1 выбирает M, стратегия с наибольшим выигрышем для игрока 2 — R. Анализируя таким образом, можно сделать вывод, что у обоих игроков нет строго доминирующей стратегии. Если внимательно присмотреться, для игрока 2 существует одна строго доминируемая стратегия.0005

В стратегии C строго доминирует R.

В этом новом матричном представлении и M, и D строго доминируются U для игрока 1.

Это привело к следующему уровню исключения, где действия M,D исключаются.

Отсюда довольно просто: Игрок 1 выбирает U, а Игрок 2 выбирает
L, так как v(L) = 3 > v(R)=2.

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

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

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

Определение : Стратегия sᵢ ∈ Sᵢ является лучшим ответом игрока i на стратегии его противников s₋ᵢ ∈ S₋ᵢ, если
vᵢ(sᵢ, s₋ᵢ) ≥ vᵢ(s”ᵢ, s₋ᵢ). ∀s”ᵢ∈ Sᵢ

Предположим, что sᵢ – лучший ответ игрока i на его оппонентов, играющих s’₋ᵢ. Игрок i будет играть sᵢ только тогда, когда он считает, что его противники будут играть s’₋ᵢ. Концепция веры занимает центральное место в анализе стратегического поведения. Строго доминирующая стратегия игрока — это его лучший ответ, независимый от игры его противников.

Пример

Если игрок 1 считает, что игрок 2 выбирает стратегию R, то и U, и D являются лучшими ответами. Таким образом, у игрока может быть более одного лучшего ответа, если он верит в выбор противника.
Теперь мы многое узнали о принятии решений в стратегических условиях. В следующих блогах этой серии мы углубимся в смешанные стратегии идей и другие концепции решений.

Спасибо за ваше время.

Теория игр | Определение, факты и примеры

платежная матрица с седловой точкой

Смотреть все СМИ

Ключевые люди:: Джон фон Нейман Уильям Райкер Томас С. Шеллинг Джон Нэш Ллойд Шепли

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

Просмотреть весь связанный контент →

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

Хотя теория игр может использоваться и использовалась для анализа салонных игр, ее приложения гораздо шире. На самом деле теория игр изначально была разработана американским математиком венгерского происхождения Джоном фон Нейманом и его коллегой из Принстонского университета Оскаром Моргенштерном, американским экономистом немецкого происхождения, для решения экономических задач. В своей книге The Theory of Games and Economic Behavior (1944) фон Нейман и Моргенштерн утверждали, что математика, разработанная для физических наук и описывающая работу бескорыстного характера, была плохой моделью для экономики. Они заметили, что экономика очень похожа на игру, в которой игроки предвидят действия друг друга, и поэтому требует нового вида математики, которую они назвали теорией игр. Дальнейшее развитие теория игр получила в XIX в.

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

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

Классификация игр

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

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

Оформите подписку Britannica Premium и получите доступ к эксклюзивному контенту. Подписаться сейчас

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

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

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

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

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

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

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

Игры для одного человека

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