Re: Задачка по теории игр

seregaohota

Наверное на верхнем этаже первый игрок ходит (выбирая левый или правый путь с разной вероятностью а на нижнем - второй (аналогично).
Получишь матрицу платежей или как её там размером 2 на 2 и вперёд - простейший случай теории игр. Подписи у путей 1,2,...,6 очевидно для мебели. Кроме нижней строчки ничего не нужно. Можешь график z выигрыша(проигрыша) 3d нарисовать от вероятностей x и y обе на отрезке [0,1] (в углах квадрата значения 1, -1, 2, -3 )
z = (1-y 1(1-x) + 2x ) +
   + y (-1(1-x) - 3x )
Если я правильно перепутал, ищи {dz/dx=0, dz/dy=0} это и будет минимах или максимин и нужная тебе седловая точка в смешанных стратегиях. А вообще я не спец и давно это мельком смотрел, так что sorry если что. Может числа с точностью до транспонирования поставил, и чему там x получится равен - вероятности 1 игрока выбрать левый (правый) путь или наоборот 2-го. Короче книжку найди.

Goodnight18

для меня как раз главная проблема - привести это к матричному виду, дальше я умею решать

seregaohota

Что-то я там чушь написал сначала про седловую точку, написав про 2 производную d^2z/dy, она там естественно везде постоянна. Я перередактировал предыдущее сообщение. Седловая точка конечно решение системы уравнений
dz/dx = 0
dz/dy = 0
Чтобы матрицу получить рассуждаем так. Допустим с вероятностью p_1 = x первый игрок выбирает левую дорогу, тогда правую он выбирает с вероятностью q_1 = 1-x, аналогично 2-й игрок независимо (и ничего не зная о выборе первого) выбирает левый путь с вероятностью p_2 = y, а правый с q_2 = 1-y.
Для независимых событий P(AB)=P(A)*P(B). Если, например, событие A={первый ушёл налево} P(A)=x, В={второй ушёл налево}, P(B)=y, то при наступлении A*B первый игрок выиграет z=1*x*y, а при наступлении неA*B первый игрок выиграет z=2*(1-x)*y, и т.д. Вообще у нас \Omega = A*B + неA*B + A*неB + неA*неB Отсюда выигрыш 1 игрока
z = x * ( 1*y - 1*(1-y +
   + (1-x)*( 2*y - 3*(1-y
Раскрыв скобки z = -3 x y + 2 x + 5 y - 3. Дальше 1 игрок рассуждает примерно так: 2-й знает, что если он возьмёт p_2=y то я распоряжаясь своим управлением p_1=x буду стараться максимизировать выигрыш, т.е. при фиксированном y найду max_x z, ему надо мой выигрыш минимизировать, т.е. я получу на руки min_y max_x z. Для второго игрока рассуждения с точностью наоборот, ну или его выигрыш=-z и тогда и получаем перестановку операций мин/макс: первому игроку к выдаче max_x min_y z. Ну или что-то в этом роде если как обычно не перепутал ничего, несколько лет назад это мельком видел и книжку не помню, по памяти пишу.
Они между собой равны min_y max_x z = max_x min_y z в седловой точке (решение игры)
dz/dy=0 => -3 x + 2 = 0 x=2/3
dz/dx=0 => -3 y + 5 = 0 y=5/3
естественно седловой точки в данной задаче при твоих исходных данных не оказалось, т.к. x и y должны быть от 0 до 1. Если бы в исходной картинке на углах квадрата на одной диагонали были числа больше, чем на другой, то седловая бы точка оказалась бы внутри квадрата 0<x<1, 0<y<1. У тебя бы z над одной диагональю (подстановка y=x) и над другой (подстановка y=1-x) z оказалась бы параболой, одна рогами вверх, другая вниз. А при твоих исходных данных это не выполнено.
Или может я постановку задачи неправильно понял вообще и ничего даже отдалённо по делу не сказал. Надо трясти того, кто задачу составил, что там имелось в виду и какие там смыслы на этой картинке.
А может это игра против природы, тогда у тебя нет никаких x и y кроме 0 и 1 и никакого квадрата возможных решений нет - только 4 угла квадрата. Тогда на любой мой выбор x=0 или x=1 я должен рассчитывать, что природой реализуется наихудший вариант эксплуатации (представляю проектирование в предположении, что природа стоздаст нам благоприятные условия ).
Т.е. если это задача в чистых стратегиях, тогда надо идти налево - а природа ответит направо и мы получим выигрыш z=-1, и это хорошо что не так много проиграли, а то вышло бы z=-3.

Goodnight18

О - спасибо за такой развернутый ответ! Но там вроде все гораздо проще, седловая точка в итоге есть и соответствует исходу -1.

seregaohota

седловая точка в итоге есть и соответствует исходу -1

Ну максимум гладкой функции в замкнутой области (на отрезке или квадрате) может достигаться не во внутренней точке, а на границе (на концах отрезка и т.п. и его максимумом называют, независимо от того сколько и каких там производных=0, или вообще ни одной. Но что седловую точку - первый раз слышу. По мне седловая точка - это как на коне, чтобы можно сидеть было, свесив ноги по сторонам, а спереди и сзади парабола рогами вверх.
Знал бы книжку подробно бы не писал, просто ссылку бы кинул. Посмотрев вокруг отловил несколько, но все научные, а не по задачкам на пальцах. Библиотека должна помочь. Может в какой серии для физматкружка что было или в журнале каком, фиг знает. Визуально пару страниц помню про то, что тут впаривал, а где оно - нет. Подвернётся - скажу.
Оставить комментарий
Имя или ник:
Комментарий: