Кооперативные биматричные игры, оптимальность по Парето, переговорное множество, арбитражные схемы Нэша, функция Нэша.

⇐ ПредыдущаяСтр 11 из 11

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

Теорема существования равновесий. В любой биматричной игре существует хотя бы одно равновесие Нэша.

Критерий равновесия. Стратегии игроков p * и q * образуют равновесие Нэша тогда и только тогда, когда при условии использования первым игроком стратегии p * любая чистая стратегия второго игрока, соответствующая приносит второму игроку один и тот же выигрыш m, а любая чистая стратегия второго игрока, соответствующая , приносит второму игроку выигрыш, не больший m, а при условии использования вторым игроком стратегии q * любая чистая стратегия первого игрока, соответствующая , приносит второму игроку один и тот же выигрыш n, а любая чистая стратегия второго игрока, соответствующая приносит второму игроку выигрыш, не больший n.

Максиминные смешанные стратегии первого и второго игроков обеспечивают им гарантированные выигрыши

α = max min β = max min

соответственно вне зависимости от поведения противника.

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

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

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

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

Рассмотрим биматричную игру, в которой выигрыши первого и второго игроков заданы матрицами ) и )

Пусть смешанные стратегии игроков. Так как

множество всех возможных вариантов пар выигрышей

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

При этом точки доминирует точку , если

или

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

Множество точек, оптимальных по Парето (т. е. не доминируемых другими), описывается так:

Если выбрать из множества точек, оптимальных по Парето, те точки, в которых выигрыши первого и второго игроков окажутся не меньше их максиминных выигрышей a и b, то получится переговорное множество

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

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

Реализация алгоритма Нэша предполагает решение задачи математического программирования

)

Целевая функция этой задачи называется функцией Нэша, а оптимальное решение задачи— решением Нэша.

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

⇐ Предыдущая 2 3 4 5 6 7 8 9 1011