Теория игр. Оуэн (1971) (1186151), страница 20
Текст из файла (страница 20)
Рассмотрим точку Р' = (х, — 2е, хе + е, х, + е); тогда — с учетом (4.6.1!) — мы имеем / сЬ= '/з+ 2е ~ /с(з — е ~ /с(в — е ) /дз. А цв цс с', 2 сз Прямая Еь очевидно, не пересекает множество М, так как на ней значение первой координаты меньше, чем в точке Р, где это значение достигает минимума в М. С другой стороны, хотя бы с е одна из прямых Лз и Лз должна (при достаточно малом е) пересекать М, так как по предположению М связно и не может лежать полностью в области, ограниченной прямыми Ез, Ез и сторонами треугольника (эта область в точности совпадает с множеством Р).
Отсюда следует, что /с(а< 1/з лшвшс' и поэтому Е(р, Р') < О. Но это означает, что р не оптимальна. Таким образом, замыкание множества М должно касаться трех сторон треугольника. Поэтому мы видим, что минимальные значения хь хз и хз на множестве М должны быть равны нулю. Чтобы найти максимальные значения, заметим прежде всего, что если М связно, то каждая прямая х~ = а при а, лежащих между нулем и максимальным значением г, координаты хь пересекает М. Но это значит, что интеграл от / по множеству М равен г,й.
Следовательно, г1 = 1/й. Аналогично, максимальным значением хз и хз (на М) будет г = 1//з. Таким образом, мы нашли, что множество М вписывается в шестиугольник, показанный на рис. 1Ч.6.3 и определенный неравенствами О з1; х, ~ г, 1= 1, 2, 3. Пусть теперь Р— точка (в замыкании М), для которой хз = г.
Можно заметить, что Е(р, Р) =Е(р, Я), где Я = (О, 1 — г, т), так как это выражение постоянно вдоль прямой РО, На рисунке пунктирная прямая, проходящая через Я, Ге. УК Беснане«ные игры 106 делит М на две части. Та часть М, которая лежит выше этой прямой, состоит из точек, которые «проигрывают» точке ф часть, которая лежит ниже этой прямой, состоит из точек, которые «выигрывают» у Я. Следовательно, интеграл от / по верхней части М должен быть равен 1/2. Далее, все прямые хе = а при а из интервала (О, 1 — г) пересекают эту часть; поэтому интеграл от / по этой части равен й(! — г). Следовательно, (1 — г)/г = '/е, так что г = '/3. (4.6.!4» ц!-г, О ! -х' /(х'+ у') е(у о (4.6.15) постоянен. Если мы произведем замену переменных у =с )/à — х~, /( = хе + уе = х'+ !е — !ехе, то получим Таким образом, мы нашли, что М должно быть связным множеством, вписанным в шестиугольник О ( х» -= е/е.
Функция / такова, что она равна нулю вне множества М и положительна на М, а интеграл от! е вдоль любой прямой, па- (1- г, О, г) ...,...,... (О, 1- г, г) раллельной одной из сторон 'У' треугольника и пересекаюе: щей М, равен 3/2. Эти соображения еще не определяют / или М одно- (Г,О,1-Г),::::::::,"::::'р~",::..":,.:,:.:.'',::.".:.':,'...:.,,-',"'::::,:: (О Ге! Г! ЗиаЧНО; ВООбщс ГОВОря, Су- ществует много оптимальй ных стратегий. Мы можем, например, считать, что М— ( ) (! г г О) круг (ясно, что шестиугольник правильный), а / является функцией, зависящей только от расстояния от центра круга.
Тогда, если / выбрана так, что ее интеграл одинаков вдоль всех прямых одного направления, то очевидно, что он одинаков вдоль всех прямых, которые пересекают М. Рассмотрим теперь круг хе+ у' ~ 1. Нам нужно найти такую функцию /(/!), что для любого х ен( — 1,!) интеграл Задачи )07 н интеграл (4.6.15) примет вид ! ~ )/~ — х'/ (х'+ /г — /гхг) Ж. е По условию этот интеграл не зависит от х, поэтому мы продифференцируем его по х и положим производную равной нулю. Производная, разумеется, представляет собой интеграл; достаточно положить подинтегральное выражение равным нулю. Таким образом, мы получаем дифференциальное уравнение х/ ® = 2х (1 — хг) (1 — !г) /' (/!), которое приводится к виду 1(Й) = 2 (1 — )т) /' ()т).
Решение этого уравнения есть Применим это к нашей задаче. Мы тем не менее должны помнить, что радиус круга, с которым мы имеем дело, равен только третьеи части единицы. Таким образом, мы имеем /(х„хг хз) = С/')/1 — 9г', где Г = (х! — /3) + (Хг — /3) + (хз /3) (4.6.16) Константу С легко вычислить, вспомнив, что интеграл вдоль прямой должен равняться з/г, это дает С = з/з, Таким образом, оптимальная стратегия равна / = 9/(2 )' à — 9гг) (4.6.17) для точек таких, что г ~ '/з, и равна 0 вне этого множества.
Задачи (, Пусть К(х,у) — ядро игры на единичном квадрате. Предположим, что К имеет непрерывные производные л-го порядка и что д"К/ду" ~ О на всем единичном квадрате. Показать, что игрок П имеет оптимальную стратегию, в которой используется не более чем л/2 точек (прн условии, что если используется концевая точка интервала, то она считается за половину точки). а) Предположим сначала, что д" К/ду" ) О. Предположим, что г"(х) является оптимальной стратегией игрока 1, Показать, что любая стратегия, оптимальная против Е, может использовать не более л/2 точек. Гд /И Бесконечные икры !08 б) ВУдем считать тепеРь, что д"К/дУ" ~ О.
ПУсть Еа(х, У)= К(х,У)+ аУ", где в > О. Пусть ба — оптимальная стратегия игрока П в игре с ядром Бю Тогда если бо является пределом стратегий бе, то 6, будет оптимальной стратегией игрока П в игре с ядром К. (Аналогично, если Ре — оптимальная стратегия игрока 1 в игре с ядром Ьа, а Ро является пределом Ра при а -+ О, то Р,— оптимальная стратегия в игре с ядром К.) 2. Показать, что если функция К непрерывна н Кгг ~ О на всем единичном квадрате, то игрок ! имеет оптимальную смешанную стратегию, использующую не более двух точек.
а) Показать, что игрок П имеет оптимальную чистую стратегию уь б) Если Р— оптимальная стратегия, то К(х,у,) = о для любой точки х, используемой в Р. в) Если игрок ! не имеет оптимальной чистой стратегии, то он должен иметь две такие чистые стратегии «1 и хь что К„(хь уа) > О и К„(хь уо) < О.
г) Игрок ! имеет оптимальную смешанную стратегию, использующую только х~ и хз. 3. Пусть Р(х, у) ~ ~~»', а хГу/-ядро игры на единичном квадрате. г-а /-о а) Если две функции распределения Р,(х) и Рг(х) имеют одинаковые моменты, т.'е. если для 1 = 1, ..., гл 1 1 Р1П-~ «'УР,(х)- ~ «'бР,(х)-Р1г1, а о то Р, оптимальна тогда и только тогда, когда оптимальна Рз. Аналогично, если 6,(у) и бз(у) имеют одинаковые моменты, то 6~ оптимальна тогда и только тогда, когда оптимальна бз. б) Момеиты Р<о любой функции распределения содержатся в выпуклой оболочке кривой, лежащей в т-мерном пространстве и заданной уравнениями г~ = г'.
в) Игроки 1 и П имеют оптимальные стратегии, использующие самое большее т н н точек соответственно. г) Выразить функцию Е(Р, 6) через в1оменты РО1 н бпч Показать, что оптимальные стратегии обоих игроков можно вычислить, решая некоторую систему алгебраических уравнений.
4. Тот факт, что игра на единичном квадрате имеет непрерывное или даже рациональное ядро, ие дает гарантии, что игроки имеют оптимальные стратегии, использующие только конечное число точек. а) Если К(х,у) — непрерывная рациональная функция и игрок 1 имеет оптимальную стратегию, использующую не более гл точек, то зта оптимальная стратегия может быть получена из решения системы алгебраических уравнений.
б) Если функция К(х,у) рацяональна, а о трансцендентно, то ни один из игроков не имеет оптимальных стратегий, которые используют лишь конечное число точек. в) Игра с ядром К(х, у) (1+х) (! +у) (1 — ху)/(1+ху)з имеет оптимальные стратегии Р (х) = (4/п) агс1п )/ х, б (у) (4/и) агс(д "г' у, в значение игры равно 4/и. Задачи 109 5. Игра даже с «очень регулярным» ядром не обязательно имеет значение. Рассмотрим ядро — 1, если х<у<х+Чз К(х, у) О, если х-у или у х+'/з, + 1 в противном случае. а) Для любой стратегии Е(х) существует такое у, что Е(р,у) '/з. (Рассмотреть два случая: Е(з/г — О) йз Чз и г (з/з — О) > Чз.) б) Для любой 6(у) существует такое х, что Е(х, 6) ~ '/,.
(Рассмотреть три случая: (!) 6(1 — 0) я '/тз (й) 6(1 — 0) <з/г, а 6('/, — О) < '/зз (1й! 6(! — 0) < < з/г, а 6('/з — 0) ~ '/з.) в) Таким образом, оз "Я '/з, а оы ~'/ь Показать, что в действительности значения '/з и '/, достигаются на стратегиях Ез и 6" соответственно, где Е» использует лишь О, '/г и 1, а 6' — лишь '/з, '/з и 1. Найти вероятности, с которыми эти точки используются в Е» и 6'. ' б. Найти значение и оптимальные стратегии игры с ядром А (х, у) = О, 2х — у+ ху, если я<у, если х-у, х-2у-ху, если х>у.
7. Найти метод решения игры-дуэли, з которой каждый игрок имеет две пули вместо одной. Предполагается, что дуэль бесшумна, так что ни один из игроков не знает, выстрелил лн другой (если тот промахнулся). 8. Пусть сз, сз, сз — положительные числа, удовлетворяющие строгому «неравенству треугольника» сз+ с, > с». Рассмотреть следующую игру, Игрок 1 выбирает неотрицательные числа (хьхахз), сумма которых равна 1. 7зналогично игрок П выбирает (уз, уз, уз). Функция выигрыша А (х, у) с, а!цп (хз — уз) + сг 3!Кя (хз — уз) + сз зуйп (хз — уз). Найти оптимальные стратегии. 9. Даже игра с рациональной функцией выигрыша может иметь сингулярное решение.
Рассмотрим функцию Кантора С(х), которая удовлетворяет соотношениям С (х/3) С (х)/2, С (х) + С (1 — х) - 1, если хз ~ хь то С(х,) ~ С(хг), а) Для любой интегрируемой функции / ! Чз 1 [ /(х) аС (х) [ / (х) дС (х) + [ /(х) з/С (х). о о зг б) Если / — произвольная непрерывная функция, то 1 [2/(х) — / (! — х/3) + /(х/3)) з!С (х) О. о в) Функция «О /((х у) Хз,"~ (1/2)л [2хл (1 х/3)л (х/3)л) [2ул (1 у/3)л (у/3)л) л о 110 Гл, ! К Бесконечные игры непрерывна н рациональна для 0 в х И 1, 0 ~ у ~!. (Для доказательства нужно раскрыть каждое слагаемое и привести подобные члены,) Кроме того, С(х) и С(у) — оптимальные стратегии обоих игроков.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
