Классификация игр.
Основы математического моделирования социально-экономических процессов
Игры с природой выходят за рамки классической теории игр, поскольку моделируемые ими ситуации хотя и предполагают неопределенность, но отличаются отсутствием конфликтности: а именно, один из игроков (природа) оказывается нейтральным, так как он не стремится извлечь максимальную выгоду для себя из взаимодействия с другими игроками. В то же время если бы один или несколько игроков знали полностью… Читать ещё >
Классификация игр. Основы математического моделирования социально-экономических процессов (реферат, курсовая, диплом, контрольная)
Игры классифицируются по различным критериям, например по количеству игроков, количеству стратегий, характеру взаимодействия игроков, характеру выигрыша, виду платежных функций, состоянию информации, а также на основе сочетания этих и других критериев. Конкретизация элементов, определяющих игру (игроки, стратегии, платежи и пр.), и связей между ними определяет многочисленные и разнообразные классы игр (табл. 3.2).
В зависимости от количества игроков, выбирающих стратегию, различают игры двух и п игроков. Игры двух игроков, как правило, вызывают меньше принципиальных и технических трудностей получения решения, чем игры п игроков. Причем наибольшую сложность для теоретико-игрового Классификация игр
Класс ифи ка ц и он н ы й признак. | Виды игр |
Число игроков. | Игры двух лиц Игры п лиц, п > 2. |
Возможность сотрудничества. | Некооперативные (бескоалиционные) Кооперативные (коалиционные). |
Форма представления игры. | Игры в нормальной форме (задаются в виде таблицы или матрицы) Игры в развернутой форме (задаются в виде графа или дерева решений) Игры с непрерывными стратегиями (задаются в виде системы платежных функций). |
Число и определенность ходов. | Статические (однократные) Повторяющиеся (статическая игра повторяется конечное или бесконечное число раз) Динамичные (многоходовые игры, в которых последовательность ходов может быть заранее определена, а может быть неизвестна). |
Степень конфликтности. | Антагонистические игры (игра двух игроков, в которой выигрыши одного игрока равны проигрышам другого) Неантагонистические игры. |
Характер распределения платежей. | Игры с нулевой суммой (сумма платежей игроков во всех стратегических ситуациях равна нулю) Игры с постоянной суммой (сумма платежей игроков во всех стратегических ситуациях равна постоянному значению) Игры с переменной суммой (сумма платежей игроков в различных стратегических ситуациях различна). |
Уровень и качество информированности. | Игры с полной информацией Игры с неполной информацией Игры с совершенной информацией Игры с несовершенной информацией Игры с асимметричной информацией. |
Статус игроков. | Игры равноправных участников Иерархические игры. |
моделирования обычно составляет переход от ситуаций с двумя участниками к ситуациям с тремя участниками, тогда как последующее наращивание числа игроков представляет относительно меньшие трудности. Это связано с тем, что, во-первых, механизм решения игры при переходе от двух к большему числу игроков не всегда очевиден, но если этот механизм найден, то при дальнейшем росте числа игроков возрастают лишь технические трудности вычислений; во-вторых, когда число игроков (возможно, с противоречивыми интересами) больше двух, возникает возможность образования коалиции, но, определив принцип анализа коалиционных взаимодействий при переходе от двух игроков к трем, в дальнейшем можно использовать этот же подход, например, при переходе от четырех к пяти игрокам, который лишь увеличивает число возможных коалиций.
По количеству стратегий игры делятся на конечные и бесконечные. Если в игре все игроки имеют конечное число возможных стратегий, то она называется конечной. Если же хотя бы один из игроков имеет бесконечное количество возможных стратегий, игра называется бесконечной.
По характеру взаимодействия игроков игры делятся на бескоалиционные (некооперативные), в которых игроки не имеют права вступать в соглашения, образовывать коалиции и координировать свои действия, и коалиционные (кооперативные), в которых игроки могут вступать в коалиции. Иногда понятие «кооперативная игра» определяется в более узком смысле — как коалиционная игра, в которой коалиции заранее определены.
Это настолько важный классификационный признак, что на его основе вся теория игр делится на две части: теорию бескоалиционных игр и теорию кооперативных игр. В теории бескоалиционных игр основной единицей анализа являются стратегии отдельных игроков, каждый из которых стремится получить наилучший собственный результат. При этом даже если игроки выбирают кооперативные стратегии в привычном смысле этого слова (например, одинаковые или каким-то образом скоординированные), это происходит потому, что подобное поведение оказывается в интересах каждого из игроков. В строгом смысле термин «кооперация», как он рассматривается в теории кооперативных игр, означает вхождение нескольких игроков в определенную коалицию, и задачей теории кооперативных игр является не анализ индивидуальных стратегий игроков (что они должны делать), а анализ того, что может получить каждая коалиция и как полученный выигрыш должен быть оптимально разделен между ее участниками. Поэтому бескоалиционные игры также называются стратегическими, а кооперативные — нестратегическими играми. Но подобная классификация не должна рассматриваться как взаимоисключающая. Это, по сути, два взгляда на одну проблему, которые способны своим взаимодополнением улучшить качество ее анализа.
По способу представления игры обычно разделяют на игры в нормальной форме (стратегические игры), задаваемые в виде таблицы или матрицы, игры в развернутой форме (позиционные игры), задаваемые в виде дерева решения (графов), и игры с непрерывными стратегиями (задаются в виде системы платежных (целевых) функций игроков).
В игре в нормальной форме игроки одновременно и независимо друг от друга выбирают из множеств Si свои стратегии. Профиль стратегий s = = (sv s2, …, sn) всех игроков определяет стратегическую ситуацию в игре. Каждый игрок i получает платеж, определяемый правилами игры для стратегической ситуации, в которой оказались игроки, и игра завершается.
Игра в нормальной форме задается множеством игроков; множеством их стратегий; множеством платежей, или платежной функцией каждого игрока, определенной на множестве ситуаций и отображающей его во множество действительных чисел. Нормальная форма игры описывает статическое взаимодействие игроков, не предусматривая возможности последовательных ходов, накопления информации о действиях соперника и повторяющегося взаимодействия. Для моделирования этих аспектов используется развернутая форма игры, предполагающая, что известны: а) порядок ходов;
б) альтернативные выборы, доступные игроку; в) информация, доступная игроку при каждом выборе; г) платежи игроков в результате того или иного выбора.
Игра в развернутой форме представляется с использованием графа (дерева игры, дерева решенийследующим образом. Вершины дерева представляют собой состояния (позиции), в которых может оказываться игра, ребра — ходы или действия, которые могут использовать игроки. Предполагается, что в каждой позиции может совершать ход только один игрок. Выделяется три вида позиций в игре:
- • начальная, не имеющая входящих ребер;
- • промежуточные, имеющие входящие и выходящие ребра;
- • терминальные, имеющие только входящие ребра.
Для каждой вершины дерева, соответствующей нетерминальной (начальной или промежуточной) позиции, задан игрок, делающий в ней ход, и определено множество ходов этого игрока (ребер, выходящих из этой вершины). Для каждой вершины, соответствующей терминальной позиции, определены платежи всех игроков.
Игра начинается из начальной позиции и предполагает следующий порядок разыгрывания. В любой нетерминальной позиции игрок, имеющий в ней право хода, выбирает ход, в результате чего игра попадает в следующую позицию, в которую входит ребро, соответствующее сделанному ходу. Если эта позиция является нетерминальной, то игра продолжается. Если игра попадает в терминальную позицию, то игроки получают определенные платежи, и игра завершается.
Проиллюстрируем две формы представления игры на примере принятия решений о запуске проекта нового самолета компаниями Airbus и Boeing (см. параграф 1.4). В формализованной модели у каждой из компаний есть две стратегии: стратегия вступления (in) и невступления в конкурентную борьбу (out). В нормальной форме эта игра может быть представлена в виде таблицы (матрицы).
(-3; -3). | (0,3: -1). |
(0; 0). | (0; 0). |
Представление игры в нормальной форме обычно отражает синхронность игры. Это понятие не означает одновременность событий, а указывает на то, что выбор стратегии игроком осуществляется в условиях отсутствия информации о выборе стратегии соперником. При развернутой форме также можно отразить синхронность игры. Если игра, представленная в развернутой форме, совмещает одновременные и последовательные действия, синхронность выражается через овальное пространство (информационное поле или информационное множество), означающее, что игрок не знает, какое из двух или более действий другого игрока реально произошло. При отсутствии этого пространства игровая ситуация приобретает иной характер: сначала решение должен бы принимать один игрок, а другой мог бы делать это вслед за ним. В развернутой форме игра представлена на рис. 3.1.
Рассмотрим понятие синхронности на примере, который характеризует различие хронологического и игрового времени. Во всем мире дети играют[1]
Рис. 3.1. Пример представления игры в развернутой форме.
в игру, которая называется «Камень, ножницы, бумага». Представьте, что есть некий арбитр, который просит одного игрока показать один из предметов, пока другой игрок отсутствует. Через какое-то время, например на следующий день, арбитр просит сделать выбор другого игрока, не сообщая ему о выборе первого. В результате арбитр выносит решение о том, какой из игроков выиграл. В данной ситуации сохраняется синхронность игры при отсутствии одновременности.
Если в игре решения принимаются игроками одновременно (синхронно), в условиях неведения о стратегиях, выбранных другими игроками, и после взаимодействия игроков на основе выбранных стратегий игра заканчивается, то такие игры называются статическими (одновременными, синхронными). В отличие от статических игр, состоящих фактически из одного хода, динамические игры допускают последовательность ходов, причем игроки могут принимать решение в зависимости от уже сделанных ходов других игроков. Статические игры, как правило, представляются в нормальной форме, динамические — в развернутой (позиционной) форме, поэтому они также называются позиционными играми.
По характеру распределения платежей между игроками игры делятся на игры с нулевой или постоянной суммой и игры с переменной суммой. В играх первого вида общий платеж всех игроков не меняется, а перераспределяется между игроками; сумма платежей всех игроков равна нулю (игры с нулевой суммой) или некоторому постоянному значению (игры с постоянной суммой). Игры с постоянной суммой могут быть приведены к играм с нулевой суммой. Это значит, что одни игроки получают положительные платежи, а другие — отрицательные, так что сумма платежей всех игроков равна нулю. В таких играх выигрыш одних игроков достигается за счет проигрыша других, и таким образом общая сумма выигрышей и потерь постоянна и равняется нулю.
В случае двух игроков игры с нулевой суммой моделируют крайний случай конфликтных ситуаций — антагонистические конфликты, в которых интересы игроков прямо противоположны, поэтому они также называются антагонистическими играми, или играми с противоположными интересами. В антагонистических играх (покер, крестики-нолики, шахматы и т. п.) выигрыш одного из игроков в точности равен проигрышу другого.
Антагонистическая игра, в которой множества чистых стратегий каждого игрока конечны, называется матричной игрой из-за определенной специфичности ее представления. В такой игре платеж одного игрока задается в виде матрицы (строка матрицы соответствует номеру чистой стратегии первого игрока, а столбец — номеру чистой стратегии второго игрока; на пересечении строки и столбца матрицы находится платеж первого игрока, соответствующий применяемым стратегиям). Платеж другого игрока задавать нет необходимости, так как он равен платежу первого игрока, взятому с обратным знаком. Примером матричной игры является прототипная игра «Орел и решка»:
Для матричных игр доказано, что любая из них имеет решение, и оно может быть легко найдено путем сведения игры к задаче линейного программирования. Несмотря на то что это самые простые игры с точки зрения техники решения, они способствовали развитию как теории игр, так и направлений экономической теории, в том числе теории полезности и теории равновесия.
Игры с переменной суммой (иногда называются играми с ненулевой суммой) моделируют ситуации, в которых конфликт присутствует, но интересы могут частично совпадать (а в некоторых случаях — совпадать полностью). Примерами таких игр являются игры «Цыпленок», моделирующая балансирование на грани острого конфликта, «Дилемма узников», моделирующая проблемы координированного действия, и различные варианты координационных игр. В таких играх сочетаются мотивы конфликта и сотрудничества: при выборе стратегии сотрудничества все игроки оказываются в выигрыше, однако ни у кого нет уверенности в том, что все игроки выберут путь сотрудничества.
Игры двух игроков с переменной суммой, в которой платежи каждого игрока задаются матрицами, называются биматричными играми. В каждой матрице строка соответствует стратегии первого игрока, столбец — стратегии второго игрока. Соответственно на пересечении строки и столбца первой матрицы находится платеж первого игрока, а на пересечении строки и столбца второй матрицы — платеж второго игрока. Все рассмотренные выше прототипные игры, за исключением игры «Орел и решка», являются биматричными играми. К примеру, игра «Семейный спор» представляется двумя платежными матрицами.
Для биматричных игр также разработана теория оптимального поведения игроков, однако решать такие игры сложнее, чем матричные.
В теории игр существует такое понятие, как игра с природой — игра, в которой в качестве одного или нескольких игроков выступает случайный, неучтенный или неизвестный фактор (или комплекс факторов), называемый «природа» (погодные условия, стихийно складывающийся рыночный спрос на товар и т. д.). Под природой понимается вся совокупность внешних обстоятельств, в которых приходится принимать решение, но которые частично или полностью не известны ЛПР.
В игре с природой частично нарушаются принципы рациональности и общего знания, так как мы не можем считать, что природа действует по тем же принципам и руководствуется теми же критериями, что, например, и фермер, принимающий решение об оптимальной структуре посевов культур в условиях неопределенности погодных условий. Хотя законы изменения случайного фактора, рассматриваемого в качестве игрока, могут быть неизвестны другим игрокам, но если известны возможные состояния внешней среды, которые условно можно считать стратегиями природы, и известны платежи игроков, определяемые в том числе этими стратегиями, то игра с природой для некоторых классов игр (например, матричных) может решаться по тем же принципам, что и игра, в которой полностью выполняется принцип рациональности. В играх с природой оптимальную смешанную стратегию природы можно принимать как наименее благоприятное распределение вероятностей ее состояний.
Игры с природой выходят за рамки классической теории игр, поскольку моделируемые ими ситуации хотя и предполагают неопределенность, но отличаются отсутствием конфликтности: а именно, один из игроков (природа) оказывается нейтральным, так как он не стремится извлечь максимальную выгоду для себя из взаимодействия с другими игроками. В то же время если бы один или несколько игроков знали полностью законы, по которым действует природа, они могли бы извлечь из этого максимальную выгоду для себя. Но в отсутствие такого знания игроки могут и должны руководствоваться также другими принципами и критериями принятия решений, а не только теми, что используются при принятии решений в предположении конфликтности и противодействия со стороны других игроков.
В играх с природой, как и в играх нескольких лиц, результаты игры для всех игроков зависят не только от их собственных стратегий, но и от неконтролируемых переменных. Но в случае игр с природой эти неконтролируемые переменные отражают неизвестные или случайные обстоятельства, которые нельзя считать обусловленными желанием получить тот или иной результат.
Хотя формы представления игр с природой часто аналогичны классическим матричным играм, методы и критерии принятия решений в играх с природой являются гораздо более многочисленными и гибкими, чем в теории антагонистических игр, а также отличаются тем, что соответствующие математические модели в гораздо большей степени включают в себя аппарат теории вероятностей и математической статистики, с помощью которых и моделируются действия всех невыявленных игроков, факторов и обстоятельств. Поэтому игры с природой либо считаются предметом раздела математики, который называется теорией статистических решенийу либо относятся к особому классу игр, называемых статистическими играми.
В связи с неоднозначностью отнесения игр с природой к теории игр методы анализа этого класса игр вынесены в приложение данной книги (см. приложение П1), но, следуя исторической традиции, также рассмотрены в контексте анализа антагонистических игр.
По полноте информации выделяются игры с полной информацией, в которых каждый игрок знает все возможные стратегии всех игроков и положение всех участников игры в любой момент времени (пример — шахматы), и игры с неполной информацией (пример — покер), где игрокам частично неизвестно, какими ресурсами располагают и какой стратегией пользуются другие участники игры, или же один или несколько игроков не знают, какой ход сделала природа, т. е. игры с неполной информацией — это игры, в которых часть игровой информации скрыта от одного или нескольких игроков.
В игре с полной информацией отсутствует элемент неопределенности в наличии возможных стратегий игроков, хотя и остается неопределенность, связанная с выбором одной из возможных стратегий. В таких играх порядок ходов определен правилами и не зависит от таких параметров, как скорость реакции игроков (т.е. очередной ход делает тот, кто должен его сделать по правилам, а не тот, кто первым успел его сделать). В любой момент игры все игроки имеют полную информацию о состоянии игры, т. е. о позиции и всех возможных ходах любого из игроков. Другими словами, каждый игрок знает точно, в каком месте дерева игры он находится, и если в игре есть игрок «природа», все игроки наблюдают его ходы.
К играм с неполной информацией можно отнести и игры с асимметричной информацией, в которых игроки владеют разным объемом информации. Например, одна фирма знает, будет ли спрос на ее продукцию высоким или низким (с определенной вероятностью), а ее конкурент — нет. Разумеется, стратегии фирм будут различаться в зависимости от того, осведомлены ли эти конкурирующие фирмы об информации, доступной конкуренту, в том числе о знании конкурентов о степени взаимной осведомленности (полноты общего знания).
В играх с полной информацией анализировать стратегии игроков проще, чем в играх с неполной информацией, но игры этого класса более адекватно описывают реальные конфликты, в том числе глобального масштаба — войны, экологические катастрофы, экономические кризисы.
В современной литературе чаще используются термины «игры с совершенной информацией» и «игры с несовершенной информацией», отражающие нс только уровень полноты, но и достоверности информации, имеющейся у игроков.
Если ни в каких аспектах игры с полной информацией (правилах, возможности или очередности ходов, определении момента завершения игры или результата и др.) не участвует элемент случайности, такая игра называется детерминированной. К таким играм относится большинство настольных игр (шахматы, шашки, крестики-нолики и т. п.). Для любой детерминированной игры теоретически можно просчитать все дерево возможных ходов игроков и определить последовательность ходов, которая приведет к выигрышу или гарантированной ничьей, но на практике дерево решений слишком велико, чтобы его можно было построить и проанализировать за приемлемое время.
В теории игр выделяются так называемые иерархические игры, в которых игроки неравноправны по статусу. Это могут быть, например, «центры», начинающие игру или даже определяющие ее правила, и «агенты», принимающие свои решения, учитывая решение «центров». В иерархических играх существует фиксированный порядок ходов — сначала ход делает «центр», имеющий право первого хода, затем свои стратегии выбирают «агенты». С этой точки зрения иерархические игры могут служить достаточно адекватным инструментом описания задач управления организационными системами.
Для иллюстрации выделенных классификационных признаков охарактеризуем с их помощью такую известную игру, как шахматы. Это бескоалиционная игра двух игроков («белые» и «черные») с полной информацией. Шахматы — антагонистическая игра, так как в ней выигрыш одного игрока равен проигрышу другого (выигранной партии можно сопоставить значение 1, ничьей — 0, проигранной—1), т. е. платежи игроков отличаются лишь знаком. Игра предполагает последовательный выбор ходов, т. е. принадлежит к классу динамических игр, и т. д.
- [1] Примеры дерева решений были приведены в параграфе 1.4. Но в представленных тампримерах вероятности различных исходов были известны ЛПР. В теоретико-игровых моделях такая вероятность во многих случаях не задается.