Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Формальный аппарат теории игр




Теория игр впервые была систематически изложена Дж. Фон Нейманом и О. Моргенштерном в 1944 г., хотя отдельные результаты были опубликованы еще в 20-х гг. прошлого века. Работа Неймана и Моргенштерна содержала главным образом экономические примеры, поскольку экономическому конфликту легче всего придать численную форму. Во время второй мировой войны и сразу после нее теория игр применялась как аппарат для исследования стратегических военных решений. Затем главное внимание снова стало уделяться экономическим проблемам.

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

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

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

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

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

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

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

Элементарные выборы в конечных играх называются чистыми стратегиями. Смешанной стратегией игрока называется сочетание его чистых стратегий, применяемых в серии игр «случайным образом» (игрок сохраняет в тайне конкретные решения для каждого акта игры) с заранее определенной вероятностью [3]. Активными стратегиями игрока называются его чистые стратегии, используемые им с ненулевой вероятностью.

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

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

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

Имеет место соотношение между верхней и нижней ценами для любой матричной игры: a £ b(доказывается «от противного»).

Ценой игры n называется средняя (в серии игровых актов) величина платежа, привлекательная (т. е. a £ n £ b) и гарантированная для обоих игроков. Решением игры называется совокупность стратегий (чистых или смешанных), позволяющая каждому игроку гарантировать результат игры (величину среднего по серии игровых актов платежа) не хуже, чем значение цены игры n. Отсюда, в силу способности каждого игрока препятствовать отклонению средней величины платежа от равновесного значения, легко сделать вывод о том, что средняя величина платежа приближается к значению n при увеличении количества игровых актов. В случае если n = 0, игра называется справедливой.

Основная теорема теории игр (теорема Неймана): всякая конечная игра с нулевой суммой имеет решение, возможно, в области смешанных стратегий.

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

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

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

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

Множество стратегий, не доминирующих друг друга, называется множеством Парето.

Аффинное преобразование платежной матрицы – это преобразование всех элементов платежной матрицы по правилу a'ij = kaij + D, n' = k n + D. Оно не меняет решения игры. Это означает, что для задания игры безразлично, в каких единицах измеряются выигрыши (например, в рублях или долларах); прибавление (вычитание) некоторой фиксированной суммы к каждому платежу изменит на такую же сумму любой выигрыш (проигрыш) каждого из игроков, не меняя решения игры.

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

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

 




Поделиться с друзьями:


Дата добавления: 2014-12-27; Просмотров: 617; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.012 сек.