gt_lec3_lp

Сегодня посмотрим, как задача ЛП используется в ТИ.

Была теорема Фон Неймана о том, что в смешанных стратегиях седловая точка есть всегда.

max {x} min {y} xAy = min {y} max {x} xAy = v

Посмотрим, как свести игру к задаче линейного программирования.

О двойственных задачах

    Прямая задача xA >= omega, x >= 0, x u -> min
    Двойственная задача y omega -> max, Ay <= u, y > 0.
    
    Если обе задачи имеют решение, то они совпадают.
    
    (один из вопросов на зачёте)
    
    1) Допустим u = (1, 1, ..., 1) in R^m
                w = (1, 1, ..., 1) in R^n
                
       Предполагаем, что в матрице только положительные числа (если это не так, то можно преобразовать).
       exists x: xA >= w (потому что x_i > 0)
       
       Для второй задачи решение -- y = (0, 0, ..., 0).
       
       x- u = y- w = 1/v > 0
       
       Рассмотрим x* = x- * v и y* = y- * v.
       Покажем, что это оптимальные стратегии.
       
       x* * u = (x- * u) v = (x- * w) v = y* u = 1.
       
       x* = x- v >= 0
       y* = y- v >= 0
       
       Мы показали, что эти векторы могут использоваться в качестве смешанных стратегий.
       
    2) Нужно показать, что цена игры будет v.
    
       Нужно вычислить выигрыш игрока 1, когда каждый из игроков использует оптимальную стратегию.
       
       K(x*, y*) = x* A y* = (x- A y-) v^2
       
       1/v = w y- <= (x- A) y- = x- (A y-) <= x- u = 1/v
       
       x- A y- = 1/v
       
       K(x*, y*) = 1/v * v^2 = v
       
    Доказательство конструктивное и показывает, как свести игру к задаче ЛП.
    
        1) Записать матрицу A' = A + B, B -- все элементы точно положительные, чтобы A' была положительной.
        
        2) Решить задачу ЛП: min (x u), xA >= u, x >= 0
           и двойственную:   max (y w), Ay <= u, y >= 0
           
        3) u = (1, 1, ..., 1)
           w = (1, 1, ..., 1)
           
           x* = x- / v, y* = y- / v
           
        4)  v'A = 1/v - beta
        
    Простой пример
    
        A = 4 0 
            3 2
            
        min(xi1 + xi2)
        4xi1 + 3xi2 >= 1
        2xi2 >= 1
        xi1 >= 0, xi2 >= 0
        
        max(et1 + et2)
        4et1 <= 1
        3et1 + 2et2 <= 1
        et1 >= 0, et2 >= 0
        
        Решается симлекс-методом.
        
Игра Мора

    Два игрока одновременно выставляют один, два или три пальца и одновременно выкрикивают число в попытке угадать число противника.
    Если угадал только один, то он получает от второго сумму, равную сумме числа показанных пальцев. Если нет, то никаких выплат не происходит.
    
    Упростим до 1 и 2, без 3:
            
            (1, 1)  (1, 2)  (2, 1)  (2, 2)
    (1, 1)    0       2      -3       0
    (1, 2)   -2       0       0       3
    (2, 1)    3       0       0      -4
    (2, 2)    0      -3       4       0
    
    В первую очередь проверим, нет ли седловой точки в чистых стратегиях.
    Нижняя цена игры -- max of mins = -2 = alpha
    Верхняя цена игры -- min of maxs = 2 = beta
    alpha != beta
    
    Прибавим к матрице 5, чтобы получить положительную:
    
    5  7  2  5
    3  5  5  8
    8  5  5  1
    5  2  9  5
    
    Запишем задачу ЛП:
    
    Выписывается система, справа стоят единицы.
    sum {x_i} -> min
    5x1 + 3x2 + 8x3 + 5x4 >= 1
    7x1 + 5x2 + 5x3 + 2x4 >= 1
    2x1 + 5x2 + 5x3 + 9x4 >= 1
    5x1 + 8x2 + 1x3 + 5x4 >= 1
    x1, x2, x3, x4 >= 0
    
    Классический симлекс-метод предполагает решение задачи максимизации, поэтому это для него обратная задача, но на самом деле неважно.
    
    Хотим избавиться от неравенств.
    Вводим переменных по числу неравенств.
    
    5x1 + 3x2 + 8x3 + 5x4 - x5 = 1
    7x1 + 5x2 + 5x3 + 2x4 - x6 = 1
    2x1 + 5x2 + 5x3 + 9x4 - x7 = 1
    5x1 + 8x2 + 1x3 + 5x4 - x8 = 1
    
    x1, x2, x3, x4 -- свободные
    x5, x6, x7, x8 -- базисные
    
    Все свободные переменные (x1, x2, x3, x4) приравниваются нулю -- получается т.н. опорное решение
    (0, 0, 0, 0, -1, -1, -1, -1)
    
    Далее выписывается целевая функция в форме Такера -- перед всеми переменными должны стоять минусы.
    
    z = 0 - (- sum x_i)
    
    Составляется таблица:
    
    Заполняется на основе системы
    
            план  x1   x2   x3   x4   x5   x6   x7   x8
        x5   -1   5    3    8    5    -1   0    0    0
        x6   -1   7    5    5    2    0    -1   0    0   <--
        x7   -1   2    5    5    9    0    0    -1   0
        x8   -1   5    8    1    5    0    0    0    -1
        z     0   -1   -1   -1   -1   0    0    0    0
                  ^
                  |
        
        Дальше метод исключения переменной. Находится ключевой столбец -- по минимальному по модулю отрицательному в строке с z. Если все одинаковые, берём любой.
        Затем -- ключевая строка -- по минимуму модуля отношения базисного плана к элементу ключевого столбца.
        
        -1/5,  -1/7,  -1/2,  -1/5

        И нужно исключить в данном случае x1 -- он отождествится с x6.
        
        Ключевую строку делим на элемент в ключевой строке и столбце.
        
        a'ij = aij - akj * ail / akl
        (k, l) -- индекс ключевого элемента.
        
Задача: Пусть у нас есть матрица игры [m x n], элементы матрицы являются независимыми одинаково распределёнными случайными величиными с плотностью вероятности f(x).
        Найти вероятность нахождения в такой матрице седловой точки.

    Делаем предположение о том, что все числа различны и являются целыми от 1 до m*n.
    Что такое седловая точка? Число, самое маленькое в строке, но при этом самое большое в столбце.
    
    Число возможных расстановок чисел в матрице -- (m*n)!. Количество способов расположить седловую точку -- (m + n - 1).
    
    Решить дома.
    
Особенность симметричных игр -- оптимальные стратегии первого и второго игрока совпадают.

    Теорема о смешанных равновесиях в симметричных играх.
    
        (sigma, sigma)
        sigma = (p1, ..., pm), p_i != 0 (вполне смешанная стратегия)
        Симметричный профиль является смешанным равновесием Нэша тогда и только тогда, когда
        A sigma = lambda (1, 1, ..., 1)^T, lambda = K(sigma, sigma).
        
        sigma = lambda A^-1 (1, 1, ..., 1)^T
        
    Теорема о диагональных играх
    
        a11 0 0 0 0 .. 0 
        0 a22 0 0 0 .. 0
        ..  ..  ..  .. 
        0 0 .. 0 0 0 ann
        
        В диагональной игре оптимальная стратегия вседа вполне смешанная.