26.6. Кооперативные игры
Пусть теперь в игре с ненулевой суммой игрокам разрешается обсуждать перед игрой свои стратегии и договариваться о совместных действиях. Такая биматричная игра называется кооперативной игрой.
Пусть S – множество точек на координатной плоскости cA,cB определяет возможные выигрыши игроков. При этом известно, что S является выпуклым, замкнутым и ограниченным множеством. Нанесем на эту координатную плоскость точку T(cA*, cB*). Координаты точки равны выигрышам игроков в равновесной ситуации, которые игроки могут получить, не вступая в переговоры друг с другом.
Точку T часто называют точкой угрозы. В этой точке, как показано ранее, каждый из игроков, действуя в одиночку, не может увеличить свой выигрыш.
cB
парето-оптимальное
множество
переговорное
множество
cB* T точка решения Нэша
S
0 CA* cA Рис.22.1. Множество выигрышей игроков
Ясно, что наибольшие возможные выигрыши игроков находятся на верхней правой части границы множества S. Эту часть границы обычно называют парето-оптимальным множеством, а каждую точку на ней – парето-оптимальной ситуацией.
В любой такой ситуации игроки, даже действуя совместно, не могут увеличить выигрыш одного из них, не уменьшая выигрыш другого. Поэтому целью вступления игроков в переговоры должно быть достижение парето-оптимальной ситуации. В этом случае есть смысл вести переговоры о достижении парето-оптимальной ситуации, только находящейся выше горизонтальной линии cB = cB* и правее вертикальной линии cA = cA*. Действительно, значения выигрышей cA* и cB* достигаются и при действиях в одиночку. Поэтому часть парето-оптимального множества, содержащая такие ситуации называется переговорным множеством.
Точкой решения Нэша называется точка, в которой достигается максимум произведения
(cA – cA*)(cB – cB*),
где (cA – cA* ) и (cB – cB* ) – превышения выигрышей игроков над выигрышами, которые могут быть получены без вступления в переговоры.
Можно доказать, что если множество S выпукло, замкнуто и ограничено, то точка решения Нэша существует и притом единственная.
Пример. Найти точку решения Нэша для «дилеммы узников».
Решение. Для нахождения точки решения Нэша нужно найти значения вероятностей p и q, лежащие на отрезке [0, 1], при которых достигается наибольшее значение функции N(p, q)
N(p, q) = (cA(p, q) – c*A) (cB(p, q) – c*B).
Подставив в выражения для cA(p, q) и cB(p, q) элементы матриц А и В, получаем:
cA(p, q) = -pq – 9p(1 – q) – 6(1 – p)(1 – q) = -6 – 3p + 6q + 2 pq;
cB(p, q) = -pq – 9p(1 – q) – 6(1 – p)(1 – q) = -6 – 3q + 6p + 2 pq.
Так как c*A = c*B = -6, то
N(p, q) = (– 3p + 6q + 2 pq)( – 3q + 6p + 2 pq) =
= 45pq –18(p2 + q2) + 6pq(p+q) + 4p2q2.
Используя элементы теории экстремума функции двух переменных, можно найти наибольшее значение функции N(p, q) на квадрате 0 p 1; 0 q 1. Однако из условия симметричности задачи относительно игроков А и В следует, что в единственной точке решения Нэша с наибольшим значением N(p, q) p = q. Тогда
N(p) = 9p2 + 12p3 + 4p4.
Очевидно, что эта функция является возрастающей на отрезке [0, 1], что следует хотя бы из положительности производной во внутренних точках отрезка. Поэтому N(p) достигает наибольшего значения при p = 1, а следовательно точкой решения Нэша является точка, в которой p = 1, q = 1.
Итак, в кооперативной игре «дилемма узников» обоим игрокам следует применять стратегии A1 и B1, т.е. не сознаваться в совместном совершении преступления. Тогда выигрыш каждого из них будет равен -1, что больше, чем выигрыш -6 в точке равновесия биматричной игры без согласования стратегий игроков.