Тигры, контрольная 1

Материал из eSyr's wiki.

Перейти к: навигация, поиск

Содержание

Описание

в 2012 году лектор дал всего две задачи. В обеих был параметр N, который на самом деле мало на что влиял. Его надо было посчитать как сумму длин составляющих вашего ФИО, то есть для Потапенко Виктор Алексеевич N = 25. Оценка складывалась из 2 за присутствие и по 1,5 за каждую из задач (за каждый из трех подпунктов первой задачи по 0,5). При неправильно посчитанном N лектор ставил 2. В проходе аудитории (П8) стоял стол, который мешал ходить, и, возможно поэтому, лектор не ходил и не проверял валидность конспектов, отсутствие телефонов и пр. На все давалось примерно 20 минут

Теория

Седловые точки

Седловая точка матрицы - это формально такой элемент матрицы, что в своем столбце он самый большой (один из самых больших, т.е. не строго >), а в своей строке он один из самых маленьких. Например в матрице

Изображение:Tig2.png

седловая точка - это элемент в первом столбце второй строке, так как он >= всех остальных элементов первого столбца и <= всех остальных элементов второй строки. Довольно просто показать, что если у матрицы несколько седловых точек, то все их значения равны. Для поиска всех седловых точек в матрицах большой размерности не нужно рассматривать каждый элемент отдельно, можно воспользоваться алгоритмом, опирающимся на вспомогательную теорему. Работу алгоритма покажем на примере поиска всех седловых точек матрицы

Изображение:Tig3.png

Соберем наименьшие значения по всем строкам, получим (-4, 2, 2, -3). Также соберем наибольшие значения по всем столбцам (7, 2, 7, 2). Проверим, равно ли наибольшее из чисел первого набора наименьшему числу из второго набора. В нашем случае это так и это число 2. Если бы оказалось, что максимум первого набора меньше, чем минимум второго, то седловых точек не было бы. А ситуации, что максимум первого набора больше минимума второго вообще быть не может, доказывается отдельно. Итак, теперь посмотрим, на каких позициях стоят 2-ки в наших наборах. В первом это {2, 3}, а во втором это {2, 4}. На произведении этих множеств и располагаются все седловые точки (то есть {2, 3} X {2, 4} = { {2, 2}, {3, 2}, {2, 4}, {3, 4} } )

Изображение:Tig4.png

Но причем здесь теория игр? Дело в том что при игре один-на-один, когда интересы игроков прямо противоположны мы пользуемся матрицами стратегий и понятием седловых точек. Например при игре в "камень ножницы бумага" матрица стратегий выглядит так

Изображение:Tig5.png

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

Изображение:Tig6.png

И на пересечениях стратегий размер выигрыша первого игрока в рублях. То есть, если первый игрок выбрал бумагу и второй игрок выбрал бумагу, то второй платит первому 2 рубля. А если первый игрок выбрал ножницы, а второй камень, то первый игрок платит второму 1 рубль. Понятно, что первый игрок сразу же поймет, что надо все время показывать бумагу, так как тогда он будет только выигрывать. А второй, стараясь проиграть меньше, будет показывать камень, так как показав камень, он проиграет рубль, а не два. Как вы наверное уже догадались, точка в первой строке втором столбце - седловая (можете проверить). Игроки в погоне за выгодой будут выбирать стратегии так, что на их пересечении будут находиться седловые точки. А значение в этой точке (в данном случае 1) называется значением игры. Тройка {оптимальная стратегия Игрока 1, оптимальная стратегия Игрока 2, значение игры} называется решением игры. В нашем случае это {1, 2, 1} (или {Б, К, 1} что тоже самое).

Но мы довольно сильно исказили матрицу стратегий, а значит и правила, игры "камень ножницы бумага". Редкий человек захочет участвовать в ней в роли Игрока 2. Наши коррективы сделали игру несправедливой. Наличие седловой точки, как правило, свидетельствует о несправедливости игры

Смешанные стратегии

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

Изображение:Tig7.png

Методы решения матричных игр

Графический алгоритм показан на примере решения второй задачи из контрольной.

Также существует способ выкидывать неинформативные строки и столбцы из матрицы стратегий. Для этого нам нужно понятия слабого доминирования и выпуклой комбинации:

Вектор a слабо доминирует вектор b, если любой i-ый элемент а больше или равен i-му элементу b.

Выпуклой комбинацией называет линейную комбинацию векторов, в которой коэффициенты неотрицательны и в сумме дают единицу. Например 0.2a + 0.3b + 0.5c это выпуклая комбинация векторов a, b и c

Итак, строку мы можем выкинуть, если существует выпуклая комбинация остальных строк, слабо доминирующая эту строку. А столбец мы можем выкинуть, только если он слабо доминирует какую-нибудь выпуклую комбинацию остальных столбцов.

Изображение:Tig8.png

Личные инструменты
Разделы