скачать
14.0207 Антагонистические игры Теория исследования операций Определение. Теория игр – теория принятия решений в условиях конфликта и/или неопределенности. Конфликт Терминология Нормативный аспект Контрпример: теория фон Неймана Рациональность Теория исследования операций. Исследование операций – построение, разработка и приложения математических моделей принятия оптимальных решений Системный анализ – дисциплина, занимающаяся проблемами принятия решений в условиях, когда выбор альтернативы требует анализа сложной информации различной физической природы Кибернетика – наука об управлении, связи и переработке информации (буквально: искусство управления рулем) Теория автоматического регулирования Теория вероятностей Определение. Операция – совокупность действий, мероприятий, направленных на достижение некоторой цели. Определение. Совокупность тех лиц или автоматов, которые стремятся в данной операции к поставленной цели, называется оперирующей стороной. Принцип Гермейера. Исследователь операции входит в оперирующую сторону и проводит исследование в его интересах Уточнение Пример – компьютеризация специализированных сельскохозяйственных предприятий Определение. Модель операции в нормальной форме <U,A,g>, где U – множество стратегий оперирующей стороны, A – множество неопределенных факторов, g:UA – критерий оперирующей стороны. Управление Контрпример: Гордиев узел Неопределенность Критерий Контрпример: нетранзитивное предпочтение Контрпример: парадокс кучи Второй принцип Гермейера. В каждой операции должен быть только один критерий. Неопределенность может возникать по различным причинам: Природа Противник Неопределенность цели Стохастика Третий принцип Гермейера. Исследователь операций должен быть осторожен. Четвертый принцип Гермейера. Исследователь операции должен учитывать всю информацию, которая будет у оперирующей стороны в момент принятия решения ^ Сужать множество неопределенных факторов может оперирующая сторона, но не исследователь операций. Пример: формирование гипотез при испытании самолетов ^ Определение. Антагонистической игрой в нормальной форме называется набор <U,V,g>, где U и V – множества, а функция g:UVR. Элементы множество U и V интерпретируются как стратегии (управления) первого и второго игрока соответственно. Цель первого игрока описывается как стремление к увеличению значения функции выигрыша g, а цель второго игрока – как стремление к его уменьшению. Пример: игра «орел–решка» Пример: Автопилот Пример: Игра «крестики–нолики» Агрегирование Матричные игры ^ максимальный гарантированный результат за первого игрока за второго игрока Пример: игра «орел–решка» Лемма. Для любой функции g:UVR выполняется неравенство . Доказательство. Очевидно, для любых управлений u и v выполняются неравенства  или . Правая часть от u не зависит, поэтому в силу произвольности u выполняется неравенство  Левая часть последнего неравенства – это просто число, значит, в силу произвольности v, имеет место неравенство , что и требовалось доказать.
Пример: каре Доказательство ^ Мотивация Простейший случай Ключевой случай Природная неопределенность «Принцип бутерброда» Определение 1. Игра <U,V,g> имеет седловую точку, если существуют число p и стратегии u0U и v0V такие, что . Число p называют ценой игры, а пару (u0,v0) – седловой точкой. Определение 2. Игра <U,V,g> имеет седловую точку, если . Если u0 реализует максимум в правой части равенства, а v0 реализует минимум в левой части, то пару (u0,v0) называют седловой точкой, а общее значение левой и правой частей – ценой игры. ^ Определения 1 и 2 эквивалентны. Доказательство. Пусть выполнено определение 1. Из равенства следует, что , а из равенства получается неравенство , то есть . В силу предыдущей леммы выполняется и обратное неравенство, а значит, на самом деле имеет место равенство . Пусть выполнено определение 2. Обозначим . По определению точки u0 имеем , а из определения точки v0 получаем . Лемма доказана. Существование (примеры) ^ Определение. Если U и V – компактные выпуклые подмножества конечномерных евклидовых пространств, а функция g:UVR непрерывна, вогнута по u при любом фиксированном v и выпукла по v при любом фиксированном u, то игра Г=<U,V,g> называется выпуклой. Терема (С. Какутани, 1941). В выпуклой игре существует седловая точка. Доказательство. Рассмотрим сначала «типичный» частный случай, когда функция g строго вогнута по u при любом фиксированном v и строго выпукла по v при любом фиксированном u. Тогда при каждом v максимум достигается в единственной точке, то есть корректно определена функция . Аналогично, единственным образом определена функция . В силу следствия из леммы о замкнутом графике (см. лекцию 1) обе эти функции непрерывны. Рассмотрим отображение F(u,v)=(f1(v),f2(u)). Оно непрерывно и отображает выпуклый компакт :UV в себя. В силу теоремы Брауэра это отображение имеет неподвижную точку, то есть существует решение (u0,v0) системы уравнений  Но тогда  то есть (u0,v0) – седловая точка. Вернемся к рассмотрению общего случая. Наряду с игрой Г рассмотрим игру Г=<U,V,g>, где функция g определена равенством . При любом >0, функция g непрерывна, строго вогнута по u при любом фиксированном v и строго выпукла по v при любом фиксированном u. Как только что доказано, в игре Г существует седловая точка (u,v). Произвольным образом зададим сходящуюся к нулю последовательность положительных чисел (1), (2),…,(n)… Рассмотрим последовательность игр и соответствующую последовательность седловых точек В силу компактности множества UV эта последовательность имеет сходящуюся подпоследовательность. Не ограничивая общности, можно считать, что сама последовательность сходится к некоторой точке (u0,v0). Покажем, что (u0,v0) есть седловая точка в игре Г. Пусть u и v – произвольные управления первого и второго игроков соответственно. Так как – седловая точка в игре , то для любого n выполняются неравенства  Переходя в этих неравенствах к пределу при n, получим  что в силу произвольности u и v завершает доказательство теоремы
Пример. Вычислить и , где U=V=[0,1] и g(u,v)=–u2+v3+uv2–4v. Решение. Вычислим . Преобразуем g(u,v)=–u2+v3+uv2–4v=–(u2–uv2+v4/4)+ v4/4+v3–4v=–(u–v2/2)2+v4/4+v3–4v. Теперь видно, что и достигается при u=v2/2. Остается найти максимум функции v4/4+v3–4v на отрезке [0,1]. Ее производная v3+3v2–4=(v3–v2)+4(v2–1)=(v–1)(v2+4v+4)= (v–1)(v+2)2 на этом отрезке имеет единственный корень v=1. Поэтому . Попытка аналогичным образом вычислить наталкивается на серьезные аналитические трудности. Поэтому целесообразно заметить, что рассматриваемая игра – выпуклая, и значит . ^ Лемма. Если a – положительное, а b – произвольное число, то множества седловых точек в играх <U,V,g> и <U,V,ag+b> совпадают. Доказательство. Данная лемма – частный случай следующей. Лемма. Если f – возрастающая функция, то множества седловых точек в играх <U,V,g> и <U,V,fg> совпадают. Доказательство. Пусть (u0,v0) – седловая точка в игре <U,V,g>. Это значит, что для любых u и v выполняются неравенства g(u,v0)g(u0,v0)g(u0,v). В силу монотонности функции f отсюда следуют неравенства f(g(u,v0))f(g(u0,v0))f(g(u0,v)). В силу произвольности u и v это означает, что (u0,v0) – седловая точка в игре <U,V,fg>. Обратно, пусть (u0,v0) – седловая точка в игре <U,V,fg>. Тогда для любых u и v выполняются неравенства f(g(u,v0))f(g(u0,v0))f(g(u0,v)). И снова с помощью монотонности функции f получаем неравенства g(u,v0)g(u0,v0)g(u0,v), откуда следует, что (u0,v0) – седловая точка в игре <U,V,g>.
Пример: игра чет-нечет и ее эквивалентность игре орел-решка Факторизация Определение. Антагонистическая игра называется симметрической, если U=V и g(u,v)=–g(v,u). Лемма. Значение симметрической игры равно нулю (если оно существует). Доказательство. Преобразуем с учетом симметрии игры: . Отсюда и следует, что p=0.
^ Лемма. Если (u1,v1) и (u2,v2) – седловые точки некоторой игры, то (u1,v2) и (u2,v1) – тоже седловые точки этой игры. Доказательство. Так как (u1,v1) – седловая точка, выполняются неравенства g(u2,v1)g(u1,v1)g(u1,v2), а так как (u2,v2) – седловая точка, имеем g(u1,v2)g(u2,v2)g(u2,v1). Сравнивая, получим g(u2,v1)g(u1,v1)g(u1,v2) g(u2,v2)g(u2,v1). Значит, на самом деле все эти неравенства обращаются в равенства: g(u2,v1)=g(u1,v1)=g(u1,v2) =g(u2,v2)=g(u2,v1). Но тогда и , то есть точка (u2,v1) – седловая. Аналогично доказывается, что и точка (u1,v2) является седловой. Следствие. Пусть S1 – множество таких точек u0U, для которых найдется такое v0V, что точка (u0,v0) является седловой. Пусть S2 – множество таких точек v0V, для которых найдется такое u0U, что точка (u0,v0) является седловой. Тогда множество седловых точек равно декартовы произведению S1S2. Лемма. Если U и V – компактные множества, а функция g:UVR непрерывна, то множество седловых точек игры <U,V,g> замкнуто. Доказательство. Пусть точки (u1,v1),(u2,v2),…,(un,vn) – седловые, и последовательность (u1,v1),(u2,v2),…,(un,vn) сходится к точке (u0,v0). Тогда для любых uU, vV и n выполняются неравенства g(u,vn)g(un,vn)g(un,v). Переходя в этих неравенствах к пределу при n и пользуясь непрерывностью функции f, получим g(u,v0)g(u0,v0)g(u0,v), что в силу произвольности u и v означает, что (u0,v0) – седловая точка.
Итак, предел любой последовательности седловых точек является седловой точкой. Значит, множество седловых точек замкнуто. ^ Множество седловых точек выпуклой игры выпукло Доказательство. Пусть (u0,v0). Тогда в обозначениях следствия к первой лемме данного раздела . Множество точек максимума вогнутой функции выпукло, значит выпукло множество ^ 1. Аналогично, множество точек минимума выпуклой функции выпукло, значит выпукло множество S2. Но тогда выпукло и их произведение. Лемма. (Независимость от посторонних альтернатив) Если (u0,v0) – седловая точка в игре <U,V,g>, а множество W содержит v0, а само содержится в V, то ситуация (u0,v0) является седловой точкой в игре <U,W,g>. Доказательство. По определению седловой точки , а по определению минимума . Значит на самом деле . Равенство непосредственно следует из определения седловой точки. Терминология (Теория особенностей) Примеры Пример: U=V=[–1,1], g(u,v)=(u–v)2 Пример: исследование игры фан-тан исходя из соображений симметрии
Задачи Докажите, что игра с матрицей имеет седловую точку тогда и только тогда, когда отрезок числовой прямой с концами a и d имеет, по крайней мере, одну общую точку с отрезком, ограниченным точками b и c. Выполняется ли в данном случае «принцип хрупкости хорошего»? Докажите, что игра с матрицей имеет седловую точку. Докажите, что если каждая 22 подматрица матрицы A имеет седловую точку, то матрица A также имеет седловую точку. Докажите, что игра с матрицей A=(aij) имеет цену в чистых стратегиях и найдите соответствующую седловую точку, если , где ai,bj – произвольные числа, ci, dj – положительные числа. Докажите, что игра <U,V,g> с функцией выигрыша имеет седловую точку, если a и c – функции непрерывные на компакте U, а b и d – функции непрерывные на компакте V, и, кроме того, c и d положительны. Докажите, что если множества U и V компактны, а функция g непрерывна, и если для любых u1,u2U, v1,v2V игра <{u1,u2},{v1,v2},g> имеет седловую точку, то и игра <U,V,g> имеет седловую точку. *** Докажите, что если каждая подматрица матрицы ^ имеет седловую точку, что и сама матрица A имеет седловую точку. Пусть задана антагонистическая игра с ml матрицей выигрыша A все элементы которой попарно различны. Докажите, что если существуют k,n>1 такие, что каждая kn подматрица, получающаяся отбрасыванием m–k строк и l–n столбцов, имеет седловую точку, то и игра с матрицей A имеет седловую точку. Приведите пример, показывающий, что в предыдущей задаче условие попарного различия всех элементов матрицы существенно. Пусть A – невырожденная nn матрица. Докажите, что если каждая подматрица размера n(n–1) имеет седловую точку, то матрица A также имеет седловую точку. *** Докажите, что для любых действительных чисел a,b,c,d игра с матрицей имеет цену p, которая удовлетворяет неравенствам max{min{a,b},min{c,d}}p max{min{a,c},min{b,d}} Докажите, что игра с матрицей A=(aij) имеет цену в чистых стратегиях и найдите соответствующую седловую точку, если А) aij=i–j; Б) aij=f(i)+g(j); В) , a,b,c,d – произвольные числа; Г) , a,b,c,d,e,f,g – произвольные числа Е) m=n и для любых i,j,k имеет место тождество aij+ajk+aki=0. Показать, что каждая из двух матриц и имеет седловую точку. Существует ли такое значение x, при котором выполняется соотношение А) p(A+B)<p(A)+p(B); Б) p(A+B)>p(A)+p(B); В) p(A+B)=p(A)+p(B), где p(A) – цена игра с матрицей A? *** Докажите, что в игре <U,V,g>, где U=V=[0,1], Существует ли седловая точка в игре <U,V,g>, где U=V=[0,1], ? Найдите и , если g(u,v)=(u–v)2 нет седловой точки. А) U=V=[0,1], g(u,v)=2u2–3uv+2v2; Б) U=[–2,3], V=[–1,2], g(u,v)=–u2+4uv–5v2+3u–2v; В) U=V=[0,1], g(u,v)=4uv2–2u2–v; Г) U=[,2], V=[/2,3/2], g(u,v)=ucosv–sinu; (*) Пусть U=V=[0,1] и . Докажите, что цена игры равна , а – седловая точка. Пусть U=V=[0,1]. Докажите, что при любых ,, игра <U,V,g> с функцией выигрыша g(u,v)=uv–u–v+ имеет седловую точку. Пусть U=V=[0,1]. При каких ,, игра <U,V,g> с функцией выигрыша g(u,v)=uv–u–v+ имеет седловую точку внутри квадрата UV? Пусть U=V=[0,1] и игра <U,V,g> имеет седловую точку (u0,v0), ледащую внутри квадрата UV. Докажите, что тогда . Пусть A1 и A2 – две положительно определенные pp матрицы, B – произвольная матрица и, наконец, a1,a2 – p-мерные векторы. Рассмотрим антагонистическую игру, в которой U=V=Rp , g(u,v)=–(A1u,u)/2+(Bu,v)+(A2v,v)+(a1,u)+(a2,v). Докажите, что эта игра имеет единственную седловую точку, и найдите ее. Пусть a1,…,an – положительные числа, а U={(u1,…,un): u1+…+un=1, u10,…,un0}. Найдите . Пусть a1,…,an – положительные числа, а U={(u1,…,un): u1+…+un=1, u10,…,un0}, V={(v1,…,vn): v1+…+vn=1, v10,…,vn0}, . Найдите и . Пусть U=V=[0,1], , где p и q убывающие непрерывные функции отображающие отрезок [0,1] на себя. Существует ли в этой игре седловая точка? Пусть U=V=[0,1], , где p и q убывающие непрерывные функции отображающие отрезок [0,1] на себя. Существует ли в этой игре седловая точка? Пусть p и q – непрерывные возрастающие функции, отображающие отрезок [0,1] на себя, U=V=[0,1], и Докажите, что в игре <U,V,g> нет седловой точки. Игрок 1 выбирает системы u из m точек отрезка [–1,1]. Одновременно игрок 2 выбирает систему v из n точек того же отрезка Функция выигрыша имеет вид . Найдите цену игры. Игрок А выбирает три точки A, B, C на окружности, а игрок Б выбирает точку X в круге, ограниченном этой окружностью. Цель игрока А состоит в максимизации суммы длин AX+BX+CX. Существует ли в этой игре седловая точка? Игрок А выбирает три точки A, B, C на окружности, а игрок Б выбирает точку X в круге, ограниченном этой окружностью. Цель игрока А состоит в минимизации суммы длин AX+BX+CX. Существует ли в этой игре седловая точка? Пусть U=V=[0,1], Найдите цену игры и -оптимальные стратегии игроков. Существует ли в этой игре седловая точка? *** Пусть U=V=[0,1], f и h – определенные на UV функции и Докажите, что игра <U,V,g> имеет седловую точку. (Указание. См. задачу (*)) Показать, что игра <U,V,g> с функцией выигрыша имеет седловую точку, если U и V – выпуклые компакты, функция f вогнута по u, выпукла по v и положительна, а функция h выпукла по u, вогнута по v и положительна. Найдите вероятность того, что игра с матрицей A=(aij) имеет седловую точку, если aij – независимые случайные величины, имеющие одну и ту же плотность распределения. Рассмотрим семейство игр с фиксированными множествами стратегий U и V и непрерывными функциями выигрыша. Снабдим это семейство метрикой, определив расстояние между играми Г1=<U,V,g1> и Г2=<U,V,g2> условием . Докажите, что множество игр, имеющих седловую точку, замкнуто. *** Докажите, что всякую непрерывную функцию можно представить как разность двух выпуклых. ф Литература Васин А.А., Морозов В.В. Теория игр и модели математической экономики. М.:МАКС Пресс, 2005. Мулен Э. Теория игр с примерами из математической экономики. М.: Мир, 1985. 233342.doc 13.10.2011
Добавить документ в свой блог или на сайт
|